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