[HICN-555] Base data structures: vector, bitmap, pool (code + doc)

Change-Id: I30b559974d4bdf57eb458f1c43a71f47598c2e70
Signed-off-by: Jordan Augé <jordan.auge+fdio@cisco.com>

6 files changed, 492 insertions, 111 deletions

diff --git a/hicn-light/src/hicn/base/bitmap.h b/hicn-light/src/hicn/base/bitmap.h
index df94b8039..bebbf8860 100644
--- a/hicn-light/src/hicn/base/bitmap.h
+++ b/hicn-light/src/hicn/base/bitmap.h
@@ -28,15 +28,54 @@
 
 #define BITMAP_WIDTH(bitmap) (sizeof((bitmap)[0]) * 8)
 
-#define bitmap_init(bitmap, size) \
-   vector_init(bitmap, next_pow2(size / BITMAP_WIDTH(bitmap)))
+/**
+ * @brief Allocate and initialize a bitmap
+ *
+ * @param[in,out] bitmap Bitmap to allocate and initialize
+ * @param[in] max_size Bitmap max_size
+ */
+#define bitmap_init(bitmap, max_size) \
+   vector_init(bitmap, next_pow2(max_size / BITMAP_WIDTH(bitmap)))
 
+/*
+ * @brief Ensures a bitmap is sufficiently large to hold an element at the
+ * given position.
+ *
+ * @param[in] bitmap The bitmap for which to validate the position.
+ * @param[in] pos The position to validate.
+ *
+ * NOTE:
+ *  - This function should always be called before writing to a bitmap element
+ *  to eventually make room for it (the bitmap will eventually be resized).
+ */
 #define bitmap_ensure_pos(bitmap, pos) vector_ensure_pos(bitmap, pos / BITMAP_WIDTH(bitmap))
 
+/**
+ * @brief Retrieve the state of the i-th bit in the bitmap.
+ *
+ * @param[in] bitmap The bitmap to access.
+ * @param[in] i The bit position.
+ */
 #define bitmap_get(bitmap, i) ((bitmap)[(i) / BITMAP_WIDTH(bitmap)] & (1 << ((i) % BITMAP_WIDTH(bitmap))))
 
+/*
+ * @brief Returns whether the i-th bit is set (equal to 1) in a bitmap.
+ *
+ * @param[in] bitmap The bitmap to access.
+ * @param[in] i The bit position.
+ *
+ * @return bool
+ */
 #define bitmap_is_set(bitmap, i) (bitmap_get((bitmap), (i)) == 1)
 
+/*
+ * @brief Returns whether the i-th bit is unset (equal to 0) in a bitmap.
+ *
+ * @param[in] bitmap The bitmap to access.
+ * @param[in] i The bit position.
+ *
+ * @return bool
+ */
 #define bitmap_is_unset(bitmap, i) (bitmap_get((bitmap), (i)) == 0)
 
 #define bitmap_set(bitmap, i) bitmap[(i) / BITMAP_WIDTH(bitmap)] |= 1 << ((i) % BITMAP_WIDTH(bitmap))
diff --git a/hicn-light/src/hicn/base/pool.c b/hicn-light/src/hicn/base/pool.c
index abca86422..0f5f728e3 100644
--- a/hicn-light/src/hicn/base/pool.c
+++ b/hicn-light/src/hicn/base/pool.c
@@ -15,41 +15,49 @@
 
 /**
  * \file pool.c
- * \brief Implementation of fixed-size pool allocator
+ * \brief Implementation of fixed-size pool allocator.
+ * 
+ * NOTE:
+ *  - Ideally, we should have a single realloc per resize, that would encompass
+ *  both the free indices vector and bitmap, by nesting data structures. Because
+ *  of the added complexity, and by lack of evidence of the need for this, we
+ *  currently rely on a simpler implementation.
  */
 
+#include <assert.h>
 #include <stdlib.h> // calloc
 
 #include "common.h"
 #include "pool.h"
 
-
-/**
- * \brief Initialize the pool data structure
- * \param [in,out] pool - Pointer to the pool structure storage
- * \param [in] elt_size - Size of elements in vector
- * \param [in] max_elts - Maximum size
- *
- * Note that an empty pool might be equal to NULL
- */
 void
-_pool_init(void ** pool_ptr, size_t elt_size, size_t max_elts)
+_pool_init(void ** pool_ptr, size_t elt_size, size_t max_size)
 {
-    pool_hdr_t * ph = calloc(POOL_HDRLEN + elt_size * max_elts, 1);
-    if (!ph)
-        abort();
+    assert(pool_ptr);
+    assert(elt_size);
+
+    pool_hdr_t * ph = calloc(POOL_HDRLEN + elt_size * max_size, 1);
+    if (!ph) {
+        *pool_ptr = NULL;
+        return;
+    }
+
+    ph->elt_size = elt_size;
+    ph->max_size = max_size;
 
     /* Free indices */
     off_t * free_indices;
-    vector_init(free_indices, max_elts);
+    vector_init(free_indices, max_size);
+    for(unsigned i = 0; i < max_size; i++)
+        free_indices[i] = (max_size - 1) - i;
+    vector_len(free_indices) = max_size;
+    ph->free_indices = free_indices;
 
+    /* Free bitmap */
     uint_fast32_t * fb = ph->free_bitmap;
-    bitmap_init(fb, max_elts);
-    bitmap_set_to(fb, max_elts);
-
-    for(unsigned i = 0; i < max_elts; i++)
-        free_indices[i] = (max_elts - 1) - i;
-    ph->free_indices = free_indices;
+    bitmap_init(fb, max_size);
+    bitmap_set_to(fb, max_size);
+    ph->free_bitmap = fb;
 
     *pool_ptr = (uint8_t*)ph + POOL_HDRLEN;
 }
@@ -65,14 +73,17 @@ void
 _pool_resize(void ** pool_ptr, size_t elt_size)
 {
     pool_hdr_t * ph = pool_hdr(*pool_ptr);
-    size_t old_elts = ph->max_elts;
+    size_t old_elts = ph->max_size;
     size_t new_elts = old_elts * 2;
 
     /* Double pool storage */
     ph = realloc(ph, POOL_HDRLEN + new_elts * elt_size);
-    if (!ph)
-        abort();
-    ph->max_elts = new_elts;
+    if (!ph) {
+        *pool_ptr = NULL;
+        return;
+    }
+    ph->elt_size = elt_size;
+    ph->max_size = new_elts;
 
     /*
      * After resize, the pool will have old_elts free indices, ranging from
@@ -86,3 +97,27 @@ _pool_resize(void ** pool_ptr, size_t elt_size)
     /* Reassign pool pointer */
     *pool_ptr = (uint8_t*)ph + POOL_HDRLEN;
 }
+
+void
+_pool_get(void ** pool_ptr, void ** elt, size_t elt_size)
+{
+    pool_hdr_t * ph = pool_hdr(*pool_ptr);
+    uint64_t l = vector_len(ph->free_indices);
+    if (l == 0)
+        _pool_resize(pool_ptr, elt_size);
+    off_t free_id = ph->free_indices[l - 1];
+    vector_len(ph->free_indices)--;
+    *elt = *pool_ptr + free_id;
+    memset(*elt, 0, sizeof(elt));
+}
+
+void
+_pool_put(void ** pool_ptr, void ** elt, size_t elt_size)
+{
+    pool_hdr_t * ph = pool_hdr(*pool_ptr);
+    uint64_t l = vector_len(ph->free_indices);
+    vector_ensure_pos(ph->free_indices, l);
+    ph->free_indices[l] = *elt - *pool_ptr;
+    vector_len(ph->free_indices)++;
+    bitmap_set(ph->free_bitmap, l);
+}
diff --git a/hicn-light/src/hicn/base/pool.h b/hicn-light/src/hicn/base/pool.h
index cdb0fc3a2..8335c9bc5 100644
--- a/hicn-light/src/hicn/base/pool.h
+++ b/hicn-light/src/hicn/base/pool.h
@@ -15,7 +15,28 @@
 
 /**
  * \file array.h
- * \brief Fixed-size pool allocator
+ * \brief Fixed-size pool allocator.
+ *
+ * This memory pool allocates a single block of memory that is used to efficiently
+ * allocate/deallocate fixed-size blocks for high churn data structures.
+ *
+ * Internally this data structure leverages a vector for managing elements (and
+ * it thus resizeable if needed), as well as a list of free indices (in the
+ * form of another vector) and a bitmap marking free indices also (for fast
+ * iteration).
+ *
+ * The internal API manipulates a pointer to the vector that that is can be
+ * seamlessly resized, and a more convenient user interface is provided through
+ * macros.
+ *
+ * The vector of free indices is managed as a stack where elements indices are
+ * retrieved from and put back to the end of the vector. In the bitmap,
+ * available elements are set to 1, and unset to 0 when in use.
+ *
+ * The pool is not currently resized down when releasing elements.
+ *
+ * It is freely inspired (and simplified) from the VPP infra infrastructure
+ * library.
  */
 
 #ifndef UTIL_POOL_H
@@ -26,68 +47,160 @@
 #include "bitmap.h"
 #include "vector.h"
 
-/** Local variable naming macro. */
-#define _pool_var(v) _pool_##v
-#ifndef u64
-#define u64 uint64_t 
-#endif
+/* Pool header */
 
 typedef struct {
     size_t elt_size;
-    size_t max_elts;
-    uint_fast32_t * free_bitmap;
+    size_t max_size;
+    uint_fast32_t * free_bitmap; /* bitmap of free indices */
     off_t * free_indices; /* vector of free indices */
 } pool_hdr_t;
 
-void _pool_init(void ** pool_ptr, size_t elt_size, size_t max_elts);
+#define POOL_HDRLEN SIZEOF_ALIGNED(pool_hdr_t)
+
+/* This header actually prepends the actual content of the pool. */
+#define pool_hdr(pool) ((pool_hdr_t *)((uint8_t*)(pool) - POOL_HDRLEN))
+
+/******************************************************************************/
+/* Helpers */
+
+/** Local variable naming macro. */
+#define _pool_var(v) _pool_##v
+
+/**
+ * @brief Allocate and initialize a pool data structure (helper).
+ *
+ * @param[in,out] pool_ptr Pointer to the pool data structure.
+ * @param[in] elt_size Size of elements in vector.
+ * @param[in] max_size Maximum size.
+ *
+ * NOTE: that an empty pool might be equal to NULL.
+ */
+void _pool_init(void ** pool_ptr, size_t elt_size, size_t max_size);
+
+/**
+ * @brief Free a pool data structure (helper).
+ *
+ * @param[in] pool_ptr Pointer to the pool data structure.
+ */
 void _pool_free(void ** pool_ptr);
+
+/**
+ * @brief Resize a pool data structure (helper).
+ *
+ * @param pool_ptr Pointer to the pool data structure.
+ *
+ * This function should only be called internally, as the resize is implicitly
+ * done (if allowed by the maximum size) when the user tries to get a new slot.
+ */
 void _pool_resize(void ** pool_ptr, size_t elt_size);
 
-#define POOL_HDRLEN SIZEOF_ALIGNED(pool_hdr_t)
+/**
+ * @brief Get a free element from the pool data structure (helper).
+ *
+ * @param[in] pool Pointer to the pool data structure to use.
+ * @param[in,out] elt Pointer to an empty element that will be used to return
+ * the allocated one from the pool.
+ *
+ * NOTES:
+ *  - The memory chunk is cleared upon attribution
+ */
+void _pool_get(void ** pool, void ** elt, size_t elt_size);
 
-/* This header actually prepends the actual content of the pool */
-#define pool_hdr(pool) ((pool_hdr_t *)((uint8_t*)(pool) - POOL_HDRLEN))
+/**
+ * @brief Put an element back into the pool data structure (helper).
+ *
+ * @param[in] pool_ptr Pointer to the pool data structure to use.
+ * @param[in] elt Pointer to the pool element to put back.
+ */
+void _pool_put(void ** pool, void ** elt, size_t elt_size);
 
-// XXX TODO need common naming for cur_len, len, max_len
-#define pool_elts(pool) \
-    (pool_hdr(pool)->max_elts - vector_len((pool_hdr(pool)->free_indices)))
+/******************************************************************************/
+/* Public API */
 
-#define pool_init(pool, max_elts)                                       \
-    _pool_init((void**)&pool, sizeof(pool[0]), max_elts);
+/**
+ * @brief Allocate and initialize a pool data structure.
+ *
+ * @param[in,out] pool Pointer to the pool data structure.
+ * @param[in] elt_size Size of elements in pool.
+ * @param[in] max_size Maximum size.
+ *
+ * NOTE: that an empty pool might be equal to NULL.
+ */
+#define pool_init(pool, max_size) \
+    _pool_init((void**)&pool, sizeof(pool[0]), max_size);
 
-#define pool_free(pool)                                                 \
-    _pool_free((void**)&pool);
+/**
+ * @brief Free a pool data structure.
+ *
+ * @param[in] pool The pool data structure to free.
+ */
+#define pool_free(pool) _pool_free((void**)&pool);
 
-#define pool_get(pool, elt)                                             \
-do {                                                                    \
-    pool_hdr_t * _pool_var(ph) = pool_hdr(pool);                        \
-    u64 _pool_var(l) = vector_len(_pool_var(ph)->free_indices);         \
-    if (_pool_var(l) == 0)                                              \
-        _pool_resize((void**)&(pool), sizeof((pool)[0]));               \
-    off_t _pool_var(free_id) =                                          \
-            _pool_var(ph)->free_indices[_pool_var(l) - 1];              \
-    elt = (pool) + _pool_var(free_id);                                  \
-    memset(&elt, 0, sizeof(elt));                                       \
-} while(0)
+/**
+ * @brief Get a free element from the pool data structure.
+ *
+ * @param[in] pool The pool data structure to use.
+ * @param[in,out] elt An empty element that will be used to return the
+ * allocated one from the pool.
+ *
+ * NOTES:
+ *  - The memory chunk is cleared upon attribution
+ */
+#define pool_get(pool, elt) _pool_get((void**)&pool, (void**)&elt, sizeof(elt))
 
-#define pool_put(pool, elt)                                             \
-do {                                                                    \
-    pool_hdr_t * _pool_var(ph) = pool_hdr(pool);                        \
-    u64 _pool_var(l) = vector_len(_pool_var(ph)->free_indices);         \
-    vector_ensure_pos(_pool_var(ph)->free_indices, _pool_var(l));       \
-    _pool_var(ph)->free_indices[_pool_var(l)] = (elt) - (pool);         \
-    vector_len(_pool_var(ph)->free_indices)++;                          \
-    bitmap_set(_pool_var(ph)->free_bitmap, _pool_var(l));               \
-} while(0)
+/**
+ * @brief Put an element back into the pool data structure.
+ *
+ * @param[in] pool The pool data structure to use.
+ * @param[in] elt The pool element to put back.
+ */
+#define pool_put(pool, elt) _pool_put((void**)&pool, (void**)&elt, sizeof(elt))
 
+/**
+ * @brief Validate a pool element by index.
+ *
+ * @param[in] pool The pool data structure to use.
+ * @param[in] id The index of the element to validate.
+ *
+ * @return bool A flag indicating whether the index is valid or not.
+ */
 #define pool_validate_id(pool, id) \
     bitmap_is_unset((pool_hdr(pool))->free_bitmap, (id))
 
+/**
+ * @brief Returns the current length of the pool.
+ *
+ * @param[in] pool The pool data structure for which to return the length.
+ *
+ * @return size_t The current length of the pool.
+ *
+ * NOTE:
+ *  - The pool length corresponds to the number of allocated elements, not the
+ *  size of the pool.
+ */
+#define pool_len(pool) \
+    (pool_hdr(pool)->max_size - vector_len((pool_hdr(pool)->free_indices)))
+
+/**
+ * @brief Enumerate elements from a pool.
+ *
+ * @param[in] pool The pool data structure to enumerate.
+ * @param[in, out] i An integer that will be used for enumeration.
+ * @param[in, out] eltp A pointer to the element type that will be used for
+ * enumeration.
+ * @param[in] BODY Block to execute during enumeration.
+ *
+ * Enumeration will iteratively execute BODY with (i, eltp) corresponding
+ * respectively to the index and element found in the pool.
+ *
+ * NOTE: i stars at 0.
+ */
 #define pool_enumerate(pool, i, eltp, BODY)                             \
 do {                                                                    \
     pool_hdr_t * _pool_var(ph) = pool_hdr(pool);                        \
     uint_fast32_t * _pool_var(fb) = _pool_var(ph)->free_bitmap;         \
-    for((i) = 0; (i) < _pool_var(ph)->max_elts; (i)++) {                \
+    for((i) = 0; (i) < _pool_var(ph)->max_size; (i)++) {                \
         if (bitmap_is_unset(_pool_var(fb), (i)))                        \
             continue;                                                   \
         eltp = (pool) + (i);                                            \
@@ -95,12 +208,22 @@ do {                                                                    \
     }                                                                   \
 } while(0)
 
+/**
+ * @brief  Iterate over elements in a pool.
+ *
+ * @param[in] pool The pool data structure to iterate over.
+ * @param[in,out] eltp A pointer to the element type that will be used for
+ * iteration.
+ * @param[in] BODY Block to execute during iteration.
+ *
+ * Iteration will execute BODY with eltp corresponding successively to all
+ * elements found in the pool. It is implemented using the more generic
+ * enumeration function.
+ */
 #define pool_foreach(pool, eltp, BODY)                                  \
 do {                                                                    \
   unsigned _pool_var(i);                                                \
   pool_enumerate((pool), _pool_var(i), (eltp), BODY);                   \
 } while(0)
 
-
-
 #endif /* UTIL_POOL_H */
diff --git a/hicn-light/src/hicn/base/test/test-vector.cc b/hicn-light/src/hicn/base/test/test-vector.cc
index 71b38a2b6..e5eeff910 100644
--- a/hicn-light/src/hicn/base/test/test-vector.cc
+++ b/hicn-light/src/hicn/base/test/test-vector.cc
@@ -48,7 +48,7 @@ class VectorTest : public ::testing::Test {
   }
 
   int *vector = NULL;
-  
+
 };
 
 TEST_F(VectorTest, VectorSize)
@@ -60,7 +60,7 @@ TEST_F(VectorTest, VectorSize)
   vector_push(vector, 109);
   size = vector_len(vector);
   EXPECT_EQ(size, 3);
-  
+
 }
 
 TEST_F(VectorTest, VectorCheckValue)
@@ -69,7 +69,6 @@ TEST_F(VectorTest, VectorCheckValue)
   vector_push(vector, 200);
   EXPECT_EQ(vector[0], 109);
   EXPECT_EQ(vector[1], 200);
-
 }
 
 TEST_F(VectorTest, VectorEnsurePos)
@@ -79,17 +78,12 @@ TEST_F(VectorTest, VectorEnsurePos)
   for (int i = 0; i <1025; i++) {
     printf("i %d\n", i);
     printf (" %p\n", vector);
-    
-    
-        vector_push(vector, i);
-      
+    vector_push(vector, i);
   }
   int size = vector_len(vector);
   EXPECT_EQ(size, 1025);
 }
 
-
-
 int main(int argc, char **argv)
 {
     ::testing::InitGoogleTest(&argc, argv);
diff --git a/hicn-light/src/hicn/base/vector.c b/hicn-light/src/hicn/base/vector.c
index d090588b4..b994a4465 100644
--- a/hicn-light/src/hicn/base/vector.c
+++ b/hicn-light/src/hicn/base/vector.c
@@ -18,19 +18,28 @@
  * \brief Implementation of resizeable static array
  */
 
+#include <assert.h>
 #include <stddef.h> // size_t
 #include <stdlib.h> // calloc
 #include <stdio.h>
 
 #include "vector.h"
 
+#define DEFAULT_VECTOR_SIZE 64
+
 void
-_vector_init(void ** vector_ptr, size_t elt_size, size_t max_elts)
+_vector_init(void ** vector_ptr, size_t elt_size, size_t init_size)
 {
-    vector_hdr_t * vh = calloc(VECTOR_HDRLEN + elt_size * max_elts, 1);
-    *vector_ptr = (uint8_t*)vh + VECTOR_HDRLEN;
-    vh->max_elts = max_elts;
-    vh->num_elts = 0;
+    assert(vector_ptr);
+
+    if (init_size == 0)
+        init_size = DEFAULT_VECTOR_SIZE;
+
+    *vector_ptr = NULL;
+    _vector_resize(vector_ptr, elt_size, init_size);
+
+    vector_hdr_t * vh = vector_hdr(*vector_ptr);
+    vh->cur_size = 0;
 }
 
 void
@@ -40,18 +49,23 @@ _vector_free(void ** vector_ptr)
     *vector_ptr = NULL;
 }
 
-void
+bool
 _vector_resize(void ** vector_ptr, size_t elt_size, off_t pos)
 {
-    vector_hdr_t * vh = vector_hdr(*vector_ptr);
-    size_t new_elts = (pos > 0) ? next_pow2(pos) : vh->max_elts * 2;
+    vector_hdr_t * vh = *vector_ptr ? vector_hdr(*vector_ptr) : NULL;
+
+    /*
+     * Round the allocated size to the next power of 2 of the requested position
+     */
+    size_t new_elts = (pos > 0) ? next_pow2(pos) : vh->max_size * 2;
 
-    /* Double the allocated vector size */
     vh = realloc(vh, VECTOR_HDRLEN + new_elts * elt_size);
     if (!vh)
-        abort();
-    vh->max_elts = new_elts;
+        return false;
+    vh->max_size = new_elts;
 
     /* Reassign vector pointer */
     *vector_ptr = (uint8_t*)vh + VECTOR_HDRLEN;
+
+    return true;
 }
diff --git a/hicn-light/src/hicn/base/vector.h b/hicn-light/src/hicn/base/vector.h
index 47cfdd11a..06ffa4428 100644
--- a/hicn-light/src/hicn/base/vector.h
+++ b/hicn-light/src/hicn/base/vector.h
@@ -16,55 +16,231 @@
 /**
  * \file vector.h
  * \brief Resizeable static array
+ *
+ * A vector is a resizeable area of contiguous memory that contains elements of
+ * fixed size. It is mostly useful to serve as the basis for more advanced data
+ * structures such as memory pools.
+ *
+ * The internal API manipulates a pointer to the vector so that it can be
+ * seamlessly resized, and a more convenient user interface is provided through
+ * macros.
+ *
+ * A vector starts at index 0, and is typed according to the elements it
+ * contains. For that matter, the data structure header precedes the returned
+ * pointer which corresponds to the storage area.
+ *
+ * A vector is by default used as a stack where an end marker is maintained and
+ * new elements are pushed right after this end marker (an indication of
+ * the size of the vector) after ensuring the vector is sufficiently large.
+ *
+ * A user should not store any pointer to vector elements as this might change
+ * during reallocations, but should use indices instead.
+ *
+ * NOTE: a maximum size is currently not implemented.
+ *
+ * It is freely inspired (and simplified) from the VPP infra infrastructure
+ * library.
  */
 
 #ifndef UTIL_VECTOR_H
 #define UTIL_VECTOR_H
 
+#include <stdbool.h>
 #include <stddef.h>
 #include <stdint.h>
+#include <string.h>
 #include <sys/types.h>
 
 #include "common.h"
 
-/** Local variable naming macro. */
-#define _vector_var(v) _vector_##v
+/******************************************************************************/
+/* Vector header */
 
 typedef struct {
-    size_t num_elts;
-    size_t max_elts;
+    size_t cur_size; /** Vector current size (corresponding to the highest used element). */
+    size_t max_size; /** The currently allocated size. */
 } vector_hdr_t;
 
-void _vector_init(void ** vector_ptr, size_t elt_size, size_t max_elts);
-void _vector_free(void ** vector_ptr);
-void _vector_resize(void ** vector_ptr, size_t elt_size, off_t pos);
-
 /* Make sure elements following the header are aligned */
 #define VECTOR_HDRLEN SIZEOF_ALIGNED(vector_hdr_t)
 
 /* This header actually prepends the actual content of the vector */
 #define vector_hdr(vector) ((vector_hdr_t *)((uint8_t*)vector - VECTOR_HDRLEN))
 
-#define vector_init(vector, max_elts) \
-    _vector_init((void**)&vector, sizeof(vector[0]), max_elts)
+/******************************************************************************/
+/* Helpers */
 
-#define vector_free(vector) \
-    _vector_free((void **)&vector)
+/** Local variable naming macro. */
+#define _vector_var(v) _vector_##v
+
+/**
+ * @brief Allocate and initialize a vector data structure (helper function).
+ *
+ * @param[in,out] vector_ptr Vector to allocate and initialize.
+ * @param[in] elt_size Size of a vector element.
+ * @param[in] max_size Maximum vector size (O = unlimited).
+ */
+void _vector_init(void ** vector_ptr, size_t elt_size, size_t max_size);
+
+/**
+ * @brief Free a vector data structure.
+ *
+ * @param vector_ptr[in] Pointer to the vector data structure to free.
+ */
+void _vector_free(void ** vector_ptr);
+
+/**
+ * @brief Resize a vector data structure.
+ *
+ * @param[in] vector_ptr A pointer to the vector data structure to resize.
+ * @param[in] elt_size The size of a vector element.
+ * @param[in] pos The position at which the vector should be able to hold an
+ * element.
+ *
+ * @return bool Flag indicating whether the vector has been correctly resized.
+ *
+ * NOTE:
+ *  - The resize operation does not specify the final size of the vector but
+ * instead ensure that it is large enough to hold an element at the specified
+ * position. This allows the caller not to care about doing successive calls to
+ * this API while the vector is growing in size.
+ */
+bool _vector_resize(void ** vector_ptr, size_t elt_size, off_t pos);
+
+/**
+ * @brief Ensures a vector is sufficiently large to hold an element at the
+ * given position.
+ *
+ * @param[in] vector_ptr A pointer to the vector data structure to resize.
+ * @param[in] elt_size The size of a vector element.
+ * @param[in] pos The position to validate.
+ *
+ * @return bool Flag indicating whether the vector is available.
+ *
+ * NOTE:
+ *  - This function should always be called before writing to a vector element
+ *  to eventually make room for it (the vector will eventually be resized).
+ *  - This function can fail if the vector is full and for any reason it cannot
+ *  be resized.
+ */
+static inline
+bool
+_vector_ensure_pos(void ** vector_ptr, size_t elt_size, off_t pos)
+{
+    vector_hdr_t * vh = vector_hdr(*vector_ptr);
+    if (pos >= vh->max_size)
+        return _vector_resize(vector_ptr, elt_size, pos);
+    return true;
+}
 
-#define vector_len(vector) (vector_hdr(vector)->num_elts)
+/**
+ * @brief Push an element at the end of a vector.
+ *
+ * @param[in] vector_ptr A pointer to the vector data structure to resize.
+ * @param[in] elt_size The size of a vector element.
+ * @param[in] elt The element to insert.
+ *
+ * NOTE:
+ *  - This function ensures there is sufficient room for inserting the element,
+ *  and evenutually resizes the vector to make room for it (if allowed by
+ *  maximum size).
+ */
+static inline
+bool
+_vector_push(void ** vector_ptr, size_t elt_size, void * elt)
+{
+    vector_hdr_t * vh = vector_hdr(*vector_ptr);
+    if (!_vector_ensure_pos(vector_ptr, elt_size, vh->cur_size))
+        return false;
+    /*(*vector_ptr)[vh->cur_size++] = elt; */
+    memcpy((uint8_t*)vector_ptr + vh->cur_size++ * elt_size, elt, elt_size);
+    return true;
+}
+
+/******************************************************************************/
+/* Public API */
+
+/**
+ * @brief Allocate and initialize a vector data structure.
+ *
+ * @param[in,out] vector Vector to allocate and initialize.
+ * @param[in] max_size Maximum vector size (nonzero).
+ */
+#define vector_init(vector, max_size) \
+    _vector_init((void**)&vector, sizeof(vector[0]), max_size)
 
+/**
+ * @brief Free a vector data structure.
+ *
+ * @param[in] vector The vector data structure to free.
+ */
+#define vector_free(vector) \
+    _vector_free((void**)&vector)
+
+/**
+ * @brief Resize a vector data structure.
+ *
+ * @param[in] vector The vector data structure to resize.
+ * @param[in] pos The position at which the vector should be able to hold an
+ * element.
+ *
+ * @return bool Flag indicating whether the vector has been correctly resized.
+ *
+ * NOTE:
+ *  - The resize operation does not specify the final size of the vector but
+ * instead ensure that it is large enough to hold an element at the specified
+ * position. This allows the caller not to care about doing successive calls to
+ * this API while the vector is growing in size.
+ *  - If the new size is smaller than the current size, the content of the
+ *  vector will be truncated.
+ */
 #define vector_resize(vector) _vector_resize((void**)&(vector), sizeof((vector)[0]), 0)
 
-#define vector_ensure_pos(vector, pos)                                          \
-do {                                                                            \
-    if ((pos) >= vector_hdr(vector)->max_elts)                                  \
-        _vector_resize((void**)&(vector), sizeof((vector)[0]), pos);            \
-} while(0)
+/**
+ * @brief Ensures a vector is sufficiently large to hold an element at the
+ * given position.
+ *
+ * @param[in] vector The vector for which to validate the position.
+ * @param[in] pos The position to validate.
+ *
+ * NOTE:
+ *  - This function should always be called before writing to a vector element
+ *  to eventually make room for it (the vector will eventually be resized).
+ */
+#define vector_ensure_pos(vector, pos) \
+    _vector_ensure_pos((void**)&(vector), sizeof((vector)[0]), pos);
 
-#define vector_push(vector, elt)                                                \
-do {                                                                            \
-    vector_ensure_pos(vector, vector_len(vector));                              \
-    vector[vector_len(vector)++] = elt;                                         \
+/**
+ * @brief Push an element at the end of a vector.
+ *
+ * @param[in] vector The vector in which to insert the element.
+ * @param[in] elt The element to insert.
+ *
+ * NOTE:
+ *  - This function ensures there is sufficient room for inserting the element,
+ *  and evenutually resizes the vector to make room for it (if allowed by
+ *  maximum size).
+ */
+#define vector_push(vector, elt)                                        \
+do {                                                                    \
+    typeof(elt) x = elt;                                                \
+    _vector_push((void**)&(vector), sizeof((vector)[0]), (void*)(&x));  \
 } while(0)
 
+/**
+ * @brief Returns the length of a vector.
+ *
+ * @param[in] vector The vector from which to get the size.
+ *
+ * @see vector_ensure_pos
+ *
+ * NOTE:
+ *  - The size of the vector corresponds to the highest accessed index (for
+ * example as specified in the resize operation) and not the currently
+ * allocated size which will typically be bigger to amortize allocations.
+ *  - A user should always call vector_ensure_pos to ensure the vector is
+ *  sufficiently large to hold an element at the specified position.
+ */
+#define vector_len(vector) vector_hdr((vector))->cur_size
+
 #endif /* UTIL_VECTOR_H */