]>
Commit | Line | Data |
---|---|---|
87d546d8 TG |
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>. | |
6 | * UCRL-CODE-235197 | |
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, see <http://www.gnu.org/licenses/>. | |
22 | *****************************************************************************/ | |
23 | ||
24 | #ifndef LSD_LIST_H | |
25 | #define LSD_LIST_H | |
26 | ||
27 | ||
28 | /*********** | |
29 | * Notes * | |
30 | ***********/ | |
31 | /* | |
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. | |
34 | * | |
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 | |
39 | * routine instead. | |
40 | * | |
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. | |
45 | * | |
46 | * If WITH_PTHREADS is defined, these routines will be thread-safe. | |
47 | */ | |
48 | ||
49 | ||
50 | /**************** | |
51 | * Data Types * | |
52 | ****************/ | |
53 | ||
54 | typedef struct list * List; | |
55 | /* | |
56 | * List opaque data type. | |
57 | */ | |
58 | ||
59 | typedef struct listIterator * ListIterator; | |
60 | /* | |
61 | * List Iterator opaque data type. | |
62 | */ | |
63 | ||
64 | typedef void (*ListDelF) (void *x); | |
65 | /* | |
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). | |
69 | */ | |
70 | ||
71 | typedef int (*ListCmpF) (void *x, void *y); | |
72 | /* | |
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). | |
76 | */ | |
77 | ||
78 | typedef int (*ListFindF) (void *x, void *key); | |
79 | /* | |
80 | * Function prototype for matching items in a list. | |
81 | * Returns non-zero if (x==key); o/w returns zero. | |
82 | */ | |
83 | ||
84 | typedef int (*ListForF) (void *x, void *arg); | |
85 | /* | |
86 | * Function prototype for operating on each item in a list. | |
87 | * Returns less-than-zero on error. | |
88 | */ | |
89 | ||
90 | ||
91 | /******************************* | |
92 | * General-Purpose Functions * | |
93 | *******************************/ | |
94 | ||
95 | List list_create (ListDelF f); | |
96 | /* | |
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 | |
102 | * in a memory leak. | |
103 | */ | |
104 | ||
105 | void list_destroy (List l); | |
106 | /* | |
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. | |
110 | */ | |
111 | ||
112 | int list_is_empty (List l); | |
113 | /* | |
114 | * Returns non-zero if list [l] is empty; o/w returns zero. | |
115 | */ | |
116 | ||
117 | int list_count (List l); | |
118 | /* | |
119 | * Returns the number of items in list [l]. | |
120 | */ | |
121 | ||
122 | ||
123 | /*************************** | |
124 | * List Access Functions * | |
125 | ***************************/ | |
126 | ||
127 | void * list_append (List l, void *x); | |
128 | /* | |
129 | * Inserts data [x] at the end of list [l]. | |
130 | * Returns the data's ptr, or lsd_nomem_error() if insertion failed. | |
131 | */ | |
132 | ||
133 | void * list_prepend (List l, void *x); | |
134 | /* | |
135 | * Inserts data [x] at the beginning of list [l]. | |
136 | * Returns the data's ptr, or lsd_nomem_error() if insertion failed. | |
137 | */ | |
138 | ||
139 | void * list_find_first (List l, ListFindF f, void *key); | |
140 | /* | |
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]). | |
147 | */ | |
148 | ||
149 | int list_delete_all (List l, ListFindF f, void *key); | |
150 | /* | |
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. | |
156 | */ | |
157 | ||
158 | int list_for_each (List l, ListForF f, void *arg); | |
159 | /* | |
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. | |
164 | */ | |
165 | ||
166 | void list_sort (List l, ListCmpF f); | |
167 | /* | |
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. | |
171 | */ | |
172 | ||
173 | ||
174 | /**************************** | |
175 | * Stack Access Functions * | |
176 | ****************************/ | |
177 | ||
178 | void * list_push (List l, void *x); | |
179 | /* | |
180 | * Pushes data [x] onto the top of stack [l]. | |
181 | * Returns the data's ptr, or lsd_nomem_error() if insertion failed. | |
182 | */ | |
183 | ||
184 | void * list_pop (List l); | |
185 | /* | |
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. | |
188 | */ | |
189 | ||
190 | void * list_peek (List l); | |
191 | /* | |
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. | |
195 | */ | |
196 | ||
197 | ||
198 | /**************************** | |
199 | * Queue Access Functions * | |
200 | ****************************/ | |
201 | ||
202 | void * list_enqueue (List l, void *x); | |
203 | /* | |
204 | * Enqueues data [x] at the tail of queue [l]. | |
205 | * Returns the data's ptr, or lsd_nomem_error() if insertion failed. | |
206 | */ | |
207 | ||
208 | void * list_dequeue (List l); | |
209 | /* | |
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. | |
212 | */ | |
213 | ||
214 | ||
215 | /***************************** | |
216 | * List Iterator Functions * | |
217 | *****************************/ | |
218 | ||
219 | ListIterator list_iterator_create (List l); | |
220 | /* | |
221 | * Creates and returns a list iterator for non-destructively traversing | |
222 | * list [l], or lsd_nomem_error() on failure. | |
223 | */ | |
224 | ||
225 | void list_iterator_reset (ListIterator i); | |
226 | /* | |
227 | * Resets the list iterator [i] to start traversal at the beginning | |
228 | * of the list. | |
229 | */ | |
230 | ||
231 | void list_iterator_destroy (ListIterator i); | |
232 | /* | |
233 | * Destroys the list iterator [i]; list iterators not explicitly destroyed | |
234 | * in this manner will be destroyed when the list is deallocated via | |
235 | * list_destroy(). | |
236 | */ | |
237 | ||
238 | void * list_next (ListIterator i); | |
239 | /* | |
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))) {...} | |
243 | */ | |
244 | ||
245 | void * list_insert (ListIterator i, void *x); | |
246 | /* | |
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. | |
251 | */ | |
252 | ||
253 | void * list_find (ListIterator i, ListFindF f, void *key); | |
254 | /* | |
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))) {...} | |
260 | */ | |
261 | ||
262 | void * list_remove (ListIterator i); | |
263 | /* | |
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. | |
267 | */ | |
268 | ||
269 | int list_delete (ListIterator i); | |
270 | /* | |
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). | |
276 | */ | |
277 | ||
278 | ||
279 | #endif /* !LSD_LIST_H */ |