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/alloc_tag.h>
13 #include <linux/atomic.h>
14 #include <linux/compiler.h>
15 #include <linux/mutex.h>
16 #include <linux/workqueue_types.h>
17
18 struct rhash_head {
19 struct rhash_head __rcu *next;
20 };
21
22 struct rhlist_head {
23 struct rhash_head rhead;
24 struct rhlist_head __rcu *next;
25 };
26
27 struct bucket_table;
28
29 /**
30 * struct rhashtable_compare_arg - Key for the function rhashtable_compare
31 * @ht: Hash table
32 * @key: Key to compare against
33 */
34 struct rhashtable_compare_arg {
35 struct rhashtable *ht;
36 const void *key;
37 };
38
39 typedef u32 (*rht_hashfn_t)(const void *data, u32 len, u32 seed);
40 typedef u32 (*rht_obj_hashfn_t)(const void *data, u32 len, u32 seed);
41 typedef int (*rht_obj_cmpfn_t)(struct rhashtable_compare_arg *arg,
42 const void *obj);
43
44 /**
45 * struct rhashtable_params - Hash table construction parameters
46 * @nelem_hint: Hint on number of elements, should be 75% of desired size
47 * @key_len: Length of key
48 * @key_offset: Offset of key in struct to be hashed
49 * @head_offset: Offset of rhash_head in struct to be hashed
50 * @max_size: Maximum size while expanding
51 * @min_size: Minimum size while shrinking
52 * @automatic_shrinking: Enable automatic shrinking of tables
53 * @hashfn: Hash function (default: jhash2 if !(key_len % 4), or jhash)
54 * @obj_hashfn: Function to hash object
55 * @obj_cmpfn: Function to compare key with object
56 */
57 struct rhashtable_params {
58 u16 nelem_hint;
59 u16 key_len;
60 u16 key_offset;
61 u16 head_offset;
62 unsigned int max_size;
63 u16 min_size;
64 bool automatic_shrinking;
65 rht_hashfn_t hashfn;
66 rht_obj_hashfn_t obj_hashfn;
67 rht_obj_cmpfn_t obj_cmpfn;
68 };
69
70 /**
71 * struct rhashtable - Hash table handle
72 * @tbl: Bucket table
73 * @key_len: Key length for hashfn
74 * @max_elems: Maximum number of elements in table
75 * @p: Configuration parameters
76 * @rhlist: True if this is an rhltable
77 * @run_work: Deferred worker to expand/shrink asynchronously
78 * @mutex: Mutex to protect current/future table swapping
79 * @lock: Spin lock to protect walker list
80 * @nelems: Number of elements in table
81 */
82 struct rhashtable {
83 struct bucket_table __rcu *tbl;
84 unsigned int key_len;
85 unsigned int max_elems;
86 struct rhashtable_params p;
87 bool rhlist;
88 struct work_struct run_work;
89 struct mutex mutex;
90 spinlock_t lock;
91 atomic_t nelems;
92 #ifdef CONFIG_MEM_ALLOC_PROFILING
93 struct alloc_tag *alloc_tag;
94 #endif
95 };
96
97 /**
98 * struct rhltable - Hash table with duplicate objects in a list
99 * @ht: Underlying rhtable
100 */
101 struct rhltable {
102 struct rhashtable ht;
103 };
104
105 /**
106 * struct rhashtable_walker - Hash table walker
107 * @list: List entry on list of walkers
108 * @tbl: The table that we were walking over
109 */
110 struct rhashtable_walker {
111 struct list_head list;
112 struct bucket_table *tbl;
113 };
114
115 /**
116 * struct rhashtable_iter - Hash table iterator
117 * @ht: Table to iterate through
118 * @p: Current pointer
119 * @list: Current hash list pointer
120 * @walker: Associated rhashtable walker
121 * @slot: Current slot
122 * @skip: Number of entries to skip in slot
123 */
124 struct rhashtable_iter {
125 struct rhashtable *ht;
126 struct rhash_head *p;
127 struct rhlist_head *list;
128 struct rhashtable_walker walker;
129 unsigned int slot;
130 unsigned int skip;
131 bool end_of_table;
132 };
133
134 int rhashtable_init_noprof(struct rhashtable *ht,
135 const struct rhashtable_params *params);
136 #define rhashtable_init(...) alloc_hooks(rhashtable_init_noprof(__VA_ARGS__))
137
138 int rhltable_init_noprof(struct rhltable *hlt,
139 const struct rhashtable_params *params);
140 #define rhltable_init(...) alloc_hooks(rhltable_init_noprof(__VA_ARGS__))
141
142 #endif /* _LINUX_RHASHTABLE_TYPES_H */
143
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.