"Fossies" - the Fresh Open Source Software Archive

Member "bind-9.17.5/libltdl/slist.c" (4 Sep 2020, 9830 Bytes) of package /linux/misc/dns/bind9/9.17.5/bind-9.17.5.tar.xz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "slist.c" see the Fossies "Dox" file reference documentation.

    1 /* slist.c -- generalised singly linked lists
    2 
    3    Copyright (C) 2000, 2004, 2007-2009, 2011-2015 Free Software
    4    Foundation, Inc.
    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
   26 License along with GNU Libltdl; see the file COPYING.LIB.  If not, a
   27 copy can be downloaded from  http://www.gnu.org/licenses/lgpl.html,
   28 or obtained by writing to the Free Software Foundation, Inc.,
   29 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
   30 */
   31 
   32 #include <assert.h>
   33 
   34 #include "slist.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 }