1 /*
2 * Copyright (c) 2019 The Linux Foundation. All rights reserved.
3 * Copyright (c) 2022-2024 Qualcomm Innovation Center, Inc. All rights reserved.
4 *
5 * Permission to use, copy, modify, and/or distribute this software for
6 * any purpose with or without fee is hereby granted, provided that the
7 * above copyright notice and this permission notice appear in all
8 * copies.
9 *
10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL
11 * WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED
12 * WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE
13 * AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL
14 * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
15 * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
16 * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
17 * PERFORMANCE OF THIS SOFTWARE.
18 */
19
20 /**
21 * DOC: qdf_ptr_hash.h
22 *
23 * A minimal hashtable implementation for doing fast lookups via pointer.
24 *
25 * qdf_ptr_hash also has the benefit of knowing its own size, allowing a pointer
26 * to the hashtable to be passed around and embedded in other structs. Since
27 * every hashtable is not necessarily of the same size, this allows using hash
28 * tables in a lot of new places which would be impossible with the current
29 * kernel hashtable implementation.
30 *
31 * Because the size of the hashtable varies with the number of bits used in the
32 * hash, declaring a qdf_ptr_hash is a bit different. If you want to embed a
33 * qdf_ptr_hash in another type, use a combination of qdf_ptr_hash_declare() and
34 * qdf_ptr_hash_ptr(). If you just want to declare and use a qdf_ptr_hash, use
35 * qdf_ptr_hash_declare_ptr() instead. Either method will ensure the appropriate
36 * number of bytes is accounted for using an internal union, and provides the
37 * consumer with a pointer to a qdf_ptr_hash type which can be used with all of
38 * the other qdf_ptr_hash APIs. Alternatively, you can skip these complexities
39 * by simply dynamically allocating the qdf_ptr_hash via qdf_ptr_hash_create().
40 */
41
42 #ifndef __QDF_PTR_HASH_H
43 #define __QDF_PTR_HASH_H
44
45 #include "i_qdf_ptr_hash.h"
46 #include "qdf_mem.h"
47 #include "qdf_slist.h"
48 #include "qdf_types.h"
49 #include "qdf_util.h"
50
51 /**
52 * struct qdf_ptr_hash_bucket - a type representing a hash bucket
53 * @list: the list used for hash chaining
54 */
55 struct qdf_ptr_hash_bucket {
56 struct qdf_slist list;
57 };
58
59 /**
60 * struct qdf_ptr_hash - a hash table type for doing fast lookups via pointer
61 * @bits: the number of bits to use when hashing keys
62 * @count: the number of buckets, always equal to 2^@bits
63 * @buckets: empty bucket array for accessing a variable length array of buckets
64 */
65 struct qdf_ptr_hash {
66 int8_t bits;
67 int16_t count;
68 struct qdf_ptr_hash_bucket buckets[];
69 };
70
71 /**
72 * struct qdf_ptr_hash_entry - entry type of membership in a qdf_ptr_hash
73 * @key: the value used as the key for insertion/lookup
74 * @node: the list node used for hash chaining
75 */
76 struct qdf_ptr_hash_entry {
77 uintptr_t key;
78 struct qdf_slist_node node;
79 };
80
81 #define __qdf_ptr_hash_size(bits) (sizeof(struct qdf_ptr_hash) + \
82 sizeof(((struct qdf_ptr_hash *)0)->buckets[0]) * (1 << bits))
83
84 /**
85 * qdf_ptr_hash_declare() - declare a new qdf_ptr_hash
86 * @name: the C identifier to use for the new hash table
87 * @_bits: The number of bits to use for hashing
88 *
89 * Return: None
90 */
91 #define qdf_ptr_hash_declare(name, _bits) \
92 union { \
93 struct qdf_ptr_hash ht; \
94 uint8_t __raw[__qdf_ptr_hash_size(_bits)]; \
95 } __##name = { .ht = { .bits = _bits, .count = (1 << _bits) } }
96
97 /**
98 * qdf_ptr_hash_ptr() - get a pointer to a declared qdf_ptr_hash
99 * @name: the C identifier of the declared qdf_ptr_hash
100 *
101 * Return: pointer to a qdf_ptr_hash
102 */
103 #define qdf_ptr_hash_ptr(name) &__##name.ht
104
105 /**
106 * qdf_ptr_hash_declare_ptr() - declare a pointer to a new qdf_ptr_hash
107 * @name: the C identifier to use for the pointer to the new qdf_ptr_hash
108 * @bits: The number of bits to use for hashing
109 *
110 * Return: None
111 */
112 #define qdf_ptr_hash_declare_ptr(name, bits) \
113 qdf_ptr_hash_declare(name, bits); \
114 struct qdf_ptr_hash *name = qdf_ptr_hash_ptr(name)
115
116 #define __qdf_ptr_hash_for_each_bucket(ht, bkt) \
117 for ((bkt) = (ht)->buckets; \
118 (bkt) < (ht)->buckets + (ht)->count; \
119 (bkt)++)
120
121 /**
122 * qdf_ptr_hash_init() - initialize a qdf_ptr_hash
123 * @ht: the hash table to initialize
124 *
125 * Return: None
126 */
qdf_ptr_hash_init(struct qdf_ptr_hash * ht)127 static inline void qdf_ptr_hash_init(struct qdf_ptr_hash *ht)
128 {
129 struct qdf_ptr_hash_bucket *bucket;
130
131 __qdf_ptr_hash_for_each_bucket(ht, bucket)
132 qdf_slist_init(&bucket->list);
133 }
134
135 /**
136 * qdf_ptr_hash_deinit() - de-initialize a qdf_ptr_hash
137 * @ht: the hash table to de-initialize
138 *
139 * Return: None
140 */
qdf_ptr_hash_deinit(struct qdf_ptr_hash * ht)141 static inline void qdf_ptr_hash_deinit(struct qdf_ptr_hash *ht)
142 {
143 struct qdf_ptr_hash_bucket *bucket;
144
145 __qdf_ptr_hash_for_each_bucket(ht, bucket)
146 qdf_slist_deinit(&bucket->list);
147 }
148
149 /**
150 * qdf_ptr_hash_create() - allocate and initialize a qdf_ptr_hash
151 * @bits: the number of bits to use for hashing
152 *
153 * Return: qdf_ptr_hash pointer on success, NULL on allocation failure
154 */
qdf_ptr_hash_create(uint8_t bits)155 static inline struct qdf_ptr_hash *qdf_ptr_hash_create(uint8_t bits)
156 {
157 struct qdf_ptr_hash *ht = qdf_mem_malloc(__qdf_ptr_hash_size(bits));
158
159 if (!ht)
160 return NULL;
161
162 ht->bits = bits;
163 ht->count = 1 << bits;
164 qdf_ptr_hash_init(ht);
165
166 return ht;
167 }
168
169 /**
170 * qdf_ptr_hash_destroy() - de-initialize and de-allocate a qdf_ptr_hash
171 * @ht: the qdf_ptr_hash to destroy
172 *
173 * Return: None
174 */
qdf_ptr_hash_destroy(struct qdf_ptr_hash * ht)175 static inline void qdf_ptr_hash_destroy(struct qdf_ptr_hash *ht)
176 {
177 qdf_ptr_hash_deinit(ht);
178 qdf_mem_free(ht);
179 }
180
181 /**
182 * qdf_ptr_hash_empty() - check if a qdf_ptr_hash has any entries
183 * @ht: the qdf_ptr_hash to check
184 *
185 * Return: true if @ht contains no entries
186 */
qdf_ptr_hash_empty(struct qdf_ptr_hash * ht)187 static inline bool qdf_ptr_hash_empty(struct qdf_ptr_hash *ht)
188 {
189 struct qdf_ptr_hash_bucket *bucket;
190
191 __qdf_ptr_hash_for_each_bucket(ht, bucket)
192 if (!qdf_slist_empty(&bucket->list))
193 return false;
194
195 return true;
196 }
197
198 #ifdef ENABLE_QDF_PTR_HASH_DEBUG
199 /**
200 * qdf_ptr_hash_dup_check_in_bucket() - check if a hash_entry is duplicated
201 * in hash_bucket
202 * @bucket: qdf_ptr_hash_bucket pointer
203 * @cmp_entry: the hash_entry to be checked
204 *
205 * if the cmp_entry is found in bucket list, then trigger
206 * assert to report duplication.
207 *
208 * Return: None
209 */
qdf_ptr_hash_dup_check_in_bucket(struct qdf_ptr_hash_bucket * bucket,struct qdf_ptr_hash_entry * cmp_entry)210 static inline void qdf_ptr_hash_dup_check_in_bucket(
211 struct qdf_ptr_hash_bucket *bucket,
212 struct qdf_ptr_hash_entry *cmp_entry)
213 {
214 struct qdf_ptr_hash_entry *tmp_entry;
215
216 qdf_slist_for_each(&bucket->list, tmp_entry, node)
217 qdf_assert_always(tmp_entry != cmp_entry);
218 }
219 #else
220 #define qdf_ptr_hash_dup_check_in_bucket(_bucket, _cmp_entry) /* no op */
221 #endif
222
223 static inline struct qdf_ptr_hash_bucket *
__qdf_ptr_hash_get_bucket(struct qdf_ptr_hash * ht,uintptr_t key)224 __qdf_ptr_hash_get_bucket(struct qdf_ptr_hash *ht, uintptr_t key)
225 {
226 return ht->buckets + __qdf_ptr_hash_key(key, ht->bits);
227 }
228
229 /**
230 * qdf_ptr_hash_add() - insert an entry into a qdf_ptr_hash
231 * @ht: the qdf_ptr_hash to insert into
232 * @key: the pointer to use as an insertion/lookup key
233 * @item: a pointer to a type that contains a qdf_ptr_hash_entry
234 * @entry_field: C identifier for the qdf_ptr_hash_entry field in @item
235 *
236 * Return: None
237 */
238 #define qdf_ptr_hash_add(ht, key, item, entry_field) \
239 __qdf_ptr_hash_add(ht, (uintptr_t)key, &(item)->entry_field)
240
__qdf_ptr_hash_add(struct qdf_ptr_hash * ht,uintptr_t key,struct qdf_ptr_hash_entry * entry)241 static inline void __qdf_ptr_hash_add(struct qdf_ptr_hash *ht, uintptr_t key,
242 struct qdf_ptr_hash_entry *entry)
243 {
244 entry->key = key;
245 /* check hash_enrty exist or not before push */
246 qdf_ptr_hash_dup_check_in_bucket(__qdf_ptr_hash_get_bucket(ht, key),
247 entry);
248 qdf_slist_push(&__qdf_ptr_hash_get_bucket(ht, key)->list, entry, node);
249 }
250
251 /**
252 * qdf_ptr_hash_remove() - remove an entry from a qdf_ptr_hash
253 * @ht: the qdf_ptr_hash to remove from
254 * @key: the pointer to use as a lookup key
255 * @cursor: a pointer to a type that contains a qdf_ptr_hash_entry
256 * @entry_field: C identifier for the qdf_ptr_hash_entry field in @cursor
257 *
258 * Return: removed item of type @cursor on success, NULL otherwise
259 */
260 #define qdf_ptr_hash_remove(ht, key, cursor, entry_field) ({ \
261 struct qdf_ptr_hash_entry *_e = \
262 __qdf_ptr_hash_remove(ht, (uintptr_t)key); \
263 cursor = _e ? qdf_container_of(_e, typeof(*(cursor)), \
264 entry_field) : NULL; \
265 cursor; })
266
267 static inline struct qdf_ptr_hash_entry *
__qdf_ptr_hash_remove(struct qdf_ptr_hash * ht,uintptr_t key)268 __qdf_ptr_hash_remove(struct qdf_ptr_hash *ht, uintptr_t key)
269 {
270 struct qdf_ptr_hash_bucket *bucket = __qdf_ptr_hash_get_bucket(ht, key);
271 struct qdf_ptr_hash_entry *prev;
272 struct qdf_ptr_hash_entry *entry;
273
274 qdf_slist_for_each_del(&bucket->list, prev, entry, node) {
275 if (entry->key == key) {
276 qdf_slist_remove(&bucket->list, prev, node);
277 /* check hash_enrty exist or not after remove */
278 qdf_ptr_hash_dup_check_in_bucket(bucket, entry);
279 entry->key = 0;
280 return entry;
281 }
282 }
283
284 return NULL;
285 }
286
287 #define __qdf_ptr_hash_for_each_in_bucket(bucket, cursor, entry_field) \
288 qdf_slist_for_each(&(bucket)->list, cursor, entry_field.node)
289
290 /**
291 * qdf_ptr_hash_for_each() - qdf_ptr_hash item iterator for all items
292 * @ht: the qdf_ptr_hash to iterate over
293 * @bucket: qdf_ptr_hash_bucket cursor pointer
294 * @cursor: a pointer to a type that contains a qdf_ptr_hash_entry
295 * @entry_field: C identifier for the qdf_ptr_hash_entry field in @cursor
296 */
297 #define qdf_ptr_hash_for_each(ht, bucket, cursor, entry_field) \
298 __qdf_ptr_hash_for_each_bucket(ht, bucket) \
299 __qdf_ptr_hash_for_each_in_bucket(bucket, cursor, entry_field)
300
301 /**
302 * qdf_ptr_hash_for_each_by_hash() - qdf_ptr_hash item iterator for items which
303 * hash to the same value as @key
304 * @ht: the qdf_ptr_hash to iterate over
305 * @key: the pointer to use as a lookup key
306 * @cursor: a pointer to a type that contains a qdf_ptr_hash_entry
307 * @entry_field: C identifier for the qdf_ptr_hash_entry field in @cursor
308 */
309 #define qdf_ptr_hash_for_each_by_hash(ht, key, cursor, entry_field) \
310 __qdf_ptr_hash_for_each_in_bucket( \
311 __qdf_ptr_hash_get_bucket(ht, (uintptr_t)key), \
312 cursor, entry_field)
313
314 /**
315 * qdf_ptr_hash_for_each_by_key() - qdf_ptr_hash item iterator for items whose
316 * keys equal @_key
317 * @ht: the qdf_ptr_hash to iterate over
318 * @_key: the pointer to use as a lookup key
319 * @cursor: a pointer to a type that contains a qdf_ptr_hash_entry
320 * @entry_field: C identifier for the qdf_ptr_hash_entry field in @cursor
321 */
322 #define qdf_ptr_hash_for_each_by_key(ht, _key, cursor, entry_field) \
323 qdf_ptr_hash_for_each_by_hash(ht, _key, cursor, entry_field) \
324 if ((cursor)->entry_field.key == (uintptr_t)_key)
325
326 /**
327 * qdf_ptr_hash_get() - get the first item whose key matches @key
328 * @ht: the qdf_ptr_hash to look in
329 * @key: the pointer to use as a lookup key
330 * @cursor: a pointer to a type that contains a qdf_ptr_hash_entry
331 * @entry_field: C identifier for the qdf_ptr_hash_entry field in @cursor
332 *
333 * Return: first item matching @key of type @cursor on success, NULL otherwise
334 */
335 #define qdf_ptr_hash_get(ht, key, cursor, entry_field) ({ \
336 cursor = NULL; \
337 qdf_ptr_hash_for_each_by_key(ht, key, cursor, entry_field) \
338 break; \
339 cursor; })
340
341 #endif /* __QDF_PTR_HASH_H */
342
343