/src/vlc/include/vlc_list.h

Source (jump to first uncovered line)
/******************************************************************************
 * vlc_list.h
 ******************************************************************************
 * Copyright © 2018 Rémi Denis-Courmont
 *
 * This program is free software; you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation; either version 2.1 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this program; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA.
 *****************************************************************************/

#ifndef VLC_LIST_H
# define VLC_LIST_H 1

# include <stdalign.h>
# include <stdbool.h>

/**
 * \defgroup list Linked lists
 * \ingroup cext
 * @{
 * \file
 * This provides convenience helpers for linked lists.
 */

/**
 * Doubly-linked list node.
 *
 * This data structure provides a doubly-linked list node.
 * It must be embedded in each member of a list as a node proper.
 * It also serves as a list head in the object containing the list.
 */
struct vlc_list
{
    struct vlc_list *prev;
    struct vlc_list *next;
};

/**
 * Static initializer for a list head.
 */
#define VLC_LIST_INITIALIZER(h) { h, h }

/**
 * Initializes an empty list head.
 */
static inline void vlc_list_init(struct vlc_list *restrict head)
{
    head->prev = head;
    head->next = head;
}

/**
 * Inserts an element in a list.
 *
 * \param node [out] Node pointer of the element to insert.
 * \param prev Node pointer of the previous element.
 * \param next Node pointer of the next element.
 */
static inline void vlc_list_add_between(struct vlc_list *restrict node,
                                        struct vlc_list *prev,
                                        struct vlc_list *next)
{
    node->prev = prev;
    node->next = next;
    prev->next = node;
    next->prev = node;
}

/**
 * Inserts an element after another.
 *
 * \param node [out] Node pointer of the element to insert
 * \param prev Node pointer of the previous element.
 */
static inline void vlc_list_add_after(struct vlc_list *restrict node,
                                      struct vlc_list *prev)
{
    vlc_list_add_between(node, prev, prev->next);
}

/**
 * Inserts an element before another.
 *
 * \param node [out] Node pointer of the element to insert.
 * \param next Node pointer of the next element.
 */
static inline void vlc_list_add_before(struct vlc_list *restrict node,
                                       struct vlc_list *next)
{
    vlc_list_add_between(node, next->prev, next);
}

/**
 * Appends an element into a list.
 *
 * \param node [out] Node pointer of the element to append to the list.
 * \param head Head pointer of the list to append the element to.
 */
static inline void vlc_list_append(struct vlc_list *restrict node,
                                   struct vlc_list *head)
{
    vlc_list_add_before(node, head);
}

/**
 * Prepends an element into a list.
 *
 * \param node [out] Node pointer of the element to prepend to the list.
 * \param head Head pointer of the list to prepend the element to.
 */
static inline void vlc_list_prepend(struct vlc_list *restrict node,
                                    struct vlc_list *head)
{
    vlc_list_add_after(node, head);
}

/**
 * Removes an element from a list.
 *
 * \param node Node of the element to remove from a list.
 * \warning The element must be inside a list.
 * Otherwise the behaviour is undefined.
 */
static inline void vlc_list_remove(struct vlc_list *restrict node)
{
    struct vlc_list *prev = node->prev;
    struct vlc_list *next = node->next;

    prev->next = next;
    next->prev = prev;
}

/**
 * Replaces an element with another one.
 *
 * \param original [in] Node pointer of the element to remove from the list.
 * \param substitute [out] Node pointer of the replacement.
 */
static inline void vlc_list_replace(const struct vlc_list *original,
                                    struct vlc_list *restrict substitute)
{
    vlc_list_add_between(substitute, original->prev, original->next);
}

/**
 * Checks if a list is empty.
 *
 * \param head [in] Head of the list to be checked.
 *
 * \retval false The list is not empty.
 * \retval true The list is empty.
 *
 * \note Obviously the list must have been initialized.
 * Otherwise, the behaviour is undefined.
 */
static inline bool vlc_list_is_empty(const struct vlc_list *head)
{
    return head->next == head;
}

/**
 * Checks if an element is first in a list.
 *
 * \param node [in] List node of the element.
 * \param head [in] Head of the list to be checked.
 *
 * \retval false The element is not first (or is in another list).
 * \retval true The element is first.
 */
static inline bool vlc_list_is_first(const struct vlc_list *node,
                                     const struct vlc_list *head)
{
    return node->prev == head;
}

/**
 * Checks if an element is last in a list.
 *
 * \param node [in] List node of the element.
 * \param head [in] Head of the list to be checked.
 *
 * \retval false The element is not last (or is in another list).
 * \retval true The element is last.
 */
static inline bool vlc_list_is_last(const struct vlc_list *node,
                                    const struct vlc_list *head)
{
    return node->next == head;
}

/**
 * List iterator.
 */
struct vlc_list_it
{
    const struct vlc_list *head;
    struct vlc_list *current;
    struct vlc_list *next;
};

static inline
struct vlc_list_it vlc_list_it_start(const struct vlc_list *head)
{
    struct vlc_list *first = head->next;

    struct vlc_list_it it = { head, first, first->next };
    return it;
}

static inline
struct vlc_list_it vlc_list_it_reverse_start(const struct vlc_list *head)
{
    struct vlc_list *first = head->prev;

    struct vlc_list_it it = { head, first, first->prev };
    return it;
}

static inline bool vlc_list_it_continue(const struct vlc_list_it *restrict it)
{
    return it->current != it->head;
}

static inline void vlc_list_it_next(struct vlc_list_it *restrict it)
{
    struct vlc_list *next = it->next;

    it->current = next;
    it->next = next->next;
}

static inline void vlc_list_it_prev(struct vlc_list_it *restrict it)
{
    struct vlc_list *next = it->next;

    it->current = next;
    it->next = next->prev;
}

/**
 * List iteration macro.
 *
 * This macro iterates over all elements (excluding the head) of a list,
 * in order from the first to the last.
 *
 * For each iteration, it sets the cursor variable to the current element.
 *
 * \param pos Cursor pointer variable identifier.
 * \param head [in] Head pointer of the list to iterate.
 * \param member Identifier of the member of the data type
 *               serving as list node.
 * \note It it safe to delete the current item while iterating.
 * It is however <b>not</b> safe to delete another item.
 */
#define vlc_list_foreach(pos, head, member) \
    for (struct vlc_list_it vlc_list_it__##pos = vlc_list_it_start(head); \
         vlc_list_it_continue(&(vlc_list_it__##pos)) \
          && ((pos) = container_of((vlc_list_it__##pos).current, \
                                   typeof (*(pos)), member), true); \
         vlc_list_it_next(&(vlc_list_it__##pos)))

/**
 * List iteration macro.
 *
 * This macro iterates over all elements (excluding the head) of a list,
 * in reversed order from the first to the last.
 *
 * For each iteration, it sets the cursor variable to the current element.
 *
 * \param pos Cursor pointer variable identifier.
 * \param head [in] Head pointer of the list to iterate.
 * \param member Identifier of the member of the data type
 *               serving as list node.
 * \note It it safe to delete the current item while iterating.
 * It is however <b>not</b> safe to delete another item.
 */
#define vlc_list_reverse_foreach(pos, head, member) \
    for (struct vlc_list_it vlc_list_it_##pos = vlc_list_it_reverse_start(head); \
         vlc_list_it_continue(&(vlc_list_it_##pos)) \
          && ((pos) = container_of((vlc_list_it_##pos).current, \
                                   typeof (*(pos)), member), true); \
         vlc_list_it_prev(&(vlc_list_it_##pos)))

/**
 * Converts a list node pointer to an element pointer.
 *
 * \param ptr list node pointer
 * \param type list data element type name
 * \param member list node member within the data element compound type
 */
#define vlc_list_entry(ptr, type, member) container_of(ptr, type, member)

static inline void *vlc_list_first_or_null(const struct vlc_list *head,
                                           size_t offset)
{
    if (vlc_list_is_empty(head))
        return NULL;
    return ((char *)(head->next)) - offset;
}

static inline void *vlc_list_last_or_null(const struct vlc_list *head,
                                          size_t offset)
{
    if (vlc_list_is_empty(head))
        return NULL;
    return ((char *)(head->prev)) - offset;
}

static inline void *vlc_list_prev_or_null(const struct vlc_list *head,
                                          const struct vlc_list *node,
                                          size_t offset)
{
    if (vlc_list_is_first(node, head))
        return NULL;
    return ((char *)(node->prev)) - offset;
}

static inline void *vlc_list_next_or_null(const struct vlc_list *head,
                                          const struct vlc_list *node,
                                          size_t offset)
{
    if (vlc_list_is_last(node, head))
        return NULL;
    return ((char *)(node->next)) - offset;
}

/**
 * Gets the first element.
 *
 * \param head [in] Head of list whose last element to get.
 *
 * \return the first entry in a list or NULL if empty.
 */
#define vlc_list_first_entry_or_null(head, type, member) \
        ((type *)vlc_list_first_or_null(head, offsetof (type, member)))

/**
 * Gets the last element.
 *
 * \param head [in] Head of list whose last element to get.
 *
 * \return the last entry in a list or NULL if empty.
 */
#define vlc_list_last_entry_or_null(head, type, member) \
        ((type *)vlc_list_last_or_null(head, offsetof (type, member)))

#define vlc_list_prev_entry_or_null(head, entry, type, member) \
        ((type *)vlc_list_prev_or_null(head, &(entry)->member, \
                                       offsetof (type, member)))
#define vlc_list_next_entry_or_null(head, entry, type, member) \
        ((type *)vlc_list_next_or_null(head, &(entry)->member, \
                                       offsetof (type, member)))

/** \todo Merging lists, splitting lists. */

/** @} */

#endif /* VLC_LIST_H */

Coverage Report

Created: 2023-06-07 06:30

Line	Count	Source (jump to first uncovered line)
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	0	{
58	0	head->prev = head;
59	0	head->next = head;
60	0	}
61
62		/**
63		* Inserts an element in a list.
64		*
65		* \param node [out] Node pointer of the element to insert.
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	0	{
73	0	node->prev = prev;
74	0	node->next = next;
75	0	prev->next = node;
76	0	next->prev = node;
77	0	}
78
79		/**
80		* Inserts an element after another.
81		*
82		* \param node [out] Node pointer of the element to insert
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	0	{
88	0	vlc_list_add_between(node, prev, prev->next);
89	0	}
90
91		/**
92		* Inserts an element before another.
93		*
94		* \param node [out] Node pointer of the element to insert.
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	0	{
100	0	vlc_list_add_between(node, next->prev, next);
101	0	}
102
103		/**
104		* Appends an element into a list.
105		*
106		* \param node [out] Node pointer of the element to append to the list.
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	0	{
112	0	vlc_list_add_before(node, head);
113	0	}
114
115		/**
116		* Prepends an element into a list.
117		*
118		* \param node [out] Node pointer of the element to prepend to the list.
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	0	{
124	0	vlc_list_add_after(node, head);
125	0	}
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	0	{
136	0	struct vlc_list *prev = node->prev;
137	0	struct vlc_list *next = node->next;
138	0
139	0	prev->next = next;
140	0	next->prev = prev;
141	0	}
142
143		/**
144		* Replaces an element with another one.
145		*
146		* \param original [in] Node pointer of the element to remove from the list.
147		* \param substitute [out] Node pointer of the replacement.
148		*/
149		static inline void vlc_list_replace(const struct vlc_list *original,
150		struct vlc_list *restrict substitute)
151	0	{
152	0	vlc_list_add_between(substitute, original->prev, original->next);
153	0	}
154
155		/**
156		* Checks if a list is empty.
157		*
158		* \param head [in] Head of the list to be checked.
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	0	{
168	0	return head->next == head;
169	0	}
170
171		/**
172		* Checks if an element is first in a list.
173		*
174		* \param node [in] List node of the element.
175		* \param head [in] Head of the list to be checked.
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	0	{
183	0	return node->prev == head;
184	0	}
185
186		/**
187		* Checks if an element is last in a list.
188		*
189		* \param node [in] List node of the element.
190		* \param head [in] Head of the list to be checked.
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	0	{
198	0	return node->next == head;
199	0	}
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	0	{
214	0	struct vlc_list *first = head->next;
215	0
216	0	struct vlc_list_it it = { head, first, first->next };
217	0	return it;
218	0	}
219
220		static inline
221		struct vlc_list_it vlc_list_it_reverse_start(const struct vlc_list *head)
222	0	{
223	0	struct vlc_list *first = head->prev;
224	0
225	0	struct vlc_list_it it = { head, first, first->prev };
226	0	return it;
227	0	}
228
229		static inline bool vlc_list_it_continue(const struct vlc_list_it *restrict it)
230	0	{
231	0	return it->current != it->head;
232	0	}
233
234		static inline void vlc_list_it_next(struct vlc_list_it *restrict it)
235	0	{
236	0	struct vlc_list *next = it->next;
237	0
238	0	it->current = next;
239	0	it->next = next->next;
240	0	}
241
242		static inline void vlc_list_it_prev(struct vlc_list_it *restrict it)
243	0	{
244	0	struct vlc_list *next = it->next;
245	0
246	0	it->current = next;
247	0	it->next = next->prev;
248	0	}
249
250		/**
251		* List iteration macro.
252		*
253		* This macro iterates over all elements (excluding the head) of a list,
254		* in order from the first to the last.
255		*
256		* For each iteration, it sets the cursor variable to the current element.
257		*
258		* \param pos Cursor pointer variable identifier.
259		* \param head [in] Head pointer of the list to iterate.
260		* \param member Identifier of the member of the data type
261		* serving as list node.
262		* \note It it safe to delete the current item while iterating.
263		* It is however <b>not</b> safe to delete another item.
264		*/
265		#define vlc_list_foreach(pos, head, member) \
266		for (struct vlc_list_it vlc_list_it__##pos = vlc_list_it_start(head); \
267		vlc_list_it_continue(&(vlc_list_it__##pos)) \
268		&& ((pos) = container_of((vlc_list_it__##pos).current, \
269		typeof (*(pos)), member), true); \
270		vlc_list_it_next(&(vlc_list_it__##pos)))
271
272		/**
273		* List iteration macro.
274		*
275		* This macro iterates over all elements (excluding the head) of a list,
276		* in reversed order from the first to the last.
277		*
278		* For each iteration, it sets the cursor variable to the current element.
279		*
280		* \param pos Cursor pointer variable identifier.
281		* \param head [in] Head pointer of the list to iterate.
282		* \param member Identifier of the member of the data type
283		* serving as list node.
284		* \note It it safe to delete the current item while iterating.
285		* It is however <b>not</b> safe to delete another item.
286		*/
287		#define vlc_list_reverse_foreach(pos, head, member) \
288		for (struct vlc_list_it vlc_list_it_##pos = vlc_list_it_reverse_start(head); \
289		vlc_list_it_continue(&(vlc_list_it_##pos)) \
290		&& ((pos) = container_of((vlc_list_it_##pos).current, \
291		typeof (*(pos)), member), true); \
292		vlc_list_it_prev(&(vlc_list_it_##pos)))
293
294		/**
295		* Converts a list node pointer to an element pointer.
296		*
297		* \param ptr list node pointer
298		* \param type list data element type name
299		* \param member list node member within the data element compound type
300		*/
301		#define vlc_list_entry(ptr, type, member) container_of(ptr, type, member)
302
303		static inline void vlc_list_first_or_null(const struct vlc_list head,
304		size_t offset)
305	0	{
306	0	if (vlc_list_is_empty(head))
307	0	return NULL;
308	0	return ((char *)(head->next)) - offset;
309	0	}
310
311		static inline void vlc_list_last_or_null(const struct vlc_list head,
312		size_t offset)
313	0	{
314	0	if (vlc_list_is_empty(head))
315	0	return NULL;
316	0	return ((char *)(head->prev)) - offset;
317	0	}
318
319		static inline void vlc_list_prev_or_null(const struct vlc_list head,
320		const struct vlc_list *node,
321		size_t offset)
322	0	{
323	0	if (vlc_list_is_first(node, head))
324	0	return NULL;
325	0	return ((char *)(node->prev)) - offset;
326	0	}
327
328		static inline void vlc_list_next_or_null(const struct vlc_list head,
329		const struct vlc_list *node,
330		size_t offset)
331	0	{
332	0	if (vlc_list_is_last(node, head))
333	0	return NULL;
334	0	return ((char *)(node->next)) - offset;
335	0	}
336
337		/**
338		* Gets the first element.
339		*
340		* \param head [in] Head of list whose last element to get.
341		*
342		* \return the first entry in a list or NULL if empty.
343		*/
344		#define vlc_list_first_entry_or_null(head, type, member) \
345		((type *)vlc_list_first_or_null(head, offsetof (type, member)))
346
347		/**
348		* Gets the last element.
349		*
350		* \param head [in] Head of list whose last element to get.
351		*
352		* \return the last entry in a list or NULL if empty.
353		*/
354		#define vlc_list_last_entry_or_null(head, type, member) \
355		((type *)vlc_list_last_or_null(head, offsetof (type, member)))
356
357		#define vlc_list_prev_entry_or_null(head, entry, type, member) \
358		((type *)vlc_list_prev_or_null(head, &(entry)->member, \
359		offsetof (type, member)))
360		#define vlc_list_next_entry_or_null(head, entry, type, member) \
361		((type *)vlc_list_next_or_null(head, &(entry)->member, \
362		offsetof (type, member)))
363
364		/** \todo Merging lists, splitting lists. */
365
366		/** @} */
367
368		#endif /* VLC_LIST_H */