ListSpace.c

1. include <stdlib.h>
2. include <stdio.h>
3. include <string.h>

int main(int argc, char **argv) {

1. define MAXITEMS 10000
2. define ROOT 0

typedef int item; item space[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; }

// 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 // - Treat each character in text-keys as a list-item-index to traverse from root // - ListSpace cannot store pointers because they are not binary-traversable, so // an ordered list of pointers to hash-table data is maintained so that list-space // can refer to the pointers in the list by integer index // Usage: pval = *trie("myKey") and *trie("myKey") = "myValue"

// - later this should use a linked-list of free-indexes, and malloc ptr-table in blocks // - but for now, a max of 1000 data-pointers can be stored (before a segmentation fault occurs:) void *trieBuf[1000]; int triePtr = 1; // start at 1 since list-space-0 means no value

// Trie-traversal requires items 0-127 be reserved for ascii character nodes while (items<128) listInsert();

// Return the pointer to the pointer-value associated with the passed text-key // - creates an association to a new ptr-entry if non-existent void **trie(unsigned char *key) { item i,subject = ROOT; while(*key) subject = listTraverse(subject,*key++); return (i = listGetValue(subject)) ? trieBuf+i : trieBuf+listSetValue(subject,triePtr++); }

void trieTest() { char* foo = "my name is mister foo, what's your's?"; *trie(foo) = "hello foo!"; *trie("pine") = "Cone"; printf("\ttrie[\"%s\"] = \"%s\"\n",foo,*trie(foo)); printf("\ttrie[\"%s\"] = \"%s\"\n","pine",*trie("pine")); } // ----------------------------------------------------------------------------------------- //

// Test trie trieTest(); listStats();

}