From 052dcc744cb04d73eedd22c823646015b34d369a Mon Sep 17 00:00:00 2001 From: =?utf8?q?Marek=20Vavru=C5=A1a?= Date: Fri, 27 Mar 2015 13:22:54 +0100 Subject: [PATCH] lib: added generics package --- .gitignore | 5 ++ doc/lib.rst | 4 ++ lib/generic/README.rst | 18 +++++++ lib/generic/array.h | 106 +++++++++++++++++++++++++++++++++++++++++ tests/test_generics.c | 60 +++++++++++++++++++++++ 5 files changed, 193 insertions(+) create mode 100644 lib/generic/README.rst create mode 100644 lib/generic/array.h create mode 100644 tests/test_generics.c diff --git a/.gitignore b/.gitignore index 07fe1c3b7..d019dec3d 100644 --- a/.gitignore +++ b/.gitignore @@ -11,10 +11,15 @@ *.swp *.d *.db +*.out +*.6 +*.log +*.inc .dirstamp .libs .deps _obj +tmp* /autom4te.cache/* /config.log /config.h diff --git a/doc/lib.rst b/doc/lib.rst index 80d38e39c..9091a70e2 100644 --- a/doc/lib.rst +++ b/doc/lib.rst @@ -59,3 +59,7 @@ API reference .. doxygengroup:: utils :project: libkresolve + +.. _lib_generics: + +.. include:: ../lib/generic/README.rst diff --git a/lib/generic/README.rst b/lib/generic/README.rst new file mode 100644 index 000000000..50e1dec2d --- /dev/null +++ b/lib/generic/README.rst @@ -0,0 +1,18 @@ +Generics library +---------------- + +This small collection of "generics" was born out of frustration that I couldn't find no +such thing for C. It's either bloated, has poor interface, null-checking is absent or +doesn't allow custom allocation scheme. BSD-licensed (or compatible) code is allowed here, +as long as it comes with a test case in `tests/test_generics.c`. + +Data structures +~~~~~~~~~~~~~~~ + +- Dynamic arrays + +API reference and examples +~~~~~~~~~~~~~~~~~~~~~~~~~~ + +.. doxygengroup:: generics + :project: libkresolve diff --git a/lib/generic/array.h b/lib/generic/array.h new file mode 100644 index 000000000..d17d017b1 --- /dev/null +++ b/lib/generic/array.h @@ -0,0 +1,106 @@ +/* Copyright (C) 2015 CZ.NIC, z.s.p.o. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU 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 General Public License + along with this program. If not, see . + */ + +/** + * Generics - simple dynamic array. + * + * \note The C has no generics, so it is implemented mostly using macros. + * Be aware of that, as direct usage of the macros in the evaluating macros + * may lead to different expectations, i.e. + * + * MIN(array_push(arr, val)) + * + * May evaluate the code twice, leading to unexpected behaviour. + * This is a price to pay for absence of proper generics. + * + * Example usage: + * + * array_t(const char*) arr; + * array_init(arr); + * + * // Reserve memory in advance + * if (array_reserve(arr, 2) < 0) { + * return ENOMEM; + * } + * + * // Already reserved, cannot fail + * array_push(arr, "princess"); + * array_push(arr, "leia"); + * + * // Not reserved, may fail + * if (array_push(arr, "han") < 0) { + * return ENOMEM; + * } + * + * // It does not hide what it really is + * for (size_t i = 0; i < arr.len; ++i) { + * printf("%s\n", arr.at[i]); + * } + * + * // Random delete + * array_del(arr, 0); + * + * \addtogroup generics + * @{ + */ + +#pragma once + +/** @todo Implement mreserve over custom memory context. */ +#include + +/** Declare an array structure. */ +#define array_t(type) struct {type * at; size_t len; size_t cap; } + +/** Zero-initialize the array. */ +#define array_init(array) ((array).at = NULL, (array).len = (array).cap = 0) + +/** Free and zero-initialize the array. */ +#define array_clear(array) \ + free((array).at), array_init(array) + +/** + * Reserve capacity up to 'n' bytes. + * @return >=0 if success + */ +#define array_reserve(array, n) \ + mreserve((char **) &(array).at, sizeof((array).at[0]), n, 0, &(array).cap) + +/** + * Push value at the end of the array, resize it if necessary. + * @note May fail if the capacity is not reserved. + * @return element index on success, <0 on failure + */ +#define array_push(array, val) \ + (array).len < (array).cap ? ((array).at[(array).len] = val, (array).len++) \ + : (array_reserve(array, ((array).cap + 1) * 2) < 0 ? -1 \ + : ((array).at[(array).len] = val, (array).len++)) + +/** + * Pop value from the end of the array. + * @return 0 on success, <0 on failure + */ +#define array_pop(array) \ + array_del((array), (array).len - 1) + +/** + * Remove value at given index. + * @return 0 on success, <0 on failure + */ +#define array_del(array, i) \ + (i) < (array).len ? ((array).at[i] = (array).at[--(array).len], 0) : -1 + +/** @} */ diff --git a/tests/test_generics.c b/tests/test_generics.c new file mode 100644 index 000000000..8108cab22 --- /dev/null +++ b/tests/test_generics.c @@ -0,0 +1,60 @@ +/* Copyright (C) 2015 CZ.NIC, z.s.p.o. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU 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 General Public License + along with this program. If not, see . + */ + +#include "tests/test.h" +#include "lib/generic/array.h" + +mm_ctx_t global_mm; + +static void test_array(void **state) +{ + int ret = 0; + array_t(int) arr; + array_init(arr); + + /* Basic access */ + assert_int_equal(arr.len, 0); + assert_int_equal(array_push(arr, 5), 0); + assert_int_equal(arr.at[0], 5); + array_clear(arr); + + /* Reserve capacity and fill. */ + assert_true(array_reserve(arr, 5) >= 0); + for (unsigned i = 0; i < 100; ++i) { + ret = array_push(arr, i); + assert_true(ret >= 0); + } + + /* Delete elements. */ + array_del(arr, 0); + for (size_t i = arr.len; --i;) { + ret = array_pop(arr); + assert_true(ret == 0); + } + + array_clear(arr); +} + +int main(void) +{ + test_mm_ctx_init(&global_mm); + + const UnitTest tests[] = { + unit_test(test_array), + }; + + return run_tests(tests); +} -- 2.47.2