^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) /* SPDX-License-Identifier: GPL-2.0 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3) * Statically sized hash table implementation
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4) * (C) 2012 Sasha Levin <levinsasha928@gmail.com>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) #ifndef _LINUX_HASHTABLE_H
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8) #define _LINUX_HASHTABLE_H
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10) #include <linux/list.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11) #include <linux/types.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12) #include <linux/kernel.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13) #include <linux/bitops.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14) #include <linux/hash.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15) #include <linux/log2.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17) #define DEFINE_HASHTABLE(name, bits) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18) struct hlist_head name[1 << (bits)] = \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) { [0 ... ((1 << (bits)) - 1)] = HLIST_HEAD_INIT }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) #define DECLARE_HASHTABLE(name, bits) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22) struct hlist_head name[1 << (bits)]
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) #define HASH_SIZE(name) (ARRAY_SIZE(name))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25) #define HASH_BITS(name) ilog2(HASH_SIZE(name))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) /* Use hash_32 when possible to allow for fast 32bit hashing in 64bit kernels. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28) #define hash_min(val, bits) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29) (sizeof(val) <= 4 ? hash_32(val, bits) : hash_long(val, bits))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31) static inline void __hash_init(struct hlist_head *ht, unsigned int sz)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) unsigned int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) for (i = 0; i < sz; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36) INIT_HLIST_HEAD(&ht[i]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40) * hash_init - initialize a hash table
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) * @hashtable: hashtable to be initialized
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43) * Calculates the size of the hashtable from the given parameter, otherwise
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44) * same as hash_init_size.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) * This has to be a macro since HASH_BITS() will not work on pointers since
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) * it calculates the size during preprocessing.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) #define hash_init(hashtable) __hash_init(hashtable, HASH_SIZE(hashtable))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) * hash_add - add an object to a hashtable
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) * @hashtable: hashtable to add to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54) * @node: the &struct hlist_node of the object to be added
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) * @key: the key of the object to be added
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) #define hash_add(hashtable, node, key) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) hlist_add_head(node, &hashtable[hash_min(key, HASH_BITS(hashtable))])
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) * hash_hashed - check whether an object is in any hashtable
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) * @node: the &struct hlist_node of the object to be checked
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64) static inline bool hash_hashed(struct hlist_node *node)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66) return !hlist_unhashed(node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) static inline bool __hash_empty(struct hlist_head *ht, unsigned int sz)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71) unsigned int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) for (i = 0; i < sz; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) if (!hlist_empty(&ht[i]))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) return false;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) return true;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81) * hash_empty - check whether a hashtable is empty
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82) * @hashtable: hashtable to check
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84) * This has to be a macro since HASH_BITS() will not work on pointers since
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) * it calculates the size during preprocessing.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87) #define hash_empty(hashtable) __hash_empty(hashtable, HASH_SIZE(hashtable))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90) * hash_del - remove an object from a hashtable
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91) * @node: &struct hlist_node of the object to remove
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) static inline void hash_del(struct hlist_node *node)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95) hlist_del_init(node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99) * hash_for_each - iterate over a hashtable
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100) * @name: hashtable to iterate
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) * @bkt: integer to use as bucket loop cursor
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102) * @obj: the type * to use as a loop cursor for each entry
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103) * @member: the name of the hlist_node within the struct
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105) #define hash_for_each(name, bkt, obj, member) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106) for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) (bkt)++)\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108) hlist_for_each_entry(obj, &name[bkt], member)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111) * hash_for_each_safe - iterate over a hashtable safe against removal of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112) * hash entry
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) * @name: hashtable to iterate
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114) * @bkt: integer to use as bucket loop cursor
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115) * @tmp: a &struct used for temporary storage
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116) * @obj: the type * to use as a loop cursor for each entry
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117) * @member: the name of the hlist_node within the struct
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119) #define hash_for_each_safe(name, bkt, tmp, obj, member) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120) for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121) (bkt)++)\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122) hlist_for_each_entry_safe(obj, tmp, &name[bkt], member)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125) * hash_for_each_possible - iterate over all possible objects hashing to the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126) * same bucket
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127) * @name: hashtable to iterate
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128) * @obj: the type * to use as a loop cursor for each entry
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129) * @member: the name of the hlist_node within the struct
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130) * @key: the key of the objects to iterate over
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132) #define hash_for_each_possible(name, obj, member, key) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133) hlist_for_each_entry(obj, &name[hash_min(key, HASH_BITS(name))], member)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136) * hash_for_each_possible_safe - iterate over all possible objects hashing to the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137) * same bucket safe against removals
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138) * @name: hashtable to iterate
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139) * @obj: the type * to use as a loop cursor for each entry
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140) * @tmp: a &struct used for temporary storage
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141) * @member: the name of the hlist_node within the struct
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142) * @key: the key of the objects to iterate over
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144) #define hash_for_each_possible_safe(name, obj, tmp, member, key) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145) hlist_for_each_entry_safe(obj, tmp,\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146) &name[hash_min(key, HASH_BITS(name))], member)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 148)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 149) #endif
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags