ListSpace.c

Legacy: This article describes a concept that has been superseded in the course of ongoing development on the Organic Design wiki. Please do not develop this any further or base work on this concept, now this page is for historic record only.

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