linked_list.h
Go to the documentation of this file.
1 /*
2 ** Copyright 2014-2016 The Earlham Institute
3 **
4 ** Licensed under the Apache License, Version 2.0 (the "License");
5 ** you may not use this file except in compliance with the License.
6 ** You may obtain a copy of the License at
7 **
8 ** http://www.apache.org/licenses/LICENSE-2.0
9 **
10 ** Unless required by applicable law or agreed to in writing, software
11 ** distributed under the License is distributed on an "AS IS" BASIS,
12 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 ** See the License for the specific language governing permissions and
14 ** limitations under the License.
15 */
16 
26 #ifndef LINKED_LIST_H
27 #define LINKED_LIST_H
28 
29 #include "typedefs.h"
31 
32 
33 
34 /******** FORWARD DECLARATION ******/
35 typedef struct ListItem ListItem;
36 
43 struct ListItem
44 {
47 };
48 
49 
56 typedef struct LinkedList
57 {
60 
63 
65  uint32 ll_size;
66 
68  void (*ll_free_node_fn_p) (ListItem * node_p);
69 
70 } LinkedList;
71 
72 #ifdef __cplusplus
73 extern "C"
74 {
75 #endif
76 
87 GRASSROOTS_UTIL_API LinkedList *AllocateLinkedList (void (*free_node_fn_p) (ListItem * const node_p));
88 
89 
99 GRASSROOTS_UTIL_API void FreeLinkedList (LinkedList * const list_p);
100 
101 
108 GRASSROOTS_UTIL_API void InitLinkedList (LinkedList * const list_p);
109 
110 
118 GRASSROOTS_UTIL_API void LinkedListAddHead (LinkedList * const list_p, ListItem * const node_p);
119 
120 
128 GRASSROOTS_UTIL_API void LinkedListAddTail (LinkedList * const list_p, ListItem * const node_p);
129 
130 
138 GRASSROOTS_UTIL_API ListItem *LinkedListRemHead (LinkedList * const list_p);
139 
140 
148 GRASSROOTS_UTIL_API ListItem *LinkedListRemTail (LinkedList * const list_p);
149 
150 
158 GRASSROOTS_UTIL_API void LinkedListRemove (LinkedList * const list_p, ListItem * const node_p);
159 
160 
172 GRASSROOTS_UTIL_API bool LinkedListSort (LinkedList * const list_p, int (*compare_nodes_fn) (const void *v1_p, const void *v2_p));
173 
174 
182 GRASSROOTS_UTIL_API void SetLinkedListFreeNodeFunction (LinkedList * const list_p, void (*free_node_fn) (ListItem * const node_p));
183 
184 
194 GRASSROOTS_UTIL_API void LinkedListPrioritisedInsert (LinkedList * const list_p, ListItem * const node_p, int (*compare_nodes_fn) (const void *v1_p, const void *v2_p));
195 
196 
206 GRASSROOTS_UTIL_API void LinkedListInsert (LinkedList * const list_p, ListItem * const prev_node_p, ListItem * const node_to_insert_p);
207 
208 
221 GRASSROOTS_UTIL_API ListItem *LinkedListBinarySearch (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);
222 
223 
234 GRASSROOTS_UTIL_API void MoveListContents (LinkedList * const src_list_p, LinkedList * const dest_list_p);
235 
236 
247 GRASSROOTS_UTIL_API LinkedList *SplitList (LinkedList * const list_p, const uint32 split_list_head_index);
248 
249 
256 GRASSROOTS_UTIL_API void ClearLinkedList (LinkedList * const list_p);
257 
258 
265 GRASSROOTS_UTIL_API void InitListItem (ListItem * const item_p);
266 
267 
268 
269 #ifdef __cplusplus
270 }
271 #endif
272 
273 #endif /* LINKED_LIST_H */
274 
275 
A doubly-linked node that points to its predecessor and successor.
Definition: linked_list.h:43
void LinkedListRemove(LinkedList *const list_p, ListItem *const node_p)
Remove a ListItem from a LinkedList.
ListItem * ll_tail_p
A pointer to the last ListItem on this list.
Definition: linked_list.h:62
ListItem * ln_prev_p
A pointer to the previous ListItem.
Definition: linked_list.h:45
void MoveListContents(LinkedList *const src_list_p, LinkedList *const dest_list_p)
Move the contents of one list to another.
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.
bool LinkedListSort(LinkedList *const list_p, int(*compare_nodes_fn)(const void *v1_p, const void *v2_p))
Sort a LinkedList.
uint32 ll_size
The number of ListItems on this list.
Definition: linked_list.h:65
void(* ll_free_node_fn_p)(ListItem *node_p)
Callback function to use when freeing a ListItem.
Definition: linked_list.h:68
ListItem * ln_next_p
A pointer to the next ListItem.
Definition: linked_list.h:46
void ClearLinkedList(LinkedList *const list_p)
Empty a LinkedList by freeing all of its ListItems.
ListItem * LinkedListBinarySearch(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.
LinkedList * SplitList(LinkedList *const list_p, const uint32 split_list_head_index)
Cut a list into two lists at the given index.
A doubly-linked list that can be traversed in either direction.
Definition: linked_list.h:56
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 l...
void InitListItem(ListItem *const item_p)
Initialise a ListItem.
void LinkedListAddHead(LinkedList *const list_p, ListItem *const node_p)
Add a ListItem to the start of a LinkedList.
void LinkedListAddTail(LinkedList *const list_p, ListItem *const node_p)
Add a ListItem to the end of a LinkedList.
LinkedList * AllocateLinkedList(void(*free_node_fn_p)(ListItem *const node_p))
Create a new LinkedList.
void InitLinkedList(LinkedList *const list_p)
Initialise/clear a LinkedList to be empty.
void FreeLinkedList(LinkedList *const list_p)
Free a LinkedList.
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.
ListItem * LinkedListRemTail(LinkedList *const list_p)
Remove the last ListItem from a LinkedList.
ListItem * ll_head_p
A pointer to the first ListItem on this list.
Definition: linked_list.h:59
ListItem * LinkedListRemHead(LinkedList *const list_p)
Remove the first ListItem from a LinkedList.