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