commit 56f8c7a245561abeaee4f5914c733a052aa51e21
parent 2d557370b263137daf4d599a97fb23fb800dd553
Author: vaplv <vaplv@free.fr>
Date: Sat, 29 Mar 2014 22:53:31 +0100
Add and test the binary heap data structure
Diffstat:
4 files changed, 282 insertions(+), 0 deletions(-)
diff --git a/cmake/CMakeLists.txt b/cmake/CMakeLists.txt
@@ -109,6 +109,7 @@ new_test(test_free_list rsys)
new_test(test_library rsys)
new_test(test_list rsys)
new_test(test_mem_allocator rsys)
+new_test(test_binary_heap rsys)
new_test(test_ref)
new_test(test_signal rsys)
new_test(test_str rsys)
diff --git a/src/binary_heap.h b/src/binary_heap.h
@@ -0,0 +1,194 @@
+#if !defined(BHEAP_DATA) && !defined(BHEAP_NAME)
+#ifndef BINARY_HEAP_H
+#define BINARY_HEAP_H
+
+#include "rsys.h"
+#include "dynamic_array.h"
+
+#endif /* BINARY_HEAP_H */
+#else
+/*
+ * Generate the binary heap data type and functions with respect to the
+ * following macros:
+ * - BHEAP_NAME: prefix of the binary heap type and its functions;
+ * - BHEAP_DATA: type of the data registered into the binary heap;
+ * - BHEAP_FUNCTOR_COMPARE: comparison functor on binary heap data. Its
+ * profile is int (*)(const BHEAP_DATA* , const BHEAP_DATA* ). It returns
+ * an integer less than, equal to, or greater than zero if the first
+ * argument is considered to be sorted respectively before, at the same
+ * position, or after the second. If not defined the `<' operator is used
+ * to sort the BHEAP_DATA;
+ * - BHEAP_FUNCTOR_INIT: init functor on BHEAP_DATA. If not defined, no
+ * specific treatment is performed on the created data;
+ * - BHEAP_FUNCTOR_COPY: copy functor on DHEAP_DATA. If not defined a
+ * bitwise copy is used instead;
+ * - BHEAP_FUNCTOR_RELEASE: release functor on BHEAP_DATA. If not defined
+ * nothing is done on the release of an element;
+ * - BHEAP_FUNCTOR_COPY_AND_RELEASE: copy and release of a DHEAP_DATA. If
+ * not defined the copy and the release functors is used.
+ *
+ * The name of the generated type is: struct bheap_<BHEAP_NAME>
+ * while the generated functions are: bheap_<BHEAP_NAME>_<FUNCTION_NAME>
+ */
+#ifndef BHEAP_NAME
+ #error "Missing the BHEAP_NAME macro defining the structure name"
+#endif
+#ifndef BHEAP_DATA
+ #error "Missing the BHEAP_DATA macro defining the heap data type"
+#endif
+
+#define DARRAY_NAME CONCAT(BHEAP_NAME, __)
+#define DARRAY_DATA BHEAP_DATA
+#ifdef BHEAP_FUNCTOR_INIT
+ #define DARRAY_FUNCTOR_INIT BHEAP_FUNCTOR_INIT
+#endif
+#ifdef BHEAP_FUNCTOR_COPY
+ #define DARRAY_FUNCTOR_COPY BHEAP_FUNCTOR_COPY
+#endif
+#ifdef BHEAP_FUNCTOR_RELEASE
+ #define DARRAY_FUNCTOR_RELEASE BHEAP_FUNCTOR_RELEASE
+#endif
+#ifdef BHEAP_FUNCTOR_COPY_AND_RELEASE
+ #define DARRAY_FUNCTOR_COPY_AND_RELEASE BHEAP_FUNCTOR_COPY_AND_RELEASE
+#endif
+#include "dynamic_array.h"
+
+/* Helper macros */
+#define BHEAP_FUNC__(Func) CONCAT(CONCAT(CONCAT(bheap_, BHEAP_NAME), _), Func)
+#define BHEAP_TYPE__ CONCAT(bheap_, BHEAP_NAME)
+#define BHEAP_NODES__ CONCAT(CONCAT(darray_, BHEAP_NAME), __)
+#define BHEAP_NODES_FUNC__(Func) CONCAT(CONCAT(BHEAP_NODES__, _), Func)
+
+struct BHEAP_TYPE__ {
+ struct BHEAP_NODES__ nodes;
+};
+
+/*******************************************************************************
+ * Internal default functors
+ ******************************************************************************/
+#ifndef BHEAP_FUNCTOR_COMPARE
+static FINLINE int
+BHEAP_FUNC__(functor_cmp__)(const BHEAP_DATA* a, const BHEAP_DATA* b)
+{
+ ASSERT(a && b);
+ if(*a < *b) return -1;
+ if(*a > *b) return 1;
+ return 0;
+}
+#define BHEAP_FUNCTOR_COMPARE BHEAP_FUNC__(functor_cmp__)
+#endif
+
+/*******************************************************************************
+ * Binary heap API
+ ******************************************************************************/
+static INLINE void
+BHEAP_FUNC__(init)
+ (struct mem_allocator* allocator, /* May be NULL <=> use default allocator */
+ struct BHEAP_TYPE__* heap)
+{
+ ASSERT(heap);
+ BHEAP_NODES_FUNC__(init)(allocator, &heap->nodes);
+}
+
+static INLINE void
+BHEAP_FUNC__(release)(struct BHEAP_TYPE__* heap)
+{
+ ASSERT(heap);
+ BHEAP_NODES_FUNC__(release)(&heap->nodes);
+}
+
+static INLINE void
+BHEAP_FUNC__(clear)(struct BHEAP_TYPE__* heap)
+{
+ ASSERT(heap);
+ BHEAP_NODES_FUNC__(clear)(&heap->nodes);
+}
+
+static INLINE char
+BHEAP_FUNC__(is_empty)(struct BHEAP_TYPE__* heap)
+{
+ ASSERT(heap);
+ return BHEAP_NODES_FUNC__(size_get)(&heap->nodes) == 0;
+}
+
+static INLINE int
+BHEAP_FUNC__(insert)(struct BHEAP_TYPE__* heap, const uint64_t value)
+{
+ uint64_t* nodes = NULL;
+ uint64_t node;
+ size_t inode = 0;
+
+ ASSERT(heap);
+ inode = BHEAP_NODES_FUNC__(size_get)(&heap->nodes);
+
+ node = value;
+ if(BHEAP_NODES_FUNC__(push_back)(&heap->nodes, &node))
+ return -1;
+
+ nodes = BHEAP_NODES_FUNC__(data_get)(&heap->nodes);
+ while(inode) {
+ const size_t iparent = (inode - 1) / 2;
+ if(BHEAP_FUNC__(functor_cmp__)(&nodes[iparent], &nodes[inode]) <= 0)
+ break;
+ SWAP(uint64_t, nodes[iparent], nodes[inode]);
+ inode = iparent;
+ }
+ return 0;
+}
+
+static INLINE uint64_t
+BHEAP_FUNC__(top)(struct BHEAP_TYPE__* heap)
+{
+ ASSERT(heap && !BHEAP_FUNC__(is_empty)(&heap->nodes));
+ return BHEAP_NODES_FUNC__(data_get)(&heap->nodes)[0];
+}
+
+static INLINE uint64_t
+BHEAP_FUNC__(pop)(struct BHEAP_TYPE__* heap)
+{
+ uint64_t* nodes = NULL;
+ uint64_t head = 0;
+ uint64_t last = 0;
+ size_t size = 0;
+ size_t inode = 0;
+ size_t ichild = 0;
+ ASSERT(heap && !BHEAP_FUNC__(is_empty)(&heap->nodes));
+
+ nodes = BHEAP_NODES_FUNC__(data_get)(&heap->nodes);
+ head = nodes[0];
+ inode = BHEAP_NODES_FUNC__(size_get)(&heap->nodes) - 1;
+ last = nodes[inode];
+ BHEAP_NODES_FUNC__(pop_back)(&heap->nodes);
+ if(!inode)
+ return head;
+
+ nodes = BHEAP_NODES_FUNC__(data_get)(&heap->nodes);
+ nodes[0] = last;
+ size = inode;
+ for(inode=0, ichild=1; ichild < size; inode = ichild, ichild = 2*inode + 1) {
+ if(ichild + 1 < size && nodes[ichild] > nodes[ichild+1])
+ ++ichild;
+
+ if(nodes[inode] < nodes[ichild])
+ break;
+
+ SWAP(uint64_t, nodes[inode], nodes[ichild]);
+ inode = ichild;
+ }
+ return head;
+}
+
+#undef BHEAP_NAME
+#undef BHEAP_DATA
+#undef BHEAP_FUNCTOR_COMPARE
+#undef BHEAP_FUNCTOR_INIT
+#undef BHEAP_FUNCTOR_COPY
+#undef BHEAP_FUNCTOR_RELEASE
+#undef BHEAP_FUNCTOR_COPY_AND_RELEASE
+#undef BHEAP_FUNC__
+#undef BHEAP_TYPE__
+#undef BHEAP_NODES__
+#undef BHEAP_NODES_FUNC__
+
+#endif /* !BHEAP_NAME || !BHEAP_DATA */
+
diff --git a/src/dynamic_array.h b/src/dynamic_array.h
@@ -183,6 +183,16 @@ DARRAY_FUNC__(push_back)
return 0;
}
+static INLINE void
+DARRAY_FUNC__(pop_back)(struct DARRAY_TYPE__* darray)
+{
+ ASSERT(darray);
+ if(darray->size > 0) {
+ const int err = DARRAY_FUNC__(resize)(darray, darray->size - 1);
+ ASSERT(!err); (void)err;
+ }
+}
+
static INLINE size_t
DARRAY_FUNC__(size_get)(const struct DARRAY_TYPE__* darray)
{
diff --git a/src/test_binary_heap.c b/src/test_binary_heap.c
@@ -0,0 +1,77 @@
+#include "binary_heap.h"
+#include "mem_allocator.h"
+
+#define BHEAP_NAME u64
+#define BHEAP_DATA uint64_t
+#include "binary_heap.h"
+
+int
+main(int argc, char** argv)
+{
+ struct mem_allocator allocator_proxy;
+ struct bheap_u64 heap;
+ uint64_t i;
+ (void)argc, (void)argv;
+
+ mem_init_proxy_allocator(&allocator_proxy, &mem_default_allocator);
+
+ bheap_u64_init(&allocator_proxy, &heap);
+ CHECK(bheap_u64_is_empty(&heap), 1);
+ bheap_u64_clear(&heap);
+ CHECK(bheap_u64_is_empty(&heap), 1);
+
+ CHECK(bheap_u64_is_empty(&heap), 1);
+ CHECK(bheap_u64_insert(&heap, 48), 0);
+ CHECK(bheap_u64_insert(&heap, 51), 0);
+ CHECK(bheap_u64_insert(&heap, 1), 0);
+ CHECK(bheap_u64_insert(&heap, 7), 0);
+ CHECK(bheap_u64_insert(&heap, 78), 0);
+ CHECK(bheap_u64_insert(&heap, 4), 0);
+ CHECK(bheap_u64_insert(&heap, 61), 0);
+ CHECK(bheap_u64_insert(&heap, 72), 0);
+ CHECK(bheap_u64_is_empty(&heap), 0);
+
+ CHECK(bheap_u64_top(&heap), 1);
+ CHECK(bheap_u64_top(&heap), 1);
+ CHECK(bheap_u64_pop(&heap), 1);
+ CHECK(bheap_u64_pop(&heap), 4);
+ CHECK(bheap_u64_pop(&heap), 7);
+ CHECK(bheap_u64_pop(&heap), 48);
+
+ CHECK(bheap_u64_insert(&heap, 5), 0);
+ CHECK(bheap_u64_insert(&heap, 50), 0);
+ CHECK(bheap_u64_insert(&heap, 51), 0);
+ CHECK(bheap_u64_top(&heap), 5);
+ CHECK(bheap_u64_pop(&heap), 5);
+ CHECK(bheap_u64_pop(&heap), 50);
+ CHECK(bheap_u64_pop(&heap), 51);
+ CHECK(bheap_u64_pop(&heap), 51);
+ CHECK(bheap_u64_pop(&heap), 61);
+ CHECK(bheap_u64_pop(&heap), 72);
+ CHECK(bheap_u64_pop(&heap), 78);;
+
+ CHECK(bheap_u64_is_empty(&heap), 1);
+
+ FOR_EACH(i, 0, 17689) {
+ CHECK(bheap_u64_insert(&heap, (uint64_t)rand()), 0);
+ }
+ CHECK(bheap_u64_is_empty(&heap), 0);
+ i = bheap_u64_pop(&heap);
+ while(!bheap_u64_is_empty(&heap)) {
+ uint64_t j = bheap_u64_pop(&heap);
+ CHECK(j >= i, 1);
+ i = j;
+ }
+
+ bheap_u64_release(&heap);
+
+ if(MEM_ALLOCATED_SIZE(&allocator_proxy)) {
+ char dump[512];
+ MEM_DUMP(&allocator_proxy, dump, sizeof(dump)/sizeof(char));
+ fprintf(stderr, "%s\n", dump);
+ FATAL("Memory leaks\n");
+ }
+ mem_shutdown_proxy_allocator(&allocator_proxy);
+ CHECK(mem_allocated_size(), 0);
+ return 0;
+}
