1 /*
2 * Copyright (c) 2015-2019, Texas Instruments Incorporated
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * * Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 *
12 * * Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * * Neither the name of Texas Instruments Incorporated nor the names of
17 * its contributors may be used to endorse or promote products derived
18 * from this software without specific prior written permission.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
21 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
22 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
23 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
24 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
25 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
26 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
27 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
28 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
29 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
30 * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 */
32 /** ============================================================================
33 * @file List.h
34 *
35 * @brief Linked List interface for use in drivers
36 *
37 * This module provides simple doubly-link list implementation. There are two
38 * main structures:
39 * - ::List_List: The structure that holds the start of a linked list. There
40 * is no API to create one. It is up to the driver to provide the structure
41 * itself.
42 * - ::List_Elem: The structure that must be in the structure that is placed
43 * onto a linked list. Generally it is the first field in the structure. For
44 * example:
45 * @code
46 * typedef struct {
47 * List_Elem elem;
48 * void *buffer;
49 * } MyStruct;
50 * @endcode
51 *
52 * The following shows how to create a linked list with three elements.
53 *
54 * @code
55 * + denotes null-terminated
56 * _______ _______ _______ _______
57 * |_______|----->|_______|----->|_______|--->|_______|--//---,
58 * ,----|_______| ,-|_______|<-----|_______|<---|_______|<-//-, +
59 * | List + elem elem elem |
60 * |_____________________________________________________________|
61 * @endcode
62 *
63 * The APIs ::List_get, ::List_put, and ::List_putHead are
64 * atomic. The other APIs are not necessarily atomic. In other words, when
65 * traversing a linked list, it is up to the application to provide
66 * thread-safety (e.g. HwiP_disable/restore or MutexP_pend/post).
67 *
68 * Initializing and adding an element to the tail and removing it
69 * @code
70 * typedef struct {
71 * List_Elem elem;
72 * void *buffer;
73 * } MyStruct;
74 *
75 * List_List list;
76 * MyStruct foo;
77 * MyStruct *bar;
78 *
79 * List_clearList(&list);
80 * List_put(&list, (List_Elem *)&foo);
81 * bar = (MyStruct *)List_get(&list);
82 * @endcode
83 *
84 * The ::List_put and ::List_get APIs are used to maintain a first-in first-out
85 * (FIFO) linked list.
86 *
87 * The ::List_putHead and ::List_get APIs are used to maintain a last-in first-out
88 * (LIFO) linked list.
89 *
90 * Traversing a list from head to tail. Note: thread-safety calls are
91 * not shown here.
92 * @code
93 * List_List list;
94 * List_Elem *temp;
95 *
96 * for (temp = List_head(&list); temp != NULL; temp = List_next(temp)) {
97 * printf("address = 0x%x\n", temp);
98 * }
99 * @endcode
100 *
101 * Traversing a list from tail to head. Note: thread-safety calls are
102 * not shown here.
103 * @code
104 * List_List list;
105 * List_Elem *temp;
106 *
107 * for (temp = List_tail(&list); temp != NULL; temp = List_prev(temp)) {
108 * printf("address = 0x%x\n", temp);
109 * }
110 * @endcode
111 *
112 * ============================================================================
113 */
114
115 #ifndef ti_drivers_utils_List__include
116 #define ti_drivers_utils_List__include
117
118 #include <stdint.h>
119 #include <stdbool.h>
120 #include <stddef.h>
121
122 #ifdef __cplusplus
123 extern "C" {
124 #endif
125
126 typedef struct List_Elem_ {
127 struct List_Elem_ *next;
128 struct List_Elem_ *prev;
129 } List_Elem;
130
131 typedef struct {
132 List_Elem *head;
133 List_Elem *tail;
134 } List_List;
135
136 /*!
137 * @brief Function to initialize the contents of a List_List
138 *
139 * @param list Pointer to a List_List structure that will be used to
140 * maintain a linked list
141 */
142 extern void List_clearList(List_List *list);
143
144 /*!
145 * @brief Function to test whether a linked list is empty
146 *
147 * @param list A pointer to a linked list
148 *
149 * @return true if empty, false if not empty
150 */
List_empty(List_List * list)151 static inline bool List_empty(List_List *list)
152 {
153 return (list->head == NULL);
154 }
155
156 /*!
157 * @brief Function to atomically get the first elem in a linked list
158 *
159 * @param list A pointer to a linked list
160 *
161 * @return Pointer the first elem in the linked list or NULL if empty
162 */
163 extern List_Elem *List_get(List_List *list);
164
165 /*!
166 * @brief Function to return the head of a linked list
167 *
168 * This function does not remove the head, it simply returns a pointer to
169 * it. This function is typically used when traversing a linked list.
170 *
171 * @param list A pointer to the linked list
172 *
173 * @return Pointer to the first elem in the linked list or NULL if empty
174 */
List_head(List_List * list)175 static inline List_Elem *List_head(List_List *list)
176 {
177 return (list->head);
178 }
179
180 /*!
181 * @brief Function to insert an elem into a linked list
182 *
183 * @param list A pointer to the linked list
184 *
185 * @param newElem New elem to insert
186 *
187 * @param curElem Elem to insert the newElem in front of.
188 * This value cannot be NULL.
189 */
190 extern void List_insert(List_List *list, List_Elem *newElem,
191 List_Elem *curElem);
192
193 /*!
194 * @brief Function to return the next elem in a linked list
195 *
196 * This function does not remove the elem, it simply returns a pointer to
197 * next one. This function is typically used when traversing a linked list.
198 *
199 * @param elem Elem in the list
200 *
201 * @return Pointer to the next elem in linked list or NULL if at the end
202 */
List_next(List_Elem * elem)203 static inline List_Elem *List_next(List_Elem *elem)
204 {
205 return (elem->next);
206 }
207
208 /*!
209 * @brief Function to return the prev elem in a linked list
210 *
211 * This function does not remove the elem, it simply returns a pointer to
212 * prev one. This function is typically used when traversing a linked list.
213 *
214 * @param elem Elem in the list
215 *
216 * @return Pointer to the prev elem in linked list or NULL if at the beginning
217 */
List_prev(List_Elem * elem)218 static inline List_Elem *List_prev(List_Elem *elem)
219 {
220 return (elem->prev);
221 }
222
223 /*!
224 * @brief Function to atomically put an elem onto the end of a linked list
225 *
226 * @param list A pointer to the linked list
227 *
228 * @param elem Element to place onto the end of the linked list
229 */
230 extern void List_put(List_List *list, List_Elem *elem);
231
232 /*!
233 * @brief Function to atomically put an elem onto the head of a linked list
234 *
235 * @param list A pointer to the linked list
236 *
237 * @param elem Element to place onto the beginning of the linked list
238 */
239 extern void List_putHead(List_List *list, List_Elem *elem);
240
241 /*!
242 * @brief Function to remove an elem from a linked list
243 *
244 * @param list A pointer to the linked list
245 *
246 * @param elem Element to be removed from a linked list
247 */
248 extern void List_remove(List_List *list, List_Elem *elem);
249
250 /*!
251 * @brief Function to return the tail of a linked list
252 *
253 * This function does not remove the tail, it simply returns a pointer to
254 * it. This function is typically used when traversing a linked list.
255 *
256 * @param list A pointer to the linked list
257 *
258 * @return Pointer to the last elem in the linked list or NULL if empty
259 */
List_tail(List_List * list)260 static inline List_Elem *List_tail(List_List *list)
261 {
262 return (list->tail);
263 }
264
265 #ifdef __cplusplus
266 }
267 #endif
268
269 #endif /* ti_drivers_utils_List__include */
270
