crackers.mx

一个内存数据库的源代码这是服务器端还有客户端

}

bit
GetHgh_@1(@1  x, bit inclusive, struct Node * current, BAT *b, BUN base, int xx, lng *p1, lng *p2, lng previous, lng next){

        BUN cur, curValue;	

	cur = base + ((current->position) * xx);
	curValue = BUNtloc(b, cur);

	if (current->deleted == TRUE){
		if ( @2_EQ(&x,curValue,@3@1) || @2_GT(&x,curValue,@3@1) ){
			 if (current->right == NULL){
                       	 	*p1 = getPreviousPosition(current, b, base,  xx, previous);
                        	*p2 = next;
                        	return 0;
                	} else
                        	return GetHgh_@1(x, inclusive, current->right, b, base, xx, p1, p2, getPreviousPosition(current, b, base,  xx, previous), next);
		}
		if (current->left == NULL){
               	 	*p1 = previous;
                	*p2 = getNextPosition(current, b, base,  xx, next);
               	 	return 0;
	        } else
                	return GetHgh_@1(x, inclusive, current->left, b, base, xx, p1, p2, previous, getNextPosition(current, b, base,  xx, next));

	}

	if ( @2_EQ(&x,curValue,@3@1) && (inclusive == FALSE || (inclusive == TRUE && current->inclusive == FALSE))){
		*p2 = *(lng*)BUNhloc(b, cur);	
		return 1;
	}	

	if ( @2_GT(&x,curValue,@3@1) || @2_EQ(&x,curValue,@3@1) ){

		if (current->right == NULL){
			/* crack until the end of the BAT if this was the last index entry but the needed value is still bigger */
			*p1 = *(lng*)BUNhloc(b, cur);
                	*p2 = next;
			return 0;
		} else
			/* check for the right one */
      			return GetHgh_@1(x, inclusive, current->right, b, base, xx, p1, p2, *(lng*)BUNhloc(b, cur), next);
	}

	/* then it is smaller than the current value */
	if (current->left == NULL){
		/* crack from the beginning of the bat until here */
		*p1 = previous;
               	*p2 = *(lng*)BUNhloc(b, cur);
		return 0;
	} else	
		/* check for the left one */	
		return GetHgh_@1(x, inclusive, current->left, b, base, xx, p1, p2, previous, *(lng*)BUNhloc(b, cur));	
}

struct Node *
InsertTree_@1(int m, int indexPosition, @1 value, bit inclusive, lng crackPosition, struct Node * current, BAT * b, BUN base, int xx){
	
	BUN cur, curValue, curPosition, Lchild, LchildValue, Rchild, RchildValue;
	int lh, rh;
	bit use;
	struct Node *temp;

	if (current == NULL){
        	current = (struct Node *)GDKmalloc(sizeof(struct Node));
                current->position = indexPosition;
                current->inclusive = inclusive;
		current->height = 0;
                current->left = NULL;
		current->right = NULL;
		current->head = FALSE;
		current->deleted = FALSE;
		current->previous = NULL;
		current->isPreviousSmaller = FALSE;
		current->hols = 0;
		goto end;
        }

	cur = base + ((current->position) * xx);
        curValue = BUNtloc(b, cur);

	/* reuse if possible nodes that have been deleted with lazy deletion */
	use = FALSE;
	if (current->deleted == TRUE){
		if (current->left != NULL && current->right != NULL){
			Lchild = base + (((getPreviousNodeAny(current))->position) * xx);
                        LchildValue = BUNtloc(b, Lchild);
			Rchild = base + (((getNextNodeAny(current))->position) * xx);
                        RchildValue = BUNtloc(b, Rchild);
			
			if ( ( @2_LT(&value,RchildValue,@3@1) || (@2_EQ(&value,RchildValue,@3@1) && inclusive == TRUE && current->right->inclusive == FALSE))  &&
			     ( @2_GT(&value,LchildValue,@3@1) || (@2_EQ(&value,LchildValue,@3@1) && inclusive == FALSE && current->left->inclusive == TRUE) ) )
				use = TRUE;
			
		} else
		if (current->left != NULL && current->right == NULL){
			Lchild = base + (((getPreviousNodeAny(current))->position) * xx);
                        LchildValue = BUNtloc(b, Lchild);

			if ( @2_GT(&value,LchildValue,@3@1) || (@2_EQ(&value,LchildValue,@3@1) && inclusive == FALSE && current->left->inclusive == TRUE) )
				use = TRUE;
		} else
		if (current->left == NULL && current->right != NULL){
			Rchild = base + (((getNextNodeAny(current))->position) * xx);
                        RchildValue = BUNtloc(b, Rchild);
			
			if ( @2_LT(&value,RchildValue,@3@1) || (@2_EQ(&value,RchildValue,@3@1) && inclusive == TRUE && current->right->inclusive == FALSE) )
				use = TRUE;
		} else
		if (current->left == NULL && current->right == NULL)
				use = TRUE;

		if (use == TRUE){
        		curPosition = BUNhloc(b, cur);
			*(lng*)curPosition = crackPosition;
                        *(@1*)curValue = value;
			current->inclusive = inclusive;
                        current->deleted = FALSE;
                        return NULL;
		}
	}

        if ( @2_LT(&value,curValue,@3@1) || (@2_EQ(&value,curValue,@3@1) && inclusive == TRUE && current->inclusive == FALSE) ){

		if ( (temp = InsertTree_@1(m, indexPosition, value, inclusive, crackPosition, current->left, b, base, xx)) == NULL )
                	return NULL;

		current->left = temp;
		temp->previous = current;
		temp->isPreviousSmaller = FALSE;

                if ( Height(current->left) - Height(current->right) == 2 ){
		        Lchild = base + ((current->left->position) * xx);
        		LchildValue = BUNtloc(b, Lchild);

                    	if ( @2_LT(&value,LchildValue,@3@1) || (@2_EQ(&value,LchildValue,@3@1) && inclusive == TRUE && current->left->inclusive == FALSE) )
                        	current = SingleRotateLeft(m, current);
                    	else
                        	current = DoubleRotateLeft(m, current);
		}
        } else
        if ( @2_GT(&value,curValue,@3@1) || (@2_EQ(&value,curValue,@3@1) && inclusive == FALSE && current->inclusive == TRUE) ){

		if ( (temp = InsertTree_@1(m, indexPosition, value, inclusive, crackPosition, current->right, b, base, xx)) == NULL )
			return NULL;

                current->right = temp;
		temp->previous = current;
		temp->isPreviousSmaller = TRUE;


                if ( Height(current->right) - Height(current->left) == 2 ){
			Rchild = base + ((current->right->position) * xx);
                        RchildValue = BUNtloc(b, Rchild);

                        if ( @2_GT(&value,RchildValue,@3@1) || (@2_EQ(&value,RchildValue,@3@1) && inclusive == FALSE && current->right->inclusive == TRUE) )
                        	current = SingleRotateRight(m, current);
                    	else
                        	current = DoubleRotateRight(m, current);
		}
        }

	end:;
	lh = Height(current->left);
	rh = Height(current->right);
		
        current->height = (lh > rh? lh : rh) + 1;
        return current;
}

struct Node *
findNodeH_@1(@1  x, bit inclusive, struct Node * current, BAT *b, BUN base, int xx, struct Node * next){

        BUN cur,curValue;	

	cur = base + ((current->position) * xx);
	curValue = BUNtloc(b, cur);

	if ( @2_EQ(&x,curValue,@3@1) && (inclusive == FALSE || (inclusive == TRUE && current->inclusive == FALSE)) )
		return (current->deleted == TRUE) ? getNextNode(current, next) : current;

        if( @2_GT(&x,curValue,@3@1) || @2_EQ(&x,curValue,@3@1) ){

		if (current->right == NULL)
			return next;
		else
      			return findNodeH_@1(x, inclusive, current->right, b, base, xx, next);
	}

	if (current->left == NULL)
		return (current->deleted == TRUE) ? getNextNode(current, next) : current;
	else		
		return findNodeH_@1(x, inclusive, current->left, b, base, xx, (current->deleted == TRUE) ? getNextNode(current, next) : current);	
}

struct Node *
findNodeL_@1(@1  x, bit inclusive, struct Node * current, BAT *b, BUN base, int xx, struct Node * prev){

	BUN cur,curValue;

	cur = base + ((current->position) * xx);
	curValue = BUNtloc(b, cur);

	if ( @2_EQ(&x,curValue,@3@1) && (inclusive == FALSE || (inclusive == TRUE && current->inclusive == TRUE)) )
		return (current->deleted == TRUE) ? getPreviousNode(current, prev) : current;

        if( @2_LT(&x,curValue,@3@1) || @2_EQ(&x,curValue,@3@1) ){

		if (current->left == NULL)
			return prev;
		else
			return findNodeL_@1(x, inclusive, current->left, b, base, xx, prev);
	}

	if (current->right == NULL)
		return (current->deleted == TRUE) ? getPreviousNode(current, prev) : current;
	else
		return findNodeL_@1(x, inclusive, current->right, b, base, xx, (current->deleted == TRUE) ? getPreviousNode(current, prev) : current);
}

void
PartiallyLazyFreeAVLTree_@1(struct Node * current, @1 value, BAT *b, BUN base, int xx){

	BUN cur,curValue;

        cur = base + ((current->position) * xx);
        curValue = BUNtloc(b, cur);

	if (current->left != NULL)
		PartiallyLazyFreeAVLTree_@1(current->left, value, b, base, xx);

	if (current->right != NULL)
		PartiallyLazyFreeAVLTree_@1(current->right, value, b, base, xx);

	if( @2_LT(&value,curValue,@3@1) || (@2_EQ(&value,curValue,@3@1) && current->inclusive == FALSE) )
		current->deleted = TRUE;
	return;
}

struct Node *
InsertAVLIndex_@1(int m, int indexPosition, @1 value,  struct Node * current, BAT * b, BUN base, int xx){
	
	BUN cur, curValue, Lchild, LchildValue, Rchild, RchildValue;
	int lh, rh;
	struct Node *temp;

	if (current == NULL){
        	current = (struct Node *)GDKmalloc(sizeof(struct Node));
                current->position = indexPosition;
                current->inclusive = TRUE;
		current->height = 0;
                current->left = NULL;
		current->right = NULL;
		current->head = FALSE;
		current->deleted = FALSE;
		current->previous = NULL;
		current->isPreviousSmaller = FALSE;
		current->hols = 0;
		goto end;
        }

	cur = base + ((current->position) * xx);
        curValue = BUNtloc(b, cur);


        if ( @2_LT(&value,curValue,@3@1) || @2_EQ(&value,curValue,@3@1) ){

		if ( (temp = InsertAVLIndex_@1(m, indexPosition, value,  current->left, b, base, xx)) == NULL )
                	return NULL;

		current->left = temp;
		temp->previous = current;
		temp->isPreviousSmaller = FALSE;

                if ( Height(current->left) - Height(current->right) == 2 ){
		        Lchild = base + ((current->left->position) * xx);
        		LchildValue = BUNtloc(b, Lchild);

                    	if ( @2_LT(&value,LchildValue,@3@1) || @2_EQ(&value,LchildValue,@3@1) )
                        	current = SingleRotateLeftAVLIndex(m, current);
                    	else
                        	current = DoubleRotateLeftAVLIndex(m, current);
		}
        } else {

		if ( (temp = InsertAVLIndex_@1(m, indexPosition, value, current->right, b, base, xx)) == NULL )
			return NULL;

                current->right = temp;
		temp->previous = current;
		temp->isPreviousSmaller = TRUE;


                if ( Height(current->right) - Height(current->left) == 2 ){
			Rchild = base + ((current->right->position) * xx);
                        RchildValue = BUNtloc(b, Rchild);

                        if ( @2_GT(&value,RchildValue,@3@1) )
                        	current = SingleRotateRightAVLIndex(m, current);
                    	else
                        	current = DoubleRotateRightAVLIndex(m, current);
		}
        }

	end:;
	lh = Height(current->left);
	rh = Height(current->right);
		
        current->height = (lh > rh? lh : rh) + 1;
        return current;
}
@

@c
@:TreeOperations(chr,simple,)@
@:TreeOperations(sht,simple,)@
@:TreeOperations(int,simple,)@
@:TreeOperations(lng,simple,)@
@:TreeOperations(flt,simple,)@
@:TreeOperations(dbl,simple,)@
@:TreeOperations(date,atom,TYPE_)@




void
FreeAVLTree(struct Node * current){

	if (current->left != NULL)
		FreeAVLTree(current->left);

	if (current->right != NULL)
		FreeAVLTree(current->right);

	GDKfree(current);
		
	return;
}

int
existsIndex(int bid)
{
	int i;
	
	for (i = 0; i < maxCrackMap; i++)
		if (Index[i].bid == bid)
			return i;
	return -1;
}

int
existsAVLIndex(int bid)
{
        int i;

        for (i = 0; i < maxCrackMap; i++)
                if (AVLIndex[i].bid == bid)
                        return i;
        return -1;
}


int
existsTreeIndex(int bid)
{
	int i;
	
	for (i = 0; i < maxCrackMap; i++)
		if (TreeIndex[i].bid == bid)
			return i;
	return -1;
}

void
printAVLTree(struct Node * current, BAT *b, BUN base, int xx){
	
	BUN cur;

	cur = base + ((current->position) * xx);
	if (current->deleted == FALSE) {
		printf("\n %lld, %d  Hols:%lld ", *(lng*)BUNhloc(b, cur), *(int*)BUNtloc(b, cur), current->hols );
	} else
		printf("\n DELETED %lld, %d  Hols:%lld ", *(lng*)BUNhloc(b, cur), *(int*)BUNtloc(b, cur), current->hols );
	
	if (current->left != NULL)
                printAVLTree(current->left, b, base, xx);

        if (current->right != NULL)
                printAVLTree(current->right, b, base, xx);

        return;

}

str
CRKprintAVLTree_int(int *k, int *bid){
	BAT *c;
	int zz, position;
	BUN idxFirst;

	(void) k;

	position = existsTreeIndex(*bid);
        if (position == -1)
                fprintf(stderr, " the crack index does not exist \n");

	if ((c = BATdescriptor(TreeIndex[position].cid)) == NULL)
                throw(MAL, "crackers.CRKprintAVLTree_int", "Cannot access cracker index");

        zz = BUNsize(c);
        idxFirst = BUNfirst(c);
	printAVLTree(TreeIndex[position].Tree, c, idxFirst, zz);

	BBPunfix(c->batCacheid);

	return MAL_SUCCEED;
}

@= CreateNewIndex

int
newTreeIndex_@1(int bid, int cbid)
{
	int i, freemap = -1, units = 1024;
	BAT *b;
	
	for (i = 0; i < maxCrackMap; i++)
		if (TreeIndex[i].bid == -1)
			freemap = i;

	if (freemap != -1) {
		TreeIndex[freemap].bid = bid;
		return freemap;
	}

	if (i == maxCrackMap) {
		CrackTreeIndex *x;

		if (maxCrackMap > 0)
			units = (int) (1.2 * maxCrackMap);
		x = (CrackTreeIndex *) GDKmalloc(sizeof(CrackTreeIndex) * units);
		memset(x, 0, sizeof(CrackTreeIndex) * units);
		if (TreeIndex) {
			fprintf(stderr, "reallocate index \n");
			memcpy(x, TreeIndex, sizeof(CrackTreeIndex) * i);
			GDKfree(TreeIndex);
		}
		TreeIndex = x;
		maxCrackMap = units;
	}

	TreeIndex[i].bid = bid;
	TreeIndex[i].cbid = cbid;
	b = BATnew(TYPE_lng, TYPE_@1, IndexEntries);	/* TODO: size */
	BBPkeepref(b->batCacheid);
	TreeIndex[i].cid = b->batCacheid;