1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/ipc/chromium/src/third_party/libevent/test/regress_minheap.c Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,98 @@
1.4 +/*
1.5 + * Copyright (c) 2009-2012 Niels Provos and Nick Mathewson
1.6 + *
1.7 + * Redistribution and use in source and binary forms, with or without
1.8 + * modification, are permitted provided that the following conditions
1.9 + * are met:
1.10 + * 1. Redistributions of source code must retain the above copyright
1.11 + * notice, this list of conditions and the following disclaimer.
1.12 + * 2. Redistributions in binary form must reproduce the above copyright
1.13 + * notice, this list of conditions and the following disclaimer in the
1.14 + * documentation and/or other materials provided with the distribution.
1.15 + * 3. The name of the author may not be used to endorse or promote products
1.16 + * derived from this software without specific prior written permission.
1.17 + *
1.18 + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
1.19 + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
1.20 + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
1.21 + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
1.22 + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
1.23 + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1.24 + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1.25 + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1.26 + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
1.27 + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1.28 + */
1.29 +
1.30 +#include <stdlib.h>
1.31 +#include "event2/event_struct.h"
1.32 +
1.33 +#include "tinytest.h"
1.34 +#include "tinytest_macros.h"
1.35 +#include "../minheap-internal.h"
1.36 +
1.37 +static void
1.38 +set_random_timeout(struct event *ev)
1.39 +{
1.40 + ev->ev_timeout.tv_sec = rand();
1.41 + ev->ev_timeout.tv_usec = rand() & 0xfffff;
1.42 + ev->ev_timeout_pos.min_heap_idx = -1;
1.43 +}
1.44 +
1.45 +static void
1.46 +check_heap(struct min_heap *heap)
1.47 +{
1.48 + unsigned i;
1.49 + for (i = 1; i < heap->n; ++i) {
1.50 + unsigned parent_idx = (i-1)/2;
1.51 + tt_want(evutil_timercmp(&heap->p[i]->ev_timeout,
1.52 + &heap->p[parent_idx]->ev_timeout, >=));
1.53 + }
1.54 +}
1.55 +
1.56 +static void
1.57 +test_heap_randomized(void *ptr)
1.58 +{
1.59 + struct min_heap heap;
1.60 + struct event *inserted[1024];
1.61 + struct event *e, *last_e;
1.62 + int i;
1.63 +
1.64 + min_heap_ctor(&heap);
1.65 +
1.66 + for (i = 0; i < 1024; ++i) {
1.67 + inserted[i] = malloc(sizeof(struct event));
1.68 + set_random_timeout(inserted[i]);
1.69 + min_heap_push(&heap, inserted[i]);
1.70 + }
1.71 + check_heap(&heap);
1.72 +
1.73 + tt_assert(min_heap_size(&heap) == 1024);
1.74 +
1.75 + for (i = 0; i < 512; ++i) {
1.76 + min_heap_erase(&heap, inserted[i]);
1.77 + if (0 == (i % 32))
1.78 + check_heap(&heap);
1.79 + }
1.80 + tt_assert(min_heap_size(&heap) == 512);
1.81 +
1.82 + last_e = min_heap_pop(&heap);
1.83 + while (1) {
1.84 + e = min_heap_pop(&heap);
1.85 + if (!e)
1.86 + break;
1.87 + tt_want(evutil_timercmp(&last_e->ev_timeout,
1.88 + &e->ev_timeout, <=));
1.89 + }
1.90 + tt_assert(min_heap_size(&heap) == 0);
1.91 +end:
1.92 + for (i = 0; i < 1024; ++i)
1.93 + free(inserted[i]);
1.94 +
1.95 + min_heap_dtor(&heap);
1.96 +}
1.97 +
1.98 +struct testcase_t minheap_testcases[] = {
1.99 + { "randomized", test_heap_randomized, 0, NULL, NULL },
1.100 + END_OF_TESTCASES
1.101 +};
