[vlc-devel] [RFC 1/1] vlc_vector: add helpers for vectors
Thomas Guillem
thomas at gllm.fr
Thu Aug 30 11:11:44 CEST 2018
On Thu, Aug 30, 2018, at 11:03, Zhao Zhili wrote:
>
>
> On 2018年08月30日 04:28, Romain Vimont wrote:
> > 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).
> > ---
> > include/vlc_common.h | 6 +
> > include/vlc_vector.h | 397 +++++++++++++++++++++++++++++++++++++++++++
> > src/Makefile.am | 5 +-
> > src/test/vector.c | 362 +++++++++++++++++++++++++++++++++++++++
> > 4 files changed, 769 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..feda4dbcaf
> > --- /dev/null
> > +++ b/include/vlc_vector.h
> > @@ -0,0 +1,397 @@
> > +/******************************************************************************
> > + * 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 { \
> > + .cap = 0, \
> > + .size = 0, \
> > + .data = NULL, \
> > +}
>
> ISO C++ does not allow C99 designated initializers.
It's a C API. C++ code should use std::vector and not this C helper.
>
> > +
> > +/**
> > + * Initialize an empty vector.
> > + */
> > +#define vlc_vector_init(pv) \
> > + /* cannot be implemened as do-while(0), called from vlc_vector_clear() */ \
> > + (void) \
> > + (((pv)->cap = 0, true) && \
> > + ((pv)->size = 0, true) && \
> > + ((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() */ \
> > + (void) \
> > + ((free((pv)->data), true) && \
> > + (vlc_vector_init(pv), true))
> > +
> > +/**
> > + * 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 void *
> > +vlc_vector_reallocarray_or_free_(void *ptr, size_t count, size_t size)
> > +{
> > + void *n = vlc_reallocarray(ptr, count, size);
> > + if (unlikely(!n))
> > + free(ptr);
> > + return n;
> > +}
> > +
> > +/**
> > + * 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 (in that case, the vector is left in an
> > + * invalid state and must be cleared to be reused)
> > + */
> > +#define vlc_vector_realloc_(pv, newsize) \
> > + (((pv)->cap = (newsize), true) && \
> > + ((pv)->size = vlc_vector_min_((pv)->size, newsize), true) && \
> > + ((pv)->data = vlc_vector_reallocarray_or_free_( \
> > + (pv)->data, newsize, sizeof(*(pv)->data))))
> > +
> > +/**
> > + * 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 (in that case, the vector is left in an
> > + * invalid state and must be cleared to be reused)
> > + */
> > +#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 (in that case, the vector is left in an
> > + * invalid state and must be cleared to be reused)
> > + */
> > +#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) \
> > + ((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 (in that case, the vector is left in an
> > + * invalid state and must be cleared to be reused)
> > + */
> > +#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 (in that case, the vector is left in an
> > + * invalid state and must be cleared to be reused)
> > + */
> > +#define vlc_vector_insert(pv, index, item) \
> > + (vlc_vector_reserve(pv, (pv)->size + 1) && \
> > + (((size_t)(index) == (pv)->size) || \
> > + (memmove(&(pv)->data[(size_t)(index) + 1], \
> > + &(pv)->data[(size_t)(index)], \
> > + ((pv)->size - (size_t)(index)) * sizeof(*(pv)->data)), \
> > + true)) && \
> > + ((pv)->data[index] = (item), true) && \
> > + ((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 (in that case, the vector is left in an
> > + * invalid state and must be cleared to be reused)
> > + */
> > +#define vlc_vector_insert_all(pv, index, items, count) \
> > + (vlc_vector_reserve(pv, (pv)->size + (size_t)(count)) && \
> > + (((size_t)(index) == (pv)->size) || \
> > + (memmove(&(pv)->data[(size_t)(index) + (size_t)(count)], \
> > + &(pv)->data[(size_t)(index)], \
> > + ((pv)->size - (size_t)(index)) * sizeof(*(pv)->data)), \
> > + true)) && \
> > + (memcpy(&(pv)->data[(size_t)(index)], items, \
> > + (size_t)(count) * sizeof(*(pv)->data)), true) && \
> > + ((pv)->size += (size_t)(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) \
> > + do { \
> > + if ((size_t)(index) + (size_t)(count) < (pv)->size) \
> > + memmove(&(pv)->data[(size_t)(index)], \
> > + &(pv)->data[(size_t)(index) + (size_t)(count)], \
> > + ((pv)->size - (size_t)(index) - (size_t)(count)) \
> > + * sizeof(*(pv)->data)); \
> > + (pv)->size -= (size_t)(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.
> > + *
> > + * 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 { \
> > + 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; \
> > + *(pidx) = vlc_vector_find_idx_ == (pv)->size ? -1 : \
> > + (ssize_t) vlc_vector_find_idx_; \
> > + } while (0)
> > +
> > +/**
> > + * For-each loop.
> > + *
> > + * \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..85c8d94aa2
> > --- /dev/null
> > +++ b/src/test/vector.c
> > @@ -0,0 +1,362 @@
> > +/*****************************************************************************
> > + * 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_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);
> > +}
> > +
> > +int main(void) {
> > + test_vector_insert_remove();
> > + test_vector_insert_array();
> > + test_vector_remove_slice();
> > + test_vector_swap_remove();
> > + test_vector_index_of();
> > + test_vector_foreach();
> > + test_vector_grow();
> > + test_vector_exp_growth();
> > + test_vector_reserve();
> > + test_vector_shrink_to_fit();
> > + return 0;
> > +}
>
> _______________________________________________
> 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