libosmocore 1.13.1.1-afb4 Osmocom core library

hashtable.h
Go to the documentation of this file.
1/* SPDX-License-Identifier: GPL-2.0 */
2/*
3 * Statically sized hash table implementation
4 * (C) 2012 Sasha Levin <levinsasha928@gmail.com>
5 */
6
7#pragma once
8
9#include <osmocom/core/linuxlist.h>
10#include <osmocom/core/hash.h>
11
12#define DEFINE_HASHTABLE(name, bits) \
13 struct hlist_head name[1 << (bits)] = \
14 { [0 ... ((1 << (bits)) - 1)] = HLIST_HEAD_INIT }
15
16#define DECLARE_HASHTABLE(name, bits) \
17 struct hlist_head name[1 << (bits)]
18
19#define HASH_SIZE(name) (ARRAY_SIZE(name))
20#define HASH_BITS(name) ilog2(HASH_SIZE(name))
21
22/* Use hash_32 when possible to allow for fast 32bit hashing in 64bit kernels. */
23#define hash_min(val, bits) \
24 (sizeof(val) <= 4 ? hash_32(val, bits) : hash_long(val, bits))
25
26 static inline void __hash_init(struct hlist_head *ht, unsigned int sz)
27{
28 unsigned int i;
29
30 for (i = 0; i < sz; i++)
31 INIT_HLIST_HEAD(&ht[i]);
32}
33
44#define hash_init(hashtable) __hash_init(hashtable, HASH_SIZE(hashtable))
45
52#define hash_add(hashtable, node, key) \
53 hlist_add_head(node, &hashtable[hash_min(key, HASH_BITS(hashtable))])
54
59 static inline bool hash_hashed(struct hlist_node *node)
60{
61 return !hlist_unhashed(node);
62}
63
64 static inline bool __hash_empty(struct hlist_head *ht, unsigned int sz)
65{
66 unsigned int i;
67
68 for (i = 0; i < sz; i++)
69 if (!hlist_empty(&ht[i]))
70 return false;
71
72 return true;
73}
74
82#define hash_empty(hashtable) __hash_empty(hashtable, HASH_SIZE(hashtable))
83
88 static inline void hash_del(struct hlist_node *node)
89{
90 hlist_del_init(node);
91}
92
100#define hash_for_each(name, bkt, obj, member) \
101 for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\
102 (bkt)++)\
103 hlist_for_each_entry(obj, &name[bkt], member)
104
114#define hash_for_each_safe(name, bkt, tmp, obj, member) \
115 for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\
116 (bkt)++)\
117 hlist_for_each_entry_safe(obj, tmp, &name[bkt], member)
118
127#define hash_for_each_possible(name, obj, member, key) \
128 hlist_for_each_entry(obj, &name[hash_min(key, HASH_BITS(name))], member)
129
139#define hash_for_each_possible_safe(name, obj, tmp, member, key) \
140 hlist_for_each_entry_safe(obj, tmp,\
141 &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:503
INIT_HLIST_HEAD
#define INIT_HLIST_HEAD(ptr)
Definition: linuxlist.h:430
hlist_unhashed
static int hlist_unhashed(const struct hlist_node *h)
Has node been removed from list and reinitialized?.
Definition: linuxlist.h:448
hlist_empty
static int hlist_empty(const struct hlist_head *h)
Is the specified hlist_head structure an empty hlist?.
Definition: linuxlist.h:470
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:420
hlist_node
Definition: linuxlist.h:424