[linux-2.6-block.git] / include / linux / rhashtable-types.h

/* SPDX-License-Identifier: GPL-2.0 */
/*
 * Resizable, Scalable, Concurrent Hash Table
 *
 * Simple structures that might be needed in include
 * files.
 */

#ifndef _LINUX_RHASHTABLE_TYPES_H
#define _LINUX_RHASHTABLE_TYPES_H

#include <linux/alloc_tag.h>
#include <linux/atomic.h>
#include <linux/compiler.h>
#include <linux/mutex.h>
#include <linux/workqueue_types.h>

struct rhash_head {
	struct rhash_head __rcu		*next;
};

struct rhlist_head {
	struct rhash_head		rhead;
	struct rhlist_head __rcu	*next;
};

struct bucket_table;

/**
 * struct rhashtable_compare_arg - Key for the function rhashtable_compare
 * @ht: Hash table
 * @key: Key to compare against
 */
struct rhashtable_compare_arg {
	struct rhashtable *ht;
	const void *key;
};

typedef u32 (*rht_hashfn_t)(const void *data, u32 len, u32 seed);
typedef u32 (*rht_obj_hashfn_t)(const void *data, u32 len, u32 seed);
typedef int (*rht_obj_cmpfn_t)(struct rhashtable_compare_arg *arg,
			       const void *obj);

/**
 * struct rhashtable_params - Hash table construction parameters
 * @nelem_hint: Hint on number of elements, should be 75% of desired size
 * @key_len: Length of key
 * @key_offset: Offset of key in struct to be hashed
 * @head_offset: Offset of rhash_head in struct to be hashed
 * @max_size: Maximum size while expanding
 * @min_size: Minimum size while shrinking
 * @automatic_shrinking: Enable automatic shrinking of tables
 * @hashfn: Hash function (default: jhash2 if !(key_len % 4), or jhash)
 * @obj_hashfn: Function to hash object
 * @obj_cmpfn: Function to compare key with object
 */
struct rhashtable_params {
	u16			nelem_hint;
	u16			key_len;
	u16			key_offset;
	u16			head_offset;
	unsigned int		max_size;
	u16			min_size;
	bool			automatic_shrinking;
	rht_hashfn_t		hashfn;
	rht_obj_hashfn_t	obj_hashfn;
	rht_obj_cmpfn_t		obj_cmpfn;
};

/**
 * struct rhashtable - Hash table handle
 * @tbl: Bucket table
 * @key_len: Key length for hashfn
 * @max_elems: Maximum number of elements in table
 * @p: Configuration parameters
 * @rhlist: True if this is an rhltable
 * @run_work: Deferred worker to expand/shrink asynchronously
 * @mutex: Mutex to protect current/future table swapping
 * @lock: Spin lock to protect walker list
 * @nelems: Number of elements in table
 */
struct rhashtable {
	struct bucket_table __rcu	*tbl;
	unsigned int			key_len;
	unsigned int			max_elems;
	struct rhashtable_params	p;
	bool				rhlist;
	struct work_struct		run_work;
	struct mutex                    mutex;
	spinlock_t			lock;
	atomic_t			nelems;
#ifdef CONFIG_MEM_ALLOC_PROFILING
	struct alloc_tag		*alloc_tag;
#endif
};

/**
 * struct rhltable - Hash table with duplicate objects in a list
 * @ht: Underlying rhtable
 */
struct rhltable {
	struct rhashtable ht;
};

/**
 * struct rhashtable_walker - Hash table walker
 * @list: List entry on list of walkers
 * @tbl: The table that we were walking over
 */
struct rhashtable_walker {
	struct list_head list;
	struct bucket_table *tbl;
};

/**
 * struct rhashtable_iter - Hash table iterator
 * @ht: Table to iterate through
 * @p: Current pointer
 * @list: Current hash list pointer
 * @walker: Associated rhashtable walker
 * @slot: Current slot
 * @skip: Number of entries to skip in slot
 */
struct rhashtable_iter {
	struct rhashtable *ht;
	struct rhash_head *p;
	struct rhlist_head *list;
	struct rhashtable_walker walker;
	unsigned int slot;
	unsigned int skip;
	bool end_of_table;
};

int rhashtable_init_noprof(struct rhashtable *ht,
		    const struct rhashtable_params *params);
#define rhashtable_init(...)	alloc_hooks(rhashtable_init_noprof(__VA_ARGS__))

int rhltable_init_noprof(struct rhltable *hlt,
		  const struct rhashtable_params *params);
#define rhltable_init(...)	alloc_hooks(rhltable_init_noprof(__VA_ARGS__))

#endif /* _LINUX_RHASHTABLE_TYPES_H */
Commit	Line	Data
0eb71a9d N	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
9e54dd8b	12	#include <linux/alloc_tag.h>
0eb71a9d N	13	#include <linux/atomic.h>
	14	#include <linux/compiler.h>
	15	#include <linux/mutex.h>
b2fa8443	16	#include <linux/workqueue_types.h>
0eb71a9d N	17
	18	struct rhash_head {
	19	struct rhash_head __rcu *next;
	20	};
	21
	22	struct rhlist_head {
	23	struct rhash_head rhead;
	24	struct rhlist_head __rcu *next;
	25	};
	26
	27	struct 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	*/
	34	struct rhashtable_compare_arg {
	35	struct rhashtable *ht;
	36	const void *key;
	37	};
	38
	39	typedef u32 (rht_hashfn_t)(const void data, u32 len, u32 seed);
	40	typedef u32 (rht_obj_hashfn_t)(const void data, u32 len, u32 seed);
	41	typedef 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
0eb71a9d	52	* @automatic_shrinking: Enable automatic shrinking of tables
0eb71a9d N	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;
0eb71a9d N	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	*/
	82	struct 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;
9e54dd8b KO	92	#ifdef CONFIG_MEM_ALLOC_PROFILING
	93	struct alloc_tag *alloc_tag;
	94	#endif
0eb71a9d N	95	};
	96
	97	/**
	98	* struct rhltable - Hash table with duplicate objects in a list
	99	* @ht: Underlying rhtable
	100	*/
	101	struct 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	*/
	110	struct 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	*/
	124	struct 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
9e54dd8b	134	int rhashtable_init_noprof(struct rhashtable *ht,
0eb71a9d	135	const struct rhashtable_params *params);
9e54dd8b KO	136	#define rhashtable_init(...) alloc_hooks(rhashtable_init_noprof(__VA_ARGS__))
	137
	138	int rhltable_init_noprof(struct rhltable *hlt,
0eb71a9d	139	const struct rhashtable_params *params);
9e54dd8b	140	#define rhltable_init(...) alloc_hooks(rhltable_init_noprof(__VA_ARGS__))
0eb71a9d N	141
0eb71a9d N	142	#endif /* _LINUX_RHASHTABLE_TYPES_H */