1 /* SPDX-License-Identifier: GPL-2.0 */
3 * Resizable, Scalable, Concurrent Hash Table
5 * Simple structures that might be needed in include
9 #ifndef _LINUX_RHASHTABLE_TYPES_H
10 #define _LINUX_RHASHTABLE_TYPES_H
12 #include <linux/atomic.h>
13 #include <linux/compiler.h>
14 #include <linux/mutex.h>
15 #include <linux/workqueue.h>
18 struct rhash_head __rcu
*next
;
22 struct rhash_head rhead
;
23 struct rhlist_head __rcu
*next
;
29 * struct rhashtable_compare_arg - Key for the function rhashtable_compare
31 * @key: Key to compare against
33 struct rhashtable_compare_arg
{
34 struct rhashtable
*ht
;
38 typedef u32 (*rht_hashfn_t
)(const void *data
, u32 len
, u32 seed
);
39 typedef u32 (*rht_obj_hashfn_t
)(const void *data
, u32 len
, u32 seed
);
40 typedef int (*rht_obj_cmpfn_t
)(struct rhashtable_compare_arg
*arg
,
44 * struct rhashtable_params - Hash table construction parameters
45 * @nelem_hint: Hint on number of elements, should be 75% of desired size
46 * @key_len: Length of key
47 * @key_offset: Offset of key in struct to be hashed
48 * @head_offset: Offset of rhash_head in struct to be hashed
49 * @max_size: Maximum size while expanding
50 * @min_size: Minimum size while shrinking
51 * @automatic_shrinking: Enable automatic shrinking of tables
52 * @hashfn: Hash function (default: jhash2 if !(key_len % 4), or jhash)
53 * @obj_hashfn: Function to hash object
54 * @obj_cmpfn: Function to compare key with object
56 struct rhashtable_params
{
61 unsigned int max_size
;
63 bool automatic_shrinking
;
65 rht_obj_hashfn_t obj_hashfn
;
66 rht_obj_cmpfn_t obj_cmpfn
;
70 * struct rhashtable - Hash table handle
72 * @key_len: Key length for hashfn
73 * @max_elems: Maximum number of elements in table
74 * @p: Configuration parameters
75 * @rhlist: True if this is an rhltable
76 * @run_work: Deferred worker to expand/shrink asynchronously
77 * @mutex: Mutex to protect current/future table swapping
78 * @lock: Spin lock to protect walker list
79 * @nelems: Number of elements in table
82 struct bucket_table __rcu
*tbl
;
84 unsigned int max_elems
;
85 struct rhashtable_params p
;
87 struct work_struct run_work
;
94 * struct rhltable - Hash table with duplicate objects in a list
95 * @ht: Underlying rhtable
102 * struct rhashtable_walker - Hash table walker
103 * @list: List entry on list of walkers
104 * @tbl: The table that we were walking over
106 struct rhashtable_walker
{
107 struct list_head list
;
108 struct bucket_table
*tbl
;
112 * struct rhashtable_iter - Hash table iterator
113 * @ht: Table to iterate through
114 * @p: Current pointer
115 * @list: Current hash list pointer
116 * @walker: Associated rhashtable walker
117 * @slot: Current slot
118 * @skip: Number of entries to skip in slot
120 struct rhashtable_iter
{
121 struct rhashtable
*ht
;
122 struct rhash_head
*p
;
123 struct rhlist_head
*list
;
124 struct rhashtable_walker walker
;
130 int rhashtable_init(struct rhashtable
*ht
,
131 const struct rhashtable_params
*params
);
132 int rhltable_init(struct rhltable
*hlt
,
133 const struct rhashtable_params
*params
);
135 #endif /* _LINUX_RHASHTABLE_TYPES_H */