Re: a totally self balanced tree for unsigned integers...

"Chris M. Thomasson" wrote in message
news:ldm2of$p64$1@speranza.aioe.org...

[...]

Here is the link to the relevant code:

https://groups.google.com/forum/#!msg/comp.programming/tjlLW7fFmsE/fXdyD9QcG2cJ

notice my name in TREE_NAME?

Grrr!!!
____________________________________________________
typedef unsigned int tree_key;

#define BITS 4
#define MASK ~(UINT_MAX << BITS)
#define NODES (MASK + 1)

struct tree
{
    struct tree* nodes[NODES];
    tree_key key;
};

struct tree*
tree_find(struct tree* root,
          tree_key origin_key)
{
    tree_key key = origin_key;

    while (root)
    {
        if (root->key == origin_key) break;

        root = root->nodes[key & MASK];

        key >>= BITS;
    }

    return root;
}

Is that something like what you are thinking of Ben?

Here is source code for a quick test program that implements the new
algorithm:

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <time.h>

#define QUOTEX(t)#t
#define QUOTE(t)QUOTEX(t)

#define HASH_DEPTH 1

#define HASH(k) ((k) & (HASH_DEPTH - 1))

#define TREE_BITS 4
#define TREE_MASK ~(UINT_MAX << TREE_BITS)
#define TREE_NODES (TREE_MASK + 1)

#define TREE_SEARCH_ALGO_BINARY 0
#define TREE_SEARCH_ALGO_BIT 1

#define TREE_SEARCH_ALGO TREE_SEARCH_ALGO_BIT

#if (TREE_SEARCH_ALGO == TREE_SEARCH_ALGO_BINARY)
# undef TREE_NODES
# define TREE_NODES 2
# define TREE_NAME "Normal Binary Tree\n\n\n"
#else
# define TREE_NAME "Chris' %lu-Ary %lu-Bit Trie?\n\n\n", \
                     TREE_NODES, TREE_BITS
#endif

typedef unsigned int tree_key;

static unsigned long int g_tree_search_count = 0;
static unsigned long int g_tree_search_count_max = 0;
static unsigned long int g_tree_search_count_min = 0;

struct tree
{
    struct tree* nodes[TREE_NODES + 2];
    tree_key key;
};

struct hash
{
    struct tree* buckets[HASH_DEPTH];
};

#define HASH_INIT { { NULL } }

struct tree*
tree_sys_find(struct tree*** pproot,
              tree_key origin_key)
{
    tree_key key = origin_key;

    unsigned long int count = 0;
    struct tree** proot = *pproot;
    struct tree* t = *proot;
    while (t)
    {
        ++count;

        if (t->key == origin_key)
        {
            break;
        }

#if (TREE_SEARCH_ALGO == TREE_SEARCH_ALGO_BIT)

        proot = &t->nodes[key & TREE_MASK];
        t = *proot;
        key >>= TREE_BITS;

#else

        if (origin_key < t->key)
        {
            proot = &t->nodes[0];
            t = *proot;
        }

        else
        {
            proot = &t->nodes[1];
            t = *proot;
        }

#endif

    }

    *pproot = proot;

    g_tree_search_count += count;

    if (count > g_tree_search_count_max)
    {
        g_tree_search_count_max = count;
    }
    else
    {
        g_tree_search_count_min = count;
    }

    return t;
}

int
tree_insert(struct tree** proot,
            struct tree* tnew)
{
    if (! tree_sys_find(&proot, tnew->key))
    {
        memset(tnew->nodes, '\0', sizeof(tnew->nodes));
        *proot = tnew;
    }
    return 0;
}

struct tree*
tree_find(struct tree** proot,
          tree_key key)
{
    return tree_sys_find(&proot, key);
}

void
tree_iterate(struct tree* root)
{
    if (root)
    {
        size_t i;

        for (i = 0; i < TREE_NODES; ++i)
        {
            tree_iterate(root->nodes[i]);
        }

        printf("tree_iterate: %lu\n", root->key);
    }
}

int
hash_insert(struct hash* h,
            struct tree* tnew)
{
    return tree_insert(&h->buckets[HASH(tnew->key)], tnew);
}

struct tree*
hash_find(struct hash* h,
          tree_key key)
{
    return tree_find(&h->buckets[HASH(key)], key);
}

#define DEPTH 1000000

int main(void)
{
    size_t i;
    struct tree* tn;
    static struct tree nodes[DEPTH];

    static struct hash hash_init = HASH_INIT;
    struct hash h = hash_init;

    srand((unsigned int)time(NULL));

    printf("Testing Algorithm: " TREE_NAME);

    puts("\nRandomized Insertion\n"
         "----------------------------------------");

    g_tree_search_count = 0;
    g_tree_search_count_max = 0;
    g_tree_search_count_min = ULONG_MAX;
    for (i = 0; i < DEPTH; ++i)
    {
        nodes[i].key = rand();
        hash_insert(&h, nodes + i);
    }
    for (i = 0; i < DEPTH; ++i)
    {
        tn = hash_find(&h, nodes[DEPTH - i - 1].key);
        if (! tn)
        {
            assert(tn);
            abort();
        }

        if (tn->key != nodes[DEPTH - i - 1].key)
        {
            assert(tn->key == nodes[DEPTH - i - 1].key);
            abort();
        }
    }
    printf("inserts/finds: %lu\n"
           "hash depth: %lu\n"
           "average: %lu\n"
           "maximum: %lu\n"
           "minimum: %lu\n",
           DEPTH,
           HASH_DEPTH,
           (g_tree_search_count / 2) / DEPTH,
           g_tree_search_count_max,
           g_tree_search_count_min);

    puts("\n\n\nSequential Worst-Case Insertion\n"
         "----------------------------------------");
____________________________________________________
[...]