Update of /cvsroot/pure-data/externals/zexy/src In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv21097

Modified Files: index.c Log Message: improved performance (i think) added a lot of new functionality

Index: index.c =================================================================== RCS file: /cvsroot/pure-data/externals/zexy/src/index.c,v retrieving revision 1.3 retrieving revision 1.4 diff -C2 -d -r1.3 -r1.4 *** index.c 19 May 2005 09:42:55 -0000 1.3 --- index.c 30 May 2005 14:34:44 -0000 1.4 *************** *** 20,31 **** "index" simulates an associative index :: that is : convert a symbol to an index

! */

! #include "zexy.h"

! #include <string.h> ! #include <stdio.h>

! #define MAXKEYLEN 16

/* ----------------------- index --------------------- */ --- 20,38 ---- "index" simulates an associative index :: that is : convert a symbol to an index

! CAVEATS: starts to count at "1"

! TODO: use "symbol" instead of "char*" : FIXED ! TODO: "dump" the contents (so we can share between [index]es, ...) FIXED ! TODO: "compact": move all entries to the beginning of the array FIXED ! TODO: "sort" FIXED ! TODO: "add" at a specific position (like "add 10 hallo" of "add hallo 10") (??) FIXED ! TODO: "delete" from a specific position (like "delete 4" deletes the 4th element) FIXED ! TODO: get the number of stored entries ("bang") FIXED ! ! TODO: resize the array if it gets to small

! */

! #include "zexy.h"

/* ----------------------- index --------------------- */ *************** *** 39,47 **** int entries, maxentries; int auto_mode; /* 1--add if key doesn't already exist; 0--do not add; */

! char **names; } t_index;

! static int find_last(char **names, int maxentries) { /* returns the index of the last entry (0..(maxentries-1)) */ while (maxentries--) if (names[maxentries]) return maxentries; --- 46,63 ---- int entries, maxentries; int auto_mode; /* 1--add if key doesn't already exist; 0--do not add; */ + int auto_resize; /* 1--resize the array if we are running out of slots; 0--don't */

! t_symbol **names; } t_index;

! /************************************ ! * helpers ! */ ! ! ! /* find the last non-NULL entry in the array * ! * LATER: shouldn't this return "-1" on failure ? ! */ ! static int find_last(t_symbol **names, int maxentries) { /* returns the index of the last entry (0..(maxentries-1)) */ while (maxentries--) if (names[maxentries]) return maxentries; *************** *** 49,53 **** }

! static int find_item(const char *key, char **names, int maxentries) { /* returns index (0..[maxentries-1?]) on success; -1 if the item could not be found */ int i=-1; --- 65,72 ---- }

! /* search the array for "key" ! * if it is not there, return "-1" ! */ ! static int find_item(const t_symbol *key, t_symbol **names, int maxentries) { /* returns index (0..[maxentries-1?]) on success; -1 if the item could not be found */ int i=-1; *************** *** 55,65 ****

while (++i<=max) ! if (names[i]) ! if (!strcmp(key, names[i])) return i;

return -1; }

! static int find_free(char **names, int maxentries) { int i=0; --- 74,86 ----

while (++i<=max) ! if (names[i] && key==names[i]) return i;

return -1; }

! /* find the first NULL entry in the array ! * return "-1" if none can be found ! */ ! static int find_free(t_symbol **names, int maxentries) { int i=0; *************** *** 72,75 **** --- 93,113 ---- }

+ /************************************ + * methods + */ + static void index_add(t_index *x, t_symbol *s, t_float f); + + /* look up a symbol in the map */ + static void index_symbol(t_index *x, t_symbol *s) + { + int element; + if ( (element = find_item(s, x->names, x->maxentries)+1) ) + outlet_float(x->x_obj.ob_outlet, (t_float)element); + else if (x->auto_mode) // not yet stored: add automatically + index_add(x, s, 0); + else outlet_float(x->x_obj.ob_outlet, 0.f); // not yet stored but do not add + } + + /* output the entry at a given index */ static void index_float(t_index *x, t_float findex) { *************** *** 78,133 **** { /* TB: output symbol to outlet */ ! t_symbol * s = gensym (x->names[iindex-1]); ! outlet_symbol (x->x_obj.ob_outlet,s); ! // post("iindex[%d] = %s", iindex, x->names[iindex-1]); } }

- static void index_auto(t_index *x, t_float automod) - { - x->auto_mode = !(!automod); - } -

! static void index_add(t_index *x, t_symbol *s) { ! int newentry; int ok = 0;

- if (! (find_item(s->s_name, x->names, x->maxentries)+1) ) { if ( x->entries < x->maxentries ) { ! newentry=find_free(x->names, x->maxentries); if (newentry + 1) { - char *buf = (char *)getbytes(sizeof(char) * MAXKEYLEN); x->entries++; ! strcpy(buf, s->s_name); ! x->names[newentry]=buf; ! ! ok=1;

outlet_float(x->x_obj.ob_outlet, (t_float)newentry+1);

! } else post("index :: couldn't find any place for new entry"); ! } else post("index :: max number of elements (%d) reached !", x->maxentries); } else post("index :: element already exists");

! if (!ok) outlet_float(x->x_obj.ob_outlet, -1.f); } ! ! static void index_delete(t_index *x, t_symbol *s) { ! int element; ! t_float r = -1.f;

! if ( (element = find_item(s->s_name,x->names, x->maxentries))+1 ) { ! freebytes(x->names[element], sizeof(char) * MAXKEYLEN); ! x->names[element]=0; ! r = 0.f; x->entries--; ! } else post("index :: couldn't find element"); ! ! outlet_float(x->x_obj.ob_outlet, r); }

static void index_reset(t_index *x) { --- 116,201 ---- { /* TB: output symbol to outlet */ ! outlet_symbol (x->x_obj.ob_outlet,x->names[iindex-1]); } }

! /* add a symbol to the map (if possible) */ ! static void index_add(t_index *x, t_symbol *s, t_float f) { ! int newentry=(int)f; int ok = 0; + + if (! (find_item(s, x->names, x->maxentries)+1) ) { + if (x->auto_resize && x->entries==x->maxentries){ + /* do some resizing */ + int maxentries=x->maxentries*2; + int i; + t_symbol**buf=(t_symbol **)getbytes(sizeof(t_symbol *) * maxentries); + if(buf!=0){ + memcpy(buf, x->names, sizeof(t_symbol *) * x->maxentries); + for(i=x->maxentries; i<maxentries; i++)buf[i]=0; + + freebytes(x->names, sizeof(t_symbol *) * x->maxentries); + + x->names=buf; + x->maxentries=maxentries; + } + }

if ( x->entries < x->maxentries ) { ! if(newentry>0){ ! newentry--; ! if(x->names[newentry]){ /* it is already taken! */ ! error("index :: couldn't add element at position %d (already taken)", newentry+1); ! outlet_float(x->x_obj.ob_outlet, -1.f); ! return; ! } ! } else ! newentry=find_free(x->names, x->maxentries); ! if (newentry + 1) { x->entries++; ! x->names[newentry]=s;

outlet_float(x->x_obj.ob_outlet, (t_float)newentry+1); + return;

! } else error("index :: couldn't find any place for new entry"); ! } else error("index :: max number of elements (%d) reached !", x->maxentries); } else post("index :: element already exists");

! /* couldn't add the symbol to our index table */ ! outlet_float(x->x_obj.ob_outlet, -1.f); } ! /* delete a symbol from the map (if it is in there) */ ! static void index_delete(t_index *x, t_symbol *s, int argc, t_atom*argv) { ! int index=-1; ! if(argc!=1){ ! error("index :: delete what ?"); ! return; ! } else { ! if(argv->a_type==A_FLOAT){ ! index=atom_getint(argv)-1; ! } else if (argv->a_type==A_SYMBOL){ ! index=find_item(atom_getsymbol(argv),x->names, x->maxentries); ! } else { ! error("index :: delete what ?"); ! return; ! } ! }

! if ( index >= 0 && index < x->maxentries) { ! x->names[index]=0; x->entries--; ! outlet_float(x->x_obj.ob_outlet, 0.0); ! } else { ! post("index :: couldn't find element"); ! outlet_float(x->x_obj.ob_outlet, -1.0); ! } }

+ /* delete all symbols from the map */ static void index_reset(t_index *x) { *************** *** 136,140 **** while (i--) if (x->names[i]) { - freebytes(x->names[i], sizeof(char) * MAXKEYLEN); x->names[i]=0; } --- 204,207 ---- *************** *** 145,162 **** }

! static void index_symbol(t_index *x, t_symbol *s) { ! int element; ! if ( (element = find_item(s->s_name, x->names, x->maxentries)+1) ) ! outlet_float(x->x_obj.ob_outlet, (t_float)element); ! else if (x->auto_mode) ! index_add(x, s); ! else outlet_float(x->x_obj.ob_outlet, 0.f); }

static void *index_new(t_symbol *s, int argc, t_atom *argv) { t_index *x = (t_index *)pd_new(index_class); ! char** buf;

int maxentries = 0, automod=0; --- 212,295 ---- }

! /* output the number of entries stored in the array */ ! static void index_bang(t_index *x) { ! outlet_float(x->x_obj.ob_outlet, (t_float)x->entries); ! } ! /* dump each entry in the format: "list <symbol> <index>" */ ! static void index_dump(t_index *x) ! { ! t_atom ap[2]; ! int i=0; ! ! for(i=0; i<x->maxentries; i++){ ! if(x->names[i]){ ! SETSYMBOL(ap, x->names[i]); ! SETFLOAT(ap+1, i+1); ! outlet_list(x->x_obj.ob_outlet, 0, 2, ap); ! } ! } ! } ! ! /* compact all entries, removing all holes in the map */ ! static void index_compact(t_index *x){ ! int i,j; ! for(i=0; i<x->entries; i++){ ! if(!x->names[i]){ ! for(j=i+1; j<x->maxentries; j++){ ! if(x->names[j]){ ! x->names[i]=x->names[j]; ! x->names[j]=0; ! break; ! } ! } ! } ! } ! } ! /* sort the map alphabetically */ ! static void index_sort(t_index *x){ ! int entries=x->entries; ! int step=entries; ! int loops=1, n; ! t_symbol**buf=x->names; ! index_compact(x); /* couldn't we do it more "in-place", e.g. don't touch empty slots ? */ ! ! while(step>1){ ! //step = (step % 2)?(step+1)/2:step/2; ! step+=step%2; ! step>>=1; ! int i = loops; ! loops+=2; ! ! while(i--) { /* there might be some optimization in here */ ! for (n=0; n<(x->entries-step); n++) { ! int comp=strcmp(buf[n]->s_name,buf[n+step]->s_name); ! if (comp>0) { // compare STRINGS not SYMBOLS ! t_symbol*s_tmp = buf[n]; ! buf[n] = buf[n+step]; ! buf[n+step] = s_tmp; ! } ! } ! } ! } }

+ /* turn on/off auto-adding of elements that are not yet in the map */ + static void index_auto(t_index *x, t_float automod) + { + x->auto_mode = !(!automod); + } + /* turn on/off auto-resizing of the map if it gets to small */ + static void index_resize(t_index *x, t_float automod) + { + x->auto_resize = !(!automod); + } + + + static void *index_new(t_symbol *s, int argc, t_atom *argv) { t_index *x = (t_index *)pd_new(index_class); ! t_symbol** buf;

int maxentries = 0, automod=0; *************** *** 170,177 **** if (!maxentries) maxentries=128;

! buf = (char **)getbytes(sizeof(char *) * maxentries);

- i = maxentries; - while (i--) buf[i]=0;

x->entries = 0; --- 303,308 ---- if (!maxentries) maxentries=128;

! buf = (t_symbol **)getbytes(sizeof(t_symbol *) * maxentries);

x->entries = 0; *************** *** 179,182 **** --- 310,316 ---- x->names = buf; x->auto_mode = !(!automod); + x->auto_resize = 1; + + while (maxentries--) buf[maxentries]=0;

outlet_new(&x->x_obj, &s_float); *************** *** 187,192 **** static void index_free(t_index *x) { ! index_reset(x); ! freebytes(x->names, sizeof(char *) * x->maxentries); }

--- 321,325 ---- static void index_free(t_index *x) { ! freebytes(x->names, sizeof(t_symbol *) * x->maxentries); }

*************** *** 195,205 **** { post("\n%c index :: index symbols to indices", HEARTSYMBOL); ! post("<symbol>\t : look up the <symbol> in the index and return it's index\n" ! "'add <symbol>'\t: add a new symbol to the index\n" ! "'delete <symbol>' : delete a symbol from the index\n" ! "'reset'\t\t : delete the whole index\n" ! "'auto <1/0>\t : if auto is 1 and a yet unknown symbol is looked up it is\n\t\t\t automatically added to the index\n" ! "'help'\t\t : view this" ! "\noutlet : <n>\t : index of the <symbol>"); post("\ncreation:"index [<maxelements> [<auto>]]": creates a <maxelements> sized index"); } --- 328,347 ---- { post("\n%c index :: index symbols to indices", HEARTSYMBOL); ! post("<symbol> : look up the <symbol> in the index and return it's index\n" ! "\n<int> : look up the element at index <int> in the index" ! "\n'add <symbol>' : add a new symbol to the index-map" ! "\n'add <symbol> <int>' : add a new symbol at the index <int>" ! "\n'delete <symbol>' : delete a symbol from the index-map" ! "\n'delete <int>' : delete the entry at index <int> from the index-map" ! "\n'reset' : delete the whole index-map" ! "\n'bang' : return the number of entries in the index-map" ! "\n'dump' : dump each entry in the format "list <symbol> <index>"" ! "\n'compact' : remove holes in the index-map" ! "\n'sort' : alphabetically sort the entries" ! "\n'auto <1/0> : if auto is 1 and a yet unknown symbol is looked up it is\n\t\t\t automatically added to the index-map" ! "\n'resize <1/0> : if resize is 1 (default), the index-map is resized\n\t\t\t automatically if needed" ! "\n'help' : view this" ! "\noutlet : <n> : index of the <symbol>" ! "\n <symbol> : entry at <index>"); post("\ncreation:"index [<maxelements> [<auto>]]": creates a <maxelements> sized index"); } *************** *** 214,223 ****

class_addmethod(index_class, (t_method)index_reset, gensym("reset"), 0); ! class_addmethod(index_class, (t_method)index_delete, gensym("delete"), A_SYMBOL, 0); ! class_addmethod(index_class, (t_method)index_add, gensym("add"), A_SYMBOL, 0);

class_addmethod(index_class, (t_method)index_auto, gensym("auto"), A_FLOAT, 0);

! class_addfloat(index_class, (t_method)index_float);

class_addmethod(index_class, (t_method)helper, gensym("help"), 0); --- 356,371 ----

class_addmethod(index_class, (t_method)index_reset, gensym("reset"), 0); ! class_addmethod(index_class, (t_method)index_delete, gensym("delete"), A_GIMME, 0); ! // class_addmethod(index_class, (t_method)index_add, gensym("add"), A_SYMBOL, 0); ! class_addmethod(index_class, (t_method)index_add, gensym("add"), A_SYMBOL, A_DEFFLOAT, 0);

class_addmethod(index_class, (t_method)index_auto, gensym("auto"), A_FLOAT, 0); + class_addmethod(index_class, (t_method)index_resize, gensym("resize"), A_FLOAT, 0);

! class_addfloat(index_class, (t_method)index_float); ! class_addbang(index_class, (t_method)index_bang); ! class_addmethod(index_class, (t_method)index_sort, gensym("sort"), 0); ! class_addmethod(index_class, (t_method)index_compact, gensym("compact"), 0); ! class_addmethod(index_class, (t_method)index_dump, gensym("dump"), 0);

class_addmethod(index_class, (t_method)helper, gensym("help"), 0);