1 /***************************************************************************** 2 * list.h 3 ***************************************************************************** 4 * Copyright (C) 2001-2002 The Regents of the University of California. 5 * Produced at Lawrence Livermore National Laboratory (cf, DISCLAIMER). 6 * Written by Chris Dunlap <cdunlap@llnl.gov>. 7 * 8 * This file is from LSD-Tools, the LLNL Software Development Toolbox. 9 * 10 * LSD-Tools is free software; you can redistribute it and/or modify it under 11 * the terms of the GNU General Public License as published by the Free 12 * Software Foundation; either version 2 of the License, or (at your option) 13 * any later version. 14 * 15 * In addition, as a special exception, the copyright holders give permission 16 * to link the code of portions of this program with the OpenSSL library under 17 * certain conditions as described in each individual source file, and 18 * distribute linked combinations including the two. You must obey the GNU 19 * General Public License in all respects for all of the code used other than 20 * OpenSSL. If you modify file(s) with this exception, you may extend this 21 * exception to your version of the file(s), but you are not obligated to do 22 * so. If you do not wish to do so, delete this exception statement from your 23 * version. If you delete this exception statement from all source files in 24 * the program, then also delete it here. 25 * 26 * LSD-Tools is distributed in the hope that it will be useful, but WITHOUT 27 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 28 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for 29 * more details. 30 * 31 * You should have received a copy of the GNU General Public License along 32 * with LSD-Tools; if not, write to the Free Software Foundation, Inc., 33 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. 34 *****************************************************************************/ 35 36 #ifndef LSD_LIST_H 37 #define LSD_LIST_H 38 39 #define FREE_NULL_LIST(_X) \ 40 do { \ 41 if (_X) list_destroy (_X); \ 42 _X = NULL; \ 43 } while (0) 44 45 /**************** 46 * Data Types * 47 ****************/ 48 49 #ifndef __list_datatypes_defined 50 # define __list_datatypes_defined 51 typedef struct xlist *List; 52 53 /* 54 * List opaque data type. 55 */ 56 57 /* 58 * List Iterator opaque data type. 59 */ 60 typedef struct listIterator *ListIterator; 61 62 /* 63 * Function prototype to deallocate data stored in a list. 64 * This function is responsible for freeing all memory associated 65 * with an item, including all subordinate items (if applicable). 66 */ 67 typedef void (*ListDelF) (void *x); 68 69 /* 70 * Function prototype for comparing two items in a list. 71 * Returns less-than-zero if (x<y), zero if (x==y), and 72 * greather-than-zero if (x>y). 73 */ 74 typedef int (*ListCmpF) (void *x, void *y); 75 76 /* 77 * Function prototype for matching items in a list. 78 * Returns non-zero if (x==key); o/w returns zero. 79 */ 80 typedef int (*ListFindF) (void *x, void *key); 81 82 /* 83 * Function prototype for operating on each item in a list. 84 * Returns less-than-zero on error. 85 */ 86 typedef int (*ListForF) (void *x, void *arg); 87 88 #endif 89 90 /******************************* 91 * General-Purpose Functions * 92 *******************************/ 93 94 /* 95 * Creates and returns a new empty list. 96 * The deletion function [f] is used to deallocate memory used by items 97 * in the list; if this is NULL, memory associated with these items 98 * will not be freed when the list is destroyed. 99 * Note: Abandoning a list without calling list_destroy() will result 100 * in a memory leak. 101 */ 102 List list_create(ListDelF f); 103 104 /* 105 * Destroys list [l], freeing memory used for list iterators and the 106 * list itself; if a deletion function was specified when the list 107 * was created, it will be called for each item in the list. 108 */ 109 void list_destroy(List l); 110 111 /* 112 * Returns non-zero if list [l] is empty; o/w returns zero. 113 */ 114 int list_is_empty(List l); 115 116 /* 117 * Return the number of items in list [l]. 118 * If [l] is NULL, return 0. 119 */ 120 int list_count(List l); 121 122 /* 123 * Create new shallow copy of list [l] pointers, without destructor. 124 * 125 * The list created is intended to allow manipulation of the list without 126 * affecting the real list (such as sorting). 127 * 128 * Warning: destruction of this list will not free members of [l]. 129 * Warning: This list is only valid while [l] is unchanged. 130 */ 131 List list_shallow_copy(List l); 132 133 /*************************** 134 * List Access Functions * 135 ***************************/ 136 137 /* 138 * Inserts data [x] at the end of list [l]. 139 * Returns the data's ptr. 140 */ 141 void *list_append(List l, void *x); 142 143 /* 144 * Inserts list [sub] at the end of list [l]. 145 * Note: list [l] must have a destroy function of NULL. 146 * Returns a count of the number of items added to list [l]. 147 */ 148 int list_append_list(List l, List sub); 149 150 /* 151 * Pops off list [sub] and appends data at the end of list [l]. 152 * Note: list [l] must have the same destroy function as list [sub]. 153 * Note: list [sub] will be returned empty, but not destroyed. 154 * Returns a count of the number of items added to list [l]. 155 */ 156 int list_transfer(List l, List sub); 157 158 /* 159 * Pops off list [sub] to [l] with maximum number of entries. 160 * Set max = -1 to transfer all entries. 161 * Note: list [l] must have the same destroy function as list [sub]. 162 * Note: list [sub] may be returned empty, but not destroyed. 163 * Returns a count of the number of items added to list [l]. 164 */ 165 int list_transfer_max(List l, List sub, int max); 166 167 /* 168 * Inserts data [x] at the beginning of list [l]. 169 * Returns the data's ptr. 170 */ 171 void *list_prepend(List l, void *x); 172 173 /* 174 * Traverses list [l] using [f] to match each item with [key]. 175 * Returns a ptr to the first item for which the function [f] 176 * returns non-zero, or NULL if no such item is found. 177 * Note: This function differs from list_find() in that it does not require 178 * a list iterator; it should only be used when all list items are known 179 * to be unique (according to the function [f]). 180 */ 181 void *list_find_first(List l, ListFindF f, void *key); 182 183 /* 184 * Traverses list [l] using [f] to match each item with [key]. 185 * Returns a ptr to the first item for which the function [f] 186 * returns non-zero and removes it from the list, or NULL if no such item is 187 * found. 188 * Note: This function differs from list_remove() in that it does not require 189 * a list iterator; it should only be used when all list items are known 190 * to be unique (according to the function [f]). 191 */ 192 void *list_remove_first(List l, ListFindF f, void *key); 193 194 /* 195 * Traverses list [l] using [f] to match each item with [key]. 196 * Removes all items from the list for which the function [f] returns 197 * non-zero; if a deletion function was specified when the list was 198 * created, it will be called to deallocate each item being removed. 199 * Returns a count of the number of items removed from the list. 200 */ 201 int list_delete_all(List l, ListFindF f, void *key); 202 203 /* 204 * For each item in list [l], invokes the function [f] with [arg]. 205 * Returns a count of the number of items on which [f] was invoked. 206 * If [f] returns <0 for a given item, the iteration is aborted and the 207 * function returns the negative of that item's position in the list. 208 */ 209 int list_for_each(List l, ListForF f, void *arg); 210 211 /* 212 * For each item in list [l], invokes the function [f] with [arg]. 213 * Returns a count of the number of items on which [f] was invoked. 214 * If [f] returns <0 for a given item, the iteration is NOT aborted but the 215 * function will return -1, else return 0. 216 */ 217 int list_for_each_nobreak(List l, ListForF f, void *arg); 218 219 /* 220 * For each item in list [l], invokes the function [f] with [arg]. 221 * Will process up to [max] number of list items, or set [max] to -1 for all. 222 * [max] will be return to the number of unprocessed items remaining. 223 * Returns a count of the number of items on which [f] was invoked. 224 * If [f] returns <0 for a given item, the iteration is aborted and the 225 * function returns the negative of that item's position in the list. 226 */ 227 int list_for_each_max(List l, int *max, ListForF f, void *arg, 228 int break_on_fail); 229 230 /* 231 * Traverses list [l] and removes all items in list 232 * If a deletion function was specified when the list was 233 * created, it will be called to deallocate each item being removed. 234 * Returns a count of the number of items removed from the list. 235 */ 236 int list_flush(List l); 237 238 /* 239 * Sorts list [l] into ascending order according to the function [f]. 240 * Note: Sorting a list resets all iterators associated with the list. 241 * This function uses the libC qsort() algorithm. 242 */ 243 void list_sort(List l, ListCmpF f); 244 245 /**************************** 246 * Stack Access Functions * 247 ****************************/ 248 249 /* 250 * Pushes data [x] onto the top of stack [l]. 251 * Returns the data's ptr. 252 */ 253 void *list_push(List l, void *x); 254 255 /* 256 * Pops the data item at the top of the stack [l]. 257 * Returns the data's ptr, or NULL if the stack is empty. 258 */ 259 void *list_pop(List l); 260 261 /* 262 * Peeks at the data item at the top of the stack (or head of the queue) [l]. 263 * Returns the data's ptr, or NULL if the stack (or queue) is empty. 264 * Note: The item is not removed from the list. 265 */ 266 void *list_peek(List l); 267 268 /**************************** 269 * Queue Access Functions * 270 ****************************/ 271 272 /* 273 * Enqueues data [x] at the tail of queue [l]. 274 * Returns the data's ptr. 275 */ 276 void *list_enqueue(List l, void *x); 277 278 /* 279 * Dequeues the data item at the head of the queue [l]. 280 * Returns the data's ptr, or NULL if the queue is empty. 281 */ 282 void *list_dequeue(List l); 283 284 285 /***************************** 286 * List Iterator Functions * 287 *****************************/ 288 289 /* 290 * Creates and returns a list iterator for non-destructively traversing 291 * list [l]. 292 */ 293 ListIterator list_iterator_create(List l); 294 295 /* 296 * Resets the list iterator [i] to start traversal at the beginning 297 * of the list. 298 */ 299 void list_iterator_reset(ListIterator i); 300 301 /* 302 * Destroys the list iterator [i]; list iterators not explicitly destroyed 303 * in this manner will be destroyed when the list is deallocated via 304 * list_destroy(). 305 */ 306 void list_iterator_destroy(ListIterator i); 307 308 /* 309 * Returns a ptr to the next item's data, 310 * or NULL once the end of the list is reached. 311 * Example: i=list_iterator_create(i); while ((x=list_next(i))) {...} 312 */ 313 void *list_next(ListIterator i); 314 315 /* 316 * Returns a ptr to the next item's data WITHOUT advancing the pointer, 317 * or NULL once the end of the list is reached. 318 */ 319 void *list_peek_next(ListIterator i); 320 321 /* 322 * Inserts data [x] immediately before the last item returned via list 323 * iterator [i]; once the list iterator reaches the end of the list, 324 * insertion is made at the list's end. 325 * Returns the data's ptr. 326 */ 327 void *list_insert(ListIterator i, void *x); 328 329 /* 330 * Traverses the list from the point of the list iterator [i] 331 * using [f] to match each item with [key]. 332 * Returns a ptr to the next item for which the function [f] 333 * returns non-zero, or NULL once the end of the list is reached. 334 * Example: i=list_iterator_reset(i); while ((x=list_find(i,f,k))) {...} 335 */ 336 void *list_find(ListIterator i, ListFindF f, void *key); 337 338 /* 339 * Removes from the list the last item returned via list iterator [i] 340 * and returns the data's ptr. 341 * Note: The client is responsible for freeing the returned data. 342 */ 343 void *list_remove(ListIterator i); 344 345 /* 346 * Removes from the list the last item returned via list iterator [i]; 347 * if a deletion function was specified when the list was created, 348 * it will be called to deallocate the item being removed. 349 * Returns a count of the number of items removed from the list 350 * (ie, '1' if the item was removed, and '0' otherwise). 351 */ 352 int list_delete_item(ListIterator i); 353 354 #endif /* !LSD_LIST_H */ 355