1 /*
2 * Copyright (c) 2020-2021 Huawei Device Co., Ltd.
3 *
4 * HDF is dual licensed: you can use it either under the terms of
5 * the GPL, or the BSD license, at your option.
6 * See the LICENSE file in the root of this repository for complete details.
7 */
8 /**
9 * @addtogroup DriverUtils
10 * @{
11 *
12 * @brief Defines common macros and interfaces of the driver module.
13 *
14 * This module provides interfaces such as log printing, doubly linked list operations, and work queues.
15 *
16 * @since 1.0
17 * @version 1.0
18 */
19
20 /**
21 * @file hdf_dlist.h
22 *
23 * @brief Declares doubly linked list structures and interfaces.
24 *
25 * This file provides interfaces such as inserting a node from the head or tail of a doubly linked list,
26 * checking whether a doubly linked list is empty, traversing a doubly linked list, and merging doubly linked lists.
27 *
28 * @since 1.0
29 * @version 1.0
30 */
31
32 #ifndef HDF_LIST_H
33 #define HDF_LIST_H
34
35 #include "hdf_base.h"
36
37 #ifdef __cplusplus
38 extern "C" {
39 #endif /* __cplusplus */
40
41 /**
42 * @brief Describes a doubly linked list.
43 */
44 struct DListHead {
45 struct DListHead *next; /**< Pointer to the next node */
46 struct DListHead *prev; /**< Pointer to the previous node */
47 };
48
49 /**
50 * @brief Initializes a doubly linked list.
51 *
52 * @param head Indicates the pointer to the linked list {@link DListHead}. The parameter cannot be empty.
53 * @since 1.0
54 * @version 1.0
55 */
DListHeadInit(struct DListHead * head)56 static inline void DListHeadInit(struct DListHead *head)
57 {
58 head->next = head;
59 head->prev = head;
60 }
61
62 /**
63 * @brief Checks whether a doubly linked list is empty.
64 *
65 * @param head Indicates the pointer to the linked list {@link DListHead}. The parameter cannot be empty.
66 * @since 1.0
67 * @version 1.0
68 */
DListIsEmpty(const struct DListHead * head)69 static inline bool DListIsEmpty(const struct DListHead *head)
70 {
71 return (head->next == head) ? true : false;
72 }
73 /**
74 * @brief Removes a node from a doubly linked list.
75 *
76 * @param entry Indicates the pointer to the node to remove. For details, see {@link DListHead}.
77 * The parameter cannot be empty.
78 * @since 1.0
79 * @version 1.0
80 */
DListRemove(struct DListHead * entry)81 static inline void DListRemove(struct DListHead *entry)
82 {
83 entry->prev->next = entry->next;
84 entry->next->prev = entry->prev;
85
86 entry->prev = NULL;
87 entry->next = NULL;
88 }
89
90 /**
91 * @brief Inserts a node from the head of a doubly linked list.
92 *
93 * @param entry Indicates the pointer to the node to insert. For details, see {@link DListHead}.
94 * The parameter cannot be empty.
95 * @param head Indicates the pointer to the linked list {@link DListHead}. The parameter cannot be empty.
96 * @since 1.0
97 * @version 1.0
98 */
DListInsertHead(struct DListHead * entry,struct DListHead * head)99 static inline void DListInsertHead(struct DListHead *entry, struct DListHead *head)
100 {
101 entry->next = head->next;
102 entry->prev = head;
103
104 head->next->prev = entry;
105 head->next = entry;
106 }
107
108 /**
109 * @brief Inserts a node from the tail of a doubly linked list.
110 *
111 * @param entry Indicates the pointer to the node to insert. For details, see {@link DListHead}.
112 * The parameter cannot be empty.
113 * @param head Indicates the pointer to the linked list {@link DListHead}. The parameter cannot be empty.
114 * @since 1.0
115 * @version 1.0
116 */
DListInsertTail(struct DListHead * entry,struct DListHead * head)117 static inline void DListInsertTail(struct DListHead *entry, struct DListHead *head)
118 {
119 entry->next = head;
120 entry->prev = head->prev;
121
122 head->prev->next = entry;
123 head->prev = entry;
124 }
125
126 /**
127 * @brief Merges two linked lists by adding the list specified by <b>list</b> to
128 * the head of the list specified by <b>head</b> and initializes the merged list.
129 *
130 * @param list Indicates the pointer to the linked list {@link DListHead}. The parameter cannot be empty.
131 * @param head Indicates the pointer to the linked list {@link DListHead}. The parameter cannot be empty.
132 * @since 1.0
133 * @version 1.0
134 */
DListMerge(struct DListHead * list,struct DListHead * head)135 static inline void DListMerge(struct DListHead *list, struct DListHead *head)
136 {
137 list->next->prev = head;
138 list->prev->next = head->next;
139
140 head->next->prev = list->prev;
141 head->next = list->next;
142
143 DListHeadInit(list);
144 }
145
146 /**
147 * @brief Get the number of elements in the linked list.
148 *
149 * @param head Indicates the pointer to the linked list {@link DListHead}. The parameter cannot be empty.
150 * @since 1.0
151 * @version 1.0
152 */
DListGetCount(const struct DListHead * head)153 static inline int DListGetCount(const struct DListHead *head)
154 {
155 struct DListHead *next = head->next;
156 int count = 0;
157 while (next != head) {
158 next = next->next;
159 count++;
160 }
161 return count;
162 }
163 /**
164 * @brief Obtains the address of a structure variable from its member address.
165 *
166 * @param ptr Indicates the structure member address.
167 * @param type Indicates the structure type.
168 * @param member Indicates the structure member.
169 * @since 1.0
170 * @version 1.0
171 */
172 #define CONTAINER_OF(ptr, type, member) \
173 (type *)((char *)(ptr) - (char *)&((type *)0)->member)
174
175 /**
176 * @brief Obtains the first node of a doubly linked list.
177 *
178 * @param ptr Indicates the structure member address.
179 * @param type Indicates the structure type.
180 * @param member Indicates the structure member.
181 * @since 1.0
182 * @version 1.0
183 */
184 #define DLIST_FIRST_ENTRY(ptr, type, member) \
185 CONTAINER_OF((ptr)->next, type, member)
186
187 /**
188 * @brief Obtains the last node of a doubly linked list.
189 *
190 * @param ptr Indicates the structure member address.
191 * @param type Indicates the structure type.
192 * @param member Indicates the structure member.
193 * @since 1.0
194 * @version 1.0
195 */
196 #define DLIST_LAST_ENTRY(ptr, type, member) \
197 CONTAINER_OF((ptr)->prev, type, member)
198
199 /**
200 * @brief Traverses all nodes in a doubly linked list.
201 *
202 * @param pos Indicates the pointer to the structure variable.
203 * @param head Indicates the pointer to the linked list head.
204 * @param type Indicates the structure type.
205 * @param member Indicates the member type of the structure.
206 * @since 1.0
207 * @version 1.0
208 */
209 #define DLIST_FOR_EACH_ENTRY(pos, head, type, member) \
210 for ((pos) = CONTAINER_OF((head)->next, type, member); \
211 &(pos)->member != (head); \
212 (pos) = CONTAINER_OF((pos)->member.next, type, member))
213
214
215 #define DLIST_FOR_EACH_ENTRY_REVERSE(pos, head, type, member) \
216 for ((pos) = CONTAINER_OF((head)->prev, type, member); \
217 &(pos)->member != (head); \
218 (pos) = CONTAINER_OF((pos)->member.prev, type, member))
219
220 /**
221 * @brief Traverses all nodes in a doubly linked list.
222 * This function is used to delete the nodes pointed to by <b>pos</b> during traversal.
223 *
224 * @param pos Indicates the pointer to the structure variable.
225 * @param tmp Indicates the pointer to the structure variable, pointing to the next node of <b>pos</b>.
226 * @param head Indicates the pointer to the linked list head.
227 * @param type Indicates the structure type.
228 * @param member Indicates the member type of the structure.
229 * @since 1.0
230 * @version 1.0
231 */
232 #define DLIST_FOR_EACH_ENTRY_SAFE(pos, tmp, head, type, member) \
233 for ((pos) = CONTAINER_OF((head)->next, type, member), \
234 (tmp) = CONTAINER_OF((pos)->member.next, type, member); \
235 &(pos)->member != (head); \
236 (pos) = (tmp), (tmp) = CONTAINER_OF((pos)->member.next, type, member))
237
238 #ifdef __cplusplus
239 }
240 #endif /* __cplusplus */
241
242 #endif /* HDF_LIST_H */
243 /** @} */
244