path: root/system/kernel/pdp_type.c

/*
 *   Pure Data Packet system implementation. : code for handling different packet types
 *   Copyright (c) by Tom Schouten <pdp@zzz.kotnet.org>
 *
 *   This program is free software; you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation; either version 2 of the License, or
 *   (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program; if not, write to the Free Software
 *   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 *
 */


/* this file contains type handling routines */

#include <stdarg.h>
#include <string.h>
#include <pthread.h>
#include "pdp_list.h"
#include "pdp_symbol.h"
#include "pdp_packet.h"
#include "pdp_post.h"
#include "pdp_type.h"
#include "pdp_mem.h"
#include "pdp_debug.h"


// debug
#define D if (0)


static t_pdp_list *conversion_list;

#define INIT_MAX_CACHE_SIZE 32

static t_pdp_list *cached_conversion_list;
static int max_cache_size;

/* mutex */
static pthread_mutex_t pdp_conversion_mutex;
static pthread_mutex_t pdp_cache_mutex;



/* convert a type to a list */
t_pdp_list *pdp_type_to_list(t_pdp_symbol *type)
{
#define TMPSIZE 1024

    char *c = type->s_name;
    char *lastname = c;
    int n = 0;
    char tmp[strlen(type->s_name)+1];
    t_pdp_list *l = pdp_list_new(0);

    while(*c){
	if (*c == '/'){
	    strncpy(tmp, lastname, n);
	    tmp[n] = 0;
	    pdp_list_add_back(l, a_symbol, (t_pdp_word)pdp_gensym(tmp));
	    c++;
	    lastname = c;
	    n = 0;
	}
	else{
	    c++;
	    n++;
	    PDP_ASSERT(n < TMPSIZE);
	}
    }
    pdp_list_add_back(l, a_symbol, (t_pdp_word)pdp_gensym(lastname));

    return l;
}


/* get the description symbol. */
t_pdp_symbol *pdp_packet_get_description(int packet)
{
    t_pdp *header = pdp_packet_header(packet);

    if (!header) return pdp_gensym("invalid");
    else if (!header->desc){

	/* since every packet is obliged to have a description, this is an error */
	pdp_post("ERROR: pdp_packet_get_description: packet %d has no description.", packet);
	pdp_packet_print_debug(packet);
	return pdp_gensym("unknown");
    }
    else return header->desc;
}



/* this runs a conversion program */
int _pdp_type_run_conversion_program(t_pdp_conversion_program *program,
	 			    int packet, t_pdp_symbol *dest_template)
{
    /* run a conversion program:
       treat the source packet as readonly, and cleanup intermediates, such
       that the net result is the production of a new packet, with the
       source packet intact. */

    int p, tmp;
    t_pdp_atom *a;
    t_pdp_conversion_method m;

    // run the first line of the program
    a = program->first;
    m = a->w.w_pointer;
    D pdp_post("DEBUG: _pdp_type_run_conversion_program: method = %x", m);
    p = m(packet, dest_template);
    D pdp_post("DEBUG: _pdp_type_run_conversion_program:");
    D pdp_post("        packet returned = %d, type = %s", 
	       p, pdp_packet_get_description(p)->s_name);

    // run the remaining lines + cleanup intermediates
    for (a=a->next; a; a=a->next){
	m = a->w.w_pointer;
	D pdp_post("DEBUG: _pdp_type_run_conversion_program: next method ptr = %x", m);
	tmp = m(p, dest_template);
	pdp_packet_mark_unused(p);
	p = tmp;
    }
    return p;
}


/* find a conversion program */
t_pdp_conversion_program *
_pdp_type_find_conversion_program(t_pdp_symbol *src_pattern, t_pdp_symbol *dst_pattern)
{
    t_pdp_conversion *c;
    t_pdp_atom *a;
    t_pdp_conversion_program *retval = 0;

    /* lock conversion list */
    pthread_mutex_lock(&pdp_conversion_mutex);

    for (a = conversion_list->first; a; a=a->next){
	c = a->w.w_pointer;
	/* can be a wildcard match */
	if (pdp_type_description_match(src_pattern, c->src_pattern) &&
	    pdp_type_description_match(dst_pattern, c->dst_pattern)) {
	    /* found a program */
	    D pdp_post("DEBUG: _pdp_type_find_conversion_program: found: %s -> %s",
		       c->src_pattern->s_name, c->dst_pattern->s_name);
	    retval = c->program;
	    goto gotit;
	}
    }

    /* no conversion program was found */
    retval = 0;
 gotit:

    /* lock conversion list */
    pthread_mutex_unlock(&pdp_conversion_mutex);
    return retval;
}

/* find a cached conversion program 
 if one is found it will be moved to the back of the queue (MRU) */
t_pdp_conversion_program *
_pdp_type_find_cached_conversion_program(t_pdp_symbol *src_pattern, t_pdp_symbol *dst_pattern)
{
    t_pdp_conversion *c, *c_tmp;
    t_pdp_atom *a;
    t_pdp_conversion_program *retval = 0;

    /* lock cached list */
    pthread_mutex_lock(&pdp_cache_mutex);

    for (a = cached_conversion_list->first; a; a=a->next){
	c = a->w.w_pointer;
	/* must be exact match */
	if ((src_pattern == c->src_pattern) &&
	    (dst_pattern == c->dst_pattern)) {

	    /* found a program */
	    D pdp_post("DEBUG: _pdp_type_find_cached_conversion_program: found: %s -> %s", 
		       c->src_pattern->s_name, c->dst_pattern->s_name);
	    retval = c->program;

	    /* make MRU (move to back) */
	    c_tmp = cached_conversion_list->last->w.w_pointer;
	    cached_conversion_list->last->w.w_pointer = c;
	    a->w.w_pointer = c_tmp;
	    goto gotit;
	}
    }

    retval = 0;

 gotit:


    /* un lock cached list */
    pthread_mutex_unlock(&pdp_cache_mutex);

    /* no conversion program was found */
    return retval;
}


/* conversion program manipulations */
void pdp_conversion_program_free(t_pdp_conversion_program *program)
{
    pdp_list_free(program);
}

/* debug print */
void _pdp_conversion_program_print(t_pdp_conversion_program *program)
{
    D pdp_post("_pdp_conversion_program_print %x", program);
    pdp_list_print(program);
}

t_pdp_conversion_program *pdp_conversion_program_new(t_pdp_conversion_method method, ...)
{
    t_pdp_conversion_program *p = pdp_list_new(0);
    t_pdp_conversion_method m = method;
    va_list ap;

    D pdp_post("DEBUG: pdp_conversion_program_new:BEGIN");

    pdp_list_add_back_pointer(p, m);
    va_start(ap, method);
    while (m = va_arg(ap, t_pdp_conversion_method)) pdp_list_add_back_pointer(p, m);
    va_end(ap);

    D pdp_post("DEBUG: pdp_conversion_program_new:END");
 
    return p;
}

t_pdp_conversion_program *pdp_conversion_program_copy(t_pdp_conversion_program *program)
{
    if (program) return pdp_list_copy(program);
    else return 0;
}

void pdp_conversion_program_add(t_pdp_conversion_program *program, 
				t_pdp_conversion_program *tail)
{ 
    return pdp_list_cat(program, tail);
}

/* conversion registration */
void pdp_type_register_conversion (t_pdp_symbol *src_pattern, t_pdp_symbol *dst_pattern, 
				   t_pdp_conversion_program *program)
{
    t_pdp_conversion *c = (t_pdp_conversion *)pdp_alloc(sizeof(*c));
    c->src_pattern = src_pattern;
    c->dst_pattern = dst_pattern;
    c->program = program;

    /* lock conversion list */
    pthread_mutex_lock(&pdp_conversion_mutex);

    pdp_list_add_back_pointer(conversion_list, c);

    /* unlock conversion list */
    pthread_mutex_unlock(&pdp_conversion_mutex);
    
}

/* register a cached conversion */
void pdp_type_register_cached_conversion (t_pdp_symbol *src_pattern, t_pdp_symbol *dst_pattern, t_pdp_conversion_program *program)
{

    /* create the new conversion */
    t_pdp_conversion *c = (t_pdp_conversion *)pdp_alloc(sizeof(*c));
    c->src_pattern = src_pattern;
    c->dst_pattern = dst_pattern;
    c->program = program;

    /* lock cached conversion list */
    pthread_mutex_lock(&pdp_cache_mutex);

    /* check size, and remove LRU (top) if the cache is full */
    while (cached_conversion_list->elements >= max_cache_size){
	t_pdp_conversion *c_old = pdp_list_pop(cached_conversion_list).w_pointer;
	if (c_old->program) pdp_conversion_program_free(c_old->program);
	pdp_dealloc(c_old);
    }
    
    /* add and make MRU (back) */
    pdp_list_add_back_pointer(cached_conversion_list, c);

    /* unlock cached conversion list */
    pthread_mutex_unlock(&pdp_cache_mutex);
}

/* convert a given packet to a certain type (template) */
int _pdp_packet_convert(int packet, t_pdp_symbol *dest_template)
{
    t_pdp_symbol *type = pdp_packet_get_description(packet);
    t_pdp_symbol *tmp_type = 0;
    int tmp_packet = -1;

    t_pdp_conversion_program *program = 0;
    t_pdp_conversion_program *program_last = 0;
    t_pdp_conversion_program *program_tail = 0;

    /* check if there is a program in the cached list, if so run it */
    if (program = _pdp_type_find_cached_conversion_program(type, dest_template))
	return _pdp_type_run_conversion_program(program, packet, dest_template);

    /* if it is not cached, iteratively convert 
       and save program on top of cache list if a conversion path (program) was found */

    // run first conversion that matches
    program = pdp_conversion_program_copy
	(_pdp_type_find_conversion_program(type, dest_template));
    program_last = program;
    if (!program){
	D pdp_post("DEBUG: pdp_type_convert: (1) can't convert %s to %s", 
		   type->s_name, dest_template->s_name);
	return -1;
    }
    tmp_packet = _pdp_type_run_conversion_program(program, packet, dest_template);
    tmp_type = pdp_packet_get_description(tmp_packet);

    // run more conversions if necessary, deleting intermediate packets
    while (!pdp_type_description_match(tmp_type, dest_template)){
	int new_packet;
	program_tail = _pdp_type_find_conversion_program(tmp_type, dest_template);
	if (!program_tail){
	    D pdp_post("DEBUG: pdp_type_convert: (2) can't convert %s to %s", 
		       tmp_type->s_name, dest_template->s_name);
	    pdp_packet_mark_unused(tmp_packet);
	    pdp_conversion_program_free(program);
	    return -1;
	}
	if (program_last == program_tail){
	    //pdp_post("ERROR: pdp_packet_convert: conversion loop detected");
	}
	program_last = program_tail;

	pdp_conversion_program_add(program, program_tail);
	new_packet = _pdp_type_run_conversion_program(program_tail, tmp_packet, dest_template);
	pdp_packet_mark_unused(tmp_packet);
	tmp_packet = new_packet;
	tmp_type = pdp_packet_get_description(tmp_packet);
    }

    // save the conversion program in the cache
    pdp_type_register_cached_conversion(type, dest_template, program);

    // return resulting packet
    return tmp_packet;
	
}

/* convert or copy ro */
int pdp_packet_convert_ro(int packet, t_pdp_symbol *dest_template)
{
    t_pdp_symbol *type = pdp_packet_get_description(packet);

    /* if it is compatible, return a ro copy */
    if (pdp_type_description_match(type, dest_template)) return pdp_packet_copy_ro(packet);

    /* if not, convert to a new type */
    else return _pdp_packet_convert(packet, dest_template);
}

/* convert or copy rw */
int pdp_packet_convert_rw(int packet, t_pdp_symbol *dest_template)
{
    t_pdp_symbol *type = pdp_packet_get_description(packet);

    /* if it is compatible, just return a rw copy */
    if (pdp_type_description_match(type, dest_template)) return pdp_packet_copy_rw(packet);

    /* if not, convert to a new type */
    else return _pdp_packet_convert(packet, dest_template);
}


/* this is a hack. type cache data: (a type description parsed into
   a pdp_list for fast comparison) should be setup when
   a packet symbol is created, but since that can be everywhere,
   we set it up on first use. type cache is permanent. */


static void _setup_type_cache(t_pdp_symbol *s)
{
    t_pdp_list *l = pdp_type_to_list(s); 
    if (!pdp_symbol_set_typelist(s, l))
	pdp_list_free(l); // list was already present -> free cached list

}

/* check if a type description fits a template
   this function is symmetric */
int pdp_type_description_match(t_pdp_symbol *description, t_pdp_symbol *pattern)
{
    int match = 0; // no match until all tests are passed

    t_pdp_atom *ad, *ap;
    t_pdp_symbol *wildcard = PDP_SYM_WILDCARD;

    PDP_ASSERT(pattern);
    PDP_ASSERT(description);

    /* same type symbol -> match */
    if (description == pattern) {match = 1; goto done;}

    /* check the description list */
    if (!(description->s_type)) _setup_type_cache(description);
    if (!(pattern->s_type))     _setup_type_cache(pattern);

    /* compare symbols of description list */
    for(ad=description->s_type->first, ap=pattern->s_type->first; 
	ad && ap; 
	ad=ad->next, ap=ap->next)
    {

	if (ad->w.w_symbol == wildcard) continue;
	if (ap->w.w_symbol == wildcard) continue;
	if (ad->w.w_symbol != ap->w.w_symbol) {goto done;} /* difference and not a wildcard */
    }

    /* ok if sizes are equal */
    if (! (ad || ap)) {match = 1; goto done;}

    /* one of the two is shorter, so the shortest list needs 
       to end with a wildcard to have a match */

    if (ap && description->s_type->last->w.w_symbol != wildcard) goto done;
    if (ad && pattern->s_type->last->w.w_symbol != wildcard) goto done;
    
    /* all tests passed: type templates match */
    match = 1;

 done:
    D pdp_post("DEBUG: testing match between %s and %s: %s", 
	   description->s_name, pattern->s_name, match ? "match" : "no match");
    return match;

}





/* setup method */
void pdp_type_setup(void)
{
    int i;

    // create mutexes
    pthread_mutex_init(&pdp_conversion_mutex, NULL);
    pthread_mutex_init(&pdp_cache_mutex, NULL);

    // create conversion lists
    cached_conversion_list = pdp_list_new(0);
    conversion_list = pdp_list_new(0);
    max_cache_size = INIT_MAX_CACHE_SIZE;




}