Generic linked list implementation. More...

#include "lists.h"
#include "os_helpers.h"

Include dependency graph for lists.c:

Functions
static bool	push_front_internal (flist_node_t *list, flist_node_t node, bool doubly_linked)

static bool	pop_front_internal (flist_node_t **list, f_list_node_del del_func, bool doubly_linked)

static bool	push_back_internal (flist_node_t *list, flist_node_t node, bool doubly_linked)

static bool	insert_after_internal (flist_node_t ref, flist_node_t node, bool doubly_linked)

static bool	remove_internal (flist_node_t *list, flist_node_t node, f_list_node_del del_func, bool doubly_linked)

static size_t	remove_if_internal (flist_node_t **list, f_list_node_pred pred_func, f_list_node_del del_func, bool doubly_linked)

static bool	sort_internal (flist_node_t **list, f_list_node_cmp cmp_func, bool doubly_linked)

static size_t	unique_internal (flist_node_t **list, f_list_node_bin_pred pred_func, f_list_node_del del_func, bool doubly_linked)

static bool	reverse_internal (flist_node_t **list, bool doubly_linked)

bool	flist_push_front (flist_node_t *list, flist_node_t node)
	Add a node at the beginning of the forward list.

bool	flist_pop_front (flist_node_t **list, f_list_node_del del_func)
	Remove and delete the first node from the forward list.

bool	flist_push_back (flist_node_t *list, flist_node_t node)
	Add a node at the end of the forward list.

bool	flist_pop_back (flist_node_t **list, f_list_node_del del_func)
	Remove and delete the last node from the forward list.

bool	flist_insert_after (flist_node_t *list, flist_node_t ref, flist_node_t *node)
	Insert a node after a reference node in the forward list.

bool	flist_remove (flist_node_t *list, flist_node_t node, f_list_node_del del_func)
	Remove and delete a specific node from the forward list.

size_t	flist_remove_if (flist_node_t **list, f_list_node_pred pred_func, f_list_node_del del_func)
	Remove all nodes matching a predicate from the forward list.

bool	flist_clear (flist_node_t **list, f_list_node_del del_func)
	Remove and delete all nodes from the forward list.

size_t	flist_size (flist_node_t const list)
	Get the number of nodes in the forward list.

bool	flist_empty (flist_node_t const list)
	Check if the forward list is empty.

bool	flist_sort (flist_node_t **list, f_list_node_cmp cmp_func)
	Sort the forward list using a comparison function.

size_t	flist_unique (flist_node_t **list, f_list_node_bin_pred pred_func, f_list_node_del del_func)
	Remove consecutive duplicate nodes from the forward list.

bool	flist_reverse (flist_node_t **list)
	Reverse the order of nodes in the forward list.

bool	list_push_front (list_node_t *list, list_node_t node)
	Add a node at the beginning of the doubly-linked list.

bool	list_pop_front (list_node_t **list, f_list_node_del del_func)
	Remove and delete the first node from the doubly-linked list.

bool	list_push_back (list_node_t *list, list_node_t node)
	Add a node at the end of the doubly-linked list.

bool	list_pop_back (list_node_t **list, f_list_node_del del_func)
	Remove and delete the last node from the doubly-linked list.

bool	list_insert_before (list_node_t *list, list_node_t ref, list_node_t *node)
	Insert a node before a reference node in the doubly-linked list.

bool	list_insert_after (list_node_t *list, list_node_t ref, list_node_t *node)
	Insert a node after a reference node in the doubly-linked list.

bool	list_remove (list_node_t *list, list_node_t node, f_list_node_del del_func)
	Remove and delete a specific node from the doubly-linked list.

size_t	list_remove_if (list_node_t **list, f_list_node_pred pred_func, f_list_node_del del_func)
	Remove all nodes matching a predicate from the doubly-linked list.

bool	list_clear (list_node_t **list, f_list_node_del del_func)
	Remove and delete all nodes from the doubly-linked list.

size_t	list_size (list_node_t const list)
	Get the number of nodes in the doubly-linked list.

bool	list_empty (list_node_t const list)
	Check if the doubly-linked list is empty.

bool	list_sort (list_node_t **list, f_list_node_cmp cmp_func)
	Sort the doubly-linked list using a comparison function.

size_t	list_unique (list_node_t **list, f_list_node_bin_pred pred_func, f_list_node_del del_func)
	Remove consecutive duplicate nodes from the doubly-linked list.

bool	list_reverse (list_node_t **list)
	Reverse the order of nodes in the doubly-linked list.

Detailed Description

Generic linked list implementation.

Provides both singly-linked (flist) and doubly-linked (list) implementations.

Definition in file lists.c.

Function Documentation

◆ flist_clear()

bool flist_clear	(	flist_node_t **	list,
		f_list_node_del	del_func
	)

Remove and delete all nodes from the forward list.

Parameters

[in,out]	list	Pointer to the list head
[in]	del_func	Function to delete each node (can be NULL)

Returns: true on success, false on error

Note: Time complexity: O(n)

Definition at line 290 of file lists.c.

◆ flist_empty()

bool flist_empty ( flist_node_t *const * list )

Check if the forward list is empty.

Parameters

[in] list Pointer to the list head

Returns: true if empty or NULL, false otherwise

Note: Time complexity: O(1)

Definition at line 322 of file lists.c.

◆ flist_insert_after()

bool flist_insert_after	(	flist_node_t **	list,
		flist_node_t *	ref,
		flist_node_t *	node
	)

Insert a node after a reference node in the forward list.

Parameters

[in,out]	list	Pointer to the list head
[in]	ref	Reference node (must be in list)
[in]	node	Node to insert (must have node->next == NULL)

Returns: true on success, false on error

Note: Time complexity: O(1)

Definition at line 274 of file lists.c.

◆ flist_pop_back()

bool flist_pop_back	(	flist_node_t **	list,
		f_list_node_del	del_func
	)

Remove and delete the last node from the forward list.

Parameters

[in,out]	list	Pointer to the list head
[in]	del_func	Function to delete the node (can be NULL)

Returns: true on success, false if list is empty or NULL

Note: Time complexity: O(n)

Definition at line 252 of file lists.c.

◆ flist_pop_front()

bool flist_pop_front	(	flist_node_t **	list,
		f_list_node_del	del_func
	)

Remove and delete the first node from the forward list.

Parameters

[in,out]	list	Pointer to the list head
[in]	del_func	Function to delete the node (can be NULL)

Returns: true on success, false if list is empty or NULL

Note: Time complexity: O(1)

Definition at line 242 of file lists.c.

◆ flist_push_back()

bool flist_push_back	(	flist_node_t **	list,
		flist_node_t *	node
	)

Add a node at the end of the forward list.

Parameters

[in,out]	list	Pointer to the list head
[in]	node	Node to add (must have node->next == NULL)

Returns: true on success, false on error

Note: Time complexity: O(n)

Definition at line 247 of file lists.c.

◆ flist_push_front()

bool flist_push_front	(	flist_node_t **	list,
		flist_node_t *	node
	)

Add a node at the beginning of the forward list.

Parameters

[in,out]	list	Pointer to the list head
[in]	node	Node to add (must have node->next == NULL)

Returns: true on success, false on error

Note: Time complexity: O(1)

Definition at line 237 of file lists.c.

◆ flist_remove()

bool flist_remove	(	flist_node_t **	list,
		flist_node_t *	node,
		f_list_node_del	del_func
	)

Remove and delete a specific node from the forward list.

Parameters

[in,out]	list	Pointer to the list head
[in]	node	Node to remove (must be in list)
[in]	del_func	Function to delete the node (can be NULL)

Returns: true on success, false if node not found or error

Note: Time complexity: O(n)

Definition at line 280 of file lists.c.

◆ flist_remove_if()

size_t flist_remove_if	(	flist_node_t **	list,
		f_list_node_pred	pred_func,
		f_list_node_del	del_func
	)

Remove all nodes matching a predicate from the forward list.

Parameters

[in,out]	list	Pointer to the list head
[in]	pred_func	Predicate function to test each node
[in]	del_func	Function to delete removed nodes (can be NULL)

Returns: Number of nodes removed

Note: Time complexity: O(n)

Definition at line 285 of file lists.c.

◆ flist_reverse()

bool flist_reverse ( flist_node_t ** list )

Reverse the order of nodes in the forward list.

Parameters

[in,out] list Pointer to the list head

Returns: true on success, false on error

Note: Time complexity: O(n)

Definition at line 337 of file lists.c.

◆ flist_size()

size_t flist_size ( flist_node_t *const * list )

Get the number of nodes in the forward list.

Parameters

[in] list Pointer to the list head

Returns: Number of nodes (0 if list is NULL or empty)

Note: Time complexity: O(n)

Definition at line 310 of file lists.c.

◆ flist_sort()

bool flist_sort	(	flist_node_t **	list,
		f_list_node_cmp	cmp_func
	)

Sort the forward list using a comparison function.

Parameters

[in,out]	list	Pointer to the list head
[in]	cmp_func	Comparison function (returns true if a < b)

Returns: true on success, false on error

Note: Time complexity: O(n log n) - merge sort algorithm

Definition at line 327 of file lists.c.

◆ flist_unique()

size_t flist_unique	(	flist_node_t **	list,
		f_list_node_bin_pred	pred_func,
		f_list_node_del	del_func
	)

Remove consecutive duplicate nodes from the forward list.

Parameters

[in,out]	list	Pointer to the list head
[in]	pred_func	Binary predicate to test equality (returns true if a == b)
[in]	del_func	Function to delete removed nodes (can be NULL)

Returns: Number of nodes removed

Note: Time complexity: O(n); List should be sorted first for best results

Definition at line 332 of file lists.c.

◆ insert_after_internal()

static bool insert_after_internal	(	flist_node_t *	ref,
		flist_node_t *	node,
		bool	doubly_linked
	)

static

Definition at line 78 of file lists.c.

◆ list_clear()

bool list_clear	(	list_node_t **	list,
		f_list_node_del	del_func
	)

Remove and delete all nodes from the doubly-linked list.

Parameters

[in,out]	list	Pointer to the list head
[in]	del_func	Function to delete each node (can be NULL)

Returns: true on success, false on error

Note: Time complexity: O(n)

Definition at line 396 of file lists.c.

◆ list_empty()

bool list_empty ( list_node_t *const * list )

Check if the doubly-linked list is empty.

Parameters

[in] list Pointer to the list head

Returns: true if empty or NULL, false otherwise

Note: Time complexity: O(1)

Definition at line 406 of file lists.c.

◆ list_insert_after()

bool list_insert_after	(	list_node_t **	list,
		list_node_t *	ref,
		list_node_t *	node
	)

Insert a node after a reference node in the doubly-linked list.

Parameters

[in,out]	list	Pointer to the list head
[in]	ref	Reference node (must be in list)
[in]	node	Node to insert (must have node->_list.next == NULL and node->prev == NULL)

Returns: true on success, false on error

Note: Time complexity: O(1)

Definition at line 380 of file lists.c.

◆ list_insert_before()

bool list_insert_before	(	list_node_t **	list,
		list_node_t *	ref,
		list_node_t *	node
	)

Insert a node before a reference node in the doubly-linked list.

Parameters

[in,out]	list	Pointer to the list head
[in]	ref	Reference node (must be in list)
[in]	node	Node to insert (must have node->_list.next == NULL and node->prev == NULL)

Returns: true on success, false on error

Note: Time complexity: O(1); This function is only available for doubly-linked lists

Definition at line 366 of file lists.c.

◆ list_pop_back()

bool list_pop_back	(	list_node_t **	list,
		f_list_node_del	del_func
	)

Remove and delete the last node from the doubly-linked list.

Parameters

[in,out]	list	Pointer to the list head
[in]	del_func	Function to delete the node (can be NULL)

Returns: true on success, false if list is empty or NULL

Note: Time complexity: O(n)

Definition at line 361 of file lists.c.

◆ list_pop_front()

bool list_pop_front	(	list_node_t **	list,
		f_list_node_del	del_func
	)

Remove and delete the first node from the doubly-linked list.

Parameters

[in,out]	list	Pointer to the list head
[in]	del_func	Function to delete the node (can be NULL)

Returns: true on success, false if list is empty or NULL

Note: Time complexity: O(1)

Definition at line 351 of file lists.c.

◆ list_push_back()

bool list_push_back	(	list_node_t **	list,
		list_node_t *	node
	)

Add a node at the end of the doubly-linked list.

Parameters

[in,out]	list	Pointer to the list head
[in]	node	Node to add (must have node->_list.next == NULL and node->prev == NULL)

Returns: true on success, false on error

Note: Time complexity: O(n)

Definition at line 356 of file lists.c.

◆ list_push_front()

bool list_push_front	(	list_node_t **	list,
		list_node_t *	node
	)

Add a node at the beginning of the doubly-linked list.

Parameters

[in,out]	list	Pointer to the list head
[in]	node	Node to add (must have node->_list.next == NULL and node->prev == NULL)

Returns: true on success, false on error

Note: Time complexity: O(1)

Definition at line 346 of file lists.c.

◆ list_remove()

bool list_remove	(	list_node_t **	list,
		list_node_t *	node,
		f_list_node_del	del_func
	)

Remove and delete a specific node from the doubly-linked list.

Parameters

[in,out]	list	Pointer to the list head
[in]	node	Node to remove (must be in list)
[in]	del_func	Function to delete the node (can be NULL)

Returns: true on success, false if node not found or error

Note: Time complexity: O(n)

Definition at line 386 of file lists.c.

◆ list_remove_if()

size_t list_remove_if	(	list_node_t **	list,
		f_list_node_pred	pred_func,
		f_list_node_del	del_func
	)

Remove all nodes matching a predicate from the doubly-linked list.

Parameters

[in,out]	list	Pointer to the list head
[in]	pred_func	Predicate function to test each node
[in]	del_func	Function to delete removed nodes (can be NULL)

Returns: Number of nodes removed

Note: Time complexity: O(n)

Definition at line 391 of file lists.c.

◆ list_reverse()

bool list_reverse ( list_node_t ** list )

Reverse the order of nodes in the doubly-linked list.

Parameters

[in,out] list Pointer to the list head

Returns: true on success, false on error

Note: Time complexity: O(n)

Definition at line 421 of file lists.c.

◆ list_size()

size_t list_size ( list_node_t *const * list )

Get the number of nodes in the doubly-linked list.

Parameters

[in] list Pointer to the list head

Returns: Number of nodes (0 if list is NULL or empty)

Note: Time complexity: O(n)

Definition at line 401 of file lists.c.

◆ list_sort()

bool list_sort	(	list_node_t **	list,
		f_list_node_cmp	cmp_func
	)

Sort the doubly-linked list using a comparison function.

Parameters

[in,out]	list	Pointer to the list head
[in]	cmp_func	Comparison function (returns true if a < b)

Returns: true on success, false on error

Note: Time complexity: O(n log n) - merge sort algorithm

Definition at line 411 of file lists.c.

◆ list_unique()

size_t list_unique	(	list_node_t **	list,
		f_list_node_bin_pred	pred_func,
		f_list_node_del	del_func
	)

Remove consecutive duplicate nodes from the doubly-linked list.

Parameters

[in,out]	list	Pointer to the list head
[in]	pred_func	Binary predicate to test equality (returns true if a == b)
[in]	del_func	Function to delete removed nodes (can be NULL)

Returns: Number of nodes removed

Note: Time complexity: O(n); List should be sorted first for best results

Definition at line 416 of file lists.c.

◆ pop_front_internal()

static bool pop_front_internal	(	flist_node_t **	list,
		f_list_node_del	del_func,
		bool	doubly_linked
	)

static

Definition at line 31 of file lists.c.

◆ push_back_internal()

static bool push_back_internal	(	flist_node_t **	list,
		flist_node_t *	node,
		bool	doubly_linked
	)

static

Definition at line 51 of file lists.c.

◆ push_front_internal()

static bool push_front_internal	(	flist_node_t **	list,
		flist_node_t *	node,
		bool	doubly_linked
	)

static

Definition at line 15 of file lists.c.

◆ remove_if_internal()

static size_t remove_if_internal	(	flist_node_t **	list,
		f_list_node_pred	pred_func,
		f_list_node_del	del_func,
		bool	doubly_linked
	)

static

Definition at line 130 of file lists.c.

◆ remove_internal()

static bool remove_internal	(	flist_node_t **	list,
		flist_node_t *	node,
		f_list_node_del	del_func,
		bool	doubly_linked
	)

static

Definition at line 94 of file lists.c.

◆ reverse_internal()

static bool reverse_internal	(	flist_node_t **	list,
		bool	doubly_linked
	)

static

Definition at line 210 of file lists.c.

◆ sort_internal()

static bool sort_internal	(	flist_node_t **	list,
		f_list_node_cmp	cmp_func,
		bool	doubly_linked
	)

static

Definition at line 155 of file lists.c.

◆ unique_internal()

static size_t unique_internal	(	flist_node_t **	list,
		f_list_node_bin_pred	pred_func,
		f_list_node_del	del_func,
		bool	doubly_linked
	)

static

Definition at line 187 of file lists.c.

Functions

Detailed Description

Function Documentation

◆ flist_clear()

◆ flist_empty()

◆ flist_insert_after()

◆ flist_pop_back()

◆ flist_pop_front()

◆ flist_push_back()

◆ flist_push_front()

◆ flist_remove()

◆ flist_remove_if()

◆ flist_reverse()

◆ flist_size()

◆ flist_sort()

◆ flist_unique()

◆ insert_after_internal()

◆ list_clear()

◆ list_empty()

◆ list_insert_after()

◆ list_insert_before()

◆ list_pop_back()

◆ list_pop_front()

◆ list_push_back()

◆ list_push_front()

◆ list_remove()

◆ list_remove_if()

◆ list_reverse()

◆ list_size()

◆ list_sort()

◆ list_unique()

◆ pop_front_internal()

◆ push_back_internal()

◆ push_front_internal()

◆ remove_if_internal()

◆ remove_internal()

◆ reverse_internal()

◆ sort_internal()

◆ unique_internal()