include/linux/rhashtable-types.h

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