a totally self balanced tree for unsigned integers...

[Chris M. Thomasson]

I do not even want to go into why James tried to post this as his own!

:^/ GRRRR!!!!! #$%#$% FUC32432KL#$@#$@


Anyway, He made a fatal mistake! My name is in my cryptic MACROS!!!!

Take a look:

https://groups.google.com/d/topic/comp.programming/tjlLW7fFmsE/discussion


HAW HAW!!!!!


:^)


Anyway, I need to use it now for a database.

 

[Chris M. Thomasson]

"Chris M. Thomasson" wrote in message

[...]

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

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.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"
"----------------------------------------");
____________________________________________________
[...]

 

[Ian Collins]

Chris M. Thomasson wrote:

<stuff>

Why are you responding to an old post in the wrong group?

 

[Chris M. Thomasson]

"Ian Collins" wrote in message news:[email protected]...

Chris M. Thomasson wrote:
<stuff>
Why are you responding to an old post in the wrong group?

Sorry about that Ian.

FWIW, I have to convert my old C code to C++.

I will go ahead and post it here when I am done. AFAICT, it's a
pretty useful tree algorithm.