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