NAME
sl − a small and flexible linked list implementation
DESCRIPTION
’sl’ provides a generic implementation of singly-linked lists and stacks.
’sl’ does not do extra allocations behind the scenes for placeholder nodes, yet users of the library can define their node structure almost any way they want. The one important thing is that the −>next member is the first member of the structure.
FUNCTIONS
void *sl_push(void *root, void *p)
Push "p" onto the list "root". Return the new list.
void *sl_pop(void *root)
Pop a node from a list. Return the pop’ed item, or NULL if the list is empty.
Note: this function takes a pointer to a pointer to a node as its argument. C does not allow "void **" to be used as a generic pointer to pointer type. However, since "void *" is a generic pointer, it can also point to a pointer to pointer.
void *sl_unshift(void *root, void *p)
Shift a node onto the ’far end’ of a list. This function can be used to append a list to another. The new list is returned.
void *sl_shift(void *)
Shift a node from the ’far end’ of a list. Returns the item shifted off the list, or NULL if the list is empty.
Note: this function takes a pointer to a pointer to a node as its argument. C does not allow "void **" to be used as a generic pointer to pointer type. However, since "void *" is a generic pointer, it can also point to a pointer to pointer.
void *sl_reverse(void *root)
Returns the reversed list.
void *sl_map(void *root, int (*func)(void *, void *), void *data)
Map a function, "func", to every element in a list. The "data" is handed to "func" along with each node. This function can be used for a sequential search of a list of nodes.
This function returns NULL on normal operation. If "func" returns non−zero, a pointer to the current node will be returned.
void *sl_filter(void *root, int (*func)(void *, void *), void *data)
If "func" returns negative when it finds a match, the element is removed from the list and returned immediatly. However, if "func" returns positive, it returns a list of *all* values that match, and these elements are removed from the original list.
To return only the first 5 elements maintain a counter in "data" and thus return only the first 5 elements matching your criteria by having "func" examine "data" and return negative instead of positive on the fifth match.
Note: this function takes a pointer to a pointer to a node as its argument. C does not allow "void **" to be used as a generic pointer to pointer type. However, since "void *" is a generic pointer, it can also point to a pointer to pointer.
void *sl_split(void *root)
Split a list roughly on the middle; return a pointer to the second half.
void *sl_merge(void *p1, void *p2, int (*cmp)(void *, void *))
Merge two sorted lists and keep the list sorted. This function is the heart of the mergesort routine. Thanks to CB Falconer for this code.
void *sl_mergesort(void *root, int (*cmp)(void *, void *))
Return the sorted list.
int sl_count(void *p)
Returns the number of elements in a list.
void sl_free(void *root, void (*func)(void*))
A macro that just calls sl__free(). This is necessary because sl_free() is a defined function on OS−X .
void sl__free(void *root, void (*func)(void*))
Free a list of nodes. Takes an optional argument, @p func, used to free the node if it is defined.
AUTHOR
Stig Brautaset <stig [AT] brautaset.org>
CREDITS
Thanks to Thomas Stegen of comp.lang.c for suggesting the "void*" trick employed in ’sl_pop()’ and ’sl_shift()’.
Thanks to CB Falconer of comp.programming for help on the sorting code.
Richard Spindler suggested what became the "sl_filter()" function.
COPYRIGHT
Copyright (C) 2003,2004,2005 Stig Brautaset
This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.