hashtable.c

Go to the documentation of this file.

/*#*
 *#* $Log$
 *#* Revision 1.8  2007/02/06 16:05:01  asterix
 *#* Replaced ROTATE_* with ROT* defined in macros.h
 *#*
 *#* Revision 1.7  2006/07/19 12:56:27  bernie
 *#* Convert to new Doxygen style.
 *#*
 *#* Revision 1.6  2006/06/01 12:27:39  marco
 *#* Added utilities for protocols
 *#*
 *#*/

#include "hashtable.h"
#include <cfg/debug.h>
#include <cfg/compiler.h>
#include <cfg/macros.h> //ROTL(), ROTR();

#include <string.h>



typedef const void** HashNodePtr;
#define NODE_EMPTY(node)               (!*(node))
#define HT_HAS_INTERNAL_KEY(ht)        (CONFIG_HT_OPTIONAL_INTERNAL_KEY && ht->flags.key_internal)

INLINE uint8_t *key_internal_get_ptr(struct HashTable *ht, HashNodePtr node)
{
    uint8_t* key_buf = ht->key_data.mem;
    size_t index;

    // Compute the index of the node and use it to move within the whole key buffer
    index = node - &ht->mem[0];
    ASSERT(index < (size_t)(1 << ht->max_elts_log2));
    key_buf += index * (INTERNAL_KEY_MAX_LENGTH + 1);

    return key_buf;
}


INLINE void node_get_key(struct HashTable* ht, HashNodePtr node, const void** key, uint8_t* key_length)
{
    if (HT_HAS_INTERNAL_KEY(ht))
    {
        uint8_t* k = key_internal_get_ptr(ht, node);

        // Key has its length stored in the first byte
        *key_length = *k++;
        *key = k;
    }
    else
        *key = ht->key_data.hook(*node, key_length);
}


INLINE bool node_key_match(struct HashTable* ht, HashNodePtr node, const void* key, uint8_t key_length)
{
    const void* key2;
    uint8_t key2_length;

    node_get_key(ht, node, &key2, &key2_length);

    return (key_length == key2_length && memcmp(key, key2, key_length) == 0);
}


static uint16_t calc_hash(const void* _key, uint8_t key_length)
{
    const char* key = (const char*)_key;
    uint16_t hash = key_length;
    int i;
    int len = (int)key_length;

    for (i = 0; i < len; ++i)
        hash = ROTL(hash, 4) ^ key[i];

    return hash ^ (hash >> 6) ^ (hash >> 13);
}


static HashNodePtr perform_lookup(struct HashTable* ht,
                                  const void* key, uint8_t key_length)
{
    uint16_t hash = calc_hash(key, key_length);
    uint16_t mask = ((1 << ht->max_elts_log2) - 1);
    uint16_t index = hash & mask;
    uint16_t first_index = index;
    uint16_t step;
    HashNodePtr node;

    // Fast-path optimization: we check immediately if the current node
    //  is the one we were looking for, so we save the computation of the
    //  increment step in the common case.
    node = &ht->mem[index];
    if (NODE_EMPTY(node)
        || node_key_match(ht, node, key, key_length))
        return node;

    // Increment while going through the hash table in case of collision.
    //  This implements the double-hash technique: we use the higher part
    //  of the hash as a step increment instead of just going to the next
    //  element, to minimize the collisions.
    // Notice that the number must be odd to be sure that the whole table
    //  is traversed. Actually MCD(table_size, step) must be 1, but
    //  table_size is always a power of 2, so we just ensure that step is
    //  never a multiple of 2.
    step = (ROTR(hash, ht->max_elts_log2) & mask) | 1;

    do
    {
        index += step;
        index &= mask;

        node = &ht->mem[index];
        if (NODE_EMPTY(node)
            || node_key_match(ht, node, key, key_length))
            return node;

        // The check is done after the key compare. This actually causes
        //  one more compare in the case the table is full (since the first
        //  element was compared at the very start, and then at the end),
        //  but it makes faster the common path where we enter this loop
        //  for the first time, and index will not match first_index for
        //  sure.
    } while (index != first_index);

    return NULL;
}


void ht_init(struct HashTable* ht)
{
    memset(ht->mem, 0, sizeof(ht->mem[0]) * (1 << ht->max_elts_log2));
}


static bool insert(struct HashTable* ht, const void* key, uint8_t key_length, const void* data)
{
    HashNodePtr node;

    if (!data)
        return false;

    if (HT_HAS_INTERNAL_KEY(ht))
        key_length = MIN(key_length, (uint8_t)INTERNAL_KEY_MAX_LENGTH);

    node = perform_lookup(ht, key, key_length);
    if (!node)
        return false;

    if (HT_HAS_INTERNAL_KEY(ht))
    {
        uint8_t* k = key_internal_get_ptr(ht, node);
        *k++ = key_length;
        memcpy(k, key, key_length);
    }

    *node = data;
    return true;
}


bool ht_insert_with_key(struct HashTable* ht, const void* key, uint8_t key_length, const void* data)
{
#ifdef _DEBUG
    if (!HT_HAS_INTERNAL_KEY(ht))
    {
        // Construct a fake node and use it to match the key
        HashNodePtr node = &data;
        if (!node_key_match(ht, node, key, key_length))
        {
            ASSERT2(0, "parameter key is different from the external key");
            return false;
        }
    }
#endif

    return insert(ht, key, key_length, data);
}


bool ht_insert(struct HashTable* ht, const void* data)
{
    const void* key;
    uint8_t key_length;

#ifdef _DEBUG
    if (HT_HAS_INTERNAL_KEY(ht))
    {
        ASSERT("parameter cannot be a hash table with internal keys - use ht_insert_with_key()"
               && 0);
        return false;
    }
#endif

    key = ht->key_data.hook(data, &key_length);

    return insert(ht, key, key_length, data);
}


const void* ht_find(struct HashTable* ht, const void* key, uint8_t key_length)
{
    HashNodePtr node;

    if (HT_HAS_INTERNAL_KEY(ht))
        key_length = MIN(key_length, (uint8_t)INTERNAL_KEY_MAX_LENGTH);

    node = perform_lookup(ht, key, key_length);

    if (!node || NODE_EMPTY(node))
        return NULL;

    return *node;
}


#if 0

#include <stdlib.h>

bool ht_test(void);

static const void* test_get_key(const void* ptr, uint8_t* length)
{
    const char* s = ptr;
    *length = strlen(s);
    return s;
}

#define NUM_ELEMENTS   256
DECLARE_HASHTABLE_STATIC(test1, 256, test_get_key);
DECLARE_HASHTABLE_INTERNALKEY_STATIC(test2, 256);

static char data[NUM_ELEMENTS][10];
static char keydomain[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";

static bool single_test(void)
{
    int i;

    ht_init(&test1);
    ht_init(&test2);

    for (i=0;i<NUM_ELEMENTS;i++)
    {
        int k;
        int klen;

        do
        {
            klen = (rand() % 8) + 1;
            for (k=0;k<klen;k++)
                data[i][k] = keydomain[rand() % (sizeof(keydomain)-1)];
            data[i][k]=0;
        } while (ht_find_str(&test1, data[i]) != NULL);

        ASSERT(ht_insert(&test1, data[i]));
        ASSERT(ht_insert_str(&test2, data[i], data[i]));
    }

    for (i=0;i<NUM_ELEMENTS;i++)
    {
        char *found1, *found2;

        found1 = (char*)ht_find_str(&test1, data[i]);
        if (strcmp(found1, data[i]) != 0)
        {
            ASSERT(strcmp(found1,data[i]) == 0);
            return false;
        }

        found2 = (char*)ht_find_str(&test2, data[i]);
        if (strcmp(found2, data[i]) != 0)
        {
            ASSERT(strcmp(found2,data[i]) == 0);
            return false;
        }
    }

    return true;
}

static uint16_t rand_seeds[] = { 1, 42, 666, 0xDEAD, 0xBEEF, 0x1337, 0xB00B };

bool ht_test(void)
{
    int i;

    for (i=0;i<countof(rand_seeds);++i)
    {
        srand(rand_seeds[i]);
        if (!single_test())
        {
            kprintf("ht_test failed\n");
            return false;
        }
    }

    kprintf("ht_test successful\n");
    return true;
}

#endif