[vlc-devel] [PATCH 1/3] vlc_list: helpers for doubly linked lists
Rémi Denis-Courmont
remi at remlab.net
Mon Jun 11 12:27:12 CEST 2018
I am storing the head so that the head expression is expansion-safe. In practice, the compiler should be able to optimize it away. Likewise, it should be able to optimize the constant offset away.
Point is that an iterator is unavoidable in the general case. With that in mind, I'd rather leverage the iterator to make the code as safe as possible.
I already replaced goal with head to make the iteration safe against removal.
Le 11 juin 2018 11:11:42 GMT+03:00, Romain Vimont <rom1v at videolabs.io> a écrit :
>On Mon, Jun 11, 2018 at 12:15:49AM +0300, Rémi Denis-Courmont wrote:
>> The iterator must be named so. And if it needs a name, it must be
>unique. Otherwise shadowing will occur, e.g. with nested loops.
>>
>> So I cannot fathom how to avoid the iterator name parameter. The
>kernel also needs an explicit parameter for iterator, at least in the
>"safe" variants.
>
>It needs an additional parameter in the safe variant, but IIUC, your
>implementation is equivalent to the unsafe one (not safe against
>removal
>while iterating).
>
>You cannot avoid naming the iterator if you use one, but I think you
>can
>avoid using an iterator at all (I mean, a separate structure like
>vlc_list_it, by using "head" as a "goal")
>
>Something like this (inspired by the linux implementation, not heavily
>tested and to be factorized):
>
> #define vlc_list_foreach(p, head, type, member) \
> for( p = (type *)(((char *)(head)->next) - offsetof(type, member)); \
> &(p)->member != (head); \
> p = (type *)(((char *)(p)->member.next) - offsetof(type, member)))
>
>Is something missing with this approach?
>
>> Note that the kernel list macros depend on GCC extension, notably
>typeof, so they are not directly applicable.
>
>OK for type/typeof.
>
>>
>> Le 10 juin 2018 23:45:53 GMT+03:00, Romain Vimont
><rom1v at videolabs.io> a écrit :
>> >On Sun, Jun 10, 2018 at 09:59:48PM +0300, Rémi Denis-Courmont wrote:
>> >> ---
>> >> include/vlc_list.h | 263
>> >+++++++++++++++++++++++++++++++++++++++++++++
>> >> src/Makefile.am | 1 +
>> >> 2 files changed, 264 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..0c6684c375
>> >> --- /dev/null
>> >> +++ b/include/vlc_list.h
>> >> @@ -0,0 +1,263 @@
>> >>
>>
>>+/******************************************************************************
>> >> + * 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
>> >> +{
>> >> + struct vlc_list *goal;
>> >> + struct vlc_list *next;
>> >> + ptrdiff_t node_offset;
>> >> +};
>> >> +
>> >> +static inline void *vlc_list_it_start(struct vlc_list_it
>*restrict
>> >it,
>> >> + struct vlc_list *head,
>size_t
>> >offset)
>> >> +{
>> >> + struct vlc_list *first = head->next;
>> >> +
>> >> + it->goal = first;
>> >> + it->next = first->next;
>> >> + it->node_offset = -offset;
>> >> + return ((char *)first) + it->node_offset;
>> >> +}
>> >> +
>> >> +static inline bool vlc_list_it_done(const struct vlc_list_it
>> >*restrict it)
>> >> +{
>> >> + return it->next == it->goal;
>> >> +}
>> >> +
>> >> +static inline void *vlc_list_it_next(struct vlc_list_it *restrict
>> >it)
>> >> +{
>> >> + struct vlc_list *next = it->next;
>> >> +
>> >> + it->next = it->next->next;
>> >> + return ((char *)next) + it->node_offset;
>> >> +}
>> >> +
>> >> +/**
>> >> + * 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) \
>> >
>> >Couldn't it be simplified so that the caller need not provide "it"
>nor
>> >"type"? (like list_for_each_entry() in linux)
>> >
>>
>><https://elixir.bootlin.com/linux/v4.17/source/include/linux/list.h#L457>
>> >
>> >> + for (p = (type *)vlc_list_it_start(&(it), head, offsetof
>(type,
>> >member)); \
>> >> + !vlc_list_it_done(&(it)); \
>> >> + p = (type *)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)
>> >> +
>> >> +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
>>
>> --
>> Envoyé de mon appareil Android avec Courriel K-9 Mail. Veuillez
>excuser ma brièveté.
>
>> _______________________________________________
>> 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
--
Envoyé de mon appareil Android avec Courriel K-9 Mail. Veuillez excuser ma brièveté.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.videolan.org/pipermail/vlc-devel/attachments/20180611/fa90a532/attachment.html>
More information about the vlc-devel
mailing list