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

// ----------------------------------------------------------------------------------------- // // Pointer Loops (used by list and hash)

typedef struct pl { void *data; struct pl *prev, *next; } loop;

void loopInsert(loop *subject, loop *object) { object->next = subject->next; subject->next = object->next->prev = object; object->prev = subject; }

void loopRemove(loop *subject) { subject->prev->next = subject->next; subject->next->prev = subject->prev; }

// ----------------------------------------------------------------------------------------- // // List Space

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) {

// Recursive-sub-function // - for each position, check 0,1 for more assocs, 2 for assoc-found-here void search(item **ptr,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(ptr,i,path,level+1); if (i=space[subject*3+1]) search(ptr,i,path+(1<<level),level+1); if (i=space[subject*3+2]) **ptr++ = path; }

// NOTE: use Linked-list-functions for this item *buf = malloc(HASHBUFSIZE), *ptr = buf; // list of key-indexes (should be dynamic alloc.)

search(&ptr,subject,0,0); 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")); }