1 /* SPDX-License-Identifier: GPL-2.0 */ 2 /* 3 * Resizable, Scalable, Concurrent Hash Table 4 * 5 * Simple structures that might be needed in include 6 * files. 7 */ 8 9 #ifndef _LINUX_RHASHTABLE_TYPES_H 10 #define _LINUX_RHASHTABLE_TYPES_H 11 12 #include <linux/atomic.h> 13 #include <linux/compiler.h> 14 #include <linux/mutex.h> 15 #include <linux/workqueue.h> 16 17 struct rhash_head { 18 struct rhash_head __rcu *next; 19 }; 20 21 struct rhlist_head { 22 struct rhash_head rhead; 23 struct rhlist_head __rcu *next; 24 }; 25 26 struct bucket_table; 27 28 /** 29 * struct rhashtable_compare_arg - Key for the function rhashtable_compare 30 * @ht: Hash table 31 * @key: Key to compare against 32 */ 33 struct rhashtable_compare_arg { 34 struct rhashtable *ht; 35 const void *key; 36 }; 37 38 typedef u32 (*rht_hashfn_t)(const void *data, u32 len, u32 seed); 39 typedef u32 (*rht_obj_hashfn_t)(const void *data, u32 len, u32 seed); 40 typedef int (*rht_obj_cmpfn_t)(struct rhashtable_compare_arg *arg, 41 const void *obj); 42 43 /** 44 * struct rhashtable_params - Hash table construction parameters 45 * @nelem_hint: Hint on number of elements, should be 75% of desired size 46 * @key_len: Length of key 47 * @key_offset: Offset of key in struct to be hashed 48 * @head_offset: Offset of rhash_head in struct to be hashed 49 * @max_size: Maximum size while expanding 50 * @min_size: Minimum size while shrinking 51 * @automatic_shrinking: Enable automatic shrinking of tables 52 * @hashfn: Hash function (default: jhash2 if !(key_len % 4), or jhash) 53 * @obj_hashfn: Function to hash object 54 * @obj_cmpfn: Function to compare key with object 55 */ 56 struct rhashtable_params { 57 u16 nelem_hint; 58 u16 key_len; 59 u16 key_offset; 60 u16 head_offset; 61 unsigned int max_size; 62 u16 min_size; 63 bool automatic_shrinking; 64 rht_hashfn_t hashfn; 65 rht_obj_hashfn_t obj_hashfn; 66 rht_obj_cmpfn_t obj_cmpfn; 67 }; 68 69 /** 70 * struct rhashtable - Hash table handle 71 * @tbl: Bucket table 72 * @key_len: Key length for hashfn 73 * @max_elems: Maximum number of elements in table 74 * @p: Configuration parameters 75 * @rhlist: True if this is an rhltable 76 * @run_work: Deferred worker to expand/shrink asynchronously 77 * @mutex: Mutex to protect current/future table swapping 78 * @lock: Spin lock to protect walker list 79 * @nelems: Number of elements in table 80 */ 81 struct rhashtable { 82 struct bucket_table __rcu *tbl; 83 unsigned int key_len; 84 unsigned int max_elems; 85 struct rhashtable_params p; 86 bool rhlist; 87 struct work_struct run_work; 88 struct mutex mutex; 89 spinlock_t lock; 90 atomic_t nelems; 91 }; 92 93 /** 94 * struct rhltable - Hash table with duplicate objects in a list 95 * @ht: Underlying rhtable 96 */ 97 struct rhltable { 98 struct rhashtable ht; 99 }; 100 101 /** 102 * struct rhashtable_walker - Hash table walker 103 * @list: List entry on list of walkers 104 * @tbl: The table that we were walking over 105 */ 106 struct rhashtable_walker { 107 struct list_head list; 108 struct bucket_table *tbl; 109 }; 110 111 /** 112 * struct rhashtable_iter - Hash table iterator 113 * @ht: Table to iterate through 114 * @p: Current pointer 115 * @list: Current hash list pointer 116 * @walker: Associated rhashtable walker 117 * @slot: Current slot 118 * @skip: Number of entries to skip in slot 119 */ 120 struct rhashtable_iter { 121 struct rhashtable *ht; 122 struct rhash_head *p; 123 struct rhlist_head *list; 124 struct rhashtable_walker walker; 125 unsigned int slot; 126 unsigned int skip; 127 bool end_of_table; 128 }; 129 130 int rhashtable_init(struct rhashtable *ht, 131 const struct rhashtable_params *params); 132 int rhltable_init(struct rhltable *hlt, 133 const struct rhashtable_params *params); 134 135 #endif /* _LINUX_RHASHTABLE_TYPES_H */ 136