1/* slist.c -- generalised singly linked lists
2
3 Copyright (C) 2000, 2004, 2007-2009, 2011-2015 Free Software
4 Foundation, Inc.
5 Written by Gary V. Vaughan, 2000
6
7 NOTE: The canonical source of this file is maintained with the
8 GNU Libtool package. Report bugs to bug-libtool@gnu.org.
9
10GNU Libltdl is free software; you can redistribute it and/or
11modify it under the terms of the GNU Lesser General Public
12License as published by the Free Software Foundation; either
13version 2 of the License, or (at your option) any later version.
14
15As a special exception to the GNU Lesser General Public License,
16if you distribute this file as part of a program or library that
17is built using GNU Libtool, you may include this file under the
18same distribution terms that you use for the rest of that program.
19
20GNU Libltdl is distributed in the hope that it will be useful,
21but WITHOUT ANY WARRANTY; without even the implied warranty of
22MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
23GNU Lesser General Public License for more details.
24
25You should have received a copy of the GNU Lesser General Public
26License along with GNU Libltdl; see the file COPYING.LIB. If not, a
27copy can be downloaded from http://www.gnu.org/licenses/lgpl.html,
28or obtained by writing to the Free Software Foundation, Inc.,
2951 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
30*/
31
32#include <assert.h>
33
34#include "slist.h"
35#include <stdlib.h>
36
37static 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*/
53SList *
54slist_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. */
77SList *
78slist_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. */
117void *
118slist_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); */
141SList *
142slist_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); */
167SList *
168slist_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. */
182SList *
183slist_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); */
193SList *
194slist_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. */
204size_t
205slist_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); */
222SList *
223slist_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. */
241void *
242slist_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. */
272static SList *
273slist_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); */
306SList *
307slist_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. */
350SList *
351slist_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. */
365void *
366slist_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}
380