external/bsd/libevent/dist/min_heap.h

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