ListSpace.h

From OrganicDesign 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);
	}