Doubly-linked lists

Doubly-linked lists.

Through this single API two flavours of lists are offered: normal lists and auto-allocating lists.

The most evident difference between them is that the latter’s elements will contain automatically allocated copies of the inserted values (the pointed data is copied) while the former’s elements will contain copies of the references to the given data (the pointer value is copied).

Other differences that the user of this API should be aware of are specified in the documention of functions.

No thread synchronization is performed by this API, i.e., it is not thread-safe to concurrently operate on a list unless you implement some external synchronization mechanism.

Summary
Doubly-linked listsDoubly-linked lists.
Types
nacore_listDoubly-linked list.
nacore_list_elemDoubly-linked list element.
Functions
nacore_list_new()Creates a new list.
nacore_list_free()Destroys a list and all its elements.
nacore_list_get_n_elems()Gets the number of elements in a list.
nacore_list_get_head()Returns the head (first element) of a list.
nacore_list_get_tail()Returns the tail (last element) of a list.
nacore_list_prepend()Creates a new list element and prepends it to a list.
nacore_list_append()Creates a new list element and appends it to a list.
nacore_list_insert_before()Creates a new list element and inserts it before another element in a list.
nacore_list_insert_after()Creates a new list element and inserts it after another element in a list.
nacore_list_move_before()Moves an element before another element in a list.
nacore_list_move_after()Moves an element after another element in a list.
nacore_list_pop()Removes an element from a list, destroys it and returns the value it contains.
nacore_list_find_first()Finds the first matching element inside a list.
nacore_list_find_last()Finds the last matching element inside a list.
nacore_list_find_before()Finds the first matching element inside a list going backwards before another given element.
nacore_list_find_after()Finds the first matching element inside a list going forwards after another given element.
nacore_list_dup()Duplicates a list.
nacore_list_merge()Merges two lists by appending the elements of src to dest.
nacore_list_dump()Dumps the structure and content of a list on stderr.
nacore_list_elem_new()Creates a new list element without adding it to a list.
nacore_list_elem_free()Destroys a list element.
nacore_list_elem_prepend()Prepends a list element to a list.
nacore_list_elem_append()Appends a list element to a list.
nacore_list_elem_insert_before()Inserts a list element before another element in a list.
nacore_list_elem_insert_after()Inserts a list element after another element in a list.
nacore_list_elem_pop()Removes an element from a list without destroying it.
nacore_list_elem_get_value()Gets the value contained in a list element.
nacore_list_elem_set_value()Sets the value contained in a list element.
nacore_list_elem_get_prev()Gets the previous element with regard to the given element in a list.
nacore_list_elem_get_next()Gets the following element with regard to the given element in a list.

Types

nacore_list

Doubly-linked list.

nacore_list_elem

Doubly-linked list element.

Functions

nacore_list_new()

_NACORE_DEF nacore_list nacore_list_new(nacore_get_size_cb gs_cb)

Creates a new list.

Use NULL as gs_cb to create a normal list, otherwise (auto-allocating list) gs_cb will be called to determine the quantity of memory to allocate and copy for each insertion and value modification.

Parameters

gs_cbData size callback or NULL.

Returns

Doubly-linked list or NULL if there was not enough memory.

nacore_list_free()

_NACORE_DEF void nacore_list_free(nacore_list list,
nacore_op_cb free_cb,
void *free_opaque)

Destroys a list and all its elements.

If the list is auto-allocating, value copies inside each element are destroied too.

In any case, before potentially being destroyed, each element value is passed to the free_cb callback, if one is given, as well as the specified extra data.

Once this function is called, referring to list or any element it contains will cause undefined behavior.  If the list is auto-allocating, the same is true for element values outside of the free_cb callback, if one is supplied.

Parameters

listDoubly-linked list.
free_cbCallback called for each list element or NULL.
free_opaqueExtra opaque data to be passed to free_cb or NULL.

nacore_list_get_n_elems()

_NACORE_DEF size_t nacore_list_get_n_elems(nacore_list list)

Gets the number of elements in a list.

Parameters

listDoubly-linked list.

Returns

Number of elements in the list or 0 if the list is empty.

nacore_list_get_head()

_NACORE_DEF nacore_list_elem nacore_list_get_head(nacore_list list)

Returns the head (first element) of a list.

Parameters

listDoubly-linked list.

Returns

Head of the list or NULL if the list is empty.

nacore_list_get_tail()

_NACORE_DEF nacore_list_elem nacore_list_get_tail(nacore_list list)

Returns the tail (last element) of a list.

Parameters

listDoubly-linked list.

Returns

Tail of the list or NULL if the list is empty.

nacore_list_prepend()

_NACORE_DEF nacore_list_elem nacore_list_prepend(nacore_list list,
void *gs_opaque,
void *value)

Creates a new list element and prepends it to a list.

Parameters

listDoubly-linked list.
gs_opaqueExtra opaque data to be passed to the data size callback or NULL.
valueThe value to be contained in the element.

Returns

New list element containing value or NULL if there was not enough memory.

See also

nacore_list_elem_prepend().

nacore_list_append()

_NACORE_DEF nacore_list_elem nacore_list_append(nacore_list list,
void *gs_opaque,
void *value)

Creates a new list element and appends it to a list.

Parameters

listDoubly-linked list.
gs_opaqueExtra opaque data to be passed to the data size callback or NULL.
valueThe value to be contained in the element.

Returns

New list element containing value or NULL if there was not enough memory.

See also

nacore_list_elem_append().

nacore_list_insert_before()

_NACORE_DEF nacore_list_elem nacore_list_insert_before(nacore_list list,
nacore_list_elem elem,
void *gs_opaque,
void *value)

Creates a new list element and inserts it before another element in a list.

Parameters

listDoubly-linked list.
elemThe element in the list that will follow the new element.
gs_opaqueExtra opaque data to be passed to the data size callback or NULL.
valueThe value to be contained in the element.

Returns

New list element containing value or NULL if there was not enough memory.

See also

nacore_list_elem_insert_before().

nacore_list_insert_after()

_NACORE_DEF nacore_list_elem nacore_list_insert_after(nacore_list list,
nacore_list_elem elem,
void *gs_opaque,
void *value)

Creates a new list element and inserts it after another element in a list.

Parameters

listDoubly-linked list.
elemThe element in the list that will precede the new element.
gs_opaqueExtra opaque data to be passed to the data size callback or NULL.
valueThe value to be contained in the element.

Returns

New list element containing value or NULL if there was not enough memory.

See also

nacore_list_elem_insert_after().

nacore_list_move_before()

_NACORE_DEF void nacore_list_move_before(nacore_list list,
nacore_list_elem dest,
nacore_list_elem src)

Moves an element before another element in a list.

If dest == src or if src immediately precedes dest already, the function does nothing.

Parameters

listDoubly-linked list.
destThe element before which src is to be moved.
srcThe element to be moved.

nacore_list_move_after()

_NACORE_DEF void nacore_list_move_after(nacore_list list,
nacore_list_elem dest,
nacore_list_elem src)

Moves an element after another element in a list.

If dest == src or if src immediately follows dest already, the function does nothing.

Parameters

listDoubly-linked list.
destThe element after which src is to be moved.
srcThe element to be moved.

nacore_list_pop()

_NACORE_DEF void * nacore_list_pop(nacore_list list,
nacore_list_elem elem)

Removes an element from a list, destroys it and returns the value it contains.

Once this function is called, referring to elem will cause undefined behavior.

Parameters

listDoubly-linked list.
elemList element to be removed.

Returns

The value contained in the element being removed.  If the list is auto-allocating the caller is in charge of free()ing the value.

See also

nacore_list_elem_pop().

nacore_list_find_first()

_NACORE_DEF nacore_list_elem nacore_list_find_first(nacore_list list,
nacore_cmp_cb cmp_cb,
void *cmp_opaque,
nacore_filter_cb filter_cb,
void *filter_opaque,
void *value)

Finds the first matching element inside a list.

It starts from the list head by comparing values using the provided cmp_cb callback.

If filter_cb is not NULL, it will be called along with filter_opaque when a matching element is found; if it is to be filtered out (i.e., filter_cb returns 0) the search will continue, etc.

Parameters

listDoubly-linked list.
cmp_cbValue comparison callback.
cmp_opaqueExtra opaque data to be passed to cmp_cb or NULL.
filter_cbValue filtering callback or NULL.
filter_opaqueExtra opaque data to be passed to filter_cb or NULL.
valueThe value to look for.

Returns

List element containing the desired value or NULL if no such element was found.

nacore_list_find_last()

_NACORE_DEF nacore_list_elem nacore_list_find_last(nacore_list list,
nacore_cmp_cb cmp_cb,
void *cmp_opaque,
nacore_filter_cb filter_cb,
void *filter_opaque,
void *value)

Finds the last matching element inside a list.

It start from the list tail by comparing values using the provided cmp_cb callback.

If filter_cb is not NULL, it will be called along with filter_opaque when a matching element is found; if it is to be filtered out (i.e., filter_cb returns 0) the search will continue, etc.

Parameters

listDoubly-linked list.
cmp_cbValue comparison callback.
cmp_opaqueExtra opaque data to be passed to cmp_cb or NULL.
filter_cbValue filtering callback or NULL.
filter_opaqueExtra opaque data to be passed to filter_cb or NULL.
valueThe value to look for.

Returns

List element containing the desired value or NULL if no such element was found.

nacore_list_find_before()

_NACORE_DEF nacore_list_elem nacore_list_find_before(
   nacore_list list,
   nacore_list_elem elem,
   nacore_cmp_cb cmp_cb,
   void *cmp_opaque,
   nacore_filter_cb filter_cb,
   void *filter_opaque,
   void *value
)

Finds the first matching element inside a list going backwards before another given element.

It does this by comparing values using the provided cmp_cb callback.

If filter_cb is not NULL, it will be called along with filter_opaque when a matching element is found; if it is to be filtered out (i.e., filter_cb returns 0) the search will continue, etc.

Parameters

listDoubly-linked list.
elemThe element before which the search happens.
cmp_cbValue comparison callback.
cmp_opaqueExtra opaque data to be passed to cmp_cb or NULL.
filter_cbValue filtering callback or NULL.
filter_opaqueExtra opaque data to be passed to filter_cb or NULL.
valueThe value to look for.

Returns

List element containing the desired value or NULL if no such element was found.

nacore_list_find_after()

_NACORE_DEF nacore_list_elem nacore_list_find_after(nacore_list list,
nacore_list_elem elem,
nacore_cmp_cb cmp_cb,
void *cmp_opaque,
nacore_filter_cb filter_cb,
void *filter_opaque,
void *value)

Finds the first matching element inside a list going forwards after another given element.

It does this by comparing values using the provided cmp_cb callback.

If filter_cb is not NULL, it will be called along with filter_opaque when a matching element is found; if it is to be filtered out (i.e., filter_cb returns 0) the search will continue, etc.

Parameters

listDoubly-linked list.
elemThe element before which the search happens.
cmp_cbValue comparison callback.
cmp_opaqueExtra opaque data to be passed to cmp_cb or NULL.
filter_cbValue filtering callback or NULL.
filter_opaqueExtra opaque data to be passed to filter_cb or NULL.
valueThe value to look for.

Returns

List element containing the desired value or NULL if no such element was found.

nacore_list_dup()

_NACORE_DEF nacore_list nacore_list_dup(nacore_list list,
nacore_get_size_cb gs_cb,
void *gs_opaque,
nacore_filter_cb filter_cb,
void *filter_opaque,
nacore_op_cb dup_cb,
void *dup_opaque)

Duplicates a list.

gs_cb is used as in nacore_list_new(), hence if it is not NULL the new list will be auto-allocating.

If filter_cb is not NULL, it will be called along with filter_opaque for each element; if it is to be filtered out (i.e., filter_cb returns 0) the element will not be included in the resulting list.

After the creation of each new element dup_cb is called, if such a callback is given, passing it the value (its copy if the new list is auto-allocating) and the specified extra data.

Parameters

listDoubly-linked list.
gs_cbData size callback or NULL.
gs_opaqueExtra opaque data to be passed to gs_cb or NULL.
filter_cbValue filtering callback or NULL.
filter_opaqueExtra opaque data to be passed to filter_cb or NULL.
dup_cbCallback called for each new list element or NULL.
dup_opaqueExtra opaque data to be passed to dup_cb or NULL.

Returns

Doubly-linked list or NULL if there was not enough memory.

nacore_list_merge()

_NACORE_DEF nacore_list nacore_list_merge(nacore_list dest,
nacore_list src)

Merges two lists by appending the elements of src to dest.

The two lists must have been created with the same data size callback (or NULL in both cases).

Once this function is called, referring to src or dest will cause undefined behavior.

Parameters

destFirst doubly-linked list.
srcSecond doubly-linked list.

Returns

The doubly-linked list containing elements from both lists.

nacore_list_dump()

_NACORE_DEF void nacore_list_dump(nacore_list list,
nacore_to_string_cb to_string_cb,
void *to_string_opaque)

Dumps the structure and content of a list on stderr.

Never rely on the exact output of this function, it is intended to be used solely for debugging purposes.

Parameters

listDoubly-linked list.
to_string_cbCallback returning a textual description of a value or NULL.
to_string_opaqueExtra opaque data to be passed to to_string_cb or NULL.

nacore_list_elem_new()

_NACORE_DEF nacore_list_elem nacore_list_elem_new(void *value)

Creates a new list element without adding it to a list.

Parameters

valueThe value to be contained in the element.

Returns

New list element containing value or NULL if there was not enough memory.

nacore_list_elem_free()

_NACORE_DEF void nacore_list_elem_free(nacore_list_elem elem)

Destroys a list element.

Once this function is called, referring to elem will cause undefined behavior.

Only to be used when the element is not part of a list.

Parameters

elemList element.

nacore_list_elem_prepend()

_NACORE_DEF void nacore_list_elem_prepend(nacore_list list,
nacore_list_elem elem)

Prepends a list element to a list.

Only to be used when the element is not part of a list.

Beware of auto-allocating lists...

Parameters

listDoubly-linked list.
elemList element.

See also

nacore_list_prepend().

nacore_list_elem_append()

_NACORE_DEF void nacore_list_elem_append(nacore_list list,
nacore_list_elem elem)

Appends a list element to a list.

Only to be used when the element is not part of a list.

Beware of auto-allocating lists...

Parameters

listDoubly-linked list.
elemList element.

See also

nacore_list_append().

nacore_list_elem_insert_before()

_NACORE_DEF void nacore_list_elem_insert_before(nacore_list list,
nacore_list_elem elem,
nacore_list_elem before)

Inserts a list element before another element in a list.

Only to be used when the element to be inserted is not part of a list.

Beware of auto-allocating lists...

Parameters

listDoubly-linked list.
elemList element.

See also

nacore_list_insert_before().

nacore_list_elem_insert_after()

_NACORE_DEF void nacore_list_elem_insert_after(nacore_list list,
nacore_list_elem elem,
nacore_list_elem after)

Inserts a list element after another element in a list.

Only to be used when the element to be inserted is not part of a list.

Beware of auto-allocating lists...

Parameters

listDoubly-linked list.
elemList element.

See also

nacore_list_insert_after().

nacore_list_elem_pop()

_NACORE_DEF void nacore_list_elem_pop(nacore_list list,
nacore_list_elem elem)

Removes an element from a list without destroying it.

Parameters

listDoubly-linked list.
elemList element.

See also

nacore_list_pop().

nacore_list_elem_get_value()

_NACORE_DEF void * nacore_list_elem_get_value(nacore_list list,
nacore_list_elem elem)

Gets the value contained in a list element.

The list parameter is currently unused.  It is however good if you set it to NULL only when elem is not part of a list.

Parameters

listDoubly-linked list the element belongs to or NULL.
elemList element.

Returns

The value contained in elem.

nacore_list_elem_set_value()

_NACORE_DEF int nacore_list_elem_set_value(nacore_list list,
nacore_list_elem elem,
nacore_op_cb free_cb,
void *free_opaque,
void *gs_opaque,
void *value)

Sets the value contained in a list element.

If the element is not part of a list set list as NULL, in which case this function shall behave as if the element is part of a normal list.

If the list is auto-allocating, first the old value is free()d, then a copy of the new value is put into the element.  Before potentially being destroyed, the element value is passed to the free_cb callback, if one is given, as well as the specified extra data.

Parameters

listDoubly-linked list the element belongs to or NULL.
elemList element.
free_cbCallback called to destroy element value or NULL.
free_opaqueExtra opaque data to be passed to free_cb or NULL.
gs_opaqueExtra opaque data to be passed to the data size callback or NULL.
valueThe value.

Returns

0 on success or ENOMEM if there was not enough memory (auto-allocating lists only).

nacore_list_elem_get_prev()

_NACORE_DEF nacore_list_elem nacore_list_elem_get_prev(nacore_list list,
nacore_list_elem elem)

Gets the previous element with regard to the given element in a list.

Parameters

listDoubly-linked list the given element belongs to.
elemList element.

Returns

Previous element w.r.t. the given element or NULL if there is none (i.e., elem is the head of the list).

nacore_list_elem_get_next()

_NACORE_DEF nacore_list_elem nacore_list_elem_get_next(nacore_list list,
nacore_list_elem elem)

Gets the following element with regard to the given element in a list.

Parameters

listDoubly-linked list the given element belongs to.
elemList element.

Returns

Following element w.r.t. the given element or NULL if there is none (i.e., elem is the tail of the list).

_NACORE_DEF nacore_list nacore_list_new(nacore_get_size_cb gs_cb)
Creates a new list.
_NACORE_DEF void nacore_list_free(nacore_list list,
nacore_op_cb free_cb,
void *free_opaque)
Destroys a list and all its elements.
_NACORE_DEF size_t nacore_list_get_n_elems(nacore_list list)
Gets the number of elements in a list.
_NACORE_DEF nacore_list_elem nacore_list_get_head(nacore_list list)
Returns the head (first element) of a list.
_NACORE_DEF nacore_list_elem nacore_list_get_tail(nacore_list list)
Returns the tail (last element) of a list.
_NACORE_DEF nacore_list_elem nacore_list_prepend(nacore_list list,
void *gs_opaque,
void *value)
Creates a new list element and prepends it to a list.
_NACORE_DEF nacore_list_elem nacore_list_append(nacore_list list,
void *gs_opaque,
void *value)
Creates a new list element and appends it to a list.
_NACORE_DEF nacore_list_elem nacore_list_insert_before(nacore_list list,
nacore_list_elem elem,
void *gs_opaque,
void *value)
Creates a new list element and inserts it before another element in a list.
_NACORE_DEF nacore_list_elem nacore_list_insert_after(nacore_list list,
nacore_list_elem elem,
void *gs_opaque,
void *value)
Creates a new list element and inserts it after another element in a list.
_NACORE_DEF void nacore_list_move_before(nacore_list list,
nacore_list_elem dest,
nacore_list_elem src)
Moves an element before another element in a list.
_NACORE_DEF void nacore_list_move_after(nacore_list list,
nacore_list_elem dest,
nacore_list_elem src)
Moves an element after another element in a list.
_NACORE_DEF void * nacore_list_pop(nacore_list list,
nacore_list_elem elem)
Removes an element from a list, destroys it and returns the value it contains.
_NACORE_DEF nacore_list_elem nacore_list_find_first(nacore_list list,
nacore_cmp_cb cmp_cb,
void *cmp_opaque,
nacore_filter_cb filter_cb,
void *filter_opaque,
void *value)
Finds the first matching element inside a list.
_NACORE_DEF nacore_list_elem nacore_list_find_last(nacore_list list,
nacore_cmp_cb cmp_cb,
void *cmp_opaque,
nacore_filter_cb filter_cb,
void *filter_opaque,
void *value)
Finds the last matching element inside a list.
_NACORE_DEF nacore_list_elem nacore_list_find_before(
   nacore_list list,
   nacore_list_elem elem,
   nacore_cmp_cb cmp_cb,
   void *cmp_opaque,
   nacore_filter_cb filter_cb,
   void *filter_opaque,
   void *value
)
Finds the first matching element inside a list going backwards before another given element.
_NACORE_DEF nacore_list_elem nacore_list_find_after(nacore_list list,
nacore_list_elem elem,
nacore_cmp_cb cmp_cb,
void *cmp_opaque,
nacore_filter_cb filter_cb,
void *filter_opaque,
void *value)
Finds the first matching element inside a list going forwards after another given element.
_NACORE_DEF nacore_list nacore_list_dup(nacore_list list,
nacore_get_size_cb gs_cb,
void *gs_opaque,
nacore_filter_cb filter_cb,
void *filter_opaque,
nacore_op_cb dup_cb,
void *dup_opaque)
Duplicates a list.
_NACORE_DEF nacore_list nacore_list_merge(nacore_list dest,
nacore_list src)
Merges two lists by appending the elements of src to dest.
_NACORE_DEF void nacore_list_dump(nacore_list list,
nacore_to_string_cb to_string_cb,
void *to_string_opaque)
Dumps the structure and content of a list on stderr.
_NACORE_DEF nacore_list_elem nacore_list_elem_new(void *value)
Creates a new list element without adding it to a list.
_NACORE_DEF void nacore_list_elem_free(nacore_list_elem elem)
Destroys a list element.
_NACORE_DEF void nacore_list_elem_prepend(nacore_list list,
nacore_list_elem elem)
Prepends a list element to a list.
_NACORE_DEF void nacore_list_elem_append(nacore_list list,
nacore_list_elem elem)
Appends a list element to a list.
_NACORE_DEF void nacore_list_elem_insert_before(nacore_list list,
nacore_list_elem elem,
nacore_list_elem before)
Inserts a list element before another element in a list.
_NACORE_DEF void nacore_list_elem_insert_after(nacore_list list,
nacore_list_elem elem,
nacore_list_elem after)
Inserts a list element after another element in a list.
_NACORE_DEF void nacore_list_elem_pop(nacore_list list,
nacore_list_elem elem)
Removes an element from a list without destroying it.
_NACORE_DEF void * nacore_list_elem_get_value(nacore_list list,
nacore_list_elem elem)
Gets the value contained in a list element.
_NACORE_DEF int nacore_list_elem_set_value(nacore_list list,
nacore_list_elem elem,
nacore_op_cb free_cb,
void *free_opaque,
void *gs_opaque,
void *value)
Sets the value contained in a list element.
_NACORE_DEF nacore_list_elem nacore_list_elem_get_prev(nacore_list list,
nacore_list_elem elem)
Gets the previous element with regard to the given element in a list.
_NACORE_DEF nacore_list_elem nacore_list_elem_get_next(nacore_list list,
nacore_list_elem elem)
Gets the following element with regard to the given element in a list.
Close