bench-llrb.c (14105B)
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 };