/usr/share/libtool/libltdl/slist.c is in libltdl-dev 2.4.2-1.7ubuntu1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
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;
}
|