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