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