aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorIOhannes m zmölnig <zmoelnig@users.sourceforge.net>2005-05-30 14:34:44 +0000
committerIOhannes m zmölnig <zmoelnig@users.sourceforge.net>2005-05-30 14:34:44 +0000
commit1579f2ca7213d90039611ab7a7d38b1a0fccafaa (patch)
tree4719353c88e4490651148902df7992117e02d49c
parent9b2f98d2feae5200d6354826eefe98084a3df476 (diff)
improved performance (i think)
added a lot of new functionality svn path=/trunk/externals/zexy/; revision=3095
-rw-r--r--src/index.c280
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"));