]> git.saurik.com Git - redis.git/blame - deps/jemalloc.orig/include/jemalloc/internal/rb.h
projects / redis.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Jemalloc updated to 3.0.0.
[redis.git] / deps / jemalloc.orig / include / jemalloc / internal / rb.h
CommitLineData
4934f93d 1/*-
2 *******************************************************************************
3 *
4 * cpp macro implementation of left-leaning 2-3 red-black trees. Parent
5 * pointers are not used, and color bits are stored in the least significant
6 * bit of right-child pointers (if RB_COMPACT is defined), thus making node
7 * linkage as compact as is possible for red-black trees.
8 *
9 * Usage:
10 *
11 * #include <stdint.h>
12 * #include <stdbool.h>
13 * #define NDEBUG // (Optional, see assert(3).)
14 * #include <assert.h>
15 * #define RB_COMPACT // (Optional, embed color bits in right-child pointers.)
16 * #include <rb.h>
17 * ...
18 *
19 *******************************************************************************
20 */
21
22#ifndef RB_H_
23#define RB_H_
24
25#if 0
26__FBSDID("$FreeBSD: head/lib/libc/stdlib/rb.h 204493 2010-02-28 22:57:13Z jasone $");
27#endif
28
29#ifdef RB_COMPACT
30/* Node structure. */
31#define rb_node(a_type) \
32struct { \
33 a_type *rbn_left; \
34 a_type *rbn_right_red; \
35}
36#else
37#define rb_node(a_type) \
38struct { \
39 a_type *rbn_left; \
40 a_type *rbn_right; \
41 bool rbn_red; \
42}
43#endif
44
45/* Root structure. */
46#define rb_tree(a_type) \
47struct { \
48 a_type *rbt_root; \
49 a_type rbt_nil; \
50}
51
52/* Left accessors. */
53#define rbtn_left_get(a_type, a_field, a_node) \
54 ((a_node)->a_field.rbn_left)
55#define rbtn_left_set(a_type, a_field, a_node, a_left) do { \
56 (a_node)->a_field.rbn_left = a_left; \
57} while (0)
58
59#ifdef RB_COMPACT
60/* Right accessors. */
61#define rbtn_right_get(a_type, a_field, a_node) \
62 ((a_type *) (((intptr_t) (a_node)->a_field.rbn_right_red) \
63 & ((ssize_t)-2)))
64#define rbtn_right_set(a_type, a_field, a_node, a_right) do { \
65 (a_node)->a_field.rbn_right_red = (a_type *) (((uintptr_t) a_right) \
66 | (((uintptr_t) (a_node)->a_field.rbn_right_red) & ((size_t)1))); \
67} while (0)
68
69/* Color accessors. */
70#define rbtn_red_get(a_type, a_field, a_node) \
71 ((bool) (((uintptr_t) (a_node)->a_field.rbn_right_red) \
72 & ((size_t)1)))
73#define rbtn_color_set(a_type, a_field, a_node, a_red) do { \
74 (a_node)->a_field.rbn_right_red = (a_type *) ((((intptr_t) \
75 (a_node)->a_field.rbn_right_red) & ((ssize_t)-2)) \
76 | ((ssize_t)a_red)); \
77} while (0)
78#define rbtn_red_set(a_type, a_field, a_node) do { \
79 (a_node)->a_field.rbn_right_red = (a_type *) (((uintptr_t) \
80 (a_node)->a_field.rbn_right_red) | ((size_t)1)); \
81} while (0)
82#define rbtn_black_set(a_type, a_field, a_node) do { \
83 (a_node)->a_field.rbn_right_red = (a_type *) (((intptr_t) \
84 (a_node)->a_field.rbn_right_red) & ((ssize_t)-2)); \
85} while (0)
86#else
87/* Right accessors. */
88#define rbtn_right_get(a_type, a_field, a_node) \
89 ((a_node)->a_field.rbn_right)
90#define rbtn_right_set(a_type, a_field, a_node, a_right) do { \
91 (a_node)->a_field.rbn_right = a_right; \
92} while (0)
93
94/* Color accessors. */
95#define rbtn_red_get(a_type, a_field, a_node) \
96 ((a_node)->a_field.rbn_red)
97#define rbtn_color_set(a_type, a_field, a_node, a_red) do { \
98 (a_node)->a_field.rbn_red = (a_red); \
99} while (0)
100#define rbtn_red_set(a_type, a_field, a_node) do { \
101 (a_node)->a_field.rbn_red = true; \
102} while (0)
103#define rbtn_black_set(a_type, a_field, a_node) do { \
104 (a_node)->a_field.rbn_red = false; \
105} while (0)
106#endif
107
108/* Node initializer. */
109#define rbt_node_new(a_type, a_field, a_rbt, a_node) do { \
110 rbtn_left_set(a_type, a_field, (a_node), &(a_rbt)->rbt_nil); \
111 rbtn_right_set(a_type, a_field, (a_node), &(a_rbt)->rbt_nil); \
112 rbtn_red_set(a_type, a_field, (a_node)); \
113} while (0)
114
115/* Tree initializer. */
116#define rb_new(a_type, a_field, a_rbt) do { \
117 (a_rbt)->rbt_root = &(a_rbt)->rbt_nil; \
118 rbt_node_new(a_type, a_field, a_rbt, &(a_rbt)->rbt_nil); \
119 rbtn_black_set(a_type, a_field, &(a_rbt)->rbt_nil); \
120} while (0)
121
122/* Internal utility macros. */
123#define rbtn_first(a_type, a_field, a_rbt, a_root, r_node) do { \
124 (r_node) = (a_root); \
125 if ((r_node) != &(a_rbt)->rbt_nil) { \
126 for (; \
127 rbtn_left_get(a_type, a_field, (r_node)) != &(a_rbt)->rbt_nil;\
128 (r_node) = rbtn_left_get(a_type, a_field, (r_node))) { \
129 } \
130 } \
131} while (0)
132
133#define rbtn_last(a_type, a_field, a_rbt, a_root, r_node) do { \
134 (r_node) = (a_root); \
135 if ((r_node) != &(a_rbt)->rbt_nil) { \
136 for (; rbtn_right_get(a_type, a_field, (r_node)) != \
137 &(a_rbt)->rbt_nil; (r_node) = rbtn_right_get(a_type, a_field, \
138 (r_node))) { \
139 } \
140 } \
141} while (0)
142
143#define rbtn_rotate_left(a_type, a_field, a_node, r_node) do { \
144 (r_node) = rbtn_right_get(a_type, a_field, (a_node)); \
145 rbtn_right_set(a_type, a_field, (a_node), \
146 rbtn_left_get(a_type, a_field, (r_node))); \
147 rbtn_left_set(a_type, a_field, (r_node), (a_node)); \
148} while (0)
149
150#define rbtn_rotate_right(a_type, a_field, a_node, r_node) do { \
151 (r_node) = rbtn_left_get(a_type, a_field, (a_node)); \
152 rbtn_left_set(a_type, a_field, (a_node), \
153 rbtn_right_get(a_type, a_field, (r_node))); \
154 rbtn_right_set(a_type, a_field, (r_node), (a_node)); \
155} while (0)
156
157/*
158 * The rb_proto() macro generates function prototypes that correspond to the
159 * functions generated by an equivalently parameterized call to rb_gen().
160 */
161
162#define rb_proto(a_attr, a_prefix, a_rbt_type, a_type) \
163a_attr void \
164a_prefix##new(a_rbt_type *rbtree); \
165a_attr a_type * \
166a_prefix##first(a_rbt_type *rbtree); \
167a_attr a_type * \
168a_prefix##last(a_rbt_type *rbtree); \
169a_attr a_type * \
170a_prefix##next(a_rbt_type *rbtree, a_type *node); \
171a_attr a_type * \
172a_prefix##prev(a_rbt_type *rbtree, a_type *node); \
173a_attr a_type * \
174a_prefix##search(a_rbt_type *rbtree, a_type *key); \
175a_attr a_type * \
176a_prefix##nsearch(a_rbt_type *rbtree, a_type *key); \
177a_attr a_type * \
178a_prefix##psearch(a_rbt_type *rbtree, a_type *key); \
179a_attr void \
180a_prefix##insert(a_rbt_type *rbtree, a_type *node); \
181a_attr void \
182a_prefix##remove(a_rbt_type *rbtree, a_type *node); \
183a_attr a_type * \
184a_prefix##iter(a_rbt_type *rbtree, a_type *start, a_type *(*cb)( \
185 a_rbt_type *, a_type *, void *), void *arg); \
186a_attr a_type * \
187a_prefix##reverse_iter(a_rbt_type *rbtree, a_type *start, \
188 a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg);
189
190/*
191 * The rb_gen() macro generates a type-specific red-black tree implementation,
192 * based on the above cpp macros.
193 *
194 * Arguments:
195 *
196 * a_attr : Function attribute for generated functions (ex: static).
197 * a_prefix : Prefix for generated functions (ex: ex_).
198 * a_rb_type : Type for red-black tree data structure (ex: ex_t).
199 * a_type : Type for red-black tree node data structure (ex: ex_node_t).
200 * a_field : Name of red-black tree node linkage (ex: ex_link).
201 * a_cmp : Node comparison function name, with the following prototype:
202 * int (a_cmp *)(a_type *a_node, a_type *a_other);
203 * ^^^^^^
204 * or a_key
205 * Interpretation of comparision function return values:
206 * -1 : a_node < a_other
207 * 0 : a_node == a_other
208 * 1 : a_node > a_other
209 * In all cases, the a_node or a_key macro argument is the first
210 * argument to the comparison function, which makes it possible
211 * to write comparison functions that treat the first argument
212 * specially.
213 *
214 * Assuming the following setup:
215 *
216 * typedef struct ex_node_s ex_node_t;
217 * struct ex_node_s {
218 * rb_node(ex_node_t) ex_link;
219 * };
220 * typedef rb_tree(ex_node_t) ex_t;
221 * rb_gen(static, ex_, ex_t, ex_node_t, ex_link, ex_cmp)
222 *
223 * The following API is generated:
224 *
225 * static void
226 * ex_new(ex_t *extree);
227 * Description: Initialize a red-black tree structure.
228 * Args:
229 * extree: Pointer to an uninitialized red-black tree object.
230 *
231 * static ex_node_t *
232 * ex_first(ex_t *extree);
233 * static ex_node_t *
234 * ex_last(ex_t *extree);
235 * Description: Get the first/last node in extree.
236 * Args:
237 * extree: Pointer to an initialized red-black tree object.
238 * Ret: First/last node in extree, or NULL if extree is empty.
239 *
240 * static ex_node_t *
241 * ex_next(ex_t *extree, ex_node_t *node);
242 * static ex_node_t *
243 * ex_prev(ex_t *extree, ex_node_t *node);
244 * Description: Get node's successor/predecessor.
245 * Args:
246 * extree: Pointer to an initialized red-black tree object.
247 * node : A node in extree.
248 * Ret: node's successor/predecessor in extree, or NULL if node is
249 * last/first.
250 *
251 * static ex_node_t *
252 * ex_search(ex_t *extree, ex_node_t *key);
253 * Description: Search for node that matches key.
254 * Args:
255 * extree: Pointer to an initialized red-black tree object.
256 * key : Search key.
257 * Ret: Node in extree that matches key, or NULL if no match.
258 *
259 * static ex_node_t *
260 * ex_nsearch(ex_t *extree, ex_node_t *key);
261 * static ex_node_t *
262 * ex_psearch(ex_t *extree, ex_node_t *key);
263 * Description: Search for node that matches key. If no match is found,
264 * return what would be key's successor/predecessor, were
265 * key in extree.
266 * Args:
267 * extree: Pointer to an initialized red-black tree object.
268 * key : Search key.
269 * Ret: Node in extree that matches key, or if no match, hypothetical
270 * node's successor/predecessor (NULL if no successor/predecessor).
271 *
272 * static void
273 * ex_insert(ex_t *extree, ex_node_t *node);
274 * Description: Insert node into extree.
275 * Args:
276 * extree: Pointer to an initialized red-black tree object.
277 * node : Node to be inserted into extree.
278 *
279 * static void
280 * ex_remove(ex_t *extree, ex_node_t *node);
281 * Description: Remove node from extree.
282 * Args:
283 * extree: Pointer to an initialized red-black tree object.
284 * node : Node in extree to be removed.
285 *
286 * static ex_node_t *
287 * ex_iter(ex_t *extree, ex_node_t *start, ex_node_t *(*cb)(ex_t *,
288 * ex_node_t *, void *), void *arg);
289 * static ex_node_t *
290 * ex_reverse_iter(ex_t *extree, ex_node_t *start, ex_node *(*cb)(ex_t *,
291 * ex_node_t *, void *), void *arg);
292 * Description: Iterate forward/backward over extree, starting at node.
293 * If extree is modified, iteration must be immediately
294 * terminated by the callback function that causes the
295 * modification.
296 * Args:
297 * extree: Pointer to an initialized red-black tree object.
298 * start : Node at which to start iteration, or NULL to start at
299 * first/last node.
300 * cb : Callback function, which is called for each node during
301 * iteration. Under normal circumstances the callback function
302 * should return NULL, which causes iteration to continue. If a
303 * callback function returns non-NULL, iteration is immediately
304 * terminated and the non-NULL return value is returned by the
305 * iterator. This is useful for re-starting iteration after
306 * modifying extree.
307 * arg : Opaque pointer passed to cb().
308 * Ret: NULL if iteration completed, or the non-NULL callback return value
309 * that caused termination of the iteration.
310 */
311#define rb_gen(a_attr, a_prefix, a_rbt_type, a_type, a_field, a_cmp) \
312a_attr void \
313a_prefix##new(a_rbt_type *rbtree) { \
314 rb_new(a_type, a_field, rbtree); \
315} \
316a_attr a_type * \
317a_prefix##first(a_rbt_type *rbtree) { \
318 a_type *ret; \
319 rbtn_first(a_type, a_field, rbtree, rbtree->rbt_root, ret); \
320 if (ret == &rbtree->rbt_nil) { \
321 ret = NULL; \
322 } \
323 return (ret); \
324} \
325a_attr a_type * \
326a_prefix##last(a_rbt_type *rbtree) { \
327 a_type *ret; \
328 rbtn_last(a_type, a_field, rbtree, rbtree->rbt_root, ret); \
329 if (ret == &rbtree->rbt_nil) { \
330 ret = NULL; \
331 } \
332 return (ret); \
333} \
334a_attr a_type * \
335a_prefix##next(a_rbt_type *rbtree, a_type *node) { \
336 a_type *ret; \
337 if (rbtn_right_get(a_type, a_field, node) != &rbtree->rbt_nil) { \
338 rbtn_first(a_type, a_field, rbtree, rbtn_right_get(a_type, \
339 a_field, node), ret); \
340 } else { \
341 a_type *tnode = rbtree->rbt_root; \
342 assert(tnode != &rbtree->rbt_nil); \
343 ret = &rbtree->rbt_nil; \
344 while (true) { \
345 int cmp = (a_cmp)(node, tnode); \
346 if (cmp < 0) { \
347 ret = tnode; \
348 tnode = rbtn_left_get(a_type, a_field, tnode); \
349 } else if (cmp > 0) { \
350 tnode = rbtn_right_get(a_type, a_field, tnode); \
351 } else { \
352 break; \
353 } \
354 assert(tnode != &rbtree->rbt_nil); \
355 } \
356 } \
357 if (ret == &rbtree->rbt_nil) { \
358 ret = (NULL); \
359 } \
360 return (ret); \
361} \
362a_attr a_type * \
363a_prefix##prev(a_rbt_type *rbtree, a_type *node) { \
364 a_type *ret; \
365 if (rbtn_left_get(a_type, a_field, node) != &rbtree->rbt_nil) { \
366 rbtn_last(a_type, a_field, rbtree, rbtn_left_get(a_type, \
367 a_field, node), ret); \
368 } else { \
369 a_type *tnode = rbtree->rbt_root; \
370 assert(tnode != &rbtree->rbt_nil); \
371 ret = &rbtree->rbt_nil; \
372 while (true) { \
373 int cmp = (a_cmp)(node, tnode); \
374 if (cmp < 0) { \
375 tnode = rbtn_left_get(a_type, a_field, tnode); \
376 } else if (cmp > 0) { \
377 ret = tnode; \
378 tnode = rbtn_right_get(a_type, a_field, tnode); \
379 } else { \
380 break; \
381 } \
382 assert(tnode != &rbtree->rbt_nil); \
383 } \
384 } \
385 if (ret == &rbtree->rbt_nil) { \
386 ret = (NULL); \
387 } \
388 return (ret); \
389} \
390a_attr a_type * \
391a_prefix##search(a_rbt_type *rbtree, a_type *key) { \
392 a_type *ret; \
393 int cmp; \
394 ret = rbtree->rbt_root; \
395 while (ret != &rbtree->rbt_nil \
396 && (cmp = (a_cmp)(key, ret)) != 0) { \
397 if (cmp < 0) { \
398 ret = rbtn_left_get(a_type, a_field, ret); \
399 } else { \
400 ret = rbtn_right_get(a_type, a_field, ret); \
401 } \
402 } \
403 if (ret == &rbtree->rbt_nil) { \
404 ret = (NULL); \
405 } \
406 return (ret); \
407} \
408a_attr a_type * \
409a_prefix##nsearch(a_rbt_type *rbtree, a_type *key) { \
410 a_type *ret; \
411 a_type *tnode = rbtree->rbt_root; \
412 ret = &rbtree->rbt_nil; \
413 while (tnode != &rbtree->rbt_nil) { \
414 int cmp = (a_cmp)(key, tnode); \
415 if (cmp < 0) { \
416 ret = tnode; \
417 tnode = rbtn_left_get(a_type, a_field, tnode); \
418 } else if (cmp > 0) { \
419 tnode = rbtn_right_get(a_type, a_field, tnode); \
420 } else { \
421 ret = tnode; \
422 break; \
423 } \
424 } \
425 if (ret == &rbtree->rbt_nil) { \
426 ret = (NULL); \
427 } \
428 return (ret); \
429} \
430a_attr a_type * \
431a_prefix##psearch(a_rbt_type *rbtree, a_type *key) { \
432 a_type *ret; \
433 a_type *tnode = rbtree->rbt_root; \
434 ret = &rbtree->rbt_nil; \
435 while (tnode != &rbtree->rbt_nil) { \
436 int cmp = (a_cmp)(key, tnode); \
437 if (cmp < 0) { \
438 tnode = rbtn_left_get(a_type, a_field, tnode); \
439 } else if (cmp > 0) { \
440 ret = tnode; \
441 tnode = rbtn_right_get(a_type, a_field, tnode); \
442 } else { \
443 ret = tnode; \
444 break; \
445 } \
446 } \
447 if (ret == &rbtree->rbt_nil) { \
448 ret = (NULL); \
449 } \
450 return (ret); \
451} \
452a_attr void \
453a_prefix##insert(a_rbt_type *rbtree, a_type *node) { \
454 struct { \
455 a_type *node; \
456 int cmp; \
457 } path[sizeof(void *) << 4], *pathp; \
458 rbt_node_new(a_type, a_field, rbtree, node); \
459 /* Wind. */ \
460 path->node = rbtree->rbt_root; \
461 for (pathp = path; pathp->node != &rbtree->rbt_nil; pathp++) { \
462 int cmp = pathp->cmp = a_cmp(node, pathp->node); \
463 assert(cmp != 0); \
464 if (cmp < 0) { \
465 pathp[1].node = rbtn_left_get(a_type, a_field, \
466 pathp->node); \
467 } else { \
468 pathp[1].node = rbtn_right_get(a_type, a_field, \
469 pathp->node); \
470 } \
471 } \
472 pathp->node = node; \
473 /* Unwind. */ \
474 for (pathp--; (uintptr_t)pathp >= (uintptr_t)path; pathp--) { \
475 a_type *cnode = pathp->node; \
476 if (pathp->cmp < 0) { \
477 a_type *left = pathp[1].node; \
478 rbtn_left_set(a_type, a_field, cnode, left); \
479 if (rbtn_red_get(a_type, a_field, left)) { \
480 a_type *leftleft = rbtn_left_get(a_type, a_field, left);\
481 if (rbtn_red_get(a_type, a_field, leftleft)) { \
482 /* Fix up 4-node. */ \
483 a_type *tnode; \
484 rbtn_black_set(a_type, a_field, leftleft); \
485 rbtn_rotate_right(a_type, a_field, cnode, tnode); \
486 cnode = tnode; \
487 } \
488 } else { \
489 return; \
490 } \
491 } else { \
492 a_type *right = pathp[1].node; \
493 rbtn_right_set(a_type, a_field, cnode, right); \
494 if (rbtn_red_get(a_type, a_field, right)) { \
495 a_type *left = rbtn_left_get(a_type, a_field, cnode); \
496 if (rbtn_red_get(a_type, a_field, left)) { \
497 /* Split 4-node. */ \
498 rbtn_black_set(a_type, a_field, left); \
499 rbtn_black_set(a_type, a_field, right); \
500 rbtn_red_set(a_type, a_field, cnode); \
501 } else { \
502 /* Lean left. */ \
503 a_type *tnode; \
504 bool tred = rbtn_red_get(a_type, a_field, cnode); \
505 rbtn_rotate_left(a_type, a_field, cnode, tnode); \
506 rbtn_color_set(a_type, a_field, tnode, tred); \
507 rbtn_red_set(a_type, a_field, cnode); \
508 cnode = tnode; \
509 } \
510 } else { \
511 return; \
512 } \
513 } \
514 pathp->node = cnode; \
515 } \
516 /* Set root, and make it black. */ \
517 rbtree->rbt_root = path->node; \
518 rbtn_black_set(a_type, a_field, rbtree->rbt_root); \
519} \
520a_attr void \
521a_prefix##remove(a_rbt_type *rbtree, a_type *node) { \
522 struct { \
523 a_type *node; \
524 int cmp; \
525 } *pathp, *nodep, path[sizeof(void *) << 4]; \
526 /* Wind. */ \
527 nodep = NULL; /* Silence compiler warning. */ \
528 path->node = rbtree->rbt_root; \
529 for (pathp = path; pathp->node != &rbtree->rbt_nil; pathp++) { \
530 int cmp = pathp->cmp = a_cmp(node, pathp->node); \
531 if (cmp < 0) { \
532 pathp[1].node = rbtn_left_get(a_type, a_field, \
533 pathp->node); \
534 } else { \
535 pathp[1].node = rbtn_right_get(a_type, a_field, \
536 pathp->node); \
537 if (cmp == 0) { \
538 /* Find node's successor, in preparation for swap. */ \
539 pathp->cmp = 1; \
540 nodep = pathp; \
541 for (pathp++; pathp->node != &rbtree->rbt_nil; \
542 pathp++) { \
543 pathp->cmp = -1; \
544 pathp[1].node = rbtn_left_get(a_type, a_field, \
545 pathp->node); \
546 } \
547 break; \
548 } \
549 } \
550 } \
551 assert(nodep->node == node); \
552 pathp--; \
553 if (pathp->node != node) { \
554 /* Swap node with its successor. */ \
555 bool tred = rbtn_red_get(a_type, a_field, pathp->node); \
556 rbtn_color_set(a_type, a_field, pathp->node, \
557 rbtn_red_get(a_type, a_field, node)); \
558 rbtn_left_set(a_type, a_field, pathp->node, \
559 rbtn_left_get(a_type, a_field, node)); \
560 /* If node's successor is its right child, the following code */\
561 /* will do the wrong thing for the right child pointer. */\
562 /* However, it doesn't matter, because the pointer will be */\
563 /* properly set when the successor is pruned. */\
564 rbtn_right_set(a_type, a_field, pathp->node, \
565 rbtn_right_get(a_type, a_field, node)); \
566 rbtn_color_set(a_type, a_field, node, tred); \
567 /* The pruned leaf node's child pointers are never accessed */\
568 /* again, so don't bother setting them to nil. */\
569 nodep->node = pathp->node; \
570 pathp->node = node; \
571 if (nodep == path) { \
572 rbtree->rbt_root = nodep->node; \
573 } else { \
574 if (nodep[-1].cmp < 0) { \
575 rbtn_left_set(a_type, a_field, nodep[-1].node, \
576 nodep->node); \
577 } else { \
578 rbtn_right_set(a_type, a_field, nodep[-1].node, \
579 nodep->node); \
580 } \
581 } \
582 } else { \
583 a_type *left = rbtn_left_get(a_type, a_field, node); \
584 if (left != &rbtree->rbt_nil) { \
585 /* node has no successor, but it has a left child. */\
586 /* Splice node out, without losing the left child. */\
587 assert(rbtn_red_get(a_type, a_field, node) == false); \
588 assert(rbtn_red_get(a_type, a_field, left)); \
589 rbtn_black_set(a_type, a_field, left); \
590 if (pathp == path) { \
591 rbtree->rbt_root = left; \
592 } else { \
593 if (pathp[-1].cmp < 0) { \
594 rbtn_left_set(a_type, a_field, pathp[-1].node, \
595 left); \
596 } else { \
597 rbtn_right_set(a_type, a_field, pathp[-1].node, \
598 left); \
599 } \
600 } \
601 return; \
602 } else if (pathp == path) { \
603 /* The tree only contained one node. */ \
604 rbtree->rbt_root = &rbtree->rbt_nil; \
605 return; \
606 } \
607 } \
608 if (rbtn_red_get(a_type, a_field, pathp->node)) { \
609 /* Prune red node, which requires no fixup. */ \
610 assert(pathp[-1].cmp < 0); \
611 rbtn_left_set(a_type, a_field, pathp[-1].node, \
612 &rbtree->rbt_nil); \
613 return; \
614 } \
615 /* The node to be pruned is black, so unwind until balance is */\
616 /* restored. */\
617 pathp->node = &rbtree->rbt_nil; \
618 for (pathp--; (uintptr_t)pathp >= (uintptr_t)path; pathp--) { \
619 assert(pathp->cmp != 0); \
620 if (pathp->cmp < 0) { \
621 rbtn_left_set(a_type, a_field, pathp->node, \
622 pathp[1].node); \
623 assert(rbtn_red_get(a_type, a_field, pathp[1].node) \
624 == false); \
625 if (rbtn_red_get(a_type, a_field, pathp->node)) { \
626 a_type *right = rbtn_right_get(a_type, a_field, \
627 pathp->node); \
628 a_type *rightleft = rbtn_left_get(a_type, a_field, \
629 right); \
630 a_type *tnode; \
631 if (rbtn_red_get(a_type, a_field, rightleft)) { \
632 /* In the following diagrams, ||, //, and \\ */\
633 /* indicate the path to the removed node. */\
634 /* */\
635 /* || */\
636 /* pathp(r) */\
637 /* // \ */\
638 /* (b) (b) */\
639 /* / */\
640 /* (r) */\
641 /* */\
642 rbtn_black_set(a_type, a_field, pathp->node); \
643 rbtn_rotate_right(a_type, a_field, right, tnode); \
644 rbtn_right_set(a_type, a_field, pathp->node, tnode);\
645 rbtn_rotate_left(a_type, a_field, pathp->node, \
646 tnode); \
647 } else { \
648 /* || */\
649 /* pathp(r) */\
650 /* // \ */\
651 /* (b) (b) */\
652 /* / */\
653 /* (b) */\
654 /* */\
655 rbtn_rotate_left(a_type, a_field, pathp->node, \
656 tnode); \
657 } \
658 /* Balance restored, but rotation modified subtree */\
659 /* root. */\
660 assert((uintptr_t)pathp > (uintptr_t)path); \
661 if (pathp[-1].cmp < 0) { \
662 rbtn_left_set(a_type, a_field, pathp[-1].node, \
663 tnode); \
664 } else { \
665 rbtn_right_set(a_type, a_field, pathp[-1].node, \
666 tnode); \
667 } \
668 return; \
669 } else { \
670 a_type *right = rbtn_right_get(a_type, a_field, \
671 pathp->node); \
672 a_type *rightleft = rbtn_left_get(a_type, a_field, \
673 right); \
674 if (rbtn_red_get(a_type, a_field, rightleft)) { \
675 /* || */\
676 /* pathp(b) */\
677 /* // \ */\
678 /* (b) (b) */\
679 /* / */\
680 /* (r) */\
681 a_type *tnode; \
682 rbtn_black_set(a_type, a_field, rightleft); \
683 rbtn_rotate_right(a_type, a_field, right, tnode); \
684 rbtn_right_set(a_type, a_field, pathp->node, tnode);\
685 rbtn_rotate_left(a_type, a_field, pathp->node, \
686 tnode); \
687 /* Balance restored, but rotation modified */\
688 /* subree root, which may actually be the tree */\
689 /* root. */\
690 if (pathp == path) { \
691 /* Set root. */ \
692 rbtree->rbt_root = tnode; \
693 } else { \
694 if (pathp[-1].cmp < 0) { \
695 rbtn_left_set(a_type, a_field, \
696 pathp[-1].node, tnode); \
697 } else { \
698 rbtn_right_set(a_type, a_field, \
699 pathp[-1].node, tnode); \
700 } \
701 } \
702 return; \
703 } else { \
704 /* || */\
705 /* pathp(b) */\
706 /* // \ */\
707 /* (b) (b) */\
708 /* / */\
709 /* (b) */\
710 a_type *tnode; \
711 rbtn_red_set(a_type, a_field, pathp->node); \
712 rbtn_rotate_left(a_type, a_field, pathp->node, \
713 tnode); \
714 pathp->node = tnode; \
715 } \
716 } \
717 } else { \
718 a_type *left; \
719 rbtn_right_set(a_type, a_field, pathp->node, \
720 pathp[1].node); \
721 left = rbtn_left_get(a_type, a_field, pathp->node); \
722 if (rbtn_red_get(a_type, a_field, left)) { \
723 a_type *tnode; \
724 a_type *leftright = rbtn_right_get(a_type, a_field, \
725 left); \
726 a_type *leftrightleft = rbtn_left_get(a_type, a_field, \
727 leftright); \
728 if (rbtn_red_get(a_type, a_field, leftrightleft)) { \
729 /* || */\
730 /* pathp(b) */\
731 /* / \\ */\
732 /* (r) (b) */\
733 /* \ */\
734 /* (b) */\
735 /* / */\
736 /* (r) */\
737 a_type *unode; \
738 rbtn_black_set(a_type, a_field, leftrightleft); \
739 rbtn_rotate_right(a_type, a_field, pathp->node, \
740 unode); \
741 rbtn_rotate_right(a_type, a_field, pathp->node, \
742 tnode); \
743 rbtn_right_set(a_type, a_field, unode, tnode); \
744 rbtn_rotate_left(a_type, a_field, unode, tnode); \
745 } else { \
746 /* || */\
747 /* pathp(b) */\
748 /* / \\ */\
749 /* (r) (b) */\
750 /* \ */\
751 /* (b) */\
752 /* / */\
753 /* (b) */\
754 assert(leftright != &rbtree->rbt_nil); \
755 rbtn_red_set(a_type, a_field, leftright); \
756 rbtn_rotate_right(a_type, a_field, pathp->node, \
757 tnode); \
758 rbtn_black_set(a_type, a_field, tnode); \
759 } \
760 /* Balance restored, but rotation modified subtree */\
761 /* root, which may actually be the tree root. */\
762 if (pathp == path) { \
763 /* Set root. */ \
764 rbtree->rbt_root = tnode; \
765 } else { \
766 if (pathp[-1].cmp < 0) { \
767 rbtn_left_set(a_type, a_field, pathp[-1].node, \
768 tnode); \
769 } else { \
770 rbtn_right_set(a_type, a_field, pathp[-1].node, \
771 tnode); \
772 } \
773 } \
774 return; \
775 } else if (rbtn_red_get(a_type, a_field, pathp->node)) { \
776 a_type *leftleft = rbtn_left_get(a_type, a_field, left);\
777 if (rbtn_red_get(a_type, a_field, leftleft)) { \
778 /* || */\
779 /* pathp(r) */\
780 /* / \\ */\
781 /* (b) (b) */\
782 /* / */\
783 /* (r) */\
784 a_type *tnode; \
785 rbtn_black_set(a_type, a_field, pathp->node); \
786 rbtn_red_set(a_type, a_field, left); \
787 rbtn_black_set(a_type, a_field, leftleft); \
788 rbtn_rotate_right(a_type, a_field, pathp->node, \
789 tnode); \
790 /* Balance restored, but rotation modified */\
791 /* subtree root. */\
792 assert((uintptr_t)pathp > (uintptr_t)path); \
793 if (pathp[-1].cmp < 0) { \
794 rbtn_left_set(a_type, a_field, pathp[-1].node, \
795 tnode); \
796 } else { \
797 rbtn_right_set(a_type, a_field, pathp[-1].node, \
798 tnode); \
799 } \
800 return; \
801 } else { \
802 /* || */\
803 /* pathp(r) */\
804 /* / \\ */\
805 /* (b) (b) */\
806 /* / */\
807 /* (b) */\
808 rbtn_red_set(a_type, a_field, left); \
809 rbtn_black_set(a_type, a_field, pathp->node); \
810 /* Balance restored. */ \
811 return; \
812 } \
813 } else { \
814 a_type *leftleft = rbtn_left_get(a_type, a_field, left);\
815 if (rbtn_red_get(a_type, a_field, leftleft)) { \
816 /* || */\
817 /* pathp(b) */\
818 /* / \\ */\
819 /* (b) (b) */\
820 /* / */\
821 /* (r) */\
822 a_type *tnode; \
823 rbtn_black_set(a_type, a_field, leftleft); \
824 rbtn_rotate_right(a_type, a_field, pathp->node, \
825 tnode); \
826 /* Balance restored, but rotation modified */\
827 /* subtree root, which may actually be the tree */\
828 /* root. */\
829 if (pathp == path) { \
830 /* Set root. */ \
831 rbtree->rbt_root = tnode; \
832 } else { \
833 if (pathp[-1].cmp < 0) { \
834 rbtn_left_set(a_type, a_field, \
835 pathp[-1].node, tnode); \
836 } else { \
837 rbtn_right_set(a_type, a_field, \
838 pathp[-1].node, tnode); \
839 } \
840 } \
841 return; \
842 } else { \
843 /* || */\
844 /* pathp(b) */\
845 /* / \\ */\
846 /* (b) (b) */\
847 /* / */\
848 /* (b) */\
849 rbtn_red_set(a_type, a_field, left); \
850 } \
851 } \
852 } \
853 } \
854 /* Set root. */ \
855 rbtree->rbt_root = path->node; \
856 assert(rbtn_red_get(a_type, a_field, rbtree->rbt_root) == false); \
857} \
858a_attr a_type * \
859a_prefix##iter_recurse(a_rbt_type *rbtree, a_type *node, \
860 a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) { \
861 if (node == &rbtree->rbt_nil) { \
862 return (&rbtree->rbt_nil); \
863 } else { \
864 a_type *ret; \
865 if ((ret = a_prefix##iter_recurse(rbtree, rbtn_left_get(a_type, \
866 a_field, node), cb, arg)) != &rbtree->rbt_nil \
867 || (ret = cb(rbtree, node, arg)) != NULL) { \
868 return (ret); \
869 } \
870 return (a_prefix##iter_recurse(rbtree, rbtn_right_get(a_type, \
871 a_field, node), cb, arg)); \
872 } \
873} \
874a_attr a_type * \
875a_prefix##iter_start(a_rbt_type *rbtree, a_type *start, a_type *node, \
876 a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) { \
877 int cmp = a_cmp(start, node); \
878 if (cmp < 0) { \
879 a_type *ret; \
880 if ((ret = a_prefix##iter_start(rbtree, start, \
881 rbtn_left_get(a_type, a_field, node), cb, arg)) != \
882 &rbtree->rbt_nil || (ret = cb(rbtree, node, arg)) != NULL) { \
883 return (ret); \
884 } \
885 return (a_prefix##iter_recurse(rbtree, rbtn_right_get(a_type, \
886 a_field, node), cb, arg)); \
887 } else if (cmp > 0) { \
888 return (a_prefix##iter_start(rbtree, start, \
889 rbtn_right_get(a_type, a_field, node), cb, arg)); \
890 } else { \
891 a_type *ret; \
892 if ((ret = cb(rbtree, node, arg)) != NULL) { \
893 return (ret); \
894 } \
895 return (a_prefix##iter_recurse(rbtree, rbtn_right_get(a_type, \
896 a_field, node), cb, arg)); \
897 } \
898} \
899a_attr a_type * \
900a_prefix##iter(a_rbt_type *rbtree, a_type *start, a_type *(*cb)( \
901 a_rbt_type *, a_type *, void *), void *arg) { \
902 a_type *ret; \
903 if (start != NULL) { \
904 ret = a_prefix##iter_start(rbtree, start, rbtree->rbt_root, \
905 cb, arg); \
906 } else { \
907 ret = a_prefix##iter_recurse(rbtree, rbtree->rbt_root, cb, arg);\
908 } \
909 if (ret == &rbtree->rbt_nil) { \
910 ret = NULL; \
911 } \
912 return (ret); \
913} \
914a_attr a_type * \
915a_prefix##reverse_iter_recurse(a_rbt_type *rbtree, a_type *node, \
916 a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) { \
917 if (node == &rbtree->rbt_nil) { \
918 return (&rbtree->rbt_nil); \
919 } else { \
920 a_type *ret; \
921 if ((ret = a_prefix##reverse_iter_recurse(rbtree, \
922 rbtn_right_get(a_type, a_field, node), cb, arg)) != \
923 &rbtree->rbt_nil || (ret = cb(rbtree, node, arg)) != NULL) { \
924 return (ret); \
925 } \
926 return (a_prefix##reverse_iter_recurse(rbtree, \
927 rbtn_left_get(a_type, a_field, node), cb, arg)); \
928 } \
929} \
930a_attr a_type * \
931a_prefix##reverse_iter_start(a_rbt_type *rbtree, a_type *start, \
932 a_type *node, a_type *(*cb)(a_rbt_type *, a_type *, void *), \
933 void *arg) { \
934 int cmp = a_cmp(start, node); \
935 if (cmp > 0) { \
936 a_type *ret; \
937 if ((ret = a_prefix##reverse_iter_start(rbtree, start, \
938 rbtn_right_get(a_type, a_field, node), cb, arg)) != \
939 &rbtree->rbt_nil || (ret = cb(rbtree, node, arg)) != NULL) { \
940 return (ret); \
941 } \
942 return (a_prefix##reverse_iter_recurse(rbtree, \
943 rbtn_left_get(a_type, a_field, node), cb, arg)); \
944 } else if (cmp < 0) { \
945 return (a_prefix##reverse_iter_start(rbtree, start, \
946 rbtn_left_get(a_type, a_field, node), cb, arg)); \
947 } else { \
948 a_type *ret; \
949 if ((ret = cb(rbtree, node, arg)) != NULL) { \
950 return (ret); \
951 } \
952 return (a_prefix##reverse_iter_recurse(rbtree, \
953 rbtn_left_get(a_type, a_field, node), cb, arg)); \
954 } \
955} \
956a_attr a_type * \
957a_prefix##reverse_iter(a_rbt_type *rbtree, a_type *start, \
958 a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) { \
959 a_type *ret; \
960 if (start != NULL) { \
961 ret = a_prefix##reverse_iter_start(rbtree, start, \
962 rbtree->rbt_root, cb, arg); \
963 } else { \
964 ret = a_prefix##reverse_iter_recurse(rbtree, rbtree->rbt_root, \
965 cb, arg); \
966 } \
967 if (ret == &rbtree->rbt_nil) { \
968 ret = NULL; \
969 } \
970 return (ret); \
971}
972
973#endif /* RB_H_ */
Redis += OpenLDAP MDB