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
25 extern "C" {
26 #endif
27 
28 typedef list_node_t multilist_node_t;
29 typedef struct multilist multilist_t;
30 typedef struct multilist_sublist multilist_sublist_t;
31 typedef unsigned int multilist_sublist_index_func_t(multilist_t *, void *);
32 
33 struct 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, in an effort to try and prevent cache line
48 	 * contention.
49 	 */
50 } ____cacheline_aligned;
51 
52 struct multilist {
53 	/*
54 	 * This is used to get to the multilist_node_t structure given
55 	 * the void *object contained on the list.
56 	 */
57 	size_t				ml_offset;
58 	/*
59 	 * The number of sublists used internally by this multilist.
60 	 */
61 	uint64_t			ml_num_sublists;
62 	/*
63 	 * The array of pointers to the actual sublists.
64 	 */
65 	multilist_sublist_t		*ml_sublists;
66 	/*
67 	 * Pointer to function which determines the sublist to use
68 	 * when inserting and removing objects from this multilist.
69 	 * Please see the comment above multilist_create for details.
70 	 */
71 	multilist_sublist_index_func_t	*ml_index_func;
72 };
73 
74 void multilist_destroy(multilist_t *);
75 multilist_t *multilist_create(size_t, size_t, multilist_sublist_index_func_t *);
76 
77 void multilist_insert(multilist_t *, void *);
78 void multilist_remove(multilist_t *, void *);
79 int  multilist_is_empty(multilist_t *);
80 
81 unsigned int multilist_get_num_sublists(multilist_t *);
82 unsigned int multilist_get_random_index(multilist_t *);
83 
84 multilist_sublist_t *multilist_sublist_lock(multilist_t *, unsigned int);
85 multilist_sublist_t *multilist_sublist_lock_obj(multilist_t *, void *);
86 void multilist_sublist_unlock(multilist_sublist_t *);
87 
88 void multilist_sublist_insert_head(multilist_sublist_t *, void *);
89 void multilist_sublist_insert_tail(multilist_sublist_t *, void *);
90 void multilist_sublist_move_forward(multilist_sublist_t *mls, void *obj);
91 void multilist_sublist_remove(multilist_sublist_t *, void *);
92 int  multilist_sublist_is_empty(multilist_sublist_t *);
93 int  multilist_sublist_is_empty_idx(multilist_t *, unsigned int);
94 
95 void *multilist_sublist_head(multilist_sublist_t *);
96 void *multilist_sublist_tail(multilist_sublist_t *);
97 void *multilist_sublist_next(multilist_sublist_t *, void *);
98 void *multilist_sublist_prev(multilist_sublist_t *, void *);
99 
100 void multilist_link_init(multilist_node_t *);
101 int  multilist_link_active(multilist_node_t *);
102 
103 #ifdef	__cplusplus
104 }
105 #endif
106 
107 #endif /* _SYS_MULTILIST_H */
108