hashtable.h
Go to the documentation of this file.
/* SPDX-License-Identifier: GPL-2.0 */
/*
* Statically sized hash table implementation
* (C) 2012 Sasha Levin <levinsasha928@gmail.com>
*/
#pragma once
#include <osmocom/core/linuxlist.h>
#include <osmocom/core/hash.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))])
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);
}
#define hash_for_each(name, bkt, obj, member) \
for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\
(bkt)++)\
hlist_for_each_entry(obj, &name[bkt], member)
#define hash_for_each_safe(name, bkt, tmp, obj, member) \
for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\
(bkt)++)\
hlist_for_each_entry_safe(obj, tmp, &name[bkt], member)
#define hash_for_each_possible(name, obj, member, key) \
hlist_for_each_entry(obj, &name[hash_min(key, HASH_BITS(name))], member)
#define hash_for_each_possible_safe(name, obj, tmp, member, key) \
hlist_for_each_entry_safe(obj, tmp,\
&name[hash_min(key, HASH_BITS(name))], member)
node
uint16_t node
hlist_del_init
static void hlist_del_init(struct hlist_node *n)
Delete the specified hlist_node from its list and initialize.
Definition: linuxlist.h:494
INIT_HLIST_HEAD
#define INIT_HLIST_HEAD(ptr)
Definition: linuxlist.h:421
hlist_unhashed
static int hlist_unhashed(const struct hlist_node *h)
Has node been removed from list and reinitialized?.
Definition: linuxlist.h:439
hlist_empty
static int hlist_empty(const struct hlist_head *h)
Is the specified hlist_head structure an empty hlist?.
Definition: linuxlist.h:461
hash.h
hash_del
static void hash_del(struct hlist_node *node)
hash_del - remove an object from a hashtable @node: &struct hlist_node of the object to remove
Definition: hashtable.h:88
__hash_empty
static bool __hash_empty(struct hlist_head *ht, unsigned int sz)
Definition: hashtable.h:64
hash_hashed
static bool hash_hashed(struct hlist_node *node)
hash_hashed - check whether an object is in any hashtable @node: the &struct hlist_node of the object...
Definition: hashtable.h:59
__hash_init
static void __hash_init(struct hlist_head *ht, unsigned int sz)
Definition: hashtable.h:26
linuxlist.h
Simple doubly linked list implementation.
hlist_head
Double linked lists with a single pointer list head.
Definition: linuxlist.h:411
hlist_node
Definition: linuxlist.h:415