Code Coverage: vinyl-cache/include/vtree.h
 
82217aa4fc7094b3610340078afaf78cd95a8ec9
 
0
/*      $NetBSD: tree.h,v 1.8 2004/03/28 19:38:30 provos Exp $  */
1
/*      $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $    */
2
3
/*-
4
 * SPDX-License-Identifier: BSD-2-Clause
5
 *
6
 * Copyright 2002 Niels Provos <provos@citi.umich.edu>
7
 * All rights reserved.
8
 *
9
 * Redistribution and use in source and binary forms, with or without
10
 * modification, are permitted provided that the following conditions
11
 * are met:
12
 * 1. Redistributions of source code must retain the above copyright
13
 *    notice, this list of conditions and the following disclaimer.
14
 * 2. Redistributions in binary form must reproduce the above copyright
15
 *    notice, this list of conditions and the following disclaimer in the
16
 *    documentation and/or other materials provided with the distribution.
17
 *
18
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
19
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
20
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
21
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
22
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
23
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
27
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28
 */
29
30
#ifndef _VTREE_H_
31
#define _VTREE_H_
32
33
/* XXX
34
 * Enable -Wall with gcc -O2
35
 */
36
#pragma GCC diagnostic ignored "-Wstrict-aliasing"
37
38
/*
39
 * This file defines data structures for different types of trees:
40
 * splay trees and rank-balanced trees.
41
 *
42
 * A splay tree is a self-organizing data structure.  Every operation
43
 * on the tree causes a splay to happen.  The splay moves the requested
44
 * node to the root of the tree and partly rebalances it.
45
 *
46
 * This has the benefit that request locality causes faster lookups as
47
 * the requested nodes move to the top of the tree.  On the other hand,
48
 * every lookup causes memory writes.
49
 *
50
 * The Balance Theorem bounds the total access time for m operations
51
 * and n inserts on an initially empty tree as O((m + n)lg n).  The
52
 * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
53
 *
54
 * A rank-balanced tree is a binary search tree with an integer
55
 * rank-difference as an attribute of each pointer from parent to child.
56
 * The sum of the rank-differences on any path from a node down to null is
57
 * the same, and defines the rank of that node. The rank of the null node
58
 * is -1.
59
 *
60
 * Different additional conditions define different sorts of balanced trees,
61
 * including "red-black" and "AVL" trees.  The set of conditions applied here
62
 * are the "weak-AVL" conditions of Haeupler, Sen and Tarjan presented in in
63
 * "Rank Balanced Trees", ACM Transactions on Algorithms Volume 11 Issue 4 June
64
 * 2015 Article No.: 30pp 1–26 https://doi.org/10.1145/2689412 (the HST paper):
65
 *      - every rank-difference is 1 or 2.
66
 *      - the rank of any leaf is 1.
67
 *
68
 * For historical reasons, rank differences that are even are associated
69
 * with the color red (Rank-Even-Difference), and the child that a red edge
70
 * points to is called a red child.
71
 *
72
 * Every operation on a rank-balanced tree is bounded as O(lg n).
73
 * The maximum height of a rank-balanced tree is 2lg (n+1).
74
 */
75
76
#ifndef __CHERI__
77
#  define __no_subobject_bounds /* */
78 4270
#  define ptraddr_t uintptr_t
79
#endif
80
81
#define VSPLAY_HEAD(name, type)                                         \
82
struct name {                                                           \
83
        struct type *sph_root; /* root of the tree */                   \
84
}
85
86
#define VSPLAY_INITIALIZER(root)                                                \
87
        { NULL }
88
89
#define VSPLAY_INIT(root) do {                                          \
90
        (root)->sph_root = NULL;                                        \
91
} while (/*CONSTCOND*/ 0)
92
93
#define VSPLAY_ENTRY(type)                                              \
94
struct {                                                                \
95
        struct type *spe_left __no_subobject_bounds; /* left element */ \
96
        struct type *spe_right __no_subobject_bounds; /* right element */ \
97
}
98
99
#define VSPLAY_LEFT(elm, field)         (elm)->field.spe_left
100
#define VSPLAY_RIGHT(elm, field)                (elm)->field.spe_right
101
#define VSPLAY_ROOT(head)               (head)->sph_root
102
#define VSPLAY_EMPTY(head)              (VSPLAY_ROOT(head) == NULL)
103
104
/* VSPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold VSPLAY_{RIGHT,LEFT} */
105
#define VSPLAY_ROTATE_RIGHT(head, tmp, field) do {                      \
106
        VSPLAY_LEFT((head)->sph_root, field) = VSPLAY_RIGHT(tmp, field);        \
107
        VSPLAY_RIGHT(tmp, field) = (head)->sph_root;                    \
108
        (head)->sph_root = tmp;                                         \
109
} while (/*CONSTCOND*/ 0)
110
111
#define VSPLAY_ROTATE_LEFT(head, tmp, field) do {                       \
112
        VSPLAY_RIGHT((head)->sph_root, field) = VSPLAY_LEFT(tmp, field);        \
113
        VSPLAY_LEFT(tmp, field) = (head)->sph_root;                     \
114
        (head)->sph_root = tmp;                                         \
115
} while (/*CONSTCOND*/ 0)
116
117
#define VSPLAY_LINKLEFT(head, tmp, field) do {                          \
118
        VSPLAY_LEFT(tmp, field) = (head)->sph_root;                     \
119
        tmp = (head)->sph_root;                                         \
120
        (head)->sph_root = VSPLAY_LEFT((head)->sph_root, field);                \
121
} while (/*CONSTCOND*/ 0)
122
123
#define VSPLAY_LINKRIGHT(head, tmp, field) do {                         \
124
        VSPLAY_RIGHT(tmp, field) = (head)->sph_root;                    \
125
        tmp = (head)->sph_root;                                         \
126
        (head)->sph_root = VSPLAY_RIGHT((head)->sph_root, field);       \
127
} while (/*CONSTCOND*/ 0)
128
129
#define VSPLAY_ASSEMBLE(head, node, left, right, field) do {            \
130
        VSPLAY_RIGHT(left, field) = VSPLAY_LEFT((head)->sph_root, field);       \
131
        VSPLAY_LEFT(right, field) = VSPLAY_RIGHT((head)->sph_root, field);\
132
        VSPLAY_LEFT((head)->sph_root, field) = VSPLAY_RIGHT(node, field);       \
133
        VSPLAY_RIGHT((head)->sph_root, field) = VSPLAY_LEFT(node, field);       \
134
} while (/*CONSTCOND*/ 0)
135
136
/* Generates prototypes and inline functions */
137
138
#define VSPLAY_PROTOTYPE(name, type, field, cmp)                                \
139
void name##_VSPLAY(struct name *, struct type *);                       \
140
void name##_VSPLAY_MINMAX(struct name *, int);                          \
141
struct type *name##_VSPLAY_INSERT(struct name *, struct type *);                \
142
struct type *name##_VSPLAY_REMOVE(struct name *, struct type *);                \
143
                                                                        \
144
/* Finds the node with the same key as elm */                           \
145
static v_unused_ __inline struct type *                                 \
146
name##_VSPLAY_FIND(struct name *head, struct type *elm)                 \
147
{                                                                       \
148
        if (VSPLAY_EMPTY(head))                                         \
149
                return(NULL);                                           \
150
        name##_VSPLAY(head, elm);                                       \
151
        if ((cmp)(elm, (head)->sph_root) == 0)                          \
152
                return (head->sph_root);                                \
153
        return (NULL);                                                  \
154
}                                                                       \
155
                                                                        \
156
static v_unused_ __inline struct type *                                 \
157
name##_VSPLAY_NEXT(struct name *head, struct type *elm)                 \
158
{                                                                       \
159
        name##_VSPLAY(head, elm);                                       \
160
        if (VSPLAY_RIGHT(elm, field) != NULL) {                         \
161
                elm = VSPLAY_RIGHT(elm, field);                         \
162
                while (VSPLAY_LEFT(elm, field) != NULL) {               \
163
                        elm = VSPLAY_LEFT(elm, field);                  \
164
                }                                                       \
165
        } else                                                          \
166
                elm = NULL;                                             \
167
        return (elm);                                                   \
168
}                                                                       \
169
                                                                        \
170
static v_unused_ __inline struct type *                                 \
171
name##_VSPLAY_MIN_MAX(struct name *head, int val)                       \
172
{                                                                       \
173
        name##_VSPLAY_MINMAX(head, val);                                        \
174
        return (VSPLAY_ROOT(head));                                     \
175
}
176
177
/* Main splay operation.
178
 * Moves node close to the key of elm to top
179
 */
180
#define VSPLAY_GENERATE(name, type, field, cmp)                         \
181
struct type *                                                           \
182
name##_VSPLAY_INSERT(struct name *head, struct type *elm)               \
183
{                                                                       \
184
    if (VSPLAY_EMPTY(head)) {                                           \
185
            VSPLAY_LEFT(elm, field) = VSPLAY_RIGHT(elm, field) = NULL;  \
186
    } else {                                                            \
187
            __typeof(cmp(NULL, NULL)) __comp;                           \
188
            name##_VSPLAY(head, elm);                                   \
189
            __comp = (cmp)(elm, (head)->sph_root);                      \
190
            if (__comp < 0) {                                           \
191
                    VSPLAY_LEFT(elm, field) = VSPLAY_LEFT((head)->sph_root, field);\
192
                    VSPLAY_RIGHT(elm, field) = (head)->sph_root;                \
193
                    VSPLAY_LEFT((head)->sph_root, field) = NULL;                \
194
            } else if (__comp > 0) {                                    \
195
                    VSPLAY_RIGHT(elm, field) = VSPLAY_RIGHT((head)->sph_root, field);\
196
                    VSPLAY_LEFT(elm, field) = (head)->sph_root;         \
197
                    VSPLAY_RIGHT((head)->sph_root, field) = NULL;       \
198
            } else                                                      \
199
                    return ((head)->sph_root);                          \
200
    }                                                                   \
201
    (head)->sph_root = (elm);                                           \
202
    return (NULL);                                                      \
203
}                                                                       \
204
                                                                        \
205
struct type *                                                           \
206
name##_VSPLAY_REMOVE(struct name *head, struct type *elm)               \
207
{                                                                       \
208
        struct type *__tmp;                                             \
209
        if (VSPLAY_EMPTY(head))                                         \
210
                return (NULL);                                          \
211
        name##_VSPLAY(head, elm);                                       \
212
        if ((cmp)(elm, (head)->sph_root) == 0) {                        \
213
                if (VSPLAY_LEFT((head)->sph_root, field) == NULL) {     \
214
                        (head)->sph_root = VSPLAY_RIGHT((head)->sph_root, field);\
215
                } else {                                                \
216
                        __tmp = VSPLAY_RIGHT((head)->sph_root, field);  \
217
                        (head)->sph_root = VSPLAY_LEFT((head)->sph_root, field);\
218
                        name##_VSPLAY(head, elm);                       \
219
                        VSPLAY_RIGHT((head)->sph_root, field) = __tmp;  \
220
                }                                                       \
221
                return (elm);                                           \
222
        }                                                               \
223
        return (NULL);                                                  \
224
}                                                                       \
225
                                                                        \
226
void                                                                    \
227
name##_VSPLAY(struct name *head, struct type *elm)                      \
228
{                                                                       \
229
        struct type __node, *__left, *__right, *__tmp;                  \
230
        __typeof(cmp(NULL, NULL)) __comp;                               \
231
\
232
        VSPLAY_LEFT(&__node, field) = VSPLAY_RIGHT(&__node, field) = NULL;\
233
        __left = __right = &__node;                                     \
234
\
235
        while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) {          \
236
                if (__comp < 0) {                                       \
237
                        __tmp = VSPLAY_LEFT((head)->sph_root, field);   \
238
                        if (__tmp == NULL)                              \
239
                                break;                                  \
240
                        if ((cmp)(elm, __tmp) < 0){                     \
241
                                VSPLAY_ROTATE_RIGHT(head, __tmp, field);        \
242
                                if (VSPLAY_LEFT((head)->sph_root, field) == NULL)\
243
                                        break;                          \
244
                        }                                               \
245
                        VSPLAY_LINKLEFT(head, __right, field);          \
246
                } else if (__comp > 0) {                                \
247
                        __tmp = VSPLAY_RIGHT((head)->sph_root, field);  \
248
                        if (__tmp == NULL)                              \
249
                                break;                                  \
250
                        if ((cmp)(elm, __tmp) > 0){                     \
251
                                VSPLAY_ROTATE_LEFT(head, __tmp, field); \
252
                                if (VSPLAY_RIGHT((head)->sph_root, field) == NULL)\
253
                                        break;                          \
254
                        }                                               \
255
                        VSPLAY_LINKRIGHT(head, __left, field);          \
256
                }                                                       \
257
        }                                                               \
258
        VSPLAY_ASSEMBLE(head, &__node, __left, __right, field);         \
259
}                                                                       \
260
                                                                        \
261
/* Splay with either the minimum or the maximum element                 \
262
 * Used to find minimum or maximum element in tree.                     \
263
 */                                                                     \
264
void name##_VSPLAY_MINMAX(struct name *head, int __comp) \
265
{                                                                       \
266
        struct type __node, *__left, *__right, *__tmp;                  \
267
\
268
        VSPLAY_LEFT(&__node, field) = VSPLAY_RIGHT(&__node, field) = NULL;\
269
        __left = __right = &__node;                                     \
270
\
271
        while (1) {                                                     \
272
                if (__comp < 0) {                                       \
273
                        __tmp = VSPLAY_LEFT((head)->sph_root, field);   \
274
                        if (__tmp == NULL)                              \
275
                                break;                                  \
276
                        if (__comp < 0){                                \
277
                                VSPLAY_ROTATE_RIGHT(head, __tmp, field);        \
278
                                if (VSPLAY_LEFT((head)->sph_root, field) == NULL)\
279
                                        break;                          \
280
                        }                                               \
281
                        VSPLAY_LINKLEFT(head, __right, field);          \
282
                } else if (__comp > 0) {                                \
283
                        __tmp = VSPLAY_RIGHT((head)->sph_root, field);  \
284
                        if (__tmp == NULL)                              \
285
                                break;                                  \
286
                        if (__comp > 0) {                               \
287
                                VSPLAY_ROTATE_LEFT(head, __tmp, field); \
288
                                if (VSPLAY_RIGHT((head)->sph_root, field) == NULL)\
289
                                        break;                          \
290
                        }                                               \
291
                        VSPLAY_LINKRIGHT(head, __left, field);          \
292
                }                                                       \
293
        }                                                               \
294
        VSPLAY_ASSEMBLE(head, &__node, __left, __right, field);         \
295
}
296
297
#define VSPLAY_NEGINF   -1
298
#define VSPLAY_INF      1
299
300
#define VSPLAY_INSERT(name, x, y)       name##_VSPLAY_INSERT(x, y)
301
#define VSPLAY_REMOVE(name, x, y)       name##_VSPLAY_REMOVE(x, y)
302
#define VSPLAY_FIND(name, x, y)         name##_VSPLAY_FIND(x, y)
303
#define VSPLAY_NEXT(name, x, y)         name##_VSPLAY_NEXT(x, y)
304
#define VSPLAY_MIN(name, x)             (VSPLAY_EMPTY(x) ? NULL \
305
                                        : name##_VSPLAY_MIN_MAX(x, VSPLAY_NEGINF))
306
#define VSPLAY_MAX(name, x)             (VSPLAY_EMPTY(x) ? NULL \
307
                                        : name##_VSPLAY_MIN_MAX(x, VSPLAY_INF))
308
309
#define VSPLAY_FOREACH(x, name, head)                                   \
310
        for ((x) = VSPLAY_MIN(name, head);                              \
311
             (x) != NULL;                                               \
312
             (x) = VSPLAY_NEXT(name, head, x))
313
314
/* Macros that define a rank-balanced tree */
315
#define VRBT_HEAD(name, type)                                           \
316
struct name {                                                           \
317
        struct type *rbh_root; /* root of the tree */                   \
318
}
319
320
#define VRBT_INITIALIZER(root)                                          \
321
        { NULL }
322
323 19563
#define VRBT_INIT(root) do {                                            \
324 19563
        (root)->rbh_root = NULL;                                        \
325 19563
} while (/*CONSTCOND*/ 0)
326
327
#define VRBT_ENTRY(type)                                                \
328
struct {                                                                \
329
        struct type *rbe_link[3] __no_subobject_bounds;                 \
330
}
331
332
/*
333
 * With the expectation that any object of struct type has an
334
 * address that is a multiple of 4, and that therefore the
335
 * 2 least significant bits of a pointer to struct type are
336
 * always zero, this implementation sets those bits to indicate
337
 * that the left or right child of the tree node is "red".
338
 */
339 88903719
#define _VRBT_LINK(elm, dir, field)     (elm)->field.rbe_link[dir]
340 23334
#define _VRBT_UP(elm, field)            _VRBT_LINK(elm, 0, field)
341 9910
#define _VRBT_L                         ((ptraddr_t)1)
342 4874
#define _VRBT_R                         ((ptraddr_t)2)
343 17444
#define _VRBT_LR                        ((ptraddr_t)3)
344 21432
#define _VRBT_BITS(elm)                 ((ptraddr_t)elm)
345 4865
#define _VRBT_BITSUP(elm, field)        _VRBT_BITS(_VRBT_UP(elm, field))
346 22283
#define _VRBT_PTR_OP(elm, op, dir)      ((__typeof(elm))                \
347 22283
                                        ((uintptr_t)(elm) op (dir)))
348 10657
#define _VRBT_PTR(elm)                  _VRBT_PTR_OP((elm), &, ~_VRBT_LR)
349 2
#define _VRBT_MOD_OR(elm, dir)          ((elm) = _VRBT_PTR_OP((elm), |, (dir)))
350 8301
#define _VRBT_MOD_XOR(elm, dir)         ((elm) = _VRBT_PTR_OP((elm), ^, (dir)))
351
352 7205
#define VRBT_PARENT(elm, field)         _VRBT_PTR(_VRBT_UP(elm, field))
353 47078618
#define VRBT_LEFT(elm, field)           _VRBT_LINK(elm, _VRBT_L, field)
354 41792020
#define VRBT_RIGHT(elm, field)          _VRBT_LINK(elm, _VRBT_R, field)
355 11157197
#define VRBT_ROOT(head)                 (head)->rbh_root
356 8326
#define VRBT_EMPTY(head)                (VRBT_ROOT(head) == NULL)
357
358 3236
#define VRBT_SET_PARENT(dst, src, field) do {                           \
359 3236
        _VRBT_UP(dst, field) = (__typeof(src))((uintptr_t)src |         \
360 3236
            (ptraddr_t)(_VRBT_BITSUP(dst, field) & _VRBT_LR));          \
361 3236
} while (/*CONSTCOND*/ 0)
362
363 5115
#define VRBT_SET(elm, parent, field) do {                               \
364 5115
        _VRBT_UP(elm, field) = parent;                                  \
365 5115
        VRBT_LEFT(elm, field) = VRBT_RIGHT(elm, field) = NULL;          \
366 5115
} while (/*CONSTCOND*/ 0)
367
368
/*
369
 * Either VRBT_AUGMENT or VRBT_AUGMENT_CHECK is invoked in a loop at the root of
370
 * every modified subtree, from the bottom up to the root, to update augmented
371
 * node data.  VRBT_AUGMENT_CHECK returns true only when the update changes the
372
 * node data, so that updating can be stopped short of the root when it returns
373
 * false.
374
 */
375
#ifndef VRBT_AUGMENT_CHECK
376
#ifndef VRBT_AUGMENT
377 14786
#define VRBT_AUGMENT_CHECK(x) 0
378
#else
379
#define VRBT_AUGMENT_CHECK(x) (VRBT_AUGMENT(x), 1)
380
#endif
381
#endif
382
383
#define VRBT_UPDATE_AUGMENT(elm, field) do {                            \
384
        __typeof(elm) rb_update_tmp = (elm);                            \
385
        while (VRBT_AUGMENT_CHECK(rb_update_tmp) &&                     \
386
            (rb_update_tmp = VRBT_PARENT(rb_update_tmp, field)) != NULL)        \
387
                ;                                                       \
388
} while (0)
389
390 3194
#define VRBT_SWAP_CHILD(head, par, out, in, field) do {                 \
391 3194
        if (par == NULL)                                                \
392 3194
                VRBT_ROOT(head) = (in);                                 \
393 3194
        else if ((out) == VRBT_LEFT(par, field))                                \
394 2386
                VRBT_LEFT(par, field) = (in);                           \
395 2386
        else                                                            \
396 2386
                VRBT_RIGHT(par, field) = (in);                          \
397 3194
} while (/*CONSTCOND*/ 0)
398
399
/*
400
 * VRBT_ROTATE macro partially restructures the tree to improve balance. In the
401
 * case when dir is _VRBT_L, tmp is a right child of elm.  After rotation, elm
402
 * is a left child of tmp, and the subtree that represented the items between
403
 * them, which formerly hung to the left of tmp now hangs to the right of elm.
404
 * The parent-child relationship between elm and its former parent is not
405
 * changed; where this macro once updated those fields, that is now left to the
406
 * caller of VRBT_ROTATE to clean up, so that a pair of rotations does not twice
407
 * update the same pair of pointer fields with distinct values.
408
 */
409 2446
#define VRBT_ROTATE(elm, tmp, dir, field) do {                          \
410 2446
        if ((_VRBT_LINK(elm, dir ^ _VRBT_LR, field) =                   \
411 2446
            _VRBT_LINK(tmp, dir, field)) != NULL)                               \
412 2446
                VRBT_SET_PARENT(_VRBT_LINK(tmp, dir, field), elm, field);       \
413 2446
        _VRBT_LINK(tmp, dir, field) = (elm);                            \
414 2446
        VRBT_SET_PARENT(elm, tmp, field);                                       \
415 2446
} while (/*CONSTCOND*/ 0)
416
417
/* Generates prototypes and inline functions */
418
#define VRBT_PROTOTYPE(name, type, field, cmp)                          \
419
        VRBT_PROTOTYPE_INTERNAL(name, type, field, cmp,)
420
#define VRBT_PROTOTYPE_STATIC(name, type, field, cmp)                   \
421
        VRBT_PROTOTYPE_INTERNAL(name, type, field, cmp, v_unused_ static)
422
#define VRBT_PROTOTYPE_INTERNAL(name, type, field, cmp, attr)           \
423
        VRBT_PROTOTYPE_RANK(name, type, attr)                           \
424
        VRBT_PROTOTYPE_INSERT_COLOR(name, type, attr);                  \
425
        VRBT_PROTOTYPE_REMOVE_COLOR(name, type, attr);                  \
426
        VRBT_PROTOTYPE_INSERT_FINISH(name, type, attr);                 \
427
        VRBT_PROTOTYPE_INSERT(name, type, attr);                                \
428
        VRBT_PROTOTYPE_REMOVE(name, type, attr);                                \
429
        VRBT_PROTOTYPE_FIND(name, type, attr);                          \
430
        VRBT_PROTOTYPE_NFIND(name, type, attr);                         \
431
        VRBT_PROTOTYPE_NEXT(name, type, attr);                          \
432
        VRBT_PROTOTYPE_INSERT_NEXT(name, type, attr);                   \
433
        VRBT_PROTOTYPE_PREV(name, type, attr);                          \
434
        VRBT_PROTOTYPE_INSERT_PREV(name, type, attr);                   \
435
        VRBT_PROTOTYPE_MINMAX(name, type, attr);                                \
436
        VRBT_PROTOTYPE_REINSERT(name, type, attr);
437
#ifdef _VRBT_DIAGNOSTIC
438
#define VRBT_PROTOTYPE_RANK(name, type, attr)                           \
439
        attr int name##_VRBT_RANK(struct type *);
440
#else
441
#define VRBT_PROTOTYPE_RANK(name, type, attr)
442
#endif
443
#define VRBT_PROTOTYPE_INSERT_COLOR(name, type, attr)                   \
444
        attr struct type *name##_VRBT_INSERT_COLOR(struct name *,               \
445
            struct type *, struct type *)
446
#define VRBT_PROTOTYPE_REMOVE_COLOR(name, type, attr)                   \
447
        attr struct type *name##_VRBT_REMOVE_COLOR(struct name *,               \
448
            struct type *, struct type *)
449
#define VRBT_PROTOTYPE_REMOVE(name, type, attr)                         \
450
        attr struct type *name##_VRBT_REMOVE(struct name *, struct type *)
451
#define VRBT_PROTOTYPE_INSERT_FINISH(name, type, attr)                  \
452
        attr struct type *name##_VRBT_INSERT_FINISH(struct name *,      \
453
            struct type *, struct type **, struct type *)
454
#define VRBT_PROTOTYPE_INSERT(name, type, attr)                         \
455
        attr struct type *name##_VRBT_INSERT(struct name *, struct type *)
456
#define VRBT_PROTOTYPE_FIND(name, type, attr)                           \
457
        attr struct type *name##_VRBT_FIND(const struct name *, const struct type *)
458
#define VRBT_PROTOTYPE_NFIND(name, type, attr)                          \
459
        attr struct type *name##_VRBT_NFIND(const struct name *, const struct type *)
460
#define VRBT_PROTOTYPE_NEXT(name, type, attr)                           \
461
        attr struct type *name##_VRBT_NEXT(struct type *)
462
#define VRBT_PROTOTYPE_INSERT_NEXT(name, type, attr)                    \
463
        attr struct type *name##_VRBT_INSERT_NEXT(struct name *,                \
464
            struct type *, struct type *)
465
#define VRBT_PROTOTYPE_PREV(name, type, attr)                           \
466
        attr struct type *name##_VRBT_PREV(struct type *)
467
#define VRBT_PROTOTYPE_INSERT_PREV(name, type, attr)                    \
468
        attr struct type *name##_VRBT_INSERT_PREV(struct name *,                \
469
            struct type *, struct type *)
470
#define VRBT_PROTOTYPE_MINMAX(name, type, attr)                         \
471
        attr struct type *name##_VRBT_MINMAX(const struct name *, int)
472
#define VRBT_PROTOTYPE_REINSERT(name, type, attr)                       \
473
        attr struct type *name##_VRBT_REINSERT(struct name *, struct type *)
474
475
/* Main rb operation.
476
 * Moves node close to the key of elm to top
477
 */
478
#define VRBT_GENERATE(name, type, field, cmp)                           \
479
        VRBT_GENERATE_INTERNAL(name, type, field, cmp,)
480
#define VRBT_GENERATE_STATIC(name, type, field, cmp)                    \
481
        VRBT_GENERATE_INTERNAL(name, type, field, cmp, v_unused_ static)
482
#define VRBT_GENERATE_INTERNAL(name, type, field, cmp, attr)            \
483
        VRBT_GENERATE_RANK(name, type, field, attr)                     \
484
        VRBT_GENERATE_INSERT_COLOR(name, type, field, attr)             \
485
        VRBT_GENERATE_REMOVE_COLOR(name, type, field, attr)             \
486
        VRBT_GENERATE_INSERT_FINISH(name, type, field, attr)            \
487
        VRBT_GENERATE_INSERT(name, type, field, cmp, attr)              \
488
        VRBT_GENERATE_REMOVE(name, type, field, attr)                   \
489
        VRBT_GENERATE_FIND(name, type, field, cmp, attr)                        \
490
        VRBT_GENERATE_NFIND(name, type, field, cmp, attr)                       \
491
        VRBT_GENERATE_NEXT(name, type, field, attr)                     \
492
        VRBT_GENERATE_INSERT_NEXT(name, type, field, cmp, attr)         \
493
        VRBT_GENERATE_PREV(name, type, field, attr)                     \
494
        VRBT_GENERATE_INSERT_PREV(name, type, field, cmp, attr)         \
495
        VRBT_GENERATE_MINMAX(name, type, field, attr)                   \
496
        VRBT_GENERATE_REINSERT(name, type, field, cmp, attr)
497
498
#ifdef _VRBT_DIAGNOSTIC
499
#ifndef VRBT_AUGMENT
500
#define _VRBT_AUGMENT_VERIFY(x) VRBT_AUGMENT_CHECK(x)
501
#else
502
#define _VRBT_AUGMENT_VERIFY(x) 0
503
#endif
504
#define VRBT_GENERATE_RANK(name, type, field, attr)                     \
505
/*                                                                      \
506
 * Return the rank of the subtree rooted at elm, or -1 if the subtree   \
507
 * is not rank-balanced, or has inconsistent augmentation data.
508
 */                                                                     \
509
attr int                                                                \
510
name##_VRBT_RANK(struct type *elm)                                      \
511
{                                                                       \
512
        struct type *left, *right, *up;                                 \
513
        int left_rank, right_rank;                                      \
514
                                                                        \
515
        if (elm == NULL)                                                \
516
                return (0);                                             \
517
        up = _VRBT_UP(elm, field);                                      \
518
        left = VRBT_LEFT(elm, field);                                   \
519
        left_rank = ((_VRBT_BITS(up) & _VRBT_L) ? 2 : 1) +                      \
520
            name##_VRBT_RANK(left);                                     \
521
        right = VRBT_RIGHT(elm, field);                                 \
522
        right_rank = ((_VRBT_BITS(up) & _VRBT_R) ? 2 : 1) +                     \
523
            name##_VRBT_RANK(right);                                    \
524
        if (left_rank != right_rank ||                                  \
525
            (left_rank == 2 && left == NULL && right == NULL) ||        \
526
            _VRBT_AUGMENT_VERIFY(elm))                                  \
527
                return (-1);                                            \
528
        return (left_rank);                                             \
529
}
530
#else
531
#define VRBT_GENERATE_RANK(name, type, field, attr)
532
#endif
533
534
#define VRBT_GENERATE_INSERT_COLOR(name, type, field, attr)             \
535
attr struct type *                                                      \
536
name##_VRBT_INSERT_COLOR(struct name *head,                             \
537 3297
    struct type *parent, struct type *elm)                              \
538 3297
{                                                                       \
539 3297
        /*                                                              \
540 3297
         * Initially, elm is a leaf.  Either its parent was previously  \
541 3297
         * a leaf, with two black null children, or an interior node    \
542 3297
         * with a black non-null child and a red null child. The        \
543 3297
         * balance criterion "the rank of any leaf is 1" precludes the  \
544 3297
         * possibility of two red null children for the initial parent. \
545 3297
         * So the first loop iteration cannot lead to accessing an      \
546 3297
         * uninitialized 'child', and a later iteration can only happen \
547 3297
         * when a value has been assigned to 'child' in the previous    \
548 3297
         * one.                                                         \
549 3297
         */                                                             \
550 3297
        struct type *child = NULL, *child_up, *gpar;                    \
551 3297
        ptraddr_t elmdir, sibdir;                                       \
552 3297
                                                                        \
553 7159
        do {                                                            \
554 7159
                /* the rank of the tree rooted at elm grew */           \
555 7159
                gpar = _VRBT_UP(parent, field);                         \
556 7159
                elmdir = VRBT_RIGHT(parent, field) == elm ? _VRBT_R : _VRBT_L; \
557 7159
                if (_VRBT_BITS(gpar) & elmdir) {                                \
558 505
                        /* shorten the parent-elm edge to rebalance */  \
559 505
                        _VRBT_MOD_XOR(_VRBT_UP(parent, field), elmdir); \
560 505
                        return (NULL);                                  \
561 505
                }                                                       \
562 7159
                sibdir = elmdir ^ _VRBT_LR;                             \
563 6654
                /* the other edge must change length */                 \
564 6654
                _VRBT_MOD_XOR(_VRBT_UP(parent, field), sibdir);         \
565 6654
                if ((_VRBT_BITS(gpar) & _VRBT_LR) == 0) {               \
566 5025
                        /* both edges now short, retry from parent */   \
567 5025
                        child = elm;                                    \
568 5025
                        elm = parent;                                   \
569 5025
                        continue;                                       \
570 5025
                }                                                       \
571 6654
                _VRBT_UP(parent, field) = gpar = _VRBT_PTR(gpar);               \
572 1629
                if (_VRBT_BITSUP(elm, field) & elmdir) {                        \
573 796
                        /*                                              \
574 796
                         * Exactly one of the edges descending from elm \
575 796
                         * is long. The long one is in the same         \
576 796
                         * direction as the edge from parent to elm,    \
577 796
                         * so change that by rotation.  The edge from   \
578 796
                         * parent to z was shortened above.  Shorten    \
579 796
                         * the long edge down from elm, and adjust      \
580 796
                         * other edge lengths based on the downward     \
581 796
                         * edges from 'child'.                          \
582 796
                         *                                              \
583 796
                         *           par                 par            \
584 796
                         *          ╱   ╲               ╱   ╲           \
585 796
                         *        elm    z             ╱     z          \
586 796
                         *       ╱  ╲                child              \
587 796
                         *      ╱  child             ╱   ╲              \
588 796
                         *     ╱   ╱  ╲            elm    ╲             \
589 796
                         *    w   ╱    ╲          ╱   ╲    y            \
590 796
                         *       x      y        w     ╲                \
591 796
                         *                              x               \
592 796
                         */                                             \
593 796
                        VRBT_ROTATE(elm, child, elmdir, field);         \
594 796
                        child_up = _VRBT_UP(child, field);              \
595 796
                        if (_VRBT_BITS(child_up) & sibdir)              \
596 796
                                _VRBT_MOD_XOR(_VRBT_UP(parent, field),  \
597 796
                                    elmdir);                            \
598 796
                        if (_VRBT_BITS(child_up) & elmdir)              \
599 796
                                _VRBT_MOD_XOR(_VRBT_UP(elm, field),     \
600 796
                                    _VRBT_LR);                          \
601 796
                        else                                            \
602 796
                                _VRBT_MOD_XOR(_VRBT_UP(elm, field),     \
603 796
                                    elmdir);                            \
604 796
                        /* if child is a leaf, don't augment elm,       \
605 796
                         * since it is restored to be a leaf again. */  \
606 796
                        if ((_VRBT_BITS(child_up) & _VRBT_LR) == 0)             \
607 796
                                elm = child;                            \
608 796
                } else                                                  \
609 1629
                        child = elm;                                    \
610 1629
                                                                        \
611 1629
                /*                                                      \
612 1629
                 * The long edge descending from 'child' points back    \
613 1629
                 * in the direction of 'parent'. Rotate to make         \
614 1629
                 * 'parent' a child of 'child', then make both edges    \
615 1629
                 * of 'child' short to rebalance.                       \
616 1629
                 *                                                      \
617 1629
                 *           par                 child                  \
618 1629
                 *          ╱   ╲               ╱     ╲                 \
619 1629
                 *         ╱     z             x       par              \
620 1629
                 *      child                         ╱   ╲             \
621 1629
                 *       ╱  ╲                        ╱     z            \
622 1629
                 *      x    ╲                      y                   \
623 1629
                 *            y                                         \
624 1629
                 */                                                     \
625 1629
                VRBT_ROTATE(parent, child, sibdir, field);              \
626 1629
                _VRBT_UP(child, field) = gpar;                          \
627 1629
                VRBT_SWAP_CHILD(head, gpar, parent, child, field);      \
628 1629
                /*                                                      \
629 1629
                 * Elements rotated down have new, smaller subtrees,    \
630 1629
                 * so update augmentation for them.                     \
631 1629
                 */                                                     \
632 1629
                if (elm != child)                                       \
633 1629
                        (void)VRBT_AUGMENT_CHECK(elm);                  \
634 1629
                (void)VRBT_AUGMENT_CHECK(parent);                               \
635 1629
                return (child);                                         \
636 6654
        } while ((parent = gpar) != NULL);                              \
637 3297
        return (NULL);                                                  \
638 3297
}
639
640
#ifndef VRBT_STRICT_HST
641
/*
642
 * In REMOVE_COLOR, the HST paper, in figure 3, in the single-rotate case, has
643
 * 'parent' with one higher rank, and then reduces its rank if 'parent' has
644
 * become a leaf.  This implementation always has the parent in its new position
645
 * with lower rank, to avoid the leaf check.  Define VRBT_STRICT_HST to 1 to get
646
 * the behavior that HST describes.
647
 */
648 30
#define VRBT_STRICT_HST 0
649
#endif
650
651
#define VRBT_GENERATE_REMOVE_COLOR(name, type, field, attr)             \
652
attr struct type *                                                      \
653
name##_VRBT_REMOVE_COLOR(struct name *head,                             \
654 973
    struct type *parent, struct type *elm)                              \
655 973
{                                                                       \
656 973
        struct type *gpar, *sib, *up;                                   \
657 973
        ptraddr_t elmdir, sibdir;                                       \
658 973
                                                                        \
659 973
        if (VRBT_RIGHT(parent, field) == elm &&                         \
660 973
            VRBT_LEFT(parent, field) == elm) {                          \
661 778
                /* Deleting a leaf that is an only-child creates a      \
662 778
                 * rank-2 leaf. Demote that leaf. */                    \
663 778
                _VRBT_UP(parent, field) = _VRBT_PTR(_VRBT_UP(parent, field));   \
664 778
                elm = parent;                                           \
665 778
                if ((parent = _VRBT_UP(elm, field)) == NULL)            \
666 778
                        return (NULL);                                  \
667 778
        }                                                               \
668 973
        do {                                                            \
669 233
                /* the rank of the tree rooted at elm shrank */         \
670 233
                gpar = _VRBT_UP(parent, field);                         \
671 233
                elmdir = VRBT_RIGHT(parent, field) == elm ? _VRBT_R : _VRBT_L; \
672 233
                _VRBT_MOD_XOR(gpar, elmdir);                            \
673 233
                if (_VRBT_BITS(gpar) & elmdir) {                        \
674 177
                        /* lengthen the parent-elm edge to rebalance */ \
675 177
                        _VRBT_UP(parent, field) = gpar;                 \
676 177
                        return (NULL);                                  \
677 177
                }                                                       \
678 233
                if (_VRBT_BITS(gpar) & _VRBT_LR) {                      \
679 32
                        /* shorten other edge, retry from parent */     \
680 32
                        _VRBT_MOD_XOR(gpar, _VRBT_LR);                  \
681 32
                        _VRBT_UP(parent, field) = gpar;                 \
682 32
                        gpar = _VRBT_PTR(gpar);                         \
683 32
                        continue;                                       \
684 32
                }                                                       \
685 56
                sibdir = elmdir ^ _VRBT_LR;                             \
686 24
                sib = _VRBT_LINK(parent, sibdir, field);                \
687 24
                up = _VRBT_UP(sib, field);                              \
688 24
                _VRBT_MOD_XOR(up, _VRBT_LR);                            \
689 24
                if ((_VRBT_BITS(up) & _VRBT_LR) == 0) {                 \
690 5
                        /* shorten edges descending from sib, retry */  \
691 5
                        _VRBT_UP(sib, field) = up;                      \
692 5
                        continue;                                       \
693 5
                }                                                       \
694 24
                if ((_VRBT_BITS(up) & sibdir) == 0) {                   \
695 2
                        /*                                              \
696 2
                         * The edge descending from 'sib' away from     \
697 2
                         * 'parent' is long.  The short edge descending \
698 2
                         * from 'sib' toward 'parent' points to 'elm*'  \
699 2
                         * Rotate to make 'sib' a child of 'elm*'       \
700 2
                         * then adjust the lengths of the edges         \
701 2
                         * descending from 'sib' and 'elm*'.            \
702 2
                         *                                              \
703 2
                         *           par                 par            \
704 2
                         *          ╱   ╲               ╱   ╲           \
705 2
                         *         ╱    sib           elm    ╲          \
706 2
                         *        ╱     / ╲                  elm*       \
707 2
                         *      elm   elm* ╲                ╱  ╲        \
708 2
                         *            ╱ ╲   ╲              ╱    ╲       \
709 2
                         *           ╱   ╲   z            ╱      ╲      \
710 2
                         *          x     y              x      sib     \
711 2
                         *                                      ╱  ╲    \
712 2
                         *                                     ╱    z   \
713 2
                         *                                    y         \
714 2
                         */                                             \
715 2
                        elm = _VRBT_LINK(sib, elmdir, field);           \
716 2
                        /* elm is a 1-child.  First rotate at elm. */   \
717 2
                        VRBT_ROTATE(sib, elm, sibdir, field);           \
718 2
                        up = _VRBT_UP(elm, field);                      \
719 2
                        _VRBT_MOD_XOR(_VRBT_UP(parent, field),          \
720 2
                            (_VRBT_BITS(up) & elmdir) ? _VRBT_LR : elmdir);     \
721 2
                        _VRBT_MOD_XOR(_VRBT_UP(sib, field),             \
722 2
                            (_VRBT_BITS(up) & sibdir) ? _VRBT_LR : sibdir);     \
723 2
                        _VRBT_MOD_OR(_VRBT_UP(elm, field), _VRBT_LR);   \
724 17
                } else {                                                \
725 17
                        if ((_VRBT_BITS(up) & elmdir) == 0 &&           \
726 17
                            VRBT_STRICT_HST && elm != NULL) {           \
727 0
                                /* if parent does not become a leaf,    \
728 0
                                   do not demote parent yet. */         \
729 0
                                _VRBT_MOD_XOR(_VRBT_UP(parent, field),  \
730 0
                                    sibdir);                            \
731 0
                                _VRBT_MOD_XOR(_VRBT_UP(sib, field),     \
732 0
                                    _VRBT_LR);                          \
733 17
                        } else if ((_VRBT_BITS(up) & elmdir) == 0) {    \
734 13
                                /* demote parent. */                    \
735 13
                                _VRBT_MOD_XOR(_VRBT_UP(parent, field),  \
736 13
                                    elmdir);                            \
737 13
                                _VRBT_MOD_XOR(_VRBT_UP(sib, field),     \
738 13
                                    sibdir);                            \
739 13
                        } else                                          \
740 17
                                _VRBT_MOD_XOR(_VRBT_UP(sib, field),     \
741 17
                                    sibdir);                            \
742 17
                        elm = sib;                                      \
743 17
                }                                                       \
744 19
                                                                        \
745 19
                /*                                                      \
746 19
                 * The edge descending from 'elm' away from 'parent'    \
747 19
                 * is short.  Rotate to make 'parent' a child of 'elm', \
748 19
                 * then lengthen the short edges descending from        \
749 19
                 * 'parent' and 'elm' to rebalance.                     \
750 19
                 *                                                      \
751 19
                 *           par                 elm                    \
752 19
                 *          ╱   ╲               ╱   ╲                   \
753 19
                 *         e     ╲             ╱     ╲                  \
754 19
                 *               elm          ╱       ╲                 \
755 19
                 *              ╱  ╲        par        s                \
756 19
                 *             ╱    ╲      ╱   ╲                        \
757 19
                 *            ╱      ╲    e     ╲                       \
758 19
                 *           x        s          x                      \
759 19
                 */                                                     \
760 19
                VRBT_ROTATE(parent, elm, elmdir, field);                        \
761 19
                VRBT_SET_PARENT(elm, gpar, field);                      \
762 19
                VRBT_SWAP_CHILD(head, gpar, parent, elm, field);                \
763 19
                /*                                                      \
764 19
                 * An element rotated down, but not into the search     \
765 19
                 * path has a new, smaller subtree, so update           \
766 19
                 * augmentation for it.                                 \
767 19
                 */                                                     \
768 19
                if (sib != elm)                                         \
769 19
                        (void)VRBT_AUGMENT_CHECK(sib);                  \
770 19
                return (parent);                                        \
771 37
        } while (elm = parent, (parent = gpar) != NULL);                \
772 224
        return (NULL);                                                  \
773 224
}
774
775 6088
#define _VRBT_AUGMENT_WALK(elm, match, field)                           \
776 6088
do {                                                                    \
777 6088
        if (match == elm)                                               \
778 6088
                match = NULL;                                           \
779 6088
} while (VRBT_AUGMENT_CHECK(elm) &&                                     \
780 6088
    (elm = VRBT_PARENT(elm, field)) != NULL)
781
782
#define VRBT_GENERATE_REMOVE(name, type, field, attr)                   \
783
attr struct type *                                                      \
784 1546
name##_VRBT_REMOVE(struct name *head, struct type *out)                 \
785 1546
{                                                                       \
786 1546
        struct type *child = NULL, *in, *opar, *parent;                 \
787 1546
                                                                        \
788 1546
        child = VRBT_LEFT(out, field);                                  \
789 1546
        in = VRBT_RIGHT(out, field);                                    \
790 1546
        opar = _VRBT_UP(out, field);                                    \
791 1546
        if (in == NULL || child == NULL) {                              \
792 1464
                in = child = (in == NULL ? child : in);                 \
793 1464
                parent = opar = _VRBT_PTR(opar);                                \
794 1464
        } else {                                                        \
795 82
                parent = in;                                            \
796 82
                while (VRBT_LEFT(in, field))                            \
797 82
                        in = VRBT_LEFT(in, field);                      \
798 82
                VRBT_SET_PARENT(child, in, field);                      \
799 82
                VRBT_LEFT(in, field) = child;                           \
800 82
                child = VRBT_RIGHT(in, field);                          \
801 82
                if (parent != in) {                                     \
802 23
                        VRBT_SET_PARENT(parent, in, field);             \
803 23
                        VRBT_RIGHT(in, field) = parent;                 \
804 23
                        parent = VRBT_PARENT(in, field);                        \
805 23
                        VRBT_LEFT(parent, field) = child;                       \
806 23
                }                                                       \
807 82
                _VRBT_UP(in, field) = opar;                             \
808 82
                opar = _VRBT_PTR(opar);                                 \
809 82
        }                                                               \
810 1546
        VRBT_SWAP_CHILD(head, opar, out, in, field);                    \
811 1546
        if (child != NULL)                                              \
812 1546
                _VRBT_UP(child, field) = parent;                                \
813 1546
        if (parent != NULL) {                                           \
814 973
                opar = name##_VRBT_REMOVE_COLOR(head, parent, child);   \
815 973
                /* if rotation has made 'parent' the root of the same   \
816 973
                 * subtree as before, don't re-augment it. */           \
817 973
                if (parent == in && VRBT_LEFT(parent, field) == NULL) { \
818 3
                        opar = NULL;                                    \
819 3
                        parent = VRBT_PARENT(parent, field);            \
820 3
                }                                                       \
821 973
                _VRBT_AUGMENT_WALK(parent, opar, field);                        \
822 973
                if (opar != NULL) {                                     \
823 1
                        /*                                              \
824 1
                         * Elements rotated into the search path have   \
825 1
                         * changed subtrees, so update augmentation for \
826 1
                         * them if AUGMENT_WALK didn't.                 \
827 1
                         */                                             \
828 1
                        (void)VRBT_AUGMENT_CHECK(opar);                 \
829 1
                        (void)VRBT_AUGMENT_CHECK(VRBT_PARENT(opar, field));     \
830 1
                }                                                       \
831 973
        }                                                               \
832 1546
        return (out);                                                   \
833 1546
}
834
835
#define VRBT_GENERATE_INSERT_FINISH(name, type, field, attr)            \
836
/* Inserts a node into the RB tree */                                   \
837
attr struct type *                                                      \
838
name##_VRBT_INSERT_FINISH(struct name *head, struct type *parent,               \
839 5115
    struct type **pptr, struct type *elm)                               \
840 5115
{                                                                       \
841 5115
        struct type *tmp = NULL;                                        \
842 5115
                                                                        \
843 5115
        VRBT_SET(elm, parent, field);                                   \
844 5115
        *pptr = elm;                                                    \
845 5115
        if (parent != NULL)                                             \
846 5115
                tmp = name##_VRBT_INSERT_COLOR(head, parent, elm);      \
847 5115
        _VRBT_AUGMENT_WALK(elm, tmp, field);                            \
848 5115
        if (tmp != NULL)                                                \
849 5115
                /*                                                      \
850 5115
                 * An element rotated into the search path has a        \
851 5115
                 * changed subtree, so update augmentation for it if    \
852 5115
                 * AUGMENT_WALK didn't.                                 \
853 5115
                 */                                                     \
854 5115
                (void)VRBT_AUGMENT_CHECK(tmp);                          \
855 5115
        return (NULL);                                                  \
856 5115
}
857
858
#define VRBT_GENERATE_INSERT(name, type, field, cmp, attr)              \
859
/* Inserts a node into the RB tree */                                   \
860
attr struct type *                                                      \
861 5921
name##_VRBT_INSERT(struct name *head, struct type *elm)                 \
862 5921
{                                                                       \
863 5921
        struct type *tmp;                                               \
864 5921
        struct type **tmpp = &VRBT_ROOT(head);                          \
865 5921
        struct type *parent = NULL;                                     \
866 5921
                                                                        \
867 22391
        while ((tmp = *tmpp) != NULL) {                                 \
868 17276
                parent = tmp;                                           \
869 17276
                __typeof(cmp(NULL, NULL)) comp = (cmp)(elm, parent);    \
870 17276
                if (comp < 0)                                           \
871 17276
                        tmpp = &VRBT_LEFT(parent, field);                       \
872 17276
                else if (comp > 0)                                      \
873 12966
                        tmpp = &VRBT_RIGHT(parent, field);              \
874 12966
                else                                                    \
875 12966
                        return (parent);                                \
876 17276
        }                                                               \
877 5921
        return (name##_VRBT_INSERT_FINISH(head, parent, tmpp, elm));    \
878 5921
}
879
880
#define VRBT_GENERATE_FIND(name, type, field, cmp, attr)                        \
881
/* Finds the node with the same key as elm */                           \
882
attr struct type *                                                      \
883 11121872
name##_VRBT_FIND(const struct name *head, const struct type *elm)                       \
884 11121872
{                                                                       \
885 11121872
        struct type *tmp = VRBT_ROOT(head);                             \
886 11121872
        __typeof(cmp(NULL, NULL)) comp;                                 \
887 99939518
        while (tmp) {                                                   \
888 99936721
                comp = cmp(elm, tmp);                                   \
889 99936721
                if (comp < 0)                                           \
890 99936721
                        tmp = VRBT_LEFT(tmp, field);                    \
891 99936721
                else if (comp > 0)                                      \
892 52875182
                        tmp = VRBT_RIGHT(tmp, field);                   \
893 52875182
                else                                                    \
894 52875182
                        return (tmp);                                   \
895 99936721
        }                                                               \
896 11121872
        return (NULL);                                                  \
897 11121872
}
898
899
#define VRBT_GENERATE_NFIND(name, type, field, cmp, attr)                       \
900
/* Finds the first node greater than or equal to the search key */      \
901
attr struct type *                                                      \
902 49
name##_VRBT_NFIND(const struct name *head, const struct type *elm)                      \
903 49
{                                                                       \
904 49
        struct type *tmp = VRBT_ROOT(head);                             \
905 49
        struct type *res = NULL;                                        \
906 49
        __typeof(cmp(NULL, NULL)) comp;                                 \
907 84
        while (tmp) {                                                   \
908 45
                comp = cmp(elm, tmp);                                   \
909 45
                if (comp < 0) {                                         \
910 35
                        res = tmp;                                      \
911 35
                        tmp = VRBT_LEFT(tmp, field);                    \
912 35
                }                                                       \
913 45
                else if (comp > 0)                                      \
914 10
                        tmp = VRBT_RIGHT(tmp, field);                   \
915 10
                else                                                    \
916 10
                        return (tmp);                                   \
917 45
        }                                                               \
918 49
        return (res);                                                   \
919 49
}
920
921
#define VRBT_GENERATE_NEXT(name, type, field, attr)                     \
922
/* ARGSUSED */                                                          \
923
attr struct type *                                                      \
924 2851
name##_VRBT_NEXT(struct type *elm)                                      \
925 2851
{                                                                       \
926 2851
        if (VRBT_RIGHT(elm, field)) {                                   \
927 1181
                elm = VRBT_RIGHT(elm, field);                           \
928 1181
                while (VRBT_LEFT(elm, field))                           \
929 1181
                        elm = VRBT_LEFT(elm, field);                    \
930 1670
        } else {                                                        \
931 2938
                while (VRBT_PARENT(elm, field) &&                               \
932 2938
                    (elm == VRBT_RIGHT(VRBT_PARENT(elm, field), field)))        \
933 1670
                        elm = VRBT_PARENT(elm, field);                  \
934 1670
                elm = VRBT_PARENT(elm, field);                          \
935 1670
        }                                                               \
936 2851
        return (elm);                                                   \
937 2851
}
938
939
#if defined(_KERNEL) && defined(DIAGNOSTIC)
940
#define _VRBT_ORDER_CHECK(cmp, lo, hi) do {                             \
941
        KASSERT((cmp)(lo, hi) < 0, ("out of order insertion"));         \
942
} while (0)
943
#else
944
#define _VRBT_ORDER_CHECK(cmp, lo, hi) do {} while (0)
945
#endif
946
947
#define VRBT_GENERATE_INSERT_NEXT(name, type, field, cmp, attr)         \
948
/* Inserts a node into the next position in the RB tree */              \
949
attr struct type *                                                      \
950
name##_VRBT_INSERT_NEXT(struct name *head,                              \
951
    struct type *elm, struct type *next)                                \
952
{                                                                       \
953
        struct type *tmp;                                               \
954
        struct type **tmpp = &VRBT_RIGHT(elm, field);                   \
955
                                                                        \
956
        _VRBT_ORDER_CHECK(cmp, elm, next);                              \
957
        if (name##_VRBT_NEXT(elm) != NULL)                              \
958
                _VRBT_ORDER_CHECK(cmp, next, name##_VRBT_NEXT(elm));    \
959
        while ((tmp = *tmpp) != NULL) {                                 \
960
                elm = tmp;                                              \
961
                tmpp = &VRBT_LEFT(elm, field);                          \
962
        }                                                               \
963
        return (name##_VRBT_INSERT_FINISH(head, elm, tmpp, next));      \
964
}
965
966
#define VRBT_GENERATE_PREV(name, type, field, attr)                     \
967
/* ARGSUSED */                                                          \
968
attr struct type *                                                      \
969 345
name##_VRBT_PREV(struct type *elm)                                      \
970 345
{                                                                       \
971 345
        if (VRBT_LEFT(elm, field)) {                                    \
972 87
                elm = VRBT_LEFT(elm, field);                            \
973 87
                while (VRBT_RIGHT(elm, field))                          \
974 87
                        elm = VRBT_RIGHT(elm, field);                   \
975 258
        } else {                                                        \
976 385
                while (VRBT_PARENT(elm, field) &&                               \
977 385
                    (elm == VRBT_LEFT(VRBT_PARENT(elm, field), field))) \
978 258
                        elm = VRBT_PARENT(elm, field);                  \
979 258
                elm = VRBT_PARENT(elm, field);                          \
980 258
        }                                                               \
981 345
        return (elm);                                                   \
982 345
}
983
984
#define VRBT_GENERATE_INSERT_PREV(name, type, field, cmp, attr)         \
985
/* Inserts a node into the prev position in the RB tree */              \
986
attr struct type *                                                      \
987
name##_VRBT_INSERT_PREV(struct name *head,                              \
988
    struct type *elm, struct type *prev)                                \
989
{                                                                       \
990
        struct type *tmp;                                               \
991
        struct type **tmpp = &VRBT_LEFT(elm, field);                    \
992
                                                                        \
993
        _VRBT_ORDER_CHECK(cmp, prev, elm);                              \
994
        if (name##_VRBT_PREV(elm) != NULL)                              \
995
                _VRBT_ORDER_CHECK(cmp, name##_VRBT_PREV(elm), prev);    \
996
        while ((tmp = *tmpp) != NULL) {                                 \
997
                elm = tmp;                                              \
998
                tmpp = &VRBT_RIGHT(elm, field);                         \
999
        }                                                               \
1000
        return (name##_VRBT_INSERT_FINISH(head, elm, tmpp, prev));      \
1001
}
1002
1003
#define VRBT_GENERATE_MINMAX(name, type, field, attr)                   \
1004
attr struct type *                                                      \
1005 19156
name##_VRBT_MINMAX(const struct name *head, int val)                            \
1006 19156
{                                                                       \
1007 19156
        struct type *tmp = VRBT_ROOT(head);                             \
1008 19156
        struct type *parent = NULL;                                     \
1009 19762
        while (tmp) {                                                   \
1010 606
                parent = tmp;                                           \
1011 606
                if (val < 0)                                            \
1012 606
                        tmp = VRBT_LEFT(tmp, field);                    \
1013 606
                else                                                    \
1014 606
                        tmp = VRBT_RIGHT(tmp, field);                   \
1015 606
        }                                                               \
1016 19156
        return (parent);                                                \
1017 19156
}
1018
1019
#define VRBT_GENERATE_REINSERT(name, type, field, cmp, attr)            \
1020
attr struct type *                                                      \
1021
name##_VRBT_REINSERT(struct name *head, struct type *elm)                       \
1022
{                                                                       \
1023
        struct type *cmpelm;                                            \
1024
        if (((cmpelm = VRBT_PREV(name, head, elm)) != NULL &&           \
1025
            cmp(cmpelm, elm) >= 0) ||                                   \
1026
            ((cmpelm = VRBT_NEXT(name, head, elm)) != NULL &&           \
1027
            cmp(elm, cmpelm) >= 0)) {                                   \
1028
                /* XXXLAS: Remove/insert is heavy handed. */            \
1029
                VRBT_REMOVE(name, head, elm);                           \
1030
                return (VRBT_INSERT(name, head, elm));                  \
1031
        }                                                               \
1032
        return (NULL);                                                  \
1033
}                                                                       \
1034
1035 19122
#define VRBT_NEGINF     -1
1036 35
#define VRBT_INF        1
1037
1038 4473
#define VRBT_INSERT(name, x, y) name##_VRBT_INSERT(x, y)
1039
#define VRBT_INSERT_NEXT(name, x, y, z) name##_VRBT_INSERT_NEXT(x, y, z)
1040
#define VRBT_INSERT_PREV(name, x, y, z) name##_VRBT_INSERT_PREV(x, y, z)
1041 1546
#define VRBT_REMOVE(name, x, y) name##_VRBT_REMOVE(x, y)
1042 11121871
#define VRBT_FIND(name, x, y)   name##_VRBT_FIND(x, y)
1043 49
#define VRBT_NFIND(name, x, y)  name##_VRBT_NFIND(x, y)
1044 1200
#define VRBT_NEXT(name, x, y)   name##_VRBT_NEXT(y)
1045 199
#define VRBT_PREV(name, x, y)   name##_VRBT_PREV(y)
1046 19122
#define VRBT_MIN(name, x)               name##_VRBT_MINMAX(x, VRBT_NEGINF)
1047 35
#define VRBT_MAX(name, x)               name##_VRBT_MINMAX(x, VRBT_INF)
1048
#define VRBT_REINSERT(name, x, y)       name##_VRBT_REINSERT(x, y)
1049
1050
#define VRBT_FOREACH(x, name, head)                                     \
1051 52
        for ((x) = VRBT_MIN(name, head);                                        \
1052 269
             (x) != NULL;                                               \
1053 217
             (x) = name##_VRBT_NEXT(x))
1054
1055
#define VRBT_FOREACH_FROM(x, name, y)                                   \
1056
        for ((x) = (y);                                                 \
1057
            ((x) != NULL) && ((y) = name##_VRBT_NEXT(x), (x) != NULL);  \
1058
             (x) = (y))
1059
1060
#define VRBT_FOREACH_SAFE(x, name, head, y)                             \
1061 19047
        for ((x) = VRBT_MIN(name, head);                                        \
1062 20481
            ((x) != NULL) && ((y) = name##_VRBT_NEXT(x), (x) != NULL);  \
1063 19047
             (x) = (y))
1064
1065
#define VRBT_FOREACH_REVERSE(x, name, head)                             \
1066 35
        for ((x) = VRBT_MAX(name, head);                                        \
1067 181
             (x) != NULL;                                               \
1068 146
             (x) = name##_VRBT_PREV(x))
1069
1070
#define VRBT_FOREACH_REVERSE_FROM(x, name, y)                           \
1071
        for ((x) = (y);                                                 \
1072
            ((x) != NULL) && ((y) = name##_VRBT_PREV(x), (x) != NULL);  \
1073
             (x) = (y))
1074
1075
#define VRBT_FOREACH_REVERSE_SAFE(x, name, head, y)                     \
1076
        for ((x) = VRBT_MAX(name, head);                                        \
1077
            ((x) != NULL) && ((y) = name##_VRBT_PREV(x), (x) != NULL);  \
1078
             (x) = (y))
1079
1080
#endif  /* _VTREE_H_ */