LXR linux/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
  17struct rhash_head {
  18        struct rhash_head __rcu         *next;
  19};
  20
  21struct rhlist_head {
  22        struct rhash_head               rhead;
  23        struct rhlist_head __rcu        *next;
  24};
  25
  26struct 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 */
  33struct rhashtable_compare_arg {
  34        struct rhashtable *ht;
  35        const void *key;
  36};
  37
  38typedef u32 (*rht_hashfn_t)(const void *data, u32 len, u32 seed);
  39typedef u32 (*rht_obj_hashfn_t)(const void *data, u32 len, u32 seed);
  40typedef 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 */
  56struct 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 */
  81struct 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 */
  97struct 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 */
 106struct 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 */
 120struct 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
 130int rhashtable_init(struct rhashtable *ht,
 131                    const struct rhashtable_params *params);
 132int rhltable_init(struct rhltable *hlt,
 133                  const struct rhashtable_params *params);
 134
 135#endif /* _LINUX_RHASHTABLE_TYPES_H */
 136