diff options
Diffstat (limited to 'hicn-light')
| -rw-r--r-- | hicn-light/src/hicn/base/bitmap.h | 43 | ||||
| -rw-r--r-- | hicn-light/src/hicn/base/pool.c | 85 | ||||
| -rw-r--r-- | hicn-light/src/hicn/base/pool.h | 207 | ||||
| -rw-r--r-- | hicn-light/src/hicn/base/test/test-vector.cc | 12 | ||||
| -rw-r--r-- | hicn-light/src/hicn/base/vector.c | 36 | ||||
| -rw-r--r-- | hicn-light/src/hicn/base/vector.h | 220 |
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 */ |