LinkedList Struct Reference

A doubly-linked list that can be traversed in either direction. More...

#include <linked_list.h>

Collaboration diagram for LinkedList:
[legend]

Public Member Functions

LinkedListAllocateLinkedList (void(*free_node_fn_p)(ListItem *const node_p))
 Create a new LinkedList. More...
 
void FreeLinkedList (LinkedList *const list_p)
 Free a LinkedList. More...
 
void InitLinkedList (LinkedList *const list_p)
 Initialise/clear a LinkedList to be empty. More...
 
void LinkedListAddHead (LinkedList *const list_p, ListItem *const node_p)
 Add a ListItem to the start of a LinkedList. More...
 
void LinkedListAddTail (LinkedList *const list_p, ListItem *const node_p)
 Add a ListItem to the end of a LinkedList. More...
 
ListItemLinkedListRemHead (LinkedList *const list_p)
 Remove the first ListItem from a LinkedList. More...
 
ListItemLinkedListRemTail (LinkedList *const list_p)
 Remove the last ListItem from a LinkedList. More...
 
void LinkedListRemove (LinkedList *const list_p, ListItem *const node_p)
 Remove a ListItem from a LinkedList. More...
 
bool LinkedListSort (LinkedList *const list_p, int(*compare_nodes_fn)(const void *v1_p, const void *v2_p))
 Sort a LinkedList. More...
 
void SetLinkedListFreeNodeFunction (LinkedList *const list_p, void(*free_node_fn)(ListItem *const node_p))
 Set the function used to free ListsNodes when the LinkedList is freed. More...
 
void LinkedListPrioritisedInsert (LinkedList *const list_p, ListItem *const node_p, int(*compare_nodes_fn)(const void *v1_p, const void *v2_p))
 Insert a node into a list using the given sorting algorithm to determine the node's position on the list. More...
 
void LinkedListInsert (LinkedList *const list_p, ListItem *const prev_node_p, ListItem *const node_to_insert_p)
 Insert a node into a list after a given node. More...
 
ListItemLinkedListBinarySearch (const LinkedList *const list_p, const ListItem *const node_p, int(*compare_nodes_fn)(const void *v1_p, const void *v2_p), int *const index_p)
 Search a sorted list using the given sorting algorithm for a given node. More...
 
void MoveListContents (LinkedList *const src_list_p, LinkedList *const dest_list_p)
 Move the contents of one list to another. More...
 
LinkedListSplitList (LinkedList *const list_p, const uint32 split_list_head_index)
 Cut a list into two lists at the given index. More...
 
void ClearLinkedList (LinkedList *const list_p)
 Empty a LinkedList by freeing all of its ListItems. More...
 
void InitListItem (ListItem *const item_p)
 Initialise a ListItem. More...
 

Data Fields

ListItemll_head_p
 A pointer to the first ListItem on this list. More...
 
ListItemll_tail_p
 A pointer to the last ListItem on this list. More...
 
uint32 ll_size
 The number of ListItems on this list. More...
 
void(* ll_free_node_fn_p )(ListItem *node_p)
 Callback function to use when freeing a ListItem. More...
 

Detailed Description

A doubly-linked list that can be traversed in either direction.

Member Function Documentation

◆ AllocateLinkedList()

LinkedList * AllocateLinkedList ( void(*)(ListItem *const node_p)  free_node_fn_p)

Create a new LinkedList.

The new LinkedList is initialised as an empty list.

Parameters
free_node_fn_pThe callback function to use when freeing ListItems. If this isn't set the default is to call free ().
Returns
The new LinkedList or NULL upon error.

◆ FreeLinkedList()

void FreeLinkedList ( LinkedList *const  list_p)

Free a LinkedList.

Each node is passed to the list's ll_free_node_fn_p or stdlib's free if ll_free_node_fn_p is NULL to be freed. Then the LinkedList is also freed

Parameters
list_pThe LinkedList to free.

◆ InitLinkedList()

void InitLinkedList ( LinkedList *const  list_p)

Initialise/clear a LinkedList to be empty.

Parameters
list_pThe LinkedList to initialise.

◆ LinkedListAddHead()

void LinkedListAddHead ( LinkedList *const  list_p,
ListItem *const  node_p 
)

Add a ListItem to the start of a LinkedList.

Parameters
list_pThe LinkedList to add the ListItem to.
node_pThe ListItem to add.

◆ LinkedListAddTail()

void LinkedListAddTail ( LinkedList *const  list_p,
ListItem *const  node_p 
)

Add a ListItem to the end of a LinkedList.

Parameters
list_pThe LinkedList to add the ListItem to.
node_pThe ListItem to add.

◆ LinkedListRemHead()

ListItem * LinkedListRemHead ( LinkedList *const  list_p)

Remove the first ListItem from a LinkedList.

Parameters
list_pThe LinkedList to remove the first ListItem from.
Returns
The removed ListItem or NULL if the LinkedList is empty.

◆ LinkedListRemTail()

ListItem * LinkedListRemTail ( LinkedList *const  list_p)

Remove the last ListItem from a LinkedList.

Parameters
list_pThe LinkedList to remove the last ListItem from.
Returns
The removed ListItem or NULL if the LinkedList is empty.

◆ LinkedListRemove()

void LinkedListRemove ( LinkedList *const  list_p,
ListItem *const  node_p 
)

Remove a ListItem from a LinkedList.

Parameters
list_pThe LinkedList to remove the ListItem from.
node_pThe ListItem to be removed.

◆ LinkedListSort()

bool LinkedListSort ( LinkedList *const  list_p,
int(*)(const void *v1_p, const void *v2_p)  compare_nodes_fn 
)

Sort a LinkedList.

Parameters
list_pThe LinkedList to sort.
compare_nodes_fnFunction used to sort the ListItems.
Returns
It returns < 0 if node1_p should be before node2_p, It returns > 0 if node1_p should be after node2_p, It returns 0 if node1_p is equal to node2_p.

◆ SetLinkedListFreeNodeFunction()

void SetLinkedListFreeNodeFunction ( LinkedList *const  list_p,
void(*)(ListItem *const node_p)  free_node_fn 
)

Set the function used to free ListsNodes when the LinkedList is freed.

Parameters
list_pThe LinkedList to set the function for.
free_node_fnThe function that will be used to free the ListItems.

◆ LinkedListPrioritisedInsert()

void LinkedListPrioritisedInsert ( LinkedList *const  list_p,
ListItem *const  node_p,
int(*)(const void *v1_p, const void *v2_p)  compare_nodes_fn 
)

Insert a node into a list using the given sorting algorithm to determine the node's position on the list.

Parameters
list_pThe LinkedList to insert the node on.
node_pThe ListItem to insert into the list.
compare_nodes_fnFunction used to compare the ListItems.

◆ LinkedListInsert()

void LinkedListInsert ( LinkedList *const  list_p,
ListItem *const  prev_node_p,
ListItem *const  node_to_insert_p 
)

Insert a node into a list after a given node.

Parameters
list_pThe LinkedList to insert the node on.
prev_node_pThe ListItem to insert our new node directly after. If this NULL, then our node will be inserted at the start of the list.
node_to_insert_pThe ListItem to insert on the list.

◆ LinkedListBinarySearch()

ListItem * LinkedListBinarySearch ( const LinkedList *const  list_p,
const ListItem *const  node_p,
int(*)(const void *v1_p, const void *v2_p)  compare_nodes_fn,
int *const  index_p 
)

Search a sorted list using the given sorting algorithm for a given node.

Parameters
list_pThe LinkedList to search.
node_pThe ListItem to search for.
compare_nodes_fnFunction used to compare the ListItems.
index_pAddress where the index of the matching item will be stored if it is found.
Returns
The matching ListItem or NULL if it could not be found on the LinkedList.

◆ MoveListContents()

void MoveListContents ( LinkedList *const  src_list_p,
LinkedList *const  dest_list_p 
)

Move the contents of one list to another.

This function is the equivalent of a "cut and paste" of all of the nodes from one list to another. The nodes are appended to the end of the destination list in the same order in which they appeared in the source list which is then left empty.

Parameters
src_list_pThe LinkedList to remove all of the nodes from.
dest_list_pThe LinkedList to which the nodes will be appended.

◆ SplitList()

LinkedList * SplitList ( LinkedList *const  list_p,
const uint32  split_list_head_index 
)

Cut a list into two lists at the given index.

Parameters
list_pThe LinkedList to split.
split_list_head_indexThe index of the ListItem that will be the first ListItem on the newly created list, i.e. its ll_head_p.
Returns
The newly created list or NULL if there was an error or if split_list_head_index was not less than the length of list_p.

◆ ClearLinkedList()

void ClearLinkedList ( LinkedList *const  list_p)

Empty a LinkedList by freeing all of its ListItems.

Parameters
list_pThe LinkedList to empty.

◆ InitListItem()

void InitListItem ( ListItem *const  item_p)

Initialise a ListItem.

Parameters
list_pThe ListItem to initialise.

Field Documentation

◆ ll_head_p

ListItem* ll_head_p

A pointer to the first ListItem on this list.

◆ ll_tail_p

ListItem* ll_tail_p

A pointer to the last ListItem on this list.

◆ ll_size

uint32 ll_size

The number of ListItems on this list.

◆ ll_free_node_fn_p

void(* ll_free_node_fn_p) (ListItem *node_p)

Callback function to use when freeing a ListItem.


The documentation for this struct was generated from the following file: