1 /**
2 * @file cstl_rawlist.c
3 * @copyright Copyright (c) Huawei Technologies Co., Ltd. 2021-2021. All rights reserved.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15
16 * @brief raw_list 实现
17 * @details raw_list源码
18 * @date 2021-04-15
19 * @version v0.1.0
20 * *******************************************************************************************
21 * @par 修改日志：
22 * <table>
23 * <tr><th>Date <th>Version <th>Author <th>Description
24 * </table>
25 * *******************************************************************************************
26 * @par 修改日志：
27 * <table>
28 * <tr><th>Date <th>Version <th>Author <th>Description
29 * </table>
30 * *******************************************************************************************
31 */
32
33 #include <stdlib.h>
34 #include "cstl_public_inner.h"
35 #include "cstl_rawlist.h"
36
37 #ifdef __cplusplus
38 extern "C" {
39 #endif
40
41 /* 内部函数定义 */
CstlRawListNodeInList(const CstlRawListNode * node)42 CSTL_STATIC inline bool CstlRawListNodeInList(const CstlRawListNode *node)
43 {
44 bool ret = false;
45
46 if ((node->next != NULL) && (node->prev != NULL) &&
47 ((const CstlRawListNode *)(node->next->prev) == node) &&
48 ((const CstlRawListNode *)(node->prev->next) == node)) {
49 ret = true;
50 }
51
52 return ret;
53 }
54
CstlRawListEmptyCheck(const CstlRawList * list)55 CSTL_STATIC inline bool CstlRawListEmptyCheck(const CstlRawList *list)
56 {
57 return (&list->head)->next == &list->head;
58 }
59
CstlRawListAddAfterNode(CstlRawListNode * node,CstlRawListNode * where)60 CSTL_STATIC inline void CstlRawListAddAfterNode(CstlRawListNode *node, CstlRawListNode *where)
61 {
62 node->next = (where)->next;
63 node->prev = (where);
64 where->next = node;
65 node->next->prev = node;
66 }
67
CstlRawListAddBeforeNode(CstlRawListNode * node,const CstlRawListNode * where)68 CSTL_STATIC inline void CstlRawListAddBeforeNode(CstlRawListNode *node, const CstlRawListNode *where)
69 {
70 CstlRawListAddAfterNode(node, where->prev);
71 }
72
CstlRawListIsFirstNode(const CstlRawList * list,const CstlRawListNode * node)73 CSTL_STATIC inline bool CstlRawListIsFirstNode(const CstlRawList *list, const CstlRawListNode *node)
74 {
75 bool ret = false;
76
77 if ((const CstlRawListNode *)list->head.next == node) {
78 ret = true;
79 }
80
81 return ret;
82 }
83
CstlRawListIsLastNode(const CstlRawList * list,const CstlRawListNode * node)84 CSTL_STATIC inline bool CstlRawListIsLastNode(const CstlRawList *list, const CstlRawListNode *node)
85 {
86 bool ret = false;
87
88 if ((const CstlRawListNode *)list->head.prev == node) {
89 ret = true;
90 }
91
92 return ret;
93 }
94
95 /* 删除链表节点，内部函数，不做入参校验 */
CstlRawListRemoveNode(CstlRawList * list,CstlRawListNode * node)96 CSTL_STATIC void CstlRawListRemoveNode(CstlRawList *list, CstlRawListNode *node)
97 {
98 node->prev->next = node->next;
99 node->next->prev = node->prev;
100
101 if (list->freeFunc != NULL) {
102 list->freeFunc((void *)node);
103 }
104 }
105
CstlRawListInit(CstlRawList * list,CstlFreeFunc freeFunc)106 __attribute__((visibility("default"))) int32_t CstlRawListInit(
107 CstlRawList *list, CstlFreeFunc freeFunc)
108 {
109 int32_t ret = (int32_t)ERRNO_CSTL_INPUT_INVALID;
110
111 if (list != NULL) {
112 list->head.next = &list->head;
113 list->head.prev = &list->head;
114 list->freeFunc = freeFunc;
115 ret = CSTL_OK;
116 }
117
118 return ret;
119 }
120
CstlRawListClear(CstlRawList * list)121 __attribute__((visibility("default"))) int32_t CstlRawListClear(
122 CstlRawList *list)
123 {
124 int32_t ret = (int32_t)ERRNO_CSTL_INPUT_INVALID;
125
126 if (list != NULL) {
127 while (!CstlRawListEmptyCheck(list)) {
128 CstlRawListRemoveNode(list, (CstlRawListNode *)list->head.next);
129 }
130
131 ret = CSTL_OK;
132 }
133
134 return ret;
135 }
136
CstlRawListDeinit(CstlRawList * list)137 __attribute__((visibility("default"))) int32_t CstlRawListDeinit(
138 CstlRawList *list)
139 {
140 int32_t ret = (int32_t)ERRNO_CSTL_INPUT_INVALID;
141
142 if (list != NULL) {
143 ret = CstlRawListClear(list);
144 list->freeFunc = NULL;
145 }
146
147 return ret;
148 }
149
CstlRawListEmpty(const CstlRawList * list)150 __attribute__((visibility("default"))) bool CstlRawListEmpty(
151 const CstlRawList *list)
152 {
153 bool ret = true;
154
155 if (list != NULL) {
156 ret = CstlRawListEmptyCheck(list);
157 }
158
159 return ret;
160 }
161
CstlRawListSizeInner(const CstlRawList * list)162 CSTL_STATIC inline size_t CstlRawListSizeInner(const CstlRawList *list)
163 {
164 size_t size = 0;
165 const CstlRawListNode *node, *head;
166
167 head = &list->head;
168 for (node = head->next; node != head; node = node->next) {
169 size++;
170 }
171
172 return size;
173 }
174
CstlRawListSize(const CstlRawList * list)175 __attribute__((visibility("default"))) size_t CstlRawListSize(
176 const CstlRawList *list)
177 {
178 size_t size = 0;
179
180 if ((list != NULL) && !CstlRawListEmptyCheck(list)) {
181 size = CstlRawListSizeInner(list);
182 }
183
184 return size;
185 }
186
CstlRawListPushFront(CstlRawList * list,CstlRawListNode * node)187 __attribute__((visibility("default"))) int32_t CstlRawListPushFront(
188 CstlRawList *list, CstlRawListNode *node)
189 {
190 int32_t ret = (int32_t)ERRNO_CSTL_INPUT_INVALID;
191
192 if ((list != NULL) && (node != NULL)) {
193 CstlRawListAddAfterNode(node, &(list->head));
194 ret = CSTL_OK;
195 }
196
197 return ret;
198 }
199
CstlRawListPushBack(CstlRawList * list,CstlRawListNode * node)200 __attribute__((visibility("default"))) int32_t CstlRawListPushBack(
201 CstlRawList *list, CstlRawListNode *node)
202 {
203 int32_t ret = (int32_t)ERRNO_CSTL_INPUT_INVALID;
204
205 if ((list != NULL) && (node != NULL)) {
206 CstlRawListAddBeforeNode(node, &(list->head));
207 ret = CSTL_OK;
208 }
209
210 return ret;
211 }
212
CstlRawListInsert(const CstlRawListNode * curNode,CstlRawListNode * newNode)213 __attribute__((visibility("default"))) int32_t CstlRawListInsert(
214 const CstlRawListNode *curNode, CstlRawListNode *newNode)
215 {
216 int32_t ret = (int32_t)ERRNO_CSTL_INPUT_INVALID;
217
218 if ((curNode != NULL) && (newNode != NULL) && (CstlRawListNodeInList(curNode))) {
219 CstlRawListAddBeforeNode(newNode, curNode);
220 ret = CSTL_OK;
221 }
222
223 return ret;
224 }
225
CstlRawListPopFront(CstlRawList * list)226 __attribute__((visibility("default"))) int32_t CstlRawListPopFront(
227 CstlRawList *list)
228 {
229 int32_t ret = (int32_t)ERRNO_CSTL_INPUT_INVALID;
230 CstlRawListNode *firstNode;
231
232 if ((list != NULL) && (!CstlRawListEmptyCheck(list))) {
233 firstNode = list->head.next;
234 CstlRawListRemoveNode(list, firstNode);
235 ret = CSTL_OK;
236 }
237
238 return ret;
239 }
240
CstlRawListPopBack(CstlRawList * list)241 __attribute__((visibility("default"))) int32_t CstlRawListPopBack(
242 CstlRawList *list)
243 {
244 int32_t ret = (int32_t)ERRNO_CSTL_INPUT_INVALID;
245 CstlRawListNode *lastNode;
246
247 if (list != NULL) {
248 if (!CstlRawListEmptyCheck(list)) {
249 lastNode = list->head.prev;
250 CstlRawListRemoveNode(list, lastNode);
251 ret = CSTL_OK;
252 } else {
253 ret = (int32_t)ERRNO_CSTL_ELEMENT_EMPTY;
254 }
255 }
256
257 return ret;
258 }
259
CstlRawListEraseInner(CstlRawList * list,CstlRawListNode * node)260 CSTL_STATIC void CstlRawListEraseInner(CstlRawList *list, CstlRawListNode *node)
261 {
262 node->prev->next = node->next;
263 node->next->prev = node->prev;
264
265 if ((list != NULL) && !CstlRawListEmptyCheck(list) && (list->freeFunc != NULL)) {
266 list->freeFunc((void *)node);
267 }
268 }
269
CstlRawListErase(CstlRawList * list,CstlRawListNode * node)270 __attribute__((visibility("default"))) int32_t CstlRawListErase(
271 CstlRawList *list, CstlRawListNode *node)
272 {
273 int32_t ret = (int32_t)ERRNO_CSTL_INPUT_INVALID;
274
275 if ((node != NULL) && (CstlRawListNodeInList(node))) {
276 CstlRawListEraseInner(list, node);
277 ret = CSTL_OK;
278 }
279
280 return ret;
281 }
282
CstlRawListFront(const CstlRawList * list)283 __attribute__((visibility("default"))) CstlRawListNode *CstlRawListFront(
284 const CstlRawList *list)
285 {
286 CstlRawListNode *front = NULL;
287
288 if ((list != NULL) && (!CstlRawListEmptyCheck(list))) {
289 front = list->head.next;
290 }
291
292 return front;
293 }
294
CstlRawListBack(const CstlRawList * list)295 __attribute__((visibility("default"))) CstlRawListNode *CstlRawListBack(
296 const CstlRawList *list)
297 {
298 CstlRawListNode *back = NULL;
299
300 if ((list != NULL) && (!CstlRawListEmptyCheck(list))) {
301 back = list->head.prev;
302 }
303
304 return back;
305 }
306
CstlRawListPrev(const CstlRawList * list,const CstlRawListNode * node)307 __attribute__((visibility("default"))) CstlRawListNode *CstlRawListPrev(
308 const CstlRawList *list, const CstlRawListNode *node)
309 {
310 CstlRawListNode *prev;
311
312 if ((list == NULL) || (node == NULL) ||
313 (CstlRawListEmptyCheck(list)) || (CstlRawListIsFirstNode(list, node)) || (!CstlRawListNodeInList(node))) {
314 prev = NULL;
315 } else {
316 prev = node->prev;
317 }
318
319 return prev;
320 }
321
CstlRawListNext(const CstlRawList * list,const CstlRawListNode * node)322 __attribute__((visibility("default"))) CstlRawListNode *CstlRawListNext(
323 const CstlRawList *list, const CstlRawListNode *node)
324 {
325 CstlRawListNode *next;
326
327 if ((list == NULL) || (node == NULL) ||
328 (CstlRawListEmptyCheck(list)) || (CstlRawListIsLastNode(list, node)) || (!CstlRawListNodeInList(node))) {
329 next = NULL;
330 } else {
331 next = node->next;
332 }
333
334 return next;
335 }
336
CstlRawListSortInner(CstlRawList * list,CstlDataCmpFunc cmpFunc)337 CSTL_STATIC void CstlRawListSortInner(CstlRawList *list, CstlDataCmpFunc cmpFunc)
338 {
339 ssize_t i, j;
340 ssize_t count;
341 int32_t cmpResult;
342 CstlRawListNode *node;
343 CstlRawListNode *nextNode;
344
345 count = (ssize_t)CstlRawListSizeInner(list);
346 for (i = 0; i < (count - 1); ++i) {
347 node = CstlRawListFront(list);
348 for (j = 0; j < (count - i - 1); ++j) {
349 nextNode = node->next;
350 cmpResult = cmpFunc(node, nextNode);
351 if (cmpResult > 0) {
352 node->prev->next = nextNode;
353 nextNode->prev = node->prev;
354
355 node->prev = nextNode;
356 node->next = nextNode->next;
357 nextNode->next->prev = node;
358 nextNode->next = node;
359
360 continue;
361 }
362 node = node->next;
363 }
364 }
365 }
366
367 /* 链表排序函数，此处函数钩子cmpFunc的两个入参，类型需由用户保证是（CstlRawListNode *） */
CstlRawListSort(CstlRawList * list,CstlDataCmpFunc cmpFunc)368 __attribute__((visibility("default"))) int32_t CstlRawListSort(
369 CstlRawList *list, CstlDataCmpFunc cmpFunc)
370 {
371 int32_t ret = (int32_t)ERRNO_CSTL_INPUT_INVALID;
372
373 if ((list != NULL) && (cmpFunc != NULL)) {
374 CstlRawListSortInner(list, cmpFunc);
375 ret = CSTL_OK;
376 }
377
378 return ret;
379 }
380
381 /* 链表节点查找函数，此处函数钩子nodeMatchFunc的第一个入参，类型需由用户保证是（CstlRawListNode *） */
CstlRawListNodeFind(const CstlRawList * list,CstlMatchFunc nodeMatchFunc,uintptr_t data)382 __attribute__((visibility("default"))) CstlRawListNode *CstlRawListNodeFind(
383 const CstlRawList *list, CstlMatchFunc nodeMatchFunc, uintptr_t data)
384 {
385 CstlRawListNode *ans = NULL;
386 CstlRawListNode *node;
387 const CstlRawListNode *head;
388
389 if ((list != NULL) && (nodeMatchFunc != NULL)) {
390 head = (const CstlRawListNode *)(&list->head);
391 node = head->next;
392 while ((const CstlRawListNode *)node != head) {
393 if (nodeMatchFunc((void *)node, data)) {
394 ans = node;
395 break;
396 }
397 node = node->next;
398 }
399 }
400
401 return ans;
402 }
403
404 #ifdef __cplusplus
405 }
406 #endif
407