8.2.x/libltdl/slist.c

/* slist.c -- generalised singly linked lists

   Copyright (C) 2000, 2004, 2007-2009, 2011-2019, 2021-2022 Free
   Software Foundation, Inc.
   Written by Gary V. Vaughan, 2000

   NOTE: The canonical source of this file is maintained with the
   GNU Libtool package.  Report bugs to bug-libtool@gnu.org.

GNU Libltdl is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2 of the License, or (at your option) any later version.

As a special exception to the GNU Lesser General Public License,
if you distribute this file as part of a program or library that
is built using GNU Libtool, you may include this file under the
same distribution terms that you use for the rest of that program.

GNU Libltdl is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public
License along with GNU Libltdl; see the file COPYING.LIB.  If not, a
copy can be downloaded from  http://www.gnu.org/licenses/lgpl.html,
or obtained by writing to the Free Software Foundation, Inc.,
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
*/

#include <assert.h>

#include "slist.h"
#include <stdlib.h>

static SList *  slist_sort_merge    (SList *left, SList *right,
                                     SListCompare *compare, void *userdata);


/* Call DELETE repeatedly on each element of HEAD.

   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 that 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_fct) (void *item))
{
  assert (delete_fct);

  while (head)
    {
      SList *next = head->next;
      (*delete_fct) (head);
      head = next;
    }

  return 0;
}

/* 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 item is destructively removed from *PHEAD, and the value
   returned by the matching call to FIND is returned.

   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.   */
SList *
slist_remove (SList **phead, SListCallback *find, void *matchdata)
{
  SList *stale = 0;
  void *result = 0;

  assert (find);

  if (!phead || !*phead)
    return 0;

  /* Does the head of the passed list match? */
  result = (*find) (*phead, matchdata);
  if (result)
    {
      stale = *phead;
      *phead = stale->next;
    }
  /* what about the rest of the elements? */
  else
    {
      SList *head;
      for (head = *phead; head->next; head = head->next)
        {
          result = (*find) (head->next, matchdata);
          if (result)
            {
              stale             = head->next;
              head->next        = stale->next;
              break;
            }
        }
    }

  return (SList *) 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)
{
  SList *last;

  if (!head)
    {
      return tail;
    }

  last = head;
  while (last->next)
    last = last->next;

  last->next = 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 *item, SList *slist)
{
  if (!item)
    {
      return slist;
    }

  assert (!item->next);

  item->next = slist;
  return item;
}

/* Return a list starting at the second item of SLIST.  */
SList *
slist_tail (SList *slist)
{
  return slist ? slist->next : NULL;
}

/* 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 *slist, size_t n)
{
  for (;n > 1 && slist; n--)
    slist = slist->next;

  return slist;
}

/* 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 store 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_foreach (SList *slist, SListCallback *foreach, void *userdata)
{
  void *result = 0;

  assert (foreach);

  while (slist)
    {
      SList *next = slist->next;
      result = (*foreach) (slist, userdata);

      if (result)
        break;

      slist = next;
    }

  return result;
}

/* 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)
{
  SList merged, *insert;

  insert = &merged;

  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_sort (SList *slist, SListCompare *compare, void *userdata)
{
  SList *left, *right;

  if (!slist)
    return slist;

  /* Be sure that LEFT and RIGHT never contain the same item.  */
  left = slist;
  right = slist->next;

  if (!right)
    return left;

  /* 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))
    {
      if (!right || !(right = right->next))
        break;
      slist = slist->next;
    }
  right = slist->next;
  slist->next = 0;

  /* Sort LEFT and RIGHT, then merge the two.  */
  return slist_sort_merge (slist_sort (left, compare, userdata),
                           slist_sort (right, compare, userdata),
                           compare, 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)
{
  SList *item = (SList *) malloc (sizeof *item);

  if (item)
    {
      item->next     = 0;
      item->userdata = userdata;
    }

  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;
}
Revision:	10082
Committed:	Sat Jun 11 11:40:12 2022 UTC (22 months ago) by michael
Content type:	text/x-csrc
File size:	9841 byte(s)
Log Message:	- autoreconf
#	User	Rev	Content
1	michael	945	/* slist.c -- generalised singly linked lists
2
3	michael	10082	Copyright (C) 2000, 2004, 2007-2009, 2011-2019, 2021-2022 Free
4			Software Foundation, Inc.
5	michael	945	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	michael	1094	#include <stdlib.h>
36	michael	945
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	michael	1094	SList *
78	michael	945	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	michael	1094	return (SList *) result;
112	michael	945	}
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	michael	4901	slist = next;
234	michael	945	}
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	michael	1094	if (!right)
319			return left;
320
321	michael	945	/* 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	michael	4901	/* Return a 'boxed' freshly mallocated 1 element list containing
349	michael	945	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	michael	4901	/* Return the contents of a 'boxed' ITEM, recycling the box itself. */
365	michael	945	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			}