px-fwlib 0.10.0
Cross-platform embedded library and documentation for 8/16/32-bit microcontrollers generated with Doxygen 1.9.2
px_link_list.h
1#ifndef __PX_LINK_LIST_H__
2#define __PX_LINK_LIST_H__
3/* =============================================================================
4 ____ ___ ____ ___ _ _ ___ __ __ ___ __ __ TM
5 | _ \ |_ _| / ___| / _ \ | \ | | / _ \ | \/ | |_ _| \ \/ /
6 | |_) | | | | | | | | | | \| | | | | | | |\/| | | | \ /
7 | __/ | | | |___ | |_| | | |\ | | |_| | | | | | | | / \
8 |_| |___| \____| \___/ |_| \_| \___/ |_| |_| |___| /_/\_\
9
10 Copyright (c) 2008 Pieter Conradie <https://piconomix.com>
11
12 License: MIT
13 https://github.com/piconomix/px-fwlib/blob/master/LICENSE.md
14
15 Title: px_link_list.h : Linked List
16 Author(s): Pieter Conradie
17 Creation Date: 2008-11-27
18
19============================================================================= */
20
21/**
22 * @ingroup UTILS
23 * @defgroup PX_LINK_LIST px_link_list.h : Linked List
24 *
25 * A double (forward and backward) linked list using pointers.
26 *
27 * File(s):
28 * - utils/inc/px_link_list.h
29 * - utils/src/px_link_list.c
30 *
31 * @see http://en.wikipedia.org/wiki/Linked_list
32 *
33 * Example:
34 *
35 * @code
36 * No items in list:
37 *
38 * [first = NULL] [last = NULL]
39 *
40 * One item in list:
41 *
42 * [first] -> [prev = NULL][next = NULL] <- [last]
43 *
44 * Two items in list:
45 *
46 * [first] -> [prev = NULL][next] <-> [prev][next = NULL] <- [last]
47 *
48 * Three items in list:
49 *
50 * [first] -> [prev = NULL][next] <-> [prev][next] <-> [prev][next = NULL] <- [last]
51 * @endcode
52 *
53 * @{
54 */
55
56/* _____STANDARD INCLUDES____________________________________________________ */
57#include <stddef.h>
58
59/* _____PROJECT INCLUDES_____________________________________________________ */
60#include "px_defs.h"
61
62#ifdef __cplusplus
63extern "C" {
64#endif
65/* _____DEFINITIONS__________________________________________________________ */
66
67/* _____TYPE DEFINITIONS_____________________________________________________ */
68/// Link structure that must be at the head of each item in the list
69typedef struct px_link_list_item_s
70{
71 struct px_link_list_item_s * next; ///< Pointer to next item in the list
72 struct px_link_list_item_s * prev; ///< Pointer to previous item in the list
73} px_link_list_item_t;
74
75/// Linked list structure
76typedef struct
77{
78 struct px_link_list_item_s * first; ///< Pointer to first item in the list
79 struct px_link_list_item_s * last; ///< Pointer to last item in the list
80 size_t item_count; ///< Number of items in the list
81 size_t items_max; ///< Maximum number of items allowed in list; 0 means no limit
82} px_link_list_t;
83
84/* _____GLOBAL VARIABLES_____________________________________________________ */
85
86/* _____GLOBAL FUNCTION DECLARATIONS_________________________________________ */
87/**
88 * Initialises a linked list structure
89 *
90 * @param list Pointer to the linked list
91 * @param max_nr_of_items Maximum number of items allowed in list; 0 means no limit
92 */
93void px_link_list_init(px_link_list_t * list,
94 size_t max_nr_of_items);
95
96/**
97 * Initialises a list item.
98 *
99 * Initialises the item structure to indicate that it is not in the list.
100 * @sa px_link_list_item_in_list()
101 *
102 * @param list Pointer to the linked list
103 * @param item Pointer to specified item
104 */
105void px_link_list_item_init(px_link_list_t * list,
106 px_link_list_item_t * item);
107
108/**
109 * See if the list is empty
110 *
111 * @param list Pointer to the linked list
112 *
113 * @return true List is empty
114 * @return false List contains one or more items
115 */
116bool px_link_list_is_empty(px_link_list_t * list);
117
118/**
119 * See if the list is full
120 *
121 * @param list Pointer to the linked list
122 *
123 * @retval true The list is full
124 * @retval false The list is not full, or there is no limit (max_nr_of_items = 0)
125 */
126bool px_link_list_is_full(px_link_list_t * list);
127
128/**
129 * Get the number of items in the list
130 *
131 * @param list Pointer to the linked list
132 *
133 * @returns size_t The number of items in the list
134 */
135size_t px_link_list_get_item_count(px_link_list_t * list);
136
137/**
138 * Get a pointer to the first item in the list
139 *
140 * @param list Pointer to the linked list
141 *
142 * @returns px_link_list_item_t * Pointer to the first item in the list;
143 * NULL will be returned if the list is empty.
144 */
145px_link_list_item_t * px_link_list_get_item_first(px_link_list_t * list);
146
147/**
148 * Get a pointer to the last item in the list
149 *
150 * @param list Pointer to the linked list
151 *
152 * @returns px_link_list_item_t * Pointer to the last item in the list;
153 * NULL will be returned if the list is empty.
154 */
155px_link_list_item_t * px_link_list_get_item_last(px_link_list_t * list);
156
157/**
158 * Get a pointer to the next item in the list (after the specified item).
159 *
160 * @param list Pointer to the linked list
161 * @param item Current item
162 *
163 * @returns px_link_list_item_t * Pointer to the next item in the list;
164 * NULL will be returned if the specified item
165 * is the last one in the list.
166 */
167px_link_list_item_t * px_link_list_get_item_next(px_link_list_t * list,
168 px_link_list_item_t * item);
169
170/**
171 * Get a pointer to the previous item in the list (before the specified item).
172 *
173 * @param list Pointer to the linked list
174 * @param item Current item
175 *
176 * @returns px_link_list_item_t * Pointer to the next item in the list;
177 * NULL will be returned if the specified item
178 * is the first one in the list.
179 */
180px_link_list_item_t * px_link_list_get_item_prev(px_link_list_t * list,
181 px_link_list_item_t * item);
182
183/**
184 * Insert item to the start of the list.
185 *
186 * @param list Pointer to the linked list
187 * @param item Item to be inserted
188 *
189 * @retval true Item has been inserted
190 * @retval false List is full
191 */
192bool px_link_list_insert_item_start(px_link_list_t * list,
193 px_link_list_item_t * item);
194
195/**
196 * Add item to the end of the list.
197 *
198 * @param list Pointer to the linked list
199 * @param item Item to be inserted
200 *
201 * @retval true Item has been inserted
202 * @retval false List is full
203 */
204bool px_link_list_insert_item_end(px_link_list_t * list,
205 px_link_list_item_t * item);
206
207/**
208 * Insert item before specified item.
209 *
210 * @param list Pointer to the linked list
211 * @param item Item to be inserted
212 * @param item_pos Insert before this item
213 *
214 * @retval true Item has been inserted
215 * @retval false List is full
216 *
217 */
218bool px_link_list_insert_item_before(px_link_list_t * list,
219 px_link_list_item_t * item,
220 px_link_list_item_t * item_pos);
221
222/**
223 * Insert item after specified item.
224 *
225 * @param list Pointer to the linked list
226 * @param item Item to be inserted
227 * @param item_pos Insert after this item
228 *
229 * @retval true Item has been inserted
230 * @retval false List is full
231 *
232 */
233bool px_link_list_insert_item_after(px_link_list_t * list,
234 px_link_list_item_t * item,
235 px_link_list_item_t * item_pos);
236
237/**
238 * Remove first item from the list
239 *
240 * @param list Pointer to the linked list
241 *
242 * @return px_link_list_item_t * Pointer to the (old) first item;
243 * NULL will be returned if the list is empty.
244 */
245px_link_list_item_t * px_link_list_remove_item_first(px_link_list_t * list);
246
247/**
248 * Remove last item from the list
249 *
250 * @param list Pointer to the linked list
251 *
252 * @return px_link_list_item_t * Pointer to the (old) last item;
253 * NULL will be returned if the list is empty.
254 */
255px_link_list_item_t * px_link_list_remove_item_last(px_link_list_t * list);
256
257/**
258 * Remove item from the list
259 *
260 * @param list Pointer to the linked list
261 * @param item Item to be removed from the list
262 *
263 */
264void px_link_list_remove_item(px_link_list_t * list,
265 px_link_list_item_t * item);
266
267/**
268 * See if item is in the list
269 *
270 * @param list Pointer to the linked list
271 * @param item Pointer to specified item
272 *
273 * @retval true Item is in the list
274 * @retval false Item is not in the list
275 */
276bool px_link_list_has_item(px_link_list_t * list,
277 px_link_list_item_t * item);
278
279/* _____MACROS_______________________________________________________________ */
280
281#ifdef __cplusplus
282}
283#endif
284
285/// @}
286#endif
px_link_list_item_t::next
struct px_link_list_item_s * next
Pointer to next item in the list.
Definition: px_link_list.h:71
px_link_list_t::item_count
size_t item_count
Number of items in the list.
Definition: px_link_list.h:80
px_link_list_t::items_max
size_t items_max
Maximum number of items allowed in list; 0 means no limit.
Definition: px_link_list.h:81
px_link_list_t::first
struct px_link_list_item_s * first
Pointer to first item in the list.
Definition: px_link_list.h:78
px_link_list_t::last
struct px_link_list_item_s * last
Pointer to last item in the list.
Definition: px_link_list.h:79
px_link_list_item_t::prev
struct px_link_list_item_s * prev
Pointer to previous item in the list.
Definition: px_link_list.h:72
px_link_list_is_empty
bool px_link_list_is_empty(px_link_list_t *list)
See if the list is empty.
Definition: px_link_list.c:53
px_link_list_get_item_next
px_link_list_item_t * px_link_list_get_item_next(px_link_list_t *list, px_link_list_item_t *item)
Get a pointer to the next item in the list (after the specified item).
Definition: px_link_list.c:97
px_link_list_get_item_count
size_t px_link_list_get_item_count(px_link_list_t *list)
Get the number of items in the list.
Definition: px_link_list.c:82
px_link_list_remove_item_last
px_link_list_item_t * px_link_list_remove_item_last(px_link_list_t *list)
Remove last item from the list.
Definition: px_link_list.c:281
px_link_list_insert_item_end
bool px_link_list_insert_item_end(px_link_list_t *list, px_link_list_item_t *item)
Add item to the end of the list.
Definition: px_link_list.c:138
px_link_list_get_item_last
px_link_list_item_t * px_link_list_get_item_last(px_link_list_t *list)
Get a pointer to the last item in the list.
Definition: px_link_list.c:92
px_link_list_get_item_first
px_link_list_item_t * px_link_list_get_item_first(px_link_list_t *list)
Get a pointer to the first item in the list.
Definition: px_link_list.c:87
px_link_list_remove_item_first
px_link_list_item_t * px_link_list_remove_item_first(px_link_list_t *list)
Remove first item from the list.
Definition: px_link_list.c:251
px_link_list_get_item_prev
px_link_list_item_t * px_link_list_get_item_prev(px_link_list_t *list, px_link_list_item_t *item)
Get a pointer to the previous item in the list (before the specified item).
Definition: px_link_list.c:103
px_link_list_has_item
bool px_link_list_has_item(px_link_list_t *list, px_link_list_item_t *item)
See if item is in the list.
Definition: px_link_list.c:342
px_link_list_init
void px_link_list_init(px_link_list_t *list, size_t max_nr_of_items)
Initialises a linked list structure.
Definition: px_link_list.c:37
px_link_list_remove_item
void px_link_list_remove_item(px_link_list_t *list, px_link_list_item_t *item)
Remove item from the list.
Definition: px_link_list.c:311
px_link_list_insert_item_after
bool px_link_list_insert_item_after(px_link_list_t *list, px_link_list_item_t *item, px_link_list_item_t *item_pos)
Insert item after specified item.
Definition: px_link_list.c:209
px_link_list_is_full
bool px_link_list_is_full(px_link_list_t *list)
See if the list is full.
Definition: px_link_list.c:65
px_link_list_item_init
void px_link_list_item_init(px_link_list_t *list, px_link_list_item_t *item)
Initialises a list item.
Definition: px_link_list.c:46
px_link_list_insert_item_start
bool px_link_list_insert_item_start(px_link_list_t *list, px_link_list_item_t *item)
Insert item to the start of the list.
Definition: px_link_list.c:109
px_link_list_insert_item_before
bool px_link_list_insert_item_before(px_link_list_t *list, px_link_list_item_t *item, px_link_list_item_t *item_pos)
Insert item before specified item.
Definition: px_link_list.c:167
px_link_list_item_t
Link structure that must be at the head of each item in the list.
Definition: px_link_list.h:70
px_link_list_t
Linked list structure.
Definition: px_link_list.h:77