Return to min_heap.h CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / libevent

libevent

    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 "event.h"
   31: #include "evutil.h"
   32: 
   33: typedef struct min_heap
   34: {
   35:     struct event** p;
   36:     unsigned n, a;
   37: } min_heap_t;
   38: 
   39: static inline void           min_heap_ctor(min_heap_t* s);
   40: static inline void           min_heap_dtor(min_heap_t* s);
   41: static inline void           min_heap_elem_init(struct event* e);
   42: static inline int            min_heap_elem_greater(struct event *a, struct event *b);
   43: static inline int            min_heap_empty(min_heap_t* s);
   44: static inline unsigned       min_heap_size(min_heap_t* s);
   45: static inline struct event*  min_heap_top(min_heap_t* s);
   46: static inline int            min_heap_reserve(min_heap_t* s, unsigned n);
   47: static inline int            min_heap_push(min_heap_t* s, struct event* e);
   48: static inline struct event*  min_heap_pop(min_heap_t* s);
   49: static inline int            min_heap_erase(min_heap_t* s, struct event* e);
   50: static inline void           min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e);
   51: static inline void           min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e);
   52: 
   53: int min_heap_elem_greater(struct event *a, struct event *b)
   54: {
   55:     return evutil_timercmp(&a->ev_timeout, &b->ev_timeout, >);
   56: }
   57: 
   58: void min_heap_ctor(min_heap_t* s) { s->p = 0; s->n = 0; s->a = 0; }
   59: void min_heap_dtor(min_heap_t* s) { if(s->p) free(s->p); }
   60: void min_heap_elem_init(struct event* e) { e->min_heap_idx = -1; }
   61: int min_heap_empty(min_heap_t* s) { return 0u == s->n; }
   62: unsigned min_heap_size(min_heap_t* s) { return s->n; }
   63: struct event* min_heap_top(min_heap_t* s) { return s->n ? *s->p : 0; }
   64: 
   65: int min_heap_push(min_heap_t* s, struct event* e)
   66: {
   67:     if(min_heap_reserve(s, s->n + 1))
   68:         return -1;
   69:     min_heap_shift_up_(s, s->n++, e);
   70:     return 0;
   71: }
   72: 
   73: struct event* min_heap_pop(min_heap_t* s)
   74: {
   75:     if(s->n)
   76:     {
   77:         struct event* e = *s->p;
   78:         min_heap_shift_down_(s, 0u, s->p[--s->n]);
   79:         e->min_heap_idx = -1;
   80:         return e;
   81:     }
   82:     return 0;
   83: }
   84: 
   85: int min_heap_erase(min_heap_t* s, struct event* e)
   86: {
   87:     if(((unsigned int)-1) != e->min_heap_idx)
   88:     {
   89:         struct event *last = s->p[--s->n];
   90:         unsigned parent = (e->min_heap_idx - 1) / 2;
   91: 	/* we replace e with the last element in the heap.  We might need to
   92: 	   shift it upward if it is less than its parent, or downward if it is
   93: 	   greater than one or both its children. Since the children are known
   94: 	   to be less than the parent, it can't need to shift both up and
   95: 	   down. */
   96:         if (e->min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last))
   97:              min_heap_shift_up_(s, e->min_heap_idx, last);
   98:         else
   99:              min_heap_shift_down_(s, e->min_heap_idx, last);
  100:         e->min_heap_idx = -1;
  101:         return 0;
  102:     }
  103:     return -1;
  104: }
  105: 
  106: int min_heap_reserve(min_heap_t* s, unsigned n)
  107: {
  108:     if(s->a < n)
  109:     {
  110:         struct event** p;
  111:         unsigned a = s->a ? s->a * 2 : 8;
  112:         if(a < n)
  113:             a = n;
  114:         if(!(p = (struct event**)realloc(s->p, a * sizeof *p)))
  115:             return -1;
  116:         s->p = p;
  117:         s->a = a;
  118:     }
  119:     return 0;
  120: }
  121: 
  122: void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e)
  123: {
  124:     unsigned parent = (hole_index - 1) / 2;
  125:     while(hole_index && min_heap_elem_greater(s->p[parent], e))
  126:     {
  127:         (s->p[hole_index] = s->p[parent])->min_heap_idx = hole_index;
  128:         hole_index = parent;
  129:         parent = (hole_index - 1) / 2;
  130:     }
  131:     (s->p[hole_index] = e)->min_heap_idx = hole_index;
  132: }
  133: 
  134: void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e)
  135: {
  136:     unsigned min_child = 2 * (hole_index + 1);
  137:     while(min_child <= s->n)
  138: 	{
  139:         min_child -= min_child == s->n || min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]);
  140:         if(!(min_heap_elem_greater(e, s->p[min_child])))
  141:             break;
  142:         (s->p[hole_index] = s->p[min_child])->min_heap_idx = hole_index;
  143:         hole_index = min_child;
  144:         min_child = 2 * (hole_index + 1);
  145: 	}
  146:     min_heap_shift_up_(s, hole_index,  e);
  147: }
  148: 
  149: #endif /* _MIN_HEAP_H_ */