slist.h File Reference

Singly linked list implementation for efficient insertions and deletions. More...

#include <stddef.h>
#include <stdlib.h>

Include dependency graph for slist.h:

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

Go to the source code of this file.

Classes
struct	slist_node
struct	slist

Macros
#define	SLIST_FOR_EACH(list, node)   for (slist_node_t * (node) = (list)->head; (node); (node) = (node)->next)

Typedefs
typedef struct slist_node	slist_node_t

Functions
slist *	slist_new (size_t elem_size)
void	slist_free (slist *list)
size_t	slist_size (const slist *list)
void	slist_clear (slist *list)
slist_node_t *	slist_node_new (size_t elem_size, void *data)
void	slist_node_free (slist_node_t *node)
void	slist_push_front (slist *list, void *elem)
void	slist_push_back (slist *list, void *elem)
void	slist_pop_front (slist *list)
void	slist_insert (slist *list, size_t index, void *elem)
void	slist_remove (slist *list, size_t index)
void *	slist_get (const slist *list, size_t index)
int	slist_index_of (const slist *list, void *elem)
void	slist_insert_after (slist *list, void *elem, void *after)
void	slist_insert_before (slist *list, void *elem, void *before)
void	slist_print_asint (const slist *list)
void	slist_print_aschar (const slist *list)

Detailed Description

Singly linked list implementation for efficient insertions and deletions.

Definition in file slist.h.

Macro Definition Documentation

SLIST_FOR_EACH

#define SLIST_FOR_EACH	(		list,
			node
	)		for (slist_node_t * (node) = (list)->head; (node); (node) = (node)->next)

Iteration macro for traversing all nodes in a list. Usage: SLIST_FOR_EACH(my_list, node) { ... use node->data ... }

Parameters

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

Definition at line 192 of file slist.h.

Typedef Documentation

slist_node_t

typedef struct slist_node slist_node_t

A node in a singly-linked list. Each node contains a pointer to element data and a pointer to the next node.

Function Documentation

slist_clear()

void slist_clear

(

slist *

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 33 of file slist.c.

References slist::head, slist_node::next, slist::size, slist_clear(), slist_node_free(), and slist::tail.

Referenced by slist_clear(), and slist_free().

Here is the call graph for this function:

Here is the caller graph for this function:

slist_free()

void slist_free

(

slist *

list

)

Frees all resources associated with a singly-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 25 of file slist.c.

References slist_clear(), and slist_free().

Referenced by slist_free().

Here is the call graph for this function:

Here is the caller graph for this function:

slist_get()

void * slist_get	(	const slist *	list,
		size_t	index
	)

Retrieves a pointer to the element at the specified index.

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.

Definition at line 140 of file slist.c.

References slist_node::data, slist::head, slist_node::next, slist::size, and slist_get().

Referenced by slist_get().

Here is the call graph for this function:

Here is the caller graph for this function:

slist_index_of()

int slist_index_of	(	const slist *	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 150 of file slist.c.

References slist_node::data, slist::elem_size, slist::head, slist_node::next, and slist_index_of().

Referenced by slist_index_of(), slist_insert_after(), and slist_insert_before().

Here is the call graph for this function:

Here is the caller graph for this function:

slist_insert()

void slist_insert	(	slist *	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.

Definition at line 95 of file slist.c.

References slist::elem_size, slist::head, slist_node::next, slist::size, slist_insert(), slist_node_new(), slist_push_back(), and slist_push_front().

Referenced by slist_insert(), slist_insert_after(), and slist_insert_before().

Here is the call graph for this function:

Here is the caller graph for this function:

slist_insert_after()

void slist_insert_after	(	slist *	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 163 of file slist.c.

References slist_index_of(), slist_insert(), and slist_insert_after().

Referenced by slist_insert_after().

Here is the call graph for this function:

Here is the caller graph for this function:

slist_insert_before()

void slist_insert_before	(	slist *	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 168 of file slist.c.

References slist_index_of(), slist_insert(), slist_insert_before(), and slist_push_front().

Referenced by slist_insert_before().

Here is the call graph for this function:

Here is the caller graph for this function:

slist_new()

slist * slist_new

(

size_t

elem_size

)

Creates a new empty singly-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 slist_free() when done.

Definition at line 14 of file slist.c.

References slist::elem_size, slist::head, slist::size, slist_new(), and slist::tail.

Referenced by slist_new().

Here is the call graph for this function:

Here is the caller graph for this function:

slist_node_free()

void slist_node_free

(

slist_node_t *

node

)

Frees a single list node and its associated data.

Parameters

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

Definition at line 57 of file slist.c.

References slist_node_free().

Referenced by slist_clear(), slist_node_free(), slist_pop_front(), and slist_remove().

Here is the call graph for this function:

Here is the caller graph for this function:

slist_node_new()

slist_node_t * slist_node_new	(	size_t	elem_size,
		void *	data
	)

Creates a new list node with a copy of the provided data.

Parameters

elem_size	Size in bytes of the element data.
data	Pointer to the element data to copy into the node. Must not be NULL.

Returns

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

Note

Internal helper function. Caller is responsible for freeing returned node.

Definition at line 46 of file slist.c.

References slist_node::data, slist_node::next, and slist_node_new().

Referenced by slist_insert(), slist_node_new(), slist_push_back(), and slist_push_front().

Here is the call graph for this function:

Here is the caller graph for this function:

slist_pop_front()

void slist_pop_front

(

slist *

list

)

Removes the first element from the list. Deallocates the head node and its data. Updates head to the next node.

Parameters

list	Pointer to the list. Must not be NULL.

Note

Does nothing if the list is empty.

Definition at line 86 of file slist.c.

References slist::head, slist_node::next, slist::size, slist_node_free(), slist_pop_front(), and slist::tail.

Referenced by slist_pop_front(), and slist_remove().

Here is the call graph for this function:

Here is the caller graph for this function:

slist_print_aschar()

void slist_print_aschar

(

const slist *

list

)

Prints all elements in the list as characters. Assumes each element is stored as a char. Prints to stdout.

Parameters

list	Pointer to the list. Must not be NULL.

Note

Debug utility function. Elements must be of type char.

Definition at line 181 of file slist.c.

References SLIST_FOR_EACH, and slist_print_aschar().

Referenced by slist_print_aschar().

Here is the call graph for this function:

Here is the caller graph for this function:

slist_print_asint()

void slist_print_asint

(

const slist *

list

)

Prints all elements in the list as integers. Assumes each element is stored as an int. Prints to stdout.

Parameters

list	Pointer to the list. Must not be NULL.

Note

Debug utility function. Elements must be of type int.

Definition at line 176 of file slist.c.

References SLIST_FOR_EACH, and slist_print_asint().

Referenced by slist_print_asint().

Here is the call graph for this function:

Here is the caller graph for this function:

slist_push_back()

void slist_push_back	(	slist *	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 72 of file slist.c.

References slist::elem_size, slist::head, slist_node::next, slist::size, slist_node_new(), slist_push_back(), and slist::tail.

Referenced by slist_insert(), and slist_push_back().

Here is the call graph for this function:

Here is the caller graph for this function:

slist_push_front()

void slist_push_front	(	slist *	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.

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 61 of file slist.c.

References slist::elem_size, slist::head, slist_node::next, slist::size, slist_node_new(), slist_push_front(), and slist::tail.

Referenced by slist_insert(), slist_insert_before(), and slist_push_front().

Here is the call graph for this function:

Here is the caller graph for this function:

slist_remove()

void slist_remove	(	slist *	list,
		size_t	index
	)

Removes the element at the specified index from the list. Deallocates the node at position index and its data.

Parameters

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

Note

Does nothing if index is out of bounds.

Definition at line 120 of file slist.c.

References slist::head, slist_node::next, slist::size, slist_node_free(), slist_pop_front(), slist_remove(), and slist::tail.

Referenced by slist_remove().

Here is the call graph for this function:

Here is the caller graph for this function:

slist_size()

size_t slist_size

(

const slist *

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 31 of file slist.c.

References slist::size, and slist_size().

Referenced by slist_size().

Here is the call graph for this function:

Here is the caller graph for this function: