libosmocore  1.9.0.20-4ca0f.202310312026
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 
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 {
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)
uint16_t node
static void hlist_del_init(struct hlist_node *n)
Delete the specified hlist_node from its list and initialize.
Definition: linuxlist.h:493
#define INIT_HLIST_HEAD(ptr)
Definition: linuxlist.h:420
static int hlist_unhashed(const struct hlist_node *h)
Has node been removed from list and reinitialized?.
Definition: linuxlist.h:438
static int hlist_empty(const struct hlist_head *h)
Is the specified hlist_head structure an empty hlist?.
Definition: linuxlist.h:460
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
static bool __hash_empty(struct hlist_head *ht, unsigned int sz)
Definition: hashtable.h:64
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
static void __hash_init(struct hlist_head *ht, unsigned int sz)
Definition: hashtable.h:26
Simple doubly linked list implementation.
Double linked lists with a single pointer list head.
Definition: linuxlist.h:410
Definition: linuxlist.h:414