The Tor Browser / file comparison
comparison: ipc/chromium/src/third_party/libevent/minheap-internal.h
ipc/chromium/src/third_party/libevent/minheap-internal.h
- changeset 0
- 6474c204b198
equal
deleted
inserted
replaced
| -1:000000000000 | 0:d676a4c9f7b5 |
|---|---|
| 1 /* | |
| 2 * Copyright (c) 2007-2012 Niels Provos and Nick Mathewson | |
| 3 * | |
| 4 * Copyright (c) 2006 Maxim Yegorushkin <maxim.yegorushkin@gmail.com> | |
| 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 "event2/event-config.h" | |
| 32 #include "event2/event.h" | |
| 33 #include "event2/event_struct.h" | |
| 34 #include "event2/util.h" | |
| 35 #include "util-internal.h" | |
| 36 #include "mm-internal.h" | |
| 37 | |
| 38 typedef struct min_heap | |
| 39 { | |
| 40 struct event** p; | |
| 41 unsigned n, a; | |
| 42 } min_heap_t; | |
| 43 | |
| 44 static inline void min_heap_ctor(min_heap_t* s); | |
| 45 static inline void min_heap_dtor(min_heap_t* s); | |
| 46 static inline void min_heap_elem_init(struct event* e); | |
| 47 static inline int min_heap_elt_is_top(const struct event *e); | |
| 48 static inline int min_heap_elem_greater(struct event *a, struct event *b); | |
| 49 static inline int min_heap_empty(min_heap_t* s); | |
| 50 static inline unsigned min_heap_size(min_heap_t* s); | |
| 51 static inline struct event* min_heap_top(min_heap_t* s); | |
| 52 static inline int min_heap_reserve(min_heap_t* s, unsigned n); | |
| 53 static inline int min_heap_push(min_heap_t* s, struct event* e); | |
| 54 static inline struct event* min_heap_pop(min_heap_t* s); | |
| 55 static inline int min_heap_erase(min_heap_t* s, struct event* e); | |
| 56 static inline void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e); | |
| 57 static inline void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e); | |
| 58 | |
| 59 int min_heap_elem_greater(struct event *a, struct event *b) | |
| 60 { | |
| 61 return evutil_timercmp(&a->ev_timeout, &b->ev_timeout, >); | |
| 62 } | |
| 63 | |
| 64 void min_heap_ctor(min_heap_t* s) { s->p = 0; s->n = 0; s->a = 0; } | |
| 65 void min_heap_dtor(min_heap_t* s) { if (s->p) mm_free(s->p); } | |
| 66 void min_heap_elem_init(struct event* e) { e->ev_timeout_pos.min_heap_idx = -1; } | |
| 67 int min_heap_empty(min_heap_t* s) { return 0u == s->n; } | |
| 68 unsigned min_heap_size(min_heap_t* s) { return s->n; } | |
| 69 struct event* min_heap_top(min_heap_t* s) { return s->n ? *s->p : 0; } | |
| 70 | |
| 71 int min_heap_push(min_heap_t* s, struct event* e) | |
| 72 { | |
| 73 if (min_heap_reserve(s, s->n + 1)) | |
| 74 return -1; | |
| 75 min_heap_shift_up_(s, s->n++, e); | |
| 76 return 0; | |
| 77 } | |
| 78 | |
| 79 struct event* min_heap_pop(min_heap_t* s) | |
| 80 { | |
| 81 if (s->n) | |
| 82 { | |
| 83 struct event* e = *s->p; | |
| 84 min_heap_shift_down_(s, 0u, s->p[--s->n]); | |
| 85 e->ev_timeout_pos.min_heap_idx = -1; | |
| 86 return e; | |
| 87 } | |
| 88 return 0; | |
| 89 } | |
| 90 | |
| 91 int min_heap_elt_is_top(const struct event *e) | |
| 92 { | |
| 93 return e->ev_timeout_pos.min_heap_idx == 0; | |
| 94 } | |
| 95 | |
| 96 int min_heap_erase(min_heap_t* s, struct event* e) | |
| 97 { | |
| 98 if (-1 != e->ev_timeout_pos.min_heap_idx) | |
| 99 { | |
| 100 struct event *last = s->p[--s->n]; | |
| 101 unsigned parent = (e->ev_timeout_pos.min_heap_idx - 1) / 2; | |
| 102 /* we replace e with the last element in the heap. We might need to | |
| 103 shift it upward if it is less than its parent, or downward if it is | |
| 104 greater than one or both its children. Since the children are known | |
| 105 to be less than the parent, it can't need to shift both up and | |
| 106 down. */ | |
| 107 if (e->ev_timeout_pos.min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last)) | |
| 108 min_heap_shift_up_(s, e->ev_timeout_pos.min_heap_idx, last); | |
| 109 else | |
| 110 min_heap_shift_down_(s, e->ev_timeout_pos.min_heap_idx, last); | |
| 111 e->ev_timeout_pos.min_heap_idx = -1; | |
| 112 return 0; | |
| 113 } | |
| 114 return -1; | |
| 115 } | |
| 116 | |
| 117 int min_heap_reserve(min_heap_t* s, unsigned n) | |
| 118 { | |
| 119 if (s->a < n) | |
| 120 { | |
| 121 struct event** p; | |
| 122 unsigned a = s->a ? s->a * 2 : 8; | |
| 123 if (a < n) | |
| 124 a = n; | |
| 125 if (!(p = (struct event**)mm_realloc(s->p, a * sizeof *p))) | |
| 126 return -1; | |
| 127 s->p = p; | |
| 128 s->a = a; | |
| 129 } | |
| 130 return 0; | |
| 131 } | |
| 132 | |
| 133 void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e) | |
| 134 { | |
| 135 unsigned parent = (hole_index - 1) / 2; | |
| 136 while (hole_index && min_heap_elem_greater(s->p[parent], e)) | |
| 137 { | |
| 138 (s->p[hole_index] = s->p[parent])->ev_timeout_pos.min_heap_idx = hole_index; | |
| 139 hole_index = parent; | |
| 140 parent = (hole_index - 1) / 2; | |
| 141 } | |
| 142 (s->p[hole_index] = e)->ev_timeout_pos.min_heap_idx = hole_index; | |
| 143 } | |
| 144 | |
| 145 void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e) | |
| 146 { | |
| 147 unsigned min_child = 2 * (hole_index + 1); | |
| 148 while (min_child <= s->n) | |
| 149 { | |
| 150 min_child -= min_child == s->n || min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]); | |
| 151 if (!(min_heap_elem_greater(e, s->p[min_child]))) | |
| 152 break; | |
| 153 (s->p[hole_index] = s->p[min_child])->ev_timeout_pos.min_heap_idx = hole_index; | |
| 154 hole_index = min_child; | |
| 155 min_child = 2 * (hole_index + 1); | |
| 156 } | |
| 157 (s->p[hole_index] = e)->ev_timeout_pos.min_heap_idx = hole_index; | |
| 158 } | |
| 159 | |
| 160 #endif /* _MIN_HEAP_H_ */ |
