gdk_search.mx

这个是内存数据库中的一个管理工具

			case TYPE_dbl:
			case TYPE_lng:
				@:starthash(lng,hloc)@
#endif
			default:
				@:starthash(any,head)@
			}
		} while (r < p && mask < cnt && (mask <<= 2));

		/* finish the hashtable with the current mask */
		p = r;
		switch (tpe) {
#ifndef NOEXPAND_CHR
		case TYPE_chr:
			@:finishhash(chr,hloc)@
#endif
#ifndef NOEXPAND_BTE
		case TYPE_bte:
			@:finishhash(bte,hloc)@
#endif
#ifndef NOEXPAND_SHT
		case TYPE_sht:
			@:finishhash(sht,hloc)@
#endif
#if !defined(NOEXPAND_INT) || !defined(NOEXPAND_FLT)
		case TYPE_int:
		case TYPE_flt:
			@:finishhash(int,hloc)@
#endif
#if !defined(NOEXPAND_DBL) || !defined(NOEXPAND_LNG)
		case TYPE_dbl:
		case TYPE_lng:
			@:finishhash(lng,hloc)@
#endif
		default:
			@:finishhash(any,head)@
		}
		b->hhash = BATmirror(b)->thash = h;
	}
	gdk_unset_lock(GDKhashLock[ABS(b->batCacheid) & BBPLOCKMASK], "BAThash");
	return b;
}

@-
The entry on which a value hashes can be calculated with the
routine @%HASHprobe@.
@c
hash_t
HASHprobe(Hash *h, ptr v)
{
	switch (ATOMstorage(h->type)) {
#ifndef NOEXPAND_CHR
	case TYPE_chr:
		return hash_chr(h, v);
#endif
#ifndef NOEXPAND_BTE
	case TYPE_bte:
		return hash_bte(h, v);
#endif
#ifndef NOEXPAND_SHT
	case TYPE_sht:
		return hash_sht(h, v);
#endif
#if !defined(NOEXPAND_INT) || !defined(NOEXPAND_FLT)
	case TYPE_int:
	case TYPE_flt:
		return hash_int(h, v);
#endif
#if !defined(NOEXPAND_DBL) || !defined(NOEXPAND_LNG)
	case TYPE_dbl:
	case TYPE_lng:
		return hash_lng(h, v);
#endif
	default:
		return hash_any(h, v);
	}
}

BAT *
HASHprint(BAT *b)
{
#if SIZEOF_OID == SIZEOF_INT
	BAT *bn = BATnew(BAThtype(b), TYPE_int, BATcount(b));
#else
	BAT *bn = BATnew(BAThtype(b), TYPE_lng, BATcount(b));
#endif
	BUN p, q;

	if (bn == NULL)
		return NULL;
	if (!(b && b->hhash))
		return 0;
	BATloop(b, p, q) {
		size_t i = HASHprobe(b->hhash, BUNhead(b, p));

		bunfastins(bn, BUNhead(b, p), &i);
	}
	bn->hsorted = BAThordered(b);
	bn->tsorted = FALSE;
	return bn;
      bunins_failed:
	BBPreclaim(bn);
	return NULL;
}

hash_t
HASHlist(Hash *h, size_t i)
{
	hash_t j;
	hash_t c = 1;

	while ((j = h->link[i]) != HASH_MAX) {
		c++;
		i = j;
		if (i > h->lim) {
			stream_printf(GDKout, "hash inconsistency link " SZFMT "\n", i);
			break;
		}
	}
	return c;
}

void
HASHremove(BAT *b)
{
	if (b->hhash) {
		BAT *p = BBP_cache(VIEWparent(b));
		BAT *m = BATmirror(b);

		if (p && b->hhash == p->hhash) {
			GDKerror("HASHremove: view-bat cannot remove parent hash-table\n");
			assert(0);
		} else {
			HEAPfree(b->hhash->heap);
			if (b->hhash->heap->storage & STORE_MMAP)
				HEAPdelete(b->hhash->heap, BBP_physical(b->batCacheid), (b->batCacheid > 0) ? "hhash" : "thash");
			GDKfree(b->hhash->heap);
			GDKfree(b->hhash);
		}
		if (m)
			m->thash = NULL;
		b->hhash = NULL;
	}
}

void
HASHdestroy(BAT *b)
{
	HASHremove(b);
	if (BATmirror(b))
		HASHremove(BATmirror(b));
}

int HASHgonebad(BAT *b, ptr v)
{
    Hash *h = b->hhash;
    if (h == NULL) return 1; /* no hash is bad hash? */

    if (h->mask*2 < BATcount(b)) {
        int (*cmp)(ptr, ptr) = BATatoms[b->htype].atomCmp;
	hash_t cnt, hit, i = h->hash[HASHprobe(h, v)];
        for(cnt=hit=1; i != HASH_MAX; i = h->link[i], cnt++) 
	    hit += ((*cmp)(v,BUNhead(b,BUNptr(b,i))) == 0);

        if (cnt/hit > 4) return 1; /* linked list too long */

        /* in this case, linked lists are long but contain the desired values 
         * such hash tables may be useful for locating all duplicates */
    }
    return 0;  /* a-ok */
}

@}

@+ Binary Search on a Sorted BAT
We have two main routines, @`SORTfndfirst@5(b,v) and @`SORTfndlast@5(b,v), that
search for a TAIL value 'v' in a sorted BAT. If the value is present, 
the first routine returns a pointer to its first occurrence, while the second
routine returns a pointer to the BUN just after the last occurrence of 'v'.
In case value 'v' does not occur in the tail of BAT b, both routines return
a pointer to the first BUN with a tail value larger than 'v' 
(i.e., @%BUNfirst(b)@, in case all tail values are larger than 'v'); 
or @%BUNlast(b)@, in case all tail values are smaller than 'v'.
@
@
From the above routines we now also defined the @`SORTfnd@5 and @%SORTfnd_tpe@
routines that look for a certain value and return a (not necessarily the first
or last) reference to it, or NULL (if the value does not exist).

Note: of the SORTfnd, only @`SORTfndfirst@5(b,v) and
@`SORTfndlast@5(b,v) work on the tail of a bat!
@
@

@- Range Binary Search
Type-specific versions of @:SORTfndfirst@ are available using macro
expansions. It finds the first BUN larger or equal than a certain
value and expands to @`SORTfndfirst_chr@5, @`SORTfndfirst_sht@5,
@`SORTfndfirst_int@5, @`SORTfndfirst_flt@5, @`SORTfndfirst_lng@5,
@`SORTfndfirst_dbl@5, @`SORTfndfirst_loc@5 and @`SORTfndfirst_var@5.

Type-specific versions of @:SORTfndlast@ are available using macro
expansions. It finds the first BUN smaller or equal than a certain
value and expands to @`SORTfndlast_chr@5, @`SORTfndlast_sht@5,
@`SORTfndlast_int@5, @`SORTfndlast_flt@5, @`SORTfndlast_lng@5,
@`SORTfndlast_dbl@5, @`SORTfndlast_loc@5 and @`SORTfndlast_var@5.
@{
@h
/* type specific binary search implementations */
gdk_export BUN SORTfnd_chr(BAT *b, ptr v);
gdk_export BUN SORTfnd_bte(BAT *b, ptr v);
gdk_export BUN SORTfnd_sht(BAT *b, ptr v);
gdk_export BUN SORTfnd_int(BAT *b, ptr v);
gdk_export BUN SORTfnd_flt(BAT *b, ptr v);
gdk_export BUN SORTfnd_lng(BAT *b, ptr v);
gdk_export BUN SORTfnd_dbl(BAT *b, ptr v);
gdk_export BUN SORTfnd_loc(BAT *b, ptr v);
gdk_export BUN SORTfnd_var(BAT *b, ptr v);
gdk_export BUN SORTfndfirst_chr(BAT *b, ptr v);
gdk_export BUN SORTfndfirst_bte(BAT *b, ptr v);
gdk_export BUN SORTfndfirst_sht(BAT *b, ptr v);
gdk_export BUN SORTfndfirst_int(BAT *b, ptr v);
gdk_export BUN SORTfndfirst_flt(BAT *b, ptr v);
gdk_export BUN SORTfndfirst_lng(BAT *b, ptr v);
gdk_export BUN SORTfndfirst_dbl(BAT *b, ptr v);
gdk_export BUN SORTfndfirst_loc(BAT *b, ptr v);
gdk_export BUN SORTfndfirst_var(BAT *b, ptr v);
gdk_export BUN SORTfndlast_chr(BAT *b, ptr v);
gdk_export BUN SORTfndlast_bte(BAT *b, ptr v);
gdk_export BUN SORTfndlast_sht(BAT *b, ptr v);
gdk_export BUN SORTfndlast_int(BAT *b, ptr v);
gdk_export BUN SORTfndlast_flt(BAT *b, ptr v);
gdk_export BUN SORTfndlast_lng(BAT *b, ptr v);
gdk_export BUN SORTfndlast_dbl(BAT *b, ptr v);
gdk_export BUN SORTfndlast_loc(BAT *b, ptr v);
gdk_export BUN SORTfndlast_var(BAT *b, ptr v);

#endif /* _GDK_SEARCH_H_ */

@-
@}
By Peter sept-99. This is a simple implementation that avoids all multiply
and divs on most bats by using integer BUNindex numbers rather than absolute
pointers (the BUNptr employed to obtain a pointer uses shift where possible).
Also, the gradient-based approach has been dropped again, which allows all
atoms to be treated in one macro. Main motivation: distrust of gradient
performance on odmg data and its high mult/div overhead.
@{
@= SORTfnd
BUN
SORTfndfirst_@2(BAT *b, ptr v)
{
	BUN end = BUNfirst(b), cur = end;
	size_t lo = BUNindex(b,end), hi = BUNindex(b,BUNlast(b));
	int cmp = 1, bunsize = BUNsize(b);

        if (lo >= hi || @3_CMP(BUNt@1(b, cur), v, @4)>=0) {
		/* shortcut: if BAT is empty or first (and hence all) tail
		 * value is >= v, we're done. */
		return cur;
	}
	while (lo < hi) {
		size_t mid = (lo+hi)>>1;

		cur = BUNptr(b, mid);
		cmp = @3_CMP(BUNt@1(b, cur), v, @4);
		if (cmp < 0) {
			lo = ++mid;
			cur += bunsize;
		} else if (cmp > 0) {
			hi = mid;
		} else {
			break;
		}
	}
	if (cmp == 0 && b->tkey == 0) {  /* shift over multiple equals */
		while((cur-=bunsize) >= end) {
			if (!@3_EQ(BUNt@1(b,cur),v,@4))
				break;
		}
		cur += bunsize;
	}
	return cur;
}

BUN
SORTfndlast_@2(BAT *b, ptr v)
{
	BUN end = BUNlast(b), cur = end;
	size_t lo = BUNindex(b,BUNfirst(b)), hi = BUNindex(b,end);
	int cmp = 1, bunsize = BUNsize(b);

        if (lo >= hi || @3_CMP(BUNt@1(b, cur-bunsize), v, @4)<=0) {
		/* shortcut: if BAT is empty or last (and hence all) tail
		 * value is <= v, we're done. */
		return cur;
	}
	while (lo < hi) {
		size_t mid = (lo+hi)>>1;
		cur = BUNptr(b, mid);
		cmp = @3_CMP(BUNt@1(b,cur),v,@4);
		if (cmp < 0) {
			lo = ++mid;
			cur += bunsize;
		} else if (cmp > 0) {
			hi = mid;
		} else {
			break;
		}
	}
	if (cmp == 0 && b->tkey == 0) {  /* shift over multiple equals */
		while((cur+=bunsize) < end) {
			if (!@3_EQ(BUNt@1(b,cur),v,@4))
				break;
		}
	} else if (cmp == 0) {
		cur += bunsize;
	}
	return cur;
}

BUN
SORTfnd_@2(BAT *m, ptr v)
{
	BAT *b = BATmirror(m);
	size_t lo = BUNindex(b,BUNfirst(b)), hi = BUNindex(b,BUNlast(b));
	int cmp = 1, bunsize = BUNsize(b);
	BUN cur = NULL;

	while (lo < hi) {
		size_t mid = (lo+hi)>>1;
		cur = BUNptr(b, mid);
		cmp = @3_CMP(BUNt@1(b,cur),v,@4);
		if (cmp < 0) {
			lo = ++mid;
			cur += bunsize;
		} else if (cmp > 0) {
			hi = mid;
		} else {
			break;
		}
	}
	return cmp ? NULL : cur;
}

@= SORTfnd_switch
BUN
SORTfnd@2(BAT *b, ptr v)
{
	if (b && b->@1sorted&1) {
		switch(ATOMstorage(b->@1type)) {
#ifndef NOEXPAND_CHR
		case TYPE_chr:
			return SORTfnd@2_chr(b,v);
#endif
#ifndef NOEXPAND_BTE
		case TYPE_bte:
			return SORTfnd@2_bte(b,v);
#endif
#ifndef NOEXPAND_SHT
		case TYPE_sht:
			return SORTfnd@2_sht(b,v);
#endif
#ifndef NOEXPAND_INT
		case TYPE_int:
			return SORTfnd@2_int(b,v);
#endif
#ifndef NOEXPAND_FLT
		case TYPE_flt:
			return SORTfnd@2_flt(b,v);
#endif
#ifndef NOEXPAND_DBL
		case TYPE_dbl:
			return SORTfnd@2_dbl(b,v);
#endif
#ifndef NOEXPAND_LNG
		case TYPE_lng:
			return SORTfnd@2_lng(b,v);
#endif
		default:
			if (b->@1varsized) {
				return SORTfnd@2_var(b,v);
			} else {
				return SORTfnd@2_loc(b,v);
			}
		}
	}
	return NULL;
}
@c
@:SORTfnd(loc,chr,simple,chr)@
@:SORTfnd(loc,bte,simple,bte)@
@:SORTfnd(loc,sht,simple,sht)@
@:SORTfnd(loc,int,simple,int)@
@:SORTfnd(loc,lng,simple,lng)@
@:SORTfnd(loc,flt,simple,flt)@
@:SORTfnd(loc,dbl,simple,dbl)@
@:SORTfnd(loc,loc,atom,b->ttype)@
@:SORTfnd(var,var,atom,b->ttype)@

@:SORTfnd_switch(h,)@
@:SORTfnd_switch(t,last)@
@:SORTfnd_switch(t,first)@

@c

@}