The Tor Browser / annotate

ipc/chromium/src/third_party/libevent/minheap-internal.h@6474c204b198 (annotated)

ipc/chromium/src/third_party/libevent/minheap-internal.h

Wed, 31 Dec 2014 06:09:35 +0100

author
Michael Schloh von Bennewitz <michael@schloh.com>
date
Wed, 31 Dec 2014 06:09:35 +0100
changeset 0
6474c204b198
permissions
-rw-r--r--

Cloned upstream origin tor-browser at tor-browser-31.3.0esr-4.5-1-build1
revision ID fc1c9ff7c1b2defdbc039f12214767608f46423f for hacking purpose.

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

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial