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 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 /** 204 * qdf_ptr_hash_add() - insert an entry into a qdf_ptr_hash 205 * @ht: the qdf_ptr_hash to insert into 206 * @key: the pointer to use as an insertion/lookup key 207 * @item: a pointer to a type that contains a qdf_ptr_hash_entry 208 * @entry_field: C identifier for the qdf_ptr_hash_entry field in @item 209 * 210 * Return: None 211 */ 212 #define qdf_ptr_hash_add(ht, key, item, entry_field) \ 213 __qdf_ptr_hash_add(ht, (uintptr_t)key, &(item)->entry_field) 214 215 static inline void __qdf_ptr_hash_add(struct qdf_ptr_hash *ht, uintptr_t key, 216 struct qdf_ptr_hash_entry *entry) 217 { 218 entry->key = key; 219 qdf_slist_push(&__qdf_ptr_hash_get_bucket(ht, key)->list, entry, node); 220 } 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 238 static inline struct qdf_ptr_hash_entry * 239 __qdf_ptr_hash_remove(struct qdf_ptr_hash *ht, uintptr_t key) 240 { 241 struct qdf_ptr_hash_bucket *bucket = __qdf_ptr_hash_get_bucket(ht, key); 242 struct qdf_ptr_hash_entry *prev; 243 struct qdf_ptr_hash_entry *entry; 244 245 qdf_slist_for_each_del(&bucket->list, prev, entry, node) { 246 if (entry->key == key) { 247 qdf_slist_remove(&bucket->list, prev, node); 248 entry->key = 0; 249 return entry; 250 } 251 } 252 253 return NULL; 254 } 255 256 #define __qdf_ptr_hash_for_each_in_bucket(bucket, cursor, entry_field) \ 257 qdf_slist_for_each(&(bucket)->list, cursor, entry_field.node) 258 259 /** 260 * qdf_ptr_hash_for_each() - qdf_ptr_hash item iterator for all items 261 * @ht: the qdf_ptr_hash to iterate over 262 * @bucket: qdf_ptr_hash_bucket cursor pointer 263 * @cursor: a pointer to a type that contains a qdf_ptr_hash_entry 264 * @entry_field: C identifier for the qdf_ptr_hash_entry field in @cursor 265 */ 266 #define qdf_ptr_hash_for_each(ht, bucket, cursor, entry_field) \ 267 __qdf_ptr_hash_for_each_bucket(ht, bucket) \ 268 __qdf_ptr_hash_for_each_in_bucket(bucket, cursor, entry_field) 269 270 /** 271 * qdf_ptr_hash_for_each_by_hash() - qdf_ptr_hash item iterator for items which 272 * hash to the same value as @key 273 * @ht: the qdf_ptr_hash to iterate over 274 * @key: the pointer to use as a lookup key 275 * @cursor: a pointer to a type that contains a qdf_ptr_hash_entry 276 * @entry_field: C identifier for the qdf_ptr_hash_entry field in @cursor 277 */ 278 #define qdf_ptr_hash_for_each_by_hash(ht, key, cursor, entry_field) \ 279 __qdf_ptr_hash_for_each_in_bucket( \ 280 __qdf_ptr_hash_get_bucket(ht, (uintptr_t)key), \ 281 cursor, entry_field) 282 283 /** 284 * qdf_ptr_hash_for_each_by_key() - qdf_ptr_hash item iterator for items whose 285 * keys equal @key 286 * @ht: the qdf_ptr_hash to iterate over 287 * @key: the pointer to use as a lookup key 288 * @cursor: a pointer to a type that contains a qdf_ptr_hash_entry 289 * @entry_field: C identifier for the qdf_ptr_hash_entry field in @cursor 290 */ 291 #define qdf_ptr_hash_for_each_by_key(ht, _key, cursor, entry_field) \ 292 qdf_ptr_hash_for_each_by_hash(ht, _key, cursor, entry_field) \ 293 if ((cursor)->entry_field.key == (uintptr_t)_key) 294 295 /** 296 * qdf_ptr_hash_get() - get the first item whose key matches @key 297 * @ht: the qdf_ptr_hash to look in 298 * @key: the pointer to use as a lookup key 299 * @cursor: a pointer to a type that contains a qdf_ptr_hash_entry 300 * @entry_field: C identifier for the qdf_ptr_hash_entry field in @cursor 301 * 302 * Return: first item matching @key of type @cursor on success, NULL otherwise 303 */ 304 #define qdf_ptr_hash_get(ht, key, cursor, entry_field) ({ \ 305 cursor = NULL; \ 306 qdf_ptr_hash_for_each_by_key(ht, key, cursor, entry_field) \ 307 break; \ 308 cursor; }) 309 310 #endif /* __QDF_PTR_HASH_H */ 311 312