gdk_search.h

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

#ifndef _GDK_SEARCH_H_
#define _GDK_SEARCH_H_
#include "gdk.h"




gdk_export Hash *HASHnew(Heap *hp, int tpe, size_t size, hash_t mask);
gdk_export hash_t HASHmask(size_t cnt);
gdk_export BAT *HASHprint(BAT *b);
gdk_export void HASHremove(BAT *b);
gdk_export void HASHdestroy(BAT *b);
gdk_export int HASHgonebad(BAT *b, ptr v);
gdk_export hash_t HASHprobe(Hash *h, ptr v);
gdk_export hash_t HASHlist(Hash *h, size_t i);

#define mix_sht(X)            (((X)>>7)^(X))
#define mix_int(X)            (((X)>>7)^((X)>>13)^((X)>>21)^(X))
#define hash_loc(H,V)         hash_any(H,V)
#define hash_var(H,V)         hash_any(H,V)
#define hash_any(H,V)         (ATOMhash((H)->type, (V)) & (H)->mask)
#define hash_bte(H,V)         ((hash_t) (*(unsigned char*) (V)) & (H)->mask)
#define hash_chr(H,V)         hash_bte(H,V)
#define hash_sht(H,V)         ((hash_t) mix_sht(*((unsigned short*) (V))) & (H)->mask)
#define hash_int(H,V)         ((hash_t) mix_int(*((unsigned int*) (V))) & (H)->mask)
/* XXX return size_t-sized value for 8-byte oid? */
#define hash_lng(H,V)         ((hash_t) mix_int((unsigned int) (*(lng *)(V) ^ (*(lng *)(V) >> 32))) & (H)->mask)




#define HASHfnd_str(x,y,z)	{					\
	hash_t _i;							\
	(x) = NULL;							\
	if ((y)->hhash || BAThash((y), 0) || GDKfatal("HASHfnd_str: hash build failed on %s.\n", BATgetId((y)))) \
		HASHloop_str((y), (y)->hhash, _i, (z)) {		\
			(x) = BUNptr((y),_i);				\
			break;						\
		}							\
}
#define HASHfnd(x,y,z)	{						\
	size_t _i;							\
	x=NULL;								\
	if ((y)->hhash || BAThash((y), 0) || GDKfatal("HASHfnd: hash build failed on %s.\n", BATgetId((y)))) \
		HASHloop((y), (y)->hhash, _i, (z)) {			\
			(x) = BUNptr((y),_i);				\
			break;						\
		}							\
}

#define HASHfnd_chr(x,y,z)	{					\
	hash_t _i;							\
	BUN _v;								\
	(x) = NULL;							\
	if ((y)->hhash || BAThash((y), 0) || GDKfatal("HASHfnd_chr: hash build failed on %s.\n", BATgetId((y)))) \
		HASHloop_chr((y), (y)->hhash, _i, (z), _v) {		\
			(x) = _v;					\
			break;						\
		}							\
}




#define HASHfnd_bte(x,y,z)	{					\
	hash_t _i;							\
	BUN _v;								\
	(x) = NULL;							\
	if ((y)->hhash || BAThash((y), 0) || GDKfatal("HASHfnd_bte: hash build failed on %s.\n", BATgetId((y)))) \
		HASHloop_bte((y), (y)->hhash, _i, (z), _v) {		\
			(x) = _v;					\
			break;						\
		}							\
}




#define HASHfnd_sht(x,y,z)	{					\
	hash_t _i;							\
	BUN _v;								\
	(x) = NULL;							\
	if ((y)->hhash || BAThash((y), 0) || GDKfatal("HASHfnd_sht: hash build failed on %s.\n", BATgetId((y)))) \
		HASHloop_sht((y), (y)->hhash, _i, (z), _v) {		\
			(x) = _v;					\
			break;						\
		}							\
}




#define HASHfnd_int(x,y,z)	{					\
	hash_t _i;							\
	BUN _v;								\
	(x) = NULL;							\
	if ((y)->hhash || BAThash((y), 0) || GDKfatal("HASHfnd_int: hash build failed on %s.\n", BATgetId((y)))) \
		HASHloop_int((y), (y)->hhash, _i, (z), _v) {		\
			(x) = _v;					\
			break;						\
		}							\
}




#define HASHfnd_lng(x,y,z)	{					\
	hash_t _i;							\
	BUN _v;								\
	(x) = NULL;							\
	if ((y)->hhash || BAThash((y), 0) || GDKfatal("HASHfnd_lng: hash build failed on %s.\n", BATgetId((y)))) \
		HASHloop_lng((y), (y)->hhash, _i, (z), _v) {		\
			(x) = _v;					\
			break;						\
		}							\
}




#if SIZEOF_VOID_P == SIZEOF_INT
#define HASHfnd_ptr(x,y,z)	HASHfnd_int(x,y,z)
#else /* SIZEOF_VOID_P == SIZEOF_LNG */
#define HASHfnd_ptr(x,y,z)	HASHfnd_lng(x,y,z)
#endif
#define HASHfnd_bit(x,y,z)	HASHfnd_chr(x,y,z)
#if SIZEOF_OID == SIZEOF_INT	/* OIDDEPEND */
#define HASHfnd_oid(x,y,z)	HASHfnd_int(x,y,z)
#else
#define HASHfnd_oid(x,y,z)	HASHfnd_lng(x,y,z)
#endif
#define HASHfnd_flt(x,y,z)	HASHfnd_int(x,y,z)
#define HASHfnd_dbl(x,y,z)	HASHfnd_lng(x,y,z)
#define HASHfnd_any(x,y,z)	HASHfnd(x,y,z)


#define HASHins_str(h,i,v) {			\
	hash_t _c;				\
	GDK_STRHASH(v,_c);			\
	_c &= (h)->mask;			\
	h->link[i] = h->hash[_c];		\
	h->hash[_c] = i;			\
}

#define HASHins_any(h,i,v) {			\
	hash_t _c = HASHprobe(h, v);		\
	h->link[i] = h->hash[_c];		\
	h->hash[_c] = i;			\
}

/* HASHins now receives a BAT* param and has become adaptive; killing wrongly configured hash tables */
/* use HASHins_any or HASHins_<tpe> instead if you know what you're doing or want to keep the hash whatever */
#define HASHins(b,i,v) \
	do if (((i) & 1023) == 1023 && HASHgonebad((b),(v))) { HASHremove(b); } else  { HASHins_any((b)->hhash,(i),(v)); } while (0)

#if SIZEOF_VOID_P == SIZEOF_INT
#define HASHins_ptr(h,i,v)	HASHins_int(h,i,v)
#else /* SIZEOF_VOID_P == SIZEOF_LNG */
#define HASHins_ptr(h,i,v)	HASHins_lng(h,i,v)
#endif
#define HASHins_bit(h,i,v)	HASHins_chr(h,i,v)
#if SIZEOF_OID == SIZEOF_INT	/* OIDDEPEND */
#define HASHins_oid(h,i,v)	HASHins_int(h,i,v)
#else
#define HASHins_oid(h,i,v)	HASHins_lng(h,i,v)
#endif
#define HASHins_flt(h,i,v)	HASHins_int(h,i,v)
#define HASHins_dbl(h,i,v)	HASHins_lng(h,i,v)
#define HASHinsvar(h,i,v)	HASHins_any(h,i,v)
#define HASHinsloc(h,i,v)	HASHins_any(h,i,v)


#define HASHins_chr(h, i, v) {			\
	hash_t _c = hash_chr(h,v);		\
	h->link[i] = h->hash[_c];		\
	h->hash[_c] = i;			\
}




#define HASHins_bte(h, i, v) {			\
	hash_t _c = hash_bte(h,v);		\
	h->link[i] = h->hash[_c];		\
	h->hash[_c] = i;			\
}




#define HASHins_sht(h, i, v) {			\
	hash_t _c = hash_sht(h,v);		\
	h->link[i] = h->hash[_c];		\
	h->hash[_c] = i;			\
}




#define HASHins_int(h, i, v) {			\
	hash_t _c = hash_int(h,v);		\
	h->link[i] = h->hash[_c];		\
	h->hash[_c] = i;			\
}




#define HASHins_lng(h, i, v) {			\
	hash_t _c = hash_lng(h,v);		\
	h->link[i] = h->hash[_c];		\
	h->hash[_c] = i;			\
}




#define HASHdel(h, i, v, next) {					\
	if (next && h->link[i+1] == i) {				\
		h->link[i+1] = h->link[i];				\
	} else {							\
		size_t _c = HASHprobe(h, v);				\
		if (h->hash[_c] == i) {					\
			h->hash[_c] = h->link[i];			\
		} else {						\
			for(_c = h->hash[_c]; _c != HASH_MAX; 		\
					_c = h->link[_c]){ 		\
				if (h->link[_c] == i) {			\
					h->link[_c] = h->link[i];	\
					break;				\
				}					\
			}						\
		}							\
	} h->link[i] = HASH_MAX;					\
}

#define HASHmove(h, i, j, v, next) {					\
	if (next && h->link[i+1] == i) {				\
		h->link[i+1] = j;					\
	} else {							\
		size_t _c = HASHprobe(h, v);				\
		if (h->hash[_c] == i) {					\
			h->hash[_c] = j;				\
		} else {						\
			for(_c = h->hash[_c]; _c != HASH_MAX; 		\
					_c = h->link[_c]){ 		\
				if (h->link[_c] == i) {			\
					h->link[_c] = j;		\
					break;				\
				}					\
			}						\
		}							\
	} h->link[j] = h->link[i];					\
}




/* 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_ */