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.

void *s_list_element_unlink(s_list_element *self, s_erc *error)

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.