Difference between revisions of "ListSpace.c"

From Organic Design wiki
m
(use new trie/hash code)
Line 46: Line 46:
  
  
 +
// ----------------------------------------------------------------------------------------- //
 +
// Trie & Hash
 +
// - 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();
−
// 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
+
item trieGetValue(unsigned char *key) {
−
// - but for now, a max of 1000 data-pointers can be stored (before a segmentation fault occurs:)
+
item subject = ROOT;
−
void *trieBuf[1000];
+
while(*key) subject = listTraverse(subject,*key++);
−
int triePtr = 1; // start at 1 since list-space-0 means no value
+
return listGetValue(subject);
 +
}
  
−
// Trie-traversal requires items 0-127 be reserved for ascii character nodes
+
item trieSetValue(unsigned char *key, item value) {
−
while (items<128) listInsert();
+
item subject = ROOT;
 +
while(*key) subject = listTraverse(subject,*key++);
 +
return listSetValue(subject,value);
 +
}
  
−
// Return the pointer to the pointer-value associated with the passed text-key
+
void *hashBuf[1000];
−
// - creates an association to a new ptr-entry if non-existent
+
int hashPtr = 0;
−
void **trie(unsigned char *key) {
+
void **hash(unsigned char *key) {
 
item i,subject = ROOT;
 
item i,subject = ROOT;
 
while(*key) subject = listTraverse(subject,*key++);
 
while(*key) subject = listTraverse(subject,*key++);
−
return (i = listGetValue(subject)) ? trieBuf+i : trieBuf+listSetValue(subject,triePtr++);
+
return (i = listGetValue(subject)) ? hashBuf+i : hashBuf+listSetValue(subject,++hashPtr);
 
}
 
}
  
−
void trieTest() {
+
void hashTest() {
 
char* foo = "my name is mister foo, what's your's?";
 
char* foo = "my name is mister foo, what's your's?";
−
*trie(foo) = "hello foo!";
+
*hash(foo) = "hello foo!";
−
*trie("pine") = "Cone";
+
*hash("pine") = "Cone";
−
printf("\ttrie[\"%s\"] = \"%s\"\n",foo,*trie(foo));
+
printf("\thash[\"%s\"] = \"%s\"\n",foo,*hash(foo));
−
printf("\ttrie[\"%s\"] = \"%s\"\n","pine",*trie("pine"));
+
printf("\thash[\"%s\"] = \"%s\"\n","pine",*hash("pine"));
 
}
 
}

Revision as of 23:47, 9 July 2006

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

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

void *hashBuf[1000]; int hashPtr = 0; 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")); }

Retrieved from "https://organicdesign.nz/wiki/index.php?title=ListSpace.c&oldid=23817"