commit 7b24c1b44e2ee18ac15d2d698e66cfee0b6bdaf4
parent 56f8c7a245561abeaee4f5914c733a052aa51e21
Author: vaplv <vaplv@free.fr>
Date: Sun, 30 Mar 2014 00:05:53 +0100
Major changes of the binary heap API
Push further the binary heap tests
Diffstat:
3 files changed, 204 insertions(+), 60 deletions(-)
diff --git a/src/binary_heap.h b/src/binary_heap.h
@@ -78,6 +78,16 @@ BHEAP_FUNC__(functor_cmp__)(const BHEAP_DATA* a, const BHEAP_DATA* b)
#define BHEAP_FUNCTOR_COMPARE BHEAP_FUNC__(functor_cmp__)
#endif
+#ifndef BHEAP_FUNCTOR_COPY
+ #define BHEAP_FUNCTOR_COPY BHEAP_NODES_FUNC__(functor_cp__)
+#endif
+#ifndef BHEAP_FUNCTOR_INIT
+ #define BHEAP_FUNCTOR_INIT BHEAP_NODES_FUNC__(functor_init__)
+#endif
+#ifndef BHEAP_FUNCTOR_RELEASE
+ #define BHEAP_FUNCTOR_RELEASE BHEAP_NODES_FUNC__(functor_release__)
+#endif
+
/*******************************************************************************
* Binary heap API
******************************************************************************/
@@ -112,70 +122,94 @@ BHEAP_FUNC__(is_empty)(struct BHEAP_TYPE__* heap)
}
static INLINE int
-BHEAP_FUNC__(insert)(struct BHEAP_TYPE__* heap, const uint64_t value)
+BHEAP_FUNC__(insert)(struct BHEAP_TYPE__* heap, const BHEAP_DATA* value)
{
- uint64_t* nodes = NULL;
- uint64_t node;
+ BHEAP_DATA* nodes = NULL;
+ BHEAP_DATA tmp;
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))
+ if(BHEAP_NODES_FUNC__(push_back)(&heap->nodes, value))
return -1;
nodes = BHEAP_NODES_FUNC__(data_get)(&heap->nodes);
+ BHEAP_FUNCTOR_INIT(heap->nodes.allocator, &tmp);
while(inode) {
const size_t iparent = (inode - 1) / 2;
- if(BHEAP_FUNC__(functor_cmp__)(&nodes[iparent], &nodes[inode]) <= 0)
+ if(BHEAP_FUNCTOR_COMPARE(&nodes[iparent], &nodes[inode]) <= 0)
break;
- SWAP(uint64_t, nodes[iparent], nodes[inode]);
+
+ BHEAP_FUNCTOR_COPY(&tmp, &nodes[iparent]);
+ BHEAP_FUNCTOR_COPY(&nodes[iparent], &nodes[inode]);
+ BHEAP_FUNCTOR_COPY(&nodes[inode], &tmp);
inode = iparent;
}
+ BHEAP_FUNCTOR_RELEASE(&tmp);
return 0;
}
-static INLINE uint64_t
-BHEAP_FUNC__(top)(struct BHEAP_TYPE__* heap)
+static INLINE char
+BHEAP_FUNC__(top)(struct BHEAP_TYPE__* heap, BHEAP_DATA* top)
{
- ASSERT(heap && !BHEAP_FUNC__(is_empty)(&heap->nodes));
- return BHEAP_NODES_FUNC__(data_get)(&heap->nodes)[0];
+ ASSERT(heap);
+
+ if(BHEAP_FUNC__(is_empty)(heap))
+ return 0;
+
+ BHEAP_FUNCTOR_COPY(top, &BHEAP_NODES_FUNC__(data_get)(&heap->nodes)[0]);
+ return 1;
}
-static INLINE uint64_t
-BHEAP_FUNC__(pop)(struct BHEAP_TYPE__* heap)
+static INLINE char
+BHEAP_FUNC__(pop)(struct BHEAP_TYPE__* heap, BHEAP_DATA* top)
{
- uint64_t* nodes = NULL;
- uint64_t head = 0;
- uint64_t last = 0;
+ BHEAP_DATA* nodes = NULL;
+ BHEAP_DATA tmp;
size_t size = 0;
size_t inode = 0;
size_t ichild = 0;
- ASSERT(heap && !BHEAP_FUNC__(is_empty)(&heap->nodes));
+ char res = 1;
+ ASSERT(heap);
+
+ BHEAP_FUNCTOR_INIT(heap->nodes.allocator, &tmp);
+
+ if(BHEAP_FUNC__(is_empty)(heap)) {
+ res = 0;
+ goto exit;
+ }
nodes = BHEAP_NODES_FUNC__(data_get)(&heap->nodes);
- head = nodes[0];
+ BHEAP_FUNCTOR_COPY(top, &nodes[0]);
inode = BHEAP_NODES_FUNC__(size_get)(&heap->nodes) - 1;
- last = nodes[inode];
+ BHEAP_FUNCTOR_COPY(&tmp, &nodes[inode]);
BHEAP_NODES_FUNC__(pop_back)(&heap->nodes);
- if(!inode)
- return head;
+ if(!inode) {
+ res = 1;
+ goto exit;
+ }
nodes = BHEAP_NODES_FUNC__(data_get)(&heap->nodes);
- nodes[0] = last;
+ BHEAP_FUNCTOR_COPY(&nodes[0], &tmp);
size = inode;
for(inode=0, ichild=1; ichild < size; inode = ichild, ichild = 2*inode + 1) {
- if(ichild + 1 < size && nodes[ichild] > nodes[ichild+1])
+
+ if(ichild + 1 < size
+ && BHEAP_FUNCTOR_COMPARE(&nodes[ichild], &nodes[ichild+1]) > 0)
++ichild;
- if(nodes[inode] < nodes[ichild])
+ if(BHEAP_FUNCTOR_COMPARE(&nodes[inode], &nodes[ichild]) <= 0)
break;
- SWAP(uint64_t, nodes[inode], nodes[ichild]);
+ BHEAP_FUNCTOR_COPY(&tmp, &nodes[inode]);
+ BHEAP_FUNCTOR_COPY(&nodes[inode], &nodes[ichild]);
+ BHEAP_FUNCTOR_COPY(&nodes[ichild], &tmp);
inode = ichild;
}
- return head;
+exit:
+ BHEAP_FUNCTOR_RELEASE(&tmp);
+ return res;
}
#undef BHEAP_NAME
diff --git a/src/test_binary_heap.c b/src/test_binary_heap.c
@@ -1,17 +1,17 @@
#include "binary_heap.h"
#include "mem_allocator.h"
+#include "str.h"
#define BHEAP_NAME u64
#define BHEAP_DATA uint64_t
#include "binary_heap.h"
-int
-main(int argc, char** argv)
+static void
+test_primitive_type(void)
{
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);
@@ -21,44 +21,63 @@ main(int argc, char** argv)
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_top(&heap, &i), 0);
+ CHECK(bheap_u64_pop(&heap, &i), 0);
+ i = 48; CHECK(bheap_u64_insert(&heap, &i), 0);
+ i = 51; CHECK(bheap_u64_insert(&heap, &i), 0);
+ i = 1; CHECK(bheap_u64_insert(&heap, &i), 0);
+ i = 7; CHECK(bheap_u64_insert(&heap, &i), 0);
+ i = 78; CHECK(bheap_u64_insert(&heap, &i), 0);
+ i = 4; CHECK(bheap_u64_insert(&heap, &i), 0);
+ i = 61; CHECK(bheap_u64_insert(&heap, &i), 0);
+ i = 72; CHECK(bheap_u64_insert(&heap, &i), 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);;
+ NCHECK(bheap_u64_top(&heap, &i), 0);
+ CHECK(i, 1);
+ NCHECK(bheap_u64_top(&heap, &i), 0);
+ CHECK(i, 1);
+ NCHECK(bheap_u64_pop(&heap, &i), 0);
+ CHECK(i, 1);
+ NCHECK(bheap_u64_pop(&heap, &i), 0);
+ CHECK(i, 4);
+ NCHECK(bheap_u64_pop(&heap, &i), 0);
+ CHECK(i, 7);
+ NCHECK(bheap_u64_pop(&heap, &i), 0);
+ CHECK(i, 48);
+
+ i = 5; CHECK(bheap_u64_insert(&heap, &i), 0);
+ i = 50; CHECK(bheap_u64_insert(&heap, &i), 0);
+ i = 51; CHECK(bheap_u64_insert(&heap, &i), 0);
+ NCHECK(bheap_u64_top(&heap, &i), 0);
+ CHECK(i, 5);
+ NCHECK(bheap_u64_pop(&heap, &i), 0);
+ CHECK(i, 5);
+ NCHECK(bheap_u64_pop(&heap, &i), 0);
+ CHECK(i, 50);
+ NCHECK(bheap_u64_pop(&heap, &i), 0);
+ CHECK(i, 51);
+ NCHECK(bheap_u64_pop(&heap, &i), 0);
+ CHECK(i, 51);
+ NCHECK(bheap_u64_pop(&heap, &i), 0);
+ CHECK(i, 61);
+ NCHECK(bheap_u64_pop(&heap, &i), 0);
+ CHECK(i, 72);
+ NCHECK(bheap_u64_pop(&heap, &i), 0);
+ CHECK(i, 78);
+ CHECK(bheap_u64_pop(&heap, &i), 0);
CHECK(bheap_u64_is_empty(&heap), 1);
FOR_EACH(i, 0, 17689) {
- CHECK(bheap_u64_insert(&heap, (uint64_t)rand()), 0);
+ const uint64_t j = (uint64_t)rand();
+ CHECK(bheap_u64_insert(&heap, &j), 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);
+ NCHECK(bheap_u64_pop(&heap, &i), 0);
+ while(bheap_u64_is_empty(&heap)) {
+ uint64_t j = 0;
+ NCHECK(bheap_u64_pop(&heap, &j), 0);
CHECK(j >= i, 1);
i = j;
}
@@ -72,6 +91,98 @@ main(int argc, char** argv)
FATAL("Memory leaks\n");
}
mem_shutdown_proxy_allocator(&allocator_proxy);
+}
+
+static int
+str_cmp(const struct str* a, const struct str* b)
+{
+ ASSERT(a && b);
+ return strcmp(str_cget(a), str_cget(b));
+}
+
+#define BHEAP_NAME str
+#define BHEAP_DATA struct str
+#define BHEAP_FUNCTOR_INIT str_init
+#define BHEAP_FUNCTOR_COPY str_copy
+#define BHEAP_FUNCTOR_RELEASE str_release
+#define BHEAP_FUNCTOR_COPY_AND_RELEASE str_copy_and_release
+#define BHEAP_FUNCTOR_COMPARE str_cmp
+#include "binary_heap.h"
+
+static void
+test_struct(void)
+{
+ struct mem_allocator allocator_proxy;
+ struct bheap_str heap;
+ struct str str;
+ size_t i;
+ const char* strs[] = {
+ "Rcvfbqr", "1,", "XARR-QRRC", "VA", "GUR", "QRNQ:\n",
+ "---------------------------------", "BAPR", "LBH", "ORNG", "GUR", "OVT",
+ "ONQNFFRF", "NAQ", "PYRNA", "BHG", "GUR", "ZBBA", "ONFR", "LBH'ER",
+ "FHCCBFRQ", "GB\n", "JVA", "NERA'G", "LBH?", "NERA'G", "LBH?", "JURER'F",
+ "LBHE", "SNG", "ERJNEQ", "NAQ", "GVPXRG", "UBZR?", "JUNG\n", "GUR", "URYY",
+ "VF", "GUVF?", "VG'F", "ABG", "FHCCBFRQ", "GB", "RAQ", "GUVF", "JNL!", "VG",
+ "FGVAXF", "YVXR", "EBGGRA", "ZRNG,", "OHG", "YBBXF", "YVXR", "GUR", "YBFG",
+ "QRVZBF", "ONFR.", "YBBXF", "YVXR\n", "LBH'ER", "FGHPX", "BA", "GUR",
+ "FUBERF", "BS", "URYY.", "GUR", "BAYL", "JNL", "BHG", "VF", "GUEBHTU.", "GB",
+ "PBAGVAHR", "GUR", "QBBZ", "RKCREVRAPR,", "CYNL", "GUR", "FUBERF", "BS",
+ "URYY", "NAQ", "VGF", "NZNMVAT\n", "FRDHRY,", "VASREAB!",
+
+ "Rcvfbqr 2, GUR FUBERF BS URYY:\n\
+ ------------------------------\n\
+ \n\
+ LBH'IR QBAR VG! GUR UVQRBHF PLORE- QRZBA YBEQ GUNG EHYRQ GUR YBFG QRVZBF ZBBA\n\
+ ONFR UNF ORRA FYNVA NAQ LBH NER GEVHZCUNAG! OHG ... JURER NER LBH? LBH\n\
+ PYNZORE GB GUR RQTR BS GUR ZBBA NAQ YBBX QBJA GB FRR GUR NJSHY GEHGU.\n\
+ \n",
+
+ "QRVZBF SYBNGF NOBIR URYY VGFRYS! LBH'IR ARIRE URNEQ BS NALBAR RFPNCVAT SEBZ\n\
+ URYY, OHG LBH'YY ZNXR GUR ONFGNEQF FBEEL GURL RIRE URNEQ BS LBH! DHVPXYL, LBH\n\
+ ENCCRY QBJA GB GUR FHESNPR BS URYY.\n\
+ \n\
+ ABJ, VG'F BA GB GUR SVANY PUNCGRE BS QBBZ! -- VASREAB."
+ };
+ const size_t nstrs = sizeof(strs)/sizeof(const char*);
+
+ mem_init_proxy_allocator(&allocator_proxy, &mem_default_allocator);
+ str_init(&allocator_proxy, &str);
+
+ bheap_str_init(&allocator_proxy, &heap);
+ FOR_EACH(i, 0, nstrs) {
+ str_set(&str, strs[i]);
+ bheap_str_insert(&heap, &str);
+ }
+
+ NCHECK(bheap_str_pop(&heap, &str), 0);
+ while(bheap_str_is_empty(&heap)) {
+ struct str str2;
+ str_init(&allocator_proxy, &str2);
+ NCHECK(bheap_str_pop(&heap, &str2), 0);
+ CHECK(strcmp(str_cget(&str), str_cget(&str2)), -1);
+ str_set(&str, str_cget(&str2));
+ str_release(&str2);
+ }
+
+ str_release(&str);
+ bheap_str_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);
+}
+
+int
+main(int argc, char** argv)
+{
+ (void)argc, (void)argv;
+ test_primitive_type();
+ test_struct();
CHECK(mem_allocated_size(), 0);
return 0;
}
+
diff --git a/src/test_dynamic_array.c b/src/test_dynamic_array.c
@@ -30,7 +30,6 @@ const char* strs[] = {
ENCCRY QBJA GB GUR FHESNPR BS URYY.\n\
\n\
ABJ, VG'F BA GB GUR SVANY PUNCGRE BS QBBZ! -- VASREAB."
-
};
const size_t nstrs = sizeof(strs)/sizeof(const char*);
