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_types.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