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 | |