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

[Romain Vimont]

Add a new API for handling general-purpose vectors, intended to replace
ARRAY_*.

Like ARRAY_*, it provides macros to handle a dynamic array generic
over the type of its items.

Contrary to ARRAY_*:
 - it does not abort on allocation failure (but reports the error);
 - it uses size_t instead of int to store the capacity and the size;
 - it checks for overflows on reallocation.

For illustration purpose, embedding a vector of input_item_t* in a
struct looks like:

    struct playlist {
        struct VLC_VECTOR(input_item_t *) items;
        // ...
    };

The main features (with names inspired by std::vector from C++ and
std::vec::Vec from Rust) are:
 - void vlc_vector_init(pv)
      init the vector (use VLC_VECTOR_INITIALIZER for static init)
 - void vlc_vector_clear(pv)
      clear the vector, and release any associated resources
 - vec.size
      read the size of the vector
 - vec.data[i]
      access the i_th item
 - bool vlc_vector_push(pv, item)
      push an item at the end of the vector
 - bool vlc_vector_insert(pv, index, item)
      insert an item at index
 - bool vlc_vector_insert_all(pv, index, items, count)
      insert several items at index
 - void vlc_vector_remove(pv, index)
      remove an item
 - void vlc_vector_remove_slice(pv, index, count)
      remove a slice of items
 - void vlc_vector_swap_remove(pv, index)
      remove an item in O(1) without preserving ordering
 - bool vlc_vector_reserve(pv, mincap)
      increase the capacity of the vector in advance
 - void vlc_vector_shrink_to_fit(pv)
      resize the vector to its actual size
 - void vlc_vector_index_of(pv, index, pidx)
      find the index of an item (returns the result in *pidx)
 - vlc_vector_foreach(item, pv)
      a for-each loop

It uses an exponential growth policy for both increasing and decreasing
the size. As a consequence, the amortized complexity of
vlc_vector_push() is O(1).
---
Changes:
 - rename `newsize` to `newcap` where suitable to avoid confusion
 - check reallocation failure via the most significant bit of `cap`, to
   avoid possible strict aliasing violation with (void **)

 include/vlc_common.h |   6 +
 include/vlc_vector.h | 504 +++++++++++++++++++++++++++++++++++++++++++
 src/Makefile.am      |   5 +-
 src/test/vector.c    | 362 +++++++++++++++++++++++++++++++
 4 files changed, 876 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..eb49bff781
--- /dev/null
+++ b/include/vlc_vector.h
@@ -0,0 +1,504 @@
+/******************************************************************************
+ * vlc_vector.h
+ ******************************************************************************
+ * Copyright © 2018 VLC authors and VideoLAN
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation; either version 2.1 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA.
+ *****************************************************************************/
+#ifndef VLC_VECTOR_H
+#define VLC_VECTOR_H
+
+#include <stdbool.h>
+
+/**
+ * \defgroup vector Vector
+ * \ingroup cext
+ * @{
+ * \file
+ * This provides convenience helpers for vectors.
+ */
+
+/**
+ * Vector struct body.
+ *
+ * A vector is a dynamic array, managed by the vlc_vector_* helpers.
+ *
+ * It is generic over the type of its items, so it is implemented as macros.
+ *
+ * To use a vector, a new type must be defined:
+ *
+ * \verbatim
+ * struct vec_int VLC_VECTOR(int);
+ * \endverbatim
+ *
+ * The struct may be anonymous:
+ *
+ * \verbatim
+ * struct VLC_VECTOR(const char *) names;
+ * \endverbatim
+ *
+ * It is convenient to define a typedef to an anonymous structure:
+ *
+ * \verbatim
+ * typedef struct VLC_VECTOR(int) vec_int_t;
+ * \endverbatim
+ *
+ * Vector size is accessible via `vec.size`, and items are intended to be
+ * accessed directly, via `vec.data[i]`.
+ *
+ * Functions and macros having name ending with '_' are private.
+ */
+#define VLC_VECTOR(type) \
+{ \
+    size_t cap; \
+    size_t size; \
+    type *data; \
+}
+
+/**
+ * Static initializer for a vector.
+ */
+#define VLC_VECTOR_INITIALIZER { 0, 0, NULL }
+
+/**
+ * Initialize an empty vector.
+ */
+#define vlc_vector_init(pv) (void) \
+( \
+    /* cannot be implemened as do-while(0), called from vlc_vector_clear() */ \
+    (pv)->cap = 0, \
+    (pv)->size = 0, \
+    (pv)->data = NULL \
+)
+
+/**
+ * Clear a vector, and release any associated resources.
+ */
+#define vlc_vector_clear(pv) \
+( \
+    /* cannot be implemened as do-while(0), called from vlc_vector_resize() */ \
+    free((pv)->data), \
+    vlc_vector_init(pv) \
+)
+
+/**
+ * The minimal allocation size, in number of items.
+ *
+ * Private.
+ */
+#define VLC_VECTOR_MINCAP_ ((size_t) 10)
+
+static inline size_t
+vlc_vector_min_(size_t a, size_t b)
+{
+    return a < b ? a : b;
+}
+
+static inline size_t
+vlc_vector_max_(size_t a, size_t b)
+{
+    return a > b ? a : b;
+}
+
+static inline size_t
+vlc_vector_between_(size_t x, size_t min, size_t max)
+{
+    return vlc_vector_max_(min, vlc_vector_min_(max, x));
+}
+
+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:
+ *  - 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)
+{
+    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 */
+        *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) \
+    ) \
+)
+
+static inline size_t
+vlc_vector_growsize_(size_t value)
+{
+    /* integer multiplication by 1.5 */
+    return value + (value >> 1);
+}
+
+/* SIZE_MAX/2 to fit in ssize_t, and so that cap*1.5 does not overflow. */
+#define vlc_vector_max_cap_(pv) (SIZE_MAX / 2 / sizeof(*(pv)->data))
+
+/**
+ * Increase the capacity of the vector to at least `mincap`.
+ *
+ * \param pv a pointer to the vector
+ * \param mincap (size_t) the requested capacity
+ * \retval true if no allocation failed
+ * \retval false on allocation failure (the vector is left untouched)
+ */
+#define vlc_vector_reserve(pv, mincap) \
+    /* avoid to allocate tiny arrays (< VLC_VECTOR_MINCAP_) */ \
+    vlc_vector_reserve_internal_(pv, \
+                                 vlc_vector_max_(mincap, VLC_VECTOR_MINCAP_))
+
+#define vlc_vector_reserve_internal_(pv, mincap) \
+( \
+    (mincap) <= (pv)->cap /* nothing to do */ || \
+    ( \
+        (mincap) <= vlc_vector_max_cap_(pv) /* not too big */ && \
+        vlc_vector_realloc_(pv, \
+                        /* multiply by 1.5, force between [mincap, maxcap] */ \
+                        vlc_vector_between_(vlc_vector_growsize_((pv)->cap), \
+                                            mincap, \
+                                            vlc_vector_max_cap_(pv))) \
+    ) \
+)
+
+/**
+ * Resize the vector so that its capacity equals its actual size.
+ *
+ * \param pv a pointer to the vector
+ */
+#define vlc_vector_shrink_to_fit(pv) \
+    (void) /* decreasing the size may not fail */ \
+    vlc_vector_resize(pv, (pv)->size)
+
+/**
+ * Resize the vector down automatically.
+ *
+ * Shrink only when necessary (in practice when cap > (size+5)*1.5)
+ *
+ * \param pv a pointer to the vector
+ */
+#define vlc_vector_autoshrink(pv) (void) \
+( \
+    (pv)->cap <= VLC_VECTOR_MINCAP_ /* do not shrink to tiny length */ || \
+    (pv)->cap < vlc_vector_growsize_((pv)->size+5) /* no need to shrink */ || \
+    vlc_vector_resize(pv, vlc_vector_max_((pv)->size+5, VLC_VECTOR_MINCAP_)) \
+)
+
+/**
+ * Push an item at the end of the vector.
+ *
+ * The amortized complexity is O(1).
+ *
+ * \param pv a pointer to the vector
+ * \param item the item to append
+ * \retval true if no allocation failed
+ * \retval false on allocation failure (the vector is left untouched)
+ */
+#define vlc_vector_push(pv, item) \
+( \
+    vlc_vector_reserve(pv, (pv)->size + 1) && \
+    ( \
+        (pv)->data[(pv)->size++] = (item), \
+        true \
+    ) \
+)
+
+/**
+ * Insert an item at the given index.
+ *
+ * The items in range [index; size-1] will be moved.
+ *
+ * \param pv a pointer to the vector
+ * \param index the index where the item is to be inserted
+ * \param item the item to append
+ * \retval true if no allocation failed
+ * \retval false on allocation failure (the vector is left untouched)
+ */
+#define vlc_vector_insert(pv, index, item) \
+    vlc_vector_insert_internal_(pv, vlc_vector_enforce_size_t_(index), item)
+
+#define vlc_vector_insert_internal_(pv, index, item) \
+( \
+    vlc_vector_reserve(pv, (pv)->size + 1) && \
+    ( \
+        (index) == (pv)->size || \
+        ( \
+            memmove(&(pv)->data[(index) + 1], \
+                    &(pv)->data[index], \
+                    ((pv)->size - (index)) * sizeof(*(pv)->data)), \
+            true \
+        ) \
+    ) && \
+    ( \
+        (pv)->data[index] = (item), \
+        (pv)->size++, \
+        true \
+    ) \
+)
+
+/**
+ * Insert `count` items at the given index.
+ *
+ * The items in range [index; size-1] will be moved.
+ *
+ * \param pv a pointer to the vector
+ * \param index the index where the items are to be inserted
+ * \param items the items array to append
+ * \param count the number of items in the array
+ * \retval true if no allocation failed
+ * \retval false on allocation failure (the vector is left untouched)
+ */
+#define vlc_vector_insert_all(pv, index, items, count) \
+    vlc_vector_insert_all_internal_(pv, vlc_vector_enforce_size_t_(index), \
+                                    items, vlc_vector_enforce_size_t_(count))
+
+#define vlc_vector_check_same_ptr_type_(a, b) \
+    (void) ((a) == (b)) /* warn on type mismatch */
+
+#define vlc_vector_insert_all_internal_(pv, index, items, count) \
+( \
+    vlc_vector_check_same_ptr_type_((pv)->data, items), \
+    vlc_vector_reserve(pv, (pv)->size + (count)) && \
+    ( \
+        (index) == (pv)->size || \
+        ( \
+            memmove(&(pv)->data[(index) + (count)], \
+                    &(pv)->data[index], \
+                    ((pv)->size - (index)) * sizeof(*(pv)->data)), \
+            true \
+        ) \
+    ) && \
+    ( \
+        memcpy(&(pv)->data[index], items, (count) * sizeof(*(pv)->data)), \
+        (pv)->size += (count), \
+        true \
+    ) \
+)
+
+/**
+ * Remove a slice of items, without shrinking the array.
+ *
+ * If you have no good reason to use the _noshrink() version, use
+ * vlc_vector_remove_slice() instead.
+ *
+ * The items in range [index+count; size-1] will be moved.
+ *
+ * \param pv a pointer to the vector
+ * \param index the index of the first item to remove
+ * \param count the number of items to remove
+ */
+#define vlc_vector_remove_slice_noshrink(pv, index, count) \
+    vlc_vector_remove_slice_noshrink_internal_(pv, \
+            vlc_vector_enforce_size_t_(index), \
+            vlc_vector_enforce_size_t_(count))
+
+#define vlc_vector_remove_slice_noshrink_internal_(pv, index, count) \
+    do { \
+        if ((index) + (count) < (pv)->size) \
+            memmove(&(pv)->data[index], \
+                    &(pv)->data[(index) + (count)], \
+                    ((pv)->size - (index) - (count)) * sizeof(*(pv)->data)); \
+        (pv)->size -= (count); \
+    } while (0)
+
+/**
+ * Remove a slice of items.
+ *
+ * The items in range [index+count; size-1] will be moved.
+ *
+ * \param pv a pointer to the vector
+ * \param index the index of the first item to remove
+ * \param count the number of items to remove
+ */
+#define vlc_vector_remove_slice(pv, index, count) \
+    do { \
+        vlc_vector_remove_slice_noshrink(pv, index, count); \
+        vlc_vector_autoshrink(pv); \
+    } while (0)
+
+/**
+ * Remove an item, without shrinking the array.
+ *
+ * If you have no good reason to use the _noshrink() version, use
+ * vlc_vector_remove() instead.
+ *
+ * The items in range [index+1; size-1] will be moved.
+ *
+ * \param pv a pointer to the vector
+ * \param index the index of item to remove
+ */
+#define vlc_vector_remove_noshrink(pv, index) \
+    vlc_vector_remove_slice_noshrink(pv, index, 1)
+
+/**
+ * Remove an item.
+ *
+ * The items in range [index+1; size-1] will be moved.
+ *
+ * \param pv a pointer to the vector
+ * \param index the index of item to remove
+ */
+#define vlc_vector_remove(pv, index) \
+    do { \
+        vlc_vector_remove_noshrink(pv, index); \
+        vlc_vector_autoshrink(pv); \
+    } while (0)
+
+/**
+ * Remove an item.
+ *
+ * The removed item is replaced by the last item of the vector.
+ *
+ * This does not preserve ordering, but is O(1). This is useful when the order
+ * of items is not meaningful.
+ *
+ * \param pv a pointer to the vector
+ * \param index the index of item to remove
+ */
+#define vlc_vector_swap_remove(pv, index) \
+    (pv)->data[index] = (pv)->data[--(pv)->size]
+
+/**
+ * Return the index of an item.
+ *
+ * Iterate over all items to find a given item.
+ *
+ * Use only for vectors of primitive types or pointers.
+ *
+ * The result is written to `*(pidx)`:
+ *  - the index of the item if it is found;
+ *  - -1 if it is not found.
+ *
+ * \param pv a pointer to the vector
+ * \param item the item to find (compared with ==)
+ * \param a pointer to the result (ssize_t *) [OUT]
+ */
+#define vlc_vector_index_of(pv, item, pidx) \
+    do { \
+        ssize_t *out = pidx; /* warning/error on type mismatch */ \
+        size_t vlc_vector_find_idx_; \
+        for (vlc_vector_find_idx_ = 0; \
+             vlc_vector_find_idx_ < (pv)->size; \
+             ++vlc_vector_find_idx_) \
+            if ((pv)->data[vlc_vector_find_idx_] == (item)) \
+                break; \
+        *out = vlc_vector_find_idx_ == (pv)->size ? -1 : \
+            (ssize_t) vlc_vector_find_idx_; \
+    } while (0)
+
+/**
+ * For-each loop.
+ *
+ * Use only for vectors of primitive types or pointers (every struct would be
+ * copied for a vector of structs).
+ *
+ * \param item the iteration variable [OUT]
+ * \param pv a pointer to the vector [OUT]
+ */
+#define vlc_vector_foreach(item, pv) \
+    for (size_t vlc_vector_idx_##item = 0; \
+         vlc_vector_idx_##item < (pv)->size && \
+             ((item) = (pv)->data[vlc_vector_idx_##item], true); \
+         ++vlc_vector_idx_##item)
+
+/** @} */
+
+#endif
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;
+}
-- 
2.19.0.rc1