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 {
128 struct List_Elem_ *next;
129 struct List_Elem_ *prev;
130 } List_Elem;
131
132 typedef struct
133 {
134 List_Elem *head;
135 List_Elem *tail;
136 } List_List;
137
138 /*!
139 * @brief Function to initialize the contents of a List_List
140 *
141 * @param list Pointer to a List_List structure that will be used to
142 * maintain a linked list
143 */
144 extern void List_clearList(List_List *list);
145
146 /*!
147 * @brief Function to test whether a linked list is empty
148 *
149 * @param list A pointer to a linked list
150 *
151 * @return true if empty, false if not empty
152 */
List_empty(List_List * list)153 static inline bool List_empty(List_List *list)
154 {
155 return (list->head == NULL);
156 }
157
158 /*!
159 * @brief Function to atomically get the first elem in a linked list
160 *
161 * @param list A pointer to a linked list
162 *
163 * @return Pointer the first elem in the linked list or NULL if empty
164 */
165 extern List_Elem *List_get(List_List *list);
166
167 /*!
168 * @brief Function to return the head of a linked list
169 *
170 * This function does not remove the head, it simply returns a pointer to
171 * it. This function is typically used when traversing a linked list.
172 *
173 * @param list A pointer to the linked list
174 *
175 * @return Pointer to the first elem in the linked list or NULL if empty
176 */
List_head(List_List * list)177 static inline List_Elem *List_head(List_List *list)
178 {
179 return (list->head);
180 }
181
182 /*!
183 * @brief Function to insert an elem into a linked list
184 *
185 * @param list A pointer to the linked list
186 *
187 * @param newElem New elem to insert
188 *
189 * @param curElem Elem to insert the newElem in front of.
190 * This value cannot be NULL.
191 */
192 extern void List_insert(List_List *list, List_Elem *newElem, List_Elem *curElem);
193
194 /*!
195 * @brief Function to return the next elem in a linked list
196 *
197 * This function does not remove the elem, it simply returns a pointer to
198 * next one. This function is typically used when traversing a linked list.
199 *
200 * @param elem Elem in the list
201 *
202 * @return Pointer to the next elem in linked list or NULL if at the end
203 */
List_next(List_Elem * elem)204 static inline List_Elem *List_next(List_Elem *elem)
205 {
206 return (elem->next);
207 }
208
209 /*!
210 * @brief Function to return the prev elem in a linked list
211 *
212 * This function does not remove the elem, it simply returns a pointer to
213 * prev one. This function is typically used when traversing a linked list.
214 *
215 * @param elem Elem in the list
216 *
217 * @return Pointer to the prev elem in linked list or NULL if at the beginning
218 */
List_prev(List_Elem * elem)219 static inline List_Elem *List_prev(List_Elem *elem)
220 {
221 return (elem->prev);
222 }
223
224 /*!
225 * @brief Function to atomically put an elem onto the end of a linked list
226 *
227 * @param list A pointer to the linked list
228 *
229 * @param elem Element to place onto the end of the linked list
230 */
231 extern void List_put(List_List *list, List_Elem *elem);
232
233 /*!
234 * @brief Function to atomically put an elem onto the head of a linked list
235 *
236 * @param list A pointer to the linked list
237 *
238 * @param elem Element to place onto the beginning of the linked list
239 */
240 extern void List_putHead(List_List *list, List_Elem *elem);
241
242 /*!
243 * @brief Function to remove an elem from a linked list
244 *
245 * @param list A pointer to the linked list
246 *
247 * @param elem Element to be removed from a linked list
248 */
249 extern void List_remove(List_List *list, List_Elem *elem);
250
251 /*!
252 * @brief Function to return the tail of a linked list
253 *
254 * This function does not remove the tail, it simply returns a pointer to
255 * it. This function is typically used when traversing a linked list.
256 *
257 * @param list A pointer to the linked list
258 *
259 * @return Pointer to the last elem in the linked list or NULL if empty
260 */
List_tail(List_List * list)261 static inline List_Elem *List_tail(List_List *list)
262 {
263 return (list->tail);
264 }
265
266 #ifdef __cplusplus
267 }
268 #endif
269
270 #endif /* ti_drivers_utils_List__include */
271
