1/*
2 * Copyright (c) 2020 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 *     http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16/*
17 * @defgroup utils_list Doubly linked list
18 * @ingroup utils
19 * @attention
20 * <ul>
21 * <li>All of the APIs provided in this module are not thread-safe.</li>
22 * </ul>
23 */
24
25#ifndef _UTILS_LIST_H
26#define _UTILS_LIST_H
27
28#include <stdbool.h>
29#include "ohos_types.h"
30
31#ifdef __cplusplus
32#if __cplusplus
33extern "C" {
34#endif /* __cplusplus */
35#endif /* __cplusplus */
36
37typedef struct UTILS_DL_LIST {
38    struct UTILS_DL_LIST *pstPrev; /* < Current node's pointer to the previous node */
39    struct UTILS_DL_LIST *pstNext; /* < Current node's pointer to the next node */
40} UTILS_DL_LIST;
41
42/*
43 * @ingroup utils_list
44 *
45 * @par Description:
46 * This API is used to initialize a doubly linked list.
47 * @attention
48 * <ul>
49 * <li>The parameter passed in should be ensured to be a legal pointer.</li>
50 * </ul>
51 *
52 * @param list    [IN] Node in a doubly linked list.
53 *
54 * @retval None.
55 * @par Dependency:
56 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
57 * @see
58 */
59static inline void UtilsListInit(UTILS_DL_LIST *list)
60{
61    list->pstNext = list;
62    list->pstPrev = list;
63}
64
65/*
66 * @ingroup utils_list
67 * @brief Point to the next node pointed to by the current node.
68 *
69 * @par Description:
70 * <ul>
71 * <li>This API is used to point to the next node pointed to by the current node.</li>
72 * </ul>
73 * @attention
74 * <ul>
75 * <li>None.</li>
76 * </ul>
77 *
78 * @param object  [IN] Node in the doubly linked list.
79 *
80 * @retval None.
81 * @par Dependency:
82 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
83 * @see
84 */
85#define UTILS_DL_LIST_FIRST(object) ((object)->pstNext)
86
87/*
88 * @ingroup utils_list
89 * @brief Node is the end of the list.
90 *
91 * @par Description:
92 * <ul>
93 * <li>This API is used to test node is the end of the list.</li>
94 * </ul>
95 * @attention
96 * <ul>
97 * <li>None.</li>
98 * </ul>
99 *
100 * @param object  [IN] Node in the doubly linked list.
101 *
102 * @retval None.
103 * @par Dependency:
104 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
105 * @see
106 */
107#define UTILS_DL_LIST_IS_END(list, node) ((list) == (node) ? TRUE : FALSE)
108
109/*
110 * @ingroup utils_list
111 * @brief Node is on the list.
112 *
113 * @par Description:
114 * <ul>
115 * <li>This API is used to test node is on the list.</li>
116 * </ul>
117 * @attention
118 * <ul>
119 * <li>None.</li>
120 * </ul>
121 *
122 * @param object  [IN] Node in the doubly linked list.
123 *
124 * @retval None.
125 * @par Dependency:
126 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
127 * @see
128 */
129#define UTILS_DL_LIST_IS_ON_QUEUE(node) ((node)->pstPrev != NULL && (node)->pstNext != NULL)
130
131/*
132 * @ingroup utils_list
133 * @brief Point to the previous node pointed to by the current node.
134 *
135 * @par Description:
136 * <ul>
137 * <li>This API is used to point to the previous node pointed to by the current node.</li>
138 * </ul>
139 * @attention
140 * <ul>
141 * <li>None.</li>
142 * </ul>
143 *
144 * @param object  [IN] Node in the doubly linked list.
145 *
146 * @retval None.
147 * @par Dependency:
148 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
149 * @see
150 */
151#define UTILS_DL_LIST_LAST(object) ((object)->pstPrev)
152
153/*
154 * @ingroup utils_list
155 * @brief Insert a new node to a doubly linked list.
156 *
157 * @par Description:
158 * This API is used to insert a new node to a doubly linked list.
159 * @attention
160 * <ul>
161 * <li>The parameters passed in should be ensured to be legal pointers.</li>
162 * </ul>
163 *
164 * @param list    [IN] Doubly linked list where the new node is inserted.
165 * @param node    [IN] New node to be inserted.
166 *
167 * @retval None
168 * @par Dependency:
169 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
170 * @see UtilsListDelete
171 */
172static inline void UtilsListAdd(UTILS_DL_LIST *list, UTILS_DL_LIST *node)
173{
174    node->pstNext = list->pstNext;
175    node->pstPrev = list;
176    list->pstNext->pstPrev = node;
177    list->pstNext = node;
178}
179
180/*
181 * @ingroup utils_list
182 * @brief Insert a node to the tail of a doubly linked list.
183 *
184 * @par Description:
185 * This API is used to insert a new node to the tail of a doubly linked list.
186 * @attention
187 * <ul>
188 * <li>The parameters passed in should be ensured to be legal pointers.</li>
189 * </ul>
190 *
191 * @param list     [IN] Doubly linked list where the new node is inserted.
192 * @param node     [IN] New node to be inserted.
193 *
194 * @retval None.
195 * @par Dependency:
196 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
197 * @see UtilsListAdd | UtilsListHeadInsert
198 */
199static inline void UtilsListTailInsert(UTILS_DL_LIST *list, UTILS_DL_LIST *node)
200{
201    UtilsListAdd(list->pstPrev, node);
202}
203
204/*
205 * @ingroup utils_list
206 * @brief Insert a node to the head of a doubly linked list.
207 *
208 * @par Description:
209 * This API is used to insert a new node to the head of a doubly linked list.
210 * @attention
211 * <ul>
212 * <li>The parameters passed in should be ensured to be legal pointers.</li>
213 * </ul>
214 *
215 * @param list     [IN] Doubly linked list where the new node is inserted.
216 * @param node     [IN] New node to be inserted.
217 *
218 * @retval None.
219 * @par Dependency:
220 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
221 * @see UtilsListAdd | UtilsListTailInsert
222 */
223static inline void UtilsListHeadInsert(UTILS_DL_LIST *list, UTILS_DL_LIST *node)
224{
225    UtilsListAdd(list, node);
226}
227
228/*
229 * @ingroup utils_list
230 *
231 * @par Description:
232 * <ul>
233 * <li>This API is used to delete a specified node from a doubly linked list.</li>
234 * </ul>
235 * @attention
236 * <ul>
237 * <li>The parameter passed in should be ensured to be a legal pointer.</li>
238 * </ul>
239 *
240 * @param node    [IN] Node to be deleted.
241 *
242 * @retval None.
243 * @par Dependency:
244 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
245 * @see UtilsListAdd
246 */
247static inline void UtilsListDelete(UTILS_DL_LIST *node)
248{
249    node->pstNext->pstPrev = node->pstPrev;
250    node->pstPrev->pstNext = node->pstNext;
251    node->pstNext = NULL;
252    node->pstPrev = NULL;
253}
254
255/*
256 * @ingroup utils_list
257 * @brief Identify whether a specified doubly linked list is empty.
258 *
259 * @par Description:
260 * <ul>
261 * <li>This API is used to return whether a doubly linked list is empty.</li>
262 * </ul>
263 * @attention
264 * <ul>
265 * <li>The parameter passed in should be ensured to be a legal pointer.</li>
266 * </ul>
267 *
268 * @param list  [IN] Doubly linked list.
269 *
270 * @retval TRUE The doubly linked list is empty.
271 * @retval FALSE The doubly linked list is not empty.
272 * @par Dependency:
273 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
274 * @see
275 */
276static inline bool UtilsListEmpty(UTILS_DL_LIST *list)
277{
278    return (bool)(list->pstNext == list);
279}
280
281/*
282 * @ingroup utils_list
283 * @brief Insert a new list to a doubly linked list.
284 *
285 * @par Description:
286 * This API is used to insert a new list to a doubly linked list.
287 * @attention
288 * <ul>
289 * <li>The parameters passed in should be ensured to be legal pointers.</li>
290 * </ul>
291 *
292 * @param oldList    [IN] Doubly linked list where the new list is inserted.
293 * @param newList    [IN] New list to be inserted.
294 *
295 * @retval None
296 * @par Dependency:
297 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
298 * @see UtilsListDelete
299 */
300static inline void UtilsListAddList(UTILS_DL_LIST *oldList, UTILS_DL_LIST *newList)
301{
302    UTILS_DL_LIST *oldListHead = oldList->pstNext;
303    UTILS_DL_LIST *oldListTail = oldList;
304    UTILS_DL_LIST *newListHead = newList;
305    UTILS_DL_LIST *newListTail = newList->pstPrev;
306
307    oldListTail->pstNext = newListHead;
308    newListHead->pstPrev = oldListTail;
309    oldListHead->pstPrev = newListTail;
310    newListTail->pstNext = oldListHead;
311}
312
313/*
314 * @ingroup utils_list
315 * @brief Insert a doubly list to the tail of a doubly linked list.
316 *
317 * @par Description:
318 * This API is used to insert a new doubly list to the tail of a doubly linked list.
319 * @attention
320 * <ul>
321 * <li>The parameters passed in should be ensured to be legal pointers.</li>
322 * </ul>
323 *
324 * @param oldList     [IN] Doubly linked list where the new list is inserted.
325 * @param newList     [IN] New list to be inserted.
326 *
327 * @retval None.
328 * @par Dependency:
329 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
330 * @see UtilsListAddList | UtilsListHeadInsertList
331 */
332static inline void UtilsListTailInsertList(UTILS_DL_LIST *oldList, UTILS_DL_LIST *newList)
333{
334    UtilsListAddList(oldList->pstPrev, newList);
335}
336
337/*
338 * @ingroup utils_list
339 * @brief Insert a doubly list to the head of a doubly linked list.
340 *
341 * @par Description:
342 * This API is used to insert a new doubly list to the head of a doubly linked list.
343 * @attention
344 * <ul>
345 * <li>The parameters passed in should be ensured to be legal pointers.</li>
346 * </ul>
347 *
348 * @param oldList     [IN] Doubly linked list where the new list is inserted.
349 * @param newList     [IN] New list to be inserted.
350 *
351 * @retval None.
352 * @par Dependency:
353 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
354 * @see UtilsListAddList | UtilsListTailInsertList
355 */
356static inline void UtilsListHeadInsertList(UTILS_DL_LIST *oldList, UTILS_DL_LIST *newList)
357{
358    UtilsListAddList(oldList, newList);
359}
360
361/*
362 * @ingroup utils_list
363 * @brief Obtain the offset of a field to a structure address.
364 *
365 * @par  Description:
366 * This API is used to obtain the offset of a field to a structure address.
367 * @attention
368 * <ul>
369 * <li>None.</li>
370 * </ul>
371 *
372 * @param type   [IN] Structure name.
373 * @param field  [IN] Name of the field of which the offset is to be measured.
374 *
375 * @retval Offset of the field to the structure address.
376 * @par Dependency:
377 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
378 * @see
379 */
380#ifndef OFFSET_OF_FIELD
381#define OFFSET_OF_FIELD(type, field) ((unsigned int)&((type *)0)->field)
382#endif
383
384/*
385 * @ingroup utils_list
386 * @brief Obtain the pointer to a doubly linked list in a structure.
387 *
388 * @par Description:
389 * This API is used to obtain the pointer to a doubly linked list in a structure.
390 * @attention
391 * <ul>
392 * <li>None.</li>
393 * </ul>
394 *
395 * @param type    [IN] Structure name.
396 * @param member  [IN] Member name of the doubly linked list in the structure.
397 *
398 * @retval Pointer to the doubly linked list in the structure.
399 * @par Dependency:
400 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
401 * @see
402 */
403#define UTILS_OFF_SET_OF(type, member) ((unsigned int)&((type *)0)->member)
404
405/*
406 * @ingroup utils_list
407 * @brief Obtain the pointer to a structure that contains a doubly linked list.
408 *
409 * @par Description:
410 * This API is used to obtain the pointer to a structure that contains a doubly linked list.
411 * <ul>
412 * <li>None.</li>
413 * </ul>
414 * @attention
415 * <ul>
416 * <li>None.</li>
417 * </ul>
418 *
419 * @param item    [IN] Current node's pointer to the next node.
420 * @param type    [IN] Structure name.
421 * @param member  [IN] Member name of the doubly linked list in the structure.
422 *
423 * @retval Pointer to the structure that contains the doubly linked list.
424 * @par Dependency:
425 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
426 * @see
427 */
428#define UTILS_DL_LIST_ENTRY(item, type, member) \
429    ((type *)(void *)((char *)(item) - UTILS_OFF_SET_OF(type, member)))
430
431/*
432 * @ingroup utils_list
433 * @brief Iterate over a doubly linked list of given type.
434 *
435 * @par Description:
436 * This API is used to iterate over a doubly linked list of given type.
437 * @attention
438 * <ul>
439 * <li>None.</li>
440 * </ul>
441 *
442 * @param item           [IN] Pointer to the structure that contains the doubly linked list that is to be traversed.
443 * @param list           [IN] Pointer to the doubly linked list to be traversed.
444 * @param type           [IN] Structure name.
445 * @param member         [IN] Member name of the doubly linked list in the structure.
446 *
447 * @retval None.
448 * @par Dependency:
449 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
450 * @see
451 */
452#define UTILS_DL_LIST_FOR_EACH_ENTRY(item, list, type, member)             \
453    for (item = UTILS_DL_LIST_ENTRY((list)->pstNext, type, member);        \
454         &(item)->member != (list);                                      \
455         item = UTILS_DL_LIST_ENTRY((item)->member.pstNext, type, member))
456
457/*
458 * @ingroup utils_list
459 * @brief iterate over a doubly linked list safe against removal of list entry.
460 *
461 * @par Description:
462 * This API is used to iterate over a doubly linked list safe against removal of list entry.
463 * @attention
464 * <ul>
465 * <li>None.</li>
466 * </ul>
467 *
468 * @param item           [IN] Pointer to the structure that contains the doubly linked list that is to be traversed.
469 * @param next           [IN] Save the next node.
470 * @param list           [IN] Pointer to the doubly linked list to be traversed.
471 * @param type           [IN] Structure name.
472 * @param member         [IN] Member name of the doubly linked list in the structure.
473 *
474 * @retval None.
475 * @par Dependency:
476 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
477 * @see
478 */
479#define UTILS_DL_LIST_FOR_EACH_ENTRY_SAFE(item, next, list, type, member)               \
480    for (item = UTILS_DL_LIST_ENTRY((list)->pstNext, type, member),                     \
481         next = UTILS_DL_LIST_ENTRY((item)->member.pstNext, type, member);              \
482         &(item)->member != (list);                                                   \
483         item = next, next = UTILS_DL_LIST_ENTRY((item)->member.pstNext, type, member))
484
485/*
486 * @ingroup utils_list
487 * @brief Delete initialize a doubly linked list.
488 *
489 * @par Description:
490 * This API is used to delete initialize a doubly linked list.
491 * @attention
492 * <ul>
493 * <li>The parameter passed in should be ensured to be s legal pointer.</li>
494 * </ul>
495 *
496 * @param list    [IN] Doubly linked list.
497 *
498 * @retval None.
499 * @par Dependency:
500 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
501 * @see
502 */
503static inline void UtilsListDelInit(UTILS_DL_LIST *list)
504{
505    list->pstNext->pstPrev = list->pstPrev;
506    list->pstPrev->pstNext = list->pstNext;
507    UtilsListInit(list);
508}
509
510/*
511 * @ingroup utils_list
512 * @brief iterate over a doubly linked list.
513 *
514 * @par Description:
515 * This API is used to iterate over a doubly linked list.
516 * @attention
517 * <ul>
518 * <li>None.</li>
519 * </ul>
520 *
521 * @param item           [IN] Pointer to the structure that contains the doubly linked list that is to be traversed.
522 * @param list           [IN] Pointer to the doubly linked list to be traversed.
523 *
524 * @retval None.
525 * @par Dependency:
526 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
527 * @see
528 */
529#define UTILS_DL_LIST_FOR_EACH(item, list) \
530    for (item = (list)->pstNext;         \
531         (item) != (list);               \
532         item = (item)->pstNext)
533
534/*
535 * @ingroup utils_list
536 * @brief Iterate over a doubly linked list safe against removal of list entry.
537 *
538 * @par Description:
539 * This API is used to iterate over a doubly linked list safe against removal of list entry.
540 * @attention
541 * <ul>
542 * <li>None.</li>
543 * </ul>
544 *
545 * @param item           [IN] Pointer to the structure that contains the doubly linked list that is to be traversed.
546 * @param next           [IN] Save the next node.
547 * @param list           [IN] Pointer to the doubly linked list to be traversed.
548 *
549 * @retval None.
550 * @par Dependency:
551 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
552 * @see
553 */
554#define UTILS_DL_LIST_FOR_EACH_SAFE(item, next, list)      \
555    for (item = (list)->pstNext, next = (item)->pstNext; \
556         (item) != (list);                               \
557         item = next, next = (item)->pstNext)
558
559/*
560 * @ingroup utils_list
561 * @brief Initialize a double linked list.
562 *
563 * @par Description:
564 * This API is used to initialize a double linked list.
565 * @attention
566 * <ul>
567 * <li>None.</li>
568 * </ul>
569 *
570 * @param list           [IN] Pointer to the doubly linked list to be traversed.
571 *
572 * @retval None.
573 * @par Dependency:
574 * <ul><li>utils_list.h: the header file that contains the API declaration.</li></ul>
575 * @see
576 */
577#define UTILS_DL_LIST_HEAD(list) UTILS_DL_LIST list = { &(list), &(list) }
578
579#define UTILS_ListPeekHeadType(list, type, element)                    \
580    do {                                                               \
581        type *__t;                                                     \
582        if ((list)->pstNext == list) {                                 \
583            __t = NULL;                                                \
584        } else {                                                       \
585            __t = UTILS_DL_LIST_ENTRY((list)->pstNext, type, element); \
586        }                                                              \
587        __t;                                                           \
588    } while (0)
589
590#define UTILS_ListRemoveHeadType(list, type, element)                  \
591    do {                                                               \
592        type *__t;                                                     \
593        if ((list)->pstNext == list) {                                 \
594            __t = NULL;                                                \
595        } else {                                                       \
596            __t = UTILS_DL_LIST_ENTRY((list)->pstNext, type, element); \
597            UtilsListDelete((list)->pstNext);                         \
598        }                                                              \
599        __t;                                                           \
600    } while (0)
601
602#define UTILS_ListNextType(list, item, type, element)                  \
603    do {                                                               \
604        type *__t;                                                     \
605        if ((item)->pstNext == list) {                                 \
606            __t = NULL;                                                \
607        } else {                                                       \
608            __t = UTILS_DL_LIST_ENTRY((item)->pstNext, type, element); \
609        }                                                              \
610        __t;                                                           \
611    } while (0)
612
613#ifdef __cplusplus
614#if __cplusplus
615}
616#endif /* __cplusplus */
617#endif /* __cplusplus */
618
619#endif /* _UTILS_LIST_H */