2
* Pure Data Packet system implementation. : code for handling different packet types
3
* Copyright (c) by Tom Schouten <pdp@zzz.kotnet.org>
5
* This program is free software; you can redistribute it and/or modify
6
* it under the terms of the GNU General Public License as published by
7
* the Free Software Foundation; either version 2 of the License, or
8
* (at your option) any later version.
10
* This program is distributed in the hope that it will be useful,
11
* but WITHOUT ANY WARRANTY; without even the implied warranty of
12
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13
* GNU General Public License for more details.
15
* You should have received a copy of the GNU General Public License
16
* along with this program; if not, write to the Free Software
17
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
22
/* this file contains type handling routines */
28
#include "pdp_symbol.h"
29
#include "pdp_packet.h"
33
#include "pdp_debug.h"
40
static t_pdp_list *conversion_list;
42
#define INIT_MAX_CACHE_SIZE 32
44
static t_pdp_list *cached_conversion_list;
45
static int max_cache_size;
48
static pthread_mutex_t pdp_conversion_mutex;
49
static pthread_mutex_t pdp_cache_mutex;
53
/* convert a type to a list */
54
t_pdp_list *pdp_type_to_list(t_pdp_symbol *type)
58
char *c = type->s_name;
61
char tmp[strlen(type->s_name)+1];
62
t_pdp_list *l = pdp_list_new(0);
66
strncpy(tmp, lastname, n);
68
pdp_list_add_back(l, a_symbol, (t_pdp_word)pdp_gensym(tmp));
76
PDP_ASSERT(n < TMPSIZE);
79
pdp_list_add_back(l, a_symbol, (t_pdp_word)pdp_gensym(lastname));
85
/* get the description symbol. */
86
t_pdp_symbol *pdp_packet_get_description(int packet)
88
t_pdp *header = pdp_packet_header(packet);
90
if (!header) return pdp_gensym("invalid");
91
else if (!header->desc){
93
/* since every packet is obliged to have a description, this is an error */
94
pdp_post("ERROR: pdp_packet_get_description: packet %d has no description.", packet);
95
pdp_packet_print_debug(packet);
96
return pdp_gensym("unknown");
98
else return header->desc;
103
/* this runs a conversion program */
104
int _pdp_type_run_conversion_program(t_pdp_conversion_program *program,
105
int packet, t_pdp_symbol *dest_template)
107
/* run a conversion program:
108
treat the source packet as readonly, and cleanup intermediates, such
109
that the net result is the production of a new packet, with the
110
source packet intact. */
114
t_pdp_conversion_method m;
116
// run the first line of the program
119
D pdp_post("DEBUG: _pdp_type_run_conversion_program: method = %x", m);
120
p = m(packet, dest_template);
121
D pdp_post("DEBUG: _pdp_type_run_conversion_program:");
122
D pdp_post(" packet returned = %d, type = %s",
123
p, pdp_packet_get_description(p)->s_name);
125
// run the remaining lines + cleanup intermediates
126
for (a=a->next; a; a=a->next){
128
D pdp_post("DEBUG: _pdp_type_run_conversion_program: next method ptr = %x", m);
129
tmp = m(p, dest_template);
130
pdp_packet_mark_unused(p);
137
/* find a conversion program */
138
t_pdp_conversion_program *
139
_pdp_type_find_conversion_program(t_pdp_symbol *src_pattern, t_pdp_symbol *dst_pattern)
143
t_pdp_conversion_program *retval = 0;
145
/* lock conversion list */
146
pthread_mutex_lock(&pdp_conversion_mutex);
148
for (a = conversion_list->first; a; a=a->next){
150
/* can be a wildcard match */
151
if (pdp_type_description_match(src_pattern, c->src_pattern) &&
152
pdp_type_description_match(dst_pattern, c->dst_pattern)) {
153
/* found a program */
154
D pdp_post("DEBUG: _pdp_type_find_conversion_program: found: %s -> %s",
155
c->src_pattern->s_name, c->dst_pattern->s_name);
161
/* no conversion program was found */
165
/* lock conversion list */
166
pthread_mutex_unlock(&pdp_conversion_mutex);
170
/* find a cached conversion program
171
if one is found it will be moved to the back of the queue (MRU) */
172
t_pdp_conversion_program *
173
_pdp_type_find_cached_conversion_program(t_pdp_symbol *src_pattern, t_pdp_symbol *dst_pattern)
175
t_pdp_conversion *c, *c_tmp;
177
t_pdp_conversion_program *retval = 0;
179
/* lock cached list */
180
pthread_mutex_lock(&pdp_cache_mutex);
182
for (a = cached_conversion_list->first; a; a=a->next){
184
/* must be exact match */
185
if ((src_pattern == c->src_pattern) &&
186
(dst_pattern == c->dst_pattern)) {
188
/* found a program */
189
D pdp_post("DEBUG: _pdp_type_find_cached_conversion_program: found: %s -> %s",
190
c->src_pattern->s_name, c->dst_pattern->s_name);
193
/* make MRU (move to back) */
194
c_tmp = cached_conversion_list->last->w.w_pointer;
195
cached_conversion_list->last->w.w_pointer = c;
196
a->w.w_pointer = c_tmp;
206
/* un lock cached list */
207
pthread_mutex_unlock(&pdp_cache_mutex);
209
/* no conversion program was found */
214
/* conversion program manipulations */
215
void pdp_conversion_program_free(t_pdp_conversion_program *program)
217
pdp_list_free(program);
221
void _pdp_conversion_program_print(t_pdp_conversion_program *program)
223
D pdp_post("_pdp_conversion_program_print %x", program);
224
pdp_list_print(program);
227
t_pdp_conversion_program *pdp_conversion_program_new(t_pdp_conversion_method method, ...)
229
t_pdp_conversion_program *p = pdp_list_new(0);
230
t_pdp_conversion_method m = method;
233
D pdp_post("DEBUG: pdp_conversion_program_new:BEGIN");
235
pdp_list_add_back_pointer(p, m);
236
va_start(ap, method);
237
while (m = va_arg(ap, t_pdp_conversion_method)) pdp_list_add_back_pointer(p, m);
240
D pdp_post("DEBUG: pdp_conversion_program_new:END");
245
t_pdp_conversion_program *pdp_conversion_program_copy(t_pdp_conversion_program *program)
247
if (program) return pdp_list_copy(program);
251
void pdp_conversion_program_add(t_pdp_conversion_program *program,
252
t_pdp_conversion_program *tail)
254
return pdp_list_cat(program, tail);
257
/* conversion registration */
258
void pdp_type_register_conversion (t_pdp_symbol *src_pattern, t_pdp_symbol *dst_pattern,
259
t_pdp_conversion_program *program)
261
t_pdp_conversion *c = (t_pdp_conversion *)pdp_alloc(sizeof(*c));
262
c->src_pattern = src_pattern;
263
c->dst_pattern = dst_pattern;
264
c->program = program;
266
/* lock conversion list */
267
pthread_mutex_lock(&pdp_conversion_mutex);
269
pdp_list_add_back_pointer(conversion_list, c);
271
/* unlock conversion list */
272
pthread_mutex_unlock(&pdp_conversion_mutex);
276
/* register a cached conversion */
277
void pdp_type_register_cached_conversion (t_pdp_symbol *src_pattern, t_pdp_symbol *dst_pattern, t_pdp_conversion_program *program)
280
/* create the new conversion */
281
t_pdp_conversion *c = (t_pdp_conversion *)pdp_alloc(sizeof(*c));
282
c->src_pattern = src_pattern;
283
c->dst_pattern = dst_pattern;
284
c->program = program;
286
/* lock cached conversion list */
287
pthread_mutex_lock(&pdp_cache_mutex);
289
/* check size, and remove LRU (top) if the cache is full */
290
while (cached_conversion_list->elements >= max_cache_size){
291
t_pdp_conversion *c_old = pdp_list_pop(cached_conversion_list).w_pointer;
292
if (c_old->program) pdp_conversion_program_free(c_old->program);
296
/* add and make MRU (back) */
297
pdp_list_add_back_pointer(cached_conversion_list, c);
299
/* unlock cached conversion list */
300
pthread_mutex_unlock(&pdp_cache_mutex);
303
/* convert a given packet to a certain type (template) */
304
int _pdp_packet_convert(int packet, t_pdp_symbol *dest_template)
306
t_pdp_symbol *type = pdp_packet_get_description(packet);
307
t_pdp_symbol *tmp_type = 0;
310
t_pdp_conversion_program *program = 0;
311
t_pdp_conversion_program *program_last = 0;
312
t_pdp_conversion_program *program_tail = 0;
314
/* check if there is a program in the cached list, if so run it */
315
if (program = _pdp_type_find_cached_conversion_program(type, dest_template))
316
return _pdp_type_run_conversion_program(program, packet, dest_template);
318
/* if it is not cached, iteratively convert
319
and save program on top of cache list if a conversion path (program) was found */
321
// run first conversion that matches
322
program = pdp_conversion_program_copy
323
(_pdp_type_find_conversion_program(type, dest_template));
324
program_last = program;
326
D pdp_post("DEBUG: pdp_type_convert: (1) can't convert %s to %s",
327
type->s_name, dest_template->s_name);
330
tmp_packet = _pdp_type_run_conversion_program(program, packet, dest_template);
331
tmp_type = pdp_packet_get_description(tmp_packet);
333
// run more conversions if necessary, deleting intermediate packets
334
while (!pdp_type_description_match(tmp_type, dest_template)){
336
program_tail = _pdp_type_find_conversion_program(tmp_type, dest_template);
338
D pdp_post("DEBUG: pdp_type_convert: (2) can't convert %s to %s",
339
tmp_type->s_name, dest_template->s_name);
340
pdp_packet_mark_unused(tmp_packet);
341
pdp_conversion_program_free(program);
344
if (program_last == program_tail){
345
pdp_post("ERROR: pdp_packet_convert: conversion loop detected");
347
program_last = program_tail;
349
pdp_conversion_program_add(program, program_tail);
350
new_packet = _pdp_type_run_conversion_program(program_tail, tmp_packet, dest_template);
351
pdp_packet_mark_unused(tmp_packet);
352
tmp_packet = new_packet;
353
tmp_type = pdp_packet_get_description(tmp_packet);
356
// save the conversion program in the cache
357
pdp_type_register_cached_conversion(type, dest_template, program);
359
// return resulting packet
364
/* convert or copy ro */
365
int pdp_packet_convert_ro(int packet, t_pdp_symbol *dest_template)
367
t_pdp_symbol *type = pdp_packet_get_description(packet);
369
/* if it is compatible, return a ro copy */
370
if (pdp_type_description_match(type, dest_template)) return pdp_packet_copy_ro(packet);
372
/* if not, convert to a new type */
373
else return _pdp_packet_convert(packet, dest_template);
376
/* convert or copy rw */
377
int pdp_packet_convert_rw(int packet, t_pdp_symbol *dest_template)
379
t_pdp_symbol *type = pdp_packet_get_description(packet);
381
/* if it is compatible, just return a rw copy */
382
if (pdp_type_description_match(type, dest_template)) return pdp_packet_copy_rw(packet);
384
/* if not, convert to a new type */
385
else return _pdp_packet_convert(packet, dest_template);
389
/* this is a hack. type cache data: (a type description parsed into
390
a pdp_list for fast comparison) should be setup when
391
a packet symbol is created, but since that can be everywhere,
392
we set it up on first use. type cache is permanent. */
395
static void _setup_type_cache(t_pdp_symbol *s)
397
t_pdp_list *l = pdp_type_to_list(s);
398
if (!pdp_symbol_set_typelist(s, l))
399
pdp_list_free(l); // list was already present -> free cached list
403
/* check if a type description fits a template
404
this function is symmetric */
405
int pdp_type_description_match(t_pdp_symbol *description, t_pdp_symbol *pattern)
407
int match = 0; // no match until all tests are passed
410
t_pdp_symbol *wildcard = PDP_SYM_WILDCARD;
413
PDP_ASSERT(description);
415
/* same type symbol -> match */
416
if (description == pattern) {match = 1; goto done;}
418
/* check the description list */
419
if (!(description->s_type)) _setup_type_cache(description);
420
if (!(pattern->s_type)) _setup_type_cache(pattern);
422
/* compare symbols of description list */
423
for(ad=description->s_type->first, ap=pattern->s_type->first;
425
ad=ad->next, ap=ap->next)
428
if (ad->w.w_symbol == wildcard) continue;
429
if (ap->w.w_symbol == wildcard) continue;
430
if (ad->w.w_symbol != ap->w.w_symbol) {goto done;} /* difference and not a wildcard */
433
/* ok if sizes are equal */
434
if (! (ad || ap)) {match = 1; goto done;}
436
/* one of the two is shorter, so the shortest list needs
437
to end with a wildcard to have a match */
439
if (ap && description->s_type->last->w.w_symbol != wildcard) goto done;
440
if (ad && pattern->s_type->last->w.w_symbol != wildcard) goto done;
442
/* all tests passed: type templates match */
446
D pdp_post("DEBUG: testing match between %s and %s: %s",
447
description->s_name, pattern->s_name, match ? "match" : "no match");
457
void pdp_type_setup(void)
462
pthread_mutex_init(&pdp_conversion_mutex, NULL);
463
pthread_mutex_init(&pdp_cache_mutex, NULL);
465
// create conversion lists
466
cached_conversion_list = pdp_list_new(0);
467
conversion_list = pdp_list_new(0);
468
max_cache_size = INIT_MAX_CACHE_SIZE;
added
removed
system/kernel/pdp_type.c
