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