[vlc-devel] [PATCH 1/4] vlc_list: helpers for doubly linked lists

[Steve Lhomme]

On 2018-06-13 11:24 AM, Romain Vimont wrote:
> On Tue, Jun 12, 2018 at 09:27:04PM +0300, Rémi Denis-Courmont wrote:
>> ---
>>   include/vlc_list.h | 261 +++++++++++++++++++++++++++++++++++++++++++++
>>   src/Makefile.am    |   1 +
>>   2 files changed, 262 insertions(+)
>>   create mode 100644 include/vlc_list.h
>>
>> diff --git a/include/vlc_list.h b/include/vlc_list.h
>> new file mode 100644
>> index 0000000000..b334c075c2
>> --- /dev/null
>> +++ b/include/vlc_list.h
>> @@ -0,0 +1,261 @@
>> +/******************************************************************************
>> + * 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 <stdbool.h>
>> +# include <stddef.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;
>> +};
>> +
>> +/**
>> + * Initializes an empty list head.
>> + */
>> +static inline void vlc_list_init(struct vlc_list *restrict head)
>> +{
>> +    head->prev = head;
>> +    head->next = head;
>> +}
>> +
>> +/**
>> + * Adds an element in a list.
>> + *
>> + * \note This is a common internal function. Do not call this directly.
>> + */
>> +static inline void vlc_list_add_internal(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;
>> +}
>> +
>> +/**
>> + * Prepends an element into a list.
>> + *
>> + * \param node Node of the element to prepend to the list [OUT].
>> + * \param head Head of the list to be prepended.
>> + */
>> +static inline void vlc_list_prepend(struct vlc_list *restrict node,
>> +                                    struct vlc_list *head)
>> +{
>> +    vlc_list_add_internal(node, head, head->next);
>> +}
>> +
>> +/**
>> + * Appends an element into a list.
>> + *
>> + * \param node Node of the element to append to the list [OUT].
>> + * \param head Head of the list to be append.
>> + */
>> +static inline void vlc_list_append(struct vlc_list *restrict node,
>> +                                   struct vlc_list *head)
>> +{
>> +    vlc_list_add_internal(node, head->prev, 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;
>> +}
>> +
>> +/**
>> + * Checks if a list is empty.
>> + *
>> + * \param head Head of the list to be checked [IN].
>> + *
>> + * \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 List node of the element [IN].
>> + * \param head Head of the list to be checked [IN].
>> + *
>> + * \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 List node of the element [IN].
>> + * \param head Head of the list to be checked [IN].
>> + *
>> + * \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;
>> +
>> +    return (struct vlc_list_it){ head, first, first->next };
>> +}
>> +
>> +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;
>> +}
>> +
>> +/**
>> + * 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 variable.
>> + * \param it Storage space fo list iterator internal data.
>> + * \param head Head of the list to iterate [IN].
>> + * \param type Data type of list elements.
>> + * \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(p, it, head, type, member) \
>> +    for (struct vlc_list_it it = vlc_list_it_start(head); \
> I see the intention to avoid the declaration on the caller-side, but it
> feels weird to require a parameter for which the caller should mostly
> pass a random string (which does not conflict with any existing variable
> name).

Since pos is already a variable that avoids shadowing, can't we use 
pos##some_suffix internally ? (which a proper STRINGIFY macro)

>
> But I think there is no perfect solution.
>
>> +         vlc_list_it_continue(&it) \
>> +          && ((p) = vlc_list_entry(it.current, type, member), true); \
> Nice :)
>
>> +         vlc_list_it_next(&it))
>> +
>> +/**
>> + * 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)
> Should include <vlc_common.h> for container_of()?
>
>> +
>> +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;
>> +}
>> +
>> +/**
>> + * Gets the first element.
>> + *
>> + * \param head Head of list whose last element to get [IN].
>> + *
>> + * \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 Head of list whose last element to get [IN].
>> + *
>> + * \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)))
>> +
>> +/** \todo Merging lists, splitting lists. */
>> +
>> +/** @} */
>> +
>> +#endif /* VLC_LIST_H */
>> diff --git a/src/Makefile.am b/src/Makefile.am
>> index a13a3147d0..56552deab2 100644
>> --- a/src/Makefile.am
>> +++ b/src/Makefile.am
>> @@ -60,6 +60,7 @@ pluginsinclude_HEADERS = \
>>   	../include/vlc_input_item.h \
>>   	../include/vlc_interface.h \
>>   	../include/vlc_keystore.h \
>> +	../include/vlc_list.h \
>>   	../include/vlc_md5.h \
>>   	../include/vlc_messages.h \
>>   	../include/vlc_meta.h \
>> -- 
>> 2.17.1
>>
>> _______________________________________________
>> vlc-devel mailing list
>> To unsubscribe or modify your subscription options:
>> https://mailman.videolan.org/listinfo/vlc-devel
> _______________________________________________
> vlc-devel mailing list
> To unsubscribe or modify your subscription options:
> https://mailman.videolan.org/listinfo/vlc-devel