release/src/router/libevent/test/regress_minheap.c

   1 /*
   2  * Copyright (c) 2009-2010 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
  27 #include <stdlib.h>
  28 #include "event2/event_struct.h"
  29
  30 #include "tinytest.h"
  31 #include "tinytest_macros.h"
  32 #include "../minheap-internal.h"
  33
  34 static void
  35 set_random_timeout(struct event *ev)
  36 {
  37         ev->ev_timeout.tv_sec = rand();
  38         ev->ev_timeout.tv_usec = rand() & 0xfffff;
  39         ev->ev_timeout_pos.min_heap_idx = -1;
  40 }
  41
  42 static void
  43 check_heap(struct min_heap *heap)
  44 {
  45         unsigned i;
  46         for (i = 1; i < heap->n; ++i) {
  47                 unsigned parent_idx = (i-1)/2;
  48                 tt_want(evutil_timercmp(&heap->p[i]->ev_timeout,
  49                         &heap->p[parent_idx]->ev_timeout, >=));
  50         }
  51 }
  52
  53 static void
  54 test_heap_randomized(void *ptr)
  55 {
  56         struct min_heap heap;
  57         struct event *inserted[1024];
  58         struct event *e, *last_e;
  59         int i;
  60
  61         min_heap_ctor(&heap);
  62
  63         for (i = 0; i < 1024; ++i) {
  64                 inserted[i] = malloc(sizeof(struct event));
  65                 set_random_timeout(inserted[i]);
  66                 min_heap_push(&heap, inserted[i]);
  67         }
  68         check_heap(&heap);
  69
  70         tt_assert(min_heap_size(&heap) == 1024);
  71
  72         for (i = 0; i < 512; ++i) {
  73                 min_heap_erase(&heap, inserted[i]);
  74                 if (0 == (i % 32))
  75                         check_heap(&heap);
  76         }
  77         tt_assert(min_heap_size(&heap) == 512);
  78
  79         last_e = min_heap_pop(&heap);
  80         while (1) {
  81                 e = min_heap_pop(&heap);
  82                 if (!e)
  83                         break;
  84                 tt_want(evutil_timercmp(&last_e->ev_timeout,
  85                         &e->ev_timeout, <=));
  86         }
  87         tt_assert(min_heap_size(&heap) == 0);
  88 end:
  89         for (i = 0; i < 1024; ++i)
  90                 free(inserted[i]);
  91
  92         min_heap_dtor(&heap);
  93 }
  94
  95 struct testcase_t minheap_testcases[] = {
  96         { "randomized", test_heap_randomized, 0, NULL, NULL },
  97         END_OF_TESTCASES
  98 };