123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342 |
- #ifndef __QDF_PTR_HASH_H
- #define __QDF_PTR_HASH_H
- #include "i_qdf_ptr_hash.h"
- #include "qdf_mem.h"
- #include "qdf_slist.h"
- #include "qdf_types.h"
- #include "qdf_util.h"
- struct qdf_ptr_hash_bucket {
- struct qdf_slist list;
- };
- struct qdf_ptr_hash {
- int8_t bits;
- int16_t count;
- struct qdf_ptr_hash_bucket buckets[];
- };
- struct qdf_ptr_hash_entry {
- uintptr_t key;
- struct qdf_slist_node node;
- };
- #define __qdf_ptr_hash_size(bits) (sizeof(struct qdf_ptr_hash) + \
- sizeof(((struct qdf_ptr_hash *)0)->buckets[0]) * (1 << bits))
- #define qdf_ptr_hash_declare(name, _bits) \
- union { \
- struct qdf_ptr_hash ht; \
- uint8_t __raw[__qdf_ptr_hash_size(_bits)]; \
- } __##name = { .ht = { .bits = _bits, .count = (1 << _bits) } }
- #define qdf_ptr_hash_ptr(name) &__##name.ht
- #define qdf_ptr_hash_declare_ptr(name, bits) \
- qdf_ptr_hash_declare(name, bits); \
- struct qdf_ptr_hash *name = qdf_ptr_hash_ptr(name)
- #define __qdf_ptr_hash_for_each_bucket(ht, bkt) \
- for ((bkt) = (ht)->buckets; \
- (bkt) < (ht)->buckets + (ht)->count; \
- (bkt)++)
- static inline void qdf_ptr_hash_init(struct qdf_ptr_hash *ht)
- {
- struct qdf_ptr_hash_bucket *bucket;
- __qdf_ptr_hash_for_each_bucket(ht, bucket)
- qdf_slist_init(&bucket->list);
- }
- static inline void qdf_ptr_hash_deinit(struct qdf_ptr_hash *ht)
- {
- struct qdf_ptr_hash_bucket *bucket;
- __qdf_ptr_hash_for_each_bucket(ht, bucket)
- qdf_slist_deinit(&bucket->list);
- }
- static inline struct qdf_ptr_hash *qdf_ptr_hash_create(uint8_t bits)
- {
- struct qdf_ptr_hash *ht = qdf_mem_malloc(__qdf_ptr_hash_size(bits));
- if (!ht)
- return NULL;
- ht->bits = bits;
- ht->count = 1 << bits;
- qdf_ptr_hash_init(ht);
- return ht;
- }
- static inline void qdf_ptr_hash_destroy(struct qdf_ptr_hash *ht)
- {
- qdf_ptr_hash_deinit(ht);
- qdf_mem_free(ht);
- }
- static inline bool qdf_ptr_hash_empty(struct qdf_ptr_hash *ht)
- {
- struct qdf_ptr_hash_bucket *bucket;
- __qdf_ptr_hash_for_each_bucket(ht, bucket)
- if (!qdf_slist_empty(&bucket->list))
- return false;
- return true;
- }
- #ifdef ENABLE_QDF_PTR_HASH_DEBUG
- static inline void qdf_ptr_hash_dup_check_in_bucket(
- struct qdf_ptr_hash_bucket *bucket,
- struct qdf_ptr_hash_entry *cmp_entry)
- {
- struct qdf_ptr_hash_entry *tmp_entry;
- qdf_slist_for_each(&bucket->list, tmp_entry, node)
- qdf_assert_always(tmp_entry != cmp_entry);
- }
- #else
- #define qdf_ptr_hash_dup_check_in_bucket(_bucket, _cmp_entry)
- #endif
- static inline struct qdf_ptr_hash_bucket *
- __qdf_ptr_hash_get_bucket(struct qdf_ptr_hash *ht, uintptr_t key)
- {
- return ht->buckets + __qdf_ptr_hash_key(key, ht->bits);
- }
- #define qdf_ptr_hash_add(ht, key, item, entry_field) \
- __qdf_ptr_hash_add(ht, (uintptr_t)key, &(item)->entry_field)
- static inline void __qdf_ptr_hash_add(struct qdf_ptr_hash *ht, uintptr_t key,
- struct qdf_ptr_hash_entry *entry)
- {
- entry->key = key;
-
- qdf_ptr_hash_dup_check_in_bucket(__qdf_ptr_hash_get_bucket(ht, key),
- entry);
- qdf_slist_push(&__qdf_ptr_hash_get_bucket(ht, key)->list, entry, node);
- }
- #define qdf_ptr_hash_remove(ht, key, cursor, entry_field) ({ \
- struct qdf_ptr_hash_entry *_e = \
- __qdf_ptr_hash_remove(ht, (uintptr_t)key); \
- cursor = _e ? qdf_container_of(_e, typeof(*(cursor)), \
- entry_field) : NULL; \
- cursor; })
- static inline struct qdf_ptr_hash_entry *
- __qdf_ptr_hash_remove(struct qdf_ptr_hash *ht, uintptr_t key)
- {
- struct qdf_ptr_hash_bucket *bucket = __qdf_ptr_hash_get_bucket(ht, key);
- struct qdf_ptr_hash_entry *prev;
- struct qdf_ptr_hash_entry *entry;
- qdf_slist_for_each_del(&bucket->list, prev, entry, node) {
- if (entry->key == key) {
- qdf_slist_remove(&bucket->list, prev, node);
-
- qdf_ptr_hash_dup_check_in_bucket(bucket, entry);
- entry->key = 0;
- return entry;
- }
- }
- return NULL;
- }
- #define __qdf_ptr_hash_for_each_in_bucket(bucket, cursor, entry_field) \
- qdf_slist_for_each(&(bucket)->list, cursor, entry_field.node)
- #define qdf_ptr_hash_for_each(ht, bucket, cursor, entry_field) \
- __qdf_ptr_hash_for_each_bucket(ht, bucket) \
- __qdf_ptr_hash_for_each_in_bucket(bucket, cursor, entry_field)
- #define qdf_ptr_hash_for_each_by_hash(ht, key, cursor, entry_field) \
- __qdf_ptr_hash_for_each_in_bucket( \
- __qdf_ptr_hash_get_bucket(ht, (uintptr_t)key), \
- cursor, entry_field)
- #define qdf_ptr_hash_for_each_by_key(ht, _key, cursor, entry_field) \
- qdf_ptr_hash_for_each_by_hash(ht, _key, cursor, entry_field) \
- if ((cursor)->entry_field.key == (uintptr_t)_key)
- #define qdf_ptr_hash_get(ht, key, cursor, entry_field) ({ \
- cursor = NULL; \
- qdf_ptr_hash_for_each_by_key(ht, key, cursor, entry_field) \
- break; \
- cursor; })
- #endif
|