diff options
| -rw-r--r-- | src/index.c | 280 |
1 files changed, 214 insertions, 66 deletions
diff --git a/src/index.c b/src/index.c index 745337a..e3007df 100644 --- a/src/index.c +++ b/src/index.c @@ -19,15 +19,22 @@ "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" -#include <string.h> -#include <stdio.h> - -#define MAXKEYLEN 16 - /* ----------------------- index --------------------- */ static t_class *index_class; @@ -38,29 +45,43 @@ typedef struct _index 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 */ - char **names; + t_symbol **names; } t_index; -static int find_last(char **names, int maxentries) +/************************************ + * 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; return 0; } -static int find_item(const char *key, char **names, int maxentries) +/* 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; int max = find_last(names, maxentries); while (++i<=max) - if (names[i]) - if (!strcmp(key, names[i])) return i; + if (names[i] && key==names[i]) return i; return -1; } -static int find_free(char **names, int maxentries) +/* 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; @@ -71,71 +92,117 @@ static int find_free(char **names, int maxentries) return -1; } +/************************************ + * 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) { int iindex = (int)findex; if ((iindex > 0) && (iindex <= x->maxentries) && (x->names[iindex-1])) { /* 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]); + outlet_symbol (x->x_obj.ob_outlet,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) +/* add a symbol to the map (if possible) */ +static void index_add(t_index *x, t_symbol *s, t_float f) { - int newentry; + 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 (! (find_item(s->s_name, x->names, x->maxentries)+1) ) { if ( x->entries < x->maxentries ) { - newentry=find_free(x->names, 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) { - char *buf = (char *)getbytes(sizeof(char) * MAXKEYLEN); x->entries++; - strcpy(buf, s->s_name); - x->names[newentry]=buf; - - ok=1; + x->names[newentry]=s; outlet_float(x->x_obj.ob_outlet, (t_float)newentry+1); + return; - } else post("index :: couldn't find any place for new entry"); - } else post("index :: max number of elements (%d) reached !", x->maxentries); + } 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"); - if (!ok) outlet_float(x->x_obj.ob_outlet, -1.f); + /* couldn't add the symbol to our index table */ + outlet_float(x->x_obj.ob_outlet, -1.f); } - -static void index_delete(t_index *x, t_symbol *s) +/* 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 element; - t_float r = -1.f; + 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 ( (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; + if ( index >= 0 && index < x->maxentries) { + x->names[index]=0; x->entries--; - } else post("index :: couldn't find element"); - - outlet_float(x->x_obj.ob_outlet, r); + 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) { int i=x->maxentries; while (i--) if (x->names[i]) { - freebytes(x->names[i], sizeof(char) * MAXKEYLEN); x->names[i]=0; } @@ -144,20 +211,86 @@ static void index_reset(t_index *x) outlet_float(x->x_obj.ob_outlet, 0.f); } -static void index_symbol(t_index *x, t_symbol *s) +/* output the number of entries stored in the array */ +static void index_bang(t_index *x) { - 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); + 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); - char** buf; + t_symbol** buf; int maxentries = 0, automod=0; int i; @@ -169,15 +302,16 @@ static void *index_new(t_symbol *s, int argc, t_atom *argv) if (!maxentries) maxentries=128; - buf = (char **)getbytes(sizeof(char *) * maxentries); + buf = (t_symbol **)getbytes(sizeof(t_symbol *) * maxentries); - i = maxentries; - while (i--) buf[i]=0; x->entries = 0; x->maxentries = maxentries; x->names = buf; x->auto_mode = !(!automod); + x->auto_resize = 1; + + while (maxentries--) buf[maxentries]=0; outlet_new(&x->x_obj, &s_float); @@ -186,21 +320,29 @@ static void *index_new(t_symbol *s, int argc, t_atom *argv) static void index_free(t_index *x) { - index_reset(x); - freebytes(x->names, sizeof(char *) * x->maxentries); + freebytes(x->names, sizeof(t_symbol *) * x->maxentries); } static void helper(t_index *x) { 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("<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"); } @@ -213,12 +355,18 @@ void index_setup(void) class_addsymbol(index_class, index_symbol); 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_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_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); class_sethelpsymbol(index_class, gensym("zexy/index")); |