]>
git.proxmox.com Git - mirror_spl.git/blob - include/list.h
1 /*****************************************************************************
2 * $Id: list.h 2899 2002-12-11 19:00:36Z dun $
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>.
8 * This file is from LSD-Tools, the LLNL Software Development Toolbox.
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)
15 * LSD-Tools is distributed in the hope that it will be useful, but WITHOUT
16 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
20 * You should have received a copy of the GNU General Public License along
21 * with LSD-Tools; if not, write to the Free Software Foundation, Inc.,
22 * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA.
23 *****************************************************************************/
34 * If NDEBUG is not defined, internal debug code will be enabled. This is
35 * intended for development use only and production code should define NDEBUG.
37 * If WITH_LSD_FATAL_ERROR_FUNC is defined, the linker will expect to
38 * find an external lsd_fatal_error(file,line,mesg) function. By default,
39 * lsd_fatal_error(file,line,mesg) is a macro definition that outputs an
40 * error message to stderr. This macro may be redefined to invoke another
43 * If WITH_LSD_NOMEM_ERROR_FUNC is defined, the linker will expect to
44 * find an external lsd_nomem_error(file,line,mesg) function. By default,
45 * lsd_nomem_error(file,line,mesg) is a macro definition that returns NULL.
46 * This macro may be redefined to invoke another routine instead.
48 * If WITH_PTHREADS is defined, these routines will be thread-safe.
56 typedef struct list
* List
;
58 * List opaque data type.
61 typedef struct listIterator
* ListIterator
;
63 * List Iterator opaque data type.
66 typedef void (*ListDelF
) (void *x
);
68 * Function prototype to deallocate data stored in a list.
69 * This function is responsible for freeing all memory associated
70 * with an item, including all subordinate items (if applicable).
73 typedef int (*ListCmpF
) (void *x
, void *y
);
75 * Function prototype for comparing two items in a list.
76 * Returns less-than-zero if (x<y), zero if (x==y), and
77 * greather-than-zero if (x>y).
80 typedef int (*ListFindF
) (void *x
, void *key
);
82 * Function prototype for matching items in a list.
83 * Returns non-zero if (x==key); o/w returns zero.
86 typedef int (*ListForF
) (void *x
, void *arg
);
88 * Function prototype for operating on each item in a list.
89 * Returns less-than-zero on error.
93 /*******************************
94 * General-Purpose Functions *
95 *******************************/
97 List
list_create (ListDelF f
);
99 * Creates and returns a new empty list, or lsd_nomem_error() on failure.
100 * The deletion function [f] is used to deallocate memory used by items
101 * in the list; if this is NULL, memory associated with these items
102 * will not be freed when the list is destroyed.
103 * Note: Abandoning a list without calling list_destroy() will result
107 void list_destroy (List l
);
109 * Destroys list [l], freeing memory used for list iterators and the
110 * list itself; if a deletion function was specified when the list
111 * was created, it will be called for each item in the list.
114 int list_is_empty (List l
);
116 * Returns non-zero if list [l] is empty; o/w returns zero.
119 int list_count (List l
);
121 * Returns the number of items in list [l].
125 /***************************
126 * List Access Functions *
127 ***************************/
129 void * list_append (List l
, void *x
);
131 * Inserts data [x] at the end of list [l].
132 * Returns the data's ptr, or lsd_nomem_error() if insertion failed.
135 void * list_prepend (List l
, void *x
);
137 * Inserts data [x] at the beginning of list [l].
138 * Returns the data's ptr, or lsd_nomem_error() if insertion failed.
141 void * list_find_first (List l
, ListFindF f
, void *key
);
143 * Traverses list [l] using [f] to match each item with [key].
144 * Returns a ptr to the first item for which the function [f]
145 * returns non-zero, or NULL if no such item is found.
146 * Note: This function differs from list_find() in that it does not require
147 * a list iterator; it should only be used when all list items are known
148 * to be unique (according to the function [f]).
151 int list_delete_all (List l
, ListFindF f
, void *key
);
153 * Traverses list [l] using [f] to match each item with [key].
154 * Removes all items from the list for which the function [f] returns
155 * non-zero; if a deletion function was specified when the list was
156 * created, it will be called to deallocate each item being removed.
157 * Returns a count of the number of items removed from the list.
160 int list_for_each (List l
, ListForF f
, void *arg
);
162 * For each item in list [l], invokes the function [f] with [arg].
163 * Returns a count of the number of items on which [f] was invoked.
164 * If [f] returns <0 for a given item, the iteration is aborted and the
165 * function returns the negative of that item's position in the list.
168 void list_sort (List l
, ListCmpF f
);
170 * Sorts list [l] into ascending order according to the function [f].
171 * Note: Sorting a list resets all iterators associated with the list.
172 * Note: The sort algorithm is stable.
176 /****************************
177 * Stack Access Functions *
178 ****************************/
180 void * list_push (List l
, void *x
);
182 * Pushes data [x] onto the top of stack [l].
183 * Returns the data's ptr, or lsd_nomem_error() if insertion failed.
186 void * list_pop (List l
);
188 * Pops the data item at the top of the stack [l].
189 * Returns the data's ptr, or NULL if the stack is empty.
192 void * list_peek (List l
);
194 * Peeks at the data item at the top of the stack (or head of the queue) [l].
195 * Returns the data's ptr, or NULL if the stack (or queue) is empty.
196 * Note: The item is not removed from the list.
200 /****************************
201 * Queue Access Functions *
202 ****************************/
204 void * list_enqueue (List l
, void *x
);
206 * Enqueues data [x] at the tail of queue [l].
207 * Returns the data's ptr, or lsd_nomem_error() if insertion failed.
210 void * list_dequeue (List l
);
212 * Dequeues the data item at the head of the queue [l].
213 * Returns the data's ptr, or NULL if the queue is empty.
217 /*****************************
218 * List Iterator Functions *
219 *****************************/
221 ListIterator
list_iterator_create (List l
);
223 * Creates and returns a list iterator for non-destructively traversing
224 * list [l], or lsd_nomem_error() on failure.
227 void list_iterator_reset (ListIterator i
);
229 * Resets the list iterator [i] to start traversal at the beginning
233 void list_iterator_destroy (ListIterator i
);
235 * Destroys the list iterator [i]; list iterators not explicitly destroyed
236 * in this manner will be destroyed when the list is deallocated via
240 void * list_next (ListIterator i
);
242 * Returns a ptr to the next item's data,
243 * or NULL once the end of the list is reached.
244 * Example: i=list_iterator_create(i); while ((x=list_next(i))) {...}
247 void * list_insert (ListIterator i
, void *x
);
249 * Inserts data [x] immediately before the last item returned via list
250 * iterator [i]; once the list iterator reaches the end of the list,
251 * insertion is made at the list's end.
252 * Returns the data's ptr, or lsd_nomem_error() if insertion failed.
255 void * list_find (ListIterator i
, ListFindF f
, void *key
);
257 * Traverses the list from the point of the list iterator [i]
258 * using [f] to match each item with [key].
259 * Returns a ptr to the next item for which the function [f]
260 * returns non-zero, or NULL once the end of the list is reached.
261 * Example: i=list_iterator_reset(i); while ((x=list_find(i,f,k))) {...}
264 void * list_remove (ListIterator i
);
266 * Removes from the list the last item returned via list iterator [i]
267 * and returns the data's ptr.
268 * Note: The client is responsible for freeing the returned data.
271 int list_delete (ListIterator i
);
273 * Removes from the list the last item returned via list iterator [i];
274 * if a deletion function was specified when the list was created,
275 * it will be called to deallocate the item being removed.
276 * Returns a count of the number of items removed from the list
277 * (ie, '1' if the item was removed, and '0' otherwise).
281 #endif /* !LSD_LIST_H */