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