[vlc-devel] [RFC v4] vlc_vector: add helpers for vectors

[Rémi Denis-Courmont]

Le perjantaina 31. elokuuta 2018, 15.04.52 EEST Romain Vimont a écrit :
> Add a new API for handling general-purpose vectors, intended to replace
> ARRAY_*.
> 
> Like ARRAY_*, it provides macros to handle a dynamic array generic
> over the type of its items.
> 
> Contrary to ARRAY_*:
>  - it does not abort on allocation failure (but reports the error);
>  - it uses size_t instead of int to store the capacity and the size;
>  - it checks for overflows on reallocation.
> 
> For illustration purpose, embedding a vector of input_item_t* in a
> struct looks like:
> 
>     struct playlist {
>         struct VLC_VECTOR(input_item_t *) items;
>         // ...
>     };
> 
> The main features (with names inspired by std::vector from C++ and
> std::vec::Vec from Rust) are:
>  - void vlc_vector_init(pv)
>       init the vector (use VLC_VECTOR_INITIALIZER for static init)
>  - void vlc_vector_clear(pv)
>       clear the vector, and release any associated resources
>  - vec.size
>       read the size of the vector
>  - vec.data[i]
>       access the i_th item
>  - bool vlc_vector_push(pv, item)
>       push an item at the end of the vector
>  - bool vlc_vector_insert(pv, index, item)
>       insert an item at index
>  - bool vlc_vector_insert_all(pv, index, items, count)
>       insert several items at index
>  - void vlc_vector_remove(pv, index)
>       remove an item
>  - void vlc_vector_remove_slice(pv, index, count)
>       remove a slice of items
>  - void vlc_vector_swap_remove(pv, index)
>       remove an item in O(1) without preserving ordering
>  - bool vlc_vector_reserve(pv, mincap)
>       increase the capacity of the vector in advance
>  - void vlc_vector_shrink_to_fit(pv)
>       resize the vector to its actual size
>  - void vlc_vector_index_of(pv, index, pidx)
>       find the index of an item (returns the result in *pidx)
>  - vlc_vector_foreach(item, pv)
>       a for-each loop
> 
> It uses an exponential growth policy for both increasing and decreasing
> the size. As a consequence, the amortized complexity of
> vlc_vector_push() is O(1).
> ---
> Changes from v3:
>  - simplify "(x, true) && (y, true)" by "(x, y)"
>  - reformat macros to explicit their structure
> 
>  include/vlc_common.h |   6 +
>  include/vlc_vector.h | 465 +++++++++++++++++++++++++++++++++++++++++++
>  src/Makefile.am      |   5 +-
>  src/test/vector.c    | 362 +++++++++++++++++++++++++++++++++
>  4 files changed, 837 insertions(+), 1 deletion(-)
>  create mode 100644 include/vlc_vector.h
>  create mode 100644 src/test/vector.c
> 
> diff --git a/include/vlc_common.h b/include/vlc_common.h
> index 3be979dab5..81310030cc 100644
> --- a/include/vlc_common.h
> +++ b/include/vlc_common.h
> @@ -1118,6 +1118,12 @@ static inline void *vlc_alloc(size_t count, size_t
> size) return mul_overflow(count, size, &size) ? NULL : malloc(size); }
> 
> +VLC_USED VLC_MALLOC
> +static inline void *vlc_reallocarray(void *ptr, size_t count, size_t size)
> +{
> +    return mul_overflow(count, size, &size) ? NULL : realloc(ptr, size);
> +}
> +
>  /**************************************************************************
> *** * I18n stuff
>  
> ***************************************************************************
> **/ diff --git a/include/vlc_vector.h b/include/vlc_vector.h
> new file mode 100644
> index 0000000000..64fe051739
> --- /dev/null
> +++ b/include/vlc_vector.h
> @@ -0,0 +1,465 @@
> +/**************************************************************************
> **** + * vlc_vector.h
> +
> ***************************************************************************
> *** + * Copyright © 2018 VLC authors and VideoLAN
> + *
> + * 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_VECTOR_H
> +#define VLC_VECTOR_H
> +
> +#include <stdbool.h>
> +
> +/**
> + * \defgroup vector Vector
> + * \ingroup cext
> + * @{
> + * \file
> + * This provides convenience helpers for vectors.
> + */
> +
> +/**
> + * Vector struct body.
> + *
> + * A vector is a dynamic array, managed by the vlc_vector_* helpers.
> + *
> + * It is generic over the type of its items, so it is implemented as
> macros. + *
> + * To use a vector, a new type must be defined:
> + *
> + * \verbatim
> + * struct vec_int VLC_VECTOR(int);
> + * \endverbatim
> + *
> + * The struct may be anonymous:
> + *
> + * \verbatim
> + * struct VLC_VECTOR(const char *) names;
> + * \endverbatim
> + *
> + * It is convenient to define a typedef to an anonymous structure:
> + *
> + * \verbatim
> + * typedef struct VLC_VECTOR(int) vec_int_t;
> + * \endverbatim
> + *
> + * Vector size is accessible via `vec.size`, and items are intended to be
> + * accessed directly, via `vec.data[i]`.
> + *
> + * Functions and macros having name ending with '_' are private.
> + */
> +#define VLC_VECTOR(type) \
> +{ \
> +    size_t cap; \
> +    size_t size; \
> +    type *data; \
> +}
> +
> +/**
> + * Static initializer for a vector.
> + */
> +#define VLC_VECTOR_INITIALIZER { 0, 0, NULL }
> +
> +/**
> + * Initialize an empty vector.
> + */
> +#define vlc_vector_init(pv) (void) \
> +( \
> +    /* cannot be implemened as do-while(0), called from vlc_vector_clear()
> */ \ +    (pv)->cap = 0, \
> +    (pv)->size = 0, \
> +    (pv)->data = NULL \
> +)
> +
> +/**
> + * Clear a vector, and release any associated resources.
> + */
> +#define vlc_vector_clear(pv) \
> +( \
> +    /* cannot be implemened as do-while(0), called from vlc_vector_resize()
> */ \ +    free((pv)->data), \
> +    vlc_vector_init(pv) \
> +)
> +
> +/**
> + * The minimal allocation size, in number of items.
> + *
> + * Private.
> + */
> +#define VLC_VECTOR_MINCAP_ ((size_t) 10)
> +
> +static inline size_t
> +vlc_vector_min_(size_t a, size_t b)
> +{
> +    return a < b ? a : b;
> +}
> +
> +static inline size_t
> +vlc_vector_max_(size_t a, size_t b)
> +{
> +    return a > b ? a : b;
> +}
> +
> +static inline size_t
> +vlc_vector_between_(size_t x, size_t min, size_t max)
> +{
> +    return vlc_vector_max_(min, vlc_vector_min_(max, x));
> +}
> +
> +/**
> + * Realloc array in *pptr.
> + *
> + * If reallocation failed, *pptr is kept untouched.
> + *
> + * Private.
> + *
> + * \retval true on success
> + * \retval false on failure
> + */
> +static inline bool
> +vlc_vector_reallocarray_(void **pptr, size_t count, size_t size)
> +{
> +    void *n = vlc_reallocarray(*pptr, count, size);
> +    if (n)
> +        /* replace ptr only on allocation success */
> +        *pptr = n;
> +    return n != NULL;
> +}
> +
> +static inline size_t
> +vlc_vector_enforce_size_t_(size_t value)
> +{
> +    return value;
> +}
> +
> +/**
> + * Realloc the underlying array to `newsize`.
> + *
> + * Private.
> + *
> + * \param pv a pointer to the vector
> + * \param newsize (size_t) the requested size
> + * \retval true if no allocation failed
> + * \retval false on allocation failure (the vector is left untouched)
> + */
> +#define vlc_vector_realloc_(pv, newsize) \
> +( \
> +    vlc_vector_reallocarray_((void **) &(pv)->data, newsize, \
> +                             sizeof(*(pv)->data)) && \

I strongly suspect a violation of type aliasing with the cast to void **.

That's one of the challenge that ruined some of my attempts to revector TAB_* 
in the past.

> +    ( \
> +        (pv)->cap = (newsize), \
> +        (pv)->size = vlc_vector_min_((pv)->size, newsize), \
> +        true \
> +    ) \
> +)
> +
> +/**
> + * Resize the vector to `newsize` exactly.
> + *
> + * If `newsize` is 0, the vector is cleared.
> + *
> + * \param pv a pointer to the vector
> + * \param newsize (size_t) the requested size
> + * \retval true if no allocation failed
> + * \retval false on allocation failure (the vector is left untouched)
> + */
> +#define vlc_vector_resize(pv, newsize) \
> +( \
> +    (pv)->cap == (newsize) /* nothing to do */ || \
> +    ( \
> +        (newsize) > 0 ? vlc_vector_realloc_(pv, newsize) \
> +                      : (vlc_vector_clear(pv), true) \
> +    ) \
> +)
> +
> +static inline size_t
> +vlc_vector_growsize_(size_t value)
> +{
> +    /* integer multiplication by 1.5 */
> +    return value + (value >> 1);
> +}
> +
> +/* SIZE_MAX/2 to fit in ssize_t, and so that cap*1.5 does not overflow. */
> +#define vlc_vector_max_cap_(pv) (SIZE_MAX / 2 / sizeof(*(pv)->data))
> +
> +/**
> + * Increase the capacity of the vector to at least `mincap`.
> + *
> + * \param pv a pointer to the vector
> + * \param mincap (size_t) the requested capacity
> + * \retval true if no allocation failed
> + * \retval false on allocation failure (the vector is left untouched)
> + */
> +#define vlc_vector_reserve(pv, mincap) \
> +    /* avoid to allocate tiny arrays (< VLC_VECTOR_MINCAP_) */ \
> +    vlc_vector_reserve_internal_(pv, \
> +                                 vlc_vector_max_(mincap,
> VLC_VECTOR_MINCAP_)) +
> +#define vlc_vector_reserve_internal_(pv, mincap) \
> +( \
> +    (mincap) <= (pv)->cap /* nothing to do */ || \
> +    ( \
> +        (mincap) <= vlc_vector_max_cap_(pv) /* not too big */ && \
> +        vlc_vector_realloc_(pv, \
> +                        /* multiply by 1.5, force between [mincap, maxcap]
> */ \ +                       
> vlc_vector_between_(vlc_vector_growsize_((pv)->cap), \ +                   
>                         mincap, \
> +                                            vlc_vector_max_cap_(pv))) \
> +    ) \
> +)
> +
> +/**
> + * Resize the vector so that its capacity equals its actual size.
> + *
> + * \param pv a pointer to the vector
> + */
> +#define vlc_vector_shrink_to_fit(pv) \
> +    (void) /* decreasing the size may not fail */ \
> +    vlc_vector_resize(pv, (pv)->size)
> +
> +/**
> + * Resize the vector down automatically.
> + *
> + * Shrink only when necessary (in practice when cap > (size+5)*1.5)
> + *
> + * \param pv a pointer to the vector
> + */
> +#define vlc_vector_autoshrink(pv) (void) \
> +( \
> +    (pv)->cap <= VLC_VECTOR_MINCAP_ /* do not shrink to tiny length */ || \
> +    (pv)->cap < vlc_vector_growsize_((pv)->size+5) /* no need to shrink */
> || \ +    vlc_vector_resize(pv, vlc_vector_max_((pv)->size+5,
> VLC_VECTOR_MINCAP_)) \ +)
> +
> +/**
> + * Push an item at the end of the vector.
> + *
> + * The amortized complexity is O(1).
> + *
> + * \param pv a pointer to the vector
> + * \param item the item to append
> + * \retval true if no allocation failed
> + * \retval false on allocation failure (the vector is left untouched)
> + */
> +#define vlc_vector_push(pv, item) \
> +( \
> +    vlc_vector_reserve(pv, (pv)->size + 1) && \
> +    ( \
> +        (pv)->data[(pv)->size++] = (item), \
> +        true \
> +    ) \
> +)
> +
> +/**
> + * Insert an item at the given index.
> + *
> + * The items in range [index; size-1] will be moved.
> + *
> + * \param pv a pointer to the vector
> + * \param index the index where the item is to be inserted
> + * \param item the item to append
> + * \retval true if no allocation failed
> + * \retval false on allocation failure (the vector is left untouched)
> + */
> +#define vlc_vector_insert(pv, index, item) \
> +    vlc_vector_insert_internal_(pv, vlc_vector_enforce_size_t_(index),
> item) +
> +#define vlc_vector_insert_internal_(pv, index, item) \
> +( \
> +    vlc_vector_reserve(pv, (pv)->size + 1) && \
> +    ( \
> +        (index) == (pv)->size || \
> +        ( \
> +            memmove(&(pv)->data[(index) + 1], \
> +                    &(pv)->data[index], \
> +                    ((pv)->size - (index)) * sizeof(*(pv)->data)), \
> +            true \
> +        ) \
> +    ) && \
> +    ( \
> +        (pv)->data[index] = (item), \
> +        (pv)->size++, \
> +        true \
> +    ) \
> +)
> +
> +/**
> + * Insert `count` items at the given index.
> + *
> + * The items in range [index; size-1] will be moved.
> + *
> + * \param pv a pointer to the vector
> + * \param index the index where the items are to be inserted
> + * \param items the items array to append
> + * \param count the number of items in the array
> + * \retval true if no allocation failed
> + * \retval false on allocation failure (the vector is left untouched)
> + */
> +#define vlc_vector_insert_all(pv, index, items, count) \
> +    vlc_vector_insert_all_internal_(pv, vlc_vector_enforce_size_t_(index),
> \ +                                    items,
> vlc_vector_enforce_size_t_(count)) +
> +#define vlc_vector_check_same_ptr_type_(a, b) \
> +    (void) ((a) == (b)) /* warn on type mismatch */

In C, you can even fail on type mismatch using _Generic.

> +
> +#define vlc_vector_insert_all_internal_(pv, index, items, count) \
> +( \
> +    vlc_vector_check_same_ptr_type_((pv)->data, items), \
> +    vlc_vector_reserve(pv, (pv)->size + (count)) && \
> +    ( \
> +        (index) == (pv)->size || \
> +        ( \
> +            memmove(&(pv)->data[(index) + (count)], \
> +                    &(pv)->data[index], \
> +                    ((pv)->size - (index)) * sizeof(*(pv)->data)), \
> +            true \
> +        ) \
> +    ) && \
> +    ( \
> +        memcpy(&(pv)->data[index], items, (count) * sizeof(*(pv)->data)), \
> +        (pv)->size += (count), \
> +        true \
> +    ) \
> +)
> +
> +/**
> + * Remove a slice of items, without shrinking the array.
> + *
> + * If you have no good reason to use the _noshrink() version, use
> + * vlc_vector_remove_slice() instead.
> + *
> + * The items in range [index+count; size-1] will be moved.
> + *
> + * \param pv a pointer to the vector
> + * \param index the index of the first item to remove
> + * \param count the number of items to remove
> + */
> +#define vlc_vector_remove_slice_noshrink(pv, index, count) \
> +    vlc_vector_remove_slice_noshrink_internal_(pv, \
> +            vlc_vector_enforce_size_t_(index), \
> +            vlc_vector_enforce_size_t_(count))
> +
> +#define vlc_vector_remove_slice_noshrink_internal_(pv, index, count) \
> +    do { \
> +        if ((index) + (count) < (pv)->size) \
> +            memmove(&(pv)->data[index], \
> +                    &(pv)->data[(index) + (count)], \
> +                    ((pv)->size - (index) - (count)) *
> sizeof(*(pv)->data)); \
> +        (pv)->size -= (count); \
> +    } while (0)
> +
> +/**
> + * Remove a slice of items.
> + *
> + * The items in range [index+count; size-1] will be moved.
> + *
> + * \param pv a pointer to the vector
> + * \param index the index of the first item to remove
> + * \param count the number of items to remove
> + */
> +#define vlc_vector_remove_slice(pv, index, count) \
> +    do { \
> +        vlc_vector_remove_slice_noshrink(pv, index, count); \
> +        vlc_vector_autoshrink(pv); \
> +    } while (0)
> +
> +/**
> + * Remove an item, without shrinking the array.
> + *
> + * If you have no good reason to use the _noshrink() version, use
> + * vlc_vector_remove() instead.
> + *
> + * The items in range [index+1; size-1] will be moved.
> + *
> + * \param pv a pointer to the vector
> + * \param index the index of item to remove
> + */
> +#define vlc_vector_remove_noshrink(pv, index) \
> +    vlc_vector_remove_slice_noshrink(pv, index, 1)
> +
> +/**
> + * Remove an item.
> + *
> + * The items in range [index+1; size-1] will be moved.
> + *
> + * \param pv a pointer to the vector
> + * \param index the index of item to remove
> + */
> +#define vlc_vector_remove(pv, index) \
> +    do { \
> +        vlc_vector_remove_noshrink(pv, index); \
> +        vlc_vector_autoshrink(pv); \
> +    } while (0)
> +
> +/**
> + * Remove an item.
> + *
> + * The removed item is replaced by the last item of the vector.
> + *
> + * This does not preserve ordering, but is O(1). This is useful when the
> order + * of items is not meaningful.
> + *
> + * \param pv a pointer to the vector
> + * \param index the index of item to remove
> + */
> +#define vlc_vector_swap_remove(pv, index) \
> +    (pv)->data[index] = (pv)->data[--(pv)->size]
> +
> +/**
> + * Return the index of an item.
> + *
> + * Iterate over all items to find a given item.
> + *
> + * Use only for vectors of primitive types or pointers.
> + *
> + * The result is written to `*(pidx)`:
> + *  - the index of the item if it is found;
> + *  - -1 if it is not found.
> + *
> + * \param pv a pointer to the vector
> + * \param item the item to find (compared with ==)
> + * \param a pointer to the result (ssize_t *) [OUT]
> + */
> +#define vlc_vector_index_of(pv, item, pidx) \
> +    do { \
> +        ssize_t *out = pidx; /* warning/error on type mismatch */ \
> +        size_t vlc_vector_find_idx_; \
> +        for (vlc_vector_find_idx_ = 0; \
> +             vlc_vector_find_idx_ < (pv)->size; \
> +             ++vlc_vector_find_idx_) \
> +            if ((pv)->data[vlc_vector_find_idx_] == (item)) \
> +                break; \
> +        *out = vlc_vector_find_idx_ == (pv)->size ? -1 : \
> +            (ssize_t) vlc_vector_find_idx_; \
> +    } while (0)
> +
> +/**
> + * For-each loop.
> + *
> + * Use only for vectors of primitive types or pointers (every struct would
> be + * copied for a vector of structs).
> + *
> + * \param item the iteration variable [OUT]
> + * \param pv a pointer to the vector [OUT]
> + */
> +#define vlc_vector_foreach(item, pv) \
> +    for (size_t vlc_vector_idx_##item = 0; \
> +         vlc_vector_idx_##item < (pv)->size && \
> +             ((item) = (pv)->data[vlc_vector_idx_##item], true); \
> +         ++vlc_vector_idx_##item)
> +
> +/** @} */
> +
> +#endif

-- 
Реми Дёни-Курмон
http://www.remlab.net/