File: slist.c

package info (click to toggle)
libprelude 4.1.0-4.2
  • links: PTS, VCS
  • area: main
  • in suites: bullseye, buster, sid
  • size: 21,452 kB
  • sloc: ansic: 103,807; cpp: 64,944; sh: 13,563; perl: 679; makefile: 674; awk: 343; yacc: 241; lex: 178; python: 89; xml: 65
file content (379 lines) | stat: -rw-r--r-- 9,844 bytes parent folder | download | duplicates (69)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
/* slist.c -- generalised singly linked lists

   Copyright (C) 2000, 2004, 2007, 2008, 2009 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 <stddef.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;
}