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.