src/list.h File Reference

A singly linked list implementation. More...

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#include "cdsa_types.h"

Include dependency graph for list.h:

Go to the source code of this file.

Typedefs

typedef struct List List

A typedef for the underlying List_ struct.

typedef struct ListNode ListNode

A typedef for the ListNode_ struct, which is the container for items stored in the list.

Functions

cdsa_status_t list_new (List **list, size_t size_elem, cdsa_destroy_func1_t destroy)

Create a new list, returning NULL if unable to for any reason.

cdsa_status_t list_destroy (List **list)

Destroy the given list, freeing its associated memory.

cdsa_status_t list_is_empty (List *list, bool *is_empty)

Answer if the given list is empty, recording result in the bool pointer iff list is valid.

cdsa_status_t list_size (List *list, size_t *size)

Answer the number of items in the given list, recording result in the size_t pointer variable.

cdsa_status_t list_head (List *list, ListNode **head)

Answer the first item of the given list, setting *head to the first item iff the list is non-empty.

cdsa_status_t list_tail (List *list, ListNode **tail)

Answer the last item of the given list, setting *tail to the last item iff the list is non-empty.

cdsa_status_t list_prepend (List *list, void *data, ListNode **new_node)

Prepend the given data to the list, placing it at the head of the list, and setting *new_node to the newly created node.

cdsa_status_t list_append (List *list, void *data, ListNode **new_node)

Append the given data to the list, placing it at the tail of the list, and setting *new_node to the new list element.

cdsa_status_t list_insert (List *list, ListNode *elem, void *data, ListNode **new_node)

Insert the data in the list after the given element of the list, setting *new_node to the newly created element.

cdsa_status_t list_remove (List *list, ListNode *elem)

Remove the given element from the list.

cdsa_status_t list_search (List *list, void *data, ListNode **node)

Search the list for a ListNode containing the given data, setting *node to the 1st node containing data iff there is such a node.

cdsa_status_t listelem_data (ListNode *elem, void *ptr)

Extract the data pointer from the given element, setting *ptr to the resultant pointer.

cdsa_status_t listelem_next (ListNode *elem, ListNode **next)

Extract the next list element from the given element, setting *next to the resultant node.

cdsa_status_t listelem_destroy (ListNode **elem)

Destroy the list node pointed to, release its associated memory, setting *elem to NULL afterwards.

Detailed Description

A singly linked list implementation.

This list implementation provides constant-time size, head, tail, prepend, and append operations, and a linear-time insert function for inserting anywhere within the list.

The client may optionally supply a destroy function that is applied to each data element when the list is destroyed.

Definition in file list.h.

Typedef Documentation

List

A typedef for the underlying List_ struct.

Functions are declared below for creating, destroying and manipulating a list.

Definition at line 42 of file list.h.

ListNode

A typedef for the ListNode_ struct, which is the container for items stored in the list.

Each node stores a pointer to some data and a pointer to the next node in the list.

Definition at line 54 of file list.h.

Function Documentation

cdsa_status_t list_new	(	List **	list,
		size_t	size_elem,
		cdsa_destroy_func1_t	destroy
	)

Create a new list, returning NULL if unable to for any reason.

Parameters:

	list	A pointer to a list pointer that will be set on success.
	size_elem	The size of each element in the list if elements should be copied into the list, or less than 1 if only pointers should be stored.
	destroy	If non-NULL, called once on every element of the list when the list_destroy function.

cdsa_status_t list_destroy ( List ** list )

Destroy the given list, freeing its associated memory.

Parameters:

list

A pointer to the list pointer to be destroyed. The list pointer will be set to NULL on success.

cdsa_status_t list_is_empty	(	List *	list,
		bool *	is_empty
	)

Answer if the given list is empty, recording result in the bool pointer iff list is valid.

Parameters:

	list	The list.
	is_empty	Pointer to boolean value to be set to true if list is empty, false if list has at least 1 element, and not set if list is not a non-NULL list.

cdsa_status_t list_size	(	List *	list,
		size_t *	size
	)

Answer the number of items in the given list, recording result in the size_t pointer variable.

This function operates in constant time.

Parameters:

	list	The list.
	size	A pointer to a size variable, which will be set if list is non-NULL.

cdsa_status_t list_head	(	List *	list,
		ListNode **	head
	)

Answer the first item of the given list, setting *head to the first item iff the list is non-empty.

Parameters:

	list	The list.
	head	A pointer to a ListNode pointer, which will be set iff list is non-empty.

Returns:: If list is non-empty, returns CDSA_SUCCESS; if list is empty, returns CDSA_EMPTY_ERR; other codes indicate other errors.

cdsa_status_t list_tail	(	List *	list,
		ListNode **	tail
	)

Answer the last item of the given list, setting *tail to the last item iff the list is non-empty.

Parameters:

	list	The list (or NULL, status_t *status).
	tail	A pointer to a ListNode pointer, which will be set iff list is non-empty.

Returns:: If list is non-empty, returns CDSA_SUCCESS; if list is empty, returns CDSA_EMPTY_ERR; other codes indicate other errors.

cdsa_status_t list_prepend	(	List *	list,
		void *	data,
		ListNode **	new_node
	)

Prepend the given data to the list, placing it at the head of the list, and setting *new_node to the newly created node.

This function operates in constant time.

Parameters:

	list	The list.
	data	A pointer to the data to be inserted at the beginning of the list.
	new_node	A pointer to a ListNode pointer, which will be set upon success to the node created for data.

cdsa_status_t list_append	(	List *	list,
		void *	data,
		ListNode **	new_node
	)

Append the given data to the list, placing it at the tail of the list, and setting *new_node to the new list element.

This function operates in constant time.

Parameters:

	list	The list.
	data	A pointer to the data to be inserted at the end of the list.
	new_node	A pointer to a ListNode pointer, which will be set upon success to the node created for data.

cdsa_status_t list_insert	(	List *	list,
		ListNode *	elem,
		void *	data,
		ListNode **	new_node
	)

Insert the data in the list after the given element of the list, setting *new_node to the newly created element.

This function operates in linear time (in the number of elements) since it traverses the list to be sure that the element is actually an element of the list.

Parameters:

	list	The list.
	elem	An element of the given list after which the data will be inserted.
	data	A pointer to the data to be inserted after the given elem.
	new_node	A pointer to a ListNode pointer, which will be set upon success to the node created for data.

Returns:: If list contains elem and insert is successful, returns CDSA_SUCCESS; if elem is not found in list, returns CDSA_NO_RESULT; other codes indicate an error.

cdsa_status_t list_remove	(	List *	list,
		ListNode *	elem
	)

Remove the given element from the list.

The client is responsible for calling free on the returned ListNode if it is not reused and reinserted again into a list.

Parameters:

	list	The list.
	elem	An element in the given list to be removed from the list.

Returns:: If list contains elem and it is removed, returns CDSA_SUCCESS; if elem is not found in list, returns CDSA_NO_RESULT; other codes indicate an error.

cdsa_status_t list_search	(	List *	list,
		void *	data,
		ListNode **	node
	)

Search the list for a ListNode containing the given data, setting *node to the 1st node containing data iff there is such a node.

Parameters:

	list	The list.
	data	The data to search for.
	node	A pointer to a ListNode pointer, which will be set to the 1st node in list containing data iff there is such a node.

Returns:: If list contains node with data, returns CDSA_SUCCESS; if no node in list has data, returns CDSA_NO_RESULT; other codes indicate an error.

cdsa_status_t listelem_data	(	ListNode *	elem,
		void *	ptr
	)

Extract the data pointer from the given element, setting *ptr to the resultant pointer.

Parameters:

	elem	A non-NULL element.
	ptr	A pointer to a pointer, which will be set to pointer of data. E.g., if we were storing int pointers, the actual type of ptr would "int **".

cdsa_status_t listelem_next	(	ListNode *	elem,
		ListNode **	next
	)

Extract the next list element from the given element, setting *next to the resultant node.

Parameters:

	elem	A non-NULL element.
	next	A pointer to a ListNode pointer, which will be set to the next ListNode from the given elem if there is a next, or to NULL if there is no next node.

cdsa_status_t listelem_destroy ( ListNode ** elem )

Destroy the list node pointed to, release its associated memory, setting *elem to NULL afterwards.

This must only be called on a ListNode that does not belong to a List (i.e., has been removed from a List and not added to another List). Nodes in a list can be destroyed by destroying the list itself.

Parameters:

elem

A pointer to a ListNode pointer to be destroyed.


Typedefs
typedef struct List	List
	A typedef for the underlying List_ struct.
typedef struct ListNode	ListNode
	A typedef for the ListNode_ struct, which is the container for items stored in the list.
Functions
cdsa_status_t	list_new (List **list, size_t size_elem, cdsa_destroy_func1_t destroy)
	Create a new list, returning NULL if unable to for any reason.
cdsa_status_t	list_destroy (List **list)
	Destroy the given list, freeing its associated memory.
cdsa_status_t	list_is_empty (List list, bool is_empty)
	Answer if the given list is empty, recording result in the bool pointer iff list is valid.
cdsa_status_t	list_size (List list, size_t size)
	Answer the number of items in the given list, recording result in the size_t pointer variable.
cdsa_status_t	list_head (List list, ListNode *head)
	Answer the first item of the given list, setting *head to the first item iff the list is non-empty.
cdsa_status_t	list_tail (List list, ListNode *tail)
	Answer the last item of the given list, setting *tail to the last item iff the list is non-empty.
cdsa_status_t	list_prepend (List list, void data, ListNode **new_node)
	Prepend the given data to the list, placing it at the head of the list, and setting *new_node to the newly created node.
cdsa_status_t	list_append (List list, void data, ListNode **new_node)
	Append the given data to the list, placing it at the tail of the list, and setting *new_node to the new list element.
cdsa_status_t	list_insert (List list, ListNode elem, void data, ListNode *new_node)
	Insert the data in the list after the given element of the list, setting *new_node to the newly created element.
cdsa_status_t	list_remove (List list, ListNode elem)
	Remove the given element from the list.
cdsa_status_t	list_search (List list, void data, ListNode **node)
	Search the list for a ListNode containing the given data, setting *node to the 1st node containing data iff there is such a node.
cdsa_status_t	listelem_data (ListNode elem, void ptr)
	Extract the data pointer from the given element, setting *ptr to the resultant pointer.
cdsa_status_t	listelem_next (ListNode elem, ListNode *next)
	Extract the next list element from the given element, setting *next to the resultant node.
cdsa_status_t	listelem_destroy (ListNode **elem)
	Destroy the list node pointed to, release its associated memory, setting *elem to NULL afterwards.