]>
Commit | Line | Data |
---|---|---|
564f6d15 | 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>. | |
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 | * 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 | |
18 | * more details. | |
19 | * | |
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 | *****************************************************************************/ | |
24 | ||
25 | ||
26 | #ifndef LSD_LIST_H | |
27 | #define LSD_LIST_H | |
28 | ||
29 | ||
30 | /*********** | |
31 | * Notes * | |
32 | ***********/ | |
33 | /* | |
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. | |
36 | * | |
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 | |
41 | * routine instead. | |
42 | * | |
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. | |
47 | * | |
48 | * If WITH_PTHREADS is defined, these routines will be thread-safe. | |
49 | */ | |
50 | ||
51 | ||
52 | /**************** | |
53 | * Data Types * | |
54 | ****************/ | |
55 | ||
56 | typedef struct list * List; | |
57 | /* | |
58 | * List opaque data type. | |
59 | */ | |
60 | ||
61 | typedef struct listIterator * ListIterator; | |
62 | /* | |
63 | * List Iterator opaque data type. | |
64 | */ | |
65 | ||
66 | typedef void (*ListDelF) (void *x); | |
67 | /* | |
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). | |
71 | */ | |
72 | ||
73 | typedef int (*ListCmpF) (void *x, void *y); | |
74 | /* | |
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). | |
78 | */ | |
79 | ||
80 | typedef int (*ListFindF) (void *x, void *key); | |
81 | /* | |
82 | * Function prototype for matching items in a list. | |
83 | * Returns non-zero if (x==key); o/w returns zero. | |
84 | */ | |
85 | ||
86 | typedef int (*ListForF) (void *x, void *arg); | |
87 | /* | |
88 | * Function prototype for operating on each item in a list. | |
89 | * Returns less-than-zero on error. | |
90 | */ | |
91 | ||
92 | ||
93 | /******************************* | |
94 | * General-Purpose Functions * | |
95 | *******************************/ | |
96 | ||
97 | List list_create (ListDelF f); | |
98 | /* | |
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 | |
104 | * in a memory leak. | |
105 | */ | |
106 | ||
107 | void list_destroy (List l); | |
108 | /* | |
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. | |
112 | */ | |
113 | ||
114 | int list_is_empty (List l); | |
115 | /* | |
116 | * Returns non-zero if list [l] is empty; o/w returns zero. | |
117 | */ | |
118 | ||
119 | int list_count (List l); | |
120 | /* | |
121 | * Returns the number of items in list [l]. | |
122 | */ | |
123 | ||
124 | ||
125 | /*************************** | |
126 | * List Access Functions * | |
127 | ***************************/ | |
128 | ||
129 | void * list_append (List l, void *x); | |
130 | /* | |
131 | * Inserts data [x] at the end of list [l]. | |
132 | * Returns the data's ptr, or lsd_nomem_error() if insertion failed. | |
133 | */ | |
134 | ||
135 | void * list_prepend (List l, void *x); | |
136 | /* | |
137 | * Inserts data [x] at the beginning of list [l]. | |
138 | * Returns the data's ptr, or lsd_nomem_error() if insertion failed. | |
139 | */ | |
140 | ||
141 | void * list_find_first (List l, ListFindF f, void *key); | |
142 | /* | |
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]). | |
149 | */ | |
150 | ||
151 | int list_delete_all (List l, ListFindF f, void *key); | |
152 | /* | |
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. | |
158 | */ | |
159 | ||
160 | int list_for_each (List l, ListForF f, void *arg); | |
161 | /* | |
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. | |
166 | */ | |
167 | ||
168 | void list_sort (List l, ListCmpF f); | |
169 | /* | |
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. | |
173 | */ | |
174 | ||
175 | ||
176 | /**************************** | |
177 | * Stack Access Functions * | |
178 | ****************************/ | |
179 | ||
180 | void * list_push (List l, void *x); | |
181 | /* | |
182 | * Pushes data [x] onto the top of stack [l]. | |
183 | * Returns the data's ptr, or lsd_nomem_error() if insertion failed. | |
184 | */ | |
185 | ||
186 | void * list_pop (List l); | |
187 | /* | |
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. | |
190 | */ | |
191 | ||
192 | void * list_peek (List l); | |
193 | /* | |
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. | |
197 | */ | |
198 | ||
199 | ||
200 | /**************************** | |
201 | * Queue Access Functions * | |
202 | ****************************/ | |
203 | ||
204 | void * list_enqueue (List l, void *x); | |
205 | /* | |
206 | * Enqueues data [x] at the tail of queue [l]. | |
207 | * Returns the data's ptr, or lsd_nomem_error() if insertion failed. | |
208 | */ | |
209 | ||
210 | void * list_dequeue (List l); | |
211 | /* | |
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. | |
214 | */ | |
215 | ||
216 | ||
217 | /***************************** | |
218 | * List Iterator Functions * | |
219 | *****************************/ | |
220 | ||
221 | ListIterator list_iterator_create (List l); | |
222 | /* | |
223 | * Creates and returns a list iterator for non-destructively traversing | |
224 | * list [l], or lsd_nomem_error() on failure. | |
225 | */ | |
226 | ||
227 | void list_iterator_reset (ListIterator i); | |
228 | /* | |
229 | * Resets the list iterator [i] to start traversal at the beginning | |
230 | * of the list. | |
231 | */ | |
232 | ||
233 | void list_iterator_destroy (ListIterator i); | |
234 | /* | |
235 | * Destroys the list iterator [i]; list iterators not explicitly destroyed | |
236 | * in this manner will be destroyed when the list is deallocated via | |
237 | * list_destroy(). | |
238 | */ | |
239 | ||
240 | void * list_next (ListIterator i); | |
241 | /* | |
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))) {...} | |
245 | */ | |
246 | ||
247 | void * list_insert (ListIterator i, void *x); | |
248 | /* | |
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. | |
253 | */ | |
254 | ||
255 | void * list_find (ListIterator i, ListFindF f, void *key); | |
256 | /* | |
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))) {...} | |
262 | */ | |
263 | ||
264 | void * list_remove (ListIterator i); | |
265 | /* | |
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. | |
269 | */ | |
270 | ||
271 | int list_delete (ListIterator i); | |
272 | /* | |
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). | |
278 | */ | |
279 | ||
280 | ||
281 | #endif /* !LSD_LIST_H */ |