improved performance (i think)

added a lot of new functionality

svn path=/trunk/externals/zexy/; revision=3095

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"));