linked-list.h File Reference

Defines a simple implementation of linked lists and functions to manipulate it. More...

#include "uevloop/utils/closure.h"

Include dependency graph for linked-list.h:

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

Go to the source code of this file.

Data Structures
struct	uel_llist_node_t
	Defines a node of the linked list. Holds a void pointer. More...
struct	uel_llist_t
	Defines a linked list. If it is empty, head == tail == NULL. Pushing or popping from both the head or tail is always O(1). More...

Functions
void	uel_llist_init (uel_llist_t *list)
	Initialised a linked list. More...
void	uel_llist_push_head (uel_llist_t *list, uel_llist_node_t *node)
	Pushes a node to the head of the list. More...
void	uel_llist_push_tail (uel_llist_t *list, uel_llist_node_t *node)
	Pushes a node to the tail of the list. More...
uel_llist_node_t *	uel_llist_pop_head (uel_llist_t *list)
	Pops a node from the head of the list. More...
uel_llist_node_t *	uel_llist_pop_tail (uel_llist_t *list)
	Pops a node from the tail of the list. More...
uel_llist_node_t *	uel_llist_peek_head (uel_llist_t *list)
	Peeks the element at the head of the list. More...
uel_llist_node_t *	uel_llist_peek_tail (uel_llist_t *list)
	Peeks the element at the tail of the list. More...
bool	uel_llist_remove (uel_llist_t *list, uel_llist_node_t *node)
	Removes a node from the queue. More...
uel_llist_t	uel_llist_remove_while (uel_llist_t *list, uel_closure_t *should_remove)
	Splits a list in two. The rupture point is determined by the supplied closure. More...
void	uel_llist_insert_at (uel_llist_t *list, uel_llist_node_t *node, uel_closure_t *should_insert)
	Scans a list until it finds a suitable spot to insert the provided node. More...

Detailed Description

Defines a simple implementation of linked lists and functions to manipulate it.

Function Documentation

uel_llist_init()

void uel_llist_init

(

uel_llist_t *

list

)

Initialised a linked list.

Parameters

list	The list to be initialised. It will be empty after initialisation.

uel_llist_insert_at()

void uel_llist_insert_at	(	uel_llist_t *	list,
		uel_llist_node_t *	node,
		uel_closure_t *	should_insert
	)

Scans a list until it finds a suitable spot to insert the provided node.

This function iterates the linked list invoking the supplied closure until it returns true. The supplied node is then inserted at this position.

The should_insert closure will be invoked for each pair of node addresses in the range [NULL, &NODE_1, &NODE_2, ..., &NODE_N, NULL] as parameter. When it finds a suitable position, it must return true.

Parameters

list	The list to insert the node at
node	The node to be inserted
should_insert	A closure that returns whether the node ought to be inserted at the current position. The closure function must unpack the closure parameters to a uel_llist_node_t **[2] and return a boolean.

uel_llist_peek_head()

uel_llist_node_t* uel_llist_peek_head

(

uel_llist_t *

list

)

Peeks the element at the head of the list.

Parameters

list	The list from where the node will be peeked

Returns

node A pointer to the peeked node if it exists. Otherwise, NULL.

uel_llist_peek_tail()

uel_llist_node_t* uel_llist_peek_tail

(

uel_llist_t *

list

)

Peeks the element at the tail of the list.

Parameters

list	The list from where the node will be peeked

Returns

node A pointer to the peeked node if it exists. Otherwise, NULL.

uel_llist_pop_head()

uel_llist_node_t* uel_llist_pop_head

(

uel_llist_t *

list

)

Pops a node from the head of the list.

Parameters

list	The list from where the node will be popped

Returns

node A pointer to the popped node if it exists. Otherwise, NULL.

uel_llist_pop_tail()

uel_llist_node_t* uel_llist_pop_tail

(

uel_llist_t *

list

)

Pops a node from the tail of the list.

Parameters

list	The list from where the node will be popped

Returns

node A pointer to the popped node if it exists. Otherwise, NULL.

uel_llist_push_head()

void uel_llist_push_head	(	uel_llist_t *	list,
		uel_llist_node_t *	node
	)

Pushes a node to the head of the list.

Parameters

list	The list into which to insert the node
node	The node to be inserted.

uel_llist_push_tail()

void uel_llist_push_tail	(	uel_llist_t *	list,
		uel_llist_node_t *	node
	)

Pushes a node to the tail of the list.

Parameters

list	The list into which to insert the node
node	The node to be inserted.

uel_llist_remove()

bool uel_llist_remove	(	uel_llist_t *	list,
		uel_llist_node_t *	node
	)

Removes a node from the queue.

Parameters

list	The list from where the node will be removed
node	Address of the node being removed

Returns

Whether the node was found and removed

uel_llist_remove_while()

uel_llist_t uel_llist_remove_while	(	uel_llist_t *	list,
		uel_closure_t *	should_remove
	)

Splits a list in two. The rupture point is determined by the supplied closure.

This function iterates the linked list invoking the provided closure for each node in it. While the closure returns true, nodes are popped from the list.

Parameters

list	The list from where to pop nodes
should_remove	A closure that will be invoked taking each node as parameter. The closure should return a boolean indicating whether the node should be removed or not.

Returns

A new list containing the removed nodes, in their original order.