src/ext/timeouts/bench/bench-heap.c

   1 /*
   2  * Copyright (c) 2006 Maxim Yegorushkin <maxim.yegorushkin@gmail.com>
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  * 3. The name of the author may not be used to endorse or promote products
  14  *    derived from this software without specific prior written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  17  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  18  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  19  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  20  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  21  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  22  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  23  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  24  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  25  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26  */
  27 #ifndef _MIN_HEAP_H_
  28 #define _MIN_HEAP_H_
  29
  30 #include <stdlib.h>
  31 #include <err.h>
  32 #include "timeout.h"
  33 #include "bench.h"
  34
  35 #define min_heap_idx interval
  36
  37 typedef timeout_t min_heap_idx_t;
  38
  39 typedef struct min_heap
  40 {
  41     struct timeout** p;
  42     unsigned n, a;
  43     timeout_t curtime;
  44 } min_heap_t;
  45
  46 static inline void           min_heap_ctor(min_heap_t* s);
  47 static inline void           min_heap_dtor(min_heap_t* s);
  48 static inline void           min_heap_elem_init(struct timeout* e);
  49 static inline int            min_heap_elem_greater(struct timeout *a, struct timeout *b);
  50 static inline int            min_heap_empty(min_heap_t* s);
  51 static inline unsigned       min_heap_size(min_heap_t* s);
  52 static inline struct timeout*  min_heap_top(min_heap_t* s);
  53 static inline int            min_heap_reserve(min_heap_t* s, unsigned n);
  54 static inline int            min_heap_push(min_heap_t* s, struct timeout* e);
  55 static inline struct timeout*  min_heap_pop(min_heap_t* s);
  56 static inline int            min_heap_erase(min_heap_t* s, struct timeout* e);
  57 static inline void           min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct timeout* e);
  58 static inline void           min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct timeout* e);
  59
  60 int min_heap_elem_greater(struct timeout *a, struct timeout *b)
  61 {
  62     return a->expires > b->expires;
  63 }
  64
  65 void min_heap_ctor(min_heap_t* s) { s->p = 0; s->n = 0; s->a = 0; }
  66 void min_heap_dtor(min_heap_t* s) { if(s->p) free(s->p); }
  67 void min_heap_elem_init(struct timeout* e) { e->min_heap_idx = -1; }
  68 int min_heap_empty(min_heap_t* s) { return 0u == s->n; }
  69 unsigned min_heap_size(min_heap_t* s) { return s->n; }
  70 struct timeout* min_heap_top(min_heap_t* s) { return s->n ? *s->p : 0; }
  71
  72 int min_heap_push(min_heap_t* s, struct timeout* e)
  73 {
  74     if(min_heap_reserve(s, s->n + 1))
  75         return -1;
  76     min_heap_shift_up_(s, s->n++, e);
  77     return 0;
  78 }
  79
  80 struct timeout* min_heap_pop(min_heap_t* s)
  81 {
  82     if(s->n)
  83     {
  84         struct timeout* e = *s->p;
  85         min_heap_shift_down_(s, 0u, s->p[--s->n]);
  86         e->min_heap_idx = -1;
  87         return e;
  88     }
  89     return 0;
  90 }
  91
  92 int min_heap_erase(min_heap_t* s, struct timeout* e)
  93 {
  94     if(((min_heap_idx_t)-1) != e->min_heap_idx)
  95     {
  96         struct timeout *last = s->p[--s->n];
  97         unsigned parent = (e->min_heap_idx - 1) / 2;
  98         /* we replace e with the last element in the heap.  We might need to
  99            shift it upward if it is less than its parent, or downward if it is
 100            greater than one or both its children. Since the children are known
 101            to be less than the parent, it can't need to shift both up and
 102            down. */
 103         if (e->min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last))
 104              min_heap_shift_up_(s, e->min_heap_idx, last);
 105         else
 106              min_heap_shift_down_(s, e->min_heap_idx, last);
 107         e->min_heap_idx = -1;
 108         return 0;
 109     }
 110     return -1;
 111 }
 112
 113 int min_heap_reserve(min_heap_t* s, unsigned n)
 114 {
 115     if(s->a < n)
 116     {
 117         struct timeout** p;
 118         unsigned a = s->a ? s->a * 2 : 8;
 119         if(a < n)
 120             a = n;
 121         if(!(p = (struct timeout**)realloc(s->p, a * sizeof *p)))
 122             return -1;
 123         s->p = p;
 124         s->a = a;
 125     }
 126     return 0;
 127 }
 128
 129 void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct timeout* e)
 130 {
 131     unsigned parent = (hole_index - 1) / 2;
 132     while(hole_index && min_heap_elem_greater(s->p[parent], e))
 133     {
 134         (s->p[hole_index] = s->p[parent])->min_heap_idx = hole_index;
 135         hole_index = parent;
 136         parent = (hole_index - 1) / 2;
 137     }
 138     (s->p[hole_index] = e)->min_heap_idx = hole_index;
 139 }
 140
 141 void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct timeout* e)
 142 {
 143     unsigned min_child = 2 * (hole_index + 1);
 144     while(min_child <= s->n)
 145         {
 146         min_child -= min_child == s->n || min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]);
 147         if(!(min_heap_elem_greater(e, s->p[min_child])))
 148             break;
 149         (s->p[hole_index] = s->p[min_child])->min_heap_idx = hole_index;
 150         hole_index = min_child;
 151         min_child = 2 * (hole_index + 1);
 152         }
 153     min_heap_shift_up_(s, hole_index,  e);
 154 }
 155
 156 #endif /* _MIN_HEAP_H_ */
 157
 158
 159 static void *init(struct timeout *timeout, size_t count, int verbose) {
 160     min_heap_t *H;
 161     size_t i;
 162
 163     H = calloc(1, sizeof *H);
 164
 165     min_heap_ctor(H);
 166     if (0 != min_heap_reserve(H, count))
 167         err(1, "realloc");
 168
 169     for (i = 0; i < count; i++) {
 170         min_heap_elem_init(&timeout[i]);
 171     }
 172
 173     return H;
 174 } /* init() */
 175
 176
 177 static void add(void *ctx, struct timeout *to, timeout_t expires) {
 178     min_heap_t *H = ctx;
 179     min_heap_erase(H, to);
 180     to->expires = H->curtime + expires;
 181     if (0 != min_heap_push(H, to))
 182         err(1, "realloc");
 183 } /* add() */
 184
 185
 186 static void del(void *ctx, struct timeout *to) {
 187     min_heap_erase(ctx, to);
 188 } /* del() */
 189
 190
 191 static struct timeout *get(void *ctx) {
 192     min_heap_t *H = ctx;
 193     struct timeout *to;
 194
 195     if ((to = min_heap_top(H)) && to->expires <= H->curtime)
 196         return min_heap_pop(H);
 197
 198     return NULL;
 199 } /* get() */
 200
 201
 202 static void update(void *ctx, timeout_t ts) {
 203     min_heap_t *H = ctx;
 204     H->curtime = ts;
 205 } /* update() */
 206
 207
 208 static void check(void *ctx) {
 209     return;
 210 } /* check() */
 211
 212
 213 static int empty(void *ctx) {
 214     min_heap_t *H = ctx;
 215
 216     return (NULL == min_heap_top(H));
 217 } /* empty() */
 218
 219
 220 static void destroy(void *H) {
 221     free(H);
 222     return;
 223 } /* destroy() */
 224
 225
 226 const struct benchops benchops = {
 227     .init    = &init,
 228     .add     = &add,
 229     .del     = &del,
 230     .get     = &get,
 231     .update  = &update,
 232     .check   = &check,
 233     .empty   = &empty,
 234     .destroy = &destroy,
 235 };
 236