From 599a8e20c02fa48bab5102d15fab79dd6b631c95 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Pablo=20Mart=C3=ADn?= Date: Sun, 7 Sep 2003 21:39:37 +0000 Subject: Updating to last version of pdp 0.12.2 svn path=/trunk/externals/pdp/; revision=940 --- system/kernel/pdp_type.c | 501 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 501 insertions(+) create mode 100644 system/kernel/pdp_type.c (limited to 'system/kernel/pdp_type.c') diff --git a/system/kernel/pdp_type.c b/system/kernel/pdp_type.c new file mode 100644 index 0000000..c220269 --- /dev/null +++ b/system/kernel/pdp_type.c @@ -0,0 +1,501 @@ +/* + * Pure Data Packet system implementation. : code for handling different packet types + * Copyright (c) by Tom Schouten + * + * 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 +#include +#include +#include "pdp.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_hash_mutex; +static pthread_mutex_t pdp_conversion_mutex; +static pthread_mutex_t pdp_cache_mutex; + +#define HASHSIZE 1024 +static t_pdp_symbol *pdp_symhash[HASHSIZE]; + + +/* shamelessly copied from pd src and made thread safe */ +t_pdp_symbol *_pdp_dogensym(char *s, t_pdp_symbol *oldsym) +{ + t_pdp_symbol **sym1, *sym2; + unsigned int hash1 = 0, hash2 = 0; + int length = 0; + char *s2 = s; + while (*s2) + { + hash1 += *s2; + hash2 += hash1; + length++; + s2++; + } + sym1 = pdp_symhash + (hash2 & (HASHSIZE-1)); + + /* lock hash */ + pthread_mutex_lock(&pdp_hash_mutex); + + while (sym2 = *sym1) + { + if (!strcmp(sym2->s_name, s)) goto gotit; + sym1 = &sym2->s_next; + } + if (oldsym) sym2 = oldsym; + else + { + sym2 = (t_pdp_symbol *)pdp_alloc(sizeof(*sym2)); + sym2->s_name = pdp_alloc(length+1); + _pdp_symbol_clear_namespaces(sym2); + sym2->s_next = 0; + strcpy(sym2->s_name, s); + } + *sym1 = sym2; + + gotit: + + /* unlock hash */ + pthread_mutex_unlock(&pdp_hash_mutex); + return (sym2); +} + +t_pdp_symbol *pdp_gensym(char *s) +{ + return(_pdp_dogensym(s, 0)); +} + +/* convert a type to a list */ +t_pdp_list *pdp_type_to_list(t_pdp_symbol *type) +{ + char *c = type->s_name; + char *lastname = c; + char tmp[100]; + int n = 0; + 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_list_add_back(l, a_symbol, (t_pdp_word)pdp_gensym(lastname)); + + return l; +} + + +/* get the description symbol. this includes some compat transition stuff with a warning */ +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){ + + 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 post("DEBUG: _pdp_type_run_conversion_program: method = %x", m); + p = m(packet, dest_template); + D post("DEBUG: _pdp_type_run_conversion_program: 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 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 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 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) +{ + 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 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 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 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 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){ + 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 + 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); +} + + +static void _setup_type_cache(t_pdp_symbol *s) +{ + t_pdp_list *l = pdp_type_to_list(s); + pthread_mutex_lock(&pdp_hash_mutex); //lock to prevent re-entry + if (!s->s_type){ + s->s_type = l; + l = 0; + } + pthread_mutex_unlock(&pdp_hash_mutex); + if (l) pdp_list_free(l); +} + +/* 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 retval = 0; + + t_pdp_atom *ad, *ap; + t_pdp_symbol *wildcard = pdp_gensym("*"); + + + if (!(pattern)) post("PANICA"); + if (!(description)) post("PANICB"); + + + /* same type -> match */ + if (description == pattern) {retval = 1; goto done;} + + /* use the description list stored in the symbol for comparison */ + if (!(description->s_type)) _setup_type_cache(description); + if (!(pattern->s_type)) _setup_type_cache(pattern); + + if (!(pattern->s_type)) post("PANIC1"); + if (!(description->s_type)) post("PANIC2"); + + /* check size */ + if (description->s_type->elements != pattern->s_type->elements){retval = 0; goto done;} + + /* compare symbols of type list */ + for(ad=description->s_type->first, ap=pattern->s_type->first; ad; 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) {retval = 0; goto done;} /* difference and not a wildcard */ + } + + /* type templates match */ + retval = 1; + + done: + D post("DEBUG: testing match between %s and %s: %s", + description->s_name, pattern->s_name, retval ? "match" : "no match"); + return retval; + +} + + + + + +/* setup method */ +void pdp_type_setup(void) +{ + int i; + + // create mutexes + pthread_mutex_init(&pdp_hash_mutex, NULL); + pthread_mutex_init(&pdp_conversion_mutex, NULL); + pthread_mutex_init(&pdp_cache_mutex, NULL); + + // init symbol hash + memset(pdp_symhash, 0, HASHSIZE * sizeof(t_pdp_symbol *)); + + // create conversion lists + cached_conversion_list = pdp_list_new(0); + conversion_list = pdp_list_new(0); + max_cache_size = INIT_MAX_CACHE_SIZE; + + + + +} -- cgit v1.2.1