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