diff options
author | Chuck Miller <shadowmil@gmail.com> | 2009-12-25 05:00:31 -0500 |
---|---|---|
committer | Jared Adams <jaxad0127@gmail.com> | 2009-12-26 00:40:11 -0700 |
commit | 634aeeb9d58b01f9de6632a014a063ef0c4cf31e (patch) | |
tree | 70023dd2bcc12a3f96ec6f118d80e27411920531 /src/common/db.c | |
parent | 113fcc4f0a7a0921e94bc415515dd4b393a29d60 (diff) | |
download | tmwa-634aeeb9d58b01f9de6632a014a063ef0c4cf31e.tar.gz tmwa-634aeeb9d58b01f9de6632a014a063ef0c4cf31e.tar.bz2 tmwa-634aeeb9d58b01f9de6632a014a063ef0c4cf31e.tar.xz tmwa-634aeeb9d58b01f9de6632a014a063ef0c4cf31e.zip |
Used the "indent" C formatting program from GNU to do some clean ups
The command options used was:
-nbad -bap -sc -bl -blf -bli0 -cli4 -cbi0
-di5 -nbc -bls -ip2 -nut -ts4 -bap -i4 -sob -npsl
Diffstat (limited to 'src/common/db.c')
-rw-r--r-- | src/common/db.c | 914 |
1 files changed, 500 insertions, 414 deletions
diff --git a/src/common/db.c b/src/common/db.c index a2dc695..7a4fa70 100644 --- a/src/common/db.c +++ b/src/common/db.c @@ -13,488 +13,574 @@ #define ROOT_SIZE 4096 #ifdef MALLOC_DBN static struct dbn *dbn_root[512], *dbn_free; -static int dbn_root_rest=0,dbn_root_num=0; +static int dbn_root_rest = 0, dbn_root_num = 0; -static void * malloc_dbn(void) +static void *malloc_dbn (void) { - struct dbn* ret; - - if(dbn_free==NULL){ - if(dbn_root_rest<=0){ - CREATE(dbn_root[dbn_root_num], struct dbn, ROOT_SIZE); - - 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; + struct dbn *ret; + + if (dbn_free == NULL) + { + if (dbn_root_rest <= 0) + { + CREATE (dbn_root[dbn_root_num], struct dbn, ROOT_SIZE); + + 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) +static void free_dbn (struct dbn *add_dbn) { - add_dbn->parent = dbn_free; - dbn_free = add_dbn; + add_dbn->parent = dbn_free; + dbn_free = add_dbn; } #endif -static int strdb_cmp(struct dbt* table,void* a,void* b) +static int strdb_cmp (struct dbt *table, void *a, void *b) { - if(table->maxlen) - return strncmp(a,b,table->maxlen); - return strcmp(a,b); + if (table->maxlen) + return strncmp (a, b, table->maxlen); + return strcmp (a, b); } -static unsigned int strdb_hash(struct dbt* table,void* a) +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; + 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) +struct dbt *strdb_init (int maxlen) { - int i; - struct dbt* table; + int i; + struct dbt *table; - CREATE(table, struct dbt, 1); + CREATE (table, struct dbt, 1); - table->cmp=strdb_cmp; - table->hash=strdb_hash; - table->maxlen=maxlen; - for(i=0;i<HASH_SIZE;i++) - table->ht[i]=NULL; - return table; + table->cmp = strdb_cmp; + table->hash = strdb_hash; + table->maxlen = maxlen; + for (i = 0; i < HASH_SIZE; i++) + table->ht[i] = NULL; + return table; } -static int numdb_cmp(struct dbt* table,void* a,void* b) +static int numdb_cmp (struct dbt *table, void *a, void *b) { - int ia,ib; + int ia, ib; - ia=(int)a; - ib=(int)b; + ia = (int) a; + ib = (int) b; - if((ia^ib) & 0x80000000) - return ia<0 ? -1 : 1; + if ((ia ^ ib) & 0x80000000) + return ia < 0 ? -1 : 1; - return ia-ib; + return ia - ib; } -static unsigned int numdb_hash(struct dbt* table,void* a) +static unsigned int numdb_hash (struct dbt *table, void *a) { - return (unsigned int)a; + return (unsigned int) a; } -struct dbt* numdb_init(void) +struct dbt *numdb_init (void) { - int i; - struct dbt* table; + int i; + struct dbt *table; - CREATE(table, struct dbt, 1); + CREATE (table, struct dbt, 1); - table->cmp=numdb_cmp; - table->hash=numdb_hash; - table->maxlen=sizeof(int); - for(i=0;i<HASH_SIZE;i++) - table->ht[i]=NULL; - return table; + table->cmp = numdb_cmp; + table->hash = numdb_hash; + table->maxlen = sizeof (int); + for (i = 0; i < HASH_SIZE; i++) + table->ht[i] = NULL; + return table; } -void* db_search(struct dbt *table,void* key) +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; + 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; } -void * db_search2(struct dbt *table, const char *key) +void *db_search2 (struct dbt *table, const char *key) { - int i,sp; - struct dbn *p,*pn,*stack[64]; - int slen = strlen(key); - - for(i=0;i<HASH_SIZE;i++){ - if((p=table->ht[i])==NULL) - continue; - sp=0; - while(1){ - if (strncasecmp(key, p->key, slen) == 0) - return p->data; - 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]; - } - } - } - } - return 0; + int i, sp; + struct dbn *p, *pn, *stack[64]; + int slen = strlen (key); + + for (i = 0; i < HASH_SIZE; i++) + { + if ((p = table->ht[i]) == NULL) + continue; + sp = 0; + while (1) + { + if (strncasecmp (key, p->key, slen) == 0) + return p->data; + 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]; + } + } + } + } + return 0; } -static void db_rotate_left(struct dbn *p,struct dbn **root) +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; + 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) +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; + 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) +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; + 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) +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 *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 *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 - if (table->release) - table->release(p, 3); - p->data=data; - p->key=key; - return p; - } - priv=p; - if(c<0){ - p=p->left; - } else { - p=p->right; - } - } + 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 + if (table->release) + table->release (p, 3); + p->data = data; + p->key = key; + return p; + } + priv = p; + if (c < 0) + { + p = p->left; + } + else + { + p = p->right; + } + } #ifdef MALLOC_DBN - p=malloc_dbn(); + p = malloc_dbn (); #else - CREATE(p, struct dbn, 1); + CREATE (p, struct dbn, 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; + 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 *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]); + 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); + free_dbn (p); #else - free(p); + free (p); #endif - return data; + return data; } -void db_foreach(struct dbt *table,int (*func)(void*,void*,va_list),...) +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;i<HASH_SIZE;i++){ - if((p=table->ht[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); + 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; i < HASH_SIZE; i++) + { + if ((p = table->ht[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),...) +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;i<HASH_SIZE;i++){ - if((p=table->ht[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]; - } - } + int i, sp; + struct dbn *p, *pn, *stack[64]; + va_list ap; + + va_start (ap, func); + for (i = 0; i < HASH_SIZE; i++) + { + if ((p = table->ht[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]; + } + } #ifdef MALLOC_DBN - free_dbn(p); + free_dbn (p); #else - free(p); + free (p); #endif - p=pn; - } - } - free(table); - va_end(ap); + p = pn; + } + } + free (table); + va_end (ap); } |