Replace struct dbt with typesafe std::map wrappers

Also fix broken save/accreg.txt reading.

1 files changed, 0 insertions, 545 deletions

diff --git a/src/common/db.cpp b/src/common/db.cpp
index 970e054..cc58ad8 100644
--- a/src/common/db.cpp
+++ b/src/common/db.cpp
@@ -1,548 +1,3 @@
 #include "db.hpp"
 
-#include <cstdlib>
-#include <cstring>
-
-#include "utils.hpp"
-
 #include "../poison.hpp"
-
-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
-void db_walk_tree(bool dealloc, struct dbn* p, db_func_t func)
-{
-    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);
-        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)
-{
-    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);
-            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
-}
-
-// This function is suspiciously similar to the previous
-void db_final(struct dbt *table, db_func_t func)
-{
-    for (int i = 0; i < HASH_SIZE; i++)
-    {
-#ifdef SMART_WALK_TREE
-        db_walk_tree(true, table->ht[i], func);
-#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);
-            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);
-}