Linux kernel mirror (for testing)
git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
tjh.dev
kernel
os
linux
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 * @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 */
57struct 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 */
83struct 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 */
99struct 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 */
108struct 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 */
122struct 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
132int rhashtable_init(struct rhashtable *ht,
133 const struct rhashtable_params *params);
134int rhltable_init(struct rhltable *hlt,
135 const struct rhashtable_params *params);
136
137#endif /* _LINUX_RHASHTABLE_TYPES_H */