Lines Matching full:hash
3 * Resizable, Scalable, Concurrent Hash Table
32 * which is linked into as hash chain from the hash table - or one
33 * of two or more hash tables when the rhashtable is being resized.
36 * the hash bucket. This allows us to be sure we've found the end
38 * The value stored in the hash bucket has BIT(0) used as a lock bit.
51 * The maximum (not average) chain length grows with the size of the hash
54 * The value of 16 is selected so that even if the hash table grew to
65 * struct bucket_table - Table of hash buckets
66 * @size: Number of hash buckets
69 * @hash_rnd: Random seed to fold into hash
74 * @buckets: size * hash buckets
91 * NULLS_MARKER() expects a hash value with the low
99 * We never store the NULLS_MARKER in the hash table
120 unsigned int hash) in rht_bucket_index() argument
122 return hash & (tbl->size - 1); in rht_bucket_index()
129 unsigned int hash; in rht_key_get_hash() local
133 hash = ht->p.hashfn(key, ht->key_len, hash_rnd); in rht_key_get_hash()
138 hash = params.hashfn(key, key_len, hash_rnd); in rht_key_get_hash()
140 hash = jhash(key, key_len, hash_rnd); in rht_key_get_hash()
142 hash = jhash2(key, key_len / sizeof(u32), hash_rnd); in rht_key_get_hash()
147 hash = params.hashfn(key, key_len, hash_rnd); in rht_key_get_hash()
149 hash = jhash(key, key_len, hash_rnd); in rht_key_get_hash()
152 return hash; in rht_key_get_hash()
159 unsigned int hash = rht_key_get_hash(ht, key, params, tbl->hash_rnd); in rht_key_hashfn() local
161 return rht_bucket_index(tbl, hash); in rht_key_hashfn()
179 * @ht: hash table
192 * @ht: hash table
205 * @ht: hash table
217 * @ht: hash table
228 int lockdep_rht_bucket_is_held(const struct bucket_table *tbl, u32 hash);
236 u32 hash) in lockdep_rht_bucket_is_held() argument
265 const struct bucket_table *tbl, unsigned int hash);
267 const struct bucket_table *tbl, unsigned int hash);
269 struct rhashtable *ht, struct bucket_table *tbl, unsigned int hash);
277 #define rht_dereference_bucket(p, tbl, hash) \ argument
278 rcu_dereference_protected(p, lockdep_rht_bucket_is_held(tbl, hash))
280 #define rht_dereference_bucket_rcu(p, tbl, hash) \ argument
281 rcu_dereference_check(p, lockdep_rht_bucket_is_held(tbl, hash))
287 const struct bucket_table *tbl, unsigned int hash) in rht_bucket() argument
289 return unlikely(tbl->nest) ? rht_bucket_nested(tbl, hash) : in rht_bucket()
290 &tbl->buckets[hash]; in rht_bucket()
294 struct bucket_table *tbl, unsigned int hash) in rht_bucket_var() argument
296 return unlikely(tbl->nest) ? __rht_bucket_nested(tbl, hash) : in rht_bucket_var()
297 &tbl->buckets[hash]; in rht_bucket_var()
301 struct rhashtable *ht, struct bucket_table *tbl, unsigned int hash) in rht_bucket_insert() argument
303 return unlikely(tbl->nest) ? rht_bucket_nested_insert(ht, tbl, hash) : in rht_bucket_insert()
304 &tbl->buckets[hash]; in rht_bucket_insert()
313 * A nested hash table might not have a bucket pointer. In that case
382 unsigned int hash) in rht_ptr() argument
384 return __rht_ptr(rht_dereference_bucket(*bkt, tbl, hash), bkt); in rht_ptr()
416 * rht_for_each_from - iterate over hash chain from given head
420 * @hash: the hash value / bucket index
422 #define rht_for_each_from(pos, head, tbl, hash) \ argument
425 pos = rht_dereference_bucket((pos)->next, tbl, hash))
428 * rht_for_each - iterate over hash chain
431 * @hash: the hash value / bucket index
433 #define rht_for_each(pos, tbl, hash) \ argument
434 rht_for_each_from(pos, rht_ptr(rht_bucket(tbl, hash), tbl, hash), \
435 tbl, hash)
438 * rht_for_each_entry_from - iterate over hash chain from given head
443 * @hash: the hash value / bucket index
446 #define rht_for_each_entry_from(tpos, pos, head, tbl, hash, member) \ argument
449 pos = rht_dereference_bucket((pos)->next, tbl, hash))
452 * rht_for_each_entry - iterate over hash chain of given type
456 * @hash: the hash value / bucket index
459 #define rht_for_each_entry(tpos, pos, tbl, hash, member) \ argument
461 rht_ptr(rht_bucket(tbl, hash), tbl, hash), \
462 tbl, hash, member)
465 * rht_for_each_entry_safe - safely iterate over hash chain of given type
470 * @hash: the hash value / bucket index
473 * This hash chain list-traversal primitive allows for the looped code to
476 #define rht_for_each_entry_safe(tpos, pos, next, tbl, hash, member) \ argument
477 for (pos = rht_ptr(rht_bucket(tbl, hash), tbl, hash), \
479 rht_dereference_bucket(pos->next, tbl, hash) : NULL; \
483 rht_dereference_bucket(pos->next, tbl, hash) : NULL)
486 * rht_for_each_rcu_from - iterate over rcu hash chain from given head
490 * @hash: the hash value / bucket index
492 * This hash chain list-traversal primitive may safely run concurrently with
496 #define rht_for_each_rcu_from(pos, head, tbl, hash) \ argument
503 * rht_for_each_rcu - iterate over rcu hash chain
506 * @hash: the hash value / bucket index
508 * This hash chain list-traversal primitive may safely run concurrently with
512 #define rht_for_each_rcu(pos, tbl, hash) \ argument
514 pos = rht_ptr_rcu(rht_bucket(tbl, hash)); \
519 * rht_for_each_entry_rcu_from - iterated over rcu hash chain from given head
524 * @hash: the hash value / bucket index
527 * This hash chain list-traversal primitive may safely run concurrently with
531 #define rht_for_each_entry_rcu_from(tpos, pos, head, tbl, hash, member) \ argument
535 pos = rht_dereference_bucket_rcu(pos->next, tbl, hash))
538 * rht_for_each_entry_rcu - iterate over rcu hash chain of given type
542 * @hash: the hash value / bucket index
545 * This hash chain list-traversal primitive may safely run concurrently with
549 #define rht_for_each_entry_rcu(tpos, pos, tbl, hash, member) \ argument
551 rht_ptr_rcu(rht_bucket(tbl, hash)), \
552 tbl, hash, member)
555 * rhl_for_each_rcu - iterate over rcu hash table list
559 * This hash chain list-traversal primitive should be used on the
566 * rhl_for_each_entry_rcu - iterate over rcu hash table list of given type
572 * This hash chain list-traversal primitive should be used on the
600 unsigned int hash; in __rhashtable_lookup() local
604 hash = rht_key_hashfn(ht, tbl, key, params); in __rhashtable_lookup()
605 bkt = rht_bucket(tbl, hash); in __rhashtable_lookup()
607 rht_for_each_rcu_from(he, rht_ptr_rcu(bkt), tbl, hash) { in __rhashtable_lookup()
614 /* An object might have been moved to a different hash chain, in __rhashtable_lookup()
630 * rhashtable_lookup - search hash table
631 * @ht: hash table
633 * @params: hash table parameters
635 * Computes the hash value for the key and traverses the bucket chain looking
652 * rhashtable_lookup_fast - search hash table, without RCU read lock
653 * @ht: hash table
655 * @params: hash table parameters
657 * Computes the hash value for the key and traverses the bucket chain looking
679 * rhltable_lookup - search hash list table
680 * @hlt: hash table
682 * @params: hash table parameters
684 * Computes the hash value for the key and traverses the bucket chain looking
718 unsigned int hash; in __rhashtable_insert_fast() local
725 hash = rht_head_hashfn(ht, tbl, obj, params); in __rhashtable_insert_fast()
727 bkt = rht_bucket_insert(ht, tbl, hash); in __rhashtable_insert_fast()
741 rht_for_each_from(head, rht_ptr(bkt, tbl, hash), tbl, hash) { in __rhashtable_insert_fast()
764 head = rht_dereference_bucket(head->next, tbl, hash); in __rhashtable_insert_fast()
786 head = rht_ptr(bkt, tbl, hash); in __rhashtable_insert_fast()
814 * rhashtable_insert_fast - insert object into hash table
815 * @ht: hash table
816 * @obj: pointer to hash head inside object
817 * @params: hash table parameters
842 * rhltable_insert_key - insert object into hash list table
843 * @hlt: hash list table
845 * @list: pointer to hash list head inside object
846 * @params: hash table parameters
866 * rhltable_insert - insert object into hash list table
867 * @hlt: hash list table
868 * @list: pointer to hash list head inside object
869 * @params: hash table parameters
892 * rhashtable_lookup_insert_fast - lookup and insert object into hash table
893 * @ht: hash table
894 * @obj: pointer to hash head inside object
895 * @params: hash table parameters
897 * This lookup function may only be used for fixed key hash table (key_len
923 * rhashtable_lookup_get_insert_fast - lookup and insert object into hash table
924 * @ht: hash table
925 * @obj: pointer to hash head inside object
926 * @params: hash table parameters
945 * rhashtable_lookup_insert_key - search and insert object to hash table
947 * @ht: hash table
949 * @obj: pointer to hash head inside object
950 * @params: hash table parameters
975 * rhashtable_lookup_get_insert_key - lookup and insert object into hash table
976 * @ht: hash table
978 * @obj: pointer to hash head inside object
979 * @params: hash table parameters
1004 unsigned int hash; in __rhashtable_remove_fast_one() local
1007 hash = rht_head_hashfn(ht, tbl, obj, params); in __rhashtable_remove_fast_one()
1008 bkt = rht_bucket_var(tbl, hash); in __rhashtable_remove_fast_one()
1014 rht_for_each_from(he, rht_ptr(bkt, tbl, hash), tbl, hash) { in __rhashtable_remove_fast_one()
1030 tbl, hash); in __rhashtable_remove_fast_one()
1036 list = rht_dereference_bucket(list->next, tbl, hash); in __rhashtable_remove_fast_one()
1042 obj = rht_dereference_bucket(obj->next, tbl, hash); in __rhashtable_remove_fast_one()
1046 list = rht_dereference_bucket(list->next, tbl, hash); in __rhashtable_remove_fast_one()
1104 * rhashtable_remove_fast - remove object from hash table
1105 * @ht: hash table
1106 * @obj: pointer to hash head inside object
1107 * @params: hash table parameters
1109 * Since the hash chain is single linked, the removal operation needs to
1111 * considerable slow if the hash table is not correctly sized.
1126 * rhltable_remove - remove object from hash list table
1127 * @hlt: hash list table
1128 * @list: pointer to hash list head inside object
1129 * @params: hash table parameters
1131 * Since the hash chain is single linked, the removal operation needs to
1133 * considerably slower if the hash table is not correctly sized.
1157 unsigned int hash; in __rhashtable_replace_fast() local
1160 /* Minimally, the old and new objects must have same hash in __rhashtable_replace_fast()
1163 hash = rht_head_hashfn(ht, tbl, obj_old, params); in __rhashtable_replace_fast()
1164 if (hash != rht_head_hashfn(ht, tbl, obj_new, params)) in __rhashtable_replace_fast()
1167 bkt = rht_bucket_var(tbl, hash); in __rhashtable_replace_fast()
1174 rht_for_each_from(he, rht_ptr(bkt, tbl, hash), tbl, hash) { in __rhashtable_replace_fast()
1198 * rhashtable_replace_fast - replace an object in hash table
1199 * @ht: hash table
1200 * @obj_old: pointer to hash head inside object being replaced
1201 * @obj_new: pointer to hash head inside object which is new
1202 * @params: hash table parameters
1204 * Replacing an object doesn't affect the number of elements in the hash table
1209 * -EINVAL if hash is not the same for the old and new objects.
1241 * @iter: Hash table Iterator
1243 * This function prepares a hash table walk.
1251 * structure outside the hash table.
1266 * rhltable_free_and_destroy - free elements and destroy hash list table
1267 * @hlt: the hash list table to destroy