[vlc-devel] [PATCH v6] vlc_vector: add helpers for vectors
Romain Vimont
rom1v at videolabs.io
Fri Oct 5 21:32:38 CEST 2018
Thank you for your review.
On Fri, Oct 05, 2018 at 08:20:09PM +0300, Rémi Denis-Courmont wrote:
> Le perjantaina 5. lokakuuta 2018, 18.29.05 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 to the end of the vector
> > - bool vlc_vector_push_all(pv, items, count)
> > push serveral items to 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_move(pv, index, target)
> > move an item to target
> > - void vlc_vector_move_all(pv, index, count, target)
> > move a slice of items to target
> > - 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 RFC v5:
> > - add vlc_vector_push_all() to push a slice items to the end of a vector
> > - add vlc_vector_move() to move an item
> > - add vlc_vector_move_all() to move a slice of items
> > - add vlc_vector_insert_hole() to make space for items that the caller can
> > initialize in place
> >
> > include/vlc_common.h | 6 +
> > include/vlc_vector.h | 628 +++++++++++++++++++++++++++++++++++++++++++
> > src/Makefile.am | 5 +-
> > src/test/vector.c | 481 +++++++++++++++++++++++++++++++++
> > 4 files changed, 1119 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
>
> I don't see how the GCC malloc attribute applies to realloc result.
OK, thank you, it was just copied from the vlc_alloc() just above.
> > +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..b95b9cec43
> > --- /dev/null
> > +++ b/include/vlc_vector.h
> > @@ -0,0 +1,628 @@
> > +/**************************************************************************
> > **** + * 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) \
> > +)
>
> Bad naming. This does not actually clear anything.
Why do you say that it does not clear anything? It clears the vector.
Before the call, the vector has any number of items, after the call,
it's empty.
> > +
> > +/**
> > + * 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));
> > +}
> > +
> > +static inline size_t
> > +vlc_vector_enforce_size_t_(size_t value)
> > +{
> > + return value;
> > +}
> > +
> > +#define VLC_VECTOR_FAILFLAG_ (~(((size_t) -1) >> 1)) /* only the MSB */
> > +
> > +/**
> > + * Realloc data and update vector fields.
> > + *
> > + * On reallocation success, return the reallocated array and update the
> > vector + * capacity and size.
> > + *
> > + * On reallocation failure, return `ptr`, keep `*psize` untouched, and set
> > the + * failflag in `*pcap` to indicate allocation failure (to be consumed
> > by + * `vlc_vector_test_and_reset_failflag_()`).
> > + *
> > + * This weird behavior allows to simultaneously:
> > + * - not require compiler extensions like "statement expressions"
> > + * - keep the vector data, size and capacity unchanged on reallocation
> > failure + * - not require output variables other than vector fields from
> > the caller + * - not violate the strict aliasing rules
> > + * - report the reallocation status (success or failure)
> > + *
> > + * Private.
> > + *
> > + * \param ptr the current data to realloc
> > + * \param the requested capacity, in number of items
> > + * \param the size of one item
> > + * \pcap a pointer to the `cap` field of the vector [IN/OUT]
> > + * \pcap a pointer to the `size` field of the vector [IN/OUT]
> > + * \return the reallocated array, or `ptr` if reallocation failed
> > + */
> > +static inline void *
> > +vlc_vector_reallocdata_(void *ptr, size_t count, size_t size,
> > + size_t *pcap, size_t *psize)
>
> Could use some restrict.
OK, I will add 3 restricts (I'm not used to add "restrict" in my code).
>
> > +{
> > + void *n = vlc_reallocarray(ptr, count, size);
> > + if (!n)
> > + {
> > + /* this vector implementation guarantees that the capacity may not
> > + * exceed SIZE_MAX/2 (to prevent overflows), so we can use the MSB
> > to + * report allocation failure */
>
> I do not see how that assumption is meant if the array element is 1 byte.
If the array element is 1 byte, the maximum number of items stored by
the vector is SIZE_MAX/2 (appending a new item will report an allocation
failure):
vlc_vector_max_cap_(pv) (SIZE_MAX / 2 / sizeof(*(pv)->data))
Even in that case, the MSB is unused.
>
> > + *pcap |= VLC_VECTOR_FAILFLAG_;
> > + return ptr;
> > + }
> > + *pcap = count;
> > + *psize = vlc_vector_min_(*psize, count);
> > + return n;
> > +}
> > +
> > +/**
> > + * Test and reset the fail flag.
> > + *
> > + * \retval true if the flag was set
> > + * \retval false if the flag was not set
> > + */
> > +static inline bool
> > +vlc_vector_test_and_reset_failflag_(size_t *pcap)
> > +{
> > + if (*pcap & VLC_VECTOR_FAILFLAG_)
> > + {
> > + *pcap &= ~VLC_VECTOR_FAILFLAG_;
> > + return true;
> > + }
> > + return false;
> > +}
> > +
> > +/**
> > + * Realloc the underlying array to `newcap`.
> > + *
> > + * Private.
> > + *
> > + * \param pv a pointer to the vector
> > + * \param newcap (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, newcap) \
> > +( \
> > + (pv)->data = vlc_vector_reallocdata_((pv)->data, newcap, \
> > + sizeof(*(pv)->data), \
> > + &(pv)->cap, &(pv)->size), \
> > + !vlc_vector_test_and_reset_failflag_(&(pv)->cap) \
> > +)
> > +
> > +/**
> > + * Resize the vector to `newcap` exactly.
> > + *
> > + * If `newcap` is 0, the vector is cleared.
> > + *
> > + * \param pv a pointer to the vector
> > + * \param newcap (size_t) the requested capacity
> > + * \retval true if no allocation failed
> > + * \retval false on allocation failure (the vector is left untouched)
> > + */
> > +#define vlc_vector_resize(pv, newcap) \
> > +( \
> > + (pv)->cap == (newcap) /* nothing to do */ || \
> > + ( \
> > + (newcap) > 0 ? vlc_vector_realloc_(pv, newcap) \
> > + : (vlc_vector_clear(pv), true) \
> > + ) \
> > +)
>
> Multiple expansion of newcap could cause problems?
In practice, probably not, but avoiding multiple expansion would be
better.
>
> > +
> > +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_)) \ +)
> > +
> > +#define vlc_vector_check_same_ptr_type_(a, b) \
> > + (void) ((a) == (b)) /* warn on type mismatch */
> > +
> > +/**
> > + * 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 \
> > + ) \
> > +)
> > +
> > +/**
> > + * Append `count` items at the end of the vector.
> > + *
> > + * \param pv a pointer to the vector
> > + * \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_push_all(pv, items, count) \
> > + vlc_vector_push_all_internal_(pv, items,
> > vlc_vector_enforce_size_t_(count)) +
> > +#define vlc_vector_push_all_internal_(pv, items, count) \
> > +( \
> > + vlc_vector_check_same_ptr_type_((pv)->data, items), \
> > + vlc_vector_reserve(pv, (pv)->size + (count)) && \
> > + ( \
> > + memcpy(&(pv)->data[(pv)->size], items, (count) *
> > sizeof(*(pv)->data)), \ + (pv)->size += (count), \
> > + true \
> > + ) \
> > +)
> > +
> > +/**
> > + * Insert an hole of size `count` to the given index.
> > + *
> > + * The items in range [index; size-1] will be moved. The items in the hole
> > are + * left uninitialized.
> > + *
> > + * \param pv a pointer to the vector
> > + * \param index the index where the hole is to be inserted
> > + * \param count the number of items in the hole
> > + * \retval true if no allocation failed
> > + * \retval false on allocation failure (the vector is left untouched)
> > + */
> > +#define vlc_vector_insert_hole(pv, index, count) \
> > + vlc_vector_insert_hole_internal_(pv, vlc_vector_enforce_size_t_(index),
> > \ + vlc_vector_enforce_size_t_(count))
> > +
> > +#define vlc_vector_insert_hole_internal_(pv, index, count) \
> > +( \
> > + 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 \
> > + ) \
> > + ) && \
> > + ( \
> > + (pv)->size += (count), \
> > + 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_hole(pv, index, 1) && \
> > + ( \
> > + (pv)->data[index] = (item), \
> > + 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_check_same_ptr_type_((pv)->data, items), \
> > + vlc_vector_insert_hole(pv, index, count) && \
> > + ( \
> > + memcpy(&(pv)->data[index], items, (count) * sizeof(*(pv)->data)), \
> > + true \
> > + ) \
> > +)
> > +
> > +/** Reverse a char array in place. */
> > +static inline void
> > +vlc_vector_reverse_array_(char *array, size_t len)
> > +{
> > + for (size_t i = 0; i < len / 2; ++i)
> > + {
> > + char c = array[i];
> > + array[i] = array[len - i - 1];
> > + array[len - i - 1] = c;
> > + }
> > +}
> > +
> > +/**
> > + * Right-rotate a (char) array in place.
> > + *
> > + * For example, left-rotating a char array containing {1, 2, 3, 4, 5, 6}
> > with + * distance 4 will result in {5, 6, 1, 2, 3, 4}.
> > + *
> > + * Private.
> > + */
> > +static inline void
> > +vlc_vector_rotate_array_left_(char *array, size_t len, size_t distance)
> > +{
> > + vlc_vector_reverse_array_(array, distance);
> > + vlc_vector_reverse_array_(&array[distance], len - distance);
> > + vlc_vector_reverse_array_(array, len);
> > +}
> > +
> > +/**
> > + * Right-rotate a (char) array in place.
> > + *
> > + * For example, left-rotating a char array containing {1, 2, 3, 4, 5, 6}
> > with + * distance 2 will result in {5, 6, 1, 2, 3, 4}.
> > + *
> > + * Private.
> > + */
> > +static inline void
> > +vlc_vector_rotate_array_right_(char *array, size_t len, size_t distance)
> > +{
> > + vlc_vector_rotate_array_left_(array, len, len - distance);
> > +}
> > +
> > +/**
> > + * Move items in a (char) array in place.
> > + *
> > + * Move slice [index, count] to target.
> > + */
> > +static inline void
> > +vlc_vector_move_(char *array, size_t index, size_t count, size_t target)
> > +{
> > + if (index < target)
> > + vlc_vector_rotate_array_left_(&array[index], target - index +
> > count, + count);
> > + else
> > + vlc_vector_rotate_array_right_(&array[target], index - target +
> > count, + count);
> > +}
> > +
> > +/**
> > + * Move a slice of items to a given target index.
> > + *
> > + * The items in range [index; count] will be moved so that the *new*
> > position + * of the first item is `target`.
> > + *
> > + * \param pv a pointer to the vector
> > + * \param index the index of the first item to move
> > + * \param count the number of items to move
> > + * \param target the new index of the moved slice
> > + */
> > +#define vlc_vector_move_slice(pv, index, count, target) \
> > + vlc_vector_move_slice_internal_(pv, \
> > + vlc_vector_enforce_size_t_(index), \
> > + vlc_vector_enforce_size_t_(count), \
> > + vlc_vector_enforce_size_t_(target))
> > +
> > +#define vlc_vector_move_slice_internal_(pv, index, count, target) \
> > + vlc_vector_move_((char *) (pv)->data, \
> > + (index) * sizeof((pv)->data[0]), \
> > + (count) * sizeof((pv)->data[0]), \
> > + (target) * sizeof((pv)->data[0]))
> > +
> > +/**
> > + * Move an item to a given target index.
> > + *
> > + * The items will be moved so that its *new* position is `target`.
> > + *
> > + * \param pv a pointer to the vector
> > + * \param index the index of the item to move
> > + * \param target the new index of the moved item
> > + */
> > +#define vlc_vector_move(pv, index, target) \
> > + vlc_vector_move_slice(pv, index, 1, target)
> > +
> > +/**
> > + * 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
> > diff --git a/src/Makefile.am b/src/Makefile.am
> > index 1802dedf58..5ede6c9ee0 100644
> > --- a/src/Makefile.am
> > +++ b/src/Makefile.am
> > @@ -97,6 +97,7 @@ pluginsinclude_HEADERS = \
> > ../include/vlc_tls.h \
> > ../include/vlc_url.h \
> > ../include/vlc_variables.h \
> > + ../include/vlc_vector.h \
> > ../include/vlc_viewpoint.h \
> > ../include/vlc_vlm.h \
> > ../include/vlc_video_splitter.h \
> > @@ -524,7 +525,8 @@ check_PROGRAMS = \
> > test_xmlent \
> > test_headers \
> > test_mrl_helpers \
> > - test_arrays
> > + test_arrays \
> > + test_vector
> >
> > TESTS = $(check_PROGRAMS) check_symbols
> >
> > @@ -547,6 +549,7 @@ test_xmlent_SOURCES = test/xmlent.c
> > test_headers_SOURCES = test/headers.c
> > test_mrl_helpers_SOURCES = test/mrl_helpers.c
> > test_arrays_SOURCES = test/arrays.c
> > +test_vector_SOURCES = test/vector.c
> >
> > AM_LDFLAGS = -no-install
> > LDADD = libvlccore.la \
> > diff --git a/src/test/vector.c b/src/test/vector.c
> > new file mode 100644
> > index 0000000000..5f0a6fb54a
> > --- /dev/null
> > +++ b/src/test/vector.c
> > @@ -0,0 +1,481 @@
> > +/**************************************************************************
> > *** + * vector.c : Test for vlc_vector macros
> > +
> > ***************************************************************************
> > ** + * Copyright (C) 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. +
> > ***************************************************************************
> > **/ +
> > +#ifdef HAVE_CONFIG_H
> > +# include "config.h"
> > +#endif
> > +
> > +#undef NDEBUG
> > +
> > +#include <assert.h>
> > +
> > +#include <vlc_common.h>
> > +#include <vlc_vector.h>
> > +
> > +static void test_vector_insert_remove(void)
> > +{
> > + struct VLC_VECTOR(int) vec = VLC_VECTOR_INITIALIZER;
> > +
> > + bool ok;
> > +
> > + ok = vlc_vector_push(&vec, 42);
> > + assert(ok);
> > + assert(vec.data[0] == 42);
> > + assert(vec.size == 1);
> > +
> > + ok = vlc_vector_push(&vec, 37);
> > + assert(ok);
> > + assert(vec.size == 2);
> > + assert(vec.data[0] == 42);
> > + assert(vec.data[1] == 37);
> > +
> > + ok = vlc_vector_insert(&vec, 1, 100);
> > + assert(ok);
> > + assert(vec.size == 3);
> > + assert(vec.data[0] == 42);
> > + assert(vec.data[1] == 100);
> > + assert(vec.data[2] == 37);
> > +
> > + ok = vlc_vector_push(&vec, 77);
> > + assert(ok);
> > + assert(vec.size == 4);
> > + assert(vec.data[0] == 42);
> > + assert(vec.data[1] == 100);
> > + assert(vec.data[2] == 37);
> > + assert(vec.data[3] == 77);
> > +
> > + vlc_vector_remove(&vec, 1);
> > + assert(vec.size == 3);
> > + assert(vec.data[0] == 42);
> > + assert(vec.data[1] == 37);
> > + assert(vec.data[2] == 77);
> > +
> > + vlc_vector_clear(&vec);
> > + assert(vec.cap == 0);
> > + assert(vec.size == 0);
> > + assert(vec.data == NULL);
> > +}
> > +
> > +static void test_vector_push_array(void)
> > +{
> > + struct VLC_VECTOR(int) vec = VLC_VECTOR_INITIALIZER;
> > + bool ok;
> > +
> > + ok = vlc_vector_push(&vec, 3); assert(ok);
> > + ok = vlc_vector_push(&vec, 14); assert(ok);
> > + ok = vlc_vector_push(&vec, 15); assert(ok);
> > + ok = vlc_vector_push(&vec, 92); assert(ok);
> > + ok = vlc_vector_push(&vec, 65); assert(ok);
> > + assert(vec.size == 5);
> > +
> > + int items[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
> > + ok = vlc_vector_push_all(&vec, items, 8);
> > +
> > + assert(ok);
> > + assert(vec.size == 13);
> > + assert(vec.data[0] == 3);
> > + assert(vec.data[1] == 14);
> > + assert(vec.data[2] == 15);
> > + assert(vec.data[3] == 92);
> > + assert(vec.data[4] == 65);
> > + assert(vec.data[5] == 1);
> > + assert(vec.data[6] == 2);
> > + assert(vec.data[7] == 3);
> > + assert(vec.data[8] == 4);
> > + assert(vec.data[9] == 5);
> > + assert(vec.data[10] == 6);
> > + assert(vec.data[11] == 7);
> > + assert(vec.data[12] == 8);
> > +
> > + vlc_vector_clear(&vec);
> > +}
> > +
> > +static void test_vector_insert_array(void)
> > +{
> > + struct VLC_VECTOR(int) vec = VLC_VECTOR_INITIALIZER;
> > + bool ok;
> > +
> > + ok = vlc_vector_push(&vec, 3); assert(ok);
> > + ok = vlc_vector_push(&vec, 14); assert(ok);
> > + ok = vlc_vector_push(&vec, 15); assert(ok);
> > + ok = vlc_vector_push(&vec, 92); assert(ok);
> > + ok = vlc_vector_push(&vec, 65); assert(ok);
> > + assert(vec.size == 5);
> > +
> > + int items[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
> > + ok = vlc_vector_insert_all(&vec, 3, items, 8);
> > + assert(ok);
> > + assert(vec.size == 13);
> > + assert(vec.data[0] == 3);
> > + assert(vec.data[1] == 14);
> > + assert(vec.data[2] == 15);
> > + assert(vec.data[3] == 1);
> > + assert(vec.data[4] == 2);
> > + assert(vec.data[5] == 3);
> > + assert(vec.data[6] == 4);
> > + assert(vec.data[7] == 5);
> > + assert(vec.data[8] == 6);
> > + assert(vec.data[9] == 7);
> > + assert(vec.data[10] == 8);
> > + assert(vec.data[11] == 92);
> > + assert(vec.data[12] == 65);
> > +
> > + vlc_vector_clear(&vec);
> > +}
> > +
> > +static void test_vector_remove_slice(void)
> > +{
> > + struct VLC_VECTOR(int) vec = VLC_VECTOR_INITIALIZER;
> > +
> > + bool ok;
> > +
> > + for (int i = 0; i < 100; ++i)
> > + {
> > + ok = vlc_vector_push(&vec, i);
> > + assert(ok);
> > + }
> > +
> > + assert(vec.size == 100);
> > +
> > + vlc_vector_remove_slice(&vec, 32, 60);
> > + assert(vec.size == 40);
> > + assert(vec.data[31] == 31);
> > + assert(vec.data[32] == 92);
> > +
> > + vlc_vector_clear(&vec);
> > +}
> > +
> > +static void test_vector_swap_remove(void)
> > +{
> > + struct VLC_VECTOR(int) vec = VLC_VECTOR_INITIALIZER;
> > +
> > + bool ok;
> > +
> > + ok = vlc_vector_push(&vec, 3); assert(ok);
> > + ok = vlc_vector_push(&vec, 14); assert(ok);
> > + ok = vlc_vector_push(&vec, 15); assert(ok);
> > + ok = vlc_vector_push(&vec, 92); assert(ok);
> > + ok = vlc_vector_push(&vec, 65); assert(ok);
> > + assert(vec.size == 5);
> > +
> > + vlc_vector_swap_remove(&vec, 1);
> > + assert(vec.size == 4);
> > + assert(vec.data[0] == 3);
> > + assert(vec.data[1] == 65);
> > + assert(vec.data[2] == 15);
> > + assert(vec.data[3] == 92);
> > +
> > + vlc_vector_clear(&vec);
> > +}
> > +
> > +static void test_vector_index_of(void)
> > +{
> > + struct VLC_VECTOR(int) vec;
> > + vlc_vector_init(&vec);
> > +
> > + bool ok;
> > +
> > + for (int i = 0; i < 10; ++i)
> > + {
> > + ok = vlc_vector_push(&vec, i);
> > + assert(ok);
> > + }
> > +
> > + ssize_t idx;
> > +
> > + vlc_vector_index_of(&vec, 0, &idx);
> > + assert(idx == 0);
> > +
> > + vlc_vector_index_of(&vec, 1, &idx);
> > + assert(idx == 1);
> > +
> > + vlc_vector_index_of(&vec, 4, &idx);
> > + assert(idx == 4);
> > +
> > + vlc_vector_index_of(&vec, 9, &idx);
> > + assert(idx == 9);
> > +
> > + vlc_vector_index_of(&vec, 12, &idx);
> > + assert(idx == -1);
> > +
> > + vlc_vector_clear(&vec);
> > +}
> > +
> > +static void test_vector_foreach(void)
> > +{
> > + struct VLC_VECTOR(int) vec = VLC_VECTOR_INITIALIZER;
> > +
> > + bool ok;
> > +
> > + for (int i = 0; i < 10; ++i)
> > + {
> > + ok = vlc_vector_push(&vec, i);
> > + assert(ok);
> > + }
> > +
> > + int count = 0;
> > + int item;
> > + vlc_vector_foreach(item, &vec)
> > + {
> > + assert(item == count);
> > + count++;
> > + }
> > + assert(count == 10);
> > +
> > + vlc_vector_clear(&vec);
> > +}
> > +
> > +static void test_vector_grow()
> > +{
> > + struct VLC_VECTOR(int) vec = VLC_VECTOR_INITIALIZER;
> > +
> > + bool ok;
> > +
> > + for (int i = 0; i < 50; ++i)
> > + {
> > + ok = vlc_vector_push(&vec, i); /* append */
> > + assert(ok);
> > + }
> > +
> > + assert(vec.cap >= 50);
> > + assert(vec.size == 50);
> > +
> > + for (int i = 0; i < 25; ++i)
> > + {
> > + ok = vlc_vector_insert(&vec, 20, i); /* insert in the middle */
> > + assert(ok);
> > + }
> > +
> > + assert(vec.cap >= 75);
> > + assert(vec.size == 75);
> > +
> > + for (int i = 0; i < 25; ++i)
> > + {
> > + ok = vlc_vector_insert(&vec, 0, i); /* prepend */
> > + assert(ok);
> > + }
> > +
> > + assert(vec.cap >= 100);
> > + assert(vec.size == 100);
> > +
> > + for (int i = 0; i < 50; ++i)
> > + vlc_vector_remove(&vec, 20); /* remove from the middle */
> > +
> > + assert(vec.cap >= 50);
> > + assert(vec.size == 50);
> > +
> > + for (int i = 0; i < 25; ++i)
> > + vlc_vector_remove(&vec, 0); /* remove from the head */
> > +
> > + assert(vec.cap >= 25);
> > + assert(vec.size == 25);
> > +
> > + for (int i = 24; i >=0; --i)
> > + vlc_vector_remove(&vec, i); /* remove from the tail */
> > +
> > + assert(vec.size == 0);
> > +
> > + vlc_vector_clear(&vec);
> > +}
> > +
> > +static void test_vector_exp_growth(void)
> > +{
> > + struct VLC_VECTOR(int) vec = VLC_VECTOR_INITIALIZER;
> > +
> > + size_t oldcap = vec.cap;
> > + int realloc_count = 0;
> > + bool ok;
> > + for (int i = 0; i < 10000; ++i)
> > + {
> > + ok = vlc_vector_push(&vec, i);
> > + assert(ok);
> > + if (vec.cap != oldcap)
> > + {
> > + realloc_count++;
> > + oldcap = vec.cap;
> > + }
> > + }
> > +
> > + /* Test speciically for an expected growth factor of 1.5. In practice,
> > the + * result is even lower (19) due to the first alloc of size 10 */
> > + assert(realloc_count <= 23); /* ln(10000) / ln(1.5) ~= 23 */
> > +
> > + realloc_count = 0;
> > + for (int i = 9999; i >= 0; --i)
> > + {
> > + vlc_vector_remove(&vec, i);
> > + if (vec.cap != oldcap)
> > + {
> > + realloc_count++;
> > + oldcap = vec.cap;
> > + }
> > + }
> > +
> > + assert(realloc_count <= 23); /* same expectations for removals */
> > + assert(realloc_count > 0); /* vlc_vector_remove() must autoshrink */
> > +
> > + vlc_vector_clear(&vec);
> > +}
> > +
> > +static void test_vector_reserve(void)
> > +{
> > + struct VLC_VECTOR(int) vec = VLC_VECTOR_INITIALIZER;
> > +
> > + bool ok;
> > +
> > + ok = vlc_vector_reserve(&vec, 800);
> > + assert(ok);
> > + assert(vec.cap >= 800);
> > + assert(vec.size == 0);
> > +
> > + size_t initial_cap = vec.cap;
> > +
> > + for (int i = 0; i < 800; ++i)
> > + {
> > + ok = vlc_vector_push(&vec, i);
> > + assert(ok);
> > + assert(vec.cap == initial_cap); /* no realloc */
> > + }
> > +
> > + vlc_vector_clear(&vec);
> > +}
> > +
> > +static void test_vector_shrink_to_fit(void)
> > +{
> > + struct VLC_VECTOR(int) vec = VLC_VECTOR_INITIALIZER;
> > +
> > + bool ok;
> > +
> > + ok = vlc_vector_reserve(&vec, 800);
> > + assert(ok);
> > + for (int i = 0; i < 250; ++i)
> > + {
> > + ok = vlc_vector_push(&vec, i);
> > + assert(ok);
> > + }
> > +
> > + assert(vec.cap >= 800);
> > + assert(vec.size == 250);
> > +
> > + vlc_vector_shrink_to_fit(&vec);
> > + assert(vec.cap == 250);
> > + assert(vec.size == 250);
> > +
> > + vlc_vector_clear(&vec);
> > +}
> > +
> > +static void test_vector_move(void)
> > +{
> > + struct VLC_VECTOR(int) vec = VLC_VECTOR_INITIALIZER;
> > +
> > + for (int i = 0; i < 7; ++i)
> > + {
> > + bool ok = vlc_vector_push(&vec, i);
> > + assert(ok);
> > + }
> > +
> > + /* move item at 1 so that its new position is 4 */
> > + vlc_vector_move(&vec, 1, 4);
> > +
> > + assert(vec.size == 7);
> > + assert(vec.data[0] == 0);
> > + assert(vec.data[1] == 2);
> > + assert(vec.data[2] == 3);
> > + assert(vec.data[3] == 4);
> > + assert(vec.data[4] == 1);
> > + assert(vec.data[5] == 5);
> > + assert(vec.data[6] == 6);
> > +
> > + vlc_vector_clear(&vec);
> > +}
> > +
> > +static void test_vector_move_slice_forward(void)
> > +{
> > + struct VLC_VECTOR(int) vec = VLC_VECTOR_INITIALIZER;
> > +
> > + for (int i = 0; i < 10; ++i)
> > + {
> > + bool ok = vlc_vector_push(&vec, i);
> > + assert(ok);
> > + }
> > +
> > + /* move slice {2, 3, 4, 5} so that its new position is 5 */
> > + vlc_vector_move_slice(&vec, 2, 4, 5);
> > +
> > + assert(vec.size == 10);
> > + assert(vec.data[0] == 0);
> > + assert(vec.data[1] == 1);
> > + assert(vec.data[2] == 6);
> > + assert(vec.data[3] == 7);
> > + assert(vec.data[4] == 8);
> > + assert(vec.data[5] == 2);
> > + assert(vec.data[6] == 3);
> > + assert(vec.data[7] == 4);
> > + assert(vec.data[8] == 5);
> > + assert(vec.data[9] == 9);
> > +
> > + vlc_vector_clear(&vec);
> > +}
> > +
> > +static void test_vector_move_slice_backward(void)
> > +{
> > + struct VLC_VECTOR(int) vec = VLC_VECTOR_INITIALIZER;
> > +
> > + for (int i = 0; i < 10; ++i)
> > + {
> > + bool ok = vlc_vector_push(&vec, i);
> > + assert(ok);
> > + }
> > +
> > + /* move slice {5, 6, 7} so that its new position is 2 */
> > + vlc_vector_move_slice(&vec, 5, 3, 2);
> > +
> > + assert(vec.size == 10);
> > + assert(vec.data[0] == 0);
> > + assert(vec.data[1] == 1);
> > + assert(vec.data[2] == 5);
> > + assert(vec.data[3] == 6);
> > + assert(vec.data[4] == 7);
> > + assert(vec.data[5] == 2);
> > + assert(vec.data[6] == 3);
> > + assert(vec.data[7] == 4);
> > + assert(vec.data[8] == 8);
> > + assert(vec.data[9] == 9);
> > +
> > + vlc_vector_clear(&vec);
> > +}
> > +
> > +int main(void) {
> > + test_vector_insert_remove();
> > + test_vector_push_array();
> > + test_vector_insert_array();
> > + test_vector_remove_slice();
> > + test_vector_swap_remove();
> > + test_vector_move();
> > + test_vector_move_slice_forward();
> > + test_vector_move_slice_backward();
> > + test_vector_index_of();
> > + test_vector_foreach();
> > + test_vector_grow();
> > + test_vector_exp_growth();
> > + test_vector_reserve();
> > + test_vector_shrink_to_fit();
> > + return 0;
> > +}
>
>
> --
> Rémi Denis-Courmont
> http://www.remlab.net/
>
>
>
>
> _______________________________________________
> 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