diff options
| -rw-r--r-- | include/array.h | 79 | ||||
| -rw-r--r-- | lib/util/Makemodule.am | 1 | ||||
| -rw-r--r-- | lib/util/array.c | 115 |
3 files changed, 195 insertions, 0 deletions
diff --git a/include/array.h b/include/array.h new file mode 100644 index 0000000..cbac7c2 --- /dev/null +++ b/include/array.h @@ -0,0 +1,79 @@ +/* SPDX-License-Identifier: LGPL-3.0-or-later */ +/* + * array.h + * + * Copyright (C) 2021 David Oberhollenzer <goliath@infraroot.at> + */ +#ifndef ARRAY_H +#define ARRAY_H + +#include "sqfs/predef.h" +#include "sqfs/error.h" + +#include <stddef.h> +#include <string.h> +#include <stdlib.h> + +typedef struct { + /* sizeof a single element */ + size_t size; + + /* total number of elements available */ + size_t count; + + /* actually used number of elements available */ + size_t used; + + void *data; +} array_t; + +static SQFS_INLINE void *array_get(array_t *array, size_t index) +{ + if (index >= array->used) + return NULL; + + return (char *)array->data + array->size * index; +} + +static SQFS_INLINE int array_set(array_t *array, size_t index, const void *data) +{ + if (index >= array->used) + return SQFS_ERROR_OUT_OF_BOUNDS; + + memcpy((char *)array->data + array->size * index, data, array->size); + return 0; +} + +static SQFS_INLINE void array_sort_range(array_t *array, size_t start, + size_t count, + int (*compare_fun)(const void *a, + const void *b)) +{ + if (start < array->used) { + if (count > (array->used - start)) + count = array->used - start; + + qsort((char *)array->data + array->size * start, count, + array->size, compare_fun); + } +} + +#ifdef __cplusplus +extern "C" { +#endif + +SQFS_INTERNAL int array_init(array_t *array, size_t size, size_t capacity); + +SQFS_INTERNAL int array_init_copy(array_t *array, const array_t *src); + +SQFS_INTERNAL void array_cleanup(array_t *array); + +SQFS_INTERNAL int array_append(array_t *array, const void *data); + +SQFS_INTERNAL int array_set_capacity(array_t *array, size_t capacity); + +#ifdef __cplusplus +} +#endif + +#endif /* ARRAY_H */ diff --git a/lib/util/Makemodule.am b/lib/util/Makemodule.am index 68f5e8d..0784898 100644 --- a/lib/util/Makemodule.am +++ b/lib/util/Makemodule.am @@ -1,6 +1,7 @@ libutil_a_SOURCES = include/util.h include/str_table.h include/hash_table.h libutil_a_SOURCES += lib/util/str_table.c lib/util/alloc.c libutil_a_SOURCES += lib/util/rbtree.c include/rbtree.h +libutil_a_SOURCES += lib/util/array.c include/array.h libutil_a_SOURCES += lib/util/xxhash.c lib/util/hash_table.c libutil_a_SOURCES += lib/util/fast_urem_by_const.h libutil_a_CFLAGS = $(AM_CFLAGS) diff --git a/lib/util/array.c b/lib/util/array.c new file mode 100644 index 0000000..3697a07 --- /dev/null +++ b/lib/util/array.c @@ -0,0 +1,115 @@ +/* SPDX-License-Identifier: LGPL-3.0-or-later */ +/* + * array.c + * + * Copyright (C) 2021 David Oberhollenzer <goliath@infraroot.at> + */ +#include "config.h" +#include "compat.h" +#include "array.h" + +#include "sqfs/error.h" + +#include <stdlib.h> + +int array_init(array_t *array, size_t size, size_t capacity) +{ + size_t total; + + memset(array, 0, sizeof(*array)); + + if (capacity > 0) { + if (SZ_MUL_OV(size, capacity, &total)) + return SQFS_ERROR_OVERFLOW; + + array->data = malloc(total); + if (array->data == NULL) + return SQFS_ERROR_ALLOC; + } + + array->size = size; + array->count = capacity; + return 0; +} + +int array_init_copy(array_t *array, const array_t *src) +{ + int ret; + + ret = array_init(array, src->size, src->used); + if (ret != 0) + return ret; + + memcpy(array->data, src->data, src->used * src->size); + array->used = src->used; + return 0; +} + +void array_cleanup(array_t *array) +{ + free(array->data); + memset(array, 0, sizeof(*array)); +} + +int array_append(array_t *array, const void *data) +{ + size_t new_sz, new_count; + void *new; + + if (array->used == array->count) { + if (array->count == 0) { + new_count = 128; + } else { + if (SZ_MUL_OV(array->count, 2, &new_count)) + return SQFS_ERROR_ALLOC; + } + + if (SZ_MUL_OV(new_count, array->size, &new_sz)) + return SQFS_ERROR_ALLOC; + + new = realloc(array->data, new_sz); + if (new == NULL) + return SQFS_ERROR_ALLOC; + + array->data = new; + array->count = new_count; + } + + memcpy((char *)array->data + array->size * array->used, + data, array->size); + + array->used += 1; + return 0; +} + +int array_set_capacity(array_t *array, size_t capacity) +{ + size_t new_sz, new_count; + void *new; + + if (capacity <= array->count) + return 0; + + if (array->count == 0) { + new_count = 128; + } else { + if (SZ_MUL_OV(array->count, 2, &new_count)) + return SQFS_ERROR_ALLOC; + } + + while (new_count < capacity) { + if (SZ_MUL_OV(new_count, 2, &new_count)) + return SQFS_ERROR_ALLOC; + } + + if (SZ_MUL_OV(new_count, array->size, &new_sz)) + return SQFS_ERROR_ALLOC; + + new = realloc(array->data, new_sz); + if (new == NULL) + return SQFS_ERROR_ALLOC; + + array->data = new; + array->count = new_count; + return 0; +} |