LIST(3) LIST(3)
NAME
list_init, list_mvprev, list_mvnext, list_mvfront, list_mvrear,
list_front, list_curr, list_rear, list_insert_before,
list_insert_after, list_remove_front, list_remove_curr,
list_remove_rear, list_remove_element, list_size, list_empty,
list_traverse, list_free - generic doubly-linked-list routines
SYNOPSIS
#include <list.h>
list_t list_init();
list_t list_mvprev(list_t list);
list_t list_mvnext(list_t list);
list_t list_mvfront(list_t list);
list_t list_mvrear(list_t list);
void *list_front(list_t list);
void *list_curr(list_t list);
void *list_rear(list_t list);
void *list_insert_before(list_t list, void *element, size_t len);
void *list_insert_after(list_t list, void *element, size_t len);
void *list_remove_front(list_t list);
void *list_remove_curr(list_t list);
void *list_remove_rear(list_t list);
list_status_t list_remove_element(list_t list, void *element);
size_t list_size(list_t list);
int list_empty(list_t list);
typedef int (*list_traverse_func_t)(void *data, void *element);
list_status_t list_traverse(list_t list, void *data,
list_traverse_func_t func, int opts);
typedef void (*list_dealloc_func_t)(void *element);
void list_free(list_t list, list_dealloc_func_t dealloc);
- 1 - Formatted: November 6, 2024
LIST(3) LIST(3)
Link with -llist.
DESCRIPTION
These routines provide generic manipulation of (potentially) multiple
linked lists. Each list can hold arbitrarily sized elements, with
individual elements within a list varying in size. It is the
programmers responsibility to account for such differences.
Lists are referred to by variables declared as list_t; the type list_t
is an opaque handle. Traditionally, LIST * was used instead. LIST * is
still defined for API backwards-compatibility, but new code should use
list_t. Each descriptor maintains references to the front, rear, and
current elements. It also holds the size (or length) of the list.
Various routines operate relative to the current element.
list_t is list handle.
list_status_t may be one of the following meaningful values:
LIST_EMPTY The list is empty. No operation was performed.
LIST_OK The operation was successfully performed.
LIST_EXTENT The operation finished without error but
the end of the list was reached without any
special action.
list_init initializes and returns a list descriptor.
list_mvprev, list_mvnext, list_mvfront, list_mvrear, move to the
previous, next, front, or rear element in list, and return the
modified list descriptor. Movement previous or next is relative to
the current element.
list_front, list_curr, and list_rear return pointers to the front,
current, or rear element in list.
list_insert_before and list_insert_after insert an element, pointed to
by element and of size len, into list, either before or after the
current element. The newly inserted element is then considered the
current element. Both routines return a pointer to the newly inserted
element. If len is greater than 0, then element is copied into the
list, otherwise only the reference data is copied into the list. This
allows the user to determine the memory allocation policy.
list_remove_front, list_remove_curr, and list_remove_rear remove the
front, current, or rear element from list and return a pointer to the
removed element. The current element is then set to the next element
(prior to the remove) in the list, unless the element at the rear of
the list was removed. In this case, the current element is set to the
previous element (prior to the remove).
list_remove_element removes an element identified by the pointer
element from the list. This function is only useful if you are
- 2 - Formatted: November 6, 2024
LIST(3) LIST(3)
allocating each element yourself (i.e., you are setting len to 0 when
calling list_insert_before or list_insert_after). This function will
remove all instances of element, at the expense of forcing a traversal
of the whole list. If the end of the list is reached without finding
element, LIST_EXTENT is returned. Otherwise, if one or more elements
is successfully removed, LIST_OK is returned.
list_size returns the size (or number of elements) of list as a
size_t.
list_empty returns 1 (TRUE) if list is empty, 0 (FALSE) otherwise.
list_traverse traverses list according to opts, calling func at each
element encountered in the traversal, until func returns 0 (FALSE) or
the extent of the list is reached. This routine can be used to search
for an item or print the contents of the list, for example. See the
section LIST TRAVERSAL for more information.
list_free deallocates list, applying the user-supplied function
dealloc to the data portion of each element remaining in the list. If
dealloc is LIST_DEALLOC, then the package will apply its own
deallocation routine. This, however, should only be done if the
package has been responsible for data element allocation, i.e., the
insert routines have been invoked with len greater than 0. If dealloc
is LIST_NODEALLOC, no per-element deallocation will be performed.
LIST TRAVERSAL
The behavior of the routine list_traversal is controlled by the user-
supplied function func which is responsible for the actions performed
at each element in the traversal. In addition, the scope and
direction of the traversal can be specified with the opts parameter.
Func should be declared to match the diff_traverse_func_t type:
int func(void *data, void *element);
and should return 1 (TRUE) if the traversal should continue, or 0
(FALSE) if the traversal should terminate. The function does not need
to check if the extent of the list has been reached; the return code
from list_traverse will indicate the status of the traversal. At each
element encountered in the traversal, list_traverse will invoke func,
passing it the two parameters data and element; data being the data
pointer sent to list_traverse originally, and element being the
current element in the traversal. For example, by passing the
following function to list_traverse, the contents of a list of names
could be printed.
struct mystruct
{
char *name;
};
- 3 - Formatted: November 6, 2024
LIST(3) LIST(3)
int func(void *data, struct mystruct *element)
{
printf("Name=%30s.\n", element->name);
return TRUE;
}
In this example, the parameter data is ignored and the function
unconditionally returns 1 (TRUE), but functions like
int func(void *data, void *element)
{
if (strcmp(data, element))
return TRUE;
else
return FALSE;
}
can be used to position the current element pointer prior to
insertion, so as to keep the list ordered.
The direction and scope of the traversal can be controlled by
specifying one or more of the following options:
LIST_FORW * traverse forward (next)
LIST_BACK traverse backwards (prev)
LIST_FRNT * start from the front of the
list (implies LIST_FORW)
LIST_CURR start from the current element
LIST_REAR start from the rear element
(implies LIST_BACK)
LIST_SAVE * do not alter the current element
pointer during the traversal
LIST_ALTR alter the current element pointer
during the traversal
The asterisks (*) denote the default values. These options can be
combined with the logical OR operator, but at least one value must be
specified. For example, specifying
LIST_FORW
for opts would request a traversal forwards from the current position,
restoring the current element pointer after the traversal, whereas
(LIST_BACK | LIST_CURR | LIST_ALTR)
would request a traversal backwards from the current position, and
would set the current element pointer to the last element encountered
in the traversal.
It should be noted that func should not invoke any of the list
- 4 - Formatted: November 6, 2024
LIST(3) LIST(3)
routines unless LIST_ALTR has been specified, since many of the
routines act relative to the current element pointer, which is not
modified during a traversal with LIST_SAVE specified.
MEMORY ALLOCATION
The routines list_init, list_insert_before, and list_insert_after
allocate memory during their execution. As such, list_insert_before
and list_insert_after insert a copy of the element into the list when
they are invoked with len greater than 0. If len is 0, then only the
reference is copied into the list. This allows the user to control
the memory allocation policy. Both functions may fail during memory
allocation; see DIAGNOSTICS below for more information.
Note that list_remove_front, list_remove_curr, and list_remove_rear do
not deallocate memory for the removed element. They simply
disassociate the element from the list, and thus return a pointer to
the element that was previously allocated by the package. It is the
programmer's responsibility to deallocate such a removed element.
If the user has been responsible for element storage allocation, i.e.
the insert routines have been called with len equal to 0, then the
user must be responsible for storage deallocation as well. A user-
supplied deallocation function should be passed to list_free for this
purpose. The deallocation function should be declared as the
list_dealloc_func_t typedef:
void dealloc(void *data)
This function will be passed each element in the list when list_free
is invoked. If liblist has been responsible for data element
allocation, list_free can be invoked with LIST_DEALLOC for dealloc,;
the list package will apply its own deallocation routine, or
LIST_NODEALLOC if no per-element deallocation is required. It is the
programmer's responsibility to insure that the memory allocation
policy is applied properly.
DIAGNOSTICS
A NULL returned by list_init, list_insert_before, or list_insert_after
indicates a failure in allocating memory for the new list or element.
See malloc(3) for more information.
list_mvprev, list_mvnext, list_mvfront, list_mvrear, list_front,
list_curr, list_rear, list_remove_front, list_remove_curr, and
list_remove_rear all return NULL if list is empty.
list_traverse returns LIST_EMPTY for an empty list, LIST_EXTENT if an
attempt was made to move beyond the extent of the list, or LIST_OK
otherwise.
A core dump indicates a bug ;-)
- 5 - Formatted: November 6, 2024
LIST(3) LIST(3)
BUGS
The routines list_remove_front, list_remove_curr, list_remove_rear,
and list_free do not physically reclaim storage space, although they
do make it available for reuse. While this is a function of free(3),
its application here could be considered a bug.
SEE ALSO
liblist_queue(3), liblist_stack(3), cache(3)
AUTHOR
Bradley C. Spatz (bcs@ufl.edu), University of Florida.
- 6 - Formatted: November 6, 2024
