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 22 extern "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 */ 71 typedef 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 */ 88 void 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 */ 97 void 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 */ 106 void 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 */ 118 typedef 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 */ 131 void 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 */ 141 typedef 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 */ 151 ListNode *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 */ 172 int 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 */ 180 typedef 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 */ 189 void 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 */ 197 int 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