Mercurial > molko
changeset 404:7321511052f6
core: rework alloc module
author | David Demelier <markand@malikania.fr> |
---|---|
date | Sat, 02 Apr 2022 16:58:33 +0200 |
parents | 7536be134718 |
children | 0e39368e106c |
files | doc/docs/dev/api/core/alloc.md src/libmlk-core/core/alloc.c src/libmlk-core/core/alloc.h src/libmlk-core/core/buf.h src/libmlk-rpg/rpg/map-file.c src/libmlk-rpg/rpg/tileset-file.c tests/test-alloc.c |
diffstat | 7 files changed, 257 insertions(+), 141 deletions(-) [+] |
line wrap: on
line diff
--- a/doc/docs/dev/api/core/alloc.md Sat Apr 02 16:58:23 2022 +0200 +++ b/doc/docs/dev/api/core/alloc.md Sat Apr 02 16:58:33 2022 +0200 @@ -10,6 +10,10 @@ allocation isn't much used in the core API, it is used in few places where static arrays would not fit (e.g. loading maps). +All of these functions are expected to never return NULL in case of memory +exhaustion but to call [panic][] instead as recovering from out-of-memory in a +game is near impossible. + ## Macros ### ALLOC\_POOL\_INIT\_DEFAULT @@ -41,14 +45,12 @@ #### alloc -Allocate the given `size` of bytes. Returns the allocated memory (or NULL on -failure). +Allocate the given `size` of bytes and return the memory region. -The default implementation uses malloc and calls [panic](panic.md) in case of -failure. +The default implementation uses malloc and calls [panic][] in case of failure. !!! note - You should set an [error](error.md) in case of failure. + You should also set an [error](error.md) in case of failure. ```c void *(*alloc)(size_t size) @@ -56,14 +58,12 @@ #### realloc -Realloc the region `ptr` with the new given `size`. Returns the new memory (may -be NULL). +Realloc the region `ptr` with the new given `size` and return the memory region. -The default implementation uses malloc and calls [panic](panic.md) in case of -failure. +The default implementation uses malloc and calls [panic][] in case of failure. !!! note - You should set an [error](error.md) in case of failure. + You should also set an [error](error.md) in case of failure. ```c void *(*realloc)(void *ptr, size_t size) @@ -81,19 +81,19 @@ ### alloc\_pool -Pool allocator. +Array 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 +This small structure is a helper to reallocate an array each time a new element +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. +returned in [alloc_pool_new](#alloc_pool_new) may get invalided when this +function is called. -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. +It is designed in mind to help allocating an array of elements when they can't +be determined at runtime (e.g. while reading a file) without the performance +cost of using [alloc_rearray](#alloc_rearray) every elements. The initial capacity is controlled by the [ALLOC\_POOL\_INIT\_DEFAULT](#macro-alloc_pool_init_default) macro and **must** @@ -102,12 +102,13 @@ A custom finalizer function can be set to finalize each individual object if necessary. -| Field | Access | Type | -|-----------------------|--------|----------| -| [data](#data) | (+?) | `void *` | -| [elemsize](#elemsize) | (-) | `size_t` | -| [size](#size) | (-) | `size_t` | -| [capacity](#capacity) | (-) | `size_t` | +| Field | Access | Type | +|-------------------------|--------|-----------------------------| +| [data](#data) | (+?) | `void *` | +| [elemsize](#elemsize) | (-) | `size_t` | +| [size](#size) | (-) | `size_t` | +| [capacity](#capacity) | (-) | `size_t` | +| [finalizer](#finalizer) | (+?) | `void (*finalizer)(void *)` | #### data @@ -166,8 +167,7 @@ ### alloc\_new -Allocate new uninitialized data of the given `size`. Returns the result of the -current allocator [alloc](#alloc) function set. +Allocate new uninitialized data of the given `size`. ```c void * @@ -176,7 +176,7 @@ ### alloc\_new0 -Invoke [alloc_new](#alloc_new) but zero initialize the memory. +Like [alloc_new](#alloc_new) but zero initialize the memory. ```c void * @@ -186,7 +186,6 @@ ### alloc\_array Allocate an uninitialized array of `len` elements of `elemsize` individually. -Returns the result of the current [alloc](#alloc) function set. ```c void * @@ -195,7 +194,7 @@ ### alloc\_array0 -Invoke [alloc_array](#alloc_array) but zero initialize the memory. +Like [alloc_array](#alloc_array) but zero initialize the memory. ```c void * @@ -205,7 +204,7 @@ ### alloc\_renew Reallocate the pointer `ptr` (which may be NULL) to the new `size` size. The -size can be 0. Returns the result of the current [alloc](#alloc) function set. +size can be 0. ```c void * @@ -215,8 +214,7 @@ ### alloc\_rearray Reallocate the pointer `ptr` (which may be NULL) as an array of `newlen` -elements of `elemsize` individually. Returns the result of the current -[realloc](#realloc) function set. +elements of `elemsize` individually. ```c void * @@ -227,8 +225,7 @@ Reallocate the `ptr` (which maybe NULL) with the `oldlen` as current number of elements of `elemsize` to the `newlen`. If the `newlen` is greater than oldlen, -the new region is cleared with 0. Returns the result of the current -[realloc](#realloc) function set. +the new region is cleared with 0. ```c void * @@ -246,8 +243,7 @@ ### alloc\_sdup -Duplicate the string `src`. Returns the result of current [alloc](#alloc) -function set. +Duplicate the string `src`. ```c char * @@ -260,7 +256,20 @@ ```c char * -alloc_sdupf(const char *fmt, ...); +alloc_sdupf(const char *fmt, ...) +``` + +### alloc\_free + +Free memory pointed by `ptr`. + +!!! note + Use this function instead of C `free()` if you have used any of the + functions from this module. + +```c +void +alloc_free(void *ptr) ``` ### alloc\_pool\_init @@ -272,11 +281,8 @@ This will effectively create a initial storage according to [ALLOC_POOL_INIT_DEFAULT](#alloc_pool_init_default). -Returns -1 on error depending on the result of the of the current -[alloc](#alloc) function set or 0 otherwise. - ```c -bool +void alloc_pool_init(struct alloc_pool *pool, size_t elemsize, void (*finalizer)(void *)) ``` @@ -287,9 +293,6 @@ 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. -Returns NULL on errors depending on the result of the of the current -[realloc](#realloc) function set. - ```c void * alloc_pool_new(struct alloc_pool *pool) @@ -307,9 +310,26 @@ alloc_pool_get(const struct alloc_pool *pool, size_t index) ``` +### alloc\_pool\_shrink + +Shrink the `pool`'s data to the exact number of elements in the array and return +the memory region which user takes full ownership. Once returned data is no +longer needed, it must be released with [alloc\_free](#alloc_free). + +The pool is emptied and must be reinitialized using +[alloc\_pool\_init](#alloc_pool_init) before reusing it. + +!!! note + It is not necessary to call [alloc\_pool\_finish](#alloc_pool_finish). + +```c +void * +alloc_pool_shrink(struct alloc_pool *pool) +``` + ### alloc\_pool\_finish -inalize the `pool` and all individual element if a finalizer is set. +Finalize the `pool` and all individual element if a finalizer is set. You must call [alloc\_pool\_init](#alloc_pool_init) again before reusing it. @@ -317,3 +337,46 @@ void alloc_pool_finish(struct alloc_pool *pool) ``` + +## Examples + +Use an [alloc_pool](#alloc_pool) to increase an array while reading a file. + +```c +/* A structure defined line by line inside a file in the form "x|y" */ +struct point { + int x; + int y; +}; + +struct alloc_pool pool; +struct point *point, *points; +size_t pointsz; +int x, y; + +alloc_pool_init(&pool, sizeof (*point), NULL); + +/* Assume fp is a FILE pointer allocated by the user. */ +while (fscanf(fp, "%d|%d\n", &x, &y) == 2) { + /* + * Returned pointer can be used to fill the region but must not be + * permanently referenced as it can get invalidated in the next + * iteration. + */ + point = alloc_pool_new(&pool); + point->x = x; + point->y = y; +} + +/* + * Shrink the data into the appropriate array length. The pool can be safely + * discarded. + */ +pointsz = pool.size; +points = alloc_pool_shrink(&pool); + +for (size_t i = 0; i < pointsz; ++i) + point_draw(&points[i]); +``` + +[panic]: panic.md
--- a/src/libmlk-core/core/alloc.c Sat Apr 02 16:58:23 2022 +0200 +++ b/src/libmlk-core/core/alloc.c Sat Apr 02 16:58:33 2022 +0200 @@ -85,12 +85,7 @@ { assert(size != 0); - void *ptr; - - if ((ptr = funcs->alloc(size))) - memset(ptr, 0, size); - - return ptr; + return memset(funcs->alloc(size), 0, size); } void * @@ -99,12 +94,7 @@ assert(len != 0); assert(elemsize != 0); - size_t size = len * elemsize; - - if (size / len != elemsize) - return errorf("%s", strerror(ENOMEM)), NULL; - - return funcs->alloc(size); + return funcs->alloc(len * elemsize); } void * @@ -113,16 +103,7 @@ assert(len != 0); assert(elemsize != 0); - void *mem; - size_t size = len * elemsize; - - if (size / len != elemsize) - return errorf("%s", strerror(ENOMEM)), NULL; - - if ((mem = funcs->alloc(size))) - memset(mem, 0, size); - - return mem; + return alloc_new0(len * elemsize); } void * @@ -134,23 +115,15 @@ void * alloc_rearray(void *ptr, size_t len, size_t elemsize) { - size_t size = len * elemsize; + assert(elemsize != 0); - if (size / len != elemsize) - return errorf("%s", strerror(ENOMEM)), NULL; - - return funcs->realloc(ptr, size); + return funcs->realloc(ptr, len * elemsize); } void * alloc_rearray0(void *ptr, size_t oldlen, size_t newlen, size_t elemsize) { - size_t size = newlen * elemsize; - - if (size / newlen != elemsize) - return errorf("%s", strerror(ENOMEM)), NULL; - if (!(ptr = funcs->realloc(ptr, size))) - return NULL; + ptr = funcs->realloc(ptr, newlen * elemsize); if (newlen > oldlen) memset((unsigned char *)ptr + (oldlen * elemsize), 0, (newlen - oldlen) * elemsize); @@ -164,12 +137,7 @@ assert(ptr); assert(size != 0); - void *mem; - - if ((mem = funcs->alloc(size))) - memcpy(mem, ptr, size); - - return mem; + return memcpy(funcs->alloc(size), ptr, size); } char * @@ -177,54 +145,41 @@ { assert(src); - char *ret; - size_t length = strlen(src) + 1; + size_t len = strlen(src) + 1; - if ((ret = funcs->alloc(length))) - memcpy(ret, src, length + 1); - - return ret; + return memcpy(funcs->alloc(len), src, len); } char * alloc_sdupf(const char *fmt, ...) { struct buf buf = {0}; - char *ret; va_list ap; va_start(ap, fmt); buf_vprintf(&buf, fmt, ap); va_end(ap); - if (!buf.data) - panicf("%s", strerror(ENOMEM)); - - /* - * We need to reallocate a copy because the API expects to use - * alloc_free. - */ - ret = alloc_dup(buf.data, buf.length + 1); - buf_finish(&buf); - - return ret; + return buf.data; } -int +void +alloc_free(void *ptr) +{ + funcs->free(ptr); +} + +void 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 -1; - + pool->data = alloc_array(ALLOC_POOL_INIT_DEFAULT, elemsize); pool->elemsize = elemsize; pool->size = 0; pool->capacity = ALLOC_POOL_INIT_DEFAULT; pool->finalizer = finalizer; - - return 0; } void * @@ -233,13 +188,8 @@ 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; + pool->data = alloc_rearray(pool->data, pool->capacity, pool->elemsize); } return ((unsigned char *)pool->data) + pool->size++ * pool->elemsize; @@ -254,11 +204,29 @@ return ((unsigned char *)pool->data) + index * pool->elemsize; } +void * +alloc_pool_shrink(struct alloc_pool *pool) +{ + assert(pool); + + void *ptr; + + ptr = alloc_rearray(pool->data, pool->size, pool->elemsize); + memset(pool, 0, sizeof (*pool)); + + return ptr; +} + void alloc_pool_finish(struct alloc_pool *pool) { + unsigned char *tab; + + if (!pool) + return; + if (pool->finalizer) { - unsigned char *tab = pool->data; + tab = pool->data; for (size_t i = 0; i < pool->size; ++i) pool->finalizer(tab + i * pool->elemsize);
--- a/src/libmlk-core/core/alloc.h Sat Apr 02 16:58:23 2022 +0200 +++ b/src/libmlk-core/core/alloc.h Sat Apr 02 16:58:33 2022 +0200 @@ -79,8 +79,11 @@ char * alloc_sdupf(const char *, ...); +void +alloc_free(void *); + /* alloc_pool functions. */ -int +void alloc_pool_init(struct alloc_pool *, size_t , void (*)(void *)); void * @@ -89,6 +92,9 @@ void * alloc_pool_get(const struct alloc_pool *, size_t); +void * +alloc_pool_shrink(struct alloc_pool *); + void alloc_pool_finish(struct alloc_pool *);
--- a/src/libmlk-core/core/buf.h Sat Apr 02 16:58:23 2022 +0200 +++ b/src/libmlk-core/core/buf.h Sat Apr 02 16:58:33 2022 +0200 @@ -22,16 +22,18 @@ #include <stdarg.h> #include <stddef.h> +#include "alloc.h" + #if !defined(BUF_MALLOC) -# define BUF_MALLOC malloc +# define BUF_MALLOC alloc_new #endif #if !defined(BUF_REALLOC) -# define BUF_REALLOC realloc +# define BUF_REALLOC alloc_renew #endif #if !defined(BUF_FREE) -# define BUF_FREE free +# define BUF_FREE alloc_free #endif #if defined(__cplusplus)
--- a/src/libmlk-rpg/rpg/map-file.c Sat Apr 02 16:58:23 2022 +0200 +++ b/src/libmlk-rpg/rpg/map-file.c Sat Apr 02 16:58:33 2022 +0200 @@ -278,8 +278,8 @@ memset(map, 0, sizeof (*map)); - if (alloc_pool_init(&file->blocks, sizeof (*map->blocks), NULL) < 0) - goto fail; + alloc_pool_init(&file->blocks, sizeof (*map->blocks), NULL); + if (zfile_open(&zf, path) < 0) goto fail;
--- a/src/libmlk-rpg/rpg/tileset-file.c Sat Apr 02 16:58:23 2022 +0200 +++ b/src/libmlk-rpg/rpg/tileset-file.c Sat Apr 02 16:58:33 2022 +0200 @@ -154,13 +154,10 @@ unsigned short id, w, h; struct tileset_tiledef *td; - if (alloc_pool_init(&ctx->tf->tiledefs, sizeof (*td), NULL) < 0) - return -1; + alloc_pool_init(&ctx->tf->tiledefs, sizeof (*td), NULL); while (fscanf(ctx->fp, "%hu|%hd|%hd|%hu|%hu\n", &id, &x, &y, &w, &h) == 5) { - if (!(td = alloc_pool_new(&ctx->tf->tiledefs))) - return -1; - + td = alloc_pool_new(&ctx->tf->tiledefs); td->id = id; td->x = x; td->y = y; @@ -184,20 +181,18 @@ unsigned short id; unsigned int delay; char filename[FILENAME_MAX + 1]; + struct tileset_animation_block *anim; - if (alloc_pool_init(&ctx->tf->anims[0], sizeof (struct tileset_animation_block), tileset_animation_block_finish) < 0 || - alloc_pool_init(&ctx->tf->anims[1], sizeof (struct tileset_animation), NULL) < 0) - return -1; + alloc_pool_init(&ctx->tf->anims[0], sizeof (struct tileset_animation_block), tileset_animation_block_finish); + alloc_pool_init(&ctx->tf->anims[1], sizeof (struct tileset_animation), NULL); /* * 1. Create the first array of animation, sprite and texture that are * owned by the tileset_file structure. */ while (fscanf(ctx->fp, "%hu|" MAX_F(FILENAME_MAX) "|%u", &id, filename, &delay) == 3) { - struct tileset_animation_block *anim; + anim = alloc_pool_new(&ctx->tf->anims[0]); - if (!(anim = alloc_pool_new(&ctx->tf->anims[0]))) - return -1; if (image_open(&anim->texture, util_pathf("%s/%s", ctx->basedir, filename)) < 0) return -1;
--- a/tests/test-alloc.c Sat Apr 02 16:58:23 2022 +0200 +++ b/tests/test-alloc.c Sat Apr 02 16:58:33 2022 +0200 @@ -25,7 +25,66 @@ int y; }; -RX_TEST_CASE(test, array_simple) +static const struct alloc_funcs standard_funcs = { + .alloc = malloc, + .realloc = realloc, + .free = free +}; + +static struct { + size_t total; + size_t alloc_count; + size_t free_count; +} my_stats; + +static void * +my_alloc(size_t n) +{ + my_stats.alloc_count += 1; + my_stats.total += n; + + return malloc(n); +} + +static void * +my_realloc(void *ptr, size_t n) +{ + (void)ptr; + (void)n; + + return NULL; +} + +static void +my_free(void *ptr) +{ + free(ptr); + my_stats.free_count += 1; +} + +static const struct alloc_funcs my_funcs = { + .alloc = my_alloc, + .realloc = my_realloc, + .free = my_free +}; + +RX_SET_UP(standard_setup) +{ + alloc_set(&standard_funcs); + + return RX_SUCCESS; +} + +RX_SET_UP(my_setup) +{ + alloc_set(&my_funcs); + + return RX_SUCCESS; +} + +RX_FIXTURE(standard_fixture, void *, .set_up = standard_setup); + +RX_TEST_CASE(test, array_simple, .fixture = standard_fixture) { struct point *points; @@ -51,12 +110,14 @@ RX_INT_REQUIRE_EQUAL(points[3].y, 0); } -RX_TEST_CASE(test, pool_simple) +RX_TEST_CASE(test, pool_simple, .fixture = standard_fixture) { struct alloc_pool pool; - struct point *p; + struct point *p, *data; + size_t total = 0; - RX_REQUIRE(alloc_pool_init(&pool, sizeof (*p), NULL) == 0); + alloc_pool_init(&pool, sizeof (*p), NULL); + RX_UINT_REQUIRE_EQUAL(pool.elemsize, sizeof (*p)); RX_UINT_REQUIRE_EQUAL(pool.size, 0); RX_UINT_REQUIRE_EQUAL(pool.capacity, ALLOC_POOL_INIT_DEFAULT); @@ -66,6 +127,7 @@ p = alloc_pool_new(&pool); p->x = (int)i + 1; p->y = (int)i + 1; + total++; } RX_UINT_REQUIRE_EQUAL(pool.size, pool.capacity); @@ -85,15 +147,22 @@ RX_REQUIRE(pool.capacity > pool.size); - alloc_pool_finish(&pool); + /* Shrink it! */ + data = alloc_pool_shrink(&pool); + + /* Verify values are correct again. */ + for (size_t i = 0; i < total; ++i) { + RX_INT_REQUIRE_EQUAL(data[i].x, (int)i + 1); + RX_INT_REQUIRE_EQUAL(data[i].y, (int)i + 1); + } RX_PTR_REQUIRE_EQUAL(pool.data, NULL); - RX_UINT_REQUIRE_EQUAL(pool.elemsize, 0U); - RX_UINT_REQUIRE_EQUAL(pool.size, 0U); - RX_UINT_REQUIRE_EQUAL(pool.capacity, 0U); + RX_UINT_REQUIRE_EQUAL(pool.size, 0); + RX_UINT_REQUIRE_EQUAL(pool.capacity, 0); + RX_UINT_REQUIRE_EQUAL(pool.elemsize, 0); } -RX_TEST_CASE(test, sdupf) +RX_TEST_CASE(test, sdupf, .fixture = standard_fixture) { char *str = alloc_sdupf("Hello %s", "David"); @@ -101,6 +170,19 @@ free(str); } +RX_FIXTURE(my_fixture, void *, .set_up = my_setup); + +RX_TEST_CASE(test, custom, .fixture = my_fixture) +{ + alloc_free(alloc_new(10)); + alloc_free(alloc_new0(20)); + alloc_free(alloc_sdup("malikania")); + + RX_INT_REQUIRE_EQUAL(my_stats.total, 40U); + RX_INT_REQUIRE_EQUAL(my_stats.alloc_count, 3U); + RX_INT_REQUIRE_EQUAL(my_stats.free_count, 3U); +} + int main(int argc, char **argv) {