Tor  0.4.6.0-alpha-dev
bench-llrb.c
1 /* ==========================================================================
2  * llrb.h - Iterative Left-leaning Red-Black Tree.
3  * --------------------------------------------------------------------------
4  * Copyright (c) 2011, 2013 William Ahern <william@25thandClement.com>
5  *
6  * Permission is hereby granted, free of charge, to any person obtaining a
7  * copy of this software and associated documentation files (the
8  * "Software"), to deal in the Software without restriction, including
9  * without limitation the rights to use, copy, modify, merge, publish,
10  * distribute, sublicense, and/or sell copies of the Software, and to permit
11  * persons to whom the Software is furnished to do so, subject to the
12  * following conditions:
13  *
14  * The above copyright notice and this permission notice shall be included
15  * in all copies or substantial portions of the Software.
16  *
17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
18  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
19  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN
20  * NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
21  * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
22  * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
23  * USE OR OTHER DEALINGS IN THE SOFTWARE.
24  * --------------------------------------------------------------------------
25  * CREDITS:
26  * o Algorithm courtesy of Robert Sedgewick, "Left-leaning Red-Black
27  * Trees" (September 2008); and Robert Sedgewick and Kevin Wayne,
28  * Algorithms (4th ed. 2011).
29  *
30  * Sedgewick touts the simplicity of the recursive implementation,
31  * but at least for the 2-3 tree variant the iterative approach is
32  * almost line-for-line identical. The magic of C pointers helps;
33  * it'd be uglier with Java.
34  *
35  * A couple of missing NULL checks were added to Sedgewick's deletion
36  * example, and insert was optimized to short-circuit rotations when
37  * walking up the tree.
38  *
39  * o Code implemented in the fashion of Niels Provos' excellent *BSD
40  * sys/tree.h pre-processor library.
41  *
42  * Regarding relative performance, I've refrained from sharing my own
43  * benchmarks. Differences in run-time speed were too correlated to
44  * compiler options and other external factors.
45  *
46  * Provos' delete implementation doesn't need to start at the root of
47  * the tree. However, RB_REMOVE must be passed the actual node to be
48  * removed. LLRB_REMOVE merely requires a key, much like
49  * RB_FIND/LLRB_FIND.
50  * ==========================================================================
51  */
52 #ifndef LLRB_H
53 #define LLRB_H
54 
55 #define LLRB_VENDOR "william@25thandClement.com"
56 #define LLRB_VERSION 0x20130925
57 
58 #ifndef LLRB_STATIC
59 #ifdef __GNUC__
60 #define LLRB_STATIC __attribute__((__unused__)) static
61 #else
62 #define LLRB_STATIC static
63 #endif
64 #endif
65 
66 #define LLRB_HEAD(name, type) \
67 struct name { struct type *rbh_root; }
68 
69 #define LLRB_INITIALIZER(root) { 0 }
70 
71 #define LLRB_INIT(root) do { (root)->rbh_root = 0; } while (0)
72 
73 #define LLRB_BLACK 0
74 #define LLRB_RED 1
75 
76 #define LLRB_ENTRY(type) \
77 struct { struct type *rbe_left, *rbe_right, *rbe_parent; _Bool rbe_color; }
78 
79 #define LLRB_LEFT(elm, field) (elm)->field.rbe_left
80 #define LLRB_RIGHT(elm, field) (elm)->field.rbe_right
81 #define LLRB_PARENT(elm, field) (elm)->field.rbe_parent
82 #define LLRB_EDGE(head, elm, field) (((elm) == LLRB_ROOT(head))? &LLRB_ROOT(head) : ((elm) == LLRB_LEFT(LLRB_PARENT((elm), field), field))? &LLRB_LEFT(LLRB_PARENT((elm), field), field) : &LLRB_RIGHT(LLRB_PARENT((elm), field), field))
83 #define LLRB_COLOR(elm, field) (elm)->field.rbe_color
84 #define LLRB_ROOT(head) (head)->rbh_root
85 #define LLRB_EMPTY(head) ((head)->rbh_root == 0)
86 #define LLRB_ISRED(elm, field) ((elm) && LLRB_COLOR((elm), field) == LLRB_RED)
87 
88 #define LLRB_PROTOTYPE(name, type, field, cmp) \
89  LLRB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
90 #define LLRB_PROTOTYPE_STATIC(name, type, field, cmp) \
91  LLRB_PROTOTYPE_INTERNAL(name, type, field, cmp, LLRB_STATIC)
92 #define LLRB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
93 attr struct type *name##_LLRB_INSERT(struct name *, struct type *); \
94 attr struct type *name##_LLRB_DELETE(struct name *, struct type *); \
95 attr struct type *name##_LLRB_FIND(struct name *, struct type *); \
96 attr struct type *name##_LLRB_MIN(struct type *); \
97 attr struct type *name##_LLRB_MAX(struct type *); \
98 attr struct type *name##_LLRB_NEXT(struct type *);
99 
100 #define LLRB_GENERATE(name, type, field, cmp) \
101  LLRB_GENERATE_INTERNAL(name, type, field, cmp,)
102 #define LLRB_GENERATE_STATIC(name, type, field, cmp) \
103  LLRB_GENERATE_INTERNAL(name, type, field, cmp, LLRB_STATIC)
104 #define LLRB_GENERATE_INTERNAL(name, type, field, cmp, attr) \
105 static inline void name##_LLRB_ROTL(struct type **pivot) { \
106  struct type *a = *pivot; \
107  struct type *b = LLRB_RIGHT(a, field); \
108  if ((LLRB_RIGHT(a, field) = LLRB_LEFT(b, field))) \
109  LLRB_PARENT(LLRB_RIGHT(a, field), field) = a; \
110  LLRB_LEFT(b, field) = a; \
111  LLRB_COLOR(b, field) = LLRB_COLOR(a, field); \
112  LLRB_COLOR(a, field) = LLRB_RED; \
113  LLRB_PARENT(b, field) = LLRB_PARENT(a, field); \
114  LLRB_PARENT(a, field) = b; \
115  *pivot = b; \
116 } \
117 static inline void name##_LLRB_ROTR(struct type **pivot) { \
118  struct type *b = *pivot; \
119  struct type *a = LLRB_LEFT(b, field); \
120  if ((LLRB_LEFT(b, field) = LLRB_RIGHT(a, field))) \
121  LLRB_PARENT(LLRB_LEFT(b, field), field) = b; \
122  LLRB_RIGHT(a, field) = b; \
123  LLRB_COLOR(a, field) = LLRB_COLOR(b, field); \
124  LLRB_COLOR(b, field) = LLRB_RED; \
125  LLRB_PARENT(a, field) = LLRB_PARENT(b, field); \
126  LLRB_PARENT(b, field) = a; \
127  *pivot = a; \
128 } \
129 static inline void name##_LLRB_FLIP(struct type *root) { \
130  LLRB_COLOR(root, field) = !LLRB_COLOR(root, field); \
131  LLRB_COLOR(LLRB_LEFT(root, field), field) = !LLRB_COLOR(LLRB_LEFT(root, field), field); \
132  LLRB_COLOR(LLRB_RIGHT(root, field), field) = !LLRB_COLOR(LLRB_RIGHT(root, field), field); \
133 } \
134 static inline void name##_LLRB_FIXUP(struct type **root) { \
135  if (LLRB_ISRED(LLRB_RIGHT(*root, field), field) && !LLRB_ISRED(LLRB_LEFT(*root, field), field)) \
136  name##_LLRB_ROTL(root); \
137  if (LLRB_ISRED(LLRB_LEFT(*root, field), field) && LLRB_ISRED(LLRB_LEFT(LLRB_LEFT(*root, field), field), field)) \
138  name##_LLRB_ROTR(root); \
139  if (LLRB_ISRED(LLRB_LEFT(*root, field), field) && LLRB_ISRED(LLRB_RIGHT(*root, field), field)) \
140  name##_LLRB_FLIP(*root); \
141 } \
142 attr struct type *name##_LLRB_INSERT(struct name *head, struct type *elm) { \
143  struct type **root = &LLRB_ROOT(head); \
144  struct type *parent = 0; \
145  while (*root) { \
146  int comp = (cmp)((elm), (*root)); \
147  parent = *root; \
148  if (comp < 0) \
149  root = &LLRB_LEFT(*root, field); \
150  else if (comp > 0) \
151  root = &LLRB_RIGHT(*root, field); \
152  else \
153  return *root; \
154  } \
155  LLRB_LEFT((elm), field) = 0; \
156  LLRB_RIGHT((elm), field) = 0; \
157  LLRB_COLOR((elm), field) = LLRB_RED; \
158  LLRB_PARENT((elm), field) = parent; \
159  *root = (elm); \
160  while (parent && (LLRB_ISRED(LLRB_LEFT(parent, field), field) || LLRB_ISRED(LLRB_RIGHT(parent, field), field))) { \
161  root = LLRB_EDGE(head, parent, field); \
162  parent = LLRB_PARENT(parent, field); \
163  name##_LLRB_FIXUP(root); \
164  } \
165  LLRB_COLOR(LLRB_ROOT(head), field) = LLRB_BLACK; \
166  return 0; \
167 } \
168 static inline void name##_LLRB_MOVL(struct type **pivot) { \
169  name##_LLRB_FLIP(*pivot); \
170  if (LLRB_ISRED(LLRB_LEFT(LLRB_RIGHT(*pivot, field), field), field)) { \
171  name##_LLRB_ROTR(&LLRB_RIGHT(*pivot, field)); \
172  name##_LLRB_ROTL(pivot); \
173  name##_LLRB_FLIP(*pivot); \
174  } \
175 } \
176 static inline void name##_LLRB_MOVR(struct type **pivot) { \
177  name##_LLRB_FLIP(*pivot); \
178  if (LLRB_ISRED(LLRB_LEFT(LLRB_LEFT(*pivot, field), field), field)) { \
179  name##_LLRB_ROTR(pivot); \
180  name##_LLRB_FLIP(*pivot); \
181  } \
182 } \
183 static inline struct type *name##_DELETEMIN(struct name *head, struct type **root) { \
184  struct type **pivot = root, *deleted, *parent; \
185  while (LLRB_LEFT(*pivot, field)) { \
186  if (!LLRB_ISRED(LLRB_LEFT(*pivot, field), field) && !LLRB_ISRED(LLRB_LEFT(LLRB_LEFT(*pivot, field), field), field)) \
187  name##_LLRB_MOVL(pivot); \
188  pivot = &LLRB_LEFT(*pivot, field); \
189  } \
190  deleted = *pivot; \
191  parent = LLRB_PARENT(*pivot, field); \
192  *pivot = 0; \
193  while (root != pivot) { \
194  pivot = LLRB_EDGE(head, parent, field); \
195  parent = LLRB_PARENT(parent, field); \
196  name##_LLRB_FIXUP(pivot); \
197  } \
198  return deleted; \
199 } \
200 attr struct type *name##_LLRB_DELETE(struct name *head, struct type *elm) { \
201  struct type **root = &LLRB_ROOT(head), *parent = 0, *deleted = 0; \
202  int comp; \
203  while (*root) { \
204  parent = LLRB_PARENT(*root, field); \
205  comp = (cmp)(elm, *root); \
206  if (comp < 0) { \
207  if (LLRB_LEFT(*root, field) && !LLRB_ISRED(LLRB_LEFT(*root, field), field) && !LLRB_ISRED(LLRB_LEFT(LLRB_LEFT(*root, field), field), field)) \
208  name##_LLRB_MOVL(root); \
209  root = &LLRB_LEFT(*root, field); \
210  } else { \
211  if (LLRB_ISRED(LLRB_LEFT(*root, field), field)) { \
212  name##_LLRB_ROTR(root); \
213  comp = (cmp)(elm, *root); \
214  } \
215  if (!comp && !LLRB_RIGHT(*root, field)) { \
216  deleted = *root; \
217  *root = 0; \
218  break; \
219  } \
220  if (LLRB_RIGHT(*root, field) && !LLRB_ISRED(LLRB_RIGHT(*root, field), field) && !LLRB_ISRED(LLRB_LEFT(LLRB_RIGHT(*root, field), field), field)) { \
221  name##_LLRB_MOVR(root); \
222  comp = (cmp)(elm, *root); \
223  } \
224  if (!comp) { \
225  struct type *orphan = name##_DELETEMIN(head, &LLRB_RIGHT(*root, field)); \
226  LLRB_COLOR(orphan, field) = LLRB_COLOR(*root, field); \
227  LLRB_PARENT(orphan, field) = LLRB_PARENT(*root, field); \
228  if ((LLRB_RIGHT(orphan, field) = LLRB_RIGHT(*root, field))) \
229  LLRB_PARENT(LLRB_RIGHT(orphan, field), field) = orphan; \
230  if ((LLRB_LEFT(orphan, field) = LLRB_LEFT(*root, field))) \
231  LLRB_PARENT(LLRB_LEFT(orphan, field), field) = orphan; \
232  deleted = *root; \
233  *root = orphan; \
234  parent = *root; \
235  break; \
236  } else \
237  root = &LLRB_RIGHT(*root, field); \
238  } \
239  } \
240  while (parent) { \
241  root = LLRB_EDGE(head, parent, field); \
242  parent = LLRB_PARENT(parent, field); \
243  name##_LLRB_FIXUP(root); \
244  } \
245  if (LLRB_ROOT(head)) \
246  LLRB_COLOR(LLRB_ROOT(head), field) = LLRB_BLACK; \
247  return deleted; \
248 } \
249 attr struct type *name##_LLRB_FIND(struct name *head, struct type *key) { \
250  struct type *elm = LLRB_ROOT(head); \
251  while (elm) { \
252  int comp = (cmp)(key, elm); \
253  if (comp < 0) \
254  elm = LLRB_LEFT(elm, field); \
255  else if (comp > 0) \
256  elm = LLRB_RIGHT(elm, field); \
257  else \
258  return elm; \
259  } \
260  return 0; \
261 } \
262 attr struct type *name##_LLRB_MIN(struct type *elm) { \
263  while (elm && LLRB_LEFT(elm, field)) \
264  elm = LLRB_LEFT(elm, field); \
265  return elm; \
266 } \
267 attr struct type *name##_LLRB_MAX(struct type *elm) { \
268  while (elm && LLRB_RIGHT(elm, field)) \
269  elm = LLRB_RIGHT(elm, field); \
270  return elm; \
271 } \
272 attr struct type *name##_LLRB_NEXT(struct type *elm) { \
273  if (LLRB_RIGHT(elm, field)) { \
274  return name##_LLRB_MIN(LLRB_RIGHT(elm, field)); \
275  } else if (LLRB_PARENT(elm, field)) { \
276  if (elm == LLRB_LEFT(LLRB_PARENT(elm, field), field)) \
277  return LLRB_PARENT(elm, field); \
278  while (LLRB_PARENT(elm, field) && elm == LLRB_RIGHT(LLRB_PARENT(elm, field), field)) \
279  elm = LLRB_PARENT(elm, field); \
280  return LLRB_PARENT(elm, field); \
281  } else return 0; \
282 }
283 
284 #define LLRB_INSERT(name, head, elm) name##_LLRB_INSERT((head), (elm))
285 #define LLRB_DELETE(name, head, elm) name##_LLRB_DELETE((head), (elm))
286 #define LLRB_REMOVE(name, head, elm) name##_LLRB_DELETE((head), (elm))
287 #define LLRB_FIND(name, head, elm) name##_LLRB_FIND((head), (elm))
288 #define LLRB_MIN(name, head) name##_LLRB_MIN(LLRB_ROOT((head)))
289 #define LLRB_MAX(name, head) name##_LLRB_MAX(LLRB_ROOT((head)))
290 #define LLRB_NEXT(name, head, elm) name##_LLRB_NEXT((elm))
291 
292 #define LLRB_FOREACH(elm, name, head) \
293 for ((elm) = LLRB_MIN(name, head); (elm); (elm) = name##_LLRB_NEXT((elm)))
294 
295 #endif /* LLRB_H */
296 
297 
298 #include <stdlib.h>
299 
300 #include "timeout.h"
301 #include "bench.h"
302 
303 
304 struct rbtimeout {
305  timeout_t expires;
306 
307  int pending;
308 
309  LLRB_ENTRY(rbtimeout) rbe;
310 };
311 
312 struct rbtimeouts {
313  timeout_t curtime;
314  LLRB_HEAD(tree, rbtimeout) tree;
315 };
316 
317 
318 static int timeoutcmp(struct rbtimeout *a, struct rbtimeout *b) {
319  if (a->expires < b->expires) {
320  return -1;
321  } else if (a->expires > b->expires) {
322  return 1;
323  } else if (a < b) {
324  return -1;
325  } else if (a > b) {
326  return 1;
327  } else {
328  return 0;
329  }
330 } /* timeoutcmp() */
331 
332 LLRB_GENERATE_STATIC(tree, rbtimeout, rbe, timeoutcmp)
333 
334 static void *init(struct timeout *timeout, size_t count, int verbose) {
335  struct rbtimeouts *T;
336  size_t i;
337 
338  T = malloc(sizeof *T);
339  T->curtime = 0;
340  LLRB_INIT(&T->tree);
341 
342  for (i = 0; i < count; i++) {
343  struct rbtimeout *to = (void *)&timeout[i];
344  to->expires = 0;
345  to->pending = 0;
346  }
347 
348  return T;
349 } /* init() */
350 
351 
352 static void add(void *ctx, struct timeout *_to, timeout_t expires) {
353  struct rbtimeouts *T = ctx;
354  struct rbtimeout *to = (void *)_to;
355 
356  if (to->pending)
357  LLRB_REMOVE(tree, &T->tree, to);
358 
359  to->expires = T->curtime + expires;
360  LLRB_INSERT(tree, &T->tree, to);
361  to->pending = 1;
362 } /* add() */
363 
364 
365 static void del(void *ctx, struct timeout *_to) {
366  struct rbtimeouts *T = ctx;
367  struct rbtimeout *to = (void *)_to;
368 
369  LLRB_REMOVE(tree, &T->tree, to);
370  to->pending = 0;
371  to->expires = 0;
372 } /* del() */
373 
374 
375 static struct timeout *get(void *ctx) {
376  struct rbtimeouts *T = ctx;
377  struct rbtimeout *to;
378 
379  if ((to = LLRB_MIN(tree, &T->tree)) && to->expires <= T->curtime) {
380  LLRB_REMOVE(tree, &T->tree, to);
381  to->pending = 0;
382  to->expires = 0;
383 
384  return (void *)to;
385  }
386 
387  return NULL;
388 } /* get() */
389 
390 
391 static void update(void *ctx, timeout_t ts) {
392  struct rbtimeouts *T = ctx;
393  T->curtime = ts;
394 } /* update() */
395 
396 
397 static void check(void *ctx) {
398  return;
399 } /* check() */
400 
401 
402 static int empty(void *ctx) {
403  struct rbtimeouts *T = ctx;
404 
405  return LLRB_EMPTY(&T->tree);
406 } /* empty() */
407 
408 
409 static void destroy(void *ctx) {
410  free(ctx);
411  return;
412 } /* destroy() */
413 
414 
415 const struct benchops benchops = {
416  .init = &init,
417  .add = &add,
418  .del = &del,
419  .get = &get,
420  .update = &update,
421  .check = &check,
422  .empty = &empty,
423  .destroy = &destroy,
424 };
425 
T
#define T(s, t, a, o)
Definition: parsecommon.h:246
rbtimeout
Definition: bench-llrb.c:304
timeout
Definition: timeout.h:115
benchops
Definition: bench.h:1
rbtimeouts
Definition: bench-llrb.c:312