1 /*
2 * Copyright (C) 2022 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 FILLP_HLIST_H
17 #define FILLP_HLIST_H
18 #include "fillp_os.h"
19 #ifdef __cplusplus
20 extern "C" {
21 #endif
22
23 struct HlistNode {
24 struct HlistNode *next;
25 struct HlistNode **pprev;
26 void *list;
27 };
28
29 struct Hlist {
30 struct HlistNode head;
31 FILLP_UINT32 size;
32 #ifdef FILLP_64BIT_ALIGN
33 FILLP_UINT8 padd[4];
34 #endif
35 };
36
37
38 #define HLIST_INIT(ptr) do { \
39 (ptr)->head.next = FILLP_NULL_PTR; \
40 (ptr)->head.pprev = &((ptr)->head.next); \
41 (ptr)->size = 0; \
42 } while (0)
43 #define HLIST_INIT_NODE(node) do { \
44 (node)->list = FILLP_NULL_PTR; \
45 (node)->next = FILLP_NULL_PTR; \
46 (node)->pprev = FILLP_NULL_PTR; \
47 } while (0)
48 #define HLIST_PREV(ptr) ((struct HlistNode *)(ptr)->pprev)
49 #define HLIST_EMPTY(list) (!((list)->size))
50 #define HLISTNODE_LINKED(_node) ((_node)->pprev != FILLP_NULL_PTR)
51 #define HLIST_FIRST(_list) ((_list)->head.next)
52 #define HLIST_TAIL(_list) (HLIST_EMPTY(_list) ? FILLP_NULL_PTR : HLIST_PREV(&(_list)->head))
53
54 #define HLIST_FOREACH_SAFE(_pos, _next, list) \
55 for ((_pos) = HLIST_FIRST(list); ((_pos) != FILLP_NULL_PTR) && ((_next) = (_pos)->next, FILLP_TRUE); \
56 (_pos) = (_next))
57
58 #define HLIST_FOREACH_AT_SAFE(_pos, _next) \
59 for (; ((_pos) != FILLP_NULL_PTR) && ((_next) = (_pos)->next, FILLP_TRUE); (_pos) = (_next))
60
61 static __inline void HlistDelete(struct Hlist *list, struct HlistNode *n);
62 static void HlistAddAfter(struct Hlist *list, struct HlistNode *prev, struct HlistNode *toBeAdded);
63
64 static struct HlistNode *HlistPopHead(struct Hlist *list);
65
66 static void HlistAddTail(struct Hlist *list, struct HlistNode *node);
67 static void HlistAddHead(struct Hlist *list, struct HlistNode *node);
68
HlistAddAfter(struct Hlist * list,struct HlistNode * prev,struct HlistNode * toBeAdded)69 static __inline void HlistAddAfter(struct Hlist *list, struct HlistNode *prev, struct HlistNode *toBeAdded)
70 {
71 if (prev->next != FILLP_NULL_PTR) {
72 prev->next->pprev = &toBeAdded->next;
73 } else {
74 list->head.pprev = &toBeAdded->next;
75 }
76
77 toBeAdded->next = prev->next;
78 toBeAdded->pprev = &prev->next;
79 prev->next = toBeAdded;
80
81 list->size++;
82
83 toBeAdded->list = (void *)list;
84 }
85
HlistAddTail(struct Hlist * list,struct HlistNode * node)86 static __inline void HlistAddTail(struct Hlist *list, struct HlistNode *node)
87 {
88 HlistAddAfter(list, HLIST_PREV(&list->head), node);
89 return;
90 }
91
HlistAddHead(struct Hlist * list,struct HlistNode * node)92 static __inline void HlistAddHead(struct Hlist *list, struct HlistNode *node)
93 {
94 HlistAddAfter(list, &list->head, node);
95 return;
96 }
97
HlistDelete(struct Hlist * list,struct HlistNode * n)98 void HlistDelete(struct Hlist *list, struct HlistNode *n)
99 {
100 if (n == HLIST_TAIL(list)) {
101 list->head.pprev = n->pprev;
102 }
103
104 HLIST_PREV(n)->next = n->next;
105 if (n->next != FILLP_NULL_PTR) {
106 n->next->pprev = n->pprev;
107 }
108 HLIST_INIT_NODE(n);
109
110 if (list->size > 0) {
111 list->size--;
112 }
113 }
114
HlistDelNode(struct HlistNode * n)115 static __inline void HlistDelNode(struct HlistNode *n)
116 {
117 if (n->list != FILLP_NULL_PTR) {
118 HlistDelete(n->list, n);
119 }
120 }
121
HlistPopHead(struct Hlist * list)122 static __inline struct HlistNode *HlistPopHead(struct Hlist *list)
123 {
124 struct HlistNode *ret = FILLP_NULL_PTR;
125 if (list == FILLP_NULL_PTR) {
126 return FILLP_NULL_PTR;
127 }
128
129 ret = HLIST_FIRST(list);
130 if (ret) {
131 HlistDelete(list, ret);
132 }
133 return ret;
134 }
135
136
137 #ifdef __cplusplus
138 }
139 #endif
140
141 #endif /* FILLP_HLIST_H */
142