jweinst1
4/28/2020 - 11:46 PM

A bit trie data structure for measuring hashing effectiveness

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