path: root/src/common/db.c

// $Id: db.c,v 1.2 2004/09/23 14:43:06 MouseJstr Exp $
// #define MALLOC_DBN
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "db.h"
#include "utils.h"

#ifdef MEMWATCH
#include "memwatch.h"
#endif

#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)
{
    if (table->maxlen)
        return strncmp (a, b, table->maxlen);
    return strcmp (a, b);
}

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;
}

struct dbt *strdb_init (int maxlen)
{
    int  i;
    struct dbt *table;

    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;
}

static int numdb_cmp (struct dbt *table, void *a, void *b)
{
    int  ia, ib;

    ia = (int) a;
    ib = (int) b;

    if ((ia ^ ib) & 0x80000000)
        return ia < 0 ? -1 : 1;

    return ia - ib;
}

static unsigned int numdb_hash (struct dbt *table, void *a)
{
    return (unsigned int) 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;
    return table;
}

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;
}

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;
}

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;
}

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;
}

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;
}

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 *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;
        }
    }
#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;
    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 *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);
#else
    free (p);
#endif
    return data;
}

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);
}

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];
                }
            }
#ifdef MALLOC_DBN
            free_dbn (p);
#else
            free (p);
#endif
            p = pn;
        }
    }
    free (table);
    va_end (ap);
}