/[svn]/ircd-hybrid-7.2/libltdl/slist.c
ViewVC logotype

Contents of /ircd-hybrid-7.2/libltdl/slist.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 945 - (show annotations)
Mon Jul 20 15:48:27 2009 UTC (10 years, 1 month ago) by michael
File MIME type: text/x-chdr
File size: 9775 byte(s)
- fixed some configure mess and imported latest libtool sources

1 /* slist.c -- generalised singly linked lists
2
3 Copyright (C) 2000, 2004, 2007, 2008 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
36 static SList * slist_sort_merge (SList *left, SList *right,
37 SListCompare *compare, void *userdata);
38
39
40 /* Call DELETE repeatedly on each element of HEAD.
41
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.
46
47 e.g. void boxed_delete (void *item) { item_free (slist_unbox (item)); }
48 ...
49 slist = slist_delete (slist, boxed_delete);
50 ...
51 */
52 SList *
53 slist_delete (SList *head, void (*delete_fct) (void *item))
54 {
55 assert (delete_fct);
56
57 while (head)
58 {
59 SList *next = head->next;
60 (*delete_fct) (head);
61 head = next;
62 }
63
64 return 0;
65 }
66
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.
71
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. */
76 void *
77 slist_remove (SList **phead, SListCallback *find, void *matchdata)
78 {
79 SList *stale = 0;
80 void *result = 0;
81
82 assert (find);
83
84 if (!phead || !*phead)
85 return 0;
86
87 /* Does the head of the passed list match? */
88 result = (*find) (*phead, matchdata);
89 if (result)
90 {
91 stale = *phead;
92 *phead = stale->next;
93 }
94 /* what about the rest of the elements? */
95 else
96 {
97 SList *head;
98 for (head = *phead; head->next; head = head->next)
99 {
100 result = (*find) (head->next, matchdata);
101 if (result)
102 {
103 stale = head->next;
104 head->next = stale->next;
105 break;
106 }
107 }
108 }
109
110 return result;
111 }
112
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. */
116 void *
117 slist_find (SList *slist, SListCallback *find, void *matchdata)
118 {
119 void *result = 0;
120
121 assert (find);
122
123 for (; slist; slist = slist->next)
124 {
125 result = (*find) (slist, matchdata);
126 if (result)
127 break;
128 }
129
130 return result;
131 }
132
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.
136
137 CAVEAT: Don't mix boxed and unboxed items in a single list.
138
139 e.g. slist1 = slist_concat (slist1, slist2); */
140 SList *
141 slist_concat (SList *head, SList *tail)
142 {
143 SList *last;
144
145 if (!head)
146 {
147 return tail;
148 }
149
150 last = head;
151 while (last->next)
152 last = last->next;
153
154 last->next = tail;
155
156 return head;
157 }
158
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.
162
163 CAVEAT: Don't mix boxed and unboxed items in a single list.
164
165 e.g. slist1 = slist_cons (slist_box (data), slist1); */
166 SList *
167 slist_cons (SList *item, SList *slist)
168 {
169 if (!item)
170 {
171 return slist;
172 }
173
174 assert (!item->next);
175
176 item->next = slist;
177 return item;
178 }
179
180 /* Return a list starting at the second item of SLIST. */
181 SList *
182 slist_tail (SList *slist)
183 {
184 return slist ? slist->next : NULL;
185 }
186
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:
190
191 e.g. shared_list = slist_nth (slist, 2); */
192 SList *
193 slist_nth (SList *slist, size_t n)
194 {
195 for (;n > 1 && slist; n--)
196 slist = slist->next;
197
198 return slist;
199 }
200
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. */
203 size_t
204 slist_length (SList *slist)
205 {
206 size_t n;
207
208 for (n = 0; slist; ++n)
209 slist = slist->next;
210
211 return n;
212 }
213
214 /* Destructively reverse the order of items in SLIST. The value of SLIST
215 is undefined after calling this function.
216
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.
219
220 e.g. slist = slist_reverse (slist); */
221 SList *
222 slist_reverse (SList *slist)
223 {
224 SList *result = 0;
225 SList *next;
226
227 while (slist)
228 {
229 next = slist->next;
230 slist->next = result;
231 result = slist;
232 slist = next;
233 }
234
235 return result;
236 }
237
238 /* Call FOREACH once for each item in SLIST, passing both the item and
239 USERDATA on each call. */
240 void *
241 slist_foreach (SList *slist, SListCallback *foreach, void *userdata)
242 {
243 void *result = 0;
244
245 assert (foreach);
246
247 while (slist)
248 {
249 SList *next = slist->next;
250 result = (*foreach) (slist, userdata);
251
252 if (result)
253 break;
254
255 slist = next;
256 }
257
258 return result;
259 }
260
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.
265
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. */
271 static SList *
272 slist_sort_merge (SList *left, SList *right, SListCompare *compare,
273 void *userdata)
274 {
275 SList merged, *insert;
276
277 insert = &merged;
278
279 while (left && right)
280 {
281 if ((*compare) (left, right, userdata) <= 0)
282 {
283 insert = insert->next = left;
284 left = left->next;
285 }
286 else
287 {
288 insert = insert->next = right;
289 right = right->next;
290 }
291 }
292
293 insert->next = left ? left : right;
294
295 return merged.next;
296 }
297
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
302 this function.
303
304 e.g. slist = slist_sort (slist, compare, 0); */
305 SList *
306 slist_sort (SList *slist, SListCompare *compare, void *userdata)
307 {
308 SList *left, *right;
309
310 if (!slist)
311 return slist;
312
313 /* Be sure that LEFT and RIGHT never contain the same item. */
314 left = slist;
315 right = slist->next;
316
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))
320 {
321 if (!right || !(right = right->next))
322 break;
323 slist = slist->next;
324 }
325 right = slist->next;
326 slist->next = 0;
327
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),
331 compare, userdata);
332 }
333
334
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. */
343
344 /* Return a `boxed' freshly mallocated 1 element list containing
345 USERDATA. */
346 SList *
347 slist_box (const void *userdata)
348 {
349 SList *item = (SList *) malloc (sizeof *item);
350
351 if (item)
352 {
353 item->next = 0;
354 item->userdata = userdata;
355 }
356
357 return item;
358 }
359
360 /* Return the contents of a `boxed' ITEM, recycling the box itself. */
361 void *
362 slist_unbox (SList *item)
363 {
364 void *userdata = 0;
365
366 if (item)
367 {
368 /* Strip the const, because responsibility for this memory
369 passes to the caller on return. */
370 userdata = (void *) item->userdata;
371 free (item);
372 }
373
374 return userdata;
375 }

Properties

Name Value
svn:eol-style native

svnadmin@ircd-hybrid.org
ViewVC Help
Powered by ViewVC 1.1.26