1 /* slist.c -- generalised singly linked lists
3 Copyright (C) 2000, 2004, 2007, 2008 Free Software Foundation, Inc.
4 Written by Gary V. Vaughan, 2000
6 NOTE: The canonical source of this file is maintained with the
7 GNU Libtool package. Report bugs to bug-libtool@gnu.org.
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.
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.
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.
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.
36 static SList
* slist_sort_merge (SList
*left
, SList
*right
,
37 SListCompare
*compare
, void *userdata
);
40 /* Call DELETE repeatedly on each element of HEAD.
42 CAVEAT: If you call this when HEAD is the start of a list of boxed
43 items, you must remember that each item passed back to your
44 DELETE function will be a boxed item that must be slist_unbox()ed
45 before operating on its contents.
47 e.g. void boxed_delete (void *item) { item_free (slist_unbox (item)); }
49 slist = slist_delete (slist, boxed_delete);
53 slist_delete (SList
*head
, void (*delete_fct
) (void *item
))
59 SList
*next
= head
->next
;
67 /* Call FIND repeatedly with MATCHDATA and each item of *PHEAD, until
68 FIND returns non-NULL, or the list is exhausted. If a match is found
69 the matching item is destructively removed from *PHEAD, and the value
70 returned by the matching call to FIND is returned.
72 CAVEAT: To avoid memory leaks, unless you already have the address of
73 the stale item, you should probably return that from FIND if
74 it makes a successful match. Don't forget to slist_unbox()
75 every item in a boxed list before operating on its contents. */
77 slist_remove (SList
**phead
, SListCallback
*find
, void *matchdata
)
84 if (!phead
|| !*phead
)
87 /* Does the head of the passed list match? */
88 result
= (*find
) (*phead
, matchdata
);
94 /* what about the rest of the elements? */
98 for (head
= *phead
; head
->next
; head
= head
->next
)
100 result
= (*find
) (head
->next
, matchdata
);
104 head
->next
= stale
->next
;
113 /* Call FIND repeatedly with each element of SLIST and MATCHDATA, until
114 FIND returns non-NULL, or the list is exhausted. If a match is found
115 the value returned by the matching call to FIND is returned. */
117 slist_find (SList
*slist
, SListCallback
*find
, void *matchdata
)
123 for (; slist
; slist
= slist
->next
)
125 result
= (*find
) (slist
, matchdata
);
133 /* Return a single list, composed by destructively concatenating the
134 items in HEAD and TAIL. The values of HEAD and TAIL are undefined
135 after calling this function.
137 CAVEAT: Don't mix boxed and unboxed items in a single list.
139 e.g. slist1 = slist_concat (slist1, slist2); */
141 slist_concat (SList
*head
, SList
*tail
)
159 /* Return a single list, composed by destructively appending all of
160 the items in SLIST to ITEM. The values of ITEM and SLIST are undefined
161 after calling this function.
163 CAVEAT: Don't mix boxed and unboxed items in a single list.
165 e.g. slist1 = slist_cons (slist_box (data), slist1); */
167 slist_cons (SList
*item
, SList
*slist
)
174 assert (!item
->next
);
180 /* Return a list starting at the second item of SLIST. */
182 slist_tail (SList
*slist
)
184 return slist
? slist
->next
: NULL
;
187 /* Return a list starting at the Nth item of SLIST. If SLIST is less
188 than N items long, NULL is returned. Just to be confusing, list items
189 are counted from 1, to get the 2nd element of slist:
191 e.g. shared_list = slist_nth (slist, 2); */
193 slist_nth (SList
*slist
, size_t n
)
195 for (;n
> 1 && slist
; n
--)
201 /* Return the number of items in SLIST. We start counting from 1, so
202 the length of a list with no items is 0, and so on. */
204 slist_length (SList
*slist
)
208 for (n
= 0; slist
; ++n
)
214 /* Destructively reverse the order of items in SLIST. The value of SLIST
215 is undefined after calling this function.
217 CAVEAT: You must store the result of this function, or you might not
218 be able to get all the items except the first one back again.
220 e.g. slist = slist_reverse (slist); */
222 slist_reverse (SList
*slist
)
230 slist
->next
= result
;
238 /* Call FOREACH once for each item in SLIST, passing both the item and
239 USERDATA on each call. */
241 slist_foreach (SList
*slist
, SListCallback
*foreach
, void *userdata
)
249 SList
*next
= slist
->next
;
250 result
= (*foreach
) (slist
, userdata
);
261 /* Destructively merge the items of two ordered lists LEFT and RIGHT,
262 returning a single sorted list containing the items of both -- Part of
263 the quicksort algorithm. The values of LEFT and RIGHT are undefined
264 after calling this function.
266 At each iteration, add another item to the merged list by taking the
267 lowest valued item from the head of either LEFT or RIGHT, determined
268 by passing those items and USERDATA to COMPARE. COMPARE should return
269 less than 0 if the head of LEFT has the lower value, greater than 0 if
270 the head of RIGHT has the lower value, otherwise 0. */
272 slist_sort_merge (SList
*left
, SList
*right
, SListCompare
*compare
,
275 SList merged
, *insert
;
279 while (left
&& right
)
281 if ((*compare
) (left
, right
, userdata
) <= 0)
283 insert
= insert
->next
= left
;
288 insert
= insert
->next
= right
;
293 insert
->next
= left
? left
: right
;
298 /* Perform a destructive quicksort on the items in SLIST, by repeatedly
299 calling COMPARE with a pair of items from SLIST along with USERDATA
300 at every iteration. COMPARE is a function as defined above for
301 slist_sort_merge(). The value of SLIST is undefined after calling
304 e.g. slist = slist_sort (slist, compare, 0); */
306 slist_sort (SList
*slist
, SListCompare
*compare
, void *userdata
)
313 /* Be sure that LEFT and RIGHT never contain the same item. */
317 /* Skip two items with RIGHT and one with SLIST, until RIGHT falls off
318 the end. SLIST must be about half way along. */
319 while (right
&& (right
= right
->next
))
321 if (!right
|| !(right
= right
->next
))
328 /* Sort LEFT and RIGHT, then merge the two. */
329 return slist_sort_merge (slist_sort (left
, compare
, userdata
),
330 slist_sort (right
, compare
, userdata
),
335 /* Aside from using the functions above to manage chained structures of
336 any type that has a NEXT pointer as its first field, SLISTs can
337 be comprised of boxed items. The boxes are chained together in
338 that case, so there is no need for a NEXT field in the item proper.
339 Some care must be taken to slist_box and slist_unbox each item in
340 a boxed list at the appropriate points to avoid leaking the memory
341 used for the boxes. It us usually a very bad idea to mix boxed and
342 non-boxed items in a single list. */
344 /* Return a `boxed' freshly mallocated 1 element list containing
347 slist_box (const void *userdata
)
349 SList
*item
= (SList
*) malloc (sizeof *item
);
354 item
->userdata
= userdata
;
360 /* Return the contents of a `boxed' ITEM, recycling the box itself. */
362 slist_unbox (SList
*item
)
368 /* Strip the const, because responsibility for this memory
369 passes to the caller on return. */
370 userdata
= (void *) item
->userdata
;