1244781f1SPrakash Surya /*
2244781f1SPrakash Surya  * CDDL HEADER START
3244781f1SPrakash Surya  *
4244781f1SPrakash Surya  * This file and its contents are supplied under the terms of the
5244781f1SPrakash Surya  * Common Development and Distribution License ("CDDL"), version 1.0.
6244781f1SPrakash Surya  * You may only use this file in accordance with the terms of version
7244781f1SPrakash Surya  * 1.0 of the CDDL.
8244781f1SPrakash Surya  *
9244781f1SPrakash Surya  * A full copy of the text of the CDDL should have accompanied this
10244781f1SPrakash Surya  * source.  A copy of the CDDL is also available via the Internet at
11244781f1SPrakash Surya  * http://www.illumos.org/license/CDDL.
12244781f1SPrakash Surya  *
13244781f1SPrakash Surya  * CDDL HEADER END
14244781f1SPrakash Surya  */
15244781f1SPrakash Surya /*
1610fbdecbSMatthew Ahrens  * Copyright (c) 2013, 2017 by Delphix. All rights reserved.
17244781f1SPrakash Surya  */
18244781f1SPrakash Surya 
19244781f1SPrakash Surya #ifndef	_SYS_MULTILIST_H
20244781f1SPrakash Surya #define	_SYS_MULTILIST_H
21244781f1SPrakash Surya 
22244781f1SPrakash Surya #include <sys/zfs_context.h>
23244781f1SPrakash Surya 
24244781f1SPrakash Surya #ifdef	__cplusplus
25244781f1SPrakash Surya extern "C" {
26244781f1SPrakash Surya #endif
27244781f1SPrakash Surya 
28244781f1SPrakash Surya typedef list_node_t multilist_node_t;
29244781f1SPrakash Surya typedef struct multilist multilist_t;
30244781f1SPrakash Surya typedef struct multilist_sublist multilist_sublist_t;
31244781f1SPrakash Surya typedef unsigned int multilist_sublist_index_func_t(multilist_t *, void *);
32244781f1SPrakash Surya 
33244781f1SPrakash Surya struct multilist_sublist {
34244781f1SPrakash Surya 	/*
35244781f1SPrakash Surya 	 * The mutex used internally to implement thread safe insertions
36244781f1SPrakash Surya 	 * and removals to this individual sublist. It can also be locked
37244781f1SPrakash Surya 	 * by a consumer using multilist_sublist_{lock,unlock}, which is
38244781f1SPrakash Surya 	 * useful if a consumer needs to traverse the list in a thread
39244781f1SPrakash Surya 	 * safe manner.
40244781f1SPrakash Surya 	 */
41244781f1SPrakash Surya 	kmutex_t	mls_lock;
42244781f1SPrakash Surya 	/*
43244781f1SPrakash Surya 	 * The actual list object containing all objects in this sublist.
44244781f1SPrakash Surya 	 */
45244781f1SPrakash Surya 	list_t		mls_list;
46244781f1SPrakash Surya 	/*
47244781f1SPrakash Surya 	 * Pad to cache line (64 bytes), in an effort to try and prevent
48244781f1SPrakash Surya 	 * cache line contention.
49244781f1SPrakash Surya 	 */
50244781f1SPrakash Surya 	uint8_t		mls_pad[24];
51244781f1SPrakash Surya };
52244781f1SPrakash Surya 
53244781f1SPrakash Surya struct multilist {
54244781f1SPrakash Surya 	/*
55244781f1SPrakash Surya 	 * This is used to get to the multilist_node_t structure given
56244781f1SPrakash Surya 	 * the void *object contained on the list.
57244781f1SPrakash Surya 	 */
58244781f1SPrakash Surya 	size_t				ml_offset;
59244781f1SPrakash Surya 	/*
60244781f1SPrakash Surya 	 * The number of sublists used internally by this multilist.
61244781f1SPrakash Surya 	 */
62244781f1SPrakash Surya 	uint64_t			ml_num_sublists;
63244781f1SPrakash Surya 	/*
64244781f1SPrakash Surya 	 * The array of pointers to the actual sublists.
65244781f1SPrakash Surya 	 */
66244781f1SPrakash Surya 	multilist_sublist_t		*ml_sublists;
67244781f1SPrakash Surya 	/*
68244781f1SPrakash Surya 	 * Pointer to function which determines the sublist to use
69244781f1SPrakash Surya 	 * when inserting and removing objects from this multilist.
70244781f1SPrakash Surya 	 * Please see the comment above multilist_create for details.
71244781f1SPrakash Surya 	 */
72244781f1SPrakash Surya 	multilist_sublist_index_func_t	*ml_index_func;
73244781f1SPrakash Surya };
74244781f1SPrakash Surya 
75244781f1SPrakash Surya void multilist_destroy(multilist_t *);
76*94c2d0ebSMatthew Ahrens multilist_t *multilist_create(size_t, size_t, multilist_sublist_index_func_t *);
77244781f1SPrakash Surya 
78244781f1SPrakash Surya void multilist_insert(multilist_t *, void *);
79244781f1SPrakash Surya void multilist_remove(multilist_t *, void *);
80244781f1SPrakash Surya int  multilist_is_empty(multilist_t *);
81244781f1SPrakash Surya 
82244781f1SPrakash Surya unsigned int multilist_get_num_sublists(multilist_t *);
83244781f1SPrakash Surya unsigned int multilist_get_random_index(multilist_t *);
84244781f1SPrakash Surya 
85244781f1SPrakash Surya multilist_sublist_t *multilist_sublist_lock(multilist_t *, unsigned int);
86*94c2d0ebSMatthew Ahrens multilist_sublist_t *multilist_sublist_lock_obj(multilist_t *, void *);
87244781f1SPrakash Surya void multilist_sublist_unlock(multilist_sublist_t *);
88244781f1SPrakash Surya 
89244781f1SPrakash Surya void multilist_sublist_insert_head(multilist_sublist_t *, void *);
90244781f1SPrakash Surya void multilist_sublist_insert_tail(multilist_sublist_t *, void *);
91244781f1SPrakash Surya void multilist_sublist_move_forward(multilist_sublist_t *mls, void *obj);
92244781f1SPrakash Surya void multilist_sublist_remove(multilist_sublist_t *, void *);
93244781f1SPrakash Surya 
94244781f1SPrakash Surya void *multilist_sublist_head(multilist_sublist_t *);
95244781f1SPrakash Surya void *multilist_sublist_tail(multilist_sublist_t *);
96244781f1SPrakash Surya void *multilist_sublist_next(multilist_sublist_t *, void *);
97244781f1SPrakash Surya void *multilist_sublist_prev(multilist_sublist_t *, void *);
98244781f1SPrakash Surya 
99244781f1SPrakash Surya void multilist_link_init(multilist_node_t *);
100244781f1SPrakash Surya int  multilist_link_active(multilist_node_t *);
101244781f1SPrakash Surya 
102244781f1SPrakash Surya #ifdef	__cplusplus
103244781f1SPrakash Surya }
104244781f1SPrakash Surya #endif
105244781f1SPrakash Surya 
106244781f1SPrakash Surya #endif /* _SYS_MULTILIST_H */
107