From 1e77f5dc8d95bbf912205c85274d294a80ea65c9 Mon Sep 17 00:00:00 2001
From: Ben Longbons <b.r.longbons@gmail.com>
Date: Sat, 23 Feb 2013 14:28:21 -0800
Subject: Replace struct dbt with typesafe std::map wrappers

Also fix broken save/accreg.txt reading.
---
 src/common/db.cpp | 545 ------------------------------------------------------
 src/common/db.hpp | 174 +++++++++--------
 2 files changed, 101 insertions(+), 618 deletions(-)

(limited to 'src/common')

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);
-}
diff --git a/src/common/db.hpp b/src/common/db.hpp
index 7d07b1d..d171429 100644
--- a/src/common/db.hpp
+++ b/src/common/db.hpp
@@ -1,91 +1,119 @@
-// WARNING: there is a system header by this name
 #ifndef DB_HPP
 #define DB_HPP
+//    db.hpp - convenience wrappers over std::map<K, V>
+//
+//    Copyright © 2013 Ben Longbons <b.r.longbons@gmail.com>
+//
+//    This file is part of The Mana World (Athena server)
+//
+//    This program is free software: you can redistribute it and/or modify
+//    it under the terms of the GNU General Public License as published by
+//    the Free Software Foundation, either version 3 of the License, or
+//    (at your option) any later version.
+//
+//    This program is distributed in the hope that it will be useful,
+//    but WITHOUT ANY WARRANTY; without even the implied warranty of
+//    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+//    GNU General Public License for more details.
+//
+//    You should have received a copy of the GNU General Public License
+//    along with this program.  If not, see <http://www.gnu.org/licenses/>.
 
 # include "sanity.hpp"
 
-# include <functional>
+# include <map>
 
-/// Number of tree roots
-// Somewhat arbitrary - larger wastes more space but is faster for large trees
-// num % HASH_SIZE minimize collisions even for similar num
-constexpr int HASH_SIZE = 256 + 27;
-
-typedef enum dbn_color
+template<class K, class V>
+class Map
 {
-    RED,
-    BLACK,
-} dbn_color;
+    typedef std::map<K, V> Impl;
 
-typedef intptr_t numdb_key_t;
-typedef union db_key_t
-{
-    char *ms __attribute__((deprecated));
-    const char* s;
-    numdb_key_t i;
+    Impl impl;
+public:
+    typedef typename Impl::iterator iterator;
+    typedef typename Impl::const_iterator const_iterator;
 
-    db_key_t(numdb_key_t n) : i(n) {}
-    db_key_t(const char * z) : s(z) {}
-} db_key_t;
-typedef void* db_val_t;
-typedef uint32_t hash_t;
-typedef std::function<void(db_key_t, db_val_t)> db_func_t;
+    iterator begin() { return impl.begin(); }
+    iterator end() { return impl.end(); }
+    const_iterator begin() const { return impl.begin(); }
+    const_iterator end() const { return impl.end(); }
 
-/// DataBase Node
-struct dbn
-{
-    struct dbn *parent, *left, *right;
-    dbn_color color;
-    db_key_t key;
-    db_val_t data;
-};
+    V *search(const K& k)
+    {
+        iterator it = impl.find(k);
+        if (it == impl.end())
+            return nullptr;
+        return &it->second;
+    }
+    const V *search(const K& k) const
+    {
+        const_iterator it = impl.find(k);
+        if (it == impl.end())
+            return nullptr;
+        return &it->second;
+    }
+    void insert(K k, V v)
+    {
+        // As far as I can tell, this is the simplest way to
+        // implement move-only insert-with-replacement.
+        iterator it = impl.lower_bound(k);
+        // invariant: if it is valid, it->first >= k
+        if (it != impl.end() && it->first == k)
+            it->second = std::move(v);
+        else
+            it = impl.insert(std::pair<K, V>(std::move(k), std::move(v))).first;
+        return (void)&it->second;
 
-typedef enum dbt_type
-{
-    DB_NUMBER,
-    DB_STRING,
-} dbt_type;
+    }
+    V *init(K k)
+    {
+        return &impl[k];
+    }
+    void erase(const K& k)
+    {
+        impl.erase(k);
+    }
+    void clear()
+    {
+        impl.clear();
+    }
+    bool empty()
+    {
+        return impl.empty();
+    }
+};
 
-/// DataBase Table
-struct dbt
+template<class K, class V>
+class DMap
 {
-    dbt_type type;
-    /// Note, before replacement, key/values to be replaced
-    // TODO refactor to decrease/eliminate the uses of this?
-    void(*release)(db_key_t, db_val_t) __attribute__((deprecated));
-    /// Maximum length of a string key - TODO refactor to ensure all strings are NUL-terminated
-    size_t maxlen __attribute__((deprecated));
-    /// The root trees
-    struct dbn *ht[HASH_SIZE];
-};
+    typedef Map<K, V> Impl;
 
-# define strdb_search(t,k)   db_search((t), (db_key_t)(k))
-# define strdb_insert(t,k,d) db_insert((t), (db_key_t)(k), (db_val_t)(d))
-# define strdb_erase(t,k)    db_erase((t), (db_key_t)(k))
-# define strdb_foreach       db_foreach
-# define strdb_final         db_final
-# define numdb_search(t,k)   db_search((t), (db_key_t)(k))
-# define numdb_insert(t,k,d) db_insert((t), (db_key_t)(k), (db_val_t)(d))
-# define numdb_erase(t,k)    db_erase((t), (db_key_t)(k))
-# define numdb_foreach       db_foreach
-# define numdb_final         db_final
+    Impl impl;
+public:
+    typedef typename Impl::iterator iterator;
+    typedef typename Impl::const_iterator const_iterator;
 
-/// Create a map from char* to void*, with strings possibly not null-terminated
-struct dbt *strdb_init(size_t maxlen);
-/// Create a map from int to void*
-struct dbt *numdb_init(void);
-/// Return the value corresponding to the key, or NULL if not found
-db_val_t db_search(struct dbt *table, db_key_t key);
-/// Add or replace table[key] = data
-// if it was already there, call release
-struct dbn *db_insert(struct dbt *table, db_key_t key, db_val_t data);
-/// Remove a key from the table, returning the data
-db_val_t db_erase(struct dbt *table, db_key_t key);
+    iterator begin() { return impl.begin(); }
+    iterator end() { return impl.end(); }
+    const_iterator begin() const { return impl.begin(); }
+    const_iterator end() const { return impl.end(); }
 
-/// Execute a function for every element, in unspecified order
-void db_foreach(struct dbt *, db_func_t);
-// opposite of init? Calls release for every element and frees memory
-// This probably isn't really needed: we don't have to free memory while exiting
-void db_final(struct dbt *, db_func_t) __attribute__((deprecated));
+    V get(K k)
+    {
+        V *vp = impl.search(k);
+        return vp ? *vp : V();
+    }
+    void put(K k, V v)
+    {
+        if (v == V())
+            impl.erase(k);
+        else
+            impl.insert(k, v);
+    }
+    void clear()
+    {
+        impl.clear();
+    }
+};
 
 #endif // DB_HPP
-- 
cgit v1.2.3-70-g09d2