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