Annotation of embedaddon/libevent/min_heap.h, revision 1.1.1.1
1.1 misho 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_ */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to min_heap.h CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / libevent