Generic linked list implementation (singly and doubly-linked) More...

#include <stdlib.h>
#include <stdbool.h>

Include dependency graph for lists.h:

This graph shows which files directly or indirectly include this file:

Classes
struct	flist_node_t
	Forward list node structure (singly-linked) More...

struct	list_node_t
	Doubly-linked list node structure. More...

Typedefs
typedef struct flist_node_t	flist_node_t

typedef struct list_node_t	list_node_t

typedef void(*	f_list_node_del) (flist_node_t *node)
	Callback function to delete/free a node.

typedef bool(*	f_list_node_cmp) (const flist_node_t a, const flist_node_t b)
	Callback function to compare two nodes for sorting.

typedef bool(*	f_list_node_pred) (const flist_node_t *node)
	Callback function to test a single node (unary predicate)

typedef bool(*	f_list_node_bin_pred) (const flist_node_t a, const flist_node_t b)
	Callback function to test two nodes for equality (binary predicate)

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 (singly and doubly-linked)

This file provides both forward lists (singly-linked) and doubly-linked lists. Based on app-ethereum implementation.

Definition in file lists.h.

Typedef Documentation

◆ f_list_node_bin_pred

f_list_node_bin_pred

Callback function to test two nodes for equality (binary predicate)

This function is used by flist_unique() and list_unique() to determine if two consecutive nodes are considered equal and should be deduplicated.

Parameters

[in]	a	First node to compare
[in]	b	Second node to compare

Returns: true if nodes are equal (b should be removed), false otherwise

Note: Both parameters are never NULL when called by list functions; Typically used after sorting to remove consecutive duplicates

Definition at line 102 of file lists.h.

◆ f_list_node_cmp

f_list_node_cmp

Callback function to compare two nodes for sorting.

This function is used by flist_sort() and list_sort() to determine node order. It should return true if node 'a' should come before node 'b' in the sorted list.

Parameters

[in]	a	First node to compare
[in]	b	Second node to compare

Returns: true if a < b (a should come before b), false otherwise

Note: Both parameters are never NULL when called by list functions; Use consistent comparison logic for stable sorting

Definition at line 72 of file lists.h.

◆ f_list_node_del

f_list_node_del

Callback function to delete/free a node.

This function is called when a node needs to be deleted from the list. It should free any resources associated with the node and the node itself.

Parameters

[in] node The node to delete (never NULL when called by list functions)

Note: If NULL is passed to list functions, nodes are removed but not freed; This function should handle the complete node lifecycle cleanup

Definition at line 56 of file lists.h.

◆ f_list_node_pred

f_list_node_pred

Callback function to test a single node (unary predicate)

This function is used by flist_remove_if() and list_remove_if() to determine which nodes should be removed from the list.

Parameters

[in] node The node to test

Returns: true if the node matches the condition (should be removed), false otherwise

Note: The parameter is never NULL when called by list functions

Definition at line 86 of file lists.h.

◆ flist_node_t

typedef struct flist_node_t flist_node_t

◆ list_node_t

typedef struct list_node_t list_node_t

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.

Classes

Typedefs

Functions

Detailed Description

Typedef Documentation

◆ f_list_node_bin_pred

◆ f_list_node_cmp

◆ f_list_node_del

◆ f_list_node_pred

◆ flist_node_t

◆ list_node_t

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