ListSpace.c

// This article and all its includes are licenced under LGPL // GPL: http://www.gnu.org/copyleft/lesser.html // SRC: http://www.organicdesign.co.nz/listSpace.c

1. define MAXITEMS 10000
2. define HASHBUFSIZE 1000
3. define ROOT 0

typedef int item; item *space = malloc(MAXITEMS*3); // should be dynamic alloc int items = 0;

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

// Move the subject onto the free-list item listRemove(item subject) { return subject; }

// 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 item *listGetKeys(item subject) {

int keys = 0;

// Recursive-sub-function // - for each position, check 0,1 for more assocs, 2 for assoc-found-here void search(item subject,int path,int level) { printf("\t\t\t\tsearch(ptr,%d,%d,%d)\n",subject,path,level); item i; if (i=space[subject*3+0]) search(i,path,level+1); if (i=space[subject*3+1]) search(i,path+(1<<level),level+1); if (i=space[subject*3+2]) insertPointer(&path) | keys++; }

search(ROOT,subject,0,0);

while(keys--) removePointer();

return buf; }

// 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); }

// NOTE: use linked-list for this too int hashPtr = 0; void **hashBuf = malloc(HASHBUFSIZE); // index-to-pointer table (should be dynamic alloc.) void **hash(unsigned char *key) { item i,subject = ROOT; while(*key) subject = listTraverse(subject,(item)*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")); }