VLC  4.0.0-dev
vlc_list.h
Go to the documentation of this file.
1 /******************************************************************************
2  * vlc_list.h
3  ******************************************************************************
4  * Copyright © 2018 Rémi Denis-Courmont
5  *
6  * This program is free software; you can redistribute it and/or modify it
7  * under the terms of the GNU Lesser General Public License as published by
8  * the Free Software Foundation; either version 2.1 of the License, or
9  * (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14  * GNU Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public License
17  * along with this program; if not, write to the Free Software Foundation,
18  * Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA.
19  *****************************************************************************/
20 
21 #ifndef VLC_LIST_H
22 # define VLC_LIST_H 1
23 
24 # include <stdalign.h>
25 # include <stdbool.h>
26 
27 /**
28  * \defgroup list Linked lists
29  * \ingroup cext
30  * @{
31  * \file
32  * This provides convenience helpers for linked lists.
33  */
34 
35 /**
36  * Doubly-linked list node.
37  *
38  * This data structure provides a doubly-linked list node.
39  * It must be embedded in each member of a list as a node proper.
40  * It also serves as a list head in the object containing the list.
41  */
42 struct vlc_list
43 {
44  struct vlc_list *prev;
45  struct vlc_list *next;
46 };
47 
48 /**
49  * Static initializer for a list head.
50  */
51 #define VLC_LIST_INITIALIZER(h) { h, h }
52 
53 /**
54  * Initializes an empty list head.
55  */
56 static inline void vlc_list_init(struct vlc_list *restrict head)
57 {
58  head->prev = head;
59  head->next = head;
60 }
61 
62 /**
63  * Inserts an element in a list.
64  *
65  * \param node Node pointer of the element to insert [OUT].
66  * \param prev Node pointer of the previous element.
67  * \param next Node pointer of the next element.
68  */
69 static inline void vlc_list_add_between(struct vlc_list *restrict node,
70  struct vlc_list *prev,
71  struct vlc_list *next)
72 {
73  node->prev = prev;
74  node->next = next;
75  prev->next = node;
76  next->prev = node;
77 }
78 
79 /**
80  * Inserts an element after another.
81  *
82  * \param node Node pointer of the element to insert [OUT].
83  * \param prev Node pointer of the previous element.
84  */
85 static inline void vlc_list_add_after(struct vlc_list *restrict node,
86  struct vlc_list *prev)
87 {
89 }
90 
91 /**
92  * Inserts an element before another.
93  *
94  * \param node Node pointer of the element to insert [OUT].
95  * \param next Node pointer of the next element.
96  */
97 static inline void vlc_list_add_before(struct vlc_list *restrict node,
98  struct vlc_list *next)
99 {
101 }
102 
103 /**
104  * Appends an element into a list.
105  *
106  * \param node Node pointer of the element to append to the list [OUT].
107  * \param head Head pointer of the list to append the element to.
108  */
109 static inline void vlc_list_append(struct vlc_list *restrict node,
110  struct vlc_list *head)
111 {
112  vlc_list_add_before(node, head);
113 }
114 
115 /**
116  * Prepends an element into a list.
117  *
118  * \param node Node pointer of the element to prepend to the list [OUT].
119  * \param head Head pointer of the list to prepend the element to.
120  */
121 static inline void vlc_list_prepend(struct vlc_list *restrict node,
122  struct vlc_list *head)
123 {
124  vlc_list_add_after(node, head);
125 }
126 
127 /**
128  * Removes an element from a list.
129  *
130  * \param node Node of the element to remove from a list.
131  * \warning The element must be inside a list.
132  * Otherwise the behaviour is undefined.
133  */
134 static inline void vlc_list_remove(struct vlc_list *restrict node)
135 {
136  struct vlc_list *prev = node->prev;
137  struct vlc_list *next = node->next;
138 
139  prev->next = next;
140  next->prev = prev;
141 }
142 
143 /**
144  * Replaces an element with another one.
145  *
146  * \param original Node pointer of the element to remove from the list [IN].
147  * \param substitute Node pointer of the replacement [OUT].
148  */
149 static inline void vlc_list_replace(const struct vlc_list *original,
150  struct vlc_list *restrict substitute)
151 {
152  vlc_list_add_between(substitute, original->prev, original->next);
153 }
154 
155 /**
156  * Checks if a list is empty.
157  *
158  * \param head Head of the list to be checked [IN].
159  *
160  * \retval false The list is not empty.
161  * \retval true The list is empty.
162  *
163  * \note Obviously the list must have been initialized.
164  * Otherwise, the behaviour is undefined.
165  */
166 static inline bool vlc_list_is_empty(const struct vlc_list *head)
167 {
168  return head->next == head;
169 }
170 
171 /**
172  * Checks if an element is first in a list.
173  *
174  * \param node List node of the element [IN].
175  * \param head Head of the list to be checked [IN].
176  *
177  * \retval false The element is not first (or is in another list).
178  * \retval true The element is first.
179  */
180 static inline bool vlc_list_is_first(const struct vlc_list *node,
181  const struct vlc_list *head)
182 {
183  return node->prev == head;
184 }
185 
186 /**
187  * Checks if an element is last in a list.
188  *
189  * \param node List node of the element [IN].
190  * \param head Head of the list to be checked [IN].
191  *
192  * \retval false The element is not last (or is in another list).
193  * \retval true The element is last.
194  */
195 static inline bool vlc_list_is_last(const struct vlc_list *node,
196  const struct vlc_list *head)
197 {
198  return node->next == head;
199 }
200 
201 /**
202  * List iterator.
203  */
204 struct vlc_list_it
205 {
206  const struct vlc_list *head;
207  struct vlc_list *current;
208  struct vlc_list *next;
209 };
210 
211 static inline
212 struct vlc_list_it vlc_list_it_start(const struct vlc_list *head)
213 {
214  struct vlc_list *first = head->next;
215 
216  struct vlc_list_it it = { head, first, first->next };
217  return it;
218 }
219 
220 static inline bool vlc_list_it_continue(const struct vlc_list_it *restrict it)
221 {
222  return it->current != it->head;
223 }
224 
225 static inline void vlc_list_it_next(struct vlc_list_it *restrict it)
226 {
227  struct vlc_list *next = it->next;
228 
229  it->current = next;
230  it->next = next->next;
231 }
232 
233 #define vlc_list_entry_aligned_size(p) \
234  ((sizeof (*(p)) + sizeof (max_align_t) - 1) / sizeof (max_align_t))
235 
236 #define vlc_list_entry_dummy(p) \
237  (0 ? (p) : ((void *)( \
238  &(max_align_t[vlc_list_entry_aligned_size(p)]){ (max_align_t){0} } \
239  )))
240 
241 #define vlc_list_offset_p(p, member) \
242  ((p) = vlc_list_entry_dummy(p), (char *)(&(p)->member) - (char *)(p))
243 
244 #define vlc_list_entry_p(node, p, member) \
245  (0 ? (p) : (void *)(((char *)(node)) - vlc_list_offset_p(p, member)))
246 
247 /**
248  * List iteration macro.
249  *
250  * This macro iterates over all elements (excluding the head) of a list,
251  * in order from the first to the last.
252  *
253  * For each iteration, it sets the cursor variable to the current element.
254  *
255  * \param pos Cursor pointer variable identifier.
256  * \param head Head pointer of the list to iterate [IN].
257  * \param member Identifier of the member of the data type
258  * serving as list node.
259  * \note It it safe to delete the current item while iterating.
260  * It is however <b>not</b> safe to delete another item.
261  */
262 #define vlc_list_foreach(pos, head, member) \
263  for (struct vlc_list_it vlc_list_it__##pos = vlc_list_it_start(head); \
264  vlc_list_it_continue(&(vlc_list_it__##pos)) \
265  && ((pos) = vlc_list_entry_p((vlc_list_it__##pos).current, \
266  pos, member), true); \
267  vlc_list_it_next(&(vlc_list_it__##pos)))
268 
269 /**
270  * Converts a list node pointer to an element pointer.
271  *
272  * \param ptr list node pointer
273  * \param type list data element type name
274  * \param member list node member within the data element compound type
275  */
276 #define vlc_list_entry(ptr, type, member) container_of(ptr, type, member)
277 
278 static inline void *vlc_list_first_or_null(const struct vlc_list *head,
279  size_t offset)
280 {
281  if (vlc_list_is_empty(head))
282  return NULL;
283  return ((char *)(head->next)) - offset;
284 }
285 
286 static inline void *vlc_list_last_or_null(const struct vlc_list *head,
287  size_t offset)
288 {
289  if (vlc_list_is_empty(head))
290  return NULL;
291  return ((char *)(head->prev)) - offset;
292 }
293 
294 static inline void *vlc_list_prev_or_null(const struct vlc_list *head,
295  struct vlc_list *node,
296  size_t offset)
297 {
298  if (vlc_list_is_first(node, head))
299  return NULL;
300  return ((char *)(node->prev)) - offset;
301 }
302 
303 static inline void *vlc_list_next_or_null(const struct vlc_list *head,
304  struct vlc_list *node,
305  size_t offset)
306 {
307  if (vlc_list_is_last(node, head))
308  return NULL;
309  return ((char *)(node->next)) - offset;
310 }
311 
312 /**
313  * Gets the first element.
314  *
315  * \param head Head of list whose last element to get [IN].
316  *
317  * \return the first entry in a list or NULL if empty.
318  */
319 #define vlc_list_first_entry_or_null(head, type, member) \
320  ((type *)vlc_list_first_or_null(head, offsetof (type, member)))
321 
322 /**
323  * Gets the last element.
324  *
325  * \param head Head of list whose last element to get [IN].
326  *
327  * \return the last entry in a list or NULL if empty.
328  */
329 #define vlc_list_last_entry_or_null(head, type, member) \
330  ((type *)vlc_list_last_or_null(head, offsetof (type, member)))
331 
332 #define vlc_list_prev_entry_or_null(head, entry, type, member) \
333  ((type *)vlc_list_prev_or_null(head, &(entry)->member, \
334  offsetof (type, member)))
335 #define vlc_list_next_entry_or_null(head, entry, type, member) \
336  ((type *)vlc_list_next_or_null(head, &(entry)->member, \
337  offsetof (type, member)))
338 
339 /** \todo Merging lists, splitting lists. */
340 
341 /** @} */
342 
343 #endif /* VLC_LIST_H */
vlc_list_it_next
static void vlc_list_it_next(struct vlc_list_it *restrict it)
Definition: vlc_list.h:226
vlc_list_it::head
const struct vlc_list * head
Definition: vlc_list.h:207
vlc_list_prev_or_null
static void * vlc_list_prev_or_null(const struct vlc_list *head, struct vlc_list *node, size_t offset)
Definition: vlc_list.h:295
vlc_common.h
vlc_list_it
List iterator.
Definition: vlc_list.h:205
vlc_list_init
static void vlc_list_init(struct vlc_list *restrict head)
Initializes an empty list head.
Definition: vlc_list.h:57
vlc_list_is_first
static bool vlc_list_is_first(const struct vlc_list *node, const struct vlc_list *head)
Checks if an element is first in a list.
Definition: vlc_list.h:181
vlc_list_it::next
struct vlc_list * next
Definition: vlc_list.h:209
vlc_list::prev
struct vlc_list * prev
Definition: vlc_list.h:45
vlc_list
Doubly-linked list node.
Definition: vlc_list.h:43
vlc_list_last_or_null
static void * vlc_list_last_or_null(const struct vlc_list *head, size_t offset)
Definition: vlc_list.h:287
vlc_list_prepend
static void vlc_list_prepend(struct vlc_list *restrict node, struct vlc_list *head)
Prepends an element into a list.
Definition: vlc_list.h:122
vlc_list_add_between
static void vlc_list_add_between(struct vlc_list *restrict node, struct vlc_list *prev, struct vlc_list *next)
Inserts an element in a list.
Definition: vlc_list.h:70
vlc_list_remove
static void vlc_list_remove(struct vlc_list *restrict node)
Removes an element from a list.
Definition: vlc_list.h:135
vlc_list_append
static void vlc_list_append(struct vlc_list *restrict node, struct vlc_list *head)
Appends an element into a list.
Definition: vlc_list.h:110
vlc_list_is_empty
static bool vlc_list_is_empty(const struct vlc_list *head)
Checks if a list is empty.
Definition: vlc_list.h:167
vlc_list_is_last
static bool vlc_list_is_last(const struct vlc_list *node, const struct vlc_list *head)
Checks if an element is last in a list.
Definition: vlc_list.h:196
vlc_list_add_before
static void vlc_list_add_before(struct vlc_list *restrict node, struct vlc_list *next)
Inserts an element before another.
Definition: vlc_list.h:98
vlc_list::next
struct vlc_list * next
Definition: vlc_list.h:46
vlc_list_add_after
static void vlc_list_add_after(struct vlc_list *restrict node, struct vlc_list *prev)
Inserts an element after another.
Definition: vlc_list.h:86
vlc_list_replace
static void vlc_list_replace(const struct vlc_list *original, struct vlc_list *restrict substitute)
Replaces an element with another one.
Definition: vlc_list.h:150
vlc_list_it::current
struct vlc_list * current
Definition: vlc_list.h:208
vlc_list_it_continue
static bool vlc_list_it_continue(const struct vlc_list_it *restrict it)
Definition: vlc_list.h:221
vlc_list_it_start
static struct vlc_list_it vlc_list_it_start(const struct vlc_list *head)
Definition: vlc_list.h:213
vlc_list_next_or_null
static void * vlc_list_next_or_null(const struct vlc_list *head, struct vlc_list *node, size_t offset)
Definition: vlc_list.h:304
vlc_list_first_or_null
static void * vlc_list_first_or_null(const struct vlc_list *head, size_t offset)
Definition: vlc_list.h:279