crackers.mx

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

crackers_export str CRKmergeInsertions_Forget(int *k, int *bid, int *new);
crackers_export str CRKmergeInsertions_OnNeed(int *k, int *bid, int *new, bit *deleteNodes);
crackers_export str CRKmergeInsertionsB_OnNeed(int *k, int *bid, int *new);
crackers_export str CRKmergeInsertions_OnNeedGradually(int *k, int *bid, int *new, bit *deleteNodes);
crackers_export str CRKmergeInsertionsB_OnNeedGradually(int *k, int *bid, int *new);
crackers_export str CRKmergeInsertions_OnNeedGraduallyRipple(int *k, int *bid, int *new, bit *deleteNodes);
crackers_export str CRKmergeInsertionsB_OnNeedGraduallyRipple(int *k, int *bid, int *new);
crackers_export str CRKextendCrackerBAT(int *k, int *bid, lng positions);
crackers_export str CRKprintAVLTree_int(int *k, int *bid);
crackers_export str CRKmergeDeletions_OnNeed(int *k, int *bid, int *new);
crackers_export str CRKmergeDeletions_OnNeedGradually(int *k, int *bid, int *new);
crackers_export str CRKmergeDeletions_OnNeedGraduallyRipple(int *k, int *bid, int *new);

#endif /* _CRACKERS_H */
   
@c
#include "mal_config.h"
#include "mal.h"
#include "mal_exception.h"
#include "crackers.h"
#include "mtime.h"
#include "bat5.h"

#define MAXPIECE 1024*100

static int maxCrackMap = 0;

static CrackIndex *Index;
static CrackTreeIndex *TreeIndex;
static AVLTreeIndex *AVLIndex;
bit IndexType = 1; /* 1 used for tree index, 0 used for bat index */
int IndexEntries = 220000; /* initial size used for the bat that stores index values*/
/* temp variables, used to test effect of stop updating the index, they operate only on one cracker bat */
int IndexSize = 0;
int IndexStop = 250000;

int
Height(struct Node * x){
        if( x == NULL )
                return -1;
        else
                return x->height;
}
/* for the comparison with an AVL Tree*/
struct Node *
SingleRotateLeftAVLIndex(int m, struct Node * node){
        struct Node * l, *lr;
	int nodeLh,nodeRh,lh;

        l = node->left;
	lr = l->right;
        node->left = l->right;
        l->right = node;

	if (node->previous == NULL)
		l->previous = NULL;
	else {
		l->previous = node->previous;
		l->isPreviousSmaller = node->isPreviousSmaller;
        }

	node->previous = l;
	node->isPreviousSmaller = TRUE;
	if (lr != NULL) {
		lr->previous = node;
		lr->isPreviousSmaller = FALSE;
	}
	if (node->head == TRUE){
		node->head = FALSE;
		l->head = TRUE;
		AVLIndex[m].Tree = l;
	}

	nodeLh = Height(node->left);
	nodeRh = Height(node->right);
	lh = Height(l->left);

	node->height = (nodeLh > nodeRh ? nodeLh : nodeRh) + 1;
        l->height = (lh > node->height ? lh : node->height) + 1;

        return l;
}

struct Node *
SingleRotateRightAVLIndex(int m, struct Node * node){
        struct Node * r, *rl;
	int nodeLh,nodeRh,rh;

        r = node->right;
	rl =  r->left;

        node->right = r->left;
        r->left = node;

	if (node->previous == NULL)
		r->previous = NULL;
	else {
		r->previous = node->previous;
		r->isPreviousSmaller = node->isPreviousSmaller;
	}
	node->previous = r;
	node->isPreviousSmaller = FALSE;

	if (rl != NULL){
		rl->previous = node;
		rl->isPreviousSmaller = TRUE;
	}

	if (node->head == TRUE){
		node->head = FALSE;
		r->head = TRUE;
		AVLIndex[m].Tree = r;
	}

	nodeLh = Height(node->left);
	nodeRh = Height(node->right);
	rh = Height(r->right);

	node->height = (nodeLh > nodeRh ? nodeLh : nodeRh) + 1;
        r->height = (rh > node->height ? rh : node->height) + 1;

        return r;
}

struct Node *
DoubleRotateLeftAVLIndex(int m, struct Node * node){
            node->left = SingleRotateRightAVLIndex(m, node->left);
            return SingleRotateLeftAVLIndex(m, node);
}

struct Node *
DoubleRotateRightAVLIndex(int m, struct Node * node){
            node->right = SingleRotateLeftAVLIndex(m, node->right);
            return SingleRotateRightAVLIndex(m, node);
}
/* end comparison with AVL tree*/

struct Node *
SingleRotateLeft(int m, struct Node * node){
        struct Node * l, *lr;
	int nodeLh,nodeRh,lh;

        l = node->left;
	lr = l->right;
        node->left = l->right;
        l->right = node;

	if (node->previous == NULL)
		l->previous = NULL;
	else {
		l->previous = node->previous;
		l->isPreviousSmaller = node->isPreviousSmaller;
        }

	node->previous = l;
	node->isPreviousSmaller = TRUE;
	if (lr != NULL) {
		lr->previous = node;
		lr->isPreviousSmaller = FALSE;
	}
	if (node->head == TRUE){
		node->head = FALSE;
		l->head = TRUE;
		TreeIndex[m].Tree = l;
	}

	nodeLh = Height(node->left);
	nodeRh = Height(node->right);
	lh = Height(l->left);

	node->height = (nodeLh > nodeRh ? nodeLh : nodeRh) + 1;
        l->height = (lh > node->height ? lh : node->height) + 1;

        return l;
}

struct Node *
SingleRotateRight(int m, struct Node * node){
        struct Node * r, *rl;
	int nodeLh,nodeRh,rh;

        r = node->right;
	rl =  r->left;

        node->right = r->left;
        r->left = node;

	if (node->previous == NULL)
		r->previous = NULL;
	else {
		r->previous = node->previous;
		r->isPreviousSmaller = node->isPreviousSmaller;
	}
	node->previous = r;
	node->isPreviousSmaller = FALSE;

	if (rl != NULL){
		rl->previous = node;
		rl->isPreviousSmaller = TRUE;
	}

	if (node->head == TRUE){
		node->head = FALSE;
		r->head = TRUE;
		TreeIndex[m].Tree = r;
	}

	nodeLh = Height(node->left);
	nodeRh = Height(node->right);
	rh = Height(r->right);

	node->height = (nodeLh > nodeRh ? nodeLh : nodeRh) + 1;
        r->height = (rh > node->height ? rh : node->height) + 1;

        return r;
}

struct Node *
DoubleRotateLeft(int m, struct Node * node){
            node->left = SingleRotateRight(m, node->left);
            return SingleRotateLeft(m, node);
}

struct Node *
DoubleRotateRight(int m, struct Node * node){
            node->right = SingleRotateLeft(m, node->right);
            return SingleRotateRight(m, node);
}


/* searching into the tree */

/* get the previous node in the index (in terms of value), the result can be any node, deleted or no */
struct Node *
getPreviousNodeAny(struct Node * current){

	struct Node *res = NULL;

	if (current->left !=NULL){
		res = current->left;
		while(res->right != NULL)
			res = res->right;
	}

	return res;	
}

/* get the next node in the index (in terms of value), the result can be any node, deleted or no */
struct Node *
getNextNodeAny(struct Node * current){

        struct Node *res = NULL;

        if (current->right !=NULL){
                res = current->right;
                while(res->left != NULL)
                        res = res->left;
        }

        return res;
}

struct Node *
getP(struct Node * current){

        struct Node *res = NULL;

	if (current->right != NULL)
		res = getP(current->right);
	if (res == NULL){
		if (current->deleted == FALSE)
			res = current;
		else
		if (current->left != NULL)
			res = getP(current->left);
	}
	return res;
}

struct Node *
getN(struct Node * current){

        struct Node *res = NULL;

	if (current->left != NULL)
		res = getN(current->left);
	if (res == NULL){
		if (current->deleted == FALSE)
			res = current;
		else
		if (current->right != NULL)
			res = getN(current->right);
	}
	return res;
}

/* get the previous node in the index (in terms of value), the result can be only a non deleted node */
struct Node *
getPreviousNode(struct Node * current, struct Node * previous){
        struct Node *res = NULL;

	if (current->left != NULL)
		res= getP(current->left);
	if (res == NULL)
		return previous;
        return res;

}

/* get the next node in the index (in terms of value), the result can be only a non deleted node */
struct Node *
getNextNode(struct Node * current, struct Node * next){

        struct Node *res = NULL;

	if (current->right != NULL)
		res= getN(current->right);
	if (res == NULL)
		return next;
        return res;
}

lng
getPreviousPosition(struct Node * current, BAT *b, BUN base, int xx, lng previous){
        struct Node *res = NULL;

	if (current->left != NULL)
		res= getP(current->left);
	if (res == NULL)
		return previous;
        return *(lng*)BUNhloc(b,base + ((res->position) * xx));

}

lng
getNextPosition(struct Node * current, BAT *b, BUN base, int xx, lng next){

        struct Node *res = NULL;

	if (current->right != NULL)
		res= getN(current->right);
	if (res == NULL)
		return next;
        return *(lng*)BUNhloc(b,base + ((res->position) * xx));
}

struct Node *
findPreviousPieceWalkingBack(struct Node * node){
	struct Node * res = NULL, *current = node;

	if (current->left != NULL)
                res= getP(current->left);
	if (res != NULL)
		return res;

	/* if nothing in the current branch we have to move back */
	while (res == NULL) {
		if (current->previous == NULL)
			return NULL;
		while  (current->isPreviousSmaller == FALSE){
			current = current->previous;
			if (current->previous == NULL)
                        	return NULL;
		}
		current = current->previous;

		if (current->deleted == FALSE)
			res = current;
		else if (current->left != NULL)
                	res= getP(current->left);
	}
	
	return res;
}

struct Node *
findNextPiece(struct Node * node){
	struct Node * res = NULL, *current = node;

	if (current->right != NULL)
                res= getN(current->right);
	if (res != NULL)
		return res;

	/* if nothing in the current branch we have to move back */
	while (res == NULL) {
		if (current->previous == NULL)
			return NULL;
		while  (current->isPreviousSmaller == TRUE){
			current = current->previous;
			if (current->previous == NULL)
                        	return NULL;
		}
		current = current->previous;

		if (current->deleted == FALSE)
			res = current;
		else if (current->right != NULL)
                	res= getN(current->right);
	}
	
	return res;
}
@= TreeOperations

bit
GetLow_@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_LT(&x,curValue,@3@1) ){	
			if (current->left == NULL){
        	                *p1 = previous;
                	        *p2 = getNextPosition(current, b, base,  xx, next);
                       	 	return 0;
                	} else
                        	/* check for the left one */
                        	return GetLow_@1(x, inclusive, current->left, b, base, xx, p1, p2, previous, getNextPosition(current, b, base,  xx, next));
		}
		if (current->right == NULL){
               	 	*p1 = getPreviousPosition(current, b, base,  xx, previous);
			*p2 = next;
			return 0;
		} else 	
			return GetLow_@1(x, inclusive, current->right, b, base, xx, p1, p2, getPreviousPosition(current, b, base,  xx, previous), next);
	}

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

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

		if (current->left == NULL){
			/* crack from the begining of the bat */
                	*p1 = previous;
			*p2 = *(lng*)BUNhloc(b, cur);
			return 0;
		} else
			/* check for the left one */
      			return GetLow_@1(x, inclusive, current->left, b, base, xx, p1, p2, previous, *(lng*)BUNhloc(b, cur));
			
	}

	if (current->right == NULL){
		/* crack until the end of the bat */
                *p1 = *(lng*)BUNhloc(b, cur);
		*p2 = next;
		return 0;
	} else 	
		/* check for the right one */
		return GetLow_@1(x, inclusive, current->right, b, base, xx, p1, p2, *(lng*)BUNhloc(b, cur), next);