From d4a6efafc666098220f9930d0fe63eeac485d276 Mon Sep 17 00:00:00 2001 From: Not Zed Date: Fri, 11 Jun 2021 17:09:05 +0930 Subject: [PATCH] Add trvial untyped growable array. --- .gitignore | 3 +- Makefile | 3 ++ ez-array.c | 79 ++++++++++++++++++++++++++++++++++++++++++++++++ ez-array.h | 84 ++++++++++++++++++++++++++++++++++++++++++++++++++++ test-array.c | 57 +++++++++++++++++++++++++++++++++++ 5 files changed, 225 insertions(+), 1 deletion(-) create mode 100644 ez-array.c create mode 100644 ez-array.h create mode 100644 test-array.c diff --git a/.gitignore b/.gitignore index d8f1701..f6959b8 100644 --- a/.gitignore +++ b/.gitignore @@ -1,4 +1,5 @@ .deps libeze.a *.o - +test-* +ez-blob-compiler diff --git a/Makefile b/Makefile index b462a2f..66a86a8 100644 --- a/Makefile +++ b/Makefile @@ -7,6 +7,7 @@ ARFLAGS=rvsUc VERSION=2.1.99 SRCS= \ + ez-array.c \ ez-bitset.c \ ez-blob.c \ ez-blob.c \ @@ -23,6 +24,7 @@ SRCS= \ ez-tree.c HEADERS = \ + ez-array.h \ ez-bitset.h \ ez-blob.h \ ez-blob-basic.h \ @@ -58,6 +60,7 @@ check: tests test-%: test-%.o $(CC) $(CFLAGS) -o $@ $< libeze.a $(test_LDLIBS) +test-array: libeze.a(ez-array.o) test-bitset: libeze.a(ez-bitset.o) test-blob: libeze.a(ez-blob.o) libeze.a(ez-blob-print.o) libeze.a(ez-blob-io.o) \ libeze.a(ez-blob-xdrn.o) libeze.a(ez-blob-tagz.o) libeze.a(ez-blob-dump.o) diff --git a/ez-array.c b/ez-array.c new file mode 100644 index 0000000..c29fdb8 --- /dev/null +++ b/ez-array.c @@ -0,0 +1,79 @@ +/* ez-array.c: Basic array + + Copyright (C) 2021 Michael Zucchi + + This program is free software: you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public License + as published by the Free Software Foundation, either version 3 of + the License, or (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this program. If not, see + . +*/ + +#include +#include +#include + +#include "ez-array.h" + +void ez_array_init(ez_array *ea) { + memset(ea, 0, sizeof(*ea)); +} + +void ez_array_clear(ez_array *ea) { + free(ea->ea_data); + ez_array_init(ea); +} + +void *ez_array_insert_space(ez_array *ea, size_t offset, size_t space) { + size_t size = ea->ea_size + space; + size_t alloc = ea->ea_alloc; + + if (alloc < size) { + void *tmp; + + alloc = alloc ? alloc : size; + while (alloc < size) + alloc = alloc * 2; + if (!(tmp = realloc(ea->ea_data, alloc))) + return tmp; + ea->ea_data = tmp; + ea->ea_alloc = alloc; + } + + memmove(ea->ea_data + offset + space, ea->ea_data + offset, ea->ea_size - offset); + ea->ea_size = size; + return ea->ea_data + offset; +} + +void *ez_array_insert(ez_array *ea, size_t offset, void *val, size_t len) { + void *tmp = ez_array_insert_space(ea, offset, len); + + if (tmp) + memcpy(tmp, val, len); + return tmp; +} + +void ez_array_remove(ez_array *ea, size_t offset, size_t len) { + memmove(ea->ea_data + offset, ea->ea_data + offset + len, ea->ea_size - offset - len); + ea->ea_size -= len; +} + +void *ez_array_add_space(ez_array *ea, size_t space) { + return ez_array_insert_space(ea, ea->ea_size, space); +} + +void *ez_array_add(ez_array *ea, void *val, size_t len) { + void *tmp = ez_array_add_space(ea, len); + + if (tmp) + memcpy(tmp, val, len); + return tmp; +} diff --git a/ez-array.h b/ez-array.h new file mode 100644 index 0000000..76efe4a --- /dev/null +++ b/ez-array.h @@ -0,0 +1,84 @@ +/* ez-array.h: Basic growable array. + + Copyright (C) 2021 Michael Zucchi + + This program is free software: you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public License + as published by the Free Software Foundation, either version 3 of + the License, or (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this program. If not, see + . +*/ + +#ifndef EZ_ARRAY_H +#define EZ_ARRAY_H + +typedef struct ez_array ez_array; + +// layout compatible with ez_blob +struct ez_array { + size_t ea_size; // valid size in bytes + union { + void *ea_data; + uint8_t ea_data8; + uint16_t ea_data16; + uint32_t ea_data32; + uint64_t ea_data64; + float *ea_float; + double *ea_double; + }; + size_t ea_alloc; // allocation size in bytes +}; + +/** + * Initialise an array struct. + * Alternatively just set it to all zeros. + */ +void ez_array_init(ez_array *ea); + +/** + * Clear array contents, freeing backing array if required. + */ +void ez_array_clear(ez_array *ea); + +/** + * Create space in array. + * + * @return pointer to space, or NULL on allocation failure. + */ +void *ez_array_insert_space(ez_array *ea, size_t offset, size_t space); + +/** + * Create space and copy data. + * + * @return pointer to space, or NULL on allocation failure. + */ +void *ez_array_insert(ez_array *ea, size_t offset, void *val, size_t len); + +/** + * Collapse space in array. + */ +void ez_array_remove(ez_array *ea, size_t offset, size_t len); + +/** + * Helper to create space at end of array. + * + * @return pointer to space, or NULL on allocation failure. + */ +void *ez_array_add_space(ez_array *ea, size_t space); + +/** + * Helper to add data at end of array. + * + * @return pointer to space, or NULL on allocation failure. + */ +void *ez_array_add(ez_array *ea, void *val, size_t len); + +#endif diff --git a/test-array.c b/test-array.c new file mode 100644 index 0000000..055e7e9 --- /dev/null +++ b/test-array.c @@ -0,0 +1,57 @@ + +#include +#include +#include +#include +#include + +#include "ez-array.h" + +static const uint32_t test0[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; +static const uint32_t test1[] = { 0, 1, 2, 3, 4, 6, 7, 8, 9 }; +static const uint32_t test2[] = { 0, 1, 11, 11, 11, 2, 3, 4, 6, 7, 8, 9 }; +static const uint32_t test3[] = { 0, 1, 11, 11, 11, 2, 3, 4, 6, 7, 8, 9, 10, 11 }; +static const uint32_t test4[] = { 11, 10, 0, 1, 11, 11, 11, 2, 3, 4, 6, 7, 8, 9, 10, 11 }; + +int main(int argc, char **argv) { + ez_array array = { 0 }; + + for (int i=0;i<10;i++) { + ez_array_add(&array, &i, sizeof(i)); + } + + assert(array.ea_size == 10 * 4); + assert(memcmp(test0, array.ea_data, sizeof(test0)) == 0); + + ez_array_remove(&array, 5*4, 1*4); + + assert(array.ea_size == 9 * 4); + assert(memcmp(test1, array.ea_data, sizeof(test1)) == 0); + + uint32_t *tmp = ez_array_insert_space(&array, 2*4, 3*4); + + for (int i=0;i<3;i++) + tmp[i] = 11; + + assert(array.ea_size == 12 * 4); + assert(memcmp(test2, array.ea_data, sizeof(test2)) == 0); + + uint32_t v10 = 10; + uint32_t v11 = 11; + + ez_array_add(&array, &v10, sizeof(v10)); + ez_array_add(&array, &v11, sizeof(v11)); + + assert(array.ea_size == 14 * 4); + assert(memcmp(test3, array.ea_data, sizeof(test3)) == 0); + + ez_array_insert(&array, 0, &v10, sizeof(v10)); + ez_array_insert(&array, 0, &v11, sizeof(v11)); + + assert(array.ea_size == 16 * 4); + assert(memcmp(test4, array.ea_data, sizeof(test4)) == 0); + + ez_array_clear(&array); + + return 0; +} -- 2.39.2