[vlc-devel] [PATCH v6] vlc_vector: add helpers for vectors
Rémi Denis-Courmont
remi at remlab.net
Fri Oct 5 19:20:09 CEST 2018
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.
> +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.
> +
> +/**
> + * 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.
> +{
> + 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.
> + *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?
> +
> +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/
More information about the vlc-devel
mailing list