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 - <so...@gentoo.org>
* Copyright 2004-2014 Mike Frysinger - <vap...@gentoo.org>
+ * Copyright 2018- Fabian Groffen - <grob...@gentoo.org>
*/
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.
*/
