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  * @locks_mul: Number of bucket locks to allocate per cpu (default: 32)
  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         u8                      locks_mul;
  66         rht_hashfn_t            hashfn;
  67         rht_obj_hashfn_t        obj_hashfn;
  68         rht_obj_cmpfn_t         obj_cmpfn;
  69 };
  70
  71 /**
  72  * struct rhashtable - Hash table handle
  73  * @tbl: Bucket table
  74  * @key_len: Key length for hashfn
  75  * @max_elems: Maximum number of elements in table
  76  * @p: Configuration parameters
  77  * @rhlist: True if this is an rhltable
  78  * @run_work: Deferred worker to expand/shrink asynchronously
  79  * @mutex: Mutex to protect current/future table swapping
  80  * @lock: Spin lock to protect walker list
  81  * @nelems: Number of elements in table
  82  */
  83 struct rhashtable {
  84         struct bucket_table __rcu       *tbl;
  85         unsigned int                    key_len;
  86         unsigned int                    max_elems;
  87         struct rhashtable_params        p;
  88         bool                            rhlist;
  89         struct work_struct              run_work;
  90         struct mutex                    mutex;
  91         spinlock_t                      lock;
  92         atomic_t                        nelems;
  93 };
  94
  95 /**
  96  * struct rhltable - Hash table with duplicate objects in a list
  97  * @ht: Underlying rhtable
  98  */
  99 struct rhltable {
 100         struct rhashtable ht;
 101 };
 102
 103 /**
 104  * struct rhashtable_walker - Hash table walker
 105  * @list: List entry on list of walkers
 106  * @tbl: The table that we were walking over
 107  */
 108 struct rhashtable_walker {
 109         struct list_head list;
 110         struct bucket_table *tbl;
 111 };
 112
 113 /**
 114  * struct rhashtable_iter - Hash table iterator
 115  * @ht: Table to iterate through
 116  * @p: Current pointer
 117  * @list: Current hash list pointer
 118  * @walker: Associated rhashtable walker
 119  * @slot: Current slot
 120  * @skip: Number of entries to skip in slot
 121  */
 122 struct rhashtable_iter {
 123         struct rhashtable *ht;
 124         struct rhash_head *p;
 125         struct rhlist_head *list;
 126         struct rhashtable_walker walker;
 127         unsigned int slot;
 128         unsigned int skip;
 129         bool end_of_table;
 130 };
 131
 132 int rhashtable_init(struct rhashtable *ht,
 133                     const struct rhashtable_params *params);
 134 int rhltable_init(struct rhltable *hlt,
 135                   const struct rhashtable_params *params);
 136
 137 #endif /* _LINUX_RHASHTABLE_TYPES_H */