Mercurial > molko
changeset 228:2734223d3daf
core: add a alloc_pool module
A miniamlist expandable array that gros each time new data is required, ideal
where data must be allocated dynamically without knowing in advance the number
of items.
author | David Demelier <markand@malikania.fr> |
---|---|
date | Thu, 19 Nov 2020 14:11:11 +0100 |
parents | befa2e855d3b |
children | e71039d820a7 |
files | libcore/core/alloc.c libcore/core/alloc.h librpg/rpg/tileset-file.c librpg/rpg/tileset-file.h tests/CMakeLists.txt tests/test-alloc.c |
diffstat | 6 files changed, 320 insertions(+), 46 deletions(-) [+] |
line wrap: on
line diff
--- a/libcore/core/alloc.c Thu Nov 19 10:48:46 2020 +0100 +++ b/libcore/core/alloc.c Thu Nov 19 14:11:11 2020 +0100 @@ -150,3 +150,52 @@ return ret; } + +bool +alloc_pool_init(struct alloc_pool *pool, size_t elemsize, void (*finalizer)(void *)) +{ + assert(pool); + assert(elemsize != 0); + + if (!(pool->data = alloc_array(ALLOC_POOL_INIT_DEFAULT, elemsize))) + return false; + + pool->elemsize = elemsize; + pool->size = 0; + pool->capacity = ALLOC_POOL_INIT_DEFAULT; + pool->finalizer = finalizer; + + return true; +} + +void * +alloc_pool_new(struct alloc_pool *pool) +{ + assert(pool); + + if (pool->size >= pool->capacity) { + void *newptr = alloc_rearray(pool->data, pool->capacity * 2, pool->elemsize); + + if (!newptr) + return NULL; + + pool->data = newptr; + pool->capacity *= 2; + } + + return ((unsigned char *)pool->data) + pool->size++ * pool->elemsize; +} + +void +alloc_pool_finish(struct alloc_pool *pool) +{ + if (pool->finalizer) { + unsigned char *tab = pool->data; + + for (size_t i = 0; i < pool->size; ++i) + pool->finalizer(tab + i * pool->elemsize); + } + + free(pool->data); + memset(pool, 0, sizeof (*pool)); +}
--- a/libcore/core/alloc.h Thu Nov 19 10:48:46 2020 +0100 +++ b/libcore/core/alloc.h Thu Nov 19 14:11:11 2020 +0100 @@ -30,11 +30,18 @@ * To change the allocator, simply modify the global allocator object. */ +#include <stdbool.h> #include <stddef.h> #include "util.h" /** + * \brief Default size to allocate in struct alloc_pool. + * \warning Must be a power of 2. + */ +#define ALLOC_POOL_INIT_DEFAULT 32 + +/** * \brief Global allocator strategy. */ struct allocator { @@ -74,6 +81,44 @@ }; /** + * \brief Pool allocator. + * + * This small structure is a helper to reallocate data each time a new slot is + * requested. It allocates twice as the current storage when size exceeds + * capacity. + * + * It uses realloc mechanism to upgrade the new storage space so pointers + * returned must not be referenced directly. + * + * It is designed in mind to help allocating resources locally that may be + * referenced in another module without having to manage an array from the user + * code. Because it is designed for this responsability only it only supports + * insertion. + * + * The initial capacity is controlled by the ALLOC_POOL_INIT_DEFAULT macro and + * **must** be a power of two. + * + * A custom finalizer function can be set to finalize each individual object if + * necessary. + */ +struct alloc_pool { + void *data; /*!< (+?) Pointer to the region. */ + size_t elemsize; /*!< (-) Size of individual element. */ + size_t size; /*!< (-) Number of items in array. */ + size_t capacity; /*!< (-) Current capacity. */ + + /** + * (+?) Optional finalizer. + * + * This function will be invoked for every element when \ref + * alloc_pool_finish is called. + * + * \param data the element to finalize + */ + void (*finalizer)(void *data); +}; + +/** * \brief Global allocator object. */ extern struct allocator allocator; @@ -144,7 +189,7 @@ /** * Duplicate region pointer by ptr. * - * This function calls \ref alloc to allocate memory. + * This function calls \ref alloc_new to allocate memory. * * \pre ptr != NULL * \param ptr the pointer @@ -154,4 +199,50 @@ void * alloc_dup(const void *ptr, size_t size); +/** + * Initialize the pool. + * + * This will effectively create a initial storage according to + * ALLOC_POOL_INIT_DEFAULT. + * + * This function effectively use the global allocator object to initialize the + * array. + * + * \pre pool != NULL + * \pre elemsize != 0 + * \param pool the pool to initialize + * \param elemsize size of each individual element + * \param finalizer a finalizer to use when clearing the pool. + * \return True if allocation suceedeed. + */ +bool +alloc_pool_init(struct alloc_pool *pool, size_t elemsize, void (*finalizer)(void *)); + +/** + * Request a new slot from the pool. + * + * If the current size has reached the capacity, it will be doubled in that case + * it is possible that all previous pointer may be invalidated. + * + * This function effectively use the global allocator object to realloc the + * array. + * + * \pre pool != NULL + * \param pool the pool + * \return The pointer to the region. + */ +void * +alloc_pool_new(struct alloc_pool *pool); + +/** + * Finalize the pool and all individual element if a finalizer is set. + * + * You must call \ref alloc_pool_init again before reusing it. + * + * \pre pool != NULL + * \param pool the pool to clear + */ +void +alloc_pool_finish(struct alloc_pool *pool); + #endif /* !MOLKO_ALLOC_H */
--- a/librpg/rpg/tileset-file.c Thu Nov 19 10:48:46 2020 +0100 +++ b/librpg/rpg/tileset-file.c Thu Nov 19 14:11:11 2020 +0100 @@ -38,7 +38,33 @@ #define MAX_F(v) MAX_F_(v) #define MAX_F_(v) "%" #v "[^|]" -struct tileset_file_animation { +/* + * This is how memory for animations is allocated in the tileset_file + * structure. + * + * As animations require a texture and a sprite to be present, we need to store + * them locally in the tileset structure. + * + * tileset_file->anims[0] array (struct anim): + * + * [0] [1] [N] + * | texture | texture | texture + * | sprite | sprite | sprite + * | animation | animation | animation + * + * tileset_file->anims[1] array (struct tileset_animation): + * + * [0] [1] [N] + * | id | id | id + * | animation ^ | animation ^ | animation ^ + * + * The second array is the exposed array through the tileset->anims pointer, + * animations are referenced from the first array. This is because user may need + * or replace the tileset by itself and as such we need to keep track of the + * resource the tileset_file have allocated itself. + */ + +struct anim { struct texture texture; struct sprite sprite; struct animation animation; @@ -64,7 +90,7 @@ }; static int -tiledef_cmp(const void *d1, const void *d2) +tileset_tiledef_cmp(const void *d1, const void *d2) { const struct tileset_tiledef *mtd1 = d1; const struct tileset_tiledef *mtd2 = d2; @@ -78,7 +104,7 @@ } static int -anim_cmp(const void *d1, const void *d2) +tileset_animation_cmp(const void *d1, const void *d2) { const struct tileset_animation *mtd1 = d1; const struct tileset_animation *mtd2 = d2; @@ -116,25 +142,41 @@ short x, y; unsigned short id, w, h; - struct tileset_tiledef *tiledefs = NULL; - size_t tiledefsz = 0; + struct tileset_file *tf = ctx->tf; + struct tileset_tiledef *td; + + if (!alloc_pool_init(&tf->tiledefs, sizeof (*td), NULL)) + return false; while (fscanf(ctx->fp, "%hu|%hd|%hd|%hu|%hu\n", &id, &x, &y, &w, &h) == 5) { - tiledefs = alloc_rearray(tiledefs, ++tiledefsz, sizeof (*tiledefs)); - tiledefs[tiledefsz - 1].id = id; - tiledefs[tiledefsz - 1].x = x; - tiledefs[tiledefsz - 1].y = y; - tiledefs[tiledefsz - 1].w = w; - tiledefs[tiledefsz - 1].h = h; + if (!(td = alloc_pool_new(&tf->tiledefs))) + return false; + + td->id = id; + td->x = x; + td->y = y; + td->w = w; + td->h = h; } - qsort(tiledefs, tiledefsz, sizeof (*tiledefs), tiledef_cmp); - ctx->tileset->tiledefs = ctx->tf->tiledefs = tiledefs; - ctx->tileset->tiledefsz = tiledefsz; + /* + * Sort the array and expose it through the tileset->tiledefs pointer. + */ + qsort(tf->tiledefs.data, tf->tiledefs.size, tf->tiledefs.elemsize, tileset_tiledef_cmp); + ctx->tileset->tiledefs = tf->tiledefs.data; + ctx->tileset->tiledefsz = tf->tiledefs.size; return true; } +static void +anim_finish(void *data) +{ + struct anim *anim = data; + + texture_finish(&anim->texture); +} + static bool parse_animations(struct context *ctx, const char *line) { @@ -145,39 +187,44 @@ char filename[FILENAME_MAX + 1], path[PATH_MAX]; struct tileset *tileset = ctx->tileset; struct tileset_file *tf = ctx->tf; + struct tileset_animation *ta; + struct anim *anim; + + if (!alloc_pool_init(&tf->anims[0], sizeof (*anim), anim_finish) || + !alloc_pool_init(&tf->anims[1], sizeof (*ta), NULL)) + return false; while (fscanf(ctx->fp, "%hu|" MAX_F(FILENAME_MAX) "|%u", &id, filename, &delay) == 3) { - struct tileset_file_animation *tfa; - - /* - * We need two arrays because one must contains sprite, texture - * and the animation while the tileset user side API only use - * one animation reference. - */ - tf->tfasz++; - tf->tfas = alloc_rearray(tf->tfas, tf->tfasz, sizeof (*tf->tfas)); - tfa = &tf->tfas[tf->tfasz - 1]; - - /* This is the real user-side tileset array of animations. */ - tf->anims = alloc_rearray(tf->anims, tf->tfasz, sizeof (*tf->anims)); + if (!(anim = alloc_pool_new(&tf->anims[0]))) + return false; snprintf(path, sizeof (path), "%s/%s", ctx->basedir, filename); - if (!image_open(&tfa->texture, path)) + if (!image_open(&anim->texture, path)) return false; /* Initialize animation. */ - sprite_init(&tfa->sprite, &tfa->texture, ctx->tilewidth, ctx->tileheight); - animation_init(&tfa->animation, &tfa->sprite, delay); + sprite_init(&anim->sprite, &anim->texture, ctx->tilewidth, ctx->tileheight); + animation_init(&anim->animation, &anim->sprite, delay); - /* Finally store it in the tiledef. */ - tf->anims[tf->tfasz - 1].id = id; - tf->anims[tf->tfasz - 1].animation = &tfa->animation; + /* + * Now create the real tileset_animation visible in + * tileset->anims. + */ + if (!(ta = alloc_pool_new(&tf->anims[1]))) + return false; + + ta->id = id; + ta->animation = &anim->animation; } - qsort(tf->anims, tf->tfasz, sizeof (*tf->anims), anim_cmp); - tileset->anims = tf->anims; - tileset->animsz = tf->tfasz; + /* + * Sort and expose the animation array through the tileset->animsz + * pointer. + */ + qsort(tf->anims[1].data, tf->anims[1].size, tf->anims[1].elemsize, tileset_animation_cmp); + tileset->anims = tf->anims[1].data; + tileset->animsz = tf->anims[1].size; return true; } @@ -282,13 +329,11 @@ { assert(tf); - for (size_t i = 0; i < tf->tfasz; ++i) - texture_finish(&tf->tfas[i].texture); + alloc_pool_finish(&tf->tiledefs); + alloc_pool_finish(&tf->anims[0]); + alloc_pool_finish(&tf->anims[1]); texture_finish(&tf->image); - free(tf->tiledefs); - free(tf->tfas); - free(tf->anims); memset(tf, 0, sizeof (*tf)); }
--- a/librpg/rpg/tileset-file.h Thu Nov 19 10:48:46 2020 +0100 +++ b/librpg/rpg/tileset-file.h Thu Nov 19 14:11:11 2020 +0100 @@ -22,6 +22,7 @@ #include <stdbool.h> #include <stddef.h> +#include <core/alloc.h> #include <core/sprite.h> #include <core/texture.h> @@ -29,12 +30,10 @@ struct tileset_tiledef; struct tileset_file { - struct tileset_tiledef *tiledefs; /*!< (*) Owned tile definitions. */ + struct alloc_pool tiledefs; + struct alloc_pool anims[2]; struct texture image; /*!< (*) Owned image file. */ struct sprite sprite; /*!< (*) Owned sprite. */ - struct tileset_file_animation *tfas; /*!< (*) Owned per tile animations. */ - size_t tfasz; /*!< (*) Onwed number of tiles. */ - struct tileset_animation *anims; /*!< (*) Owned animations array. */ }; bool
--- a/tests/CMakeLists.txt Thu Nov 19 10:48:46 2020 +0100 +++ b/tests/CMakeLists.txt Thu Nov 19 14:11:11 2020 +0100 @@ -20,6 +20,7 @@ molko_define_test(TARGET action SOURCES test-action.c) molko_define_test(TARGET action-script SOURCES test-action-script.c) +molko_define_test(TARGET alloc SOURCES test-alloc.c) molko_define_test(TARGET color SOURCES test-color.c) molko_define_test(TARGET error SOURCES test-error.c)
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/tests/test-alloc.c Thu Nov 19 14:11:11 2020 +0100 @@ -0,0 +1,89 @@ +/* + * test-alloc.c -- test allocators + * + * Copyright (c) 2020 David Demelier <markand@malikania.fr> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#define GREATEST_USE_ABBREVS 0 +#include <greatest.h> + +#include <core/alloc.h> + +struct point { + int x; + int y; +}; + +GREATEST_TEST +test_basics_simple(void) +{ + struct alloc_pool pool; + struct point *p; + + GREATEST_ASSERT(alloc_pool_init(&pool, sizeof (*p), NULL)); + GREATEST_ASSERT_EQ(sizeof (*p), pool.elemsize); + GREATEST_ASSERT_EQ(0, pool.size); + GREATEST_ASSERT_EQ(ALLOC_POOL_INIT_DEFAULT, pool.capacity); + + /* Create until we reach the capacity. */ + for (size_t i = 0; i < pool.capacity; ++i) { + p = alloc_pool_new(&pool); + p->x = (int)i + 1; + p->y = (int)i + 1; + } + + GREATEST_ASSERT_EQ(pool.size, pool.capacity); + + /* Verify values are correct. */ + for (size_t i = 0; i < pool.size; ++i) { + p = ((struct point *)pool.data) + i; + + GREATEST_ASSERT_EQ((int)i + 1, p->x); + GREATEST_ASSERT_EQ((int)i + 1, p->y); + } + + /* Now it should reallocate. */ + p = alloc_pool_new(&pool); + p->x = 9999; + p->y = 9999; + + GREATEST_ASSERT(pool.capacity > pool.size); + + alloc_pool_finish(&pool); + + GREATEST_ASSERT_EQ(NULL, pool.data); + GREATEST_ASSERT_EQ(0, pool.elemsize); + GREATEST_ASSERT_EQ(0, pool.size); + GREATEST_ASSERT_EQ(0, pool.capacity); + + GREATEST_PASS(); +} + +GREATEST_SUITE(suite_basics) +{ + GREATEST_RUN_TEST(test_basics_simple); +} + +GREATEST_MAIN_DEFS(); + +int +main(int argc, char **argv) +{ + GREATEST_MAIN_BEGIN(); + GREATEST_RUN_SUITE(suite_basics); + GREATEST_MAIN_END(); + + return 0; +}