1 #pragma once
2 #include <common/stddef.h>
3 
4 #include <asm/asm.h>
5 #include <common/compiler.h>
6 
7 //链表数据结构
8 struct List
9 {
10     struct List *prev, *next;
11 };
12 
13 //初始化循环链表
list_init(struct List * list)14 static inline void list_init(struct List *list)
15 {
16     list->next = list;
17     io_mfence();
18     list->prev = list;
19 }
20 
21 /**
22  * @brief
23 
24  * @param entry 给定的节点
25  * @param node 待插入的节点
26  **/
list_add(struct List * entry,struct List * node)27 static inline void list_add(struct List *entry, struct List *node)
28 {
29 
30     node->next = entry->next;
31     barrier();
32     node->prev = entry;
33     barrier();
34     node->next->prev = node;
35     barrier();
36     entry->next = node;
37 }
38 
39 /**
40  * @brief 将node添加到给定的list的结尾(也就是当前节点的前面)
41  * @param entry 列表的入口
42  * @param node 待添加的节点
43  */
list_append(struct List * entry,struct List * node)44 static inline void list_append(struct List *entry, struct List *node)
45 {
46 
47     struct List *tail = entry->prev;
48     list_add(tail, node);
49 }
50 
51 /**
52  * @brief 从列表中删除节点
53  * @param entry 待删除的节点
54  */
list_del(struct List * entry)55 static inline void list_del(struct List *entry)
56 {
57 
58     entry->next->prev = entry->prev;
59     entry->prev->next = entry->next;
60 }
61 
62 /**
63  * @brief 删除链表的结点，并将这个结点重新初始化
64  *
65  */
66 #define list_del_init(entry) \
67     list_del(entry);         \
68     list_init(entry);
69 
70 /**
71  * @brief 将新的链表结点替换掉旧的链表结点，并使得旧的结点的前后指针均为NULL
72  *
73  * @param old 要被替换的结点
74  * @param new 新的要换上去的结点
75  */
list_replace(struct List * old,struct List * new)76 static inline void list_replace(struct List *old, struct List *new)
77 {
78     if (old->prev != NULL)
79         old->prev->next = new;
80     new->prev = old->prev;
81     if (old->next != NULL)
82         old->next->prev = new;
83     new->next = old->next;
84 
85     old->prev = NULL;
86     old->next = NULL;
87 }
88 
list_empty(struct List * entry)89 static inline bool list_empty(struct List *entry)
90 {
91     /**
92      * @brief 判断循环链表是否为空
93      * @param entry 入口
94      */
95 
96     if (entry == entry->next && entry->prev == entry)
97         return true;
98     else
99         return false;
100 }
101 
102 /**
103  * @brief 获取链表的上一个元素
104  *
105  * @param entry
106  * @return 链表的上一个元素
107  */
list_prev(struct List * entry)108 static inline struct List *list_prev(struct List *entry)
109 {
110     if (entry->prev != NULL)
111         return entry->prev;
112     else
113         return NULL;
114 }
115 
116 /**
117  * @brief 获取链表的下一个元素
118  *
119  * @param entry
120  * @return 链表的下一个元素
121  */
list_next(struct List * entry)122 static inline struct List *list_next(struct List *entry)
123 {
124     if (entry->next != NULL)
125         return entry->next;
126     else
127         return NULL;
128 }
129 
130 /**
131  * @brief 获取当前entry的链表结构体
132  *
133  * @param ptr 指向List结构体的指针
134  * @param type 包裹着List结构体的外层结构体的类型
135  * @param member List结构体在上述的“包裹list结构体的结构体”中的变量名
136  */
137 #define list_entry(ptr, type, member) container_of(ptr, type, member)
138 
139 /**
140  * @brief 获取链表中的第一个元素
141  * 请注意，该宏要求链表非空，否则会出错
142  *
143  * @param ptr 指向链表头的指针
144  * @param type 包裹着List结构体的外层结构体的类型
145  * @param member List结构体在上述的“包裹list结构体的结构体”中的变量名
146  */
147 #define list_first_entry(ptr, type, member) list_entry((ptr)->next, type, member)
148 
149 /**
150  * @brief 获取链表中的第一个元素
151  * 若链表为空，则返回NULL
152  *
153  * @param ptr 指向链表头的指针
154  * @param type 包裹着List结构体的外层结构体的类型
155  * @param member List结构体在上述的“包裹list结构体的结构体”中的变量名
156  */
157 #define list_first_entry_or_null(ptr, type, member) (!list_empty(ptr) ? list_entry((ptr)->next, type, member) : NULL)
158 
159 /**
160  * @brief 获取链表中的最后一个元素
161  * 请注意，该宏要求链表非空，否则会出错
162  *
163  * @param ptr 指向链表头的指针
164  * @param type 包裹着List结构体的外层结构体的类型
165  * @param member List结构体在上述的“包裹list结构体的结构体”中的变量名
166  */
167 #define list_last_entry(ptr, type, member) list_entry((ptr)->prev, type, member)
168 
169 /**
170  * @brief 获取链表中的最后一个元素
171  * 若链表为空，则返回NULL
172  *
173  * @param ptr 指向链表头的指针
174  * @param type 包裹着List结构体的外层结构体的类型
175  * @param member List结构体在上述的“包裹list结构体的结构体”中的变量名
176  */
177 #define list_last_entry_or_full(ptr, type, member) (!list_empty(ptr) ? list_entry((ptr)->prev, type, member) : NULL)
178 
179 /**
180  * @brief 获取链表中的下一个元素
181  *
182  * @param pos 指向当前的外层结构体的指针
183  * @param member 链表结构体在外层结构体内的变量名
184  */
185 #define list_next_entry(pos, member) list_entry((pos)->member.next, typeof(*(pos)), member)
186 
187 /**
188  * @brief 获取链表中的上一个元素
189  *
190  * @param pos 指向当前的外层结构体的指针
191  * @param member 链表结构体在外层结构体内的变量名
192  */
193 #define list_prev_entry(pos, member) list_entry((pos)->member.prev, typeof(*(pos)), member)
194 
195 /**
196  * @brief 遍历整个链表（从前往后）
197  *
198  * @param ptr the &struct list_head to use as a loop cursor.
199  * @param head the head for your list.
200  */
201 #define list_for_each(ptr, head) \
202     for ((ptr) = (head)->next; (ptr) != (head); (ptr) = (ptr)->next)
203 
204 /**
205  * @brief 遍历整个链表（从后往前）
206  *
207  * @param ptr the &struct list_head to use as a loop cursor.
208  * @param head the head for your list.
209  */
210 #define list_for_each_prev(ptr, head) \
211     for ((ptr) = (head)->prev; (ptr) != (head); (ptr) = (ptr)->prev)
212 
213 /**
214  * @brief 遍历整个链表（从前往后）（支持删除当前链表结点）
215  * 该宏通过暂存中间变量，防止在迭代链表的过程中，由于删除了当前ptr所指向的链表结点从而造成错误
216  *
217  * @param ptr the &struct list_head to use as a loop cursor.
218  * @param n 用于存储临时值的List类型的指针
219  * @param head the head for your list.
220  */
221 #define list_for_each_safe(ptr, n, head) \
222     for ((ptr) = (head)->next, (n) = (ptr)->next; (ptr) != (head); (ptr) = n, n = (ptr)->next)
223 
224 /**
225  * @brief 遍历整个链表（从前往后）（支持删除当前链表结点）
226  * 该宏通过暂存中间变量，防止在迭代链表的过程中，由于删除了当前ptr所指向的链表结点从而造成错误
227  *
228  * @param ptr the &struct list_head to use as a loop cursor.
229  * @param n 用于存储临时值的List类型的指针
230  * @param head the head for your list.
231  */
232 #define list_for_each_prev_safe(ptr, n, head) \
233     for ((ptr) = (head)->prev, (n) = (ptr)->prev; (ptr) != (head); (ptr) = n, n = (ptr)->prev)
234 
235 /**
236  * @brief 从头开始迭代给定类型的链表
237  *
238  * @param pos 指向特定类型的结构体的指针
239  * @param head 链表头
240  * @param member struct List在pos的结构体中的成员变量名
241  */
242 #define list_for_each_entry(pos, head, member)               \
243     for (pos = list_first_entry(head, typeof(*pos), member); \
244          &pos->member != (head);                             \
245          pos = list_next_entry(pos, member))
246 
247 /**
248  * @brief 从头开始迭代给定类型的链表（支持删除当前链表结点）
249  *
250  * @param pos 指向特定类型的结构体的指针
251  * @param n 用于存储临时值的，和pos相同类型的指针
252  * @param head 链表头
253  * @param member struct List在pos的结构体中的成员变量名
254  */
255 #define list_for_each_entry_safe(pos, n, head, member)                                         \
256     for (pos = list_first_entry(head, typeof(*pos), member), n = list_next_entry(pos, member); \
257          &pos->member != (head);                                                               \
258          pos = n, n = list_next_entry(n, member))
259 
260 /**
261  * @brief 逆序迭代给定类型的链表
262  *
263  * @param pos 指向特定类型的结构体的指针
264  * @param head 链表头
265  * @param member struct List在pos的结构体中的成员变量名
266  */
267 #define list_for_each_entry_reverse(pos, head, member)      \
268     for (pos = list_last_entry(head, typeof(*pos), member); \
269          &pos->member != (head);                            \
270          pos = list_prev_entry(pos, member))
271 
272 /**
273  * @brief 为list_for_each_entry_continue()准备一个'pos'结构体
274  *
275  * @param pos 指向特定类型的结构体的，用作迭代起点的指针
276  * @param head 指向要开始迭代的struct List结构体的指针
277  * @param member struct List在pos的结构体中的成员变量名
278  */
279 #define list_prepare_entry(pos, head, member) \
280     ((pos) ? pos : list_entry(head, typeof(*pos), member))
281 
282 /**
283  * @brief 从指定的位置的[下一个元素开始],继续迭代给定的链表
284  *
285  * @param pos 指向特定类型的结构体的指针。该指针用作迭代的指针。
286  * @param head 指向链表头的struct List的指针
287  * @param member struct List在pos指向的结构体中的成员变量名
288  */
289 #define list_for_each_entry_continue(pos, head, member) \
290     for (pos = list_next_entry(pos, member);            \
291          &pos->member != (head);                        \
292          pos = list_next_entry(pos, member))
293 
294 /**
295  * @brief 从指定的位置的[下一个元素开始],继续迭代给定的链表。（支持删除当前链表结点）
296  *
297  * @param pos 指向特定类型的结构体的指针。该指针用作迭代的指针。
298  * @param n 用于存储临时值的，和pos相同类型的指针
299  * @param head 指向链表头的struct List的指针
300  * @param member struct List在pos指向的结构体中的成员变量名
301  */
302 #define list_for_each_entry_safe_continue(pos, n, head, member)                \
303     for (pos = list_next_entry(pos, member), n = list_next_entry(pos, member); \
304          &pos->member != (head);                                               \
305          pos = n, n = list_next_entry(n, member))
306 
307 /**
308  * @brief 从指定的位置的[上一个元素开始],【逆序】迭代给定的链表
309  *
310  * @param pos 指向特定类型的结构体的指针。该指针用作迭代的指针。
311  * @param head 指向链表头的struct List的指针
312  * @param member struct List在pos指向的结构体中的成员变量名
313  */
314 #define list_for_each_entry_continue_reverse(pos, head, member) \
315     for (pos = list_prev_entry(pos, member);                    \
316          &pos->member != (head);                                \
317          pos = list_prev_entry(pos, member))
318 
319 /**
320  * @brief 从指定的位置的[上一个元素开始],【逆序】迭代给定的链表。（支持删除当前链表结点）
321  *
322  * @param pos 指向特定类型的结构体的指针。该指针用作迭代的指针。
323  * @param head 指向链表头的struct List的指针
324  * @param member struct List在pos指向的结构体中的成员变量名
325  */
326 #define list_for_each_entry_safe_continue_reverse(pos, n, head, member)        \
327     for (pos = list_prev_entry(pos, member), n = list_prev_entry(pos, member); \
328          &pos->member != (head);                                               \
329          pos = n, n = list_prev_entry(n, member))
330 
331 /**
332  * @brief 从指定的位置开始,继续迭代给定的链表
333  *
334  * @param pos 指向特定类型的结构体的指针。该指针用作迭代的指针。
335  * @param head 指向链表头的struct List的指针
336  * @param member struct List在pos指向的结构体中的成员变量名
337  */
338 #define list_for_each_entry_from(pos, head, member) \
339     for (;                                          \
340          &pos->member != (head);                    \
341          pos = list_next_entry(pos, member))
342 
343 /**
344  * @brief 从指定的位置开始,继续迭代给定的链表.（支持删除当前链表结点）
345  *
346  * @param pos 指向特定类型的结构体的指针。该指针用作迭代的指针。
347  * @param n 用于存储临时值的，和pos相同类型的指针
348  * @param head 指向链表头的struct List的指针
349  * @param member struct List在pos指向的结构体中的成员变量名
350  */
351 #define list_for_each_entry_safe_from(pos, n, head, member) \
352     for (n = list_next_entry(pos, member);                  \
353          &pos->member != (head);                            \
354          pos = n, n = list_next_entry(n, member))
355