diff options
author | Kenny Levinsen <kl@kl.wtf> | 2022-08-18 11:51:21 +0200 |
---|---|---|
committer | Kenny Levinsen <kl@kl.wtf> | 2022-08-19 19:38:33 +0200 |
commit | 724aa38fc2de14909663cb984a9de64a561abf5f (patch) | |
tree | fef5edaf1f4adb49a99cb53442d3164f8f03b61c | |
parent | 9ab819684d41b5052260e11a337ce0cdee6ce3bd (diff) |
util/array: Add array_realloc for wl_array
array_realloc will grow the array for the target size like wl_insert_add, but
will also shrink the array if the target size is sufficiently smaller than the
current allocation.
-rw-r--r-- | include/util/array.h | 5 | ||||
-rw-r--r-- | util/array.c | 29 |
2 files changed, 34 insertions, 0 deletions
diff --git a/include/util/array.h b/include/util/array.h index 9612e7db..2b7278cc 100644 --- a/include/util/array.h +++ b/include/util/array.h @@ -27,4 +27,9 @@ bool set_remove(uint32_t values[], size_t *len, size_t cap, uint32_t target); */ void array_remove_at(struct wl_array *arr, size_t offset, size_t size); +/** + * Grow or shrink the array to fit the specifized size. + */ +bool array_realloc(struct wl_array *arr, size_t size); + #endif diff --git a/util/array.c b/util/array.c index 50025b77..9da26127 100644 --- a/util/array.c +++ b/util/array.c @@ -55,3 +55,32 @@ void array_remove_at(struct wl_array *arr, size_t offset, size_t size) { memmove(&data[offset], &data[offset + size], arr->size - offset - size); arr->size -= size; } + +bool array_realloc(struct wl_array *arr, size_t size) { + // If the size is less than 1/4th of the allocation size, we shrink it. + // 1/4th is picked to provide hysteresis, without which an array with size + // arr->alloc would constantly reallocate if an element is added and then + // removed continously. + size_t alloc; + if (arr->alloc > 0 && size > arr->alloc / 4) { + alloc = arr->alloc; + } else { + alloc = 16; + } + + while (alloc < size) { + alloc *= 2; + } + + if (alloc == arr->alloc) { + return true; + } + + void *data = realloc(arr->data, alloc); + if (data == NULL) { + return false; + } + arr->data = data; + arr->alloc = alloc; + return true; +} |