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/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 */