source: squid-ssl/trunk/fuentes/libltdl/slist.c @ 5496

Last change on this file since 5496 was 5496, checked in by Juanma, 23 months ago

Initial release

File size: 9.6 KB
Line 
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
9GNU Libltdl is free software; you can redistribute it and/or
10modify it under the terms of the GNU Lesser General Public
11License as published by the Free Software Foundation; either
12version 2 of the License, or (at your option) any later version.
13
14As a special exception to the GNU Lesser General Public License,
15if you distribute this file as part of a program or library that
16is built using GNU Libtool, you may include this file under the
17same distribution terms that you use for the rest of that program.
18
19GNU Libltdl is distributed in the hope that it will be useful,
20but WITHOUT ANY WARRANTY; without even the implied warranty of
21MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
22GNU Lesser General Public License for more details.
23
24You should have received a copy of the GNU Lesser General Public
25License along with GNU Libltdl; see the file COPYING.LIB.  If not, a
26copy can be downloaded from  http://www.gnu.org/licenses/lgpl.html,
27or obtained by writing to the Free Software Foundation, Inc.,
2851 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
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}
Note: See TracBrowser for help on using the repository browser.