1*0Sstevel@tonic-gate /* 2*0Sstevel@tonic-gate * CDDL HEADER START 3*0Sstevel@tonic-gate * 4*0Sstevel@tonic-gate * The contents of this file are subject to the terms of the 5*0Sstevel@tonic-gate * Common Development and Distribution License, Version 1.0 only 6*0Sstevel@tonic-gate * (the "License"). You may not use this file except in compliance 7*0Sstevel@tonic-gate * with the License. 8*0Sstevel@tonic-gate * 9*0Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10*0Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing. 11*0Sstevel@tonic-gate * See the License for the specific language governing permissions 12*0Sstevel@tonic-gate * and limitations under the License. 13*0Sstevel@tonic-gate * 14*0Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each 15*0Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16*0Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the 17*0Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying 18*0Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner] 19*0Sstevel@tonic-gate * 20*0Sstevel@tonic-gate * CDDL HEADER END 21*0Sstevel@tonic-gate */ 22*0Sstevel@tonic-gate /* 23*0Sstevel@tonic-gate * Copyright 2003 Sun Microsystems, Inc. All rights reserved. 24*0Sstevel@tonic-gate * Use is subject to license terms. 25*0Sstevel@tonic-gate */ 26*0Sstevel@tonic-gate 27*0Sstevel@tonic-gate #ifndef _VOLUME_DLIST_H 28*0Sstevel@tonic-gate #define _VOLUME_DLIST_H 29*0Sstevel@tonic-gate 30*0Sstevel@tonic-gate #pragma ident "%Z%%M% %I% %E% SMI" 31*0Sstevel@tonic-gate 32*0Sstevel@tonic-gate #ifdef __cplusplus 33*0Sstevel@tonic-gate extern "C" { 34*0Sstevel@tonic-gate #endif 35*0Sstevel@tonic-gate 36*0Sstevel@tonic-gate #include <sys/types.h> 37*0Sstevel@tonic-gate 38*0Sstevel@tonic-gate /* 39*0Sstevel@tonic-gate * Structure defining a doubly linked list of arbitrary objects 40*0Sstevel@tonic-gate */ 41*0Sstevel@tonic-gate typedef struct dlist { 42*0Sstevel@tonic-gate 43*0Sstevel@tonic-gate struct dlist *next; 44*0Sstevel@tonic-gate struct dlist *prev; 45*0Sstevel@tonic-gate void *obj; 46*0Sstevel@tonic-gate 47*0Sstevel@tonic-gate } dlist_t; 48*0Sstevel@tonic-gate 49*0Sstevel@tonic-gate /* 50*0Sstevel@tonic-gate * module globals 51*0Sstevel@tonic-gate */ 52*0Sstevel@tonic-gate extern const boolean_t ASCENDING; 53*0Sstevel@tonic-gate extern const boolean_t DESCENDING; 54*0Sstevel@tonic-gate extern const boolean_t AT_TAIL; 55*0Sstevel@tonic-gate extern const boolean_t AT_HEAD; 56*0Sstevel@tonic-gate 57*0Sstevel@tonic-gate /* from types.h */ 58*0Sstevel@tonic-gate #ifndef TRUE 59*0Sstevel@tonic-gate #define TRUE B_TRUE 60*0Sstevel@tonic-gate #endif 61*0Sstevel@tonic-gate 62*0Sstevel@tonic-gate #ifndef FALSE 63*0Sstevel@tonic-gate #define FALSE B_FALSE 64*0Sstevel@tonic-gate #endif 65*0Sstevel@tonic-gate 66*0Sstevel@tonic-gate /* 67*0Sstevel@tonic-gate * doubly linked list utility methods 68*0Sstevel@tonic-gate */ 69*0Sstevel@tonic-gate 70*0Sstevel@tonic-gate /* 71*0Sstevel@tonic-gate * count the number of elements currently in the list 72*0Sstevel@tonic-gate */ 73*0Sstevel@tonic-gate extern int dlist_length(dlist_t *list); 74*0Sstevel@tonic-gate 75*0Sstevel@tonic-gate /* 76*0Sstevel@tonic-gate * Traverse the list pointed to by head and free each 77*0Sstevel@tonic-gate * list node. If freefunc is non-NULL, call freefunc 78*0Sstevel@tonic-gate * for each node's object. 79*0Sstevel@tonic-gate */ 80*0Sstevel@tonic-gate extern void dlist_free_items(dlist_t *list, void (freefunc(void *))); 81*0Sstevel@tonic-gate 82*0Sstevel@tonic-gate /* 83*0Sstevel@tonic-gate * append item to list. If atend is true, the item is 84*0Sstevel@tonic-gate * added at the end of the list, otherwise it is added 85*0Sstevel@tonic-gate * at the beginning. 86*0Sstevel@tonic-gate * 87*0Sstevel@tonic-gate * returns the possibly changed head of the list. 88*0Sstevel@tonic-gate */ 89*0Sstevel@tonic-gate extern dlist_t *dlist_append( 90*0Sstevel@tonic-gate dlist_t *item, 91*0Sstevel@tonic-gate dlist_t *list, 92*0Sstevel@tonic-gate boolean_t atend); 93*0Sstevel@tonic-gate 94*0Sstevel@tonic-gate /* 95*0Sstevel@tonic-gate * Create a dlist_t element for the given object and append to list. 96*0Sstevel@tonic-gate * 97*0Sstevel@tonic-gate * @param object 98*0Sstevel@tonic-gate * the obj member of the dlist_t element to be created 99*0Sstevel@tonic-gate * 100*0Sstevel@tonic-gate * @param list 101*0Sstevel@tonic-gate * the list to which to append the new dlist_t element 102*0Sstevel@tonic-gate * 103*0Sstevel@tonic-gate * @param attail 104*0Sstevel@tonic-gate * whether to append at the beginning (AT_HEAD) or end 105*0Sstevel@tonic-gate * (AT_TAIL) of the list 106*0Sstevel@tonic-gate * 107*0Sstevel@tonic-gate * @return 0 108*0Sstevel@tonic-gate * if successful 109*0Sstevel@tonic-gate * 110*0Sstevel@tonic-gate * @return ENOMEM 111*0Sstevel@tonic-gate * if a dlist_t could not be allocated 112*0Sstevel@tonic-gate */ 113*0Sstevel@tonic-gate extern int dlist_append_object( 114*0Sstevel@tonic-gate void *object, 115*0Sstevel@tonic-gate dlist_t **list, 116*0Sstevel@tonic-gate boolean_t attail); 117*0Sstevel@tonic-gate 118*0Sstevel@tonic-gate /* 119*0Sstevel@tonic-gate * Appends list2 to the end of list1. 120*0Sstevel@tonic-gate * 121*0Sstevel@tonic-gate * Returns the resulting list. 122*0Sstevel@tonic-gate */ 123*0Sstevel@tonic-gate extern dlist_t *dlist_append_list( 124*0Sstevel@tonic-gate dlist_t *list1, 125*0Sstevel@tonic-gate dlist_t *list2); 126*0Sstevel@tonic-gate 127*0Sstevel@tonic-gate /* 128*0Sstevel@tonic-gate * Remove the first node pointing to same content as item from list, 129*0Sstevel@tonic-gate * clear it's next and prev pointers, return new list head. 130*0Sstevel@tonic-gate * 131*0Sstevel@tonic-gate * The caller is responsible for freeing the removed item if it is no 132*0Sstevel@tonic-gate * longer needed. 133*0Sstevel@tonic-gate * 134*0Sstevel@tonic-gate * The comparison function should be of the form: 135*0Sstevel@tonic-gate * 136*0Sstevel@tonic-gate * int compare(void *obj1, void* obj2); 137*0Sstevel@tonic-gate * 138*0Sstevel@tonic-gate * When called, obj1 will be the object passed into 139*0Sstevel@tonic-gate * dlist_remove_equivalent_item and obj2 will be an object pointed to by an 140*0Sstevel@tonic-gate * item in the list. 141*0Sstevel@tonic-gate * 142*0Sstevel@tonic-gate * The function should return 0 if the two objects are equivalent The 143*0Sstevel@tonic-gate * function should return nonzero otherwise 144*0Sstevel@tonic-gate * 145*0Sstevel@tonic-gate * @param list 146*0Sstevel@tonic-gate * the list containing the item to remove 147*0Sstevel@tonic-gate * 148*0Sstevel@tonic-gate * @param obj 149*0Sstevel@tonic-gate * the object with which to compare each item 150*0Sstevel@tonic-gate * 151*0Sstevel@tonic-gate * @param compare 152*0Sstevel@tonic-gate * the comparison function, passed obj and the obj member 153*0Sstevel@tonic-gate * of each item, to return 0 if item should be removed 154*0Sstevel@tonic-gate * 155*0Sstevel@tonic-gate * @param removed 156*0Sstevel@tonic-gate * RETURN: the removed item, or NULL if none was found 157*0Sstevel@tonic-gate * 158*0Sstevel@tonic-gate * @return the first element of the resulting list 159*0Sstevel@tonic-gate */ 160*0Sstevel@tonic-gate extern dlist_t *dlist_remove_equivalent_item( 161*0Sstevel@tonic-gate dlist_t *list, 162*0Sstevel@tonic-gate void *obj, 163*0Sstevel@tonic-gate int (compare)(void *obj1, void *obj2), 164*0Sstevel@tonic-gate dlist_t **removed); 165*0Sstevel@tonic-gate 166*0Sstevel@tonic-gate /* 167*0Sstevel@tonic-gate * Remove an item from its list. Return the resulting list. 168*0Sstevel@tonic-gate * 169*0Sstevel@tonic-gate * @param item 170*0Sstevel@tonic-gate * the item to remove, with prev and next pointers 171*0Sstevel@tonic-gate * set to NULL 172*0Sstevel@tonic-gate * 173*0Sstevel@tonic-gate * @return the first element of the resulting list 174*0Sstevel@tonic-gate */ 175*0Sstevel@tonic-gate dlist_t * 176*0Sstevel@tonic-gate dlist_remove( 177*0Sstevel@tonic-gate dlist_t *item); 178*0Sstevel@tonic-gate 179*0Sstevel@tonic-gate /* 180*0Sstevel@tonic-gate * allocates memory for a new list item. The list item will 181*0Sstevel@tonic-gate * point at obj. 182*0Sstevel@tonic-gate * 183*0Sstevel@tonic-gate * returns the new list item. 184*0Sstevel@tonic-gate */ 185*0Sstevel@tonic-gate extern dlist_t *dlist_new_item(void *obj); 186*0Sstevel@tonic-gate 187*0Sstevel@tonic-gate /* 188*0Sstevel@tonic-gate * inserts item in the correct position within the list based on 189*0Sstevel@tonic-gate * the comparison function. if ascending is true, the list will 190*0Sstevel@tonic-gate * be in ascending order, otherwise descending. 191*0Sstevel@tonic-gate * 192*0Sstevel@tonic-gate * the comparison function should be of the form: 193*0Sstevel@tonic-gate * 194*0Sstevel@tonic-gate * int compare(void *obj1, void *obj2); 195*0Sstevel@tonic-gate * 196*0Sstevel@tonic-gate * When called, obj1 will be the object pointed to by the item to 197*0Sstevel@tonic-gate * be added to the list, obj2 will be an object pointed to by an 198*0Sstevel@tonic-gate * item currently in the list. 199*0Sstevel@tonic-gate * 200*0Sstevel@tonic-gate * The function should return 0 if the two objects are equivalent 201*0Sstevel@tonic-gate * The function should return <0 if obj1 comes before obj2 202*0Sstevel@tonic-gate * The function should return >0 if obj1 comes after obj2 203*0Sstevel@tonic-gate * 204*0Sstevel@tonic-gate * dlist_insert_ordered returns the possibly changed head 205*0Sstevel@tonic-gate * of the list. 206*0Sstevel@tonic-gate */ 207*0Sstevel@tonic-gate extern dlist_t *dlist_insert_ordered( 208*0Sstevel@tonic-gate dlist_t *item, 209*0Sstevel@tonic-gate dlist_t *list, 210*0Sstevel@tonic-gate boolean_t ascending, 211*0Sstevel@tonic-gate int (compare)(void *obj1, void *obj2)); 212*0Sstevel@tonic-gate 213*0Sstevel@tonic-gate /* 214*0Sstevel@tonic-gate * Locates the item in the list which contains object. 215*0Sstevel@tonic-gate * 216*0Sstevel@tonic-gate * the comparison function should be of the form: 217*0Sstevel@tonic-gate * 218*0Sstevel@tonic-gate * int compare(void *obj1, void *obj2); 219*0Sstevel@tonic-gate * 220*0Sstevel@tonic-gate * When called, obj1 will be the input object, obj2 will be 221*0Sstevel@tonic-gate * an object pointed to by an item currently in the list. 222*0Sstevel@tonic-gate * 223*0Sstevel@tonic-gate * The function should return 0 if the two objects are equivalent 224*0Sstevel@tonic-gate * The function should return non-zero otherwise 225*0Sstevel@tonic-gate * 226*0Sstevel@tonic-gate * dlist_find() returns the found item or NULL if one was not found. 227*0Sstevel@tonic-gate */ 228*0Sstevel@tonic-gate extern dlist_t *dlist_find( 229*0Sstevel@tonic-gate dlist_t *list, 230*0Sstevel@tonic-gate void *obj, 231*0Sstevel@tonic-gate int (compare)(void *obj1, void *obj2)); 232*0Sstevel@tonic-gate 233*0Sstevel@tonic-gate /* 234*0Sstevel@tonic-gate * Determines if list has an item which contains object. 235*0Sstevel@tonic-gate * 236*0Sstevel@tonic-gate * the comparison function should be of the form: 237*0Sstevel@tonic-gate * 238*0Sstevel@tonic-gate * int compare(void *obj1, void *obj2); 239*0Sstevel@tonic-gate * 240*0Sstevel@tonic-gate * When called, obj1 will be the input object, obj2 will be 241*0Sstevel@tonic-gate * an object pointed to by an item currently in the list. 242*0Sstevel@tonic-gate * 243*0Sstevel@tonic-gate * The function should return 0 if the two objects are equivalent 244*0Sstevel@tonic-gate * The function should return non-zero otherwise 245*0Sstevel@tonic-gate * 246*0Sstevel@tonic-gate * dlist_contains() returns TRUE if the object is already 247*0Sstevel@tonic-gate * in the list or FALSE otherwise. 248*0Sstevel@tonic-gate */ 249*0Sstevel@tonic-gate extern boolean_t dlist_contains( 250*0Sstevel@tonic-gate dlist_t *list, 251*0Sstevel@tonic-gate void *obj, 252*0Sstevel@tonic-gate int (compare)(void *obj1, void *obj2)); 253*0Sstevel@tonic-gate 254*0Sstevel@tonic-gate /* 255*0Sstevel@tonic-gate * Order the given list such that the number of similar elements 256*0Sstevel@tonic-gate * adjacent to each other are minimized. Two elements are considered 257*0Sstevel@tonic-gate * similar if the given compare function returns 0. 258*0Sstevel@tonic-gate * 259*0Sstevel@tonic-gate * @param list 260*0Sstevel@tonic-gate * the list to order 261*0Sstevel@tonic-gate * 262*0Sstevel@tonic-gate * @param compare 263*0Sstevel@tonic-gate * the comparison function, passed the obj members 264*0Sstevel@tonic-gate * of two items, to return 0 if the items can be 265*0Sstevel@tonic-gate * considered similar 266*0Sstevel@tonic-gate * 267*0Sstevel@tonic-gate * @return the first element of the resulting list 268*0Sstevel@tonic-gate */ 269*0Sstevel@tonic-gate extern dlist_t * 270*0Sstevel@tonic-gate dlist_separate_similar_elements( 271*0Sstevel@tonic-gate dlist_t *list, 272*0Sstevel@tonic-gate int(*equals)(void *, void *)); 273*0Sstevel@tonic-gate 274*0Sstevel@tonic-gate #ifdef __cplusplus 275*0Sstevel@tonic-gate } 276*0Sstevel@tonic-gate #endif 277*0Sstevel@tonic-gate 278*0Sstevel@tonic-gate #endif /* _VOLUME_DLIST_H */ 279