ListSpace.c

1. define MAXITEMS 10000
2. define ROOT 0

typedef int item; item *space = malloc(MAXITEMS*3); int items = 0;

// Create a new listItem in the space and return its index item listInsert() { if (items >= MAXITEMS) printf("No more items in the space!"); else return items++; return 0; }

// Start at subject listItem and traverse the object as an association to a new listItem // - object is also a listItem reference and its binary address is used as the traversal path // - subject and object (all list-item references are ints starting at item 0) item listTraverse(item subject, item object) { object += 2; // tmp: can't traverse items 0 or 1 int i,j; for (i=1; i<=object>>1; i<<=1) subject = space[j=subject*3+(object&i?1:0)]?space[j]:(space[j]=listInsert()); return subject; }

// Get the value (payload key) of the subject Item item listGetValue(item subject) { return space[subject*3+2]; }

// Set the payload key of the subject Item to the passed value item listSetValue(item subject, item value) { return space[subject*3+2] = value; }

// Returns keys contained within passed node // - this is an expensive operation and should not be used by the core void listGetKeys(item subject) { item *buf = malloc(1000), *ptr = buf; // list of key-indexes (should be dynamic alloc.) listGetKeys2(ptr,subject,0,0); }

// Recursive-sub-function // - for each position, check 0,1 for more assocs, 2 for assoc-found-here void listGetKeys2(item* &ptr,item subject,int path,int level) { item i; if (i=space[subject*3+0]) listGetKeys2(ptr,i,path,level+1); if (i=space[subject*3+1]) listGetKeys2(ptr,i,path+(1<<level),level+1); if (i=space[subject*3+2]) *ptr++ = path; }

// Print listSpace statistics // - currently just counts how many nodes have payloads and displays content void listStats() { int i,j,p=0; printf("\nlistStatistics:\n"); for (i=0; i<MAXITEMS; i++) if (listGetValue(i)) p++; printf("\t%d of %d items in use:\n",p,MAXITEMS); //for (i=0; i<MAXITEMS; i++) if (j=listGetValue(i)) printf("  %d = %d\n",i,j); printf("\n\n"); }

// ----------------------------------------------------------------------------------------- // // Trie & Hash // - not really part of listSpace, but needed by env's with no hash-tables // - uses ascii traversal by reserving first list items // - trie sets/gets list items using ascii-traversal // - hash sets/gets pointers - see hashTest() for example

while (items<128) listInsert();

item trieGetValue(unsigned char *key) { item subject = ROOT; while(*key) subject = listTraverse(subject,*key++); return listGetValue(subject); }

item trieSetValue(unsigned char *key, item value) { item subject = ROOT; while(*key) subject = listTraverse(subject,*key++); return listSetValue(subject,value); }

int hashPtr = 0; void **hashBuf = malloc(1000); // index-to-pointer table (should be dynamic alloc.) void **hash(unsigned char *key) { item i,subject = ROOT; while(*key) subject = listTraverse(subject,*key++); return (i = listGetValue(subject)) ? hashBuf+i : hashBuf+listSetValue(subject,++hashPtr); }

void hashTest() { char* foo = "my name is mister foo, what's your's?"; *hash(foo) = "hello foo!"; *hash("pine") = "Cone"; printf("\thash[\"%s\"] = \"%s\"\n",foo,*hash(foo)); printf("\thash[\"%s\"] = \"%s\"\n","pine",*hash("pine")); }