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