1 /*
2 * Copyright (c) 2013-2019 Huawei Technologies Co., Ltd. All rights reserved.
3 * Copyright (c) 2020-2021 Huawei Device Co., Ltd. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without modification,
6 * are permitted provided that the following conditions are met:
7 *
8 * 1. Redistributions of source code must retain the above copyright notice, this list of
9 * conditions and the following disclaimer.
10 *
11 * 2. Redistributions in binary form must reproduce the above copyright notice, this list
12 * of conditions and the following disclaimer in the documentation and/or other materials
13 * provided with the distribution.
14 *
15 * 3. Neither the name of the copyright holder nor the names of its contributors may be used
16 * to endorse or promote products derived from this software without specific prior written
17 * permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
21 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
23 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
24 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
25 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
26 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
27 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
28 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
29 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 */
31
32 /**
33 * @defgroup los_list Doubly linked list
34 * @ingroup kernel
35 */
36
37 #ifndef _LOS_LIST_H
38 #define _LOS_LIST_H
39
40 #include "los_compiler.h"
41
42 #ifdef __cplusplus
43 #if __cplusplus
44 extern "C" {
45 #endif /* __cplusplus */
46 #endif /* __cplusplus */
47
48 /**
49 * @ingroup los_list
50 * Structure of a node in a doubly linked list.
51 */
52 typedef struct LOS_DL_LIST {
53 struct LOS_DL_LIST *pstPrev; /**< Current node's pointer to the previous node */
54 struct LOS_DL_LIST *pstNext; /**< Current node's pointer to the next node */
55 } LOS_DL_LIST;
56
57 /**
58 * @ingroup los_list
59 * @brief Initialize a doubly linked list.
60 *
61 * @par Description:
62 * This API is used to initialize a doubly linked list.
63 * @attention
64 * <ul>
65 * <li>The parameter passed in should be ensured to be a legal pointer.</li>
66 * </ul>
67 *
68 * @param list [IN] Node in a doubly linked list.
69 *
70 * @retval None.
71 * @par Dependency:
72 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
73 * @see
74 */
LOS_ListInit(LOS_DL_LIST * list)75 LITE_OS_SEC_ALW_INLINE STATIC_INLINE VOID LOS_ListInit(LOS_DL_LIST *list)
76 {
77 list->pstNext = list;
78 list->pstPrev = list;
79 }
80
81 /**
82 * @ingroup los_list
83 * @brief Point to the next node pointed to by the current node.
84 *
85 * @par Description:
86 * <ul>
87 * <li>This API is used to point to the next node pointed to by the current node.</li>
88 * </ul>
89 * @attention
90 * <ul>
91 * <li>None.</li>
92 * </ul>
93 *
94 * @param object [IN] Node in the doubly linked list.
95 *
96 * @retval None.
97 * @par Dependency:
98 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
99 * @see
100 */
101 #define LOS_DL_LIST_FIRST(object) ((object)->pstNext)
102
103 /**
104 * @ingroup los_list
105 * @brief Insert a new node to a doubly linked list.
106 *
107 * @par Description:
108 * This API is used to insert a new node to a doubly linked list.
109 * @attention
110 * <ul>
111 * <li>The parameters passed in should be ensured to be legal pointers.</li>
112 * </ul>
113 *
114 * @param list [IN] Doubly linked list where the new node is inserted.
115 * @param node [IN] New node to be inserted.
116 *
117 * @retval None
118 * @par Dependency:
119 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
120 * @see LOS_ListDelete
121 */
LOS_ListAdd(LOS_DL_LIST * list,LOS_DL_LIST * node)122 LITE_OS_SEC_ALW_INLINE STATIC_INLINE VOID LOS_ListAdd(LOS_DL_LIST *list, LOS_DL_LIST *node)
123 {
124 node->pstNext = list->pstNext;
125 node->pstPrev = list;
126 list->pstNext->pstPrev = node;
127 list->pstNext = node;
128 }
129
130 /**
131 * @ingroup los_list
132 * @brief Insert a node to the tail of a doubly linked list.
133 *
134 * @par Description:
135 * This API is used to insert a new node to the tail of a doubly linked list.
136 * @attention
137 * <ul>
138 * <li>The parameters passed in should be ensured to be legal pointers.</li>
139 * </ul>
140 *
141 * @param list [IN] Doubly linked list where the new node is inserted.
142 * @param node [IN] New node to be inserted.
143 *
144 * @retval None.
145 * @par Dependency:
146 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
147 * @see LOS_ListAdd | LOS_ListHeadInsert
148 */
LOS_ListTailInsert(LOS_DL_LIST * list,LOS_DL_LIST * node)149 LITE_OS_SEC_ALW_INLINE STATIC_INLINE VOID LOS_ListTailInsert(LOS_DL_LIST *list, LOS_DL_LIST *node)
150 {
151 LOS_ListAdd(list->pstPrev, node);
152 }
153
154 /**
155 * @ingroup los_list
156 * @brief Insert a node to the head of a doubly linked list.
157 *
158 * @par Description:
159 * This API is used to insert a new node to the head of a doubly linked list.
160 * @attention
161 * <ul>
162 * <li>The parameters passed in should be ensured to be legal pointers.</li>
163 * </ul>
164 *
165 * @param list [IN] Doubly linked list where the new node is inserted.
166 * @param node [IN] New node to be inserted.
167 *
168 * @retval None.
169 * @par Dependency:
170 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
171 * @see LOS_ListAdd | LOS_ListTailInsert
172 */
LOS_ListHeadInsert(LOS_DL_LIST * list,LOS_DL_LIST * node)173 LITE_OS_SEC_ALW_INLINE STATIC_INLINE VOID LOS_ListHeadInsert(LOS_DL_LIST *list, LOS_DL_LIST *node)
174 {
175 LOS_ListAdd(list, node);
176 }
177
178 /**
179 * @ingroup los_list
180 * @brief Delete a specified node from a doubly linked list.
181 *
182 * @par Description:
183 * <ul>
184 * <li>This API is used to delete a specified node from a doubly linked list.</li>
185 * </ul>
186 * @attention
187 * <ul>
188 * <li>The parameter passed in should be ensured to be a legal pointer.</li>
189 * </ul>
190 *
191 * @param node [IN] Node to be deleted.
192 *
193 * @retval None.
194 * @par Dependency:
195 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
196 * @see LOS_ListAdd
197 */
LOS_ListDelete(LOS_DL_LIST * node)198 LITE_OS_SEC_ALW_INLINE STATIC_INLINE VOID LOS_ListDelete(LOS_DL_LIST *node)
199 {
200 node->pstNext->pstPrev = node->pstPrev;
201 node->pstPrev->pstNext = node->pstNext;
202 node->pstNext = (LOS_DL_LIST *)NULL;
203 node->pstPrev = (LOS_DL_LIST *)NULL;
204 }
205
206 /**
207 * @ingroup los_list
208 * @brief Identify whether a specified doubly linked list is empty.
209 *
210 * @par Description:
211 * <ul>
212 * <li>This API is used to return whether a doubly linked list is empty.</li>
213 * </ul>
214 * @attention
215 * <ul>
216 * <li>The parameter passed in should be ensured to be a legal pointer.</li>
217 * </ul>
218 *
219 * @param list [IN] Doubly linked node.
220 *
221 * @retval TRUE The doubly linked list is empty.
222 * @retval FALSE The doubly linked list is not empty.
223 * @par Dependency:
224 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
225 * @see
226 */
LOS_ListEmpty(LOS_DL_LIST * node)227 LITE_OS_SEC_ALW_INLINE STATIC_INLINE BOOL LOS_ListEmpty(LOS_DL_LIST *node)
228 {
229 return (BOOL)(node->pstNext == node);
230 }
231
232 /**
233 * @ingroup los_list
234 * @brief Obtain the pointer to a doubly linked list in a structure.
235 *
236 * @par Description:
237 * This API is used to obtain the pointer to a doubly linked list in a structure.
238 * @attention
239 * <ul>
240 * <li>None.</li>
241 * </ul>
242 *
243 * @param type [IN] Structure name.
244 * @param member [IN] Member name of the doubly linked list in the structure.
245 *
246 * @retval Pointer to the doubly linked list in the structure.
247 * @par Dependency:
248 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
249 * @see
250 */
251 #define LOS_OFF_SET_OF(type, member) ((UINT32)&(((type *)0)->member))
252
253 /**
254 * @ingroup los_list
255 * @brief Obtain the pointer to a structure that contains a doubly linked list.
256 *
257 * @par Description:
258 * This API is used to obtain the pointer to a structure that contains a doubly linked list.
259 * <ul>
260 * <li>None.</li>
261 * </ul>
262 * @attention
263 * <ul>
264 * <li>None.</li>
265 * </ul>
266 *
267 * @param item [IN] Current node's pointer to the next node.
268 * @param type [IN] Structure name.
269 * @param member [IN] Member name of the doubly linked list in the structure.
270 *
271 * @retval Pointer to the structure that contains the doubly linked list.
272 * @par Dependency:
273 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
274 * @see
275 */
276 #define LOS_DL_LIST_ENTRY(item, type, member) \
277 ((type *)(VOID *)((CHAR *)(item) - LOS_OFF_SET_OF(type, member))) \
278
279 /**
280 * @ingroup los_list
281 * @brief Iterate over a doubly linked list of given type.
282 *
283 * @par Description:
284 * This API is used to iterate over a doubly linked list of given type.
285 * @attention
286 * <ul>
287 * <li>None.</li>
288 * </ul>
289 *
290 * @param item [IN] Pointer to the structure that contains the doubly linked list that is to be traversed.
291 * @param list [IN] Pointer to the doubly linked list to be traversed.
292 * @param type [IN] Structure name.
293 * @param member [IN] Member name of the doubly linked list in the structure.
294 *
295 * @retval None.
296 * @par Dependency:
297 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
298 * @see
299 */
300 #define LOS_DL_LIST_FOR_EACH_ENTRY(item, list, type, member) \
301 for ((item) = LOS_DL_LIST_ENTRY((list)->pstNext, type, member); \
302 &(item)->member != (list); \
303 (item) = LOS_DL_LIST_ENTRY((item)->member.pstNext, type, member))
304
305 /**
306 * @ingroup los_list
307 * @brief iterate over a doubly linked list safe against removal of list entry.
308 *
309 * @par Description:
310 * This API is used to iterate over a doubly linked list safe against removal of list entry.
311 * @attention
312 * <ul>
313 * <li>None.</li>
314 * </ul>
315 *
316 * @param item [IN] Pointer to the structure that contains the doubly linked list that is to be traversed.
317 * @param next [IN] Save the next node.
318 * @param list [IN] Pointer to the doubly linked list to be traversed.
319 * @param type [IN] Structure name.
320 * @param member [IN] Member name of the doubly linked list in the structure.
321 *
322 * @retval None.
323 * @par Dependency:
324 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
325 * @see
326 */
327 #define LOS_DL_LIST_FOR_EACH_ENTRY_SAFE(item, next, list, type, member) \
328 for ((item) = LOS_DL_LIST_ENTRY((list)->pstNext, type, member), \
329 (next) = LOS_DL_LIST_ENTRY((item)->member.pstNext, type, member); \
330 &((item)->member) != (list); \
331 (item) = (next), (next) = LOS_DL_LIST_ENTRY((item)->member.pstNext, type, member))
332
333 /**
334 * @ingroup los_list
335 * @brief Delete initialize a doubly linked list.
336 *
337 * @par Description:
338 * This API is used to delete initialize a doubly linked list.
339 * @attention
340 * <ul>
341 * <li>The parameter passed in should be ensured to be s legal pointer.</li>
342 * </ul>
343 *
344 * @param list [IN] Doubly linked list.
345 *
346 * @retval None.
347 * @par Dependency:
348 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
349 * @see
350 */
LOS_ListDelInit(LOS_DL_LIST * list)351 LITE_OS_SEC_ALW_INLINE STATIC_INLINE VOID LOS_ListDelInit(LOS_DL_LIST *list)
352 {
353 list->pstNext->pstPrev = list->pstPrev;
354 list->pstPrev->pstNext = list->pstNext;
355 LOS_ListInit(list);
356 }
357
358 /**
359 * @ingroup los_list
360 * @brief iterate over a doubly linked list.
361 *
362 * @par Description:
363 * This API is used to iterate over a doubly linked list.
364 * @attention
365 * <ul>
366 * <li>None.</li>
367 * </ul>
368 *
369 * @param item [IN] Pointer to the structure that contains the doubly linked list that is to be traversed.
370 * @param list [IN] Pointer to the doubly linked list to be traversed.
371 *
372 * @retval None.
373 * @par Dependency:
374 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
375 * @see
376 */
377 #define LOS_DL_LIST_FOR_EACH(item, list) \
378 for ((item) = (list)->pstNext; (item) != (list); (item) = (item)->pstNext)
379
380 /**
381 * @ingroup los_list
382 * @brief Iterate over a doubly linked list safe against removal of list entry.
383 *
384 * @par Description:
385 * This API is used to iterate over a doubly linked list safe against removal of list entry.
386 * @attention
387 * <ul>
388 * <li>None.</li>
389 * </ul>
390 *
391 * @param item [IN] Pointer to the structure that contains the doubly linked list that is to be traversed.
392 * @param next [IN] Save the next node.
393 * @param list [IN] Pointer to the doubly linked list to be traversed.
394 *
395 * @retval None.
396 * @par Dependency:
397 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
398 * @see
399 */
400 #define LOS_DL_LIST_FOR_EACH_SAFE(item, next, list) \
401 for ((item) = (list)->pstNext, (next) = (item)->pstNext; (item) != (list); \
402 (item) = (next), (next) = (item)->pstNext)
403
404 /**
405 * @ingroup los_list
406 * @brief Initialize a double linked list.
407 *
408 * @par Description:
409 * This API is used to initialize a double linked list.
410 * @attention
411 * <ul>
412 * <li>None.</li>
413 * </ul>
414 *
415 * @param list [IN] Pointer to the doubly linked list to be traversed.
416 *
417 * @retval None.
418 * @par Dependency:
419 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
420 * @see
421 */
422 #define LOS_DL_LIST_HEAD(list) \
423 LOS_DL_LIST list = { &(list), &(list) }
424
425 #ifdef __cplusplus
426 #if __cplusplus
427 }
428 #endif /* __cplusplus */
429 #endif /* __cplusplus */
430
431 #endif /* _LOS_LIST_H */
432