1 /*
2 * Copyright (c) 2023 Institute of Parallel And Distributed Systems (IPADS), Shanghai Jiao Tong University (SJTU)
3 * Licensed under the Mulan PSL v2.
4 * You can use this software according to the terms and conditions of the Mulan PSL v2.
5 * You may obtain a copy of Mulan PSL v2 at:
6 * http://license.coscl.org.cn/MulanPSL2
7 * THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND, EITHER EXPRESS OR
8 * IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT, MERCHANTABILITY OR FIT FOR A PARTICULAR
9 * PURPOSE.
10 * See the Mulan PSL v2 for more details.
11 */
12 #ifndef COMMON_LIST_H
13 #define COMMON_LIST_H
14
15 #include <common/macro.h>
16 #include <common/types.h>
17
18 struct list_head {
19 struct list_head *prev;
20 struct list_head *next;
21 };
22
init_list_head(struct list_head * list)23 static inline void init_list_head(struct list_head *list)
24 {
25 list->next = list;
26 list->prev = list;
27 }
28
list_add(struct list_head * new,struct list_head * head)29 static inline void list_add(struct list_head *new, struct list_head *head)
30 {
31 new->next = head->next;
32 new->prev = head;
33 head->next->prev = new;
34 head->next = new;
35 }
36
list_append(struct list_head * new,struct list_head * head)37 static inline void list_append(struct list_head *new, struct list_head *head)
38 {
39 struct list_head *tail = head->prev;
40 return list_add(new, tail);
41 }
42
list_del(struct list_head * node)43 static inline void list_del(struct list_head *node)
44 {
45 node->prev->next = node->next;
46 node->next->prev = node->prev;
47 }
48
list_empty(struct list_head * head)49 static inline bool list_empty(struct list_head *head)
50 {
51 /* When this thing happens, it means someone at the middle of operation */
52 return head->next == head;
53 }
54
55 #define next_container_of_safe(obj, type, field) \
56 ({ \
57 typeof(obj) __obj = (obj); \
58 (__obj ? container_of_safe(((__obj)->field).next, type, field) : \
59 NULL); \
60 })
61
62 #define list_entry(ptr, type, field) container_of(ptr, type, field)
63
64 #define for_each_in_list(elem, type, field, head) \
65 for ((elem) = container_of((head)->next, type, field); \
66 &((elem)->field) != (head); \
67 (elem) = container_of(((elem)->field).next, type, field))
68
69 #define __for_each_in_list_safe(elem, tmp, type, field, head) \
70 for ((elem) = container_of((head)->next, type, field), \
71 (tmp) = next_container_of_safe(elem, type, field); \
72 &((elem)->field) != (head); \
73 (elem) = (tmp), (tmp) = next_container_of_safe(tmp, type, field))
74
75 #define for_each_in_list_safe(elem, tmp, field, head) \
76 __for_each_in_list_safe (elem, tmp, typeof(*(elem)), field, head)
77
78 struct hlist_head {
79 struct hlist_node *next;
80 };
81 struct hlist_node {
82 struct hlist_node *next;
83 struct hlist_node **pprev; /* the field that points to this node */
84 };
85
init_hlist_head(struct hlist_head * head)86 static inline void init_hlist_head(struct hlist_head *head)
87 {
88 head->next = NULL;
89 }
init_hlist_node(struct hlist_node * node)90 static inline void init_hlist_node(struct hlist_node *node)
91 {
92 node->next = NULL;
93 node->pprev = NULL;
94 }
95
hlist_add(struct hlist_node * new,struct hlist_head * head)96 static inline void hlist_add(struct hlist_node *new, struct hlist_head *head)
97 {
98 new->next = head->next;
99 new->pprev = &head->next;
100 if (head->next)
101 head->next->pprev = &new->next;
102 head->next = new;
103 }
104
hlist_del(struct hlist_node * node)105 static inline void hlist_del(struct hlist_node *node)
106 {
107 if (node->next)
108 node->next->pprev = node->pprev;
109 *node->pprev = node->next;
110 }
111
hlist_empty(struct hlist_head * head)112 static inline bool hlist_empty(struct hlist_head *head)
113 {
114 return head->next == NULL;
115 }
116
117 #define hlist_entry(ptr, type, field) container_of(ptr, type, field)
118
119 #define __for_each_in_hlist(elem, type, field, head) \
120 for ((elem) = container_of_safe((head)->next, type, field); elem; \
121 (elem) = (elem) ? \
122 container_of_safe(((elem)->field).next, type, field) : \
123 NULL)
124
125 #define for_each_in_hlist(elem, field, head) \
126 __for_each_in_hlist (elem, typeof(*(elem)), field, head)
127
128 #define __for_each_in_hlist_safe(elem, tmp, type, field, head) \
129 for ((elem) = container_of_safe((head)->next, type, field), \
130 (tmp) = next_container_of_safe(elem, type, field); \
131 elem; \
132 (elem) = (tmp), (tmp) = next_container_of_safe(elem, type, field))
133
134 #define for_each_in_hlist_safe(elem, tmp, field, head) \
135 __for_each_in_hlist_safe (elem, tmp, typeof(*(elem)), field, head)
136
kprint_hlist(struct hlist_head * head)137 static inline void kprint_hlist(struct hlist_head *head)
138 {
139 }
140
141 #endif /* COMMON_LIST_H */
142