Tor  0.4.6.0-alpha-dev
bench-heap.c
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 <stdlib.h>
31 #include <err.h>
32 #include "timeout.h"
33 #include "bench.h"
34 
35 #define min_heap_idx interval
36 
37 typedef timeout_t min_heap_idx_t;
38 
39 typedef struct min_heap
40 {
41  struct timeout** p;
42  unsigned n, a;
43  timeout_t curtime;
44 } min_heap_t;
45 
46 static inline void min_heap_ctor(min_heap_t* s);
47 static inline void min_heap_dtor(min_heap_t* s);
48 static inline void min_heap_elem_init(struct timeout* e);
49 static inline int min_heap_elem_greater(struct timeout *a, struct timeout *b);
50 static inline int min_heap_empty(min_heap_t* s);
51 static inline unsigned min_heap_size(min_heap_t* s);
52 static inline struct timeout* min_heap_top(min_heap_t* s);
53 static inline int min_heap_reserve(min_heap_t* s, unsigned n);
54 static inline int min_heap_push(min_heap_t* s, struct timeout* e);
55 static inline struct timeout* min_heap_pop(min_heap_t* s);
56 static inline int min_heap_erase(min_heap_t* s, struct timeout* e);
57 static inline void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct timeout* e);
58 static inline void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct timeout* e);
59 
60 int min_heap_elem_greater(struct timeout *a, struct timeout *b)
61 {
62  return a->expires > b->expires;
63 }
64 
65 void min_heap_ctor(min_heap_t* s) { s->p = 0; s->n = 0; s->a = 0; }
66 void min_heap_dtor(min_heap_t* s) { if(s->p) free(s->p); }
67 void min_heap_elem_init(struct timeout* e) { e->min_heap_idx = -1; }
68 int min_heap_empty(min_heap_t* s) { return 0u == s->n; }
69 unsigned min_heap_size(min_heap_t* s) { return s->n; }
70 struct timeout* min_heap_top(min_heap_t* s) { return s->n ? *s->p : 0; }
71 
72 int min_heap_push(min_heap_t* s, struct timeout* e)
73 {
74  if(min_heap_reserve(s, s->n + 1))
75  return -1;
76  min_heap_shift_up_(s, s->n++, e);
77  return 0;
78 }
79 
80 struct timeout* min_heap_pop(min_heap_t* s)
81 {
82  if(s->n)
83  {
84  struct timeout* e = *s->p;
85  min_heap_shift_down_(s, 0u, s->p[--s->n]);
86  e->min_heap_idx = -1;
87  return e;
88  }
89  return 0;
90 }
91 
92 int min_heap_erase(min_heap_t* s, struct timeout* e)
93 {
94  if(((min_heap_idx_t)-1) != e->min_heap_idx)
95  {
96  struct timeout *last = s->p[--s->n];
97  unsigned parent = (e->min_heap_idx - 1) / 2;
98  /* we replace e with the last element in the heap. We might need to
99  shift it upward if it is less than its parent, or downward if it is
100  greater than one or both its children. Since the children are known
101  to be less than the parent, it can't need to shift both up and
102  down. */
103  if (e->min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last))
104  min_heap_shift_up_(s, e->min_heap_idx, last);
105  else
106  min_heap_shift_down_(s, e->min_heap_idx, last);
107  e->min_heap_idx = -1;
108  return 0;
109  }
110  return -1;
111 }
112 
113 int min_heap_reserve(min_heap_t* s, unsigned n)
114 {
115  if(s->a < n)
116  {
117  struct timeout** p;
118  unsigned a = s->a ? s->a * 2 : 8;
119  if(a < n)
120  a = n;
121  if(!(p = (struct timeout**)realloc(s->p, a * sizeof *p)))
122  return -1;
123  s->p = p;
124  s->a = a;
125  }
126  return 0;
127 }
128 
129 void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct timeout* e)
130 {
131  unsigned parent = (hole_index - 1) / 2;
132  while(hole_index && min_heap_elem_greater(s->p[parent], e))
133  {
134  (s->p[hole_index] = s->p[parent])->min_heap_idx = hole_index;
135  hole_index = parent;
136  parent = (hole_index - 1) / 2;
137  }
138  (s->p[hole_index] = e)->min_heap_idx = hole_index;
139 }
140 
141 void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct timeout* e)
142 {
143  unsigned min_child = 2 * (hole_index + 1);
144  while(min_child <= s->n)
145  {
146  min_child -= min_child == s->n || min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]);
147  if(!(min_heap_elem_greater(e, s->p[min_child])))
148  break;
149  (s->p[hole_index] = s->p[min_child])->min_heap_idx = hole_index;
150  hole_index = min_child;
151  min_child = 2 * (hole_index + 1);
152  }
153  min_heap_shift_up_(s, hole_index, e);
154 }
155 
156 #endif /* _MIN_HEAP_H_ */
157 
158 
159 static void *init(struct timeout *timeout, size_t count, int verbose) {
160  min_heap_t *H;
161  size_t i;
162 
163  H = calloc(1, sizeof *H);
164 
165  min_heap_ctor(H);
166  if (0 != min_heap_reserve(H, count))
167  err(1, "realloc");
168 
169  for (i = 0; i < count; i++) {
170  min_heap_elem_init(&timeout[i]);
171  }
172 
173  return H;
174 } /* init() */
175 
176 
177 static void add(void *ctx, struct timeout *to, timeout_t expires) {
178  min_heap_t *H = ctx;
179  min_heap_erase(H, to);
180  to->expires = H->curtime + expires;
181  if (0 != min_heap_push(H, to))
182  err(1, "realloc");
183 } /* add() */
184 
185 
186 static void del(void *ctx, struct timeout *to) {
187  min_heap_erase(ctx, to);
188 } /* del() */
189 
190 
191 static struct timeout *get(void *ctx) {
192  min_heap_t *H = ctx;
193  struct timeout *to;
194 
195  if ((to = min_heap_top(H)) && to->expires <= H->curtime)
196  return min_heap_pop(H);
197 
198  return NULL;
199 } /* get() */
200 
201 
202 static void update(void *ctx, timeout_t ts) {
203  min_heap_t *H = ctx;
204  H->curtime = ts;
205 } /* update() */
206 
207 
208 static void check(void *ctx) {
209  return;
210 } /* check() */
211 
212 
213 static int empty(void *ctx) {
214  min_heap_t *H = ctx;
215 
216  return (NULL == min_heap_top(H));
217 } /* empty() */
218 
219 
220 static void destroy(void *H) {
221  free(H);
222  return;
223 } /* destroy() */
224 
225 
226 const struct benchops benchops = {
227  .init = &init,
228  .add = &add,
229  .del = &del,
230  .get = &get,
231  .update = &update,
232  .check = &check,
233  .empty = &empty,
234  .destroy = &destroy,
235 };
236 
timeout
Definition: timeout.h:115
benchops
Definition: bench.h:1
min_heap_t
Definition: bench-heap.c:40