16577bea1SDustin Brown /* 26577bea1SDustin Brown * Copyright (c) 2019 The Linux Foundation. All rights reserved. 3*319d2073SAditya Kodukula * Copyright (c) 2022-2024 Qualcomm Innovation Center, Inc. All rights reserved. 46577bea1SDustin Brown * 56577bea1SDustin Brown * Permission to use, copy, modify, and/or distribute this software for 66577bea1SDustin Brown * any purpose with or without fee is hereby granted, provided that the 76577bea1SDustin Brown * above copyright notice and this permission notice appear in all 86577bea1SDustin Brown * copies. 96577bea1SDustin Brown * 106577bea1SDustin Brown * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL 116577bea1SDustin Brown * WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED 126577bea1SDustin Brown * WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE 136577bea1SDustin Brown * AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL 146577bea1SDustin Brown * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR 156577bea1SDustin Brown * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER 166577bea1SDustin Brown * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 176577bea1SDustin Brown * PERFORMANCE OF THIS SOFTWARE. 186577bea1SDustin Brown */ 196577bea1SDustin Brown 206577bea1SDustin Brown /** 216577bea1SDustin Brown * DOC: qdf_ptr_hash.h 226577bea1SDustin Brown * 236577bea1SDustin Brown * A minimal hashtable implementation for doing fast lookups via pointer. 246577bea1SDustin Brown * 256577bea1SDustin Brown * qdf_ptr_hash also has the benefit of knowing its own size, allowing a pointer 266577bea1SDustin Brown * to the hashtable to be passed around and embedded in other structs. Since 276577bea1SDustin Brown * every hashtable is not necessarily of the same size, this allows using hash 286577bea1SDustin Brown * tables in a lot of new places which would be impossible with the current 296577bea1SDustin Brown * kernel hashtable implementation. 306577bea1SDustin Brown * 316577bea1SDustin Brown * Because the size of the hashtable varies with the number of bits used in the 326577bea1SDustin Brown * hash, declaring a qdf_ptr_hash is a bit different. If you want to embed a 336577bea1SDustin Brown * qdf_ptr_hash in another type, use a combination of qdf_ptr_hash_declare() and 346577bea1SDustin Brown * qdf_ptr_hash_ptr(). If you just want to declare and use a qdf_ptr_hash, use 356577bea1SDustin Brown * qdf_ptr_hash_declare_ptr() instead. Either method will ensure the appropriate 366577bea1SDustin Brown * number of bytes is accounted for using an internal union, and provides the 376577bea1SDustin Brown * consumer with a pointer to a qdf_ptr_hash type which can be used with all of 386577bea1SDustin Brown * the other qdf_ptr_hash APIs. Alternatively, you can skip these complexities 396577bea1SDustin Brown * by simply dynamically allocating the qdf_ptr_hash via qdf_ptr_hash_create(). 406577bea1SDustin Brown */ 416577bea1SDustin Brown 426577bea1SDustin Brown #ifndef __QDF_PTR_HASH_H 436577bea1SDustin Brown #define __QDF_PTR_HASH_H 446577bea1SDustin Brown 456577bea1SDustin Brown #include "i_qdf_ptr_hash.h" 466577bea1SDustin Brown #include "qdf_mem.h" 476577bea1SDustin Brown #include "qdf_slist.h" 486577bea1SDustin Brown #include "qdf_types.h" 496577bea1SDustin Brown #include "qdf_util.h" 506577bea1SDustin Brown 516577bea1SDustin Brown /** 526577bea1SDustin Brown * struct qdf_ptr_hash_bucket - a type representing a hash bucket 536577bea1SDustin Brown * @list: the list used for hash chaining 546577bea1SDustin Brown */ 556577bea1SDustin Brown struct qdf_ptr_hash_bucket { 566577bea1SDustin Brown struct qdf_slist list; 576577bea1SDustin Brown }; 586577bea1SDustin Brown 596577bea1SDustin Brown /** 606577bea1SDustin Brown * struct qdf_ptr_hash - a hash table type for doing fast lookups via pointer 616577bea1SDustin Brown * @bits: the number of bits to use when hashing keys 626577bea1SDustin Brown * @count: the number of buckets, always equal to 2^@bits 636577bea1SDustin Brown * @buckets: empty bucket array for accessing a variable length array of buckets 646577bea1SDustin Brown */ 656577bea1SDustin Brown struct qdf_ptr_hash { 666577bea1SDustin Brown int8_t bits; 676577bea1SDustin Brown int16_t count; 68*319d2073SAditya Kodukula struct qdf_ptr_hash_bucket buckets[]; 696577bea1SDustin Brown }; 706577bea1SDustin Brown 716577bea1SDustin Brown /** 726577bea1SDustin Brown * struct qdf_ptr_hash_entry - entry type of membership in a qdf_ptr_hash 736577bea1SDustin Brown * @key: the value used as the key for insertion/lookup 746577bea1SDustin Brown * @node: the list node used for hash chaining 756577bea1SDustin Brown */ 766577bea1SDustin Brown struct qdf_ptr_hash_entry { 776577bea1SDustin Brown uintptr_t key; 786577bea1SDustin Brown struct qdf_slist_node node; 796577bea1SDustin Brown }; 806577bea1SDustin Brown 816577bea1SDustin Brown #define __qdf_ptr_hash_size(bits) (sizeof(struct qdf_ptr_hash) + \ 826577bea1SDustin Brown sizeof(((struct qdf_ptr_hash *)0)->buckets[0]) * (1 << bits)) 836577bea1SDustin Brown 846577bea1SDustin Brown /** 856577bea1SDustin Brown * qdf_ptr_hash_declare() - declare a new qdf_ptr_hash 866577bea1SDustin Brown * @name: the C identifier to use for the new hash table 874042de59SJeff Johnson * @_bits: The number of bits to use for hashing 886577bea1SDustin Brown * 896577bea1SDustin Brown * Return: None 906577bea1SDustin Brown */ 916577bea1SDustin Brown #define qdf_ptr_hash_declare(name, _bits) \ 926577bea1SDustin Brown union { \ 936577bea1SDustin Brown struct qdf_ptr_hash ht; \ 946577bea1SDustin Brown uint8_t __raw[__qdf_ptr_hash_size(_bits)]; \ 956577bea1SDustin Brown } __##name = { .ht = { .bits = _bits, .count = (1 << _bits) } } 966577bea1SDustin Brown 976577bea1SDustin Brown /** 986577bea1SDustin Brown * qdf_ptr_hash_ptr() - get a pointer to a declared qdf_ptr_hash 996577bea1SDustin Brown * @name: the C identifier of the declared qdf_ptr_hash 1006577bea1SDustin Brown * 1016577bea1SDustin Brown * Return: pointer to a qdf_ptr_hash 1026577bea1SDustin Brown */ 1036577bea1SDustin Brown #define qdf_ptr_hash_ptr(name) &__##name.ht 1046577bea1SDustin Brown 1056577bea1SDustin Brown /** 1066577bea1SDustin Brown * qdf_ptr_hash_declare_ptr() - declare a pointer to a new qdf_ptr_hash 1076577bea1SDustin Brown * @name: the C identifier to use for the pointer to the new qdf_ptr_hash 1086577bea1SDustin Brown * @bits: The number of bits to use for hashing 1096577bea1SDustin Brown * 1106577bea1SDustin Brown * Return: None 1116577bea1SDustin Brown */ 1126577bea1SDustin Brown #define qdf_ptr_hash_declare_ptr(name, bits) \ 1136577bea1SDustin Brown qdf_ptr_hash_declare(name, bits); \ 1146577bea1SDustin Brown struct qdf_ptr_hash *name = qdf_ptr_hash_ptr(name) 1156577bea1SDustin Brown 1166577bea1SDustin Brown #define __qdf_ptr_hash_for_each_bucket(ht, bkt) \ 1176577bea1SDustin Brown for ((bkt) = (ht)->buckets; \ 1186577bea1SDustin Brown (bkt) < (ht)->buckets + (ht)->count; \ 1196577bea1SDustin Brown (bkt)++) 1206577bea1SDustin Brown 1216577bea1SDustin Brown /** 1226577bea1SDustin Brown * qdf_ptr_hash_init() - initialize a qdf_ptr_hash 1236577bea1SDustin Brown * @ht: the hash table to initialize 1246577bea1SDustin Brown * 1256577bea1SDustin Brown * Return: None 1266577bea1SDustin Brown */ 1276577bea1SDustin Brown static inline void qdf_ptr_hash_init(struct qdf_ptr_hash *ht) 1286577bea1SDustin Brown { 1296577bea1SDustin Brown struct qdf_ptr_hash_bucket *bucket; 1306577bea1SDustin Brown 1316577bea1SDustin Brown __qdf_ptr_hash_for_each_bucket(ht, bucket) 1326577bea1SDustin Brown qdf_slist_init(&bucket->list); 1336577bea1SDustin Brown } 1346577bea1SDustin Brown 1356577bea1SDustin Brown /** 1366577bea1SDustin Brown * qdf_ptr_hash_deinit() - de-initialize a qdf_ptr_hash 1376577bea1SDustin Brown * @ht: the hash table to de-initialize 1386577bea1SDustin Brown * 1396577bea1SDustin Brown * Return: None 1406577bea1SDustin Brown */ 1416577bea1SDustin Brown static inline void qdf_ptr_hash_deinit(struct qdf_ptr_hash *ht) 1426577bea1SDustin Brown { 1436577bea1SDustin Brown struct qdf_ptr_hash_bucket *bucket; 1446577bea1SDustin Brown 1456577bea1SDustin Brown __qdf_ptr_hash_for_each_bucket(ht, bucket) 1466577bea1SDustin Brown qdf_slist_deinit(&bucket->list); 1476577bea1SDustin Brown } 1486577bea1SDustin Brown 1496577bea1SDustin Brown /** 1506577bea1SDustin Brown * qdf_ptr_hash_create() - allocate and initialize a qdf_ptr_hash 1516577bea1SDustin Brown * @bits: the number of bits to use for hashing 1526577bea1SDustin Brown * 1533bdf954aSJeff Johnson * Return: qdf_ptr_hash pointer on success, NULL on allocation failure 1546577bea1SDustin Brown */ 1556577bea1SDustin Brown static inline struct qdf_ptr_hash *qdf_ptr_hash_create(uint8_t bits) 1566577bea1SDustin Brown { 1576577bea1SDustin Brown struct qdf_ptr_hash *ht = qdf_mem_malloc(__qdf_ptr_hash_size(bits)); 1586577bea1SDustin Brown 1596577bea1SDustin Brown if (!ht) 1606577bea1SDustin Brown return NULL; 1616577bea1SDustin Brown 1626577bea1SDustin Brown ht->bits = bits; 1636577bea1SDustin Brown ht->count = 1 << bits; 1646577bea1SDustin Brown qdf_ptr_hash_init(ht); 1656577bea1SDustin Brown 1666577bea1SDustin Brown return ht; 1676577bea1SDustin Brown } 1686577bea1SDustin Brown 1696577bea1SDustin Brown /** 1706577bea1SDustin Brown * qdf_ptr_hash_destroy() - de-initialize and de-allocate a qdf_ptr_hash 1716577bea1SDustin Brown * @ht: the qdf_ptr_hash to destroy 1726577bea1SDustin Brown * 1736577bea1SDustin Brown * Return: None 1746577bea1SDustin Brown */ 1756577bea1SDustin Brown static inline void qdf_ptr_hash_destroy(struct qdf_ptr_hash *ht) 1766577bea1SDustin Brown { 1776577bea1SDustin Brown qdf_ptr_hash_deinit(ht); 1786577bea1SDustin Brown qdf_mem_free(ht); 1796577bea1SDustin Brown } 1806577bea1SDustin Brown 1816577bea1SDustin Brown /** 1826577bea1SDustin Brown * qdf_ptr_hash_empty() - check if a qdf_ptr_hash has any entries 1836577bea1SDustin Brown * @ht: the qdf_ptr_hash to check 1846577bea1SDustin Brown * 1856577bea1SDustin Brown * Return: true if @ht contains no entries 1866577bea1SDustin Brown */ 1876577bea1SDustin Brown static inline bool qdf_ptr_hash_empty(struct qdf_ptr_hash *ht) 1886577bea1SDustin Brown { 1896577bea1SDustin Brown struct qdf_ptr_hash_bucket *bucket; 1906577bea1SDustin Brown 1916577bea1SDustin Brown __qdf_ptr_hash_for_each_bucket(ht, bucket) 1926577bea1SDustin Brown if (!qdf_slist_empty(&bucket->list)) 1936577bea1SDustin Brown return false; 1946577bea1SDustin Brown 1956577bea1SDustin Brown return true; 1966577bea1SDustin Brown } 1976577bea1SDustin Brown 19808de3a02SJinwei Chen #ifdef ENABLE_QDF_PTR_HASH_DEBUG 19908de3a02SJinwei Chen /** 20008de3a02SJinwei Chen * qdf_ptr_hash_dup_check_in_bucket() - check if a hash_entry is duplicated 2014042de59SJeff Johnson * in hash_bucket 20208de3a02SJinwei Chen * @bucket: qdf_ptr_hash_bucket pointer 2034042de59SJeff Johnson * @cmp_entry: the hash_entry to be checked 20408de3a02SJinwei Chen * 20508de3a02SJinwei Chen * if the cmp_entry is found in bucket list, then trigger 20608de3a02SJinwei Chen * assert to report duplication. 20708de3a02SJinwei Chen * 20808de3a02SJinwei Chen * Return: None 20908de3a02SJinwei Chen */ 21008de3a02SJinwei Chen static inline void qdf_ptr_hash_dup_check_in_bucket( 21108de3a02SJinwei Chen struct qdf_ptr_hash_bucket *bucket, 21208de3a02SJinwei Chen struct qdf_ptr_hash_entry *cmp_entry) 21308de3a02SJinwei Chen { 21408de3a02SJinwei Chen struct qdf_ptr_hash_entry *tmp_entry; 21508de3a02SJinwei Chen 21608de3a02SJinwei Chen qdf_slist_for_each(&bucket->list, tmp_entry, node) 21708de3a02SJinwei Chen qdf_assert_always(tmp_entry != cmp_entry); 21808de3a02SJinwei Chen } 21908de3a02SJinwei Chen #else 22008de3a02SJinwei Chen #define qdf_ptr_hash_dup_check_in_bucket(_bucket, _cmp_entry) /* no op */ 22108de3a02SJinwei Chen #endif 22208de3a02SJinwei Chen 2236577bea1SDustin Brown static inline struct qdf_ptr_hash_bucket * 2246577bea1SDustin Brown __qdf_ptr_hash_get_bucket(struct qdf_ptr_hash *ht, uintptr_t key) 2256577bea1SDustin Brown { 2266577bea1SDustin Brown return ht->buckets + __qdf_ptr_hash_key(key, ht->bits); 2276577bea1SDustin Brown } 2286577bea1SDustin Brown 2296577bea1SDustin Brown /** 2306577bea1SDustin Brown * qdf_ptr_hash_add() - insert an entry into a qdf_ptr_hash 2316577bea1SDustin Brown * @ht: the qdf_ptr_hash to insert into 2326577bea1SDustin Brown * @key: the pointer to use as an insertion/lookup key 2336577bea1SDustin Brown * @item: a pointer to a type that contains a qdf_ptr_hash_entry 2346577bea1SDustin Brown * @entry_field: C identifier for the qdf_ptr_hash_entry field in @item 2356577bea1SDustin Brown * 2366577bea1SDustin Brown * Return: None 2376577bea1SDustin Brown */ 2386577bea1SDustin Brown #define qdf_ptr_hash_add(ht, key, item, entry_field) \ 2396577bea1SDustin Brown __qdf_ptr_hash_add(ht, (uintptr_t)key, &(item)->entry_field) 2406577bea1SDustin Brown 2416577bea1SDustin Brown static inline void __qdf_ptr_hash_add(struct qdf_ptr_hash *ht, uintptr_t key, 2426577bea1SDustin Brown struct qdf_ptr_hash_entry *entry) 2436577bea1SDustin Brown { 2446577bea1SDustin Brown entry->key = key; 24508de3a02SJinwei Chen /* check hash_enrty exist or not before push */ 24608de3a02SJinwei Chen qdf_ptr_hash_dup_check_in_bucket(__qdf_ptr_hash_get_bucket(ht, key), 24708de3a02SJinwei Chen entry); 2486577bea1SDustin Brown qdf_slist_push(&__qdf_ptr_hash_get_bucket(ht, key)->list, entry, node); 2496577bea1SDustin Brown } 2506577bea1SDustin Brown 2516577bea1SDustin Brown /** 2526577bea1SDustin Brown * qdf_ptr_hash_remove() - remove an entry from a qdf_ptr_hash 2536577bea1SDustin Brown * @ht: the qdf_ptr_hash to remove from 2546577bea1SDustin Brown * @key: the pointer to use as a lookup key 2556577bea1SDustin Brown * @cursor: a pointer to a type that contains a qdf_ptr_hash_entry 2566577bea1SDustin Brown * @entry_field: C identifier for the qdf_ptr_hash_entry field in @cursor 2576577bea1SDustin Brown * 2586577bea1SDustin Brown * Return: removed item of type @cursor on success, NULL otherwise 2596577bea1SDustin Brown */ 2606577bea1SDustin Brown #define qdf_ptr_hash_remove(ht, key, cursor, entry_field) ({ \ 2616577bea1SDustin Brown struct qdf_ptr_hash_entry *_e = \ 2626577bea1SDustin Brown __qdf_ptr_hash_remove(ht, (uintptr_t)key); \ 2636577bea1SDustin Brown cursor = _e ? qdf_container_of(_e, typeof(*(cursor)), \ 2646577bea1SDustin Brown entry_field) : NULL; \ 2656577bea1SDustin Brown cursor; }) 2666577bea1SDustin Brown 2676577bea1SDustin Brown static inline struct qdf_ptr_hash_entry * 2686577bea1SDustin Brown __qdf_ptr_hash_remove(struct qdf_ptr_hash *ht, uintptr_t key) 2696577bea1SDustin Brown { 2706577bea1SDustin Brown struct qdf_ptr_hash_bucket *bucket = __qdf_ptr_hash_get_bucket(ht, key); 2716577bea1SDustin Brown struct qdf_ptr_hash_entry *prev; 2726577bea1SDustin Brown struct qdf_ptr_hash_entry *entry; 2736577bea1SDustin Brown 2746577bea1SDustin Brown qdf_slist_for_each_del(&bucket->list, prev, entry, node) { 2756577bea1SDustin Brown if (entry->key == key) { 2766577bea1SDustin Brown qdf_slist_remove(&bucket->list, prev, node); 27708de3a02SJinwei Chen /* check hash_enrty exist or not after remove */ 27808de3a02SJinwei Chen qdf_ptr_hash_dup_check_in_bucket(bucket, entry); 2796577bea1SDustin Brown entry->key = 0; 2806577bea1SDustin Brown return entry; 2816577bea1SDustin Brown } 2826577bea1SDustin Brown } 2836577bea1SDustin Brown 2846577bea1SDustin Brown return NULL; 2856577bea1SDustin Brown } 2866577bea1SDustin Brown 2876577bea1SDustin Brown #define __qdf_ptr_hash_for_each_in_bucket(bucket, cursor, entry_field) \ 2886577bea1SDustin Brown qdf_slist_for_each(&(bucket)->list, cursor, entry_field.node) 2896577bea1SDustin Brown 2906577bea1SDustin Brown /** 2916577bea1SDustin Brown * qdf_ptr_hash_for_each() - qdf_ptr_hash item iterator for all items 2926577bea1SDustin Brown * @ht: the qdf_ptr_hash to iterate over 2936577bea1SDustin Brown * @bucket: qdf_ptr_hash_bucket cursor pointer 2946577bea1SDustin Brown * @cursor: a pointer to a type that contains a qdf_ptr_hash_entry 2956577bea1SDustin Brown * @entry_field: C identifier for the qdf_ptr_hash_entry field in @cursor 2966577bea1SDustin Brown */ 2976577bea1SDustin Brown #define qdf_ptr_hash_for_each(ht, bucket, cursor, entry_field) \ 2986577bea1SDustin Brown __qdf_ptr_hash_for_each_bucket(ht, bucket) \ 2996577bea1SDustin Brown __qdf_ptr_hash_for_each_in_bucket(bucket, cursor, entry_field) 3006577bea1SDustin Brown 3016577bea1SDustin Brown /** 3026577bea1SDustin Brown * qdf_ptr_hash_for_each_by_hash() - qdf_ptr_hash item iterator for items which 3036577bea1SDustin Brown * hash to the same value as @key 3046577bea1SDustin Brown * @ht: the qdf_ptr_hash to iterate over 3056577bea1SDustin Brown * @key: the pointer to use as a lookup key 3066577bea1SDustin Brown * @cursor: a pointer to a type that contains a qdf_ptr_hash_entry 3076577bea1SDustin Brown * @entry_field: C identifier for the qdf_ptr_hash_entry field in @cursor 3086577bea1SDustin Brown */ 3096577bea1SDustin Brown #define qdf_ptr_hash_for_each_by_hash(ht, key, cursor, entry_field) \ 3106577bea1SDustin Brown __qdf_ptr_hash_for_each_in_bucket( \ 3116577bea1SDustin Brown __qdf_ptr_hash_get_bucket(ht, (uintptr_t)key), \ 3126577bea1SDustin Brown cursor, entry_field) 3136577bea1SDustin Brown 3146577bea1SDustin Brown /** 3156577bea1SDustin Brown * qdf_ptr_hash_for_each_by_key() - qdf_ptr_hash item iterator for items whose 3164042de59SJeff Johnson * keys equal @_key 3176577bea1SDustin Brown * @ht: the qdf_ptr_hash to iterate over 3184042de59SJeff Johnson * @_key: the pointer to use as a lookup key 3196577bea1SDustin Brown * @cursor: a pointer to a type that contains a qdf_ptr_hash_entry 3206577bea1SDustin Brown * @entry_field: C identifier for the qdf_ptr_hash_entry field in @cursor 3216577bea1SDustin Brown */ 3226577bea1SDustin Brown #define qdf_ptr_hash_for_each_by_key(ht, _key, cursor, entry_field) \ 3236577bea1SDustin Brown qdf_ptr_hash_for_each_by_hash(ht, _key, cursor, entry_field) \ 3246577bea1SDustin Brown if ((cursor)->entry_field.key == (uintptr_t)_key) 3256577bea1SDustin Brown 3266577bea1SDustin Brown /** 3276577bea1SDustin Brown * qdf_ptr_hash_get() - get the first item whose key matches @key 3286577bea1SDustin Brown * @ht: the qdf_ptr_hash to look in 3296577bea1SDustin Brown * @key: the pointer to use as a lookup key 3306577bea1SDustin Brown * @cursor: a pointer to a type that contains a qdf_ptr_hash_entry 3316577bea1SDustin Brown * @entry_field: C identifier for the qdf_ptr_hash_entry field in @cursor 3326577bea1SDustin Brown * 3336577bea1SDustin Brown * Return: first item matching @key of type @cursor on success, NULL otherwise 3346577bea1SDustin Brown */ 3356577bea1SDustin Brown #define qdf_ptr_hash_get(ht, key, cursor, entry_field) ({ \ 3366577bea1SDustin Brown cursor = NULL; \ 3376577bea1SDustin Brown qdf_ptr_hash_for_each_by_key(ht, key, cursor, entry_field) \ 3386577bea1SDustin Brown break; \ 3396577bea1SDustin Brown cursor; }) 3406577bea1SDustin Brown 3416577bea1SDustin Brown #endif /* __QDF_PTR_HASH_H */ 3426577bea1SDustin Brown 343