aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorJordan Augé <jordan.auge+fdio@cisco.com>2020-09-02 08:43:12 +0200
committerJordan Augé <jordan.auge+fdio@cisco.com>2020-09-18 16:54:01 +0200
commitfe310f8b7a54f31b7270107b57b5ffcc00966f45 (patch)
treeeaf58421f2ad4829188444aee519f2fd2c647b2a
parent7d1d3c33387effd7baa91c55dfc1bd711fd4ffe1 (diff)
[HICN-555] Base data structures: vector, bitmap, pool (code + doc)
Change-Id: I30b559974d4bdf57eb458f1c43a71f47598c2e70 Signed-off-by: Jordan Augé <jordan.auge+fdio@cisco.com>
-rw-r--r--hicn-light/src/hicn/base/bitmap.h43
-rw-r--r--hicn-light/src/hicn/base/pool.c85
-rw-r--r--hicn-light/src/hicn/base/pool.h207
-rw-r--r--hicn-light/src/hicn/base/test/test-vector.cc12
-rw-r--r--hicn-light/src/hicn/base/vector.c36
-rw-r--r--hicn-light/src/hicn/base/vector.h220
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 df94b80..bebbf88 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 abca864..0f5f728 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 cdb0fc3..8335c9b 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 71b38a2..e5eeff9 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 d090588..b994a44 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 47cfdd1..06ffa44 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 */