Topic: [ANN] cbitcoin 2.0 - A Bitcoin Library in C - page 4. (Read 17227 times)

#include 
#include 
#include 
#include 

#define CB_BTREE_ORDER 8
#define CB_BTREE_HALF_ORDER CB_BTREE_ORDER/2

typedef struct{
	void * parent;
	void * children[CB_BTREE_ORDER + 1];
	unsigned char numElements;
} CBBTreeNode;

typedef struct{
	unsigned char found;
	CBBTreeNode * node;
	unsigned char pos;
} CBFindResult;

typedef struct{
	unsigned char keySize;
	unsigned char dataSize;
	int nodeSize;
	CBBTreeNode * root;
} CBAssociativeArray;

CBFindResult CBAssociativeArrayFind(CBAssociativeArray * self, unsigned char * key);
void CBAssociativeArrayInsert(CBAssociativeArray * self, unsigned char * key, void * data, CBFindResult pos, CBBTreeNode * right);
CBFindResult CBBTreeNodeBinarySearch(CBBTreeNode * self, unsigned char * key, unsigned char keySize);
void CBInitAssociativeArray(CBAssociativeArray * self, unsigned char keySize, unsigned char dataSize);

CBFindResult CBAssociativeArrayFind(CBAssociativeArray * self, unsigned char * key){
	CBFindResult result;
	CBBTreeNode * node = self->root;
	for (;;) {
		result = CBBTreeNodeBinarySearch(node, key, self->keySize);
		if (result.found){
			result.node = node;
			return result;
		}else{
			if (node->children[result.pos])
				node = node->children[result.pos];
			else{
				result.node = node;
				return result;
			}
		}
	}
}
void CBAssociativeArrayInsert(CBAssociativeArray * self, unsigned char * key, void * data, CBFindResult pos, CBBTreeNode * right){
	// See if we can insert data in this node
	unsigned char * keys = (unsigned char *)(pos.node + 1);
	unsigned char * dataElements = keys + self->keySize * CB_BTREE_ORDER;
	if (pos.node->numElements < CB_BTREE_ORDER) {
		if (pos.node->numElements > pos.pos){
			memmove(keys + (pos.pos + 1) * self->keySize, keys + pos.pos * self->keySize, (pos.node->numElements - pos.pos) * self->keySize);
			memmove(dataElements + (pos.pos + 1) * self->dataSize, dataElements + pos.pos * self->dataSize, (pos.node->numElements - pos.pos) * self->dataSize);
			memmove(pos.node->children + pos.pos + 2, pos.node->children + pos.pos + 1, (pos.node->numElements - pos.pos) *  sizeof(*pos.node->children));
		}
		memcpy(keys + pos.pos * self->keySize, key, self->keySize);
		memcpy(dataElements + pos.pos * self->dataSize, data, self->dataSize);
		pos.node->children[pos.pos + 1] = right;
		pos.node->numElements++;
	}else{
		CBBTreeNode * new = malloc(self->nodeSize);
		unsigned char * newKeys = (unsigned char *)(new + 1);
		unsigned char * newData = newKeys + self->keySize * CB_BTREE_ORDER;
		new->numElements = CB_BTREE_HALF_ORDER;
		pos.node->numElements = CB_BTREE_HALF_ORDER;
		unsigned char * midKey;
		unsigned char * midVal;
		if (pos.pos >= CB_BTREE_HALF_ORDER) {
			if (pos.pos == CB_BTREE_HALF_ORDER) {
				memcpy(newKeys, keys + CB_BTREE_HALF_ORDER * self->keySize, CB_BTREE_HALF_ORDER * self->keySize);
				memcpy(newData, dataElements + CB_BTREE_HALF_ORDER * self->dataSize, CB_BTREE_HALF_ORDER * self->dataSize);
				memcpy(new->children + 1, pos.node->children + CB_BTREE_HALF_ORDER + 1, CB_BTREE_HALF_ORDER * sizeof(*new->children));
				new->children[0] = right;
				midKey = key;
				midVal = data;
			}else{
				if (pos.pos > CB_BTREE_HALF_ORDER + 1){
					memcpy(newKeys, keys + (CB_BTREE_HALF_ORDER + 1) * self->keySize, (pos.pos - CB_BTREE_HALF_ORDER - 1) * self->keySize);
					memcpy(newData, dataElements + (CB_BTREE_HALF_ORDER + 1) * self->dataSize, (pos.pos - CB_BTREE_HALF_ORDER - 1)  * self->dataSize);
				}
				memcpy(newKeys + (pos.pos - CB_BTREE_HALF_ORDER - 1) * self->keySize, key, self->keySize);
				memcpy(newData + (pos.pos - CB_BTREE_HALF_ORDER - 1) * self->dataSize, data, self->dataSize);
				memcpy(newKeys + (pos.pos - CB_BTREE_HALF_ORDER) * self->keySize, keys + pos.pos * self->keySize, (CB_BTREE_ORDER - pos.pos) * self->keySize);
				memcpy(newData + (pos.pos - CB_BTREE_HALF_ORDER) * self->dataSize, dataElements + pos.pos * self->dataSize, (CB_BTREE_ORDER - pos.pos) * self->dataSize); // o 0 i 1 ii 2 iii 3 iv
				memcpy(new->children, pos.node->children + CB_BTREE_HALF_ORDER + 1, (pos.pos - CB_BTREE_HALF_ORDER) * sizeof(*new->children));
				new->children[pos.pos - CB_BTREE_HALF_ORDER] = right;
				if (CB_BTREE_ORDER > pos.pos)
					memcpy(new->children + pos.pos - CB_BTREE_HALF_ORDER + 1, pos.node->children + pos.pos + 1, (CB_BTREE_ORDER - pos.pos) * sizeof(*new->children));
				midKey = keys + CB_BTREE_HALF_ORDER * self->keySize;
				midVal = dataElements + CB_BTREE_HALF_ORDER * self->dataSize;
			}
		}else{
			memcpy(newKeys, keys + CB_BTREE_HALF_ORDER * self->keySize, CB_BTREE_HALF_ORDER * self->keySize);
			memcpy(newData, dataElements + CB_BTREE_HALF_ORDER * self->dataSize, CB_BTREE_HALF_ORDER * self->dataSize);
			memcpy(new->children, pos.node->children + CB_BTREE_HALF_ORDER, (CB_BTREE_HALF_ORDER + 1) * sizeof(*new->children));
			memmove(keys + (pos.pos + 1) * self->keySize, keys + pos.pos * self->keySize, (CB_BTREE_HALF_ORDER - pos.pos) * self->keySize);
			memmove(dataElements + (pos.pos + 1) * self->dataSize, dataElements + pos.pos * self->dataSize, (CB_BTREE_HALF_ORDER - pos.pos) * self->dataSize);
			if (CB_BTREE_HALF_ORDER > 1 + pos.pos)
				memmove(pos.node->children + pos.pos + 2, pos.node->children + pos.pos + 1, (CB_BTREE_HALF_ORDER - pos.pos - 1) * self->dataSize);
			memcpy(keys + pos.pos * self->keySize, key, self->keySize);
			memcpy(dataElements + pos.pos * self->dataSize, data, self->dataSize);
			pos.node->children[pos.pos + 1] = right;
			midKey = keys + CB_BTREE_HALF_ORDER * self->keySize;
			midVal = dataElements + CB_BTREE_HALF_ORDER * self->dataSize;
		}
		if ( ! pos.node->parent) {
			self->root = malloc(self->nodeSize);
			self->root->numElements = 0;
			self->root->parent = NULL;
			pos.node->parent = self->root;
			self->root->children[0] = pos.node;
		}
		new->parent = pos.node->parent;
		CBFindResult res = CBBTreeNodeBinarySearch(pos.node->parent, midKey, self->keySize);
		res.node = pos.node->parent;
		return CBAssociativeArrayInsert(self, midKey, midVal, res, new);
	}
}
CBFindResult CBBTreeNodeBinarySearch(CBBTreeNode * self, unsigned char * key, unsigned char keySize){
	CBFindResult res;
	res.found = 0;
	if ( ! self->numElements) {
		res.pos = 0;
		return res;
	}
	unsigned char left = 0;
	unsigned char right = self->numElements - 1;
	unsigned char * keys = (unsigned char *)(self + 1);
	int cmp;
	while (left <= right) {
		res.pos = (right+left)/2;
		cmp = memcmp(key, keys + res.pos * keySize, keySize);
		if (cmp == 0) {
			res.found = 1;
			break;
		}else if (cmp < 0){
			if ( ! res.pos)
				break;
			right = res.pos - 1;
		}else
			left = res.pos + 1;
	}
	if (cmp > 0)
		res.pos++;
	return res;
}
void CBInitAssociativeArray(CBAssociativeArray * self, unsigned char keySize, unsigned char dataSize){
	self->keySize = keySize;
	self->dataSize = dataSize;
	self->nodeSize = sizeof(*self->root) + (keySize + dataSize) * CB_BTREE_ORDER;
	self->root = malloc(self->nodeSize);
	self->root->parent = NULL;
	self->root->numElements = 0;
	for (unsigned char x = 0; x < CB_BTREE_ORDER + 1; x++)
		self->root->children[x] = NULL;
}

int main(){
	srand(1);
	CBAssociativeArray array;
	CBInitAssociativeArray(&array, 10, 10);
	int size = CB_BTREE_ORDER * (CB_BTREE_ORDER + 2) * 10;;
	unsigned char * keys = malloc(size);
	for (int x = 0; x < size; x++) {
		keys[x] = rand();
	}
	for (int x = 0; x < size; x += 10) {
		CBAssociativeArrayInsert(&array, keys + x, keys + x, CBAssociativeArrayFind(&array, keys + x), NULL);
		for (int y = 0; y <= x; y += 10) {
			if ( ! CBAssociativeArrayFind(&array, keys + y).found) {
				printf("RANDOM FIND FAIL %u - %u\n", y, x);
				return 1;
			}
		}
	}
    return 0;
}