ListSpace.c

1. define MAXITEMS 10000
2. define ROOT 0

typedef int item; item items = 0; int *space;

// Create a new listItem in the space and return its index item listInsert() { //printf("listInsert(): new item %d\n", items); return items++; }

// 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 void listSetValue(item subject, item value) { space[subject*3+2] = value; }

// The following four functions are used internally by hashSet/Get // - 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

item hashTraverse(char *text) { item subject = ROOT; int i; for (i=0; i<strlen(text); i++) subject = listTraverse(subject, (item)text[i]); return subject; }

void *hashReturnPointer(int index) { void *ptr; return ptr; }

int hashInsertPointer(void *ptr) { int index; return index; }

void hashRemovePointer(int index) { }

// Get the pointer to the data associated with the passed text-key void *hashGetValue(char* key) { return hashReturnPointer((int)listGetValue(hashTraverse(key))); }

// Set the data-pointer associated with the passed text-key void hashSetValue(char* key, void *value) { *hashReturnPointer((int)listGetValue(hashTraverse(key))) = value; }

// Allocate memory for maximum ListItems space = calloc(MAXITEMS*3, sizeof(item)); printf("%d bytes of memory allocated\n", MAXITEMS*3*sizeof(item));

// Insert items 0-127 as ascii character nodes // - this allows us to temporarily use list-space as a hash-table // since C/C++ doesn't inherently have one for (i=0; i<128; i++) listInsert();

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