]>
Commit | Line | Data |
---|---|---|
0191e3d3 AC |
1 | /* slist.c -- generalised singly linked lists |
2 | ||
3 | Copyright (C) 2000, 2004, 2007, 2008, 2009 Free Software Foundation, Inc. | |
4 | Written by Gary V. Vaughan, 2000 | |
5 | ||
6 | NOTE: The canonical source of this file is maintained with the | |
7 | GNU Libtool package. Report bugs to bug-libtool@gnu.org. | |
8 | ||
9 | GNU Libltdl is free software; you can redistribute it and/or | |
10 | modify it under the terms of the GNU Lesser General Public | |
11 | License as published by the Free Software Foundation; either | |
12 | version 2 of the License, or (at your option) any later version. | |
13 | ||
14 | As a special exception to the GNU Lesser General Public License, | |
15 | if you distribute this file as part of a program or library that | |
16 | is built using GNU Libtool, you may include this file under the | |
17 | same distribution terms that you use for the rest of that program. | |
18 | ||
19 | GNU Libltdl is distributed in the hope that it will be useful, | |
20 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
21 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
22 | GNU Lesser General Public License for more details. | |
23 | ||
24 | You should have received a copy of the GNU Lesser General Public | |
25 | License along with GNU Libltdl; see the file COPYING.LIB. If not, a | |
26 | copy can be downloaded from http://www.gnu.org/licenses/lgpl.html, | |
27 | or obtained by writing to the Free Software Foundation, Inc., | |
28 | 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. | |
29 | */ | |
30 | ||
31 | #include <assert.h> | |
32 | ||
33 | #include "slist.h" | |
34 | #include <stddef.h> | |
35 | #include <stdlib.h> | |
36 | ||
37 | static SList * slist_sort_merge (SList *left, SList *right, | |
38 | SListCompare *compare, void *userdata); | |
39 | ||
40 | ||
41 | /* Call DELETE repeatedly on each element of HEAD. | |
42 | ||
43 | CAVEAT: If you call this when HEAD is the start of a list of boxed | |
44 | items, you must remember that each item passed back to your | |
45 | DELETE function will be a boxed item that must be slist_unbox()ed | |
46 | before operating on its contents. | |
47 | ||
48 | e.g. void boxed_delete (void *item) { item_free (slist_unbox (item)); } | |
49 | ... | |
50 | slist = slist_delete (slist, boxed_delete); | |
51 | ... | |
52 | */ | |
53 | SList * | |
54 | slist_delete (SList *head, void (*delete_fct) (void *item)) | |
55 | { | |
56 | assert (delete_fct); | |
57 | ||
58 | while (head) | |
59 | { | |
60 | SList *next = head->next; | |
61 | (*delete_fct) (head); | |
62 | head = next; | |
63 | } | |
64 | ||
65 | return 0; | |
66 | } | |
67 | ||
68 | /* Call FIND repeatedly with MATCHDATA and each item of *PHEAD, until | |
69 | FIND returns non-NULL, or the list is exhausted. If a match is found | |
70 | the matching item is destructively removed from *PHEAD, and the value | |
71 | returned by the matching call to FIND is returned. | |
72 | ||
73 | CAVEAT: To avoid memory leaks, unless you already have the address of | |
74 | the stale item, you should probably return that from FIND if | |
75 | it makes a successful match. Don't forget to slist_unbox() | |
76 | every item in a boxed list before operating on its contents. */ | |
77 | SList * | |
78 | slist_remove (SList **phead, SListCallback *find, void *matchdata) | |
79 | { | |
80 | SList *stale = 0; | |
81 | void *result = 0; | |
82 | ||
83 | assert (find); | |
84 | ||
85 | if (!phead || !*phead) | |
86 | return 0; | |
87 | ||
88 | /* Does the head of the passed list match? */ | |
89 | result = (*find) (*phead, matchdata); | |
90 | if (result) | |
91 | { | |
92 | stale = *phead; | |
93 | *phead = stale->next; | |
94 | } | |
95 | /* what about the rest of the elements? */ | |
96 | else | |
97 | { | |
98 | SList *head; | |
99 | for (head = *phead; head->next; head = head->next) | |
100 | { | |
101 | result = (*find) (head->next, matchdata); | |
102 | if (result) | |
103 | { | |
104 | stale = head->next; | |
105 | head->next = stale->next; | |
106 | break; | |
107 | } | |
108 | } | |
109 | } | |
110 | ||
111 | return (SList *) result; | |
112 | } | |
113 | ||
114 | /* Call FIND repeatedly with each element of SLIST and MATCHDATA, until | |
115 | FIND returns non-NULL, or the list is exhausted. If a match is found | |
116 | the value returned by the matching call to FIND is returned. */ | |
117 | void * | |
118 | slist_find (SList *slist, SListCallback *find, void *matchdata) | |
119 | { | |
120 | void *result = 0; | |
121 | ||
122 | assert (find); | |
123 | ||
124 | for (; slist; slist = slist->next) | |
125 | { | |
126 | result = (*find) (slist, matchdata); | |
127 | if (result) | |
128 | break; | |
129 | } | |
130 | ||
131 | return result; | |
132 | } | |
133 | ||
134 | /* Return a single list, composed by destructively concatenating the | |
135 | items in HEAD and TAIL. The values of HEAD and TAIL are undefined | |
136 | after calling this function. | |
137 | ||
138 | CAVEAT: Don't mix boxed and unboxed items in a single list. | |
139 | ||
140 | e.g. slist1 = slist_concat (slist1, slist2); */ | |
141 | SList * | |
142 | slist_concat (SList *head, SList *tail) | |
143 | { | |
144 | SList *last; | |
145 | ||
146 | if (!head) | |
147 | { | |
148 | return tail; | |
149 | } | |
150 | ||
151 | last = head; | |
152 | while (last->next) | |
153 | last = last->next; | |
154 | ||
155 | last->next = tail; | |
156 | ||
157 | return head; | |
158 | } | |
159 | ||
160 | /* Return a single list, composed by destructively appending all of | |
161 | the items in SLIST to ITEM. The values of ITEM and SLIST are undefined | |
162 | after calling this function. | |
163 | ||
164 | CAVEAT: Don't mix boxed and unboxed items in a single list. | |
165 | ||
166 | e.g. slist1 = slist_cons (slist_box (data), slist1); */ | |
167 | SList * | |
168 | slist_cons (SList *item, SList *slist) | |
169 | { | |
170 | if (!item) | |
171 | { | |
172 | return slist; | |
173 | } | |
174 | ||
175 | assert (!item->next); | |
176 | ||
177 | item->next = slist; | |
178 | return item; | |
179 | } | |
180 | ||
181 | /* Return a list starting at the second item of SLIST. */ | |
182 | SList * | |
183 | slist_tail (SList *slist) | |
184 | { | |
185 | return slist ? slist->next : NULL; | |
186 | } | |
187 | ||
188 | /* Return a list starting at the Nth item of SLIST. If SLIST is less | |
189 | than N items long, NULL is returned. Just to be confusing, list items | |
190 | are counted from 1, to get the 2nd element of slist: | |
191 | ||
192 | e.g. shared_list = slist_nth (slist, 2); */ | |
193 | SList * | |
194 | slist_nth (SList *slist, size_t n) | |
195 | { | |
196 | for (;n > 1 && slist; n--) | |
197 | slist = slist->next; | |
198 | ||
199 | return slist; | |
200 | } | |
201 | ||
202 | /* Return the number of items in SLIST. We start counting from 1, so | |
203 | the length of a list with no items is 0, and so on. */ | |
204 | size_t | |
205 | slist_length (SList *slist) | |
206 | { | |
207 | size_t n; | |
208 | ||
209 | for (n = 0; slist; ++n) | |
210 | slist = slist->next; | |
211 | ||
212 | return n; | |
213 | } | |
214 | ||
215 | /* Destructively reverse the order of items in SLIST. The value of SLIST | |
216 | is undefined after calling this function. | |
217 | ||
218 | CAVEAT: You must store the result of this function, or you might not | |
219 | be able to get all the items except the first one back again. | |
220 | ||
221 | e.g. slist = slist_reverse (slist); */ | |
222 | SList * | |
223 | slist_reverse (SList *slist) | |
224 | { | |
225 | SList *result = 0; | |
226 | SList *next; | |
227 | ||
228 | while (slist) | |
229 | { | |
230 | next = slist->next; | |
231 | slist->next = result; | |
232 | result = slist; | |
233 | slist = next; | |
234 | } | |
235 | ||
236 | return result; | |
237 | } | |
238 | ||
239 | /* Call FOREACH once for each item in SLIST, passing both the item and | |
240 | USERDATA on each call. */ | |
241 | void * | |
242 | slist_foreach (SList *slist, SListCallback *foreach, void *userdata) | |
243 | { | |
244 | void *result = 0; | |
245 | ||
246 | assert (foreach); | |
247 | ||
248 | while (slist) | |
249 | { | |
250 | SList *next = slist->next; | |
251 | result = (*foreach) (slist, userdata); | |
252 | ||
253 | if (result) | |
254 | break; | |
255 | ||
256 | slist = next; | |
257 | } | |
258 | ||
259 | return result; | |
260 | } | |
261 | ||
262 | /* Destructively merge the items of two ordered lists LEFT and RIGHT, | |
263 | returning a single sorted list containing the items of both -- Part of | |
264 | the quicksort algorithm. The values of LEFT and RIGHT are undefined | |
265 | after calling this function. | |
266 | ||
267 | At each iteration, add another item to the merged list by taking the | |
268 | lowest valued item from the head of either LEFT or RIGHT, determined | |
269 | by passing those items and USERDATA to COMPARE. COMPARE should return | |
270 | less than 0 if the head of LEFT has the lower value, greater than 0 if | |
271 | the head of RIGHT has the lower value, otherwise 0. */ | |
272 | static SList * | |
273 | slist_sort_merge (SList *left, SList *right, SListCompare *compare, | |
274 | void *userdata) | |
275 | { | |
276 | SList merged, *insert; | |
277 | ||
278 | insert = &merged; | |
279 | ||
280 | while (left && right) | |
281 | { | |
282 | if ((*compare) (left, right, userdata) <= 0) | |
283 | { | |
284 | insert = insert->next = left; | |
285 | left = left->next; | |
286 | } | |
287 | else | |
288 | { | |
289 | insert = insert->next = right; | |
290 | right = right->next; | |
291 | } | |
292 | } | |
293 | ||
294 | insert->next = left ? left : right; | |
295 | ||
296 | return merged.next; | |
297 | } | |
298 | ||
299 | /* Perform a destructive quicksort on the items in SLIST, by repeatedly | |
300 | calling COMPARE with a pair of items from SLIST along with USERDATA | |
301 | at every iteration. COMPARE is a function as defined above for | |
302 | slist_sort_merge(). The value of SLIST is undefined after calling | |
303 | this function. | |
304 | ||
305 | e.g. slist = slist_sort (slist, compare, 0); */ | |
306 | SList * | |
307 | slist_sort (SList *slist, SListCompare *compare, void *userdata) | |
308 | { | |
309 | SList *left, *right; | |
310 | ||
311 | if (!slist) | |
312 | return slist; | |
313 | ||
314 | /* Be sure that LEFT and RIGHT never contain the same item. */ | |
315 | left = slist; | |
316 | right = slist->next; | |
317 | ||
318 | if (!right) | |
319 | return left; | |
320 | ||
321 | /* Skip two items with RIGHT and one with SLIST, until RIGHT falls off | |
322 | the end. SLIST must be about half way along. */ | |
323 | while (right && (right = right->next)) | |
324 | { | |
325 | if (!right || !(right = right->next)) | |
326 | break; | |
327 | slist = slist->next; | |
328 | } | |
329 | right = slist->next; | |
330 | slist->next = 0; | |
331 | ||
332 | /* Sort LEFT and RIGHT, then merge the two. */ | |
333 | return slist_sort_merge (slist_sort (left, compare, userdata), | |
334 | slist_sort (right, compare, userdata), | |
335 | compare, userdata); | |
336 | } | |
337 | ||
338 | ||
339 | /* Aside from using the functions above to manage chained structures of | |
340 | any type that has a NEXT pointer as its first field, SLISTs can | |
341 | be comprised of boxed items. The boxes are chained together in | |
342 | that case, so there is no need for a NEXT field in the item proper. | |
343 | Some care must be taken to slist_box and slist_unbox each item in | |
344 | a boxed list at the appropriate points to avoid leaking the memory | |
345 | used for the boxes. It us usually a very bad idea to mix boxed and | |
346 | non-boxed items in a single list. */ | |
347 | ||
348 | /* Return a `boxed' freshly mallocated 1 element list containing | |
349 | USERDATA. */ | |
350 | SList * | |
351 | slist_box (const void *userdata) | |
352 | { | |
353 | SList *item = (SList *) malloc (sizeof *item); | |
354 | ||
355 | if (item) | |
356 | { | |
357 | item->next = 0; | |
358 | item->userdata = userdata; | |
359 | } | |
360 | ||
361 | return item; | |
362 | } | |
363 | ||
364 | /* Return the contents of a `boxed' ITEM, recycling the box itself. */ | |
365 | void * | |
366 | slist_unbox (SList *item) | |
367 | { | |
368 | void *userdata = 0; | |
369 | ||
370 | if (item) | |
371 | { | |
372 | /* Strip the const, because responsibility for this memory | |
373 | passes to the caller on return. */ | |
374 | userdata = (void *) item->userdata; | |
375 | free (item); | |
376 | } | |
377 | ||
378 | return userdata; | |
379 | } |