tommyhashlin.h

Go to the documentation of this file.

// SPDX-License-Identifier: BSD-2-Clause
// Copyright (C) 2010 Andrea Mazzoleni
 
#ifndef TOMMY_HASHLIN_H
#define TOMMY_HASHLIN_H
 
#include "tommyhash.h"
#include "tommylist.h"
 
/******************************************************************************/
/* hashlin */
 
#define TOMMY_HASHLIN_BIT 6
 
typedef tommy_node tommy_hashlin_node;
 
typedef struct tommy_hashlin_struct {
        tommy_hashlin_node** bucket[TOMMY_SIZE_BIT]; 
        tommy_size_t bucket_max; 
        tommy_size_t bucket_mask; 
        tommy_size_t low_max; 
        tommy_size_t low_mask; 
        tommy_size_t split; 
        tommy_size_t count; 
        tommy_uint_t bucket_bit; 
        tommy_uint_t state; 
} tommy_hashlin;
 
TOMMY_API void tommy_hashlin_init(tommy_hashlin* hashlin);
 
TOMMY_API void tommy_hashlin_done(tommy_hashlin* hashlin);
 
tommy_inline void tommy_hashlin_swap(tommy_hashlin* first, tommy_hashlin* second)
{
        tommy_hashlin tmp = *first;
        *first = *second;
        *second = tmp;
}
 
TOMMY_API void tommy_hashlin_clear(tommy_hashlin* hashlin);
 
TOMMY_API void tommy_hashlin_insert(tommy_hashlin* hashlin, tommy_hashlin_node* node, void* data, tommy_hash_t hash);
 
TOMMY_API void* tommy_hashlin_insert_unique(tommy_hashlin* hashlin, tommy_hashlin_node* node, void* data, tommy_search_func* cmp, const void* cmp_arg, tommy_hash_t hash);
 
TOMMY_API void* tommy_hashlin_remove(tommy_hashlin* hashlin, tommy_search_func* cmp, const void* cmp_arg, tommy_hash_t hash);
 
tommy_inline tommy_hashlin_node** tommy_hashlin_pos(tommy_hashlin* hashlin, tommy_hash_t pos)
{
        tommy_uint_t bsr;
 
        /* get the highest bit set, in case of all 0, return 0 */
        bsr = tommy_ilog2(pos | 1);
 
        return &hashlin->bucket[bsr][pos];
}
 
tommy_inline tommy_hashlin_node** tommy_hashlin_bucket_ref(tommy_hashlin* hashlin, tommy_hash_t hash)
{
        tommy_size_t pos = hash & hashlin->low_mask;
        tommy_size_t high_pos = hash & hashlin->bucket_mask;
 
        /* if this position is already allocated in the high half */
        if (pos < hashlin->split) {
                /* the following assignment is expected to be implemented */
                /* with a conditional move instruction */
                /* that results in a little better and constant performance */
                /* regardless of the split position. */
                /* this affects mostly the worst case, when the split value */
                /* is near at its half, resulting in a totally unpredictable */
                /* condition by the CPU. */
                /* in such case, the use of the conditional move is generally faster. */
 
                /* use also the high bit */
                pos = high_pos;
        }
 
        return tommy_hashlin_pos(hashlin, pos);
}
 
tommy_inline tommy_hashlin_node* tommy_hashlin_bucket(tommy_hashlin* hashlin, tommy_hash_t hash)
{
        return *tommy_hashlin_bucket_ref(hashlin, hash);
}
 
tommy_inline tommy_hashlin_node* tommy_hashlin_find(tommy_hashlin* hashlin, tommy_search_func* cmp, const void* cmp_arg, tommy_hash_t hash)
{
        tommy_hashlin_node* i = tommy_hashlin_bucket(hashlin, hash);
 
        while (i) {
                /* we first check if the hash matches, as in the same bucket we may have multiple hash values */
                if (i->index == hash && cmp(cmp_arg, i->data) == 0)
                        return i;
                i = i->next;
        }
        return 0;
}
 
tommy_inline void* tommy_hashlin_search(tommy_hashlin* hashlin, tommy_search_func* cmp, const void* cmp_arg, tommy_hash_t hash)
{
        tommy_hashlin_node* node = tommy_hashlin_find(hashlin, cmp, cmp_arg, hash);
 
        return node ? node->data : 0;
}
 
TOMMY_API void* tommy_hashlin_remove_existing(tommy_hashlin* hashlin, tommy_hashlin_node* node);
 
TOMMY_API tommy_hashlin_node* tommy_hashlin_head(tommy_hashlin* hashlin);
 
TOMMY_API tommy_hashlin_node* tommy_hashlin_tail(tommy_hashlin* hashlin);
 
TOMMY_API tommy_hashlin_node* tommy_hashlin_next(tommy_hashlin* hashlin, tommy_hashlin_node* node);
 
TOMMY_API tommy_hashlin_node* tommy_hashlin_prev(tommy_hashlin* hashlin, tommy_hashlin_node* node);
 
TOMMY_API void tommy_hashlin_rehash_existing(tommy_hashlin* hashlin, tommy_hashlin_node* node, tommy_hash_t hash);
 
TOMMY_API void tommy_hashlin_foreach(tommy_hashlin* hashlin, tommy_foreach_func* func);
 
TOMMY_API void tommy_hashlin_foreach_arg(tommy_hashlin* hashlin, tommy_foreach_arg_func* func, void* arg);
 
tommy_inline tommy_size_t tommy_hashlin_count(const tommy_hashlin* hashlin)
{
        return hashlin->count;
}
 
tommy_inline tommy_bool_t tommy_hashlin_empty(const tommy_hashlin* hashlin)
{
        return hashlin->count == 0;
}
 
tommy_inline tommy_size_t tommy_hashlin_bucket_count(const tommy_hashlin* hashlin)
{
        return hashlin->low_max + hashlin->split;
}
 
TOMMY_API tommy_size_t tommy_hashlin_memory_usage(const tommy_hashlin* hashlin);
 
TOMMY_API void tommy_hashlin_to_list(tommy_hashlin* hashlin, tommy_list* list);
 
#endif