commit: ace156ca85c3d5c804ec06e7cb4172f5b6d279e1 Author: Fabian Groffen <grobian <AT> gentoo <DOT> org> AuthorDate: Tue Feb 26 08:32:50 2019 +0000 Commit: Fabian Groffen <grobian <AT> gentoo <DOT> org> CommitDate: Wed Feb 27 20:49:47 2019 +0000 URL: https://gitweb.gentoo.org/proj/portage-utils.git/commit/?id=ace156ca
xarray: improve malloc efficiency, allow removing elements Pre-allocate members such that we don't have to re-alloc for every insertion. Allow removing elements from the array, such that they can be used as containers of running lists. Signed-off-by: Fabian Groffen <grobian <AT> gentoo.org> libq/xarray.c | 22 ++++++++++++++++++++-- 1 file changed, 20 insertions(+), 2 deletions(-) diff --git a/libq/xarray.c b/libq/xarray.c index 64334bb..3ed9872 100644 --- a/libq/xarray.c +++ b/libq/xarray.c @@ -1,14 +1,16 @@ /* - * Copyright 2003-2018 Gentoo Foundation + * Copyright 2003-2019 Gentoo Foundation * Distributed under the terms of the GNU General Public License v2 * * Copyright 2003-2007 Ned Ludd - <[email protected]> * Copyright 2004-2014 Mike Frysinger - <[email protected]> + * Copyright 2018- Fabian Groffen - <[email protected]> */ typedef struct { void **eles; size_t num; + size_t len; } array_t; #define xrealloc_array(ptr, size, ele_size) xrealloc(ptr, (size) * (ele_size)) @@ -23,6 +25,7 @@ typedef struct { #define array_init_decl { .eles = NULL, .num = 0, } #define array_cnt(arr) (arr)->num #define DECLARE_ARRAY(arr) array_t _##arr = array_init_decl, *arr = &_##arr +#define ARRAY_INC_SIZE 32 /* Push a pointer to memory we already hold and don't want to release. Do not * mix xarraypush_ptr usage with the other push funcs which duplicate memory. @@ -31,7 +34,10 @@ typedef struct { static void *xarraypush_ptr(array_t *arr, void *ele) { size_t n = arr->num++; - arr->eles = xrealloc_array(arr->eles, arr->num, sizeof(ele)); + if (arr->num > arr->len) { + arr->len += ARRAY_INC_SIZE; + arr->eles = xrealloc_array(arr->eles, arr->len, sizeof(ele)); + } arr->eles[n] = ele; return ele; } @@ -42,6 +48,18 @@ static void *xarraypush(array_t *arr, const void *ele, size_t ele_len) #define xarraypush_str(arr, ele) xarraypush(arr, ele, strlen(ele) + 1 /*NUL*/) #define xarraypush_struct(arr, ele) xarraypush(arr, ele, sizeof(*(ele))) +static void xarraydelete_ptr(array_t *arr, size_t elem) +{ + arr->num--; + memmove(&arr->eles[elem], &arr->eles[elem + 1], arr->num - elem); +} + +static void xarraydelete(array_t *arr, size_t elem) +{ + free(arr->eles[elem]); + xarraydelete_ptr(arr, elem); +} + /* Useful for people who call xarraypush_ptr as it does not free any of the * pointers in the eles list. */
