1*c43e99fdSEd Maste /*
2*c43e99fdSEd Maste * Copyright (c) 2009-2012 Niels Provos and Nick Mathewson
3*c43e99fdSEd Maste *
4*c43e99fdSEd Maste * Redistribution and use in source and binary forms, with or without
5*c43e99fdSEd Maste * modification, are permitted provided that the following conditions
6*c43e99fdSEd Maste * are met:
7*c43e99fdSEd Maste * 1. Redistributions of source code must retain the above copyright
8*c43e99fdSEd Maste * notice, this list of conditions and the following disclaimer.
9*c43e99fdSEd Maste * 2. Redistributions in binary form must reproduce the above copyright
10*c43e99fdSEd Maste * notice, this list of conditions and the following disclaimer in the
11*c43e99fdSEd Maste * documentation and/or other materials provided with the distribution.
12*c43e99fdSEd Maste * 3. The name of the author may not be used to endorse or promote products
13*c43e99fdSEd Maste * derived from this software without specific prior written permission.
14*c43e99fdSEd Maste *
15*c43e99fdSEd Maste * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
16*c43e99fdSEd Maste * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
17*c43e99fdSEd Maste * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
18*c43e99fdSEd Maste * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
19*c43e99fdSEd Maste * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
20*c43e99fdSEd Maste * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21*c43e99fdSEd Maste * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
22*c43e99fdSEd Maste * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23*c43e99fdSEd Maste * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
24*c43e99fdSEd Maste * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25*c43e99fdSEd Maste */
26*c43e99fdSEd Maste #include "../minheap-internal.h"
27*c43e99fdSEd Maste
28*c43e99fdSEd Maste #include <stdlib.h>
29*c43e99fdSEd Maste #include "event2/event_struct.h"
30*c43e99fdSEd Maste
31*c43e99fdSEd Maste #include "tinytest.h"
32*c43e99fdSEd Maste #include "tinytest_macros.h"
33*c43e99fdSEd Maste #include "regress.h"
34*c43e99fdSEd Maste
35*c43e99fdSEd Maste static void
set_random_timeout(struct event * ev)36*c43e99fdSEd Maste set_random_timeout(struct event *ev)
37*c43e99fdSEd Maste {
38*c43e99fdSEd Maste ev->ev_timeout.tv_sec = test_weakrand();
39*c43e99fdSEd Maste ev->ev_timeout.tv_usec = test_weakrand() & 0xfffff;
40*c43e99fdSEd Maste ev->ev_timeout_pos.min_heap_idx = -1;
41*c43e99fdSEd Maste }
42*c43e99fdSEd Maste
43*c43e99fdSEd Maste static void
check_heap(struct min_heap * heap)44*c43e99fdSEd Maste check_heap(struct min_heap *heap)
45*c43e99fdSEd Maste {
46*c43e99fdSEd Maste unsigned i;
47*c43e99fdSEd Maste for (i = 1; i < heap->n; ++i) {
48*c43e99fdSEd Maste unsigned parent_idx = (i-1)/2;
49*c43e99fdSEd Maste tt_want(evutil_timercmp(&heap->p[i]->ev_timeout,
50*c43e99fdSEd Maste &heap->p[parent_idx]->ev_timeout, >=));
51*c43e99fdSEd Maste }
52*c43e99fdSEd Maste }
53*c43e99fdSEd Maste
54*c43e99fdSEd Maste static void
test_heap_randomized(void * ptr)55*c43e99fdSEd Maste test_heap_randomized(void *ptr)
56*c43e99fdSEd Maste {
57*c43e99fdSEd Maste struct min_heap heap;
58*c43e99fdSEd Maste struct event *inserted[1024];
59*c43e99fdSEd Maste struct event *e, *last_e;
60*c43e99fdSEd Maste int i;
61*c43e99fdSEd Maste
62*c43e99fdSEd Maste min_heap_ctor_(&heap);
63*c43e99fdSEd Maste
64*c43e99fdSEd Maste for (i = 0; i < 1024; ++i) {
65*c43e99fdSEd Maste inserted[i] = malloc(sizeof(struct event));
66*c43e99fdSEd Maste set_random_timeout(inserted[i]);
67*c43e99fdSEd Maste min_heap_push_(&heap, inserted[i]);
68*c43e99fdSEd Maste }
69*c43e99fdSEd Maste check_heap(&heap);
70*c43e99fdSEd Maste
71*c43e99fdSEd Maste tt_assert(min_heap_size_(&heap) == 1024);
72*c43e99fdSEd Maste
73*c43e99fdSEd Maste for (i = 0; i < 512; ++i) {
74*c43e99fdSEd Maste min_heap_erase_(&heap, inserted[i]);
75*c43e99fdSEd Maste if (0 == (i % 32))
76*c43e99fdSEd Maste check_heap(&heap);
77*c43e99fdSEd Maste }
78*c43e99fdSEd Maste tt_assert(min_heap_size_(&heap) == 512);
79*c43e99fdSEd Maste
80*c43e99fdSEd Maste last_e = min_heap_pop_(&heap);
81*c43e99fdSEd Maste while (1) {
82*c43e99fdSEd Maste e = min_heap_pop_(&heap);
83*c43e99fdSEd Maste if (!e)
84*c43e99fdSEd Maste break;
85*c43e99fdSEd Maste tt_want(evutil_timercmp(&last_e->ev_timeout,
86*c43e99fdSEd Maste &e->ev_timeout, <=));
87*c43e99fdSEd Maste }
88*c43e99fdSEd Maste tt_assert(min_heap_size_(&heap) == 0);
89*c43e99fdSEd Maste end:
90*c43e99fdSEd Maste for (i = 0; i < 1024; ++i)
91*c43e99fdSEd Maste free(inserted[i]);
92*c43e99fdSEd Maste
93*c43e99fdSEd Maste min_heap_dtor_(&heap);
94*c43e99fdSEd Maste }
95*c43e99fdSEd Maste
96*c43e99fdSEd Maste struct testcase_t minheap_testcases[] = {
97*c43e99fdSEd Maste { "randomized", test_heap_randomized, 0, NULL, NULL },
98*c43e99fdSEd Maste END_OF_TESTCASES
99*c43e99fdSEd Maste };
100