Generic linked list implementation. More...

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

Include dependency graph for lists.c:

Functions
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 292 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 324 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 276 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 254 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 244 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 249 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 239 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 282 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 287 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 339 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 312 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 329 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 334 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 398 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 408 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 382 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 368 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 363 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 353 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 358 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 348 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 388 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 393 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 423 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 403 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 413 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 418 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()

◆ 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()