1/*
2 * CDDL HEADER START
3 *
4 * This file and its contents are supplied under the terms of the
5 * Common Development and Distribution License ("CDDL"), version 1.0.
6 * You may only use this file in accordance with the terms of version
7 * 1.0 of the CDDL.
8 *
9 * A full copy of the text of the CDDL should have accompanied this
10 * source.  A copy of the CDDL is also available via the Internet at
11 * http://www.illumos.org/license/CDDL.
12 *
13 * CDDL HEADER END
14 */
15/*
16 * Copyright (c) 2013, 2017 by Delphix. All rights reserved.
17 */
18
19#ifndef	_SYS_MULTILIST_H
20#define	_SYS_MULTILIST_H
21
22#include <sys/zfs_context.h>
23
24#ifdef	__cplusplus
25extern "C" {
26#endif
27
28typedef list_node_t multilist_node_t;
29typedef struct multilist multilist_t;
30typedef struct multilist_sublist multilist_sublist_t;
31typedef unsigned int multilist_sublist_index_func_t(multilist_t *, void *);
32
33struct multilist_sublist {
34	/*
35	 * The mutex used internally to implement thread safe insertions
36	 * and removals to this individual sublist. It can also be locked
37	 * by a consumer using multilist_sublist_{lock,unlock}, which is
38	 * useful if a consumer needs to traverse the list in a thread
39	 * safe manner.
40	 */
41	kmutex_t	mls_lock;
42	/*
43	 * The actual list object containing all objects in this sublist.
44	 */
45	list_t		mls_list;
46	/*
47	 * Pad to cache line (64 bytes), in an effort to try and prevent
48	 * cache line contention.
49	 */
50	uint8_t		mls_pad[24];
51};
52
53struct multilist {
54	/*
55	 * This is used to get to the multilist_node_t structure given
56	 * the void *object contained on the list.
57	 */
58	size_t				ml_offset;
59	/*
60	 * The number of sublists used internally by this multilist.
61	 */
62	uint64_t			ml_num_sublists;
63	/*
64	 * The array of pointers to the actual sublists.
65	 */
66	multilist_sublist_t		*ml_sublists;
67	/*
68	 * Pointer to function which determines the sublist to use
69	 * when inserting and removing objects from this multilist.
70	 * Please see the comment above multilist_create for details.
71	 */
72	multilist_sublist_index_func_t	*ml_index_func;
73};
74
75void multilist_destroy(multilist_t *);
76multilist_t *multilist_create(size_t, size_t, multilist_sublist_index_func_t *);
77
78void multilist_insert(multilist_t *, void *);
79void multilist_remove(multilist_t *, void *);
80int  multilist_is_empty(multilist_t *);
81
82unsigned int multilist_get_num_sublists(multilist_t *);
83unsigned int multilist_get_random_index(multilist_t *);
84
85multilist_sublist_t *multilist_sublist_lock(multilist_t *, unsigned int);
86multilist_sublist_t *multilist_sublist_lock_obj(multilist_t *, void *);
87void multilist_sublist_unlock(multilist_sublist_t *);
88
89void multilist_sublist_insert_head(multilist_sublist_t *, void *);
90void multilist_sublist_insert_tail(multilist_sublist_t *, void *);
91void multilist_sublist_move_forward(multilist_sublist_t *mls, void *obj);
92void multilist_sublist_remove(multilist_sublist_t *, void *);
93int  multilist_sublist_is_empty(multilist_sublist_t *);
94int  multilist_sublist_is_empty_idx(multilist_t *, unsigned int);
95
96void *multilist_sublist_head(multilist_sublist_t *);
97void *multilist_sublist_tail(multilist_sublist_t *);
98void *multilist_sublist_next(multilist_sublist_t *, void *);
99void *multilist_sublist_prev(multilist_sublist_t *, void *);
100
101void multilist_link_init(multilist_node_t *);
102int  multilist_link_active(multilist_node_t *);
103
104#ifdef	__cplusplus
105}
106#endif
107
108#endif /* _SYS_MULTILIST_H */
109