Annotation of gforth/libltdl/slist.c, revision 1.1

1.1     ! anton       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: }

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>