Table Of Contents

Previous topic

Simple Containers

Next topic

Hash Table

Doubly Linked List

A doubly linked list data structure definition and functions.

Summary

s_list_new Create a new list.
s_list_delete Delete a list.
s_list_find_index Find the element in the list which matches the comparison with the comparison function s_list_compare_fp.
s_list_find Find the list element which matches the given data with the comparison function s_list_compare_fp.
s_list_index Find the index into the list of the given list element.
s_list_nth Find the nth element in the list.
s_list_first Return the first element in the list.
s_list_last Return the last element in the list.
s_list_element_get Get the list element data.
s_list_element_replace Replace the list element data, does not delete old data.
s_list_element_unlink Unlink list element from list.
s_list_element_delete Remove the list element from it’s parent list and delete the list element data.
s_list_element_next Return the next element in the list relative to the given one.
s_list_element_prev Return the previous element in the list relative to the given one.
s_list_isempty Query if the list has any elements.
s_list_size Get the number of elements in the list.
s_list_push Push data onto end of list.
s_list_pop Pop last element of list.
s_list_reverse Reverse the elements in the list.
s_list_prepend Prepend data to beginning of the list.
s_list_append Append data to end of the list.
s_list_insert_before Insert data before given list element.
s_list_insert_after Insert data after given list element.

Definition

typedef struct s_list s_list

Opaque definition of a doubly linked list.

The doubly linked list is headed by a pair of pointers, one to the head of the list and the other to the tail of the list. The elements are doubly linked so that an arbitrary element can be removed without a need to traverse the list. New elements can be added to the list before or after an existing element, at the head of the list, or at the end of the list. A doubly linked list may be traversed in either direction.

typedef struct s_list_element s_list_element

Opaque definition of a list element.

The list element represents one element in the doubly linked list.

Create/Delete

s_list *s_list_new(s_list_compare_fp compare_func, s_list_free_fp free_func, s_erc *error)

Create a new list.

Creates a new list and sets the comparison and free functions. The comparison function must be of the type s_list_compare_fp while the free function must be of the type s_list_free_fp. If the comparison function is NULL then s_list_find will do nothing. If the free function is NULL then the s_list_element_delete and s_list_delete functions will do nothing.

Parameters:
  • compare_func

    A comparison function. Used to find an element in the list.

  • free_func

    A memory free function. Used to free element data from the list.

  • error

    Error code.

Return:

Pointer to a list data structure.

void s_list_delete(s_list *self, s_erc *error)

Delete a list.

Delete a list and all its elements. If the s_list_free_fp is NULL then the elements memory wont be freed.

Parameters:
  • self

    The list to delete.

  • error

    Error code.

Function Pointers

typedef s_bool (*s_list_compare_fp)(const void *le1, const void *le2, s_erc *error)

The s_list element comparison function typedef.

A pointer to a function that compares 2 elements of a list.

Parameters:
  • le1

    List element 1.

  • le2

    List element 2.

  • error

    Error code.

Return:

TRUE if elements are equal else FALSE.

typedef void(*s_list_free_fp)(void *le, s_erc *error)

The s_list element free function typedef.

A pointer to a function that frees the dynamically allocated memory of a list element.

Parameters:
  • le

    List element to free.

  • error

    Error code.

Accessing

s_list_element *s_list_find_index(const s_list *self, const s_list_element *f, const void *data, int *index, s_erc *error)

Find the element in the list which matches the comparison with the comparison function s_list_compare_fp.

If the comparison function is null then nothing is done.

Parameters:
  • self

    The list.

  • f

    Start searching from this element (including) onwards. If NULL then start from first element.

  • data

    The data to match.

  • index

    A variable to hold the index of the element found which matches the data. -1 if not found. Set to NULL if not required.

  • error

    Error code.

Return:

Pointer to the list element which matches the data, else NULL.

Note:

Lists are indexed starting from 0.

The index variable will be relative if f is notNULL.

macro s_list_find(self, data, error)

Find the list element which matches the given data with the comparison function s_list_compare_fp.

If the comparison function is NULL then nothing is done.

Parameters:
  • self

    The list.

  • data

    The data to match.

  • error

    Error code.

Return:

Pointer to the list element which matches the data, else NULL.

Note:

Returns the first match.

macro s_list_index(self, data, index, error)

Find the index into the list of the given list element.

If the list comparison function s_list_compare_fp is NULL then nothing is done.

Parameters:
  • self

    The list.

  • data

    The data to match.

  • index

    A variable to hold the index of the element found which matches the data. -1 if not found.

  • error

    Error code.

Return:

Pointer to the list element which matches the data, else NULL.

Note:

Lists are indexed starting from 0.

const s_list_element *s_list_nth(const s_list *self, uint32 n, s_erc *error)

Find the nth element in the list.

Parameters:
  • self

    The list.

  • n

    Index of element to find.

  • error

    Error code.

Return:

Pointer to the nth list element or NULL if index is out of bounds.

Note:

The list elements are indexed from 0.

const s_list_element *s_list_first(const s_list *self, s_erc *error)

Return the first element in the list.

Parameters:
  • self

    The list.

  • error

    Error code.

Return:

Pointer to the first element in the list.

const s_list_element *s_list_last(const s_list *self, s_erc *error)

Return the last element in the list.

Parameters:
  • self

    The list.

  • error

    Error code.

Return:

Pointer to the last element in the list.

Element functions

const void *s_list_element_get(const s_list_element *self, s_erc *error)

Get the list element data.

Parameters:
  • self

    The list element.

  • error

    Error code.

Return:

Pointer to the list element data.

void *s_list_element_replace(s_list_element *self, void *data, s_erc *error)

Replace the list element data, does not delete old data.

Parameters:
  • self

    The list element who’s data is to be replaced.

  • data

    The new list element data.

  • error

    Error code.

Return:

Pointer to the replaced list element data.

Note:

The list element takes ownership of the new data.

Unlink list element from list.

Does not delete data of element.

Parameters:
  • self

    The list element to be unlinked.

  • error

    Error code.

Return:

Pointer to the unlinked list element data.

Note:

The caller is responsible for the returned data’s memory.

s_list_element *s_list_element_delete(s_list_element *self, s_erc *error)

Remove the list element from it’s parent list and delete the list element data.

Parameters:
  • self

    The list element to be deleted.

  • error

    Error code.

Return:

Pointer to the previous list element or NULL if none.

Note:

If s_list_free_fp is not defined then nothing is done and NULL returned.

const s_list_element *s_list_element_next(const s_list_element *self, s_erc *error)

Return the next element in the list relative to the given one.

Parameters:
  • self

    Pointer to current position in list.

  • error

    Error code.

Return:

Pointer to the next element in the list.

const s_list_element *s_list_element_prev(const s_list_element *self, s_erc *error)

Return the previous element in the list relative to the given one.

Parameters:
  • self

    Pointer to current position in list.

  • error

    Error code.

Return:

Pointer to the previous element in the list.

Query

s_bool s_list_isempty(const s_list *self, s_erc *error)

Query if the list has any elements.

Parameters:
  • self

    The list to query.

  • error

    Error code.

Return:

TRUE or FALSE.

uint32 s_list_size(const s_list *self, s_erc *error)

Get the number of elements in the list.

Parameters:
  • self

    The list to query.

  • error

    Error code.

Return:

The number of elements in the list.

Queue

void s_list_push(s_list *self, void *data, s_erc *error)

Push data onto end of list.

Same as s_list_append.

Parameters:
  • self

    The list.

  • error

    Error code.

  • data

    The data to append.

Note:

The list takes ownership of the data.

void *s_list_pop(s_list *self, s_erc *error)

Pop last element of list.

Removes last element from list and returns the element data.

Parameters:
  • self

    The list.

  • error

    Error code.

Return:

Pointer to popped element data.

Note:

The caller is responsible for the memory of the returned data.

void s_list_reverse(s_list *self, s_erc *error)

Reverse the elements in the list.

Parameters:
  • self

    The list to reverse.

  • error

    Error code.

Insertion

void s_list_prepend(s_list *self, void *data, s_erc *error)

Prepend data to beginning of the list.

Parameters:
  • self

    The list.

  • error

    Error code.

  • data

    The data to prepend.

Note:

The list takes ownership of the data.

void s_list_append(s_list *self, void *data, s_erc *error)

Append data to end of the list.

Parameters:
  • self

    The list.

  • error

    Error code.

  • data

    The data to append.

Note:

The list takes ownership of the data.

const s_list_element *s_list_insert_before(s_list_element *self, void *data, s_erc *error)

Insert data before given list element.

Return reference to inserted data element.

Parameters:
  • self

    The element before which data must be inserted.

  • data

    The data to be inserted.

  • error

    Error code.

Return:

Pointer to the inserted list element.

Note:

The list takes ownership of the data.

const s_list_element *s_list_insert_after(s_list_element *self, void *data, s_erc *error)

Insert data after given list element.

Return reference to inserted data element.

Parameters:
  • self

    The element after which data must be inserted.

  • data

    The data to be inserted.

  • error

    Error code.

Return:

Pointer to the inserted list element.

Note:

The list takes ownership of the data.