]>
git.proxmox.com Git - mirror_spl-debian.git/blob - lib/list.h
1 /*****************************************************************************
2 * Copyright (C) 2007-2010 Lawrence Livermore National Security, LLC.
3 * Copyright (C) 2001-2007 The Regents of the University of California.
4 * Produced at Lawrence Livermore National Laboratory (cf, DISCLAIMER).
5 * 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, see <http://www.gnu.org/licenses/>.
22 *****************************************************************************/
32 * If NDEBUG is not defined, internal debug code will be enabled. This is
33 * intended for development use only and production code should define NDEBUG.
35 * If WITH_LSD_FATAL_ERROR_FUNC is defined, the linker will expect to
36 * find an external lsd_fatal_error(file,line,mesg) function. By default,
37 * lsd_fatal_error(file,line,mesg) is a macro definition that outputs an
38 * error message to stderr. This macro may be redefined to invoke another
41 * If WITH_LSD_NOMEM_ERROR_FUNC is defined, the linker will expect to
42 * find an external lsd_nomem_error(file,line,mesg) function. By default,
43 * lsd_nomem_error(file,line,mesg) is a macro definition that returns NULL.
44 * This macro may be redefined to invoke another routine instead.
46 * If WITH_PTHREADS is defined, these routines will be thread-safe.
54 typedef struct list
* List
;
56 * List opaque data type.
59 typedef struct listIterator
* ListIterator
;
61 * List Iterator opaque data type.
64 typedef void (*ListDelF
) (void *x
);
66 * Function prototype to deallocate data stored in a list.
67 * This function is responsible for freeing all memory associated
68 * with an item, including all subordinate items (if applicable).
71 typedef int (*ListCmpF
) (void *x
, void *y
);
73 * Function prototype for comparing two items in a list.
74 * Returns less-than-zero if (x<y), zero if (x==y), and
75 * greather-than-zero if (x>y).
78 typedef int (*ListFindF
) (void *x
, void *key
);
80 * Function prototype for matching items in a list.
81 * Returns non-zero if (x==key); o/w returns zero.
84 typedef int (*ListForF
) (void *x
, void *arg
);
86 * Function prototype for operating on each item in a list.
87 * Returns less-than-zero on error.
91 /*******************************
92 * General-Purpose Functions *
93 *******************************/
95 List
list_create (ListDelF f
);
97 * Creates and returns a new empty list, or lsd_nomem_error() on failure.
98 * The deletion function [f] is used to deallocate memory used by items
99 * in the list; if this is NULL, memory associated with these items
100 * will not be freed when the list is destroyed.
101 * Note: Abandoning a list without calling list_destroy() will result
105 void list_destroy (List l
);
107 * Destroys list [l], freeing memory used for list iterators and the
108 * list itself; if a deletion function was specified when the list
109 * was created, it will be called for each item in the list.
112 int list_is_empty (List l
);
114 * Returns non-zero if list [l] is empty; o/w returns zero.
117 int list_count (List l
);
119 * Returns the number of items in list [l].
123 /***************************
124 * List Access Functions *
125 ***************************/
127 void * list_append (List l
, void *x
);
129 * Inserts data [x] at the end of list [l].
130 * Returns the data's ptr, or lsd_nomem_error() if insertion failed.
133 void * list_prepend (List l
, void *x
);
135 * Inserts data [x] at the beginning of list [l].
136 * Returns the data's ptr, or lsd_nomem_error() if insertion failed.
139 void * list_find_first (List l
, ListFindF f
, void *key
);
141 * Traverses list [l] using [f] to match each item with [key].
142 * Returns a ptr to the first item for which the function [f]
143 * returns non-zero, or NULL if no such item is found.
144 * Note: This function differs from list_find() in that it does not require
145 * a list iterator; it should only be used when all list items are known
146 * to be unique (according to the function [f]).
149 int list_delete_all (List l
, ListFindF f
, void *key
);
151 * Traverses list [l] using [f] to match each item with [key].
152 * Removes all items from the list for which the function [f] returns
153 * non-zero; if a deletion function was specified when the list was
154 * created, it will be called to deallocate each item being removed.
155 * Returns a count of the number of items removed from the list.
158 int list_for_each (List l
, ListForF f
, void *arg
);
160 * For each item in list [l], invokes the function [f] with [arg].
161 * Returns a count of the number of items on which [f] was invoked.
162 * If [f] returns <0 for a given item, the iteration is aborted and the
163 * function returns the negative of that item's position in the list.
166 void list_sort (List l
, ListCmpF f
);
168 * Sorts list [l] into ascending order according to the function [f].
169 * Note: Sorting a list resets all iterators associated with the list.
170 * Note: The sort algorithm is stable.
174 /****************************
175 * Stack Access Functions *
176 ****************************/
178 void * list_push (List l
, void *x
);
180 * Pushes data [x] onto the top of stack [l].
181 * Returns the data's ptr, or lsd_nomem_error() if insertion failed.
184 void * list_pop (List l
);
186 * Pops the data item at the top of the stack [l].
187 * Returns the data's ptr, or NULL if the stack is empty.
190 void * list_peek (List l
);
192 * Peeks at the data item at the top of the stack (or head of the queue) [l].
193 * Returns the data's ptr, or NULL if the stack (or queue) is empty.
194 * Note: The item is not removed from the list.
198 /****************************
199 * Queue Access Functions *
200 ****************************/
202 void * list_enqueue (List l
, void *x
);
204 * Enqueues data [x] at the tail of queue [l].
205 * Returns the data's ptr, or lsd_nomem_error() if insertion failed.
208 void * list_dequeue (List l
);
210 * Dequeues the data item at the head of the queue [l].
211 * Returns the data's ptr, or NULL if the queue is empty.
215 /*****************************
216 * List Iterator Functions *
217 *****************************/
219 ListIterator
list_iterator_create (List l
);
221 * Creates and returns a list iterator for non-destructively traversing
222 * list [l], or lsd_nomem_error() on failure.
225 void list_iterator_reset (ListIterator i
);
227 * Resets the list iterator [i] to start traversal at the beginning
231 void list_iterator_destroy (ListIterator i
);
233 * Destroys the list iterator [i]; list iterators not explicitly destroyed
234 * in this manner will be destroyed when the list is deallocated via
238 void * list_next (ListIterator i
);
240 * Returns a ptr to the next item's data,
241 * or NULL once the end of the list is reached.
242 * Example: i=list_iterator_create(i); while ((x=list_next(i))) {...}
245 void * list_insert (ListIterator i
, void *x
);
247 * Inserts data [x] immediately before the last item returned via list
248 * iterator [i]; once the list iterator reaches the end of the list,
249 * insertion is made at the list's end.
250 * Returns the data's ptr, or lsd_nomem_error() if insertion failed.
253 void * list_find (ListIterator i
, ListFindF f
, void *key
);
255 * Traverses the list from the point of the list iterator [i]
256 * using [f] to match each item with [key].
257 * Returns a ptr to the next item for which the function [f]
258 * returns non-zero, or NULL once the end of the list is reached.
259 * Example: i=list_iterator_reset(i); while ((x=list_find(i,f,k))) {...}
262 void * list_remove (ListIterator i
);
264 * Removes from the list the last item returned via list iterator [i]
265 * and returns the data's ptr.
266 * Note: The client is responsible for freeing the returned data.
269 int list_delete (ListIterator i
);
271 * Removes from the list the last item returned via list iterator [i];
272 * if a deletion function was specified when the list was created,
273 * it will be called to deallocate the item being removed.
274 * Returns a count of the number of items removed from the list
275 * (ie, '1' if the item was removed, and '0' otherwise).
279 #endif /* !LSD_LIST_H */