7. Linkedlist

The linkedlist functions manipulate a sigularly linked list of data pointers.

The struct linkedlist * parameter represeting the list being operated on must be valid. If a the list parameter is a null pointer, a null pointer or -1 will be returned and errno will be set to EINVAL.

7.1. Memory management functions

These functions should be used to create and destroy linkedlist objects.

The linkedlist_new function
Synopsis

#include <mba/linkedlist.h> struct linkedlist *linkedlist_new(unsigned int max_size);
Description
Create a new linkedlist object that accepts no more than max_size items. If max_size is zero the list will accept no more than MAX_INT items. A linkedlist object may be freed with linkedlist_del.
Returns
a new linkedlist object. If memory for the linkedlist cannot be allocated a null pointer is returned and errno is set to ENOMEM.

The linkedlist_del function
Synopsis

#include <mba/linkedlist.h> void linkedlist_del(struct linkedlist *this, void (*free_data_fn)(void *));
Description
frees the list and all associated resources.

The linkedlist_clear function
Synopsis

#include <mba/linkedlist.h> void linkedlist_clear(struct linkedlist *this, void (*free_data_fn)(void *));
Description
clears the list of all data pointers. If the free_data_fn function is not NULL, it will be called for each data pointer in the list as an argument.

7.2. List functions

The linkedlist_add function
Synopsis

#include <mba/linkedlist.h> int linkedlist_add(struct linkedlist *this, void *data);
Description
The linkedlist_add function appends a data pointer to the end of the list.
Returns
The linkedlist_insert function returns 0 if the operation was successfull and -1 if an error occurred in which case errno will be set appropriately.

The linkedlist_insert function
Synopsis

#include <mba/linkedlist.h> int linkedlist_insert(struct linkedlist *this, unsigned int idx, void *data);
Description
inserts a data pointer before the item at idx. If idx equals the size of the list, the data pointer will be appended to the list.
Returns
The linkedlist_insert function returns 0 if the operation was successfull and -1 if an error occurred in which case errno will be set appropriately.

The linkedlist_insert_sorted function
Synopsis

#include <mba/linkedlist.h> int linkedlist_insert_sorted(struct linkedlist *this, int (*compar)(const void *, const void *), void **replaced, void *data)
Description
The linkedlist_insert_sorted funtion inserts the data pointer data into the linked list this in a position determined by the comparison function compar which will be called repeatedly with the new data pointer and each data pointer in the list. The following describes the outcome of the linkedlist_insert_sorted operation depending on the result of compar:
Returns
The linkedlist_insert_sorted function returns 0 if the operation was successfull and -1 if an error occurred in which case errno will be set appropriately.

The linkedlist_is_empty function
Synopsis

#include <mba/linkedlist.h> int linkedlist_is_empty(const struct linkedlist *this);
Description
tests if the list is empty.
Returns
non-zero if the list is empty and zero otherwise.

The linkedlist_size function
Synopsis

#include <mba/linkedlist.h> unsigned int linkedlist_size(const struct linkedlist *this);
Description
returns the number of items in the list.

The linkedlist_get function
Synopsis

#include <mba/linkedlist.h> void *linkedlist_get(const struct linkedlist *this, unsigned int idx);
Description
The linkedlist_get function retrieves an item from the list by index. If elements are accessed sequentially each call is an O(1) operation.
Returns
The linkedlist_get function returns the data pointer being retrieved. If the specified idx was out of range, a null pointer is returned and errno is set appropriately.

The linkedlist_get_last function
Synopsis

#include <mba/linkedlist.h> void *linkedlist_get_last(const struct linkedlist *this);
Description
The linkedlist_get_last function retrieves the last data pointer in the list.
Returns
The linkedlist_get_last function returns the data pointer or a null pointer if the list is empty.

The linkedlist_iterate function
Synopsis

#include <mba/linkedlist.h> void linkedlist_iterate(void *this, iter_t *iter);
Description
Enumerate each element in the list. The linkedlist_iterate function initializes the iter object to point to the first item in the list. Each subsequent call to linkedlist_next returns the next element in the list or NULL if all elements have been enumerated. The elements are returned in order.

To enumerate each element in a list the following code might be used:

  iter_t iter;
  linkedlist_iterate(lst, &iter);
  while ((el = linkedlist_next(lst, &iter)) {
      /* use el */
  }
  

The linkedlist_next function
Synopsis

#include <mba/linkedlist.h> void *linkedlist_next(void *this, iter_t *iter);
Returns
The linkedlist_next function returns the next data pointer in the list or NULL if all elements have been enumerated.

The linkedlist_remove function
Synopsis

#include <mba/linkedlist.h> void *linkedlist_remove(struct linkedlist *this, unsigned int idx);
Description
removes the data pointer at idx from the list.
Returns
the data pointer removed from the list.

The linkedlist_remove_last function
Synopsis

#include <mba/linkedlist.h> void *linkedlist_remove_last(struct linkedlist *this);
Description
The linkedlist_remove_last function removes the last data pointer in the list.
Returns
The linkedlist_remove_last function returns the data pointer removed from the list.


Copyright 2002 Michael B. Allen <mballen@erols.com>