SL(3)                                                              SL Reference                                                              SL(3)

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)
           "func" is called once for each node in the list, having the node itself passed as the first argument; "data" is passed as the second
           argument.  If "func" returns a positive value the current node will be extracted from the passed-in list and stored in a temporary
           list. When we get to the end of the passed-in list, the temporary list is returned.

           If "func" returns a negative value the same happens as when a positive value is returened but in addition any further traversal of the
           passed-in array is terminated and the current temporary list is returned immediately.

           You can return the first 5 elements that matches a certain criteria by maintaining a counter in "data" and return 1 until the fifth
           node is found, then return -1.

           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@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.

POD ERRORS

       Hey! The above document had some coding errors, which are explained below:

       Around line 58:
           =cut found outside a pod block.  Skipping to next block.

simplelist 0.3.4                                                    2006-12-21                                                               SL(3)