* libltdl/slist.c, libltdl/slist.h: Merge in changes from latest

upstream.  Mostly comments, formal item boxing, a sort function,
and const madness reduction.
(slist_new): Removed.
(slist_box, slist_unbox, slist_sort): New.
(SListCompare, SListCallback): Swapped!
(slist_remove, slist_find): Change order of parameters for
orthogonality with slist_foreach.  Changed all callers.
* libltdl/lt_dlloader.c (loader_cmp): Renamed to...
(loader_callback): ...this.  Return boxed item.
(lt_dlloader_remove): Adjust to new loader_callback semantics;
unbox each removed item before returning.
Remove unused variable.
Remove const from name parameter, since the slist API cannot
guarantee userdata const-ancy for its callback functions.
(lt_dlloader_find): Adjust to new loader_callback semantics; need
to return the contents of the boxed item.
Remove const from name parameter, since the slist API cannot
guarantee userdata const-ancy for its callback functions.
* libltdl/lt_dlloader.h (lt_dlloader_find, lt_dlloader_remove):
Adjust to new constless footprint.
* libltdl/ltdl.c (ltdl_exit): The global `loaders' list is changed
variable `loader' is invalidated.  Since some loaders may be
resident modules that cannot be unloaded (though we have none
yet), we must save each `next' address before calling
`lt_dlloader_remove'.
* NEWS: Updated.
* THANKS: Added Ralf.

1 files changed, 220 insertions, 62 deletions

diff --git a/libltdl/slist.c b/libltdl/slist.c
index e24b092d..06ccf346 100644
--- a/libltdl/slist.c
+++ b/libltdl/slist.c
@@ -1,6 +1,6 @@
 /* slist.h -- generalised singly linked lists
    Copyright (C) 2000, 2004 Free Software Foundation, Inc.
-   Originally by Gary V. Vaughan  <gary@gnu.org>
+   Written by Gary V. Vaughan  <gary@gnu.org>
 
    NOTE: The canonical source of this file is maintained with the
    GNU Libtool package.  Report bugs to bug-libtool@gnu.org.
@@ -31,23 +31,24 @@ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
 
 #include "slist.h"
 
+static SList *	slist_sort_merge    (SList *left, SList *right,
+				     SListCompare *compare, void *userdata);
 
-SList *
-slist_new (const void *userdata)
-{
-  SList *node = malloc (sizeof *node);
 
-  if (node)
-    {
-      node->next     = 0;
-      node->userdata = userdata;
-    }
+/* Call DELETE repeatedly on each element of HEAD.
 
-  return node;
-}
+   CAVEAT: If you call this when HEAD is the start of a list of boxed
+           items, you must remember that each item passed back to your
+	   DELETE function will be a boxed item must be slist_unbox()ed
+	   before operating on its contents.
 
+   e.g. void boxed_delete (void *item) { item_free (slist_unbox (item)); }
+        ...
+	  slist = slist_delete (slist, boxed_delete);
+	...
+*/
 SList *
-slist_delete (SList *head, void (*delete) (void *data))
+slist_delete (SList *head, void (*delete) (void *item))
 {
   assert (delete);
 
@@ -61,16 +62,17 @@ slist_delete (SList *head, void (*delete) (void *data))
   return 0;
 }
 
-/* Call Find repeatedly with MATCH and each element of *PHEAD, until
+/* Call FIND repeatedly with MATCHDATA and each item of *PHEAD, until
    FIND returns non-NULL, or the list is exhausted.  If a match is found
-   the matching element is removed from *PHEAD, and the value returned
-   by the matching call to FIND is returned.
+   the matching item is destructively removed from *PHEAD, and the value
+   returned by the matching call to FIND is returned.
 
-  To avoid memory leaks, unless you already have the address of the
-  stale element, you should probably return that from FIND if it makes
-  a successful match.  */
+   CAVEAT: To avoid memory leaks, unless you already have the address of
+           the stale item, you should probably return that from FIND if
+	   it makes a successful match.  Don't forget to slist_unbox()
+	   every item in a boxed list before operating on its contents.   */
 void *
-slist_remove (SList **phead, const void *match, SListCompare *find)
+slist_remove (SList **phead, SListCallback *find, void *matchdata)
 {
   SList *stale = 0;
   void *result = 0;
@@ -81,7 +83,7 @@ slist_remove (SList **phead, const void *match, SListCompare *find)
     return 0;
 
   /* Does the head of the passed list match? */
-  result = (*find) (*phead, match);
+  result = (*find) (*phead, matchdata);
   if (result)
     {
       stale = *phead;
@@ -93,7 +95,7 @@ slist_remove (SList **phead, const void *match, SListCompare *find)
       SList *head;
       for (head = *phead; head->next; head = head->next)
 	{
-	  result = (*find) (head->next, match);
+	  result = (*find) (head->next, matchdata);
 	  if (result)
 	    {
 	      stale		= head->next;
@@ -105,6 +107,33 @@ slist_remove (SList **phead, const void *match, SListCompare *find)
   return result;
 }
 
+/* Call FIND repeatedly with each element of SLIST and MATCHDATA, until
+   FIND returns non-NULL, or the list is exhausted.  If a match is found
+   the value returned by the matching call to FIND is returned. */
+void *
+slist_find (SList *slist, SListCallback *find, void *matchdata)
+{
+  void *result = 0;
+
+  assert (find);
+
+  for (; slist; slist = slist->next)
+    {
+      result = (*find) (slist, matchdata);
+      if (result)
+	break;
+    }
+
+  return result;
+}
+
+/* Return a single list, composed by destructively concatenating the
+   items in HEAD and TAIL.  The values of HEAD and TAIL are undefined
+   after calling this function.
+
+   CAVEAT: Don't mix boxed and unboxed items in a single list.
+
+   e.g.  slist1 = slist_concat (slist1, slist2);  */
 SList *
 slist_concat (SList *head, SList *tail)
 {
@@ -121,89 +150,218 @@ slist_concat (SList *head, SList *tail)
   return head;
 }
 
+/* Return a single list, composed by destructively appending all of
+   the items in SLIST to ITEM.  The values of ITEM and SLIST are undefined
+   after calling this function.
+
+   CAVEAT:  Don't mix boxed and unboxed items in a single list.
+
+   e.g.  slist1 = slist_cons (slist_box (data), slist1);  */
 SList *
-slist_cons (SList *head, SList *tail)
+slist_cons (SList *item, SList *slist)
 {
-  if (!head)
+  if (!item)
     {
-      return tail;
+      return slist;
     }
 
-  head->next = tail;
-  return head;
+  item->next = slist;
+  return item;
 }
 
+/* Return a list starting at the second item of SLIST.  */
 SList *
-slist_tail (SList *head)
+slist_tail (SList *slist)
 {
-  return head ? head->next : 0;
+  return slist ? slist->next : 0;
 }
 
+/* Return a list starting at the Nth item of SLIST.  If SLIST is less
+   than N items long, NULL is returned.  Just to be confusing, list items
+   are counted from 1, to get the 2nd element of slist:
+
+   e.g. shared_list = slist_nth (slist, 2);  */
 SList *
-slist_nth (SList *head, size_t n)
+slist_nth (SList *slist, size_t n)
 {
-  for (;n > 1 && head; n--)
-    head = head->next;
+  for (;n > 1 && slist; n--)
+    slist = slist->next;
 
-  return head;
+  return slist;
 }
 
-/* Call FIND repeatedly with SEARCH and each element of HEAD, until
-   FIND returns non-NULL, or the list is exhausted.  If a match is found
-   the value returned by the matching call to FIND is returned. */
+/* Return the number of items in SLIST.  We start counting from 1, so
+   the length of a list with no items is 0, and so on.  */
+size_t
+slist_length (SList *slist)
+{
+  size_t n;
+
+  for (n = 0; slist; ++n)
+    slist = slist->next;
+
+  return n;
+}
+
+/* Destructively reverse the order of items in SLIST.  The value of SLIST
+   is undefined after calling this function.
+
+  CAVEAT: You must stare the result of this function, or you might not
+          be able to get all the items except the first one back again.
+
+  e.g.    slist = slist_reverse (slist);  */
+SList *
+slist_reverse (SList *slist)
+{
+  SList *result = 0;
+  SList *next;
+
+  while (slist)
+    {
+      next		= slist->next;
+      slist->next	= result;
+      result		= slist;
+      slist 		= next;
+    }
+
+  return result;
+}
+
+/* Call FOREACH once for each item in SLIST, passing both the item and
+   USERDATA on each call. */
 void *
-slist_find (SList *head, const void *match, SListCompare *find)
+slist_foreach (SList *slist, SListCallback *foreach, void *userdata)
 {
   void *result = 0;
 
-  assert (find);
+  assert (foreach);
 
-  for (; head; head = head->next)
+  while (slist)
     {
-      result = (*find) (head, match);
+      SList *next = slist->next;
+      void *result = (*foreach) (slist, userdata);
+
       if (result)
 	break;
+
+      slist = next;
     }
 
   return result;
 }
 
-size_t
-slist_length (SList *head)
+/* Destructively merge the items of two ordered lists LEFT and RIGHT,
+   returning a single sorted list containing the items of both --  Part of
+   the quicksort algorithm.  The values of LEFT and RIGHT are undefined
+   after calling this function.
+
+   At each iteration, add another item to the merged list by taking the
+   lowest valued item from the head of either LEFT or RIGHT, determined
+   by passing those items and USERDATA to COMPARE.  COMPARE should return
+   less than 0 if the head of LEFT has the lower value, greater than 0 if
+   the head of RIGHT has the lower value, otherwise 0.  */
+static SList *
+slist_sort_merge (SList *left, SList *right, SListCompare *compare,
+		  void *userdata)
 {
-  size_t n;
+  SList merged, *insert;
 
-  for (n = 0; head; ++n)
-    head = head->next;
+  insert = &merged;
 
-  return n;
+  while (left && right)
+    {
+      if ((*compare) (left, right, userdata) <= 0)
+	{
+	  insert = insert->next = left;
+	  left = left->next;
+	}
+      else
+	{
+	  insert = insert->next = right;
+	  right = right->next;
+	}
+    }
+
+  insert->next = left ? left : right;
+
+  return merged.next;
 }
 
+/* Perform a destructive quicksort on the items in SLIST, by repeatedly
+   calling COMPARE with a pair of items from SLIST along with USERDATA
+   at every iteration.  COMPARE is a function as defined above for
+   slist_sort_merge().  The value of SLIST is undefined after calling
+   this function.
+
+   e.g.  slist = slist_sort (slist, compare, 0);  */
 SList *
-slist_reverse (SList *head)
+slist_sort (SList *slist, SListCompare *compare, void *userdata)
 {
-  SList *result = 0;
-  SList *next;
+  SList *left, *right;
 
-  while (head)
+  if (!slist)
+    return slist;
+
+  /* Be sure that LEFT and RIGHT never contain the same item.  */
+  left = slist;
+  right = slist->next;
+
+  /* Skip two items with RIGHT and one with SLIST, until RIGHT falls off
+     the end.  SLIST must be about half way along.  */
+  while (right && (right = right->next))
     {
-      next		= head->next;
-      head->next	= result;
-      result		= head;
-      head 		= next;
+      if (!right || !(right = right->next))
+	break;
+      slist = slist->next;
     }
+  right = slist->next;
+  slist->next = 0;
 
-  return result;
+  /* Sort LEFT and RIGHT, then merge the two.  */
+  return slist_sort_merge (slist_sort (left, compare, userdata),
+			   slist_sort (right, compare, userdata),
+			   compare, userdata);
 }
 
-int
-slist_foreach (SList *head, SListCallback *foreach, const void *userdata)
+
+/* Aside from using the functions above to manage chained structures of
+   any type that has a NEXT pointer as its first field, SLISTs can
+   be comprised of boxed items.  The boxes are chained together in
+   that case, so there is no need for a NEXT field in the item proper.
+   Some care must be taken to slist_box and slist_unbox each item in
+   a boxed list at the appropriate points to avoid leaking the memory
+   used for the boxes.  It us usually a very bad idea to mix boxed and
+   non-boxed items in a single list.  */
+
+/* Return a `boxed' freshly mallocated 1 element list containing
+   USERDATA.  */
+SList *
+slist_box (const void *userdata)
 {
-  assert (foreach);
+  SList *item = malloc (sizeof *item);
 
-  for (; head; head = head->next)
-    if ((*foreach) (head, userdata) < 0)
-      return -1;
+  if (item)
+    {
+      item->next     = 0;
+      item->userdata = userdata;
+    }
 
-  return 0;
+  return item;
+}
+
+/* Return the contents of a `boxed' ITEM, recycling the box itself.  */
+void *
+slist_unbox (SList *item)
+{
+  void *userdata = 0;
+
+  if (item)
+    {
+      /* Strip the const, because responsibility for this memory
+	 passes to the caller on return.  */
+      userdata = (void *) item->userdata;
+      free (item);
+    }
+
+  return userdata;
 }