libltdl/slist.c

   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 }