1 /* SPDX-License-Identifier: GPL-2.0 */
2 /*
3  * Resizable, Scalable, Concurrent Hash Table
4  *
5  * Simple structures that might be needed in include
6  * files.
7  */
8 
9 #ifndef _LINUX_RHASHTABLE_TYPES_H
10 #define _LINUX_RHASHTABLE_TYPES_H
11 
12 #include <linux/atomic.h>
13 #include <linux/compiler.h>
14 #include <linux/mutex.h>
15 #include <linux/workqueue.h>
16 
17 struct rhash_head {
18 	struct rhash_head __rcu		*next;
19 };
20 
21 struct rhlist_head {
22 	struct rhash_head		rhead;
23 	struct rhlist_head __rcu	*next;
24 };
25 
26 struct bucket_table;
27 
28 /**
29  * struct rhashtable_compare_arg - Key for the function rhashtable_compare
30  * @ht: Hash table
31  * @key: Key to compare against
32  */
33 struct rhashtable_compare_arg {
34 	struct rhashtable *ht;
35 	const void *key;
36 };
37 
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,
41 			       const void *obj);
42 
43 /**
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
55  */
56 struct rhashtable_params {
57 	u16			nelem_hint;
58 	u16			key_len;
59 	u16			key_offset;
60 	u16			head_offset;
61 	unsigned int		max_size;
62 	u16			min_size;
63 	bool			automatic_shrinking;
64 	rht_hashfn_t		hashfn;
65 	rht_obj_hashfn_t	obj_hashfn;
66 	rht_obj_cmpfn_t		obj_cmpfn;
67 };
68 
69 /**
70  * struct rhashtable - Hash table handle
71  * @tbl: Bucket table
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
80  */
81 struct rhashtable {
82 	struct bucket_table __rcu	*tbl;
83 	unsigned int			key_len;
84 	unsigned int			max_elems;
85 	struct rhashtable_params	p;
86 	bool				rhlist;
87 	struct work_struct		run_work;
88 	struct mutex                    mutex;
89 	spinlock_t			lock;
90 	atomic_t			nelems;
91 };
92 
93 /**
94  * struct rhltable - Hash table with duplicate objects in a list
95  * @ht: Underlying rhtable
96  */
97 struct rhltable {
98 	struct rhashtable ht;
99 };
100 
101 /**
102  * struct rhashtable_walker - Hash table walker
103  * @list: List entry on list of walkers
104  * @tbl: The table that we were walking over
105  */
106 struct rhashtable_walker {
107 	struct list_head list;
108 	struct bucket_table *tbl;
109 };
110 
111 /**
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
119  */
120 struct rhashtable_iter {
121 	struct rhashtable *ht;
122 	struct rhash_head *p;
123 	struct rhlist_head *list;
124 	struct rhashtable_walker walker;
125 	unsigned int slot;
126 	unsigned int skip;
127 	bool end_of_table;
128 };
129 
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);
134 
135 #endif /* _LINUX_RHASHTABLE_TYPES_H */
136