diff options
Diffstat (limited to 'src/common/db.c')
| -rw-r--r-- | src/common/db.c | 424 |
1 files changed, 192 insertions, 232 deletions
diff --git a/src/common/db.c b/src/common/db.c index 07b08c8..cee17df 100644 --- a/src/common/db.c +++ b/src/common/db.c @@ -1,125 +1,93 @@ -// $Id: db.c,v 1.2 2004/09/23 14:43:06 MouseJstr Exp $ -// #define MALLOC_DBN +#include "db.h" + #include <stdio.h> #include <stdlib.h> #include <string.h> -#include "db.h" -#include "utils.h" -#ifdef MEMWATCH -#include "memwatch.h" -#endif +#include "utils.h" #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 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; -} - -static void free_dbn (struct dbn *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, const char *a, const char* 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 hash_t strdb_hash (struct dbt *table, const char *a) { - int i; - unsigned int h; - unsigned char *p = a; - - i = table->maxlen; + size_t i = table->maxlen; if (i == 0) - i = 0x7fffffff; - for (h = 0; *p && --i >= 0;) + i = (size_t)-1; + hash_t h = 0; + const unsigned char *p = (const unsigned char*)a; + while (*p && i--) { h = (h * 33 + *p++) ^ (h >> 24); } return h; } -struct dbt *strdb_init (int maxlen) +struct dbt *strdb_init (size_t maxlen) { - int i; struct dbt *table; - CREATE (table, struct dbt, 1); - - table->cmp = strdb_cmp; - table->hash = strdb_hash; + table->type = DB_STRING; 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 (numdb_key_t a, numdb_key_t b) { - int ia, ib; - - ia = (int) a; - ib = (int) b; - - if ((ia ^ ib) & 0x80000000) - return ia < 0 ? -1 : 1; - - return ia - ib; + if (a == b) + return 0; + if (a < b) + return -1; + return 1; } -static unsigned int numdb_hash (struct dbt *table, void *a) +static hash_t numdb_hash (numdb_key_t a) { - return (unsigned int) a; + return (hash_t) a; } struct dbt *numdb_init (void) { - int i; struct dbt *table; - 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; + table->type = DB_NUMBER; return table; } -void *db_search (struct dbt *table, void *key) +static int table_cmp (struct dbt *table, db_key_t a, db_key_t b) +{ + switch(table->type) + { + case DB_NUMBER: return numdb_cmp (a.i, b.i); + case DB_STRING: return strdb_cmp (table, a.s, b.s); + } + abort(); +} + +static hash_t table_hash (struct dbt *table, db_key_t key) +{ + switch(table->type) + { + case DB_NUMBER: return numdb_hash (key.i); + case DB_STRING: return strdb_hash (table, key.s); + } + abort(); +} + +/// Search for a node with the given key +db_val_t db_search (struct dbt *table, db_key_t key) { - struct dbn *p; + struct dbn *p = table->ht[table_hash (table, key) % HASH_SIZE]; - for (p = table->ht[table->hash (table, key) % HASH_SIZE]; p;) + while (p) { - int c = table->cmp (table, key, p->key); + int c = table_cmp (table, key, p->key); if (c == 0) return p->data; if (c < 0) @@ -130,52 +98,12 @@ void *db_search (struct dbt *table, void *key) return NULL; } -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; -} - +// Tree maintainance methods static void db_rotate_left (struct dbn *p, struct dbn **root) { struct dbn *y = p->right; p->right = y->left; - if (y->left != 0) + if (y->left) y->left->parent = p; y->parent = p->parent; @@ -193,7 +121,7 @@ static void db_rotate_right (struct dbn *p, struct dbn **root) { struct dbn *y = p->left; p->left = y->right; - if (y->right != 0) + if (y->right) y->right->parent = p; y->parent = p->parent; @@ -211,7 +139,7 @@ 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; @@ -260,23 +188,26 @@ static void db_rebalance (struct dbn *p, struct dbn **root) (*root)->color = BLACK; } +// param z = node to remove static void db_rebalance_erase (struct dbn *z, struct dbn **root) { - struct dbn *y = z, *x = NULL, *x_parent = NULL; + struct dbn *y = z; + struct dbn *x = NULL; - if (y->left == NULL) + if (!y->left) x = y->right; - else if (y->right == NULL) + else if (!y->right) x = y->left; else { y = y->right; - while (y->left != NULL) + while (y->left) y = y->left; x = y->right; } + struct dbn *x_parent = NULL; if (y != z) - { // 左右が両方埋まっていた時 yをzの位置に持ってきてzを浮かせる + { z->left->parent = y; y->left = z->left; if (y != z->right) @@ -305,7 +236,7 @@ static void db_rebalance_erase (struct dbn *z, struct dbn **root) y = z; } else - { // どちらか空いていた場合 xをzの位置に持ってきてzを浮かせる + { x_parent = y->parent; if (x) x->parent = y->parent; @@ -316,10 +247,9 @@ static void db_rebalance_erase (struct dbn *z, struct dbn **root) else z->parent->right = x; } - // ここまで色の移動の除いて通常の2分木と同じ if (y->color != RED) - { // 赤が消える分には影響無し - while (x != *root && (x == NULL || x->color == BLACK)) + { + while (x != *root && (!x || x->color == BLACK)) if (x == x_parent->left) { struct dbn *w = x_parent->right; @@ -330,17 +260,16 @@ static void db_rebalance_erase (struct dbn *z, struct dbn **root) 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)) + if ((!w->left || w->left->color == BLACK) && + (!w->right || w->right->color == BLACK)) { w->color = RED; x = x_parent; - x_parent = x_parent->parent; + x_parent = x->parent; } else { - if (w->right == NULL || w->right->color == BLACK) + if (!w->right|| w->right->color == BLACK) { if (w->left) w->left->color = BLACK; @@ -357,7 +286,8 @@ static void db_rebalance_erase (struct dbn *z, struct dbn **root) } } else - { // same as above, with right <-> left. + { + // same as above, with right <-> left. struct dbn *w = x_parent->left; if (w->color == RED) { @@ -366,9 +296,8 @@ static void db_rebalance_erase (struct dbn *z, struct dbn **root) 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)) + if ((!w->right || w->right->color == BLACK) && + (!w->left || w->left->color == BLACK)) { w->color = RED; x = x_parent; @@ -376,7 +305,7 @@ static void db_rebalance_erase (struct dbn *z, struct dbn **root) } else { - if (w->left == NULL || w->left->color == BLACK) + if (!w->left || w->left->color == BLACK) { if (w->right) w->right->color = BLACK; @@ -397,46 +326,33 @@ static void db_rebalance_erase (struct dbn *z, struct dbn **root) } } -struct dbn *db_insert (struct dbt *table, void *key, void *data) +struct dbn *db_insert (struct dbt *table, db_key_t key, db_val_t 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;) + hash_t hash = table_hash (table, key) % HASH_SIZE; + int c = 0; + struct dbn *prev = NULL; + struct dbn *p = table->ht[hash]; + while (p) { - c = table->cmp (table, key, p->key); + c = table_cmp (table, key, p->key); if (c == 0) - { // replace + { + // key found in table, replace + // Tell the user of the table to free the key and value if (table->release) - table->release (p, 3); + table->release (p->key, p->data); p->data = data; p->key = key; return p; } - priv = p; + // prev is always p->parent? + prev = p; if (c < 0) - { p = p->left; - } else - { p = p->right; - } } -#ifdef MALLOC_DBN - p = malloc_dbn (); -#else 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; @@ -444,37 +360,28 @@ struct dbn *db_insert (struct dbt *table, void *key, void *data) { // hash entry is empty table->ht[hash] = p; p->color = BLACK; + return p; } + p->parent = prev; + if (c < 0) + prev->left = p; else + prev->right = p; + if (prev->color == RED) { - 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]); - } + // must rebalance + db_rebalance (p, &table->ht[hash]); } return p; } -void *db_erase (struct dbt *table, void *key) +db_val_t db_erase (struct dbt *table, db_key_t key) { - void *data; - struct dbn *p; - int c, hash; - - hash = table->hash (table, key) % HASH_SIZE; - for (c = 0, p = table->ht[hash]; p;) + hash_t hash = table_hash (table, key) % HASH_SIZE; + struct dbn *p = table->ht[hash]; + while (p) { - c = table->cmp (table, key, p->key); + int c = table_cmp (table, key, p->key); if (c == 0) break; if (c < 0) @@ -484,103 +391,156 @@ void *db_erase (struct dbt *table, void *key) } if (!p) return NULL; - data = p->data; + db_val_t data = p->data; db_rebalance_erase (p, &table->ht[hash]); -#ifdef MALLOC_DBN - free_dbn (p); -#else free (p); -#endif return data; } +#ifdef SMART_WALK_TREE +static inline void db_walk_tree (bool dealloc, struct dbn* p, db_func_t func, va_list ap) +{ + if (!p) + return; + if (!dealloc && !func) + { + fprintf(stderr, "DEBUG: Must walk tree to either free or invoke a function.\n"); + abort(); + } + if (p->parent) + { + fprintf(stderr, "DEBUG: Root nodes must not have parents\n"); + abort(); + } + while (true) + { + // apply_func loop + if (func) + func (p->key, p->data, ap); + if (p->left) + { + // continue descending + p = p->left; + continue; //goto apply_func; + } + if (p->right) + { + // descending the other side + p = p->right; + continue; //goto apply_func; + } + while (true) + { + // backtrack loop + if (!p->parent) + { + if (dealloc) + free (p); + // if we have already done both children, there is no more to do + return; + } + if (p->parent->left == p && p->parent->right) + { + // finished the left tree, now walk the right tree + p = p->parent->right; + if (dealloc) + free (p->parent->left); + break; //goto apply_func; + } + // p->parent->right == p + // or p->parent->left == p but p->parent->right == NULL + // keep backtracking + p = p->parent; + if (dealloc) + free (p->right?:p->left); + } //backtrack loop + } // apply_func loop +} +#endif // SMART_WALK_TREE -void db_foreach (struct dbt *table, int (*func) (void *, void *, va_list), - ...) +void db_foreach (struct dbt *table, db_func_t func, ...) { - 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++) + + for (int i = 0; i < HASH_SIZE; i++) { - if ((p = table->ht[i]) == NULL) +#ifdef SMART_WALK_TREE + db_walk_tree (false, table->ht[i], func, ap); +#else + struct dbn *p = table->ht[i]; + if (!p) continue; - sp = 0; + struct dbn *stack[64]; + int sp = 0; while (1) { func (p->key, p->data, ap); - if ((pn = p->left) != NULL) + struct dbn *pn = p->left; + if (pn) { if (p->right) - { stack[sp++] = p->right; - } p = pn; } - else + else // pn == NULL, time to do the right branch { if (p->right) - { p = p->right; - } else { if (sp == 0) break; p = stack[--sp]; } - } - } - } + } // if pn else if !pn + } // while true +#endif // else ! SMART_WALK_TREE + } // for i va_end (ap); } -void db_final (struct dbt *table, int (*func) (void *, void *, va_list), ...) +// This function is suspiciously similar to the previous +void db_final (struct dbt *table, db_func_t func, ...) { - int i, sp; - struct dbn *p, *pn, *stack[64]; va_list ap; - va_start (ap, func); - for (i = 0; i < HASH_SIZE; i++) + + for (int i = 0; i < HASH_SIZE; i++) { - if ((p = table->ht[i]) == NULL) +#ifdef SMART_WALK_TREE + db_walk_tree (true, table->ht[i], func, ap); +#else + struct dbn *p = table->ht[i]; + if (!p) continue; - sp = 0; + struct dbn *stack[64]; + int sp = 0; while (1) { if (func) func (p->key, p->data, ap); - if ((pn = p->left) != NULL) + struct dbn *pn = p->left; + if (pn) { if (p->right) - { stack[sp++] = p->right; - } } - else + else // pn == NULL, check the right { if (p->right) - { pn = p->right; - } else { if (sp == 0) break; pn = stack[--sp]; } - } -#ifdef MALLOC_DBN - free_dbn (p); -#else + } // if pn else if !pn free (p); -#endif p = pn; - } - } + } // while true +#endif // else ! SMART_WALK_TREE + } // for i free (table); va_end (ap); } |