1/*
2 * Copyright (c) 2021 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#ifndef BASE_STARTUP_INITLITE_LIST_H
17#define BASE_STARTUP_INITLITE_LIST_H
18#include <stddef.h>
19
20#ifdef __cplusplus
21#if __cplusplus
22extern "C" {
23#endif
24#endif
25
26/**
27 * @brief Double linked list structure is show as below:
28 *
29 *     |￣￣￣￣￣|-----------------------------------------------|
30 *  |->|  head  |                                               |
31 *  |  |________|<-------------------------------------------|  |
32 *  |   |                                                    |  |
33 *  |   └-next->|▔▔▔▔▔▔|-next->|▔▔▔▔▔▔|-next->|▔▔▔▔▔▔|-next--|  |
34 *  └------prev-| node |<-prev-| node |<-prev-| node |<-prev----|
35 *              |------|       |------|       |------|
36 *              | extra|       | extra|       | extra|
37 *              |______|       |______|       |______|
38 *
39 * Usage Example:
40 * 1. Define structure for each item in the list
41 *   typedef struct tagTEST_LIST_ITEM {
42 *       ListNode node;
43 *       int value;
44 *   } TEST_LIST_ITEM;
45 *
46 * 2. Define a list and init list by OH_ListAddTail
47 *   ListNode testList;
48 *   c(&testList);
49 *
50 * 3. Define a list item instance
51 *   TEST_LIST_ITEM item;
52 *   item.value = 0;
53 *
54 * 4. Add list item to list
55 *   OH_ListAddTail(&testList, (ListNode *)(&item));
56 *
57 * 5. Advanced usage: add with order
58 *   // Ordering compare function
59 *   static int TestListItemCompareProc(ListNode *node, ListNode *newNode)
60 *   {
61 *       TEST_LIST_ITEM *left = (TEST_LIST_ITEM *)node;
62 *       TEST_LIST_ITEM *right = (TEST_LIST_ITEM *)newNode;
63 *       return left->value - right->value;
64 *   }
65 *   OH_ListAddWithOrder(&testList, (ListNode *)(&item))
66 */
67
68/**
69 * @brief Double linked list node
70 */
71typedef struct ListNode {
72    struct ListNode *next;
73    struct ListNode *prev;
74} ListNode, ListHead;
75
76#define ListEmpty(node)   ((node).next == &(node) && (node).prev == &(node))
77#define ListEntry(ptr, type, member)   ((type *)((char *)(ptr) - offsetof(type, member)))
78#define ForEachListEntry(list, node)   for (node = (list)->next; node != (list); node = node->next)
79
80/**
81 * @brief Initialize a double-linked list head
82 *
83 * All other list API should be initialized by this function.\n
84 *
85 * @param head list head, make sure head is valid pointer
86 * @return None
87 */
88void OH_ListInit(struct ListNode *list);
89
90/**
91 * @brief Add a node to the end of the list
92 *
93 * @param head list head, make sure head is valid pointer
94 * @param item new node to be added
95 * @return None
96 */
97void OH_ListAddTail(struct ListNode *list, struct ListNode *item);
98
99/**
100 * @brief Remove a node from the list
101 *
102 * @param item the node to be removed from the list.
103 *             This function does not free any memory within item.
104 * @return None
105 */
106void OH_ListRemove(struct ListNode *item);
107
108/**
109 * @brief ListNode comparison function prototype
110 *
111 * @param node ListNode to be compared.
112 * @param newNode new ListNode to be compared.
113 * @return
114 *     <0 if node < newNode
115 *     =0 if node = newNode
116 *     >0 if Node > newNode
117 */
118typedef int (*ListCompareProc)(ListNode *node, ListNode *newNode);
119
120/**
121 * @brief Add a node to the list with order
122 *
123 * @param head list head, make sure head is valid pointer
124 * @param item new node to be added
125 * @param compareProc comparison function for adding node
126 *      if it is ascending order, this function should return an integer less than,
127 *      equal to, or greater than zero if the first argument is considered to be
128 *      respectively less than, equal to, or greater than the second.
129 * @return None
130 */
131void OH_ListAddWithOrder(struct ListNode *head, struct ListNode *item, ListCompareProc compareProc);
132
133/**
134 * @brief ListNode traversing and find function prototype
135 *
136 * @param node ListNode to be compared.
137 * @param data value for traversing
138 * @return
139 *     return 0 if node value equals data for OH_ListFind
140 */
141typedef int (*ListTraversalProc)(ListNode *node, void *data);
142
143/**
144 * @brief Find a node by traversing the list
145 *
146 * @param head list head, make sure head is valid pointer.
147 * @param data comparing data.
148 * @param compareProc comparing function, return 0 if matched.
149 * @return the found node; return NULL if none is found.
150 */
151ListNode *OH_ListFind(const ListNode *head, void *data, ListTraversalProc compareProc);
152
153/* Traversing from end to start */
154#define TRAVERSE_REVERSE_ORDER   0x1
155/* Stop traversing when error returned */
156#define TRAVERSE_STOP_WHEN_ERROR 0x2
157
158/**
159 * @brief Traversal the list with specified function
160 *
161 * @param head list head, make sure head is valid pointer.
162 * @param cookie optional traversing data.
163 * @param traversalProc comparing function, return 0 if matched.
164 * @param flags optional traversing flags:
165 *  TRAVERSE_REVERSE_ORDER: traversing from last node to first node;
166 *                          default behaviour is from first node to last node
167 *  TRAVERSE_STOP_WHEN_ERROR: stop traversing if traversalProc return non-zero
168 *                          default behaviour will ignore traversalProc return values
169 * @return return -1 for invalid input arguments.
170 *         when TRAVERSE_STOP_WHEN_ERROR is specified, it will return errors from traversalProc
171 */
172int OH_ListTraversal(ListNode *head, void *data, ListTraversalProc traversalProc, unsigned int flags);
173
174/**
175 * @brief ListNode destroy function prototype
176 *
177 * @param node ListNode to be destroyed.
178 * @return None
179 */
180typedef void (*ListDestroyProc)(ListNode *node);
181
182/**
183 * @brief Find a node by traversing the list
184 *
185 * @param head list head, make sure head is valid pointer.
186 * @param destroyProc destroy function; if NULL, it will free each node by default.
187 * @return None
188 */
189void OH_ListRemoveAll(ListNode *head, ListDestroyProc destroyProc);
190
191/**
192 * @brief Get list count
193 *
194 * @param head list head, make sure head is valid pointer.
195 * @return the count of nodes in the list; return 0 if error
196 */
197int OH_ListGetCnt(const ListNode *head);
198
199#ifdef __cplusplus
200#if __cplusplus
201}
202#endif
203#endif
204
205#endif // BASE_STARTUP_INITLITE_LIST_H
206