Annotation of parser3/src/lib/ltdl/slist.c, revision 1.1
1.1 ! moko 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:
! 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: #include <stdlib.h>
! 36:
! 37: static 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: */
! 53: SList *
! 54: slist_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. */
! 77: SList *
! 78: slist_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. */
! 117: void *
! 118: slist_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); */
! 141: SList *
! 142: slist_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); */
! 167: SList *
! 168: slist_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. */
! 182: SList *
! 183: slist_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); */
! 193: SList *
! 194: slist_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. */
! 204: size_t
! 205: slist_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); */
! 222: SList *
! 223: slist_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. */
! 241: void *
! 242: slist_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. */
! 272: static SList *
! 273: slist_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); */
! 306: SList *
! 307: slist_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. */
! 350: SList *
! 351: slist_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. */
! 365: void *
! 366: slist_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: }
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