diff options
Diffstat (limited to 'test/rspamd_heap_test.c')
| -rw-r--r-- | test/rspamd_heap_test.c | 166 |
1 files changed, 82 insertions, 84 deletions
diff --git a/test/rspamd_heap_test.c b/test/rspamd_heap_test.c index 711ab1c88..dcc7bbc4d 100644 --- a/test/rspamd_heap_test.c +++ b/test/rspamd_heap_test.c @@ -22,53 +22,51 @@ static const guint niter = 100500; static const guint nrem = 100; -static inline -struct rspamd_min_heap_elt * -new_elt (guint pri) +static inline struct rspamd_min_heap_elt * +new_elt(guint pri) { struct rspamd_min_heap_elt *elt; - elt = g_slice_alloc0 (sizeof (*elt)); + elt = g_slice_alloc0(sizeof(*elt)); elt->pri = pri; return elt; } static gdouble -heap_nelts_test (guint nelts) +heap_nelts_test(guint nelts) { struct rspamd_min_heap *heap; struct rspamd_min_heap_elt *elts; gdouble t1, t2; guint i; - heap = rspamd_min_heap_create (nelts); + heap = rspamd_min_heap_create(nelts); /* Preallocate all elts */ - elts = g_slice_alloc (sizeof (*elts) * nelts); + elts = g_slice_alloc(sizeof(*elts) * nelts); - for (i = 0; i < nelts; i ++) { - elts[i].pri = ottery_rand_uint32 () % G_MAXINT32 + 1; + for (i = 0; i < nelts; i++) { + elts[i].pri = ottery_rand_uint32() % G_MAXINT32 + 1; elts[i].idx = 0; } - t1 = rspamd_get_virtual_ticks (); - for (i = 0; i < nelts; i ++) { - rspamd_min_heap_push (heap, &elts[i]); + t1 = rspamd_get_virtual_ticks(); + for (i = 0; i < nelts; i++) { + rspamd_min_heap_push(heap, &elts[i]); } - for (i = 0; i < nelts; i ++) { - (void)rspamd_min_heap_pop (heap); + for (i = 0; i < nelts; i++) { + (void) rspamd_min_heap_pop(heap); } - t2 = rspamd_get_virtual_ticks (); + t2 = rspamd_get_virtual_ticks(); - g_slice_free1 (sizeof (*elts) * nelts, elts); - rspamd_min_heap_destroy (heap); + g_slice_free1(sizeof(*elts) * nelts, elts); + rspamd_min_heap_destroy(heap); return (t2 - t1); } -void -rspamd_heap_test_func (void) +void rspamd_heap_test_func(void) { struct rspamd_min_heap *heap; struct rspamd_min_heap_elt *elt, *telt; @@ -77,108 +75,108 @@ rspamd_heap_test_func (void) 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); - - 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); + 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->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); + 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); + 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); + 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); + 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 = 100; i > 0; i--) { + elt = new_elt(i - 1); + rspamd_min_heap_push(heap, elt); } - for (i = 0; i < 100; i ++) { - elt = rspamd_min_heap_pop (heap); - g_assert (elt->pri == i); + for (i = 0; i < 100; i++) { + elt = rspamd_min_heap_pop(heap); + g_assert(elt->pri == i); } - rspamd_min_heap_destroy (heap); + rspamd_min_heap_destroy(heap); /* Fuzz test */ - heap = rspamd_min_heap_create (128); + 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); + 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); + 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); + 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); + for (i = 0; i < niter - nrem; i++) { + elt = rspamd_min_heap_pop(heap); if (prev != 0) { - g_assert (elt->pri >= prev); + g_assert(elt->pri >= prev); } prev = elt->pri; } - rspamd_min_heap_destroy (heap); + 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)); + for (i = 1; i <= G_N_ELEMENTS(t); i++) { + t[i - 1] = heap_nelts_test(0x1 << (i + 4)); } - for (i = 1; i <= G_N_ELEMENTS (t); i ++) { - rspamd_printf ("Elements: %d, time: %.4f\n", 0x1 << (i + 4), t[i - 1]); + for (i = 1; i <= G_N_ELEMENTS(t); i++) { + rspamd_printf("Elements: %d, time: %.4f\n", 0x1 << (i + 4), t[i - 1]); } } |