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/alloc_tag.h>
 13#include <linux/atomic.h>
 14#include <linux/compiler.h>
 15#include <linux/mutex.h>
 16#include <linux/workqueue_types.h>
 17
 18struct rhash_head {
 19	struct rhash_head __rcu		*next;
 20};
 21
 22struct rhlist_head {
 23	struct rhash_head		rhead;
 24	struct rhlist_head __rcu	*next;
 25};
 26
 27struct bucket_table;
 28
 29/**
 30 * struct rhashtable_compare_arg - Key for the function rhashtable_compare
 31 * @ht: Hash table
 32 * @key: Key to compare against
 33 */
 34struct rhashtable_compare_arg {
 35	struct rhashtable *ht;
 36	const void *key;
 37};
 38
 39typedef u32 (*rht_hashfn_t)(const void *data, u32 len, u32 seed);
 40typedef u32 (*rht_obj_hashfn_t)(const void *data, u32 len, u32 seed);
 41typedef int (*rht_obj_cmpfn_t)(struct rhashtable_compare_arg *arg,
 42			       const void *obj);
 43
 44/**
 45 * struct rhashtable_params - Hash table construction parameters
 46 * @nelem_hint: Hint on number of elements, should be 75% of desired size
 47 * @key_len: Length of key
 48 * @key_offset: Offset of key in struct to be hashed
 49 * @head_offset: Offset of rhash_head in struct to be hashed
 50 * @max_size: Maximum size while expanding
 51 * @min_size: Minimum size while shrinking
 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	rht_hashfn_t		hashfn;
 66	rht_obj_hashfn_t	obj_hashfn;
 67	rht_obj_cmpfn_t		obj_cmpfn;
 68};
 69
 70/**
 71 * struct rhashtable - Hash table handle
 72 * @tbl: Bucket table
 73 * @key_len: Key length for hashfn
 74 * @max_elems: Maximum number of elements in table
 75 * @p: Configuration parameters
 76 * @rhlist: True if this is an rhltable
 77 * @run_work: Deferred worker to expand/shrink asynchronously
 78 * @mutex: Mutex to protect current/future table swapping
 79 * @lock: Spin lock to protect walker list
 80 * @nelems: Number of elements in table
 81 */
 82struct rhashtable {
 83	struct bucket_table __rcu	*tbl;
 84	unsigned int			key_len;
 85	unsigned int			max_elems;
 86	struct rhashtable_params	p;
 87	bool				rhlist;
 88	struct work_struct		run_work;
 89	struct mutex                    mutex;
 90	spinlock_t			lock;
 91	atomic_t			nelems;
 92#ifdef CONFIG_MEM_ALLOC_PROFILING
 93	struct alloc_tag		*alloc_tag;
 94#endif
 95};
 96
 97/**
 98 * struct rhltable - Hash table with duplicate objects in a list
 99 * @ht: Underlying rhtable
100 */
101struct rhltable {
102	struct rhashtable ht;
103};
104
105/**
106 * struct rhashtable_walker - Hash table walker
107 * @list: List entry on list of walkers
108 * @tbl: The table that we were walking over
109 */
110struct rhashtable_walker {
111	struct list_head list;
112	struct bucket_table *tbl;
113};
114
115/**
116 * struct rhashtable_iter - Hash table iterator
117 * @ht: Table to iterate through
118 * @p: Current pointer
119 * @list: Current hash list pointer
120 * @walker: Associated rhashtable walker
121 * @slot: Current slot
122 * @skip: Number of entries to skip in slot
123 */
124struct rhashtable_iter {
125	struct rhashtable *ht;
126	struct rhash_head *p;
127	struct rhlist_head *list;
128	struct rhashtable_walker walker;
129	unsigned int slot;
130	unsigned int skip;
131	bool end_of_table;
132};
133
134int rhashtable_init_noprof(struct rhashtable *ht,
135		    const struct rhashtable_params *params);
136#define rhashtable_init(...)	alloc_hooks(rhashtable_init_noprof(__VA_ARGS__))
137
138int rhltable_init_noprof(struct rhltable *hlt,
139		  const struct rhashtable_params *params);
140#define rhltable_init(...)	alloc_hooks(rhltable_init_noprof(__VA_ARGS__))
141
142#endif /* _LINUX_RHASHTABLE_TYPES_H */