www.pudn.com > 传奇3源代码.rar > db.c

// $Id: db.c,v 1.6 2003/06/29 05:49:37 lemit Exp $ 
#define MALLOC_DBN 
#include  
#include  
#include  
#include "db.h" 
 
#ifdef MEMWATCH 
#include "memwatch.h" 
#endif 
 
#define ROOT_SIZE 4096 
static struct dbn *dbn_root[512], *dbn_free; 
static int dbn_root_rest=0,dbn_root_num=0; 
 
static void * malloc_dbn(void) 
{ 
	struct dbn* ret; 
 
	if(dbn_free==NULL){ 
		if(dbn_root_rest<=0){ 
			dbn_root[dbn_root_num]=calloc(sizeof(struct dbn)*ROOT_SIZE, 1); 
			if(dbn_root[dbn_root_num]==NULL){ 
				printf("out of memory : malloc_dbn\n"); 
				exit(1); 
			} 
			dbn_root_rest=ROOT_SIZE; 
			dbn_root_num++; 
		} 
		return &(dbn_root[dbn_root_num-1][--dbn_root_rest]); 
	} 
	ret=dbn_free; 
	dbn_free = dbn_free->parent; 
	return ret; 
} 
 
static void free_dbn(struct dbn* add_dbn) 
{ 
	add_dbn->parent = dbn_free; 
	dbn_free = add_dbn; 
} 
 
static int strdb_cmp(struct dbt* table,void* a,void* b) 
{ 
	if(table->maxlen) 
		return strncmp(a,b,table->maxlen); 
	return strcmp(a,b); 
} 
 
static unsigned int strdb_hash(struct dbt* table,void* a) 
{ 
	int i; 
	unsigned int h; 
	unsigned char *p=a; 
 
	i=table->maxlen; 
	if(i==0) i=0x7fffffff; 
	for(h=0;*p && --i>=0;){ 
		h=(h*33 + *p++) ^ (h>>24); 
	} 
	return h; 
} 
 
struct dbt* strdb_init(int maxlen) 
{ 
	int i; 
	struct dbt* table; 
 
	table = calloc(sizeof(*table), 1); 
	if (table == NULL) { 
		printf("out of memory : strdb_init\n"); 
		exit(1); 
	} 
	table->cmp=strdb_cmp; 
	table->hash=strdb_hash; 
	table->maxlen=maxlen; 
	for(i=0;iht[i]=NULL; 
	return table; 
} 
 
static int numdb_cmp(struct dbt* table,void* a,void* b) 
{ 
	int ia,ib; 
 
	ia=(int)a; 
	ib=(int)b; 
 
	if((ia^ib) & 0x80000000) 
		return ia<0 ? -1 : 1; 
 
	return ia-ib; 
} 
 
static unsigned int numdb_hash(struct dbt* table,void* a) 
{ 
	return (unsigned int)a; 
} 
 
struct dbt* numdb_init(void) 
{ 
	int i; 
	struct dbt* table; 
 
	table = calloc(sizeof *table, 1); 
	if (table == NULL) { 
		printf("out of memory : numdb_init\n"); 
		exit(1); 
	} 
	table->cmp=numdb_cmp; 
	table->hash=numdb_hash; 
	table->maxlen=sizeof(int); 
	for(i=0;iht[i]=NULL; 
	return table; 
} 
 
void* db_search(struct dbt *table,void* key) 
{ 
	struct dbn *p; 
 
	for(p=table->ht[table->hash(table,key) % HASH_SIZE];p;){ 
		int c=table->cmp(table,key,p->key); 
		if(c==0) 
			return p->data; 
		if(c<0) 
			p=p->left; 
		else 
			p=p->right; 
	} 
	return NULL; 
} 
 
static void db_rotate_left(struct dbn *p,struct dbn **root) 
{ 
	struct dbn * y = p->right; 
	p->right = y->left; 
	if (y->left !=0) 
		y->left->parent = p; 
	y->parent = p->parent; 
 
	if (p == *root) 
		*root = y; 
	else if (p == p->parent->left) 
		p->parent->left = y; 
	else 
		p->parent->right = y; 
	y->left = p; 
	p->parent = y; 
} 
 
static void db_rotate_right(struct dbn *p,struct dbn **root) 
{ 
	struct dbn * y = p->left; 
	p->left = y->right; 
	if (y->right != 0) 
		y->right->parent = p; 
	y->parent = p->parent; 
 
	if (p == *root) 
		*root = y; 
	else if (p == p->parent->right) 
		p->parent->right = y; 
	else 
		p->parent->left = y; 
	y->right = p; 
	p->parent = y; 
} 
 
static void db_rebalance(struct dbn *p,struct dbn **root) 
{ 
	p->color = RED; 
	while(p!=*root && p->parent->color==RED){ // root偼昁偢崟偱恊偼愒偄偺偱恊偺恊偼昁偢懚嵼偡傞 
		if (p->parent == p->parent->parent->left) { 
			struct dbn *y = p->parent->parent->right; 
			if (y && y->color == RED) { 
				p->parent->color = BLACK; 
				y->color = BLACK; 
				p->parent->parent->color = RED; 
				p = p->parent->parent; 
			} else { 
				if (p == p->parent->right) { 
					p = p->parent; 
					db_rotate_left(p, root); 
				} 
				p->parent->color = BLACK; 
				p->parent->parent->color = RED; 
				db_rotate_right(p->parent->parent, root); 
			} 
		} else { 
			struct dbn* y = p->parent->parent->left; 
			if (y && y->color == RED) { 
				p->parent->color = BLACK; 
				y->color = BLACK; 
				p->parent->parent->color = RED; 
				p = p->parent->parent; 
			} else { 
				if (p == p->parent->left) { 
					p = p->parent; 
					db_rotate_right(p, root); 
				} 
				p->parent->color = BLACK; 
				p->parent->parent->color = RED; 
				db_rotate_left(p->parent->parent, root); 
			} 
		} 
	} 
	(*root)->color=BLACK; 
} 
 
static void db_rebalance_erase(struct dbn *z,struct dbn **root) 
{ 
	struct dbn *y = z, *x = NULL, *x_parent = NULL; 
 
	if (y->left == NULL) 
		x = y->right; 
	else if (y->right == NULL) 
		x = y->left; 
	else { 
		y = y->right; 
		while (y->left != NULL) 
			y = y->left; 
		x = y->right; 
	} 
	if (y != z) { // 嵍塃偑椉曽杽傑偭偰偄偨帪 y傪z偺埵抲偵帩偭偰偒偰z傪晜偐偣傞 
		z->left->parent = y; 
		y->left = z->left; 
		if (y != z->right) { 
			x_parent = y->parent; 
			if (x) x->parent = y->parent; 
			y->parent->left = x; 
			y->right = z->right; 
			z->right->parent = y; 
		} else 
			x_parent = y; 
		if (*root == z) 
			*root = y; 
		else if (z->parent->left == z) 
			z->parent->left = y; 
		else 
			z->parent->right = y; 
		y->parent = z->parent; 
		{ int tmp=y->color; y->color=z->color; z->color=tmp; } 
		y = z; 
	} else { // 偳偪傜偐嬻偄偰偄偨応崌 x傪z偺埵抲偵帩偭偰偒偰z傪晜偐偣傞 
		x_parent = y->parent; 
		if (x) x->parent = y->parent; 
		if (*root == z) 
			*root = x; 
		else if (z->parent->left == z) 
			z->parent->left = x; 
		else 
			z->parent->right = x; 
	} 
	// 偙偙傑偱怓偺堏摦偺彍偄偰捠忢偺2暘栘偲摨偠 
	if (y->color != RED) { // 愒偑徚偊傞暘偵偼塭嬁柍偟 
		while (x != *root && (x == NULL || x->color == BLACK)) 
			if (x == x_parent->left) { 
				struct dbn* w = x_parent->right; 
				if (w->color == RED) { 
					w->color = BLACK; 
					x_parent->color = RED; 
					db_rotate_left(x_parent, root); 
					w = x_parent->right; 
				} 
				if ((w->left == NULL || 
					 w->left->color == BLACK) && 
					(w->right == NULL || 
					 w->right->color == BLACK)) { 
					w->color = RED; 
					x = x_parent; 
					x_parent = x_parent->parent; 
				} else { 
					if (w->right == NULL || 
						w->right->color == BLACK) { 
						if (w->left) w->left->color = BLACK; 
						w->color = RED; 
						db_rotate_right(w, root); 
						w = x_parent->right; 
					} 
					w->color = x_parent->color; 
					x_parent->color = BLACK; 
					if (w->right) w->right->color = BLACK; 
					db_rotate_left(x_parent, root); 
					break; 
				} 
			} else {                  // same as above, with right <-> left. 
				struct dbn* w = x_parent->left; 
				if (w->color == RED) { 
					w->color = BLACK; 
					x_parent->color = RED; 
					db_rotate_right(x_parent, root); 
					w = x_parent->left; 
				} 
				if ((w->right == NULL || 
					 w->right->color == BLACK) && 
					(w->left == NULL || 
					 w->left->color == BLACK)) { 
					w->color = RED; 
					x = x_parent; 
					x_parent = x_parent->parent; 
				} else { 
					if (w->left == NULL || 
						w->left->color == BLACK) { 
						if (w->right) w->right->color = BLACK; 
						w->color = RED; 
						db_rotate_left(w, root); 
						w = x_parent->left; 
					} 
					w->color = x_parent->color; 
					x_parent->color = BLACK; 
					if (w->left) w->left->color = BLACK; 
					db_rotate_right(x_parent, root); 
					break; 
				} 
			} 
		if (x) x->color = BLACK; 
	} 
} 
 
struct dbn* db_insert(struct dbt *table,void* key,void* data) 
{ 
	struct dbn *p,*priv; 
	int c,hash; 
 
	hash = table->hash(table,key) % HASH_SIZE; 
	for(c=0,priv=NULL ,p = table->ht[hash];p;){ 
		c=table->cmp(table,key,p->key); 
		if(c==0){ // replace 
			p->data=data; 
			return p; 
		} 
		priv=p; 
		if(c<0){ 
			p=p->left; 
		} else { 
			p=p->right; 
		} 
	} 
#ifdef MALLOC_DBN 
	p=malloc_dbn(); 
#else 
	p=calloc(sizeof(*p), 1); 
#endif 
	if(p==NULL){ 
		printf("out of memory : db_insert\n"); 
		return NULL; 
	} 
	p->parent= NULL; 
	p->left  = NULL; 
	p->right = NULL; 
	p->key   = key; 
	p->data  = data; 
	p->color = RED; 
	if(c==0){ // hash entry is empty 
		table->ht[hash] = p; 
		p->color = BLACK; 
	} else { 
		if(c<0){ // left node 
			priv->left = p; 
			p->parent=priv; 
		} else { // right node 
			priv->right = p; 
			p->parent=priv; 
		} 
		if(priv->color==RED){ // must rebalance 
			db_rebalance(p,&table->ht[hash]); 
		} 
	} 
	return p; 
} 
 
void* db_erase(struct dbt *table,void* key) 
{ 
	void *data; 
	struct dbn *p; 
	int c,hash; 
 
	hash = table->hash(table,key) % HASH_SIZE; 
	for(c=0,p = table->ht[hash];p;){ 
		c=table->cmp(table,key,p->key); 
		if(c==0) 
			break; 
		if(c<0) 
			p=p->left; 
		else 
			p=p->right; 
	} 
	if(!p) 
		return NULL; 
	data=p->data; 
	db_rebalance_erase(p,&table->ht[hash]); 
#ifdef MALLOC_DBN 
	free_dbn(p); 
#else 
	free(p); 
#endif 
	return data; 
} 
 
void db_foreach(struct dbt *table,int (*func)(void*,void*,va_list),...) 
{ 
	int i,sp; 
	// red-black tree側偺偱64屄stack偑偁傟偽2^32屄僲乕僪傑偱戝忎晇 
	struct dbn *p,*pn,*stack[64]; 
	va_list ap; 
 
	va_start(ap,func); 
	for(i=0;iht[i])==NULL) 
			continue; 
		sp=0; 
		while(1){ 
			func(p->key,p->data,ap); 
			if((pn=p->left)!=NULL){ 
				if(p->right){ 
					stack[sp++]=p->right; 
				} 
				p=pn; 
			} else { 
				if(p->right){ 
					p=p->right; 
				} else { 
					if(sp==0) 
						break; 
					p=stack[--sp]; 
				} 
			} 
		} 
	} 
	va_end(ap); 
} 
 
void db_final(struct dbt *table,int (*func)(void*,void*,va_list),...) 
{ 
	int i,sp; 
	struct dbn *p,*pn,*stack[64]; 
	va_list ap; 
 
	va_start(ap,func); 
	for(i=0;iht[i])==NULL) 
			continue; 
		sp=0; 
		while(1){ 
			if(func) 
				func(p->key,p->data,ap); 
			if((pn=p->left)!=NULL){ 
				if(p->right){ 
					stack[sp++]=p->right; 
				} 
			} else { 
				if(p->right){ 
					pn=p->right; 
				} else { 
					if(sp==0) 
						break; 
					pn=stack[--sp]; 
				} 
			} 
			free_dbn(p); 
			p=pn; 
		} 
	} 
	free(table); 
	va_end(ap); 
}