[vlc-devel] [PATCH 1/4] vlc_list: helpers for doubly linked lists
Romain Vimont
rom1v at videolabs.io
Wed Jun 13 21:45:46 CEST 2018
On Wed, Jun 13, 2018 at 12:55:17PM +0300, Rémi Denis-Courmont wrote:
> pos is an l-value, not necessarily a variable. If you look at existing array macros usages, quite often the l-values for array and size are not variables, so I don't think we should make that assumption.
What about using a name that will never shadow in practice?
for( struct vlc_list_t _an_awful_name_that_will_never_shadow_user_code_in_practice; … )
They would only shadow to provide the expected behavior for nested
foreach loops.
>
> Le 13 juin 2018 12:45:19 GMT+03:00, Steve Lhomme <robux4 at ycbcr.xyz> a écrit :
> >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
> >
> >_______________________________________________
> >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
More information about the vlc-devel
mailing list