commit 5127c17eea94d34ca2c485f88adfe4c4c632c989
parent 300f505af95218f5144b876b654b8c2951aceb96
Author: vaplv <vaplv@free.fr>
Date: Wed, 8 Apr 2015 17:51:03 +0200
Add and test the stretchy array data structure
Diffstat:
3 files changed, 208 insertions(+), 0 deletions(-)
diff --git a/cmake/CMakeLists.txt b/cmake/CMakeLists.txt
@@ -141,6 +141,7 @@ if(NOT NO_TEST)
new_test(test_ref)
new_test(test_signal rsys)
new_test(test_str rsys)
+ new_test(test_stretchy_array rsys)
new_test(test_time rsys)
add_library(test_lib SHARED ${RSYS_SOURCE_DIR}/test_library.c)
diff --git a/src/stretchy_array.h b/src/stretchy_array.h
@@ -0,0 +1,101 @@
+/* Copyright (C) 2013-2015 Vincent Forest (vaplv@free.fr)
+ *
+ * The RSys library 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.
+ *
+ * The RSys library 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 Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with the RSys library. If not, see <http://www.gnu.org/licenses/>. */
+
+#ifndef STRETCHY_ARRAY_H
+#define STRETCHY_ARRAY_H
+
+#include "math.h"
+#include "mem_allocator.h"
+
+/*
+ * Port of the suckless Sean T. Barret's stretchy buffer. Stretchy arrays can
+ * be use on data types that does not rely on an init or release process and
+ * can be bitwise copied. Refer to dynamic_array for more advanced data types
+ */
+
+/*******************************************************************************
+ * Internal macros
+ ******************************************************************************/
+#define sa_raw__(A) ((size_t*)(A)-2)
+#define sa_capacity__(A) sa_raw__(A)[0]
+#define sa_size__(A) sa_raw__(A)[1]
+#define sa_need_grow__(A, N) ((A)==NULL || sa_size__(A) + (N) >= sa_capacity__(A))
+#define sa_may_be_grow__(A, N) (sa_need_grow__(A, (N)) ? sa_grow__(A, N) : 0)
+#define sa_grow__(A, N) ((A) = sa_grow_func__((A), (N), sizeof(*(A))))
+
+/*******************************************************************************
+ * Stretchy buffer API
+ ******************************************************************************/
+/* Free `Array' memory */
+#define sa_release(Array) { \
+ if(Array) \
+ mem_free(sa_raw__(Array)); \
+ } (void)0
+
+/* Push back `Val' in `Array' */
+#define sa_push(Array, Val) { \
+ sa_may_be_grow__(Array, 1); \
+ (Array)[sa_size__(Array)++] = (Val); \
+ } (void)0
+
+/* Clean up `Array' but does not release its memory */
+#define sa_clear(Array) { \
+ if(Array) \
+ sa_size__(Array) = 0; \
+ } (void)0
+
+/* Add `N' uninitialized items to `Array'. Return a pointer to the 1st added */
+#define sa_add(Array, N) \
+ (sa_may_be_grow__(Array, N), \
+ sa_size__(Array) += (N), \
+ &(Array)[sa_size__(Array) - (N)])
+
+/* Return a lvalue of the last item in `Array' */
+#define sa_last(Array) ((Array)[sa_size__(Array)-1])
+
+/* Return the number of items in `Array' */
+#define sa_size(Array) ((Array) ? sa_size__(Array) : 0)
+
+/*******************************************************************************
+ * Helper internal function
+ ******************************************************************************/
+static INLINE void*
+sa_grow_func__(void* array, const size_t increment, const size_t itemsize)
+{
+ size_t dbl_capacity = array ? 2 * sa_capacity__(array) : 0;
+ size_t min_needed_capacity = MMIN(sa_size(array) + increment, 32);
+ size_t new_capacity = MMAX(dbl_capacity, min_needed_capacity);
+ size_t sizeof_array = itemsize * new_capacity + sizeof(size_t)*2;
+ size_t* new_array;
+ ASSERT(itemsize);
+
+ if(array) {
+ new_array = (size_t*)mem_realloc(sa_raw__(array), sizeof_array);
+ } else {
+ new_array = (size_t*)mem_alloc_aligned(sizeof_array, 16);
+ }
+
+ if(!new_array) {
+ FATAL("Unsufficient memory\n");
+ return NULL;
+ }
+
+ if(!array) new_array[1] = 0;
+ new_array[0] = new_capacity;
+ return new_array+2;
+}
+
+#endif /* STRETCHY_ARRAY_H */
+
diff --git a/src/test_stretchy_array.c b/src/test_stretchy_array.c
@@ -0,0 +1,106 @@
+/* copyright (c) 2013-2015 vincent forest (vaplv@free.fr)
+ *
+ * the rsys library 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.
+ *
+ * the rsys library 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 lesser general public license for more details.
+ *
+ * you should have received a copy of the gnu lesser general public license
+ * along with the rsys library. if not, see <http://www.gnu.org/licenses/>. */
+
+#include "stretchy_array.h"
+#include "math.h"
+
+static void
+test_double(void)
+{
+ double* array = NULL;
+
+ CHECK(sa_size(array), 0);
+ sa_clear(array);
+
+ CHECK(sa_add(array, 4), array);
+ CHECK(sa_size(array), 4);
+
+ array[0] = PI;
+ array[1] = PI;
+ array[2] = PI;
+ array[3] = PI;
+ CHECK(sa_last(array), PI);
+
+ sa_push(array, 1.2345);
+ CHECK(sa_last(array), 1.2345);
+ sa_push(array, 6.7890);
+ CHECK(sa_last(array), 6.7890);
+
+ CHECK(array[0], PI);
+ CHECK(array[1], PI);
+ CHECK(array[2], PI);
+ CHECK(array[3], PI);
+ CHECK(array[4], 1.2345);
+ CHECK(array[5], 6.7890);
+ CHECK(sa_size(array), 6);
+
+ sa_clear(array);
+ CHECK(sa_size(array), 0);
+
+ sa_release(array);
+}
+
+static void
+test_int(void)
+{
+ int* array = NULL;
+ int* p;
+ size_t i;
+
+ CHECK(sa_size(array), 0);
+
+ FOR_EACH(i, 0, 1024)
+ sa_push(array, (int)i);
+
+ CHECK(sa_size(array), 1024);
+
+ FOR_EACH(i, 0, 1024)
+ CHECK(array[i], (int)i);
+
+ CHECK(sa_last(array), 1023);
+
+ p = sa_add(array, 32);
+ CHECK(sa_size(array), 1056);
+
+ FOR_EACH(i, 0, 32)
+ p[i] = (int)i;
+
+ CHECK(sa_last(array), 31);
+ FOR_EACH(i, 0, 32)
+ array[1024 + i] = (int)i;
+
+ sa_clear(array);
+ CHECK(sa_size(array), 0);
+ p = sa_add(array, 16);
+ CHECK(p, array);
+ CHECK(sa_size(array), 16);
+ FOR_EACH(i, 0, 16)
+ p[i] = -(int)i;
+
+ FOR_EACH(i, 0, 16)
+ CHECK(array[i], -(int)i);
+
+ sa_release(array);
+}
+
+int
+main(int argc, char** argv)
+{
+ (void)argc, (void)argv;
+ test_int();
+ test_double();
+ CHECK(mem_allocated_size(), 0);
+ return 0;
+}
