crackers.mx

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

	BAT *b, *u;

	(void) k;
	indexPos = existsAVLIndex(*bid);
	if (indexPos == -1)	
		throw(MAL, "crackers.insert AVL index", "No AVL index present for this BAT");

        if ((b = BATdescriptor(*bid)) == NULL)
		throw(MAL, "crackers.insert AVL index", "Cannot access descriptor");

        if ((u = BATdescriptor(*uid)) == NULL)
		throw(MAL, "crackers.insert AVL index", "Cannot access update descriptor");

	cur = BUNfirst(u);
	last = BUNlast(u);
	xx = BUNsize(b);
	curPos = BATcount(b)-BATcount(u);
	while (cur < last){
		addAVLIndex_@1(indexPos,curPos,b);
		cur+=xx;
		curPos++;
	}
	
	BBPunfix(b->batCacheid);
	BBPunfix(u->batCacheid);
	return MAL_SUCCEED;
}

lng 
findQualifyingValuesAVLIndex_@1(@1 *low, @1 *hgh, bit *inclusiveLow, bit *inclusiveHgh, lng resSize, BAT *b, BUN first, int xx, struct Node * cur, BUN resh, BUN rest, @1 prevL)
{
	BUN rh = resh, rt = rest;
	lng size = resSize;
	
	@1 value = *(@1*)BUNtloc(b,first+cur->position*xx);
	if (cur->deleted == FALSE){
		if ( (@2_GT(&value,low,@3@1) && @2_LT(&value,hgh,@3@1)) ||
		     (@2_EQ(&value,low,@3@1) && *inclusiveLow == TRUE) ||	
		     (@2_EQ(&value,hgh,@3@1) && *inclusiveHgh == TRUE) ){
			*(oid*)rh = (oid)cur->position;
       	         	*(@1 *)rt = *(@1*)BUNtloc(b,first+cur->position*xx);
	       	         rh+=xx; rt+=xx;
        	        size++;	
		}
	}

	if (cur->left != NULL &&  @2_GT(&value,low,@3@1) && @2_LT(&prevL,hgh,@3@1) )
		size = findQualifyingValuesAVLIndex_@1(low, hgh, inclusiveLow, inclusiveHgh, size, b, first, xx, cur->left, rh, rt, prevL);
	if (cur->right != NULL && (@2_LT(&value,hgh,@3@1) || (@2_EQ(&value,hgh,@3@1) && *inclusiveHgh == TRUE)))
		size = findQualifyingValuesAVLIndex_@1(low, hgh, inclusiveLow, inclusiveHgh, size, b, first, xx, cur->right, rh, rt, value);

	return size;
}

crackers_export str CRKAVLIndexSelectBounds_@1(int *vid, int *bid, @1 *low, @1 *hgh, bit *inclusiveLow, bit *inclusiveHgh);
str
CRKAVLIndexSelectBounds_@1(int *vid, int *bid, @1 *low, @1 *hgh, bit *inclusiveLow, bit *inclusiveHgh)
{
	BAT *b, *result;
	int indexPos;
	struct Node *cur;
	int xx;
	lng  resSize;
	BUN first, resLast, resh, rest;

	indexPos = existsAVLIndex(*bid);
        if (indexPos == -1)
                throw(MAL, "crackers.insert AVL index", "No AVL index present for this BAT");
	
        if ((b = BATdescriptor(*bid)) == NULL)
		throw(MAL, "crackers.insert AVL index", "Cannot access descriptor");

	result = BATnew(TYPE_oid, TYPE_@1, (*(@1*)hgh-*(@1*)low)*2);

	/* find the node that we should start searching from */
	cur = AVLIndex[indexPos].Tree;
	first = BUNfirst(b);
	xx = BUNsize(b);

	while( @2_LT(BUNtloc(b,first+cur->position*xx),low,@3@1) && cur != NULL )		
		cur = cur->right;

	resSize = 0;
	/*if NULL then result is empty */
	if (cur == NULL){
		resLast = BUNfirst(result);
		result->batBuns->free =  resLast - result->batBuns->base;
                BATsetcount(result, 0);
		BBPkeepref(result->batCacheid);
		*vid = result->batCacheid;
		BBPunfix(b->batCacheid);

		return MAL_SUCCEED;
	}

	resh = BUNhloc(result, BUNfirst(result));
	rest = BUNtloc(result, BUNfirst(result));
	if (@2_EQ(low,BUNtloc(b,first+cur->position*xx),@3@1) && *inclusiveLow == TRUE){
		while (@2_EQ(low,BUNtloc(b,first+cur->position*xx),@3@1) && cur != NULL){
			if (cur->deleted == FALSE){
				*(oid*)resh = (oid)cur->position;
				*(@1 *)rest = *(@1 *)BUNtloc(b,first+cur->position*xx);
				resh+=xx; rest+=xx;
				resSize++;
			}
			cur = cur->right;
		}
	} else
	if (@2_EQ(low,BUNtloc(b,first+cur->position*xx),@3@1) && *inclusiveLow == FALSE){
		while(@2_EQ(low,BUNtloc(b,first+cur->position*xx),@3@1) && cur != NULL)
			cur = cur->right;
	} 

	if (cur != NULL)       
		resSize = findQualifyingValuesAVLIndex_@1(low, hgh, inclusiveLow, inclusiveHgh, resSize, b, first, xx, cur, resh, rest, *(@1*)BUNtloc(b,first+cur->position));


	resLast = BUNfirst(result) + xx*resSize;
        result->batBuns->free =  resLast - result->batBuns->base;
        BATsetcount(result, resSize);
        BBPkeepref(result->batCacheid);
        *vid = result->batCacheid;
        BBPunfix(b->batCacheid);


	return MAL_SUCCEED;
}

/* Locate and mark as deleted a node in the AVL tree, starting from a given node */
struct Node *
LocateDelete_@1(struct Node *cur, oid id, @1 *value, BAT *b, BUN first, int xx){
	struct Node * current = cur;
	if ( @2_GT(BUNtloc(b, first + current->position*xx),value,@3@1) )
		return current->right != NULL ? LocateDelete_@1(current->right, id, value, b, first, xx): NULL;	
	else
	if ( @2_LT(BUNtloc(b, first + current->position*xx),value,@3@1) )
		return current->left != NULL ? LocateDelete_@1(current->left, id, value, b, first, xx): NULL;	
	else
	if ( @2_EQ(BUNtloc(b, first + current->position*xx),value,@3@1) ){
		if ( (oid)current->position ==  id ){
			current->deleted = TRUE;
			return current;
		}
		else {
			while(1){
				if (current->right != NULL)
					current= current->right;
				if ( @2_EQ(BUNtloc(b, first + current->position*xx),value,@3@1) ){
			                if ( (oid)current->position ==  id ){
						current->deleted = TRUE;
               		 		        return current;
					} else
						continue;
				} else {
					return current;
				}
			}
		}
	}

	return NULL;
}

crackers_export str CRKdeleteFromAVL_@1(int *k, int *bid, int *uid);
/* delete from the AVL tree a collection of values */
str
CRKdeleteFromAVL_@1(int *k, int *bid, int *uid){
	BAT *b, *u;
	lng indexPos;
	BUN delt, delh, delLast, first;
	int xx;
	
	(void)k;
	
	indexPos = existsAVLIndex(*bid);
        if (indexPos == -1)
                throw(MAL, "crackers.delete from AVL index", "No AVL index present for this BAT");

        if ((b = BATdescriptor(*bid)) == NULL)
                throw(MAL, "crackers.delete from AVL index", "Cannot access descriptor");


	if ((u = BATdescriptor(*uid)) == NULL)
                throw(MAL, "crackers.delete from AVL index", "Cannot access deletions BAT");

        if (BATcount(u) == 0){
                BBPunfix(u->batCacheid);
                return MAL_SUCCEED; /* no qualifying values in the insertions */
        }

        /* if necessary, sort in place the insertions bat */
        if (u->tsorted == FALSE){
                u->batRestricted = BAT_WRITE;
                BATmirror(BATorder(BATmirror(u)));
        }

	first = BUNfirst(b);
	xx = BUNsize(b);
	delt = BUNtloc(u, BUNfirst(u));
	delh = BUNhloc(u, BUNfirst(u));
	delLast = BUNtloc(u, BUNlast(u));
	while (delt < delLast){
		LocateDelete_@1(AVLIndex[indexPos].Tree, *(oid*)delh, (@1*)delt, b, first, xx);
		delt+=xx; delh+=xx;
	}
	
	BATmode(u, TRANSIENT);
	BBPunfix(b->batCacheid);
	BBPunfix(u->batCacheid);
	
	return MAL_SUCCEED;
}

@

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

@-
The core cracking routines.

@= moveOrdered
	while (@1 @6 ){
		@2 @4= xx;
		@3 @4= xx;
		@5
	}
@

@= OThree
	while (*(@1*)tmpt @5){
		tmpt @2= xx;
		tmph @2= xx;
	}
	
	while (tmpt @3 ht){
		if ( *(@1*)tmpt @4){
			if (*(@1*)ct @5){
				scr_h[hil] = *(oid*)ch;
				scr_t[hil] = *(@1* )ct;				
				hil++;	
			}
			*(oid*)ch = *(oid*)tmph;
			*(@1 *)ct = *(@1 *)tmpt;
			ch @2= xx;
			ct @2= xx;
		
		}
		else{
			scr_h[mids] = *(oid*)tmph;
			scr_t[mids] = *(@1* )tmpt;				
			mids--;	
		}
		tmpt @2= xx;
		tmph @2= xx;
		while (tmpt @3 ht && *(@1*)tmpt @5){
			tmpt @2= xx;
			tmph @2= xx;
		}
	}
	tmph = hh;
	tmpt = ht;
	ct @2= xx*((scrH-mids)+hil);
	for(; tmpt @7 ct; tmph @6=xx, tmpt @6=xx){
		if (*(@1*)tmpt @5){
			*(oid*)hh = *(oid*)tmph;
			*(@1 *)ht = *(@1 *)tmpt;
			hh @6= xx;
			ht @6= xx;
		}
	}
	for (i= hil-1; i >= 0; i--){
		if (*(@1*)tmpt @5){
			*(oid*)hh = *(oid*)tmph;
			*(@1 *)ht = *(@1 *)tmpt;
			hh @6= xx;
			ht @6= xx;
		}	
		*(oid*)tmph = scr_h[i];
		*(@1 *)tmpt = scr_t[i];
		tmpt @6= xx;
		tmph @6= xx;
	}
	i = mids + 1;
	for (; i <= scrH; i++){
		 if (*(@1*)tmpt @5){
                        *(oid*)hh = *(oid*)tmph;
                        *(@1 *)ht = *(@1 *)tmpt;
                        hh @6= xx;
                        ht @6= xx;
                }
		*(oid*)tmph = scr_h[i];
		*(@1 *)tmpt = scr_t[i];
		tmph @6= xx;
		tmpt @6= xx;
	}
@

@= crackInThreeOrderedPieces
crackers_export str CRKcrackOrderedThree_@2_@3_@1(BAT *b, @1 low, @1 hgh, int idx_first, int idx_last);
str
CRKcrackOrderedThree_@2_@3_@1(BAT *b, @1 low, @1 hgh, int idx_first, int idx_last)
{
	BUN hh, ht, tmpt, tmph, ch, ct, t, s, fh, ft;
	oid *scr_h;
	@1  *scr_t;
	int scr_size = idx_last - idx_first +1;
	int hghShrinked = 0, lowShrinked = 0, scrH, hil, mids, probe, j;
	int xx = BUNsize(b);
	int i;

	tmph = BUNhloc(b, BUNptr(b, idx_first));
	tmpt = BUNtloc(b, BUNptr(b, idx_first));
	ht = BUNtloc(b, BUNptr(b, idx_last));
	hh = BUNhloc(b, BUNptr(b, idx_last));

	@:moveOrdered(*(@1*)tmpt @4 low,tmph,tmpt,+,lowShrinked++;,&& tmpt<=ht)@
	@:moveOrdered(*(@1*)ht @7 hgh ,hh,ht,-,hghShrinked++;,&& ht<=tmpt)@

	if (lowShrinked == idx_last - idx_first +1) return MAL_SUCCEED;
	if (hghShrinked == idx_last - idx_first +1) return MAL_SUCCEED;

	scrH = scr_size-1;	
	hil = 0; mids = scrH;
	ch = tmph; ct = tmpt;
	scr_h = (oid*) GDKmalloc(scr_size * sizeof(oid));
	scr_t = (@1 *) GDKmalloc(scr_size * sizeof(@1 ));

	probe = 25;
	t = tmpt;
	s = tmpt+(2*probe*xx);
	j=0;
	for (;t<s;t+=xx)
		j += *(@1*)t @4 low;

	if (j > probe){
		ch = tmph; ct = tmpt;
		@:OThree(@1,+,<=,@4 low,@7 hgh,-,>=)@
	}
	else{
		ch = hh; ct = ht;
		fh = tmph; ft = tmpt;
		tmph = hh; tmpt = ht;
		hh = fh; ht = ft;
		@:OThree(@1,-,>=,@7 hgh,@4 low,+,<=)@
	}
	GDKfree(scr_h);
	GDKfree(scr_t);
	
	return MAL_SUCCEED;
}

crackers_export str CRKcrackOrderedThreeL_@2_@3_@1(BAT *b, @1 low, @1 hgh, lng idx_first, lng idx_last, lng *posl, lng *posh);
str
CRKcrackOrderedThreeL_@2_@3_@1(BAT *b, @1 low, @1 hgh, lng idx_first, lng idx_last, lng *posl, lng *posh)
{
	BUN lh, lt, hh, ht, tmpt, tmph, t, s, fh, ft, mh, mt;
	oid *scr_h,*mscr_h;
	@1  *scr_t,*mscr_t;
	int scr_size = idx_last - idx_first +1;
	int hghShrinked = 0, lowShrinked = 0, scrH, hp, hil, mids, mmids, j, probe;
	int xx = BUNsize(b);
	lng pos1, pos2;

	lh = BUNhloc(b, BUNptr(b, idx_first));
	lt = BUNtloc(b, BUNptr(b, idx_first));
	ht = BUNtloc(b, BUNptr(b, idx_last));
	hh = BUNhloc(b, BUNptr(b, idx_last));

	@:moveOrdered(*(@1*)lt @4 low,lh,lt,+,lowShrinked++;,&& lt<=ht)@
	@:moveOrdered(*(@1*)ht @7 hgh ,hh,ht,-,hghShrinked++;,&& ht>=lt)@

	/*These are different cases. For now just make sure that the result will be empty.
		todo: when the index will learn from empty results return the appropriate information*/
	
	if (lowShrinked == scr_size) {
		*posl = -1;
		*posh = -1;
		return MAL_SUCCEED;
	}
	if (hghShrinked == scr_size){
		*posl =  1;
		*posh = -1;
		return MAL_SUCCEED;
	}
	/*Middle piece is empty and lt = ht + 1*/
	if (lowShrinked + hghShrinked == scr_size){
		*posl =  BUNindex(b,lt);
		*posh =  BUNindex(b,ht);
		return MAL_SUCCEED;
	}

	scrH = scr_size-1;	
	hp = 0; hil = 0; mids = scrH; mmids = 0;
	scr_h = (oid*) GDKmalloc(scr_size * sizeof(oid));
	scr_t = (@1 *) GDKmalloc(scr_size * sizeof(@1 ));
	mscr_h = (oid*) GDKmalloc(scr_size * sizeof(oid));
	mscr_t = (@1 *) GDKmalloc(scr_size * sizeof(@1 ));

	probe = 100;
	t = lt;
	s = lt+(2*probe*xx);
	j=0;
	for (;t<s;t+=xx)
		j += *(@1*)t @4 low;
	if (j > probe){
		tmph = lh;
		tmpt = lt;	
		@:OThreeLateCopying(@1,+,<=,@4 low,@7 hgh,-,>=,@5,@6)@
		*posl = pos1;
		*posh = pos2;
	}
	else{
		tmph = hh;
		tmpt = ht;	
		fh = lh; ft = lt;
		lh = hh; lt = ht;
		hh = fh; ht = ft;
		@:OThreeLateCopying(@1,-,>=,@7 hgh,@4 low,+,<=,@5,@6)@
		*posl = pos2;
		*posh = pos1;
	}
	
	GDKfree(scr_h);
	GDKfree(scr_t);
	return MAL_SUCCEED;
}
@
@= OThreeLateCopying
{
	BUN tmp1, tmp2;
	int i;

	while (*(@1*)tmpt @5){
		tmpt @2= xx;
		tmph @2= xx;
	}
	tmp1 = lt;
	while (tmpt @3 ht){
		if ( *(@1*)tmpt @4){
			if (*(@1*)lt @5){
				scr_h[hil] = *(oid*)lh;
				scr_t[hil] = *(@1* )lt;				
				hil++;	
			}
			if (*(@1*)lt @8 low && *(@1*)lt @9 hgh){
				scr_h[mids] = *(oid*)lh;
				scr_t[mids] = *(@1* )lt;				
				mids--;	
			}