1 /*
2 * Copyright (C) 2022 Huawei Technologies Co., Ltd.
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
13 #ifndef LIBTEEOS_DLIST_H
14 #define LIBTEEOS_DLIST_H
15
16 #include <stddef.h>
17 #include <stdbool.h>
18
19 #ifndef array_size
20 #define array_size(a) (sizeof(a) / sizeof((a)[0]))
21 #endif
22
23 #define offset_of(type, member) (unsigned long)(&(((type *)0)->member))
24 #ifndef container_of
25 #define container_of(ptr, type, member) (type *)(((void *)(ptr)) - offset_of(type, member))
26 #endif
27
28 /*
29 * The dlist node structure
30 * representing the head node and the body nodes of the dlist
31 */
32 struct dlist_node {
33 struct dlist_node *prev;
34 struct dlist_node *next;
35 };
36
37 #define dlist_head(name) struct dlist_node name = { &(name), &(name) }
38 #define dlist_head_init(name) { \
39 .next = &(name), \
40 .prev = &(name), \
41 }
42
43 /*
44 * Initialize the empty dlist
45 * PRE: a dlist_node struct for the head node, with unspecified field values
46 * POST: the field set to point to the head node itself, thus initialized to be an empty dlist
47 */
dlist_init(struct dlist_node * head)48 static inline void dlist_init(struct dlist_node *head)
49 {
50 head->prev = head;
51 head->next = head;
52 }
53
54 /*
55 * Check if the dlist is empty
56 * PRE: head points to the head node of a well formed dlist
57 * POST: return 1 if the dlist is empty, return 0 if it is not
58 */
dlist_empty(const struct dlist_node * head)59 static inline bool dlist_empty(const struct dlist_node *head)
60 {
61 /* dlist is well formed, so only needs check the next ptr here */
62 return (head->next == head);
63 }
64
65 /*
66 * Get the first node of a dlist
67 * PRE: head points to the head node of a well formed dlist
68 * POST: return the pointer to the first node of the dlist if it's not empty, or to the head node if it's empty
69 */
dlist_get_first(const struct dlist_node * head)70 static inline struct dlist_node *dlist_get_first(const struct dlist_node *head)
71 {
72 return head->next;
73 }
74
75 /*
76 * Get the last node of a dlist
77 * PRE: head points to the head node of a well formed dlist
78 * POST: return the pointer to the last node of the dlist if it's not empty, or to the head node if it's empty
79 */
dlist_get_last(const struct dlist_node * head)80 static inline struct dlist_node *dlist_get_last(const struct dlist_node *head)
81 {
82 return head->prev;
83 }
84
85 /*
86 * Insert after a given position of the dlist
87 * PRE: pos points to a node(can be the head node) in a well formed dlist, node points to a node to be inserted(not in
88 * the dlist) POST: node has been inserted into the dlist after pos, the new dlist is well formed
89 */
dlist_insert(struct dlist_node * pos,struct dlist_node * node)90 static inline void dlist_insert(struct dlist_node *pos, struct dlist_node *node)
91 {
92 struct dlist_node *tmp = NULL;
93
94 tmp = pos->next;
95 tmp->prev = node;
96 node->prev = pos;
97 node->next = pos->next;
98 pos->next = node;
99 }
100
101 /*
102 * Insert a new node at head of a dlist
103 * PRE: head points to the head node of a well formed dlist, node points to the node to be inserted(not in the dlist)
104 * POST: the new node has been inserted to the head of the dlist, the new dlist is well formed
105 */
dlist_insert_head(struct dlist_node * node,struct dlist_node * head)106 static inline void dlist_insert_head(struct dlist_node *node, struct dlist_node *head)
107 {
108 dlist_insert(head, node);
109 }
110
111 /*
112 * Insert a new node at tail of a dlist
113 * PRE: head points to the head node of a well formed dlist, node points to the node to be inserted(not in the dlist)
114 * POST: the new node has been inserted to the tail of the dlist, the new dlist is well formed
115 */
dlist_insert_tail(struct dlist_node * node,const struct dlist_node * head)116 static inline void dlist_insert_tail(struct dlist_node *node, const struct dlist_node *head)
117 {
118 struct dlist_node *tmp = NULL;
119
120 tmp = dlist_get_last(head);
121 dlist_insert(tmp, node);
122 }
123
124 /*
125 * Delete a node from a dlist
126 * PRE: node points to a node in a well formed dlist
127 * POST: node has been taken out of the dlist, the remaining dlist is still well formed
128 */
dlist_delete(struct dlist_node * node)129 static inline void dlist_delete(struct dlist_node *node)
130 {
131 struct dlist_node *tmp = NULL;
132
133 tmp = node->prev;
134 tmp->next = node->next;
135 tmp = node->next;
136 tmp->prev = node->prev;
137 dlist_init(node);
138 }
139
140 /*
141 * Replace an old node in the dlist with a new node
142 * PRE: old node points to a node in the dlist, new node points a node not in the dlist, dlist well formed
143 * POST: the new node has been inserted into the dlist, the old node has been taken out, the dlist is still well formed
144 */
dlist_replace(const struct dlist_node * old_node,struct dlist_node * new_node)145 static inline void dlist_replace(const struct dlist_node *old_node, struct dlist_node *new_node)
146 {
147 struct dlist_node *tmp = NULL;
148
149 new_node->prev = old_node->prev;
150 new_node->next = old_node->next;
151 tmp = old_node->prev;
152 tmp->next = new_node;
153 tmp = old_node->next;
154 tmp->prev = new_node;
155 }
156
157 /*
158 * Get the prev node of a dlist node or a dlist head
159 * PRE: node points to a dlist head or a dlist node of a well formed dlist
160 * POST: return the pointer to the prev node of the dlist node or the dlist head
161 */
dlist_get_prev(const struct dlist_node * node)162 static inline struct dlist_node *dlist_get_prev(const struct dlist_node *node)
163 {
164 return node->prev;
165 }
166
167 /*
168 * Get the next node of a dlist node or a dlist head
169 * PRE: node points to a dlist head or a dlist node of a well formed dlist
170 * POST: return the pointer to the next node of the dlist node or the dlist head
171 */
dlist_get_next(const struct dlist_node * node)172 static inline struct dlist_node *dlist_get_next(const struct dlist_node *node)
173 {
174 return node->next;
175 }
176
177 /* get the address of the containing struct */
178 #define dlist_entry(ptr, type, member) container_of(ptr, type, member)
179
180 /* dlist_fisrt_entry */
181 #define dlist_first_entry(ptr, type, member) dlist_entry((ptr)->next, type, member)
182
183 /* dlist_last_entry */
184 #define dlist_last_entry(ptr, type, member) dlist_entry((ptr)->prev, type, member)
185
186 /* get the address of the next containing struct on the dlist */
187 #define dlist_next_entry(pos, type, member) dlist_entry((pos)->member.next, type, member)
188
189 /* get the address of the previous containing struct on the dlist */
190 #define dlist_prev_entry(pos, type, member) dlist_entry((pos)->member.prev, type, member)
191
192 /* dlist for each node entry */
193 #define dlist_for_each(pos, head) \
194 for ((pos) = ((head)->next); \
195 (pos) != (head); (pos) = ((pos)->next))
196
197 #define dlist_for_each_prev(pos, head) \
198 for ((pos) = ((head)->prev); \
199 (pos) != (head); (pos) = ((pos)->prev))
200
201 #define dlist_for_each_safe(pos, n, head) \
202 for ((pos) = ((head)->next), (n) = ((pos)->next); \
203 (pos) != (head); \
204 (pos) = (n), (n) = ((pos)->next))
205
206 /* dlist for each struct entry */
207 #define dlist_for_each_entry(pos, head, type, member) \
208 for ((pos) = dlist_first_entry(head, type, member); &((pos)->member) != (head); \
209 pos = dlist_next_entry(pos, type, member))
210
211 #define dlist_for_each_entry_safe(pos, n, head, type, member) \
212 for ((pos) = dlist_first_entry(head, type, member), (n) = dlist_next_entry(pos, type, member); \
213 (&(pos)->member != (head)); (pos) = (n), (n) = dlist_next_entry(n, type, member))
214
215 #endif