[Test] More improvements to heap tests

1 files changed, 67 insertions, 26 deletions

diff --git a/test/rspamd_heap_test.c b/test/rspamd_heap_test.c
index 56f9e0b9c..711ab1c88 100644
--- a/test/rspamd_heap_test.c
+++ b/test/rspamd_heap_test.c
@@ -19,8 +19,8 @@
 #include "heap.h"
 #include "ottery.h"
 
-static const niter = 100500;
-static const nrem = 100;
+static const guint niter = 100500;
+static const guint nrem = 100;
 
 static inline
 struct rspamd_min_heap_elt *
@@ -48,7 +48,7 @@ heap_nelts_test (guint nelts)
 
 	for (i = 0; i < nelts; i ++) {
 		elts[i].pri = ottery_rand_uint32 () % G_MAXINT32 + 1;
-		elts[i].idx = NULL;
+		elts[i].idx = 0;
 	}
 
 	t1 = rspamd_get_virtual_ticks ();
@@ -71,38 +71,96 @@ void
 rspamd_heap_test_func (void)
 {
 	struct rspamd_min_heap *heap;
-	struct rspamd_min_heap_elt *elt;
-	gint i;
+	struct rspamd_min_heap_elt *elt, *telt;
+	guint i;
 	guint prev;
 	gdouble t[16];
 
+	/* Push + update */
 	heap = rspamd_min_heap_create (32);
+	elt = new_elt (2);
+	elt->data = GINT_TO_POINTER (1);
+	rspamd_min_heap_push (heap, elt);
+	elt = new_elt (3);
+	elt->data = GINT_TO_POINTER (2);
+	rspamd_min_heap_push (heap, elt);
+	elt = new_elt (4);
+	elt->data = GINT_TO_POINTER (3);
+	rspamd_min_heap_push (heap, elt);
 
-	for (i = 100; i >= 0; i --) {
-		elt = new_elt (i);
+	rspamd_min_heap_update_elt (heap, elt, 0);
+	elt = rspamd_min_heap_pop (heap);
+	g_assert (elt->data == GINT_TO_POINTER (3));
+
+	rspamd_min_heap_destroy (heap);
+
+	/* Push + remove */
+	heap = rspamd_min_heap_create (32);
+	elt = new_elt (2);
+	elt->data = GINT_TO_POINTER (1);
+	rspamd_min_heap_push (heap, elt);
+	rspamd_min_heap_remove_elt (heap, elt);
+	elt = new_elt (3);
+	elt->data = GINT_TO_POINTER (2);
+	rspamd_min_heap_push (heap, elt);
+	elt = rspamd_min_heap_pop (heap);
+	g_assert (elt->data == GINT_TO_POINTER (2));
+	elt = rspamd_min_heap_pop (heap);
+	g_assert (elt == NULL);
+
+	/* Push + push + remove + pop */
+	elt = new_elt (2);
+	elt->data = GINT_TO_POINTER (1);
+	rspamd_min_heap_push (heap, elt);
+	telt = elt;
+	elt = new_elt (3);
+	elt->data = GINT_TO_POINTER (2);
+	rspamd_min_heap_push (heap, elt);
+	rspamd_min_heap_remove_elt (heap, telt);
+	elt = rspamd_min_heap_pop (heap);
+	g_assert (elt->data == GINT_TO_POINTER (2));
+	rspamd_min_heap_destroy (heap);
+
+	/* Bulk test */
+	heap = rspamd_min_heap_create (32);
+
+	for (i = 100; i > 0; i --) {
+		elt = new_elt (i - 1);
 		rspamd_min_heap_push (heap, elt);
 	}
 
-	for (i = 0; i <= 100; i ++) {
+	for (i = 0; i < 100; i ++) {
 		elt = rspamd_min_heap_pop (heap);
 		g_assert (elt->pri == i);
 	}
 
 	rspamd_min_heap_destroy (heap);
+
+	/* Fuzz test */
 	heap = rspamd_min_heap_create (128);
 
+	/* Add */
 	for (i = 0; i < niter; i ++) {
 		elt = new_elt (ottery_rand_uint32 () % G_MAXINT32 + 1);
 		rspamd_min_heap_push (heap, elt);
 	}
 
+	/* Remove */
 	for (i = 0; i < nrem; i ++) {
 		elt = rspamd_min_heap_index (heap, ottery_rand_uint32 () % niter);
 		rspamd_min_heap_remove_elt (heap, elt);
 	}
 
+	/* Update */
+	for (i = 0; i < niter / 10; i ++) {
+		elt = rspamd_min_heap_index (heap, ottery_rand_uint32 () % (niter - nrem));
+		rspamd_min_heap_update_elt (heap, elt,
+				ottery_rand_uint32 () % G_MAXINT32 + 1);
+	}
+
 	prev = 0;
 
+	/* Pop and check invariant */
 	for (i = 0; i < niter - nrem; i ++) {
 		elt = rspamd_min_heap_pop (heap);
 
@@ -115,24 +173,7 @@ rspamd_heap_test_func (void)
 
 	rspamd_min_heap_destroy (heap);
 
-	heap = rspamd_min_heap_create (32);
-
-	elt = new_elt (2);
-	elt->data = GINT_TO_POINTER (1);
-	rspamd_min_heap_push (heap, elt);
-	elt = new_elt (3);
-	elt->data = GINT_TO_POINTER (2);
-	rspamd_min_heap_push (heap, elt);
-	elt = new_elt (4);
-	elt->data = GINT_TO_POINTER (3);
-	rspamd_min_heap_push (heap, elt);
-
-	rspamd_min_heap_update_elt (heap, elt, 0);
-	elt = rspamd_min_heap_pop (heap);
-	g_assert (elt->idx == GINT_TO_POINTER (3));
-
-	rspamd_min_heap_destroy (heap);
-
+	/* Complexity test (should be O(n * logn) */
 	for (i = 1; i <= G_N_ELEMENTS (t); i ++) {
 		t[i - 1] = heap_nelts_test (0x1 << (i + 4));
 	}