diff options
Diffstat (limited to 'hicn-light/src/hicn/base')
| -rw-r--r-- | hicn-light/src/hicn/base/bitmap.h | 126 | ||||
| -rw-r--r-- | hicn-light/src/hicn/base/common.h | 4 | ||||
| -rw-r--r-- | hicn-light/src/hicn/base/pool.c | 89 | ||||
| -rw-r--r-- | hicn-light/src/hicn/base/pool.h | 19 | ||||
| -rw-r--r-- | hicn-light/src/hicn/base/test/test-bitmap.cc | 122 | ||||
| -rw-r--r-- | hicn-light/src/hicn/base/test/test-pool.cc | 140 | ||||
| -rw-r--r-- | hicn-light/src/hicn/base/test/test-vector.cc | 96 | ||||
| -rw-r--r-- | hicn-light/src/hicn/base/vector.c | 43 | ||||
| -rw-r--r-- | hicn-light/src/hicn/base/vector.h | 52 |
9 files changed, 516 insertions, 175 deletions
diff --git a/hicn-light/src/hicn/base/bitmap.h b/hicn-light/src/hicn/base/bitmap.h index 8fd9fcd70..4a78af567 100644 --- a/hicn-light/src/hicn/base/bitmap.h +++ b/hicn-light/src/hicn/base/bitmap.h @@ -23,7 +23,12 @@ #ifndef UTIL_BITMAP_H #define UTIL_BITMAP_H +#include <assert.h> #include <string.h> +#include <sys/param.h> // MIN, MAX + +#include <hicn/util/log.h> + #include "common.h" #include "vector.h" @@ -37,8 +42,9 @@ typedef uint_fast32_t bitmap_t; * @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))) +#define bitmap_init(bitmap, init_size, max_size) \ + vector_init(bitmap, next_pow2(init_size / BITMAP_WIDTH(bitmap)), \ + max_size == 0 ? 0 : next_pow2(max_size / BITMAP_WIDTH(bitmap))) /* * @brief Ensures a bitmap is sufficiently large to hold an element at the @@ -51,7 +57,13 @@ typedef uint_fast32_t bitmap_t; * - 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)) +static inline +int +bitmap_ensure_pos(bitmap_t * bitmap, off_t pos) +{ + size_t offset = pos / BITMAP_WIDTH(bitmap); + return vector_ensure_pos(bitmap, offset); +} /** * @brief Retrieve the state of the i-th bit in the bitmap. @@ -59,7 +71,15 @@ typedef uint_fast32_t bitmap_t; * @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)))) >> ((i) % BITMAP_WIDTH(bitmap))) +static inline +int +bitmap_get(const bitmap_t * bitmap, off_t i) +{ + size_t offset = i / BITMAP_WIDTH(bitmap); + size_t pos = i % BITMAP_WIDTH(bitmap); + size_t shift = BITMAP_WIDTH(bitmap) - pos - 1; + return (bitmap[offset] >> shift) & 1; +} /* * @brief Returns whether the i-th bit is set (equal to 1) in a bitmap. @@ -70,6 +90,7 @@ typedef uint_fast32_t bitmap_t; * @return bool */ #define bitmap_is_set(bitmap, i) (bitmap_get((bitmap), (i)) == 1) +#define bitmap_is_unset(bitmap, i) (bitmap_get((bitmap), (i)) == 0) /* * @brief Returns whether the i-th bit is unset (equal to 0) in a bitmap. @@ -79,19 +100,94 @@ typedef uint_fast32_t bitmap_t; * * @return bool */ -#define bitmap_is_unset(bitmap, i) (bitmap_get((bitmap), (i)) == 0) +static inline +int +bitmap_set(bitmap_t * bitmap, off_t i) +{ + if (bitmap_ensure_pos(bitmap, i) < 0) + return -1; + size_t offset = i / BITMAP_WIDTH(bitmap); + size_t pos = i % BITMAP_WIDTH(bitmap); + size_t shift = BITMAP_WIDTH(bitmap) - pos - 1; + bitmap[offset] |= 1ul << shift; + return 0; +} + +static inline +int +bitmap_unset(bitmap_t * bitmap, off_t i) +{ + if (bitmap_ensure_pos(bitmap, i) < 0) + return -1; + size_t offset = i / BITMAP_WIDTH(bitmap); + size_t pos = i % BITMAP_WIDTH(bitmap); + size_t shift = BITMAP_WIDTH(bitmap) - pos - 1; + bitmap[offset] &= ~ (1ul << shift); + return 0; +} + + +static inline +int +bitmap_set_range(bitmap_t * bitmap, off_t from, off_t to) +{ + assert(from <= to); + ssize_t offset_from = from / BITMAP_WIDTH(bitmap); + ssize_t offset_to = to / BITMAP_WIDTH(bitmap); + size_t pos_from = from % BITMAP_WIDTH(bitmap); + size_t pos_to = to % BITMAP_WIDTH(bitmap); + + + /* + * First block initialization is needed if <from> is not aligned with the + * bitmap element size or if to is within the same one. + */ + if ((pos_from != 0) || ((offset_to == offset_from) && (pos_to != BITMAP_WIDTH(bitmap) - 1))) { + size_t from_end = MIN(to, (offset_from + 1) * BITMAP_WIDTH(bitmap)); + for (size_t k = from; k < from_end; k++) { + if (bitmap_set(bitmap, k) < 0) + goto END; + } + } + + /* + * Second block is needed if <to> is not aligned with the bitmap element + * size + */ + if ((pos_to != BITMAP_WIDTH(bitmap) - 1) && (offset_to != offset_from)) { + size_t to_start = MAX(from, offset_to * BITMAP_WIDTH(bitmap)); + for (size_t k = to_start; k < to; k++) { + if (bitmap_set(bitmap, k) < 0) + goto END; + } + } + + if (pos_from != 0) + offset_from += 1; + if (pos_to != BITMAP_WIDTH(bitmap) - 1) + offset_to -= 1; + + /* + * We need to cover both elements at position offset_from and offset_to + * provided that offset_from is not bigger + */ + if (offset_to >= offset_from) { + memset(&bitmap[offset_from], 0xFF, (offset_to - offset_from + 1) * sizeof(bitmap[0])); + } + + return 0; + +END: + ERROR("Error setting bitmap range\n"); + return -1; +} -#define bitmap_set(bitmap, i) bitmap[(i) / BITMAP_WIDTH(bitmap)] |= 1 << ((i) % BITMAP_WIDTH(bitmap)) +#define bitmap_set_to(bitmap, to) bitmap_set_range((bitmap), 0, (to)) -#define bitmap_unset(bitmap, i) bitmap[(i) / BITMAP_WIDTH(bitmap)] &= ~ (1 << ((i) % BITMAP_WIDTH(bitmap))) +#define bitmap_free(bitmap) vector_free(bitmap) -#define bitmap_set_to(bitmap, pos) \ -do { \ - size_t offset = (pos / BITMAP_WIDTH(bitmap) + 1); \ - memset(bitmap, 0xFF, pos * sizeof(bitmap[0])); \ - size_t set_bits = offset * BITMAP_WIDTH(bitmap); \ - for (unsigned i = pos; i < set_bits; i++) \ - bitmap_unset(bitmap, i); \ -} while(0); +#ifdef WITH_TESTS +#define bitmap_get_alloc_size(bitmap) vector_get_alloc_size(bitmap) +#endif /* WITH_TESTS */ #endif /* UTIL_BITMAP_H */ diff --git a/hicn-light/src/hicn/base/common.h b/hicn-light/src/hicn/base/common.h index 996050308..9ba426bb8 100644 --- a/hicn-light/src/hicn/base/common.h +++ b/hicn-light/src/hicn/base/common.h @@ -46,7 +46,7 @@ uint32_t __inline __builtin_clz(uint32_t value) { return 32; } -uint32_t __inline __builtin_clzll(uint64_t value) { +uint32_t __inline __builtin_clzl2(uint64_t value) { uint32_t leading_zero = 0; if (_BitScanReverse64(&leading_zero, value)) return 63 - leading_zero; @@ -57,6 +57,6 @@ uint32_t __inline __builtin_clzll(uint64_t value) { #define __builtin_clzl __builtin_clzll #endif -#define next_pow2(x) (x == 1 ? 1 : 1<<(64-__builtin_clzl(x-1))) +#define next_pow2(x) (x <= 1 ? 1 : 1ul <<(64-__builtin_clzl(x-1))) #endif /* UTIL_COMMON_H */ diff --git a/hicn-light/src/hicn/base/pool.c b/hicn-light/src/hicn/base/pool.c index 0f5f728e3..31abb13f1 100644 --- a/hicn-light/src/hicn/base/pool.c +++ b/hicn-light/src/hicn/base/pool.c @@ -30,36 +30,52 @@ #include "common.h" #include "pool.h" +#include <stdio.h> // XXX + void -_pool_init(void ** pool_ptr, size_t elt_size, size_t max_size) +_pool_init(void ** pool_ptr, size_t elt_size, size_t init_size, size_t max_size) { assert(pool_ptr); assert(elt_size); - pool_hdr_t * ph = calloc(POOL_HDRLEN + elt_size * max_size, 1); - if (!ph) { - *pool_ptr = NULL; - return; - } + init_size = next_pow2(init_size); + + if (max_size && init_size > max_size) + goto ERR_MAX_SIZE; + + /* The initial pool size is rounded to the next power of two */ + size_t alloc_size = next_pow2(init_size); + + pool_hdr_t * ph = calloc(POOL_HDRLEN + alloc_size * elt_size, 1); + if (!ph) + goto ERR_MALLOC; ph->elt_size = elt_size; + ph->alloc_size = alloc_size; ph->max_size = max_size; /* Free indices */ off_t * free_indices; - 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; + vector_init(free_indices, init_size, max_size); + for(unsigned i = 0; i < init_size; i++) + free_indices[i] = (init_size - 1) - i; + vector_len(free_indices) = init_size; ph->free_indices = free_indices; /* Free bitmap */ uint_fast32_t * fb = ph->free_bitmap; - bitmap_init(fb, max_size); - bitmap_set_to(fb, max_size); + bitmap_init(fb, init_size, max_size); + bitmap_set_to(fb, init_size); ph->free_bitmap = fb; *pool_ptr = (uint8_t*)ph + POOL_HDRLEN; + + return; + +ERR_MALLOC: +ERR_MAX_SIZE: + *pool_ptr = NULL; + return; } void @@ -73,42 +89,59 @@ void _pool_resize(void ** pool_ptr, size_t elt_size) { pool_hdr_t * ph = pool_hdr(*pool_ptr); - size_t old_elts = ph->max_size; - size_t new_elts = old_elts * 2; + size_t old_size = ph->alloc_size; + size_t new_size = old_size * 2; + + if (ph->max_size && new_size > ph->max_size) + goto ERR_MAX_SIZE; /* Double pool storage */ - ph = realloc(ph, POOL_HDRLEN + new_elts * elt_size); - if (!ph) { - *pool_ptr = NULL; - return; - } + ph = realloc(ph, POOL_HDRLEN + new_size * elt_size); + if (!ph) + goto ERR_REALLOC; ph->elt_size = elt_size; - ph->max_size = new_elts; + ph->alloc_size = new_size; /* - * After resize, the pool will have old_elts free indices, ranging from - * old_elts to (new_elts - 1) + * After resize, the pool will have new free indices, ranging from + * old_size to (new_size - 1) */ - off_t * free_indices = ph->free_indices; - vector_ensure_pos(free_indices, old_elts); - for (unsigned i = 0; i < old_elts; i++) - free_indices[i] = new_elts - 1 - i; + vector_ensure_pos(ph->free_indices, old_size); + for (unsigned i = 0; i < old_size; i++) + ph->free_indices[i] = new_size - 1 - i; + vector_len(ph->free_indices) = old_size; + + /* We also need to update the bitmap */ + bitmap_ensure_pos(ph->free_bitmap, new_size - 1); + bitmap_set_range(ph->free_bitmap, old_size, new_size - 1); /* Reassign pool pointer */ *pool_ptr = (uint8_t*)ph + POOL_HDRLEN; + + return; + +ERR_REALLOC: +ERR_MAX_SIZE: + *pool_ptr = NULL; + return; } -void +off_t _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) + if (l == 0) { _pool_resize(pool_ptr, elt_size); + ph = pool_hdr(*pool_ptr); + l = vector_len(ph->free_indices); + } off_t free_id = ph->free_indices[l - 1]; vector_len(ph->free_indices)--; + bitmap_unset(ph->free_bitmap, free_id); *elt = *pool_ptr + free_id; memset(*elt, 0, sizeof(elt)); + return free_id; } void diff --git a/hicn-light/src/hicn/base/pool.h b/hicn-light/src/hicn/base/pool.h index 8335c9bc5..57172192b 100644 --- a/hicn-light/src/hicn/base/pool.h +++ b/hicn-light/src/hicn/base/pool.h @@ -51,6 +51,7 @@ typedef struct { size_t elt_size; + size_t alloc_size; size_t max_size; uint_fast32_t * free_bitmap; /* bitmap of free indices */ off_t * free_indices; /* vector of free indices */ @@ -76,7 +77,7 @@ typedef struct { * * NOTE: that an empty pool might be equal to NULL. */ -void _pool_init(void ** pool_ptr, size_t elt_size, size_t max_size); +void _pool_init(void ** pool_ptr, size_t elt_size, size_t init_size, size_t max_size); /** * @brief Free a pool data structure (helper). @@ -105,7 +106,7 @@ void _pool_resize(void ** pool_ptr, size_t elt_size); * NOTES: * - The memory chunk is cleared upon attribution */ -void _pool_get(void ** pool, void ** elt, size_t elt_size); +off_t _pool_get(void ** pool, void ** elt, size_t elt_size); /** * @brief Put an element back into the pool data structure (helper). @@ -127,8 +128,8 @@ void _pool_put(void ** pool, void ** elt, size_t elt_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_init(pool, init_size, max_size) \ + _pool_init((void**)&pool, sizeof(pool[0]), init_size, max_size); /** * @brief Free a pool data structure. @@ -168,6 +169,8 @@ void _pool_put(void ** pool, void ** elt, size_t elt_size); #define pool_validate_id(pool, id) \ bitmap_is_unset((pool_hdr(pool))->free_bitmap, (id)) +#define pool_get_free_indices_size(pool) vector_len(pool_hdr(pool)->free_indices) + /** * @brief Returns the current length of the pool. * @@ -180,7 +183,7 @@ void _pool_put(void ** pool, void ** elt, size_t elt_size); * size of the pool. */ #define pool_len(pool) \ - (pool_hdr(pool)->max_size - vector_len((pool_hdr(pool)->free_indices))) + (pool_hdr(pool)->alloc_size - pool_get_free_indices_size(pool)) /** * @brief Enumerate elements from a pool. @@ -226,4 +229,10 @@ do { \ pool_enumerate((pool), _pool_var(i), (eltp), BODY); \ } while(0) +#ifdef WITH_TESTS +#define pool_get_alloc_size(bitmap) pool_hdr(pool)->alloc_size +#define pool_get_free_indices(pool) pool_hdr(pool)->free_indices +#define pool_get_free_bitmap(pool) pool_hdr(pool)->free_bitmap +#endif /* WITH_TESTS */ + #endif /* UTIL_POOL_H */ diff --git a/hicn-light/src/hicn/base/test/test-bitmap.cc b/hicn-light/src/hicn/base/test/test-bitmap.cc index d6ab94f3e..1a62edba3 100644 --- a/hicn-light/src/hicn/base/test/test-bitmap.cc +++ b/hicn-light/src/hicn/base/test/test-bitmap.cc @@ -24,60 +24,114 @@ #include <netinet/in.h> extern "C" { -#include <hicn/base/vector.h> +#define WITH_TESTS #include <hicn/base/bitmap.h> } +#define DEFAULT_SIZE 10 + class BitmapTest : public ::testing::Test { - protected: - BitmapTest() { - } +protected: + BitmapTest() { } - virtual ~BitmapTest() { + virtual ~BitmapTest() { } - // You can do clean-up work that doesn't throw exceptions here. - } + bitmap_t * bitmap; +}; - // If the constructor and destructor are not enough for setting up - // and cleaning up each test, you can define the following methods: +/* + * TEST: bitmap allocation + */ +TEST_F(BitmapTest, BitmapAllocation) +{ + int rc; - virtual void SetUp() { - bitmap_init(bitmap, 1024); - } + /* + * We take a value < 32 on purpose to avoid confusion on the choice of a 32 + * or 64 bit integer for storage + */ + size_t size_not_pow2 = DEFAULT_SIZE; + bitmap_init(bitmap, size_not_pow2, 0); - virtual void TearDown() { - free(bitmap); - } - uint32_t *bitmap; -}; + /* + * Bitmap should have been allocated with a size rounded to the next power + * of 2 + */ + EXPECT_EQ(bitmap_get_alloc_size(bitmap), 1); + + /* By default, no element should be set */ + EXPECT_FALSE(bitmap_is_set(bitmap, 0)); + EXPECT_TRUE(bitmap_is_unset(bitmap, 0)); + + EXPECT_EQ(bitmap_get_alloc_size(bitmap), 1); + + EXPECT_FALSE(bitmap_is_set(bitmap, size_not_pow2 - 1)); + EXPECT_TRUE(bitmap_is_unset(bitmap, size_not_pow2 - 1)); + + /* Bitmap should not have been reallocated */ + EXPECT_EQ(bitmap_get_alloc_size(bitmap), 1); + + /* After setting a bit after the end, bitmap should have been reallocated */ + bitmap_set(bitmap, sizeof(bitmap[0]) * 8 - 1); + EXPECT_EQ(bitmap_get_alloc_size(bitmap), 1); + + /* After setting a bit after the end, bitmap should have been reallocated */ + rc = bitmap_set(bitmap, sizeof(bitmap[0]) * 8); + EXPECT_GE(rc, 0); + EXPECT_EQ(bitmap_get_alloc_size(bitmap), 2); + + rc = bitmap_set(bitmap, sizeof(bitmap[0]) * 8 + 1); + EXPECT_GE(rc, 0); + EXPECT_EQ(bitmap_get_alloc_size(bitmap), 2); + + bitmap_free(bitmap); + + size_t size_pow2 = 16; + + /* Limiting test for allocation size */ + bitmap_init(bitmap, size_pow2, 0); + EXPECT_EQ(bitmap_get_alloc_size(bitmap), 1); + + bitmap_free(bitmap); +} TEST_F(BitmapTest, BitmapSet) { - bitmap_set(bitmap, 20); - EXPECT_TRUE(bitmap_is_set(bitmap, 20)); - EXPECT_FALSE(bitmap_is_unset(bitmap, 20)); - EXPECT_FALSE(bitmap_is_set(bitmap, 19)); - EXPECT_TRUE(bitmap_is_unset(bitmap, 19)); + bitmap_init(bitmap, DEFAULT_SIZE, 0); + + bitmap_set(bitmap, 20); + EXPECT_TRUE(bitmap_is_set(bitmap, 20)); + EXPECT_FALSE(bitmap_is_unset(bitmap, 20)); + EXPECT_FALSE(bitmap_is_set(bitmap, 19)); + EXPECT_TRUE(bitmap_is_unset(bitmap, 19)); + bitmap_free(bitmap); } TEST_F(BitmapTest, BitmapUnSet) { - bitmap_set(bitmap, 20); - bitmap_set(bitmap, 19); - bitmap_unset(bitmap, 20); - EXPECT_FALSE(bitmap_is_set(bitmap, 20)); - EXPECT_TRUE(bitmap_is_unset(bitmap, 20)); - EXPECT_TRUE(bitmap_is_set(bitmap, 19)); - EXPECT_FALSE(bitmap_is_unset(bitmap, 19)); + bitmap_init(bitmap, DEFAULT_SIZE, 0); + + bitmap_set(bitmap, 20); + bitmap_set(bitmap, 19); + bitmap_unset(bitmap, 20); + EXPECT_FALSE(bitmap_is_set(bitmap, 20)); + EXPECT_TRUE(bitmap_is_unset(bitmap, 20)); + EXPECT_TRUE(bitmap_is_set(bitmap, 19)); + EXPECT_FALSE(bitmap_is_unset(bitmap, 19)); + bitmap_free(bitmap); } TEST_F(BitmapTest, BitmapSetTo) { - bitmap_set_to(bitmap, 40); - EXPECT_TRUE(bitmap_is_set(bitmap, 20)); - EXPECT_TRUE(bitmap_is_set(bitmap, 21)); - EXPECT_TRUE(bitmap_is_unset(bitmap, 41)); - EXPECT_TRUE(bitmap_is_unset(bitmap, 42)); + bitmap_init(bitmap, DEFAULT_SIZE, 0); + + bitmap_set_to(bitmap, 40); + EXPECT_TRUE(bitmap_is_set(bitmap, 20)); + EXPECT_TRUE(bitmap_is_set(bitmap, 21)); + EXPECT_TRUE(bitmap_is_unset(bitmap, 41)); + EXPECT_TRUE(bitmap_is_unset(bitmap, 42)); + + bitmap_free(bitmap); } int main(int argc, char **argv) diff --git a/hicn-light/src/hicn/base/test/test-pool.cc b/hicn-light/src/hicn/base/test/test-pool.cc index 86c1c1270..1146ef2b7 100644 --- a/hicn-light/src/hicn/base/test/test-pool.cc +++ b/hicn-light/src/hicn/base/test/test-pool.cc @@ -24,45 +24,135 @@ #include <netinet/in.h> extern "C" { +#define WITH_TESTS #include <hicn/base/pool.h> } +/* + * TODO + * - test max_size + */ + +#define DEFAULT_SIZE 10 + class PoolTest : public ::testing::Test { - protected: - PoolTest() { - } +protected: + PoolTest() { } + virtual ~PoolTest() { } - virtual ~PoolTest() { - // You can do clean-up work that doesn't throw exceptions here. - } + int *pool; +}; - // If the constructor and destructor are not enough for setting up - // and cleaning up each test, you can define the following methods: +TEST_F(PoolTest, PoolAllocation) +{ + int rc; - virtual void SetUp() { - - } + pool_init(pool, DEFAULT_SIZE, 0); - virtual void TearDown() { - pool_free(pool); - } + size_t pool_size = next_pow2(DEFAULT_SIZE); - int *pool; -}; + EXPECT_EQ(pool_get_alloc_size(pool), pool_size); + + /* Check that free indices and bitmaps are correctly initialize */ + off_t * fi = pool_get_free_indices(pool); + EXPECT_EQ(vector_len(fi), pool_size); + EXPECT_EQ(fi[0], pool_size - 1); + EXPECT_EQ(fi[pool_size - 1], 0); + + /* The allocated size of the underlying vector should be the next power of two */ + EXPECT_EQ(vector_get_alloc_size(fi), pool_size); + + bitmap_t * fb = pool_get_free_bitmap(pool); + EXPECT_TRUE(bitmap_is_set(fb, 0)); + EXPECT_TRUE(bitmap_is_set(fb, pool_size - 2)); + EXPECT_TRUE(bitmap_is_set(fb, pool_size - 1)); + EXPECT_TRUE(bitmap_is_unset(fb, pool_size)); + + /* Getting elements from the pool should correctly update the free indices + * and bitmap */ + int * elt; + + rc = pool_get(pool, elt); + EXPECT_GE(rc, 0); + EXPECT_EQ(vector_len(fi), pool_size - 1); + EXPECT_TRUE(bitmap_is_unset(fb, 0)); + + rc = pool_get(pool, elt); + EXPECT_GE(rc, 0); + EXPECT_EQ(vector_len(fi), pool_size - 2); + EXPECT_TRUE(bitmap_is_unset(fb, 1)); + + for (unsigned i = 0; i < pool_size - 4; i++) { + rc = pool_get(pool, elt); + EXPECT_GE(rc, 0); + } + + rc = pool_get(pool, elt); + EXPECT_GE(rc, 0); + EXPECT_EQ(vector_len(fi), 1); + EXPECT_TRUE(bitmap_is_unset(fb, pool_size - 2)); + + rc = pool_get(pool, elt); + EXPECT_GE(rc, 0); + EXPECT_EQ(vector_len(fi), 0); + EXPECT_TRUE(bitmap_is_unset(fb, pool_size - 1)); + /* + * Getting elements within the allocated range should not have triggered a + * resize + */ + EXPECT_EQ(pool_len(pool), pool_size); + + /* + * Getting elements once the allocated range has been exceeded should + * trigger a resize + */ + rc = pool_get(pool, elt); + EXPECT_GE(rc, 0); + + EXPECT_EQ(pool_get_alloc_size(pool), pool_size * 2); + + EXPECT_EQ(pool_len(pool), pool_size + 1); + + /* + * Doubling the size, we should have again pool_size elements free, minus 1 + */ + EXPECT_EQ(pool_get_free_indices_size(pool), pool_size - 1); + + /* + * NOTE: this is wrong as there has been a realloc and the old fi + * pointer is now invalid + */ + //EXPECT_EQ(vector_len(fi), pool_size - 1); + + /* And the bitmap should also be correctly modified */ + fb = pool_get_free_bitmap(pool); + EXPECT_TRUE(bitmap_is_unset(fb, pool_size)); + + /* Check that surrounding values are also correct */ + EXPECT_TRUE(bitmap_is_unset(fb, pool_size - 1)); + EXPECT_TRUE(bitmap_is_set(fb, pool_size + 1)); + + /* Setting elements after should through */ + + /* Check that free indices and bitmaps are correctly updated */ + + pool_free(pool); +} + +// XXX todo : check state after several get and put TEST_F(PoolTest, PoolPut) { - pool_init(pool, 1024); - int* elt; - pool_get(pool, elt); - *elt = 10; + pool_init(pool, DEFAULT_SIZE, 0); + + int* elt; + pool_get(pool, elt); + *elt = 10; printf("2\n"); - pool_put(pool, elt); + pool_put(pool, elt); printf("3\n"); - - //pool_get(pool) - //loop_ = loop_create(); - //EXPECT_TRUE(loop_ != NULL); + + pool_free(pool); } diff --git a/hicn-light/src/hicn/base/test/test-vector.cc b/hicn-light/src/hicn/base/test/test-vector.cc index e5eeff910..59571b053 100644 --- a/hicn-light/src/hicn/base/test/test-vector.cc +++ b/hicn-light/src/hicn/base/test/test-vector.cc @@ -24,64 +24,90 @@ #include <netinet/in.h> extern "C" { +#define WITH_TESTS #include <hicn/base/vector.h> } +/* + * TODO + * - test max_size + */ + +#define DEFAULT_SIZE 10 + class VectorTest : public ::testing::Test { - protected: - VectorTest() { - } +protected: + VectorTest() { } + virtual ~VectorTest() { } - virtual ~VectorTest() { - // You can do clean-up work that doesn't throw exceptions here. - } + int *vector = NULL; +}; - // If the constructor and destructor are not enough for setting up - // and cleaning up each test, you can define the following methods: +/* TEST: Vector allocation and initialization */ +TEST_F(VectorTest, VectorAllocate) +{ + vector_init(vector, DEFAULT_SIZE, 0); - virtual void SetUp() {; - vector_init(vector, 1024); - } + /* Allocated size should be the next power of two */ + EXPECT_EQ(vector_get_alloc_size(vector), 16); - virtual void TearDown() { - vector_free(vector); - } + /* Setting elements within the allocated size should not trigger a resize */ + vector_ensure_pos(vector, 15); + EXPECT_EQ(vector_get_alloc_size(vector), 16); - int *vector = NULL; + /* Setting elements after should through */ + vector_ensure_pos(vector, 16); + EXPECT_EQ(vector_get_alloc_size(vector), 32); -}; + /* Check that free indices and bitmaps are correctly updated */ + + vector_free(vector); +} TEST_F(VectorTest, VectorSize) { - vector_push(vector, 109); - vector_push(vector, 109); - int size = vector_len(vector); - EXPECT_EQ(size, 2); - vector_push(vector, 109); - size = vector_len(vector); - EXPECT_EQ(size, 3); + vector_init(vector, DEFAULT_SIZE, 0); + + vector_push(vector, 109); + int size = vector_len(vector); + EXPECT_EQ(size, 1); + vector_push(vector, 109); + size = vector_len(vector); + EXPECT_EQ(size, 2); + vector_push(vector, 109); + size = vector_len(vector); + EXPECT_EQ(size, 3); + vector_free(vector); } TEST_F(VectorTest, VectorCheckValue) { - vector_push(vector, 109); - vector_push(vector, 200); - EXPECT_EQ(vector[0], 109); - EXPECT_EQ(vector[1], 200); + vector_init(vector, DEFAULT_SIZE, 0); + + vector_push(vector, 109); + vector_push(vector, 200); + EXPECT_EQ(vector[0], 109); + EXPECT_EQ(vector[1], 200); + + vector_free(vector); } TEST_F(VectorTest, VectorEnsurePos) { - printf (" %p\n", vector); - vector_ensure_pos(vector, 1025); - for (int i = 0; i <1025; i++) { - printf("i %d\n", i); + vector_init(vector, DEFAULT_SIZE, 0); + printf (" %p\n", vector); - vector_push(vector, i); - } - int size = vector_len(vector); - EXPECT_EQ(size, 1025); + vector_ensure_pos(vector, 1025); + for (int i = 0; i <1025; i++) { + //printf("i %d\n", i); + //printf (" %p\n", vector); + vector_push(vector, i); + } + int size = vector_len(vector); + EXPECT_EQ(size, 1025); + + vector_free(vector); } int main(int argc, char **argv) diff --git a/hicn-light/src/hicn/base/vector.c b/hicn-light/src/hicn/base/vector.c index b994a4465..43110414a 100644 --- a/hicn-light/src/hicn/base/vector.c +++ b/hicn-light/src/hicn/base/vector.c @@ -28,9 +28,10 @@ #define DEFAULT_VECTOR_SIZE 64 void -_vector_init(void ** vector_ptr, size_t elt_size, size_t init_size) +_vector_init(void ** vector_ptr, size_t elt_size, size_t init_size, size_t max_size) { assert(vector_ptr); + assert(max_size == 0 || init_size < max_size); if (init_size == 0) init_size = DEFAULT_VECTOR_SIZE; @@ -40,6 +41,7 @@ _vector_init(void ** vector_ptr, size_t elt_size, size_t init_size) vector_hdr_t * vh = vector_hdr(*vector_ptr); vh->cur_size = 0; + vh->max_size = max_size; } void @@ -49,23 +51,42 @@ _vector_free(void ** vector_ptr) *vector_ptr = NULL; } -bool +int _vector_resize(void ** vector_ptr, size_t elt_size, off_t pos) { - vector_hdr_t * vh = *vector_ptr ? vector_hdr(*vector_ptr) : NULL; + vector_hdr_t * vh; - /* - * 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; + size_t old_size; - vh = realloc(vh, VECTOR_HDRLEN + new_elts * elt_size); + if (*vector_ptr) { + vh = vector_hdr(*vector_ptr); + old_size = vh->alloc_size; + } else { + vh = NULL; + old_size = 0; + } + + /* Round the allocated size to the next power of 2 of the requested position */ + size_t new_size = next_pow2(pos); + + /* Don't grow the vector back */ + if (new_size < old_size) + return 0; + + /* Don't exceed maximum size (for init, check is done beforehand) */ + if (vh && vh->max_size && new_size > vh->max_size) + return -1; + + vh = realloc(vh, VECTOR_HDRLEN + new_size * elt_size); if (!vh) - return false; - vh->max_size = new_elts; + return -1; + vh->alloc_size = new_size; + + /* Zero out the newly allocated memory (except headers) */ + memset((uint8_t*)vh + VECTOR_HDRLEN + old_size * elt_size, 0, (new_size - old_size) * elt_size); /* Reassign vector pointer */ *vector_ptr = (uint8_t*)vh + VECTOR_HDRLEN; - return true; + return 0; } diff --git a/hicn-light/src/hicn/base/vector.h b/hicn-light/src/hicn/base/vector.h index 06ffa4428..ff12e6ee6 100644 --- a/hicn-light/src/hicn/base/vector.h +++ b/hicn-light/src/hicn/base/vector.h @@ -45,7 +45,7 @@ #ifndef UTIL_VECTOR_H #define UTIL_VECTOR_H -#include <stdbool.h> +#include <stdint.h> #include <stddef.h> #include <stdint.h> #include <string.h> @@ -58,7 +58,8 @@ typedef struct { size_t cur_size; /** Vector current size (corresponding to the highest used element). */ - size_t max_size; /** The currently allocated size. */ + size_t alloc_size; /** The currently allocated size. */ + size_t max_size; /** The maximum allowed size (0 = no limit) */ } vector_hdr_t; /* Make sure elements following the header are aligned */ @@ -80,7 +81,7 @@ typedef struct { * @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); +void _vector_init(void ** vector_ptr, size_t elt_size, size_t init_size, size_t max_size); /** * @brief Free a vector data structure. @@ -97,7 +98,7 @@ void _vector_free(void ** vector_ptr); * @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. + * @return int Flag indicating whether the vector has been correctly resized. * * NOTE: * - The resize operation does not specify the final size of the vector but @@ -105,7 +106,7 @@ void _vector_free(void ** vector_ptr); * 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); +int _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 @@ -115,7 +116,7 @@ bool _vector_resize(void ** vector_ptr, size_t elt_size, off_t pos); * @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. + * @return int Flag indicating whether the vector is available. * * NOTE: * - This function should always be called before writing to a vector element @@ -124,13 +125,13 @@ bool _vector_resize(void ** vector_ptr, size_t elt_size, off_t pos); * be resized. */ static inline -bool +int _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; + if (pos >= vh->alloc_size) + return _vector_resize(vector_ptr, elt_size, pos + 1); + return 0; } /** @@ -146,15 +147,17 @@ _vector_ensure_pos(void ** vector_ptr, size_t elt_size, off_t pos) * maximum size). */ static inline -bool +int _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; + if (_vector_ensure_pos(vector_ptr, elt_size, vh->cur_size) < 0) + return -1; + /* Always get header after a potential resize */ + memcpy((uint8_t*)*vector_ptr + vh->cur_size * elt_size, elt, elt_size); + vh = vector_hdr(*vector_ptr); + vh->cur_size++; + return 0; } /******************************************************************************/ @@ -165,9 +168,13 @@ _vector_push(void ** vector_ptr, size_t elt_size, void * elt) * * @param[in,out] vector Vector to allocate and initialize. * @param[in] max_size Maximum vector size (nonzero). + * + * NOTE: + * - Allocated memory is set to 0 (used by bitmap) */ -#define vector_init(vector, max_size) \ - _vector_init((void**)&vector, sizeof(vector[0]), max_size) + +#define vector_init(vector, init_size, max_size) \ + _vector_init((void**)&vector, sizeof(vector[0]), init_size, max_size) /** * @brief Free a vector data structure. @@ -184,7 +191,7 @@ _vector_push(void ** vector_ptr, size_t elt_size, void * elt) * @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. + * @return int Flag indicating whether the vector has been correctly resized. * * NOTE: * - The resize operation does not specify the final size of the vector but @@ -193,6 +200,7 @@ _vector_push(void ** vector_ptr, size_t elt_size, void * elt) * 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. + * - Newly allocated memory is set to 0 (used by bitmap) */ #define vector_resize(vector) _vector_resize((void**)&(vector), sizeof((vector)[0]), 0) @@ -241,6 +249,10 @@ do { \ * - 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 +#define vector_len(vector) vector_hdr(vector)->cur_size + +#ifdef WITH_TESTS +#define vector_get_alloc_size(vector) vector_hdr(vector)->alloc_size +#endif /* WITH_TESTS */ #endif /* UTIL_VECTOR_H */ |