hashtable.h

Go to the documentation of this file.

/*
 * Statically sized hash table implementation
 * (C) 2012  Sasha Levin <[email protected]>
 */

#ifndef _LINUX_HASHTABLE_H
#define _LINUX_HASHTABLE_H

#include <linux/list.h>
#include <linux/types.h>
#include <linux/kernel.h>
#include <linux/hash.h>
#include <linux/rculist.h>

#define DEFINE_HASHTABLE(name, bits)                        \
    struct hlist_head name[1 << (bits)] =                   \
            { [0 ... ((1 << (bits)) - 1)] = HLIST_HEAD_INIT }

#define DECLARE_HASHTABLE(name, bits)                                       \
    struct hlist_head name[1 << (bits)]

#define HASH_SIZE(name) (ARRAY_SIZE(name))
#define HASH_BITS(name) ilog2(HASH_SIZE(name))

/* Use hash_32 when possible to allow for fast 32bit hashing in 64bit kernels. */
#define hash_min(val, bits)                         \
    (sizeof(val) <= 4 ? hash_32(val, bits) : hash_long(val, bits))

static inline void __hash_init(struct hlist_head *ht, unsigned int sz)
{
    unsigned int i;

    for (i = 0; i < sz; i++)
        INIT_HLIST_HEAD(&ht[i]);
}

#define hash_init(hashtable) __hash_init(hashtable, HASH_SIZE(hashtable))

#define hash_add(hashtable, node, key)                      \
    hlist_add_head(node, &hashtable[hash_min(key, HASH_BITS(hashtable))])

#define hash_add_rcu(hashtable, node, key)                  \
    hlist_add_head_rcu(node, &hashtable[hash_min(key, HASH_BITS(hashtable))])

static inline bool hash_hashed(struct hlist_node *node)
{
    return !hlist_unhashed(node);
}

static inline bool __hash_empty(struct hlist_head *ht, unsigned int sz)
{
    unsigned int i;

    for (i = 0; i < sz; i++)
        if (!hlist_empty(&ht[i]))
            return false;

    return true;
}

#define hash_empty(hashtable) __hash_empty(hashtable, HASH_SIZE(hashtable))

static inline void hash_del(struct hlist_node *node)
{
    hlist_del_init(node);
}

static inline void hash_del_rcu(struct hlist_node *node)
{
    hlist_del_init_rcu(node);
}

#define hash_for_each(name, bkt, node, obj, member)             \
    for ((bkt) = 0, node = NULL; node == NULL && (bkt) < HASH_SIZE(name); (bkt)++)\
        hlist_for_each_entry(obj, node, &name[bkt], member)

#define hash_for_each_rcu(name, bkt, node, obj, member)             \
    for ((bkt) = 0, node = NULL; node == NULL && (bkt) < HASH_SIZE(name); (bkt)++)\
        hlist_for_each_entry_rcu(obj, node, &name[bkt], member)

#define hash_for_each_safe(name, bkt, node, tmp, obj, member)           \
    for ((bkt) = 0, node = NULL; node == NULL && (bkt) < HASH_SIZE(name); (bkt)++)\
        hlist_for_each_entry_safe(obj, node, tmp, &name[bkt], member)

#define hash_for_each_possible(name, obj, node, member, key)            \
    hlist_for_each_entry(obj, node, &name[hash_min(key, HASH_BITS(name))], member)

#define hash_for_each_possible_rcu(name, obj, node, member, key)        \
    hlist_for_each_entry_rcu(obj, node, &name[hash_min(key, HASH_BITS(name))], member)

#define hash_for_each_possible_safe(name, obj, node, tmp, member, key)      \
    hlist_for_each_entry_safe(obj, node, tmp,               \
        &name[hash_min(key, HASH_BITS(name))], member)


#endif