ListSpace.c
From Organic Design wiki
// [[[[http://www.organicdesign.co.nz/peerd|peerd]]]] - nodal p2p wiki daemon
// 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]]]]
// included in [[[[http://www.organicdesign.co.nz/category:peerd/files/C|peerd]]]][[[[http://www.organicdesign.co.nz/peerd.c|/peerd.c]]]]
typedef int item;
item *space;
// tmp: should use new pointer-lists
#define MAXITEMS 100000
int items = 0;
char *nssBuf;
// Prototypes
int listInit();
int listExit();
item listInsert();
item listRemove(item subject);
item listTraverse(item subject, item object);
item listGetValue(item subject);
item listSetValue(item subject, item value);
void listStats();
item trieGetValue(unsigned char *key);
item trieSetValue(unsigned char *key, item value);
// ----------------------------------------------------------------------------------------- //
// listSpace.c
int listInit() {
// all these are tmp and should be handled with new pointer-list
space = calloc(MAXITEMS,3*sizeof(item));
nssBuf = malloc(30);
return EXIT_SUCCESS;
}
int listExit() {
free(space);
}
// 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) logAdd("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 key as an association to a new listItem
// - key is also a listItem reference and its binary address is used as the traversal path
// - subject and key (all list-item references are ints starting at item 0)
// - if key is 0 the subject is returned unchanged, key 1 and 2 are the two single-iteration traversals
item listTraverse(item subject, item key) {
if (key++) {
int i,j;
for (i=1; i<=key>>1; i<<=1)
subject = space[j=subject+(subject<<1)+(key&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+(subject<<1)+2];
}
// Set the payload key of the subject Item to the passed value
item listSetValue(item subject, item value) {
return space[subject+(subject<<1)+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
// - 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
item trieGetValue(unsigned char *key) {
item subject = nodeTRIE;
while(*key) subject = listTraverse(subject,*key++);
return listGetValue(subject);
}
item trieSetValue(unsigned char *key, item value) {
item subject = nodeTRIE;
while(*key) subject = listTraverse(subject,*key++);
return listSetValue(subject,value);
}