include/linux/rhashtable-types.h

0001 /* SPDX-License-Identifier: GPL-2.0 */
0002 /*
0003  * Resizable, Scalable, Concurrent Hash Table
0004  *
0005  * Simple structures that might be needed in include
0006  * files.
0007  */
0008
0009 #ifndef _LINUX_RHASHTABLE_TYPES_H
0010 #define _LINUX_RHASHTABLE_TYPES_H
0011
0012 #include <linux/atomic.h>
0013 #include <linux/compiler.h>
0014 #include <linux/mutex.h>
0015 #include <linux/workqueue.h>
0016
0017 struct rhash_head {
0018     struct rhash_head __rcu     *next;
0019 };
0020
0021 struct rhlist_head {
0022     struct rhash_head       rhead;
0023     struct rhlist_head __rcu    *next;
0024 };
0025
0026 struct bucket_table;
0027
0028 /**
0029  * struct rhashtable_compare_arg - Key for the function rhashtable_compare
0030  * @ht: Hash table
0031  * @key: Key to compare against
0032  */
0033 struct rhashtable_compare_arg {
0034     struct rhashtable *ht;
0035     const void *key;
0036 };
0037
0038 typedef u32 (*rht_hashfn_t)(const void *data, u32 len, u32 seed);
0039 typedef u32 (*rht_obj_hashfn_t)(const void *data, u32 len, u32 seed);
0040 typedef int (*rht_obj_cmpfn_t)(struct rhashtable_compare_arg *arg,
0041                    const void *obj);
0042
0043 /**
0044  * struct rhashtable_params - Hash table construction parameters
0045  * @nelem_hint: Hint on number of elements, should be 75% of desired size
0046  * @key_len: Length of key
0047  * @key_offset: Offset of key in struct to be hashed
0048  * @head_offset: Offset of rhash_head in struct to be hashed
0049  * @max_size: Maximum size while expanding
0050  * @min_size: Minimum size while shrinking
0051  * @automatic_shrinking: Enable automatic shrinking of tables
0052  * @hashfn: Hash function (default: jhash2 if !(key_len % 4), or jhash)
0053  * @obj_hashfn: Function to hash object
0054  * @obj_cmpfn: Function to compare key with object
0055  */
0056 struct rhashtable_params {
0057     u16         nelem_hint;
0058     u16         key_len;
0059     u16         key_offset;
0060     u16         head_offset;
0061     unsigned int        max_size;
0062     u16         min_size;
0063     bool            automatic_shrinking;
0064     rht_hashfn_t        hashfn;
0065     rht_obj_hashfn_t    obj_hashfn;
0066     rht_obj_cmpfn_t     obj_cmpfn;
0067 };
0068
0069 /**
0070  * struct rhashtable - Hash table handle
0071  * @tbl: Bucket table
0072  * @key_len: Key length for hashfn
0073  * @max_elems: Maximum number of elements in table
0074  * @p: Configuration parameters
0075  * @rhlist: True if this is an rhltable
0076  * @run_work: Deferred worker to expand/shrink asynchronously
0077  * @mutex: Mutex to protect current/future table swapping
0078  * @lock: Spin lock to protect walker list
0079  * @nelems: Number of elements in table
0080  */
0081 struct rhashtable {
0082     struct bucket_table __rcu   *tbl;
0083     unsigned int            key_len;
0084     unsigned int            max_elems;
0085     struct rhashtable_params    p;
0086     bool                rhlist;
0087     struct work_struct      run_work;
0088     struct mutex                    mutex;
0089     spinlock_t          lock;
0090     atomic_t            nelems;
0091 };
0092
0093 /**
0094  * struct rhltable - Hash table with duplicate objects in a list
0095  * @ht: Underlying rhtable
0096  */
0097 struct rhltable {
0098     struct rhashtable ht;
0099 };
0100
0101 /**
0102  * struct rhashtable_walker - Hash table walker
0103  * @list: List entry on list of walkers
0104  * @tbl: The table that we were walking over
0105  */
0106 struct rhashtable_walker {
0107     struct list_head list;
0108     struct bucket_table *tbl;
0109 };
0110
0111 /**
0112  * struct rhashtable_iter - Hash table iterator
0113  * @ht: Table to iterate through
0114  * @p: Current pointer
0115  * @list: Current hash list pointer
0116  * @walker: Associated rhashtable walker
0117  * @slot: Current slot
0118  * @skip: Number of entries to skip in slot
0119  */
0120 struct rhashtable_iter {
0121     struct rhashtable *ht;
0122     struct rhash_head *p;
0123     struct rhlist_head *list;
0124     struct rhashtable_walker walker;
0125     unsigned int slot;
0126     unsigned int skip;
0127     bool end_of_table;
0128 };
0129
0130 int rhashtable_init(struct rhashtable *ht,
0131             const struct rhashtable_params *params);
0132 int rhltable_init(struct rhltable *hlt,
0133           const struct rhashtable_params *params);
0134
0135 #endif /* _LINUX_RHASHTABLE_TYPES_H */