external/bsd/libevent/dist/minheap-internal.h

   1 /*      $NetBSD: minheap-internal.h,v 1.2 2013/04/12 18:11:15 joerg Exp $       */
   2 /*
   3  * Copyright (c) 2007-2012 Niels Provos and Nick Mathewson
   4  *
   5  * Copyright (c) 2006 Maxim Yegorushkin <maxim.yegorushkin@gmail.com>
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  * 2. Redistributions in binary form must reproduce the above copyright
  13  *    notice, this list of conditions and the following disclaimer in the
  14  *    documentation and/or other materials provided with the distribution.
  15  * 3. The name of the author may not be used to endorse or promote products
  16  *    derived from this software without specific prior written permission.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  19  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  20  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  21  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  22  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  23  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  24  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  25  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  26  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  27  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  28  */
  29 #ifndef _MIN_HEAP_H_
  30 #define _MIN_HEAP_H_
  31
  32 #include "event2/event-config.h"
  33 #include "event2/event.h"
  34 #include "event2/event_struct.h"
  35 #include "event2/util.h"
  36 #include "util-internal.h"
  37 #include "mm-internal.h"
  38
  39 typedef struct min_heap
  40 {
  41         struct event** p;
  42         unsigned n, a;
  43 } min_heap_t;
  44
  45 static inline void           min_heap_ctor(min_heap_t* s);
  46 static inline void           min_heap_dtor(min_heap_t* s);
  47 static inline void           min_heap_elem_init(struct event* e);
  48 static inline int            min_heap_elt_is_top(const struct event *e);
  49 static inline int            min_heap_elem_greater(struct event *a, struct event *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 event*  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 event* e);
  55 static inline struct event*  min_heap_pop(min_heap_t* s);
  56 static inline int            min_heap_erase(min_heap_t* s, struct event* e);
  57 static inline void           min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e);
  58 static inline void           min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e);
  59
  60 static inline int min_heap_elem_greater(struct event *a, struct event *b)
  61 {
  62         return evutil_timercmp(&a->ev_timeout, &b->ev_timeout, >);
  63 }
  64
  65 static inline void min_heap_ctor(min_heap_t* s) { s->p = 0; s->n = 0; s->a = 0; }
  66 static inline void min_heap_dtor(min_heap_t* s) { if (s->p) mm_free(s->p); }
  67 static inline void min_heap_elem_init(struct event* e) { e->ev_timeout_pos.min_heap_idx = -1; }
  68 static inline int min_heap_empty(min_heap_t* s) { return 0u == s->n; }
  69 static inline unsigned min_heap_size(min_heap_t* s) { return s->n; }
  70 static inline struct event* min_heap_top(min_heap_t* s) { return s->n ? *s->p : 0; }
  71
  72 static inline int min_heap_push(min_heap_t* s, struct event* 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 static inline struct event* min_heap_pop(min_heap_t* s)
  81 {
  82         if (s->n)
  83         {
  84                 struct event* e = *s->p;
  85                 min_heap_shift_down_(s, 0u, s->p[--s->n]);
  86                 e->ev_timeout_pos.min_heap_idx = -1;
  87                 return e;
  88         }
  89         return 0;
  90 }
  91
  92 static inline int min_heap_elt_is_top(const struct event *e)
  93 {
  94         return e->ev_timeout_pos.min_heap_idx == 0;
  95 }
  96
  97 static inline int min_heap_erase(min_heap_t* s, struct event* e)
  98 {
  99         if (-1 != e->ev_timeout_pos.min_heap_idx)
 100         {
 101                 struct event *last = s->p[--s->n];
 102                 unsigned parent = (e->ev_timeout_pos.min_heap_idx - 1) / 2;
 103                 /* we replace e with the last element in the heap.  We might need to
 104                    shift it upward if it is less than its parent, or downward if it is
 105                    greater than one or both its children. Since the children are known
 106                    to be less than the parent, it can't need to shift both up and
 107                    down. */
 108                 if (e->ev_timeout_pos.min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last))
 109                         min_heap_shift_up_(s, e->ev_timeout_pos.min_heap_idx, last);
 110                 else
 111                         min_heap_shift_down_(s, e->ev_timeout_pos.min_heap_idx, last);
 112                 e->ev_timeout_pos.min_heap_idx = -1;
 113                 return 0;
 114         }
 115         return -1;
 116 }
 117
 118 static inline int min_heap_reserve(min_heap_t* s, unsigned n)
 119 {
 120         if (s->a < n)
 121         {
 122                 struct event** p;
 123                 unsigned a = s->a ? s->a * 2 : 8;
 124                 if (a < n)
 125                         a = n;
 126                 if (!(p = (struct event**)mm_realloc(s->p, a * sizeof *p)))
 127                         return -1;
 128                 s->p = p;
 129                 s->a = a;
 130         }
 131         return 0;
 132 }
 133
 134 static inline void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e)
 135 {
 136     unsigned parent = (hole_index - 1) / 2;
 137     while (hole_index && min_heap_elem_greater(s->p[parent], e))
 138     {
 139         (s->p[hole_index] = s->p[parent])->ev_timeout_pos.min_heap_idx = hole_index;
 140         hole_index = parent;
 141         parent = (hole_index - 1) / 2;
 142     }
 143     (s->p[hole_index] = e)->ev_timeout_pos.min_heap_idx = hole_index;
 144 }
 145
 146 static inline void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e)
 147 {
 148     unsigned min_child = 2 * (hole_index + 1);
 149     while (min_child <= s->n)
 150         {
 151         min_child -= min_child == s->n || min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]);
 152         if (!(min_heap_elem_greater(e, s->p[min_child])))
 153             break;
 154         (s->p[hole_index] = s->p[min_child])->ev_timeout_pos.min_heap_idx = hole_index;
 155         hole_index = min_child;
 156         min_child = 2 * (hole_index + 1);
 157         }
 158     (s->p[hole_index] = e)->ev_timeout_pos.min_heap_idx = hole_index;
 159 }
 160
 161 #endif /* _MIN_HEAP_H_ */