list.h File Reference

Doubly linked list implementation with memory management. More...

#include <stddef.h>
#include <stdio.h>

Include dependency graph for list.h:

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

Go to the source code of this file.

Classes
struct	list_node
struct	list_t

Macros
#define	LIST_FOR_EACH(list, node)   for (list_node_t * (node) = (list)->head; (node); (node) = (node)->next)
#define	LIST_FOR_EACH_REVERSE(list, node)   for (list_node_t * (node) = (list)->tail; (node); (node) = (node)->prev)

Typedefs
typedef struct list_node	list_node_t

Functions
list_t *	list_new (size_t elem_size)
void	list_free (list_t *list)
void	list_clear (list_t *list)
size_t	list_size (const list_t *list)
void	list_push_back (list_t *list, void *elem)
void	list_pop_back (list_t *list)
void	list_push_front (list_t *list, void *elem)
void	list_pop_front (list_t *list)
void *	list_get (const list_t *list, size_t index)
int	list_index_of (const list_t *list, void *elem)
void	list_insert (list_t *list, size_t index, void *elem)
void	list_remove (list_t *list, void *elem)
void	list_insert_after (list_t *list, void *elem, void *after)
void	list_insert_before (list_t *list, void *elem, void *before)

Detailed Description

Doubly linked list implementation with memory management.

Definition in file list.h.

Macro Definition Documentation

LIST_FOR_EACH

#define LIST_FOR_EACH	(		list,
			node
	)		for (list_node_t * (node) = (list)->head; (node); (node) = (node)->next)

Forward iteration macro for traversing all nodes in a list. Iterates from head to tail. Usage: LIST_FOR_EACH(my_list, node) { ... use node->data ... }

Parameters

list	Pointer to the list to iterate over.
node	Name of the list_node_t* variable to use in the loop body.

Definition at line 176 of file list.h.

LIST_FOR_EACH_REVERSE

#define LIST_FOR_EACH_REVERSE	(		list,
			node
	)		for (list_node_t * (node) = (list)->tail; (node); (node) = (node)->prev)

Reverse iteration macro for traversing all nodes in a list. Iterates from tail to head. Usage: LIST_FOR_EACH_REVERSE(my_list, node) { ... use node->data ... }

Parameters

list	Pointer to the list to iterate over.
node	Name of the list_node_t* variable to use in the loop body.

Definition at line 185 of file list.h.

Typedef Documentation

list_node_t

typedef struct list_node list_node_t

A node in a doubly-linked list. Each node contains a pointer to element data and bidirectional links.

Function Documentation

list_clear()

void list_clear

(

list_t *

list

)

Removes all elements from the list. Deallocates all nodes and their data, leaving the list empty.

Parameters

list	Pointer to the list to clear. Must not be NULL.

Definition at line 47 of file list.c.

References list_t::head, list_clear(), list_node::next, list_t::size, and list_t::tail.

Referenced by list_clear(), and list_free().

Here is the call graph for this function:

Here is the caller graph for this function:

list_free()

void list_free

(

list_t *

list

)

Frees all resources associated with a doubly-linked list. Deallocates all nodes and their data, then the list structure itself.

Parameters

list	Pointer to the list to free. Safe to pass NULL.

Definition at line 41 of file list.c.

References list_clear(), and list_free().

Referenced by list_free().

Here is the call graph for this function:

Here is the caller graph for this function:

list_get()

void * list_get	(	const list_t *	list,
		size_t	index
	)

Retrieves a pointer to the element at the specified index. Traverses the list to find the element at the given position.

Parameters

list	Pointer to the list. Must not be NULL.
index	Zero-based position of the element to retrieve. Must be < list size.

Returns

Pointer to the element data on success, NULL if index is out of bounds.

Note

Returned pointer is valid until the list is modified or freed. Operation is O(n).

Definition at line 115 of file list.c.

References list_node::data, list_t::head, list_get(), list_node::next, and list_t::size.

Referenced by list_get().

Here is the call graph for this function:

Here is the caller graph for this function:

list_index_of()

int list_index_of	(	const list_t *	list,
		void *	elem
	)

Finds the index of the first occurrence of an element in the list. Compares element addresses, not content (pointer equality).

Parameters

list	Pointer to the list. Must not be NULL.
elem	Pointer to the element data to find. Must not be NULL.

Returns

Zero-based index of the element if found, -1 otherwise.

Definition at line 122 of file list.c.

References list_node::data, list_t::elem_size, list_t::head, list_index_of(), and list_node::next.

Referenced by list_index_of(), list_insert_after(), list_insert_before(), and list_remove().

Here is the call graph for this function:

Here is the caller graph for this function:

list_insert()

void list_insert	(	list_t *	list,
		size_t	index,
		void *	elem
	)

Inserts an element at the specified index in the list. Creates a new node with a copy of the element data at position index. Existing elements at index and beyond are shifted right.

Parameters

list	Pointer to the list. Must not be NULL.
index	Zero-based position at which to insert. Must be <= list size.
elem	Pointer to the element data to insert. Must not be NULL.

Note

If index equals list size, appends to the end. Operation is O(n).

Definition at line 134 of file list.c.

References list_t::elem_size, list_t::head, list_insert(), list_push_back(), list_push_front(), list_node::next, list_node::prev, and list_t::size.

Referenced by list_insert(), list_insert_after(), and list_insert_before().

Here is the call graph for this function:

Here is the caller graph for this function:

list_insert_after()

void list_insert_after	(	list_t *	list,
		void *	elem,
		void *	after
	)

Inserts an element immediately after a specified element in the list. Creates a new node with a copy of elem and inserts it after the node containing after.

Parameters

list	Pointer to the list. Must not be NULL.
elem	Pointer to the element data to insert. Must not be NULL.
after	Pointer to the element data after which to insert. Must not be NULL.

Note

Does nothing if after is not found in the list.

Definition at line 181 of file list.c.

References list_index_of(), list_insert(), and list_insert_after().

Referenced by list_insert_after().

Here is the call graph for this function:

Here is the caller graph for this function:

list_insert_before()

void list_insert_before	(	list_t *	list,
		void *	elem,
		void *	before
	)

Inserts an element immediately before a specified element in the list. Creates a new node with a copy of elem and inserts it before the node containing before.

Parameters

list	Pointer to the list. Must not be NULL.
elem	Pointer to the element data to insert. Must not be NULL.
before	Pointer to the element data before which to insert. Must not be NULL.

Note

Does nothing if before is not found in the list.

Definition at line 187 of file list.c.

References list_index_of(), list_insert(), and list_insert_before().

Referenced by list_insert_before().

Here is the call graph for this function:

Here is the caller graph for this function:

list_new()

list_t * list_new

(

size_t

elem_size

)

Creates a new empty doubly-linked list.

Parameters

elem_size

Size in bytes of each element to be stored in the list.

Returns

Pointer to newly allocated list on success, NULL on allocation failure.

Note

Caller must free the list using list_free() when done.

Definition at line 32 of file list.c.

References list_t::elem_size, list_t::head, list_new(), list_t::size, and list_t::tail.

Referenced by list_new().

Here is the call graph for this function:

Here is the caller graph for this function:

list_pop_back()

void list_pop_back

(

list_t *

list

)

Removes the last element from the list. Deallocates the tail node and its data. Updates tail to the previous node.

Parameters

list	Pointer to the list. Must not be NULL.

Note

Does nothing if the list is empty.

Definition at line 76 of file list.c.

References list_t::head, list_pop_back(), list_node::next, list_node::prev, list_t::size, and list_t::tail.

Referenced by list_pop_back().

Here is the call graph for this function:

Here is the caller graph for this function:

list_pop_front()

void list_pop_front

(

list_t *

list

)

Removes the first element from the list. Deallocates the head node and its data. Updates head to the next node. Operation is O(1).

Parameters

list	Pointer to the list. Must not be NULL.

Note

Does nothing if the list is empty.

Definition at line 103 of file list.c.

References list_t::head, list_pop_front(), list_node::next, list_node::prev, list_t::size, and list_t::tail.

Referenced by list_pop_front().

Here is the call graph for this function:

Here is the caller graph for this function:

list_push_back()

void list_push_back	(	list_t *	list,
		void *	elem
	)

Appends an element to the back of the list. Creates a new node with a copy of the element data and makes it the new tail. Operation is O(1) due to tail pointer maintenance.

Parameters

list	Pointer to the list. Must not be NULL.
elem	Pointer to the element data to append. Must not be NULL.

Definition at line 61 of file list.c.

References list_t::elem_size, list_t::head, list_push_back(), list_node::next, list_node::prev, list_t::size, and list_t::tail.

Referenced by list_insert(), and list_push_back().

Here is the call graph for this function:

Here is the caller graph for this function:

list_push_front()

void list_push_front	(	list_t *	list,
		void *	elem
	)

Inserts an element at the front of the list. Creates a new node with a copy of the element data and makes it the new head. Operation is O(1).

Parameters

list	Pointer to the list. Must not be NULL.
elem	Pointer to the element data to insert. Must not be NULL.

Definition at line 88 of file list.c.

References list_t::elem_size, list_t::head, list_push_front(), list_node::next, list_node::prev, list_t::size, and list_t::tail.

Referenced by list_insert(), and list_push_front().

Here is the call graph for this function:

Here is the caller graph for this function:

list_remove()

void list_remove	(	list_t *	list,
		void *	elem
	)

Removes the first occurrence of an element from the list. Searches for the element by pointer equality and removes it. Deallocates the matching node and its data.

Parameters

list	Pointer to the list. Must not be NULL.
elem	Pointer to the element data to remove. Must not be NULL.

Note

Does nothing if the element is not found in the list.

Definition at line 159 of file list.c.

References list_t::head, list_index_of(), list_remove(), list_node::next, list_node::prev, list_t::size, and list_t::tail.

Referenced by list_remove().

Here is the call graph for this function:

Here is the caller graph for this function:

list_size()

size_t list_size

(

const list_t *

list

)

Returns the number of elements in the list.

Parameters

list	Pointer to the list. Must not be NULL.

Returns

Number of elements currently stored in the list.

Definition at line 59 of file list.c.

References list_size(), and list_t::size.

Referenced by list_size().

Here is the call graph for this function:

Here is the caller graph for this function: