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, 2014 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 *);
76void multilist_create(multilist_t *, size_t, size_t, unsigned int,
77 multilist_sublist_index_func_t *);
78
79void multilist_insert(multilist_t *, void *);
80void multilist_remove(multilist_t *, void *);
81int multilist_is_empty(multilist_t *);
82
83unsigned int multilist_get_num_sublists(multilist_t *);
84unsigned int multilist_get_random_index(multilist_t *);
85
86multilist_sublist_t *multilist_sublist_lock(multilist_t *, unsigned int);
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 *);
93
94void *multilist_sublist_head(multilist_sublist_t *);
95void *multilist_sublist_tail(multilist_sublist_t *);
96void *multilist_sublist_next(multilist_sublist_t *, void *);
97void *multilist_sublist_prev(multilist_sublist_t *, void *);
98
99void multilist_link_init(multilist_node_t *);
100int multilist_link_active(multilist_node_t *);
101
102#ifdef __cplusplus
103}
104#endif
105
106#endif /* _SYS_MULTILIST_H */
107