Coverage Report

Created: 2021-04-05 03:19

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