summaryrefslogtreecommitdiff
path: root/src/common/db.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/common/db.cpp')
-rw-r--r--src/common/db.cpp545
1 files changed, 1 insertions, 544 deletions
diff --git a/src/common/db.cpp b/src/common/db.cpp
index 21a3597..cc58ad8 100644
--- a/src/common/db.cpp
+++ b/src/common/db.cpp
@@ -1,546 +1,3 @@
#include "db.hpp"
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-
-#include "utils.hpp"
-
-#define ROOT_SIZE 4096
-
-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 hash_t strdb_hash (struct dbt *table, const char *a)
-{
- size_t i = table->maxlen;
- if (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 (size_t maxlen)
-{
- struct dbt *table;
- CREATE (table, struct dbt, 1);
- table->type = DB_STRING;
- table->maxlen = maxlen;
- return table;
-}
-
-static int numdb_cmp (numdb_key_t a, numdb_key_t b)
-{
- if (a == b)
- return 0;
- if (a < b)
- return -1;
- return 1;
-}
-
-static hash_t numdb_hash (numdb_key_t a)
-{
- return (hash_t) a;
-}
-
-struct dbt *numdb_init (void)
-{
- struct dbt *table;
- CREATE (table, struct dbt, 1);
- table->type = DB_NUMBER;
- return table;
-}
-
-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 = table->ht[table_hash (table, key) % HASH_SIZE];
-
- while (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;
-}
-
-// 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)
- 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)
- 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)
- {
- 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;
-}
-
-// param z = node to remove
-static void db_rebalance_erase (struct dbn *z, struct dbn **root)
-{
- struct dbn *y = z;
- struct dbn *x = NULL;
-
- if (!y->left)
- x = y->right;
- else if (!y->right)
- x = y->left;
- else
- {
- y = y->right;
- while (y->left)
- y = y->left;
- x = y->right;
- }
- struct dbn *x_parent = NULL;
- if (y != 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;
- {
- dbn_color tmp = y->color;
- y->color = z->color;
- z->color = tmp;
- }
- y = z;
- }
- else
- {
- 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;
- }
- if (y->color != RED)
- {
- while (x != *root && (!x || 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 || w->left->color == BLACK) &&
- (!w->right || w->right->color == BLACK))
- {
- w->color = RED;
- x = x_parent;
- x_parent = x->parent;
- }
- else
- {
- if (!w->right|| 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 || w->right->color == BLACK) &&
- (!w->left || w->left->color == BLACK))
- {
- w->color = RED;
- x = x_parent;
- x_parent = x_parent->parent;
- }
- else
- {
- if (!w->left || 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, db_key_t key, db_val_t data)
-{
- 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);
- if (c == 0)
- {
- // key found in table, replace
- // Tell the user of the table to free the key and value
- if (table->release)
- table->release (p->key, p->data);
- p->data = data;
- p->key = key;
- return p;
- }
- // prev is always p->parent?
- prev = p;
- if (c < 0)
- p = p->left;
- else
- p = p->right;
- }
- CREATE (p, struct dbn, 1);
- p->key = key;
- p->data = data;
- p->color = RED;
- if (c == 0)
- { // 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)
- {
- // must rebalance
- db_rebalance (p, &table->ht[hash]);
- }
- return p;
-}
-
-db_val_t db_erase (struct dbt *table, db_key_t key)
-{
- hash_t hash = table_hash (table, key) % HASH_SIZE;
- struct dbn *p = table->ht[hash];
- while (p)
- {
- int 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;
- db_val_t data = p->data;
- db_rebalance_erase (p, &table->ht[hash]);
- free (p);
- 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, db_func_t func, ...)
-{
- va_list ap;
- va_start (ap, func);
-
- for (int i = 0; i < HASH_SIZE; i++)
- {
-#ifdef SMART_WALK_TREE
- db_walk_tree (false, table->ht[i], func, ap);
-#else
- struct dbn *p = table->ht[i];
- if (!p)
- continue;
- struct dbn *stack[64];
- int sp = 0;
- while (1)
- {
- func (p->key, p->data, ap);
- struct dbn *pn = p->left;
- if (pn)
- {
- if (p->right)
- stack[sp++] = p->right;
- p = pn;
- }
- 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);
-}
-
-// This function is suspiciously similar to the previous
-void db_final (struct dbt *table, db_func_t func, ...)
-{
- va_list ap;
- va_start (ap, func);
-
- for (int i = 0; i < HASH_SIZE; i++)
- {
-#ifdef SMART_WALK_TREE
- db_walk_tree (true, table->ht[i], func, ap);
-#else
- struct dbn *p = table->ht[i];
- if (!p)
- continue;
- struct dbn *stack[64];
- int sp = 0;
- while (1)
- {
- if (func)
- func (p->key, p->data, ap);
- struct dbn *pn = p->left;
- if (pn)
- {
- if (p->right)
- stack[sp++] = p->right;
- }
- else // pn == NULL, check the right
- {
- if (p->right)
- pn = p->right;
- else
- {
- if (sp == 0)
- break;
- pn = stack[--sp];
- }
- } // if pn else if !pn
- free (p);
- p = pn;
- } // while true
-#endif // else ! SMART_WALK_TREE
- } // for i
- free (table);
- va_end (ap);
-}
+#include "../poison.hpp"
generated by cgit v1.2.3-60-g2f50 (git 2.42.0) at 2024-06-30 19:33:47 +0000