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_typedef.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 *
60 * @par Description:
61 * This API is used to initialize a doubly linked list.
62 * @attention
63 * <ul>
64 * <li>The parameter passed in should be ensured to be a legal pointer.</li>
65 * </ul>
66 *
67 * @param list [IN] Node in a doubly linked list.
68 *
69 * @retval None.
70 * @par Dependency:
71 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
72 * @see
73 */
LOS_ListInit(LOS_DL_LIST * list)74 LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListInit(LOS_DL_LIST *list)
75 {
76 list->pstNext = list;
77 list->pstPrev = list;
78 }
79
80 /**
81 * @ingroup los_list
82 * @brief Point to the next node pointed to by the current node.
83 *
84 * @par Description:
85 * <ul>
86 * <li>This API is used to point to the next node pointed to by the current node.</li>
87 * </ul>
88 * @attention
89 * <ul>
90 * <li>None.</li>
91 * </ul>
92 *
93 * @param object [IN] Node in the doubly linked list.
94 *
95 * @retval None.
96 * @par Dependency:
97 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
98 * @see
99 */
100 #define LOS_DL_LIST_FIRST(object) ((object)->pstNext)
101
102 /**
103 * @ingroup los_list
104 * @brief Node is the end of the list.
105 *
106 * @par Description:
107 * <ul>
108 * <li>This API is used to test node is the end of the list.</li>
109 * </ul>
110 * @attention
111 * <ul>
112 * <li>None.</li>
113 * </ul>
114 *
115 * @param list [IN] Doubly linked list.
116 * @param node [IN] The node to be tested if the end of the list.
117 *
118 * @retval None.
119 * @par Dependency:
120 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
121 * @see
122 */
123 #define LOS_DL_LIST_IS_END(list, node) ((list) == (node) ? TRUE : FALSE)
124
125 /**
126 * @ingroup los_list
127 * @brief Node is on the list.
128 *
129 * @par Description:
130 * <ul>
131 * <li>This API is used to test node is on the list.</li>
132 * </ul>
133 * @attention
134 * <ul>
135 * <li>None.</li>
136 * </ul>
137 *
138 * @param object [IN] Node in the doubly linked list.
139 *
140 * @retval None.
141 * @par Dependency:
142 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
143 * @see
144 */
145 #define LOS_DL_LIST_IS_ON_QUEUE(node) ((node)->pstPrev != NULL && (node)->pstNext != NULL)
146
147 /**
148 * @ingroup los_list
149 * @brief Point to the previous node pointed to by the current node.
150 *
151 * @par Description:
152 * <ul>
153 * <li>This API is used to point to the previous node pointed to by the current node.</li>
154 * </ul>
155 * @attention
156 * <ul>
157 * <li>None.</li>
158 * </ul>
159 *
160 * @param object [IN] Node in the doubly linked list.
161 *
162 * @retval None.
163 * @par Dependency:
164 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
165 * @see
166 */
167 #define LOS_DL_LIST_LAST(object) ((object)->pstPrev)
168
169 /**
170 * @ingroup los_list
171 * @brief Insert a new node to a doubly linked list.
172 *
173 * @par Description:
174 * This API is used to insert a new node to a doubly linked list.
175 * @attention
176 * <ul>
177 * <li>The parameters passed in should be ensured to be legal pointers.</li>
178 * </ul>
179 *
180 * @param list [IN] Doubly linked list where the new node is inserted.
181 * @param node [IN] New node to be inserted.
182 *
183 * @retval None
184 * @par Dependency:
185 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
186 * @see LOS_ListDelete
187 */
LOS_ListAdd(LOS_DL_LIST * list,LOS_DL_LIST * node)188 LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListAdd(LOS_DL_LIST *list, LOS_DL_LIST *node)
189 {
190 node->pstNext = list->pstNext;
191 node->pstPrev = list;
192 list->pstNext->pstPrev = node;
193 list->pstNext = node;
194 }
195
196 /**
197 * @ingroup los_list
198 * @brief Insert a node to the tail of a doubly linked list.
199 *
200 * @par Description:
201 * This API is used to insert a new node to the tail of a doubly linked list.
202 * @attention
203 * <ul>
204 * <li>The parameters passed in should be ensured to be legal pointers.</li>
205 * </ul>
206 *
207 * @param list [IN] Doubly linked list where the new node is inserted.
208 * @param node [IN] New node to be inserted.
209 *
210 * @retval None.
211 * @par Dependency:
212 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
213 * @see LOS_ListAdd | LOS_ListHeadInsert
214 */
LOS_ListTailInsert(LOS_DL_LIST * list,LOS_DL_LIST * node)215 LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListTailInsert(LOS_DL_LIST *list, LOS_DL_LIST *node)
216 {
217 LOS_ListAdd(list->pstPrev, node);
218 }
219
220 /**
221 * @ingroup los_list
222 * @brief Insert a node to the head of a doubly linked list.
223 *
224 * @par Description:
225 * This API is used to insert a new node to the head of a doubly linked list.
226 * @attention
227 * <ul>
228 * <li>The parameters passed in should be ensured to be legal pointers.</li>
229 * </ul>
230 *
231 * @param list [IN] Doubly linked list where the new node is inserted.
232 * @param node [IN] New node to be inserted.
233 *
234 * @retval None.
235 * @par Dependency:
236 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
237 * @see LOS_ListAdd | LOS_ListTailInsert
238 */
LOS_ListHeadInsert(LOS_DL_LIST * list,LOS_DL_LIST * node)239 LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListHeadInsert(LOS_DL_LIST *list, LOS_DL_LIST *node)
240 {
241 LOS_ListAdd(list, node);
242 }
243
244 /**
245 * @ingroup los_list
246 *
247 * @par Description:
248 * <ul>
249 * <li>This API is used to delete a specified node from a doubly linked list.</li>
250 * </ul>
251 * @attention
252 * <ul>
253 * <li>The parameter passed in should be ensured to be a legal pointer.</li>
254 * </ul>
255 *
256 * @param node [IN] Node to be deleted.
257 *
258 * @retval None.
259 * @par Dependency:
260 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
261 * @see LOS_ListAdd
262 */
LOS_ListDelete(LOS_DL_LIST * node)263 LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListDelete(LOS_DL_LIST *node)
264 {
265 node->pstNext->pstPrev = node->pstPrev;
266 node->pstPrev->pstNext = node->pstNext;
267 node->pstNext = NULL;
268 node->pstPrev = NULL;
269 }
270
271 /**
272 * @ingroup los_list
273 * @brief Identify whether a specified doubly linked list is empty.
274 *
275 * @par Description:
276 * <ul>
277 * <li>This API is used to return whether a doubly linked list is empty.</li>
278 * </ul>
279 * @attention
280 * <ul>
281 * <li>The parameter passed in should be ensured to be a legal pointer.</li>
282 * </ul>
283 *
284 * @param list [IN] Doubly linked list.
285 *
286 * @retval TRUE The doubly linked list is empty.
287 * @retval FALSE The doubly linked list is not empty.
288 * @par Dependency:
289 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
290 * @see
291 */
LOS_ListEmpty(LOS_DL_LIST * list)292 LITE_OS_SEC_ALW_INLINE STATIC INLINE BOOL LOS_ListEmpty(LOS_DL_LIST *list)
293 {
294 return (BOOL)(list->pstNext == list);
295 }
296
297 /**
298 * @ingroup los_list
299 * @brief Insert a new list to a doubly linked list.
300 *
301 * @par Description:
302 * This API is used to insert a new list to a doubly linked list.
303 * @attention
304 * <ul>
305 * <li>The parameters passed in should be ensured to be legal pointers.</li>
306 * </ul>
307 *
308 * @param oldList [IN] Doubly linked list where the new list is inserted.
309 * @param newList [IN] New list to be inserted.
310 *
311 * @retval None
312 * @par Dependency:
313 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
314 * @see LOS_ListDelete
315 */
LOS_ListAddList(LOS_DL_LIST * oldList,LOS_DL_LIST * newList)316 LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListAddList(LOS_DL_LIST *oldList, LOS_DL_LIST *newList)
317 {
318 LOS_DL_LIST *oldListHead = oldList->pstNext;
319 LOS_DL_LIST *oldListTail = oldList;
320 LOS_DL_LIST *newListHead = newList;
321 LOS_DL_LIST *newListTail = newList->pstPrev;
322
323 oldListTail->pstNext = newListHead;
324 newListHead->pstPrev = oldListTail;
325 oldListHead->pstPrev = newListTail;
326 newListTail->pstNext = oldListHead;
327 }
328
329 /**
330 * @ingroup los_list
331 * @brief Insert a doubly list to the tail of a doubly linked list.
332 *
333 * @par Description:
334 * This API is used to insert a new doubly list to the tail of a doubly linked list.
335 * @attention
336 * <ul>
337 * <li>The parameters passed in should be ensured to be legal pointers.</li>
338 * </ul>
339 *
340 * @param oldList [IN] Doubly linked list where the new list is inserted.
341 * @param newList [IN] New list to be inserted.
342 *
343 * @retval None.
344 * @par Dependency:
345 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
346 * @see LOS_ListAddList | LOS_ListHeadInsertList
347 */
LOS_ListTailInsertList(LOS_DL_LIST * oldList,LOS_DL_LIST * newList)348 LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListTailInsertList(LOS_DL_LIST *oldList, LOS_DL_LIST *newList)
349 {
350 LOS_ListAddList(oldList->pstPrev, newList);
351 }
352
353 /**
354 * @ingroup los_list
355 * @brief Insert a doubly list to the head of a doubly linked list.
356 *
357 * @par Description:
358 * This API is used to insert a new doubly list to the head of a doubly linked list.
359 * @attention
360 * <ul>
361 * <li>The parameters passed in should be ensured to be legal pointers.</li>
362 * </ul>
363 *
364 * @param oldList [IN] Doubly linked list where the new list is inserted.
365 * @param newList [IN] New list to be inserted.
366 *
367 * @retval None.
368 * @par Dependency:
369 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
370 * @see LOS_ListAddList | LOS_ListTailInsertList
371 */
LOS_ListHeadInsertList(LOS_DL_LIST * oldList,LOS_DL_LIST * newList)372 LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListHeadInsertList(LOS_DL_LIST *oldList, LOS_DL_LIST *newList)
373 {
374 LOS_ListAddList(oldList, newList);
375 }
376
377 /**
378 * @ingroup los_list
379 * @brief Obtain the offset of a field to a structure address.
380 *
381 * @par Description:
382 * This API is used to obtain the offset of a field to a structure address.
383 * @attention
384 * <ul>
385 * <li>None.</li>
386 * </ul>
387 *
388 * @param type [IN] Structure name.
389 * @param member [IN] Name of the member of which the offset is to be measured.
390 *
391 * @retval Offset of the field to the structure address.
392 * @par Dependency:
393 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
394 * @see
395 */
396 #define LOS_OFF_SET_OF(type, member) ((UINTPTR)&((type *)0)->member)
397
398 /**
399 * @ingroup los_list
400 * @brief Obtain the pointer to a structure that contains a doubly linked list.
401 *
402 * @par Description:
403 * This API is used to obtain the pointer to a structure that contains a doubly linked list.
404 * <ul>
405 * <li>None.</li>
406 * </ul>
407 * @attention
408 * <ul>
409 * <li>None.</li>
410 * </ul>
411 *
412 * @param item [IN] Current node's pointer to the next node.
413 * @param type [IN] Structure name.
414 * @param member [IN] Member name of the doubly linked list in the structure.
415 *
416 * @retval Pointer to the structure that contains the doubly linked list.
417 * @par Dependency:
418 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
419 * @see
420 */
421 #define LOS_DL_LIST_ENTRY(item, type, member) \
422 ((type *)(VOID *)((CHAR *)(item) - LOS_OFF_SET_OF(type, member)))
423
424 /**
425 * @ingroup los_list
426 * @brief Iterate over a doubly linked list of given type.
427 *
428 * @par Description:
429 * This API is used to iterate over a doubly linked list of given type.
430 * @attention
431 * <ul>
432 * <li>None.</li>
433 * </ul>
434 *
435 * @param item [IN] Pointer to the structure that contains the doubly linked list that is to be traversed.
436 * @param list [IN] Pointer to the doubly linked list to be traversed.
437 * @param type [IN] Structure name.
438 * @param member [IN] Member name of the doubly linked list in the structure.
439 *
440 * @retval None.
441 * @par Dependency:
442 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
443 * @see
444 */
445 #define LOS_DL_LIST_FOR_EACH_ENTRY(item, list, type, member) \
446 for (item = LOS_DL_LIST_ENTRY((list)->pstNext, type, member); \
447 &(item)->member != (list); \
448 item = LOS_DL_LIST_ENTRY((item)->member.pstNext, type, member))
449
450 /**
451 * @ingroup los_list
452 * @brief iterate over a doubly linked list safe against removal of list entry.
453 *
454 * @par Description:
455 * This API is used to iterate over a doubly linked list safe against removal of list entry.
456 * @attention
457 * <ul>
458 * <li>None.</li>
459 * </ul>
460 *
461 * @param item [IN] Pointer to the structure that contains the doubly linked list that is to be traversed.
462 * @param next [IN] Save the next node.
463 * @param list [IN] Pointer to the doubly linked list to be traversed.
464 * @param type [IN] Structure name.
465 * @param member [IN] Member name of the doubly linked list in the structure.
466 *
467 * @retval None.
468 * @par Dependency:
469 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
470 * @see
471 */
472 #define LOS_DL_LIST_FOR_EACH_ENTRY_SAFE(item, next, list, type, member) \
473 for (item = LOS_DL_LIST_ENTRY((list)->pstNext, type, member), \
474 next = LOS_DL_LIST_ENTRY((item)->member.pstNext, type, member); \
475 &(item)->member != (list); \
476 item = next, next = LOS_DL_LIST_ENTRY((item)->member.pstNext, type, member))
477
478 /**
479 * @ingroup los_list
480 * @brief Delete initialize a doubly linked list.
481 *
482 * @par Description:
483 * This API is used to delete initialize a doubly linked list.
484 * @attention
485 * <ul>
486 * <li>The parameter passed in should be ensured to be s legal pointer.</li>
487 * </ul>
488 *
489 * @param list [IN] Doubly linked list.
490 *
491 * @retval None.
492 * @par Dependency:
493 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
494 * @see
495 */
LOS_ListDelInit(LOS_DL_LIST * list)496 LITE_OS_SEC_ALW_INLINE STATIC INLINE VOID LOS_ListDelInit(LOS_DL_LIST *list)
497 {
498 list->pstNext->pstPrev = list->pstPrev;
499 list->pstPrev->pstNext = list->pstNext;
500 LOS_ListInit(list);
501 }
502
503 /**
504 * @ingroup los_list
505 * @brief iterate over a doubly linked list.
506 *
507 * @par Description:
508 * This API is used to iterate over a doubly linked list.
509 * @attention
510 * <ul>
511 * <li>None.</li>
512 * </ul>
513 *
514 * @param item [IN] Pointer to the structure that contains the doubly linked list that is to be traversed.
515 * @param list [IN] Pointer to the doubly linked list to be traversed.
516 *
517 * @retval None.
518 * @par Dependency:
519 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
520 * @see
521 */
522 #define LOS_DL_LIST_FOR_EACH(item, list) \
523 for (item = (list)->pstNext; \
524 (item) != (list); \
525 item = (item)->pstNext)
526
527 /**
528 * @ingroup los_list
529 * @brief Iterate over a doubly linked list safe against removal of list entry.
530 *
531 * @par Description:
532 * This API is used to iterate over a doubly linked list safe against removal of list entry.
533 * @attention
534 * <ul>
535 * <li>None.</li>
536 * </ul>
537 *
538 * @param item [IN] Pointer to the structure that contains the doubly linked list that is to be traversed.
539 * @param next [IN] Save the next node.
540 * @param list [IN] Pointer to the doubly linked list to be traversed.
541 *
542 * @retval None.
543 * @par Dependency:
544 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
545 * @see
546 */
547 #define LOS_DL_LIST_FOR_EACH_SAFE(item, next, list) \
548 for (item = (list)->pstNext, next = (item)->pstNext; \
549 (item) != (list); \
550 item = next, next = (item)->pstNext)
551
552 /**
553 * @ingroup los_list
554 * @brief Initialize a double linked list.
555 *
556 * @par Description:
557 * This API is used to initialize a double linked list.
558 * @attention
559 * <ul>
560 * <li>None.</li>
561 * </ul>
562 *
563 * @param list [IN] Pointer to the doubly linked list to be traversed.
564 *
565 * @retval None.
566 * @par Dependency:
567 * <ul><li>los_list.h: the header file that contains the API declaration.</li></ul>
568 * @see
569 */
570 #define LOS_DL_LIST_HEAD(list) LOS_DL_LIST list = { &(list), &(list) }
571
572 #define LOS_ListPeekHeadType(list, type, element) ({ \
573 type *__t; \
574 if ((list)->pstNext == list) { \
575 __t = NULL; \
576 } else { \
577 __t = LOS_DL_LIST_ENTRY((list)->pstNext, type, element); \
578 } \
579 __t; \
580 })
581
582 #define LOS_ListRemoveHeadType(list, type, element) ({ \
583 type *__t; \
584 if ((list)->pstNext == list) { \
585 __t = NULL; \
586 } else { \
587 __t = LOS_DL_LIST_ENTRY((list)->pstNext, type, element); \
588 LOS_ListDelete((list)->pstNext); \
589 } \
590 __t; \
591 })
592
593 #define LOS_ListNextType(list, item, type, element) ({ \
594 type *__t; \
595 if ((item)->pstNext == list) { \
596 __t = NULL; \
597 } else { \
598 __t = LOS_DL_LIST_ENTRY((item)->pstNext, type, element); \
599 } \
600 __t; \
601 })
602
603 #ifdef __cplusplus
604 #if __cplusplus
605 }
606 #endif /* __cplusplus */
607 #endif /* __cplusplus */
608
609 #endif /* _LOS_LIST_H */
610