---

ds_list.h File Reference

#include "ds_common.h"

Go to the source code of this file.

Data Structures
struct	List
struct	ListWorkspace
struct	Node
Defines
#define	ListPopBack(pList)   ListRemove(pList, pList->pTail)
#define	ListPopFront(pList)   ListRemove(pList, pList->pHead)
Functions
List *	ListCreate (int iWSSize)
void	ListDestroy (List *pList)
Node *	ListPushFront (List *pList, void *pData)
Node *	ListPushBack (List *pList, void *pData)
Node *	ListInsertBefore (List *pList, Node *pNode, void *pData)
Node *	ListInsertAfter (List *pList, Node *pNode, void *pData)
Node *	ListFind (Node *pStart, void *pData, bool bDirection)
void	ListRemove (List *pList, Node *pNode)
Variables
Node	Node
ListWorkspace	ListWorkspace
List	List

---

Define Documentation

#define ListPopBack (  pList   )     ListRemove(pList, pList->pTail)

Remove the last Node from the list. Parameters: pList   List to remove the last Node from.

#define ListPopFront (  pList   )     ListRemove(pList, pList->pHead)

Remove the first Node from the list. Parameters: pList   List to remove the first Node from.

---

Function Documentation

List* ListCreate (  int   iWSSize )

Create a new linked list. Parameters: iWSSize   Size of workspace to allocate for this list. Returns: A pointer to the newly created list if successful, otherwise NULL. Remarks: A workspace of size iWSSize elements will be allocated, from which nodes will be used. If the list size grows beyond this, nodes will be allocated from memory as needed. When nodes are removed, new additions will be allocated from the free positions in the workspace. void pointers are used as the list data, so any type where sizeof(type) <= sizeof(void*) can be directly inserted into the data, avoiding the need to dereference a pointer. Any larger type must be allocated separately, and a pointer to it placed into the list. Note: If a pointer to a separately allocated item of data is placed into the list then it must be deallocated before the list is destroyed. See also: ListDestroy for information on separately allocated data items.

void ListDestroy (  List *   pList )

Destroy a list. Parameters: pList   List to destroy. Remarks: If pList contains any elements, they are iterated through and destroyed. The workspace and list structure memory are then freed. Note: If any larger data items have been allocated and their pointers placed in the list, they must be deallocated before calling ListDestroy, otherwise a memory leak will occur. However, if their pointers have been saved elsewhere then this is not required.

Node* ListFind (  Node *   pStart, void *   pData, bool   bDirection )

Find a node in a list. Parameters: pStart   Node to start the search from. pData   Data to search for. bDirection   Direction to search in: true is forwards, false is backwards. Returns: The first node found, or NULL if pData was not found. Remarks: Starting at pStart this function iterates through the list in the direction specified by bDirection comparing all the nodes against pData. If it is found, then the node containing the first occurrence of pData is returned. If pData is not found before the list terminates, NULL is returned. Note: There may be more occurrences of pData in the list, so if a node is returned it is best to continue calling ListFind as shown below. If NULL is passed, NULL will be returned to enable use of the function in this way.   Node *pNode = pList->pHead; while(pNode = ListFind(pNode, pDataToFind, true)) { printf("Found %d at %d\n", pDataToFind, pNode); pNode = pNode->pNext; }

Node* ListInsertAfter (  List *   pList, Node *   pNode, void *   pData )

Insert a node into the list. Parameters: pList   List to insert pData to. pNode   Node to insert pData after. pData   Data to append to pList. Returns: The newly inserted node if successful, otherwise NULL. Remarks: Behaviour is undefined if pList is NULL, or if any internal data structures have been changed outside of the list management functions. See also: ListCreate for information on type sizes and storing data.

Node* ListInsertBefore (  List *   pList, Node *   pNode, void *   pData )

Insert a node into the list. Parameters: pList   List to insert pData to. pNode   Node to insert pData before. pData   Data to append to pList. Returns: The newly inserted node if successful, otherwise NULL. Remarks: Behaviour is undefined if pList is NULL, or if any internal data structures have been changed outside of the list management functions. See also: ListCreate for information on type sizes and storing data.

Node* ListPushBack (  List *   pList, void *   pData )

Append a node to the list. Parameters: pList   List to append pData to. pData   Data to append to pList. Returns: The newly inserted node if successful, otherwise NULL. Remarks: Behaviour is undefined if pList is NULL, or if any internal data structures have been changed outside of the list management functions. See also: ListCreate for information on type sizes and storing data.

Node* ListPushFront (  List *   pList, void *   pData )

Prepend a node to the list. Parameters: pList   List to prepend pData to. pData   Data to prepend to pList. Returns: The newly inserted node if successful, otherwise NULL. Remarks: Behaviour is undefined if pList is NULL, or if any internal data structures have been changed outside of the list management functions. See also: ListCreate for information on type sizes and storing data.

void ListRemove (  List *   pList, Node *   pNode )

Remove a node from the list. Parameters: pList   List to remove pNode from. pNode   Node to remove from pList. Remarks: This function removes a node from the specified list. If the node is in the middle of the list, the two outer nodes are linked together, otherwise the node is removed and the respective end node has its trailing pointer set to NULL.

---

Variable Documentation

struct List List

Linked list.

struct ListWorkspace ListWorkspace

List allocation workspace.

struct Node Node

Node in a linked list.

---