comp.lang.c++ - 26 new messages in 10 topics - digest

comp.lang.c++
http://groups.google.com/group/comp.lang.c++?hl=en

comp.lang.c++@googlegroups.com

Today's topics:

* a totally self balanced tree for unsigned integers... - 3 messages, 2
authors
http://groups.google.com/group/comp.lang.c++/t/f7fa6decb00d9969?hl=en
* Available C++ Libraries FAQ - 1 messages, 1 author
http://groups.google.com/group/comp.lang.c++/t/3575ff8bbf7f732e?hl=en
* Boost - 7 messages, 4 authors
http://groups.google.com/group/comp.lang.c++/t/81738d66827a11c8?hl=en
* Can't think of a good subject - 7 messages, 4 authors
http://groups.google.com/group/comp.lang.c++/t/ff410bf5e81204c2?hl=en
* show all subset of a set - 1 messages, 1 author
http://groups.google.com/group/comp.lang.c++/t/708873746ae8ae59?hl=en
* This is 4 u - 1 messages, 1 author
http://groups.google.com/group/comp.lang.c++/t/e7671013dc7133f3?hl=en
* A Brief Introduction to Islam - 2 messages, 2 authors
http://groups.google.com/group/comp.lang.c++/t/a31b8ce9ae713c37?hl=en
* Address one past the end of array - is this syntax a valid C++? - 1 messages,
1 author
http://groups.google.com/group/comp.lang.c++/t/3660f2b84a4f1cb3?hl=en
* SMITHSONIAN SHUT DOWN FOR GOOD -- THE THRINAXODON TIMES REPORTS, YOU CALL
OUT BULLSHIT - 1 messages, 1 author
http://groups.google.com/group/comp.lang.c++/t/91d9902b0f7df726?hl=en
* Flummoxed - Please Help! - 2 messages, 2 authors
http://groups.google.com/group/comp.lang.c++/t/d4b5a6ac1e14e414?hl=en

==============================================================================
TOPIC: a totally self balanced tree for unsigned integers...
http://groups.google.com/group/comp.lang.c++/t/f7fa6decb00d9969?hl=en
==============================================================================

== 1 of 3 ==
Date: Fri, Feb 14 2014 2:51 pm
From: "Chris M. Thomasson"




"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