qdf_ptr_hash.h 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342
  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. * DOC: qdf_ptr_hash.h
  21. *
  22. * A minimal hashtable implementation for doing fast lookups via pointer.
  23. *
  24. * qdf_ptr_hash also has the benefit of knowing its own size, allowing a pointer
  25. * to the hashtable to be passed around and embedded in other structs. Since
  26. * every hashtable is not necessarily of the same size, this allows using hash
  27. * tables in a lot of new places which would be impossible with the current
  28. * kernel hashtable implementation.
  29. *
  30. * Because the size of the hashtable varies with the number of bits used in the
  31. * hash, declaring a qdf_ptr_hash is a bit different. If you want to embed a
  32. * qdf_ptr_hash in another type, use a combination of qdf_ptr_hash_declare() and
  33. * qdf_ptr_hash_ptr(). If you just want to declare and use a qdf_ptr_hash, use
  34. * qdf_ptr_hash_declare_ptr() instead. Either method will ensure the appropriate
  35. * number of bytes is accounted for using an internal union, and provides the
  36. * consumer with a pointer to a qdf_ptr_hash type which can be used with all of
  37. * the other qdf_ptr_hash APIs. Alternatively, you can skip these complexities
  38. * by simply dynamically allocating the qdf_ptr_hash via qdf_ptr_hash_create().
  39. */
  40. #ifndef __QDF_PTR_HASH_H
  41. #define __QDF_PTR_HASH_H
  42. #include "i_qdf_ptr_hash.h"
  43. #include "qdf_mem.h"
  44. #include "qdf_slist.h"
  45. #include "qdf_types.h"
  46. #include "qdf_util.h"
  47. /**
  48. * struct qdf_ptr_hash_bucket - a type representing a hash bucket
  49. * @list: the list used for hash chaining
  50. */
  51. struct qdf_ptr_hash_bucket {
  52. struct qdf_slist list;
  53. };
  54. /**
  55. * struct qdf_ptr_hash - a hash table type for doing fast lookups via pointer
  56. * @bits: the number of bits to use when hashing keys
  57. * @count: the number of buckets, always equal to 2^@bits
  58. * @buckets: empty bucket array for accessing a variable length array of buckets
  59. */
  60. struct qdf_ptr_hash {
  61. int8_t bits;
  62. int16_t count;
  63. struct qdf_ptr_hash_bucket buckets[];
  64. };
  65. /**
  66. * struct qdf_ptr_hash_entry - entry type of membership in a qdf_ptr_hash
  67. * @key: the value used as the key for insertion/lookup
  68. * @node: the list node used for hash chaining
  69. */
  70. struct qdf_ptr_hash_entry {
  71. uintptr_t key;
  72. struct qdf_slist_node node;
  73. };
  74. #define __qdf_ptr_hash_size(bits) (sizeof(struct qdf_ptr_hash) + \
  75. sizeof(((struct qdf_ptr_hash *)0)->buckets[0]) * (1 << bits))
  76. /**
  77. * qdf_ptr_hash_declare() - declare a new qdf_ptr_hash
  78. * @name: the C identifier to use for the new hash table
  79. * @_bits: The number of bits to use for hashing
  80. *
  81. * Return: None
  82. */
  83. #define qdf_ptr_hash_declare(name, _bits) \
  84. union { \
  85. struct qdf_ptr_hash ht; \
  86. uint8_t __raw[__qdf_ptr_hash_size(_bits)]; \
  87. } __##name = { .ht = { .bits = _bits, .count = (1 << _bits) } }
  88. /**
  89. * qdf_ptr_hash_ptr() - get a pointer to a declared qdf_ptr_hash
  90. * @name: the C identifier of the declared qdf_ptr_hash
  91. *
  92. * Return: pointer to a qdf_ptr_hash
  93. */
  94. #define qdf_ptr_hash_ptr(name) &__##name.ht
  95. /**
  96. * qdf_ptr_hash_declare_ptr() - declare a pointer to a new qdf_ptr_hash
  97. * @name: the C identifier to use for the pointer to the new qdf_ptr_hash
  98. * @bits: The number of bits to use for hashing
  99. *
  100. * Return: None
  101. */
  102. #define qdf_ptr_hash_declare_ptr(name, bits) \
  103. qdf_ptr_hash_declare(name, bits); \
  104. struct qdf_ptr_hash *name = qdf_ptr_hash_ptr(name)
  105. #define __qdf_ptr_hash_for_each_bucket(ht, bkt) \
  106. for ((bkt) = (ht)->buckets; \
  107. (bkt) < (ht)->buckets + (ht)->count; \
  108. (bkt)++)
  109. /**
  110. * qdf_ptr_hash_init() - initialize a qdf_ptr_hash
  111. * @ht: the hash table to initialize
  112. *
  113. * Return: None
  114. */
  115. static inline void qdf_ptr_hash_init(struct qdf_ptr_hash *ht)
  116. {
  117. struct qdf_ptr_hash_bucket *bucket;
  118. __qdf_ptr_hash_for_each_bucket(ht, bucket)
  119. qdf_slist_init(&bucket->list);
  120. }
  121. /**
  122. * qdf_ptr_hash_deinit() - de-initialize a qdf_ptr_hash
  123. * @ht: the hash table to de-initialize
  124. *
  125. * Return: None
  126. */
  127. static inline void qdf_ptr_hash_deinit(struct qdf_ptr_hash *ht)
  128. {
  129. struct qdf_ptr_hash_bucket *bucket;
  130. __qdf_ptr_hash_for_each_bucket(ht, bucket)
  131. qdf_slist_deinit(&bucket->list);
  132. }
  133. /**
  134. * qdf_ptr_hash_create() - allocate and initialize a qdf_ptr_hash
  135. * @bits: the number of bits to use for hashing
  136. *
  137. * Return: qdf_ptr_hash pointer on success, NULL on allocation failure
  138. */
  139. static inline struct qdf_ptr_hash *qdf_ptr_hash_create(uint8_t bits)
  140. {
  141. struct qdf_ptr_hash *ht = qdf_mem_malloc(__qdf_ptr_hash_size(bits));
  142. if (!ht)
  143. return NULL;
  144. ht->bits = bits;
  145. ht->count = 1 << bits;
  146. qdf_ptr_hash_init(ht);
  147. return ht;
  148. }
  149. /**
  150. * qdf_ptr_hash_destroy() - de-initialize and de-allocate a qdf_ptr_hash
  151. * @ht: the qdf_ptr_hash to destroy
  152. *
  153. * Return: None
  154. */
  155. static inline void qdf_ptr_hash_destroy(struct qdf_ptr_hash *ht)
  156. {
  157. qdf_ptr_hash_deinit(ht);
  158. qdf_mem_free(ht);
  159. }
  160. /**
  161. * qdf_ptr_hash_empty() - check if a qdf_ptr_hash has any entries
  162. * @ht: the qdf_ptr_hash to check
  163. *
  164. * Return: true if @ht contains no entries
  165. */
  166. static inline bool qdf_ptr_hash_empty(struct qdf_ptr_hash *ht)
  167. {
  168. struct qdf_ptr_hash_bucket *bucket;
  169. __qdf_ptr_hash_for_each_bucket(ht, bucket)
  170. if (!qdf_slist_empty(&bucket->list))
  171. return false;
  172. return true;
  173. }
  174. #ifdef ENABLE_QDF_PTR_HASH_DEBUG
  175. /**
  176. * qdf_ptr_hash_dup_check_in_bucket() - check if a hash_entry is duplicated
  177. * in hash_bucket
  178. * @bucket: qdf_ptr_hash_bucket pointer
  179. * @cmp_entry: the hash_entry to be checked
  180. *
  181. * if the cmp_entry is found in bucket list, then trigger
  182. * assert to report duplication.
  183. *
  184. * Return: None
  185. */
  186. static inline void qdf_ptr_hash_dup_check_in_bucket(
  187. struct qdf_ptr_hash_bucket *bucket,
  188. struct qdf_ptr_hash_entry *cmp_entry)
  189. {
  190. struct qdf_ptr_hash_entry *tmp_entry;
  191. qdf_slist_for_each(&bucket->list, tmp_entry, node)
  192. qdf_assert_always(tmp_entry != cmp_entry);
  193. }
  194. #else
  195. #define qdf_ptr_hash_dup_check_in_bucket(_bucket, _cmp_entry) /* no op */
  196. #endif
  197. static inline struct qdf_ptr_hash_bucket *
  198. __qdf_ptr_hash_get_bucket(struct qdf_ptr_hash *ht, uintptr_t key)
  199. {
  200. return ht->buckets + __qdf_ptr_hash_key(key, ht->bits);
  201. }
  202. /**
  203. * qdf_ptr_hash_add() - insert an entry into a qdf_ptr_hash
  204. * @ht: the qdf_ptr_hash to insert into
  205. * @key: the pointer to use as an insertion/lookup key
  206. * @item: a pointer to a type that contains a qdf_ptr_hash_entry
  207. * @entry_field: C identifier for the qdf_ptr_hash_entry field in @item
  208. *
  209. * Return: None
  210. */
  211. #define qdf_ptr_hash_add(ht, key, item, entry_field) \
  212. __qdf_ptr_hash_add(ht, (uintptr_t)key, &(item)->entry_field)
  213. static inline void __qdf_ptr_hash_add(struct qdf_ptr_hash *ht, uintptr_t key,
  214. struct qdf_ptr_hash_entry *entry)
  215. {
  216. entry->key = key;
  217. /* check hash_enrty exist or not before push */
  218. qdf_ptr_hash_dup_check_in_bucket(__qdf_ptr_hash_get_bucket(ht, key),
  219. entry);
  220. qdf_slist_push(&__qdf_ptr_hash_get_bucket(ht, key)->list, entry, node);
  221. }
  222. /**
  223. * qdf_ptr_hash_remove() - remove an entry from a qdf_ptr_hash
  224. * @ht: the qdf_ptr_hash to remove from
  225. * @key: the pointer to use as a lookup key
  226. * @cursor: a pointer to a type that contains a qdf_ptr_hash_entry
  227. * @entry_field: C identifier for the qdf_ptr_hash_entry field in @cursor
  228. *
  229. * Return: removed item of type @cursor on success, NULL otherwise
  230. */
  231. #define qdf_ptr_hash_remove(ht, key, cursor, entry_field) ({ \
  232. struct qdf_ptr_hash_entry *_e = \
  233. __qdf_ptr_hash_remove(ht, (uintptr_t)key); \
  234. cursor = _e ? qdf_container_of(_e, typeof(*(cursor)), \
  235. entry_field) : NULL; \
  236. cursor; })
  237. static inline struct qdf_ptr_hash_entry *
  238. __qdf_ptr_hash_remove(struct qdf_ptr_hash *ht, uintptr_t key)
  239. {
  240. struct qdf_ptr_hash_bucket *bucket = __qdf_ptr_hash_get_bucket(ht, key);
  241. struct qdf_ptr_hash_entry *prev;
  242. struct qdf_ptr_hash_entry *entry;
  243. qdf_slist_for_each_del(&bucket->list, prev, entry, node) {
  244. if (entry->key == key) {
  245. qdf_slist_remove(&bucket->list, prev, node);
  246. /* check hash_enrty exist or not after remove */
  247. qdf_ptr_hash_dup_check_in_bucket(bucket, entry);
  248. entry->key = 0;
  249. return entry;
  250. }
  251. }
  252. return NULL;
  253. }
  254. #define __qdf_ptr_hash_for_each_in_bucket(bucket, cursor, entry_field) \
  255. qdf_slist_for_each(&(bucket)->list, cursor, entry_field.node)
  256. /**
  257. * qdf_ptr_hash_for_each() - qdf_ptr_hash item iterator for all items
  258. * @ht: the qdf_ptr_hash to iterate over
  259. * @bucket: qdf_ptr_hash_bucket cursor pointer
  260. * @cursor: a pointer to a type that contains a qdf_ptr_hash_entry
  261. * @entry_field: C identifier for the qdf_ptr_hash_entry field in @cursor
  262. */
  263. #define qdf_ptr_hash_for_each(ht, bucket, cursor, entry_field) \
  264. __qdf_ptr_hash_for_each_bucket(ht, bucket) \
  265. __qdf_ptr_hash_for_each_in_bucket(bucket, cursor, entry_field)
  266. /**
  267. * qdf_ptr_hash_for_each_by_hash() - qdf_ptr_hash item iterator for items which
  268. * hash to the same value as @key
  269. * @ht: the qdf_ptr_hash to iterate over
  270. * @key: the pointer to use as a lookup key
  271. * @cursor: a pointer to a type that contains a qdf_ptr_hash_entry
  272. * @entry_field: C identifier for the qdf_ptr_hash_entry field in @cursor
  273. */
  274. #define qdf_ptr_hash_for_each_by_hash(ht, key, cursor, entry_field) \
  275. __qdf_ptr_hash_for_each_in_bucket( \
  276. __qdf_ptr_hash_get_bucket(ht, (uintptr_t)key), \
  277. cursor, entry_field)
  278. /**
  279. * qdf_ptr_hash_for_each_by_key() - qdf_ptr_hash item iterator for items whose
  280. * keys equal @_key
  281. * @ht: the qdf_ptr_hash to iterate over
  282. * @_key: the pointer to use as a lookup key
  283. * @cursor: a pointer to a type that contains a qdf_ptr_hash_entry
  284. * @entry_field: C identifier for the qdf_ptr_hash_entry field in @cursor
  285. */
  286. #define qdf_ptr_hash_for_each_by_key(ht, _key, cursor, entry_field) \
  287. qdf_ptr_hash_for_each_by_hash(ht, _key, cursor, entry_field) \
  288. if ((cursor)->entry_field.key == (uintptr_t)_key)
  289. /**
  290. * qdf_ptr_hash_get() - get the first item whose key matches @key
  291. * @ht: the qdf_ptr_hash to look in
  292. * @key: the pointer to use as a lookup key
  293. * @cursor: a pointer to a type that contains a qdf_ptr_hash_entry
  294. * @entry_field: C identifier for the qdf_ptr_hash_entry field in @cursor
  295. *
  296. * Return: first item matching @key of type @cursor on success, NULL otherwise
  297. */
  298. #define qdf_ptr_hash_get(ht, key, cursor, entry_field) ({ \
  299. cursor = NULL; \
  300. qdf_ptr_hash_for_each_by_key(ht, key, cursor, entry_field) \
  301. break; \
  302. cursor; })
  303. #endif /* __QDF_PTR_HASH_H */