1 /*
2 * Copyright (C) 2021 HiSilicon (Shanghai) Technologies CO., LIMITED.
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License
6 * as published by the Free Software Foundation; either version 2
7 * of the License, or (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17 */
18 #ifndef __HI_LIST_H__
19 #define __HI_LIST_H__
20
21 #include <hi_types_base.h>
22
23 /* ************************************************************************** */
24 HI_START_HEADER
25
26 /*
27 * 备注：本文件对链表接口重新命名，使用LTOS接口重新实现。
28 */
29 typedef struct hi_list {
30 struct hi_list *prev;
31 struct hi_list *next;
32 } hi_list;
33
34 /*
35 功能描述：
36 初始化头节点，注意此节点仅用于管理，不是用户输入的数据节点
37 */
hi_list_init(hi_list * list)38 static inline hi_void hi_list_init(hi_list *list)
39 {
40 list->next = list;
41 list->prev = list;
42 }
43
44 /*
45 功能描述：
46 把node插入为list的第一个节点
47 */
hi_list_head_insert(hi_list * node,hi_list * list)48 static inline hi_void hi_list_head_insert(hi_list *node, hi_list *list)
49 {
50 node->next = list->next;
51 node->prev = list;
52 list->next->prev = node;
53 list->next = node;
54 }
55
56 /*
57 功能描述：
58 把node插入为list的第一个节点
59 */
hi_list_head_insert_optimize(hi_list * node,hi_list * list)60 __attribute__((always_inline)) static inline hi_void hi_list_head_insert_optimize(hi_list *node, hi_list *list)
61 {
62 node->next = list->next;
63 node->prev = list;
64 list->next->prev = node;
65 list->next = node;
66 }
67
68 /*
69 功能描述：
70 把node插入为list的最后一个节点
71 */
hi_list_tail_insert(hi_list * node,hi_list * list)72 static inline hi_void hi_list_tail_insert(hi_list *node, hi_list *list)
73 {
74 hi_list_head_insert(node, list->prev);
75 }
76
77 /*
78 功能描述：
79 把node插入为list的最后一个节点
80 */
hi_list_tail_insert_optimize(hi_list * node,hi_list * list)81 __attribute__((always_inline)) static inline hi_void hi_list_tail_insert_optimize(hi_list *node, hi_list *list)
82 {
83 hi_list_head_insert_optimize(node, list->prev);
84 }
85
86 /*
87 功能描述：
88 从链表中删除某个节点
89 */
hi_list_delete(hi_list * node)90 static inline hi_void hi_list_delete(hi_list *node)
91 {
92 if (node->next == HI_NULL || node->prev == HI_NULL) {
93 return;
94 }
95
96 node->next->prev = node->prev;
97 node->prev->next = node->next;
98 node->next = (hi_list *)HI_NULL;
99 node->prev = (hi_list *)HI_NULL;
100 }
101
102 /*
103 功能描述：
104 从链表中删除某个节点
105 */
hi_list_delete_optimize(hi_list * node)106 __attribute__((always_inline)) static inline hi_void hi_list_delete_optimize(hi_list *node)
107 {
108 if (node->next == HI_NULL || node->prev == HI_NULL) {
109 return;
110 }
111
112 node->next->prev = node->prev;
113 node->prev->next = node->next;
114 node->next = (hi_list *)HI_NULL;
115 node->prev = (hi_list *)HI_NULL;
116 }
117
118 /*
119 功能描述：
120 删除链表的第一个节点，不释放相关内存
121 */
hi_list_delete_head(hi_list * list)122 static inline hi_list *hi_list_delete_head(hi_list *list)
123 {
124 hi_list *del_node;
125
126 del_node = list->next;
127 if (del_node == list || del_node == HI_NULL) {
128 return HI_NULL;
129 }
130
131 hi_list_delete(del_node);
132 return del_node;
133 }
134
135 /*
136 功能描述：
137 删除链表的第一个节点，不释放相关内存
138 */
hi_list_delete_head_optimize(hi_list * list)139 __attribute__((always_inline)) static inline hi_list *hi_list_delete_head_optimize(hi_list *list)
140 {
141 hi_list *del_node;
142
143 del_node = list->next;
144 if (del_node == list || del_node == HI_NULL) {
145 return HI_NULL;
146 }
147
148 hi_list_delete_optimize(del_node);
149 return del_node;
150 }
151
152 /*
153 功能描述：
154 删除链表尾部节点，不释放相关内存
155 */
hi_list_delete_tail(hi_list * list)156 static inline hi_list *hi_list_delete_tail(hi_list *list)
157 {
158 hi_list *del_node;
159
160 del_node = list->prev;
161 if (del_node == list || del_node == HI_NULL) {
162 return HI_NULL;
163 }
164
165 hi_list_delete(del_node);
166 return del_node;
167 }
168
169 /*
170 功能描述：
171 判断链表是否为空
172 */
hi_is_list_empty(hi_list * list)173 static inline hi_bool hi_is_list_empty(hi_list *list)
174 {
175 if (list->next == HI_NULL || list->prev == HI_NULL) {
176 return HI_TRUE;
177 }
178 return (hi_bool)(list->next == list);
179 }
180
hi_is_list_empty_optimize(hi_list * list)181 __attribute__((always_inline)) static inline hi_bool hi_is_list_empty_optimize(hi_list *list)
182 {
183 if (list->next == HI_NULL || list->prev == HI_NULL) {
184 return HI_TRUE;
185 }
186 return (hi_bool)(list->next == list);
187 }
188
189
190 /*
191 功能描述：
192 去初始化链表，管理节点清空，其他成员节点首尾相连仍然是一个双向链表。
193 */
hi_list_del_init(hi_list * list)194 static inline hi_void hi_list_del_init(hi_list *list)
195 {
196 list->next->prev = list->prev;
197 list->prev->next = list->next;
198
199 list->next = list;
200 list->prev = list;
201 }
202
203 /*
204 功能描述：
205 将链表2加入链表1的尾部
206 */
hi_list_join_tail(hi_list * list1,hi_list * list2)207 static inline hi_void hi_list_join_tail(hi_list *list1, hi_list *list2)
208 {
209 list1->prev->next = list2->next;
210 list2->next->prev = list1->prev;
211 list2->prev->next = list1;
212 list1->prev = list2->prev;
213 }
214
215 /*
216 功能描述：
217 将链表2加入链表1的头部
218 */
hi_list_join_head(hi_list * list1,hi_list * list2)219 static inline hi_void hi_list_join_head(hi_list *list1, hi_list *list2)
220 {
221 /* list2 is empty. */
222 if (list2->next == list2) {
223 return;
224 }
225
226 list2->prev->next = list1->next;
227 list1->next->prev = list2->prev;
228 list1->next = list2->next;
229 list2->next->prev = list1;
230 }
231
232 /*
233 * 功能描述：
234 将链表2中从第一个元素到last_node元素摘出， 加入空链表1的头部
235 */
hi_list_remove_head(hi_list * list1,hi_list * list2,hi_list * last_node)236 static inline hi_void hi_list_remove_head(hi_list *list1, hi_list *list2, hi_list *last_node)
237 {
238 /* 对list1赋值 */
239 list1->next = list2->next;
240 list1->prev = last_node;
241
242 list2->next = last_node->next;
243 ((hi_list *)(last_node->next))->prev = list2;
244
245 last_node->next = list1;
246 /* last_node为list2中第一个成员 */
247 if (last_node->prev == list2) {
248 last_node->prev = list1;
249 }
250 }
251
252 #define hi_list_init_macro(_list_name) hi_list _list_name = { (hi_list *)&(_list_name), (hi_list *)&(_list_name) }
253
254 /* 获取第一个节点指针 */
255 #define hi_list_first(object) ((object)->next)
256
257 /* 获取最后一个节点指针 */
258 #define hi_list_last(object) ((object)->prev)
259
260 /*
261 * 功能描述：
262 获取到一个包含双链表的结构体的指针地址。
263 */
264 #define hi_list_entry(item, type, member) ((type *)((char *)(item)-hi_offset_of_member(type, member)))
265
266 /*
267 * 功能列表：
268 通过LIST遍历每一个成员节点所在结构体的指针入口地址。
269 */
270 #define hi_list_for_each_entry(item, list, type, member) \
271 for ((item) = hi_list_entry((list)->next, type, member); &(item)->member != (list); \
272 (item) = hi_list_entry((item)->member.next, type, member))
273
274 /*
275 * 功能列表：
276 通过LIST遍历每一个成员节点所在结构体的指针入口地址，保存下一个节点的指针，避免当前节点处理完成后删除的场景。
277 */
278 #define hi_list_for_each_entry_safe(list, item, pnext, type, member) \
279 for ((item) = hi_list_entry((list)->next, type, member), \
280 (pnext) = hi_list_entry((item)->member.next, type, member); \
281 &(item)->member != (list); (item) = (pnext), (pnext) = hi_list_entry((item)->member.next, type, member))
282
283 #define hi_list_for_each_entry_continue_safe(pitem, list, item, pnext, type, member) \
284 for ((item) = hi_list_entry((pitem)->next, type, member), \
285 (pnext) = hi_list_entry((item)->member.next, type, member); \
286 &((item)->member) != (list); (item) = (pnext), (pnext) = hi_list_entry((pnext)->member.next, type, member))
287
288 /* 双向链表操作简单实现 */
289 #define hi_list_head(list) hi_list list = { &(list), &(list) }
290
291 #define hi_list_for_each(item, list) for ((item) = (list)->next; (item) != (list); (item) = (item)->next)
292
293 #define hi_list_for_each_safe(item, pnext, list) \
294 for ((item) = (list)->next, (pnext) = (item)->next; (item) != (list); (item) = (pnext), (pnext) = (item)->next)
295
296 HI_END_HEADER
297 #endif /* __HI_STDLIB_H__ */
298