A bit trie data structure for measuring hashing effectiveness
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <limits.h>
/**
* Data structure to monitor the collision rate of hashes.
* Keys are 64 bit unsigned integers, read big endian sytle
*/
struct bit_node_t {
size_t count;
struct bit_node_t* children[2];
};
typedef struct bit_node_t bit_node_t;
bit_node_t* bit_node_new(bit_node_t* b0, bit_node_t* b1) {
bit_node_t* node = calloc(1, sizeof(bit_node_t));
assert(node != NULL);
node->children[0] = b0;
node->children[1] = b1;
return node;
}
void bit_node_del(bit_node_t* node) {
if (node->children[0] != NULL)
bit_node_del(node->children[0]);
if (node->children[1] != NULL)
bit_node_del(node->children[1]);
free(node);
}
void bit_node_insert(bit_node_t* root, size_t digest)
{
bit_node_t* ptr = root;
size_t biti = CHAR_BIT * sizeof(size_t);
while (--biti) {
#ifdef BIT_DEBUG
printf("INSERT Got bit for node: %zu, at index %zu\n", (digest >> biti) & 1, biti);
#endif
bit_node_t** child = &(ptr->children[(digest >> biti) & 1]);
if (*child == NULL) {
*child = bit_node_new(NULL, NULL);
}
ptr = *child;
}
// last node, increase count
bit_node_t** child = &(ptr->children[(digest >> biti) & 1]);
#ifdef BIT_DEBUG
printf("INSERT Got bit for node: %zu, at index %zu\n", (digest >> biti) & 1, biti);
#endif
if (*child == NULL) {
*child = bit_node_new(NULL, NULL);
}
(*child)->count++;
}
size_t bit_node_find(const bit_node_t* root, size_t key)
{
const bit_node_t* ptr = root;
long biti = (long)(CHAR_BIT * sizeof(size_t));
while (--biti > 0) {
const bit_node_t* const * child = &(ptr->children[(key >> biti) & 1]);
#ifdef BIT_DEBUG
printf("FIND Got bit for node: %zu, at index %ld\n", (key >> biti) & 1, biti);
#endif
if (*child == NULL)
return 0;
else
ptr = *child;
}
#ifdef BIT_DEBUG
printf("FIND Got bit for node: %zu, at index %ld\n", (key >> biti) & 1, biti);
#endif
const bit_node_t* const * child = &(ptr->children[(key >> biti) & 1]);
if (*child == NULL) {
return 0;
}
return (*child)->count;
}
typedef struct bit_node_t bit_node_t;
int main(int argc, char const* argv[]) {
bit_node_t* root = bit_node_new(NULL, NULL);
bit_node_insert(root, 0x0F0F);
bit_node_insert(root, 0x0F0F);
printf("The count is %zu\n", bit_node_find(root, 0x0F0F));
bit_node_del(root);
return 0;
}