1fad4b12bSEdward Tomasz Napierala /*- 24d846d26SWarner Losh * SPDX-License-Identifier: BSD-2-Clause 3fad4b12bSEdward Tomasz Napierala * 4fad4b12bSEdward Tomasz Napierala * Copyright 2002 Niels Provos <provos@citi.umich.edu> 5014931a8SEdward Tomasz Napierala * Copyright 2018-2019 Netflix, Inc. 6fad4b12bSEdward Tomasz Napierala * All rights reserved. 7fad4b12bSEdward Tomasz Napierala * 8fad4b12bSEdward Tomasz Napierala * Redistribution and use in source and binary forms, with or without 9fad4b12bSEdward Tomasz Napierala * modification, are permitted provided that the following conditions 10fad4b12bSEdward Tomasz Napierala * are met: 11fad4b12bSEdward Tomasz Napierala * 1. Redistributions of source code must retain the above copyright 12fad4b12bSEdward Tomasz Napierala * notice, this list of conditions and the following disclaimer. 13fad4b12bSEdward Tomasz Napierala * 2. Redistributions in binary form must reproduce the above copyright 14fad4b12bSEdward Tomasz Napierala * notice, this list of conditions and the following disclaimer in the 15fad4b12bSEdward Tomasz Napierala * documentation and/or other materials provided with the distribution. 16fad4b12bSEdward Tomasz Napierala * 17fad4b12bSEdward Tomasz Napierala * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 18fad4b12bSEdward Tomasz Napierala * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 19fad4b12bSEdward Tomasz Napierala * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 20fad4b12bSEdward Tomasz Napierala * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 21fad4b12bSEdward Tomasz Napierala * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 22fad4b12bSEdward Tomasz Napierala * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23fad4b12bSEdward Tomasz Napierala * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24fad4b12bSEdward Tomasz Napierala * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25fad4b12bSEdward Tomasz Napierala * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 26fad4b12bSEdward Tomasz Napierala * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27fad4b12bSEdward Tomasz Napierala */ 28fad4b12bSEdward Tomasz Napierala 29fad4b12bSEdward Tomasz Napierala #ifndef _SYS_ARB_H_ 30fad4b12bSEdward Tomasz Napierala #define _SYS_ARB_H_ 31fad4b12bSEdward Tomasz Napierala 32fad4b12bSEdward Tomasz Napierala #include <sys/cdefs.h> 33fad4b12bSEdward Tomasz Napierala 34fad4b12bSEdward Tomasz Napierala /* Array-based red-black trees. */ 35fad4b12bSEdward Tomasz Napierala 36fad4b12bSEdward Tomasz Napierala #define ARB_NULLIDX -1 37fad4b12bSEdward Tomasz Napierala #define ARB_NULLCOL -1 38fad4b12bSEdward Tomasz Napierala 39fad4b12bSEdward Tomasz Napierala #define ARB_BLACK 0 40fad4b12bSEdward Tomasz Napierala #define ARB_RED 1 41fad4b12bSEdward Tomasz Napierala 42fad4b12bSEdward Tomasz Napierala #define ARB_NEGINF -1 43fad4b12bSEdward Tomasz Napierala #define ARB_INF 1 44fad4b12bSEdward Tomasz Napierala 45fad4b12bSEdward Tomasz Napierala #define ARB_HEAD(name, type, idxbits) \ 46fad4b12bSEdward Tomasz Napierala struct name { \ 47fad4b12bSEdward Tomasz Napierala int##idxbits##_t arb_curnodes; \ 48fad4b12bSEdward Tomasz Napierala int##idxbits##_t arb_maxnodes; \ 49fad4b12bSEdward Tomasz Napierala int##idxbits##_t arb_root_idx; \ 50fad4b12bSEdward Tomasz Napierala int##idxbits##_t arb_free_idx; \ 51fad4b12bSEdward Tomasz Napierala int##idxbits##_t arb_min_idx; \ 52fad4b12bSEdward Tomasz Napierala int##idxbits##_t arb_max_idx; \ 53fad4b12bSEdward Tomasz Napierala struct type arb_nodes[]; \ 54fad4b12bSEdward Tomasz Napierala } 55fad4b12bSEdward Tomasz Napierala #define ARB8_HEAD(name, type) ARB_HEAD(name, type, 8) 56fad4b12bSEdward Tomasz Napierala #define ARB16_HEAD(name, type) ARB_HEAD(name, type, 16) 57fad4b12bSEdward Tomasz Napierala #define ARB32_HEAD(name, type) ARB_HEAD(name, type, 32) 58fad4b12bSEdward Tomasz Napierala 59fad4b12bSEdward Tomasz Napierala #define ARB_ALLOCSIZE(head, maxn, x) \ 60fad4b12bSEdward Tomasz Napierala (sizeof(*head) + (maxn) * sizeof(*x)) 61fad4b12bSEdward Tomasz Napierala 62fad4b12bSEdward Tomasz Napierala #define ARB_INITIALIZER(name, maxn) \ 63fad4b12bSEdward Tomasz Napierala ((struct name){ 0, maxn, ARB_NULLIDX, ARB_NULLIDX, \ 64fad4b12bSEdward Tomasz Napierala ARB_NULLIDX, ARB_NULLIDX }) 65fad4b12bSEdward Tomasz Napierala 66fad4b12bSEdward Tomasz Napierala #define ARB_INIT(x, field, head, maxn) \ 67fad4b12bSEdward Tomasz Napierala (head)->arb_curnodes = 0; \ 68fad4b12bSEdward Tomasz Napierala (head)->arb_maxnodes = (maxn); \ 69fad4b12bSEdward Tomasz Napierala (head)->arb_root_idx = (head)->arb_free_idx = \ 70fad4b12bSEdward Tomasz Napierala (head)->arb_min_idx = (head)->arb_max_idx = ARB_NULLIDX; \ 71fad4b12bSEdward Tomasz Napierala /* The ARB_RETURNFREE() puts all entries on the free list. */ \ 72fad4b12bSEdward Tomasz Napierala ARB_ARRFOREACH_REVWCOND(x, field, head, \ 73fad4b12bSEdward Tomasz Napierala ARB_RETURNFREE(head, x, field)) 74fad4b12bSEdward Tomasz Napierala 75fad4b12bSEdward Tomasz Napierala #define ARB_ENTRY(idxbits) \ 76fad4b12bSEdward Tomasz Napierala struct { \ 77fad4b12bSEdward Tomasz Napierala int##idxbits##_t arbe_parent_idx; \ 78fad4b12bSEdward Tomasz Napierala int##idxbits##_t arbe_left_idx; \ 79fad4b12bSEdward Tomasz Napierala int##idxbits##_t arbe_right_idx; \ 80fad4b12bSEdward Tomasz Napierala int8_t arbe_color; \ 81fad4b12bSEdward Tomasz Napierala } 82fad4b12bSEdward Tomasz Napierala #define ARB8_ENTRY() ARB_ENTRY(8) 83fad4b12bSEdward Tomasz Napierala #define ARB16_ENTRY() ARB_ENTRY(16) 84fad4b12bSEdward Tomasz Napierala #define ARB32_ENTRY() ARB_ENTRY(32) 85fad4b12bSEdward Tomasz Napierala 86fad4b12bSEdward Tomasz Napierala #define ARB_ENTRYINIT(elm, field) do { \ 87fad4b12bSEdward Tomasz Napierala (elm)->field.arbe_parent_idx = \ 88fad4b12bSEdward Tomasz Napierala (elm)->field.arbe_left_idx = \ 89fad4b12bSEdward Tomasz Napierala (elm)->field.arbe_right_idx = ARB_NULLIDX; \ 90fad4b12bSEdward Tomasz Napierala (elm)->field.arbe_color = ARB_NULLCOL; \ 91fad4b12bSEdward Tomasz Napierala } while (/*CONSTCOND*/ 0) 92fad4b12bSEdward Tomasz Napierala 93fad4b12bSEdward Tomasz Napierala #define ARB_ELMTYPE(head) __typeof(&(head)->arb_nodes[0]) 94fad4b12bSEdward Tomasz Napierala #define ARB_NODES(head) (head)->arb_nodes 95fad4b12bSEdward Tomasz Napierala #define ARB_MAXNODES(head) (head)->arb_maxnodes 96fad4b12bSEdward Tomasz Napierala #define ARB_CURNODES(head) (head)->arb_curnodes 97fad4b12bSEdward Tomasz Napierala #define ARB_EMPTY(head) ((head)->arb_curnodes == 0) 98fad4b12bSEdward Tomasz Napierala #define ARB_FULL(head) ((head)->arb_curnodes >= (head)->arb_maxnodes) 99fad4b12bSEdward Tomasz Napierala #define ARB_CNODE(head, idx) \ 100fad4b12bSEdward Tomasz Napierala ((((intptr_t)(idx) <= ARB_NULLIDX) || ((idx) >= ARB_MAXNODES(head))) ? \ 101fad4b12bSEdward Tomasz Napierala NULL : ((const ARB_ELMTYPE(head))(ARB_NODES(head) + (idx)))) 102fad4b12bSEdward Tomasz Napierala #define ARB_NODE(head, idx) \ 103fad4b12bSEdward Tomasz Napierala (__DECONST(ARB_ELMTYPE(head), ARB_CNODE(head, idx))) 104fad4b12bSEdward Tomasz Napierala #define ARB_ROOT(head) ARB_NODE(head, ARB_ROOTIDX(head)) 105fad4b12bSEdward Tomasz Napierala #define ARB_LEFT(head, elm, field) ARB_NODE(head, ARB_LEFTIDX(elm, field)) 106fad4b12bSEdward Tomasz Napierala #define ARB_RIGHT(head, elm, field) ARB_NODE(head, ARB_RIGHTIDX(elm, field)) 107fad4b12bSEdward Tomasz Napierala #define ARB_PARENT(head, elm, field) ARB_NODE(head, ARB_PARENTIDX(elm, field)) 108fad4b12bSEdward Tomasz Napierala #define ARB_FREEIDX(head) (head)->arb_free_idx 109fad4b12bSEdward Tomasz Napierala #define ARB_ROOTIDX(head) (head)->arb_root_idx 110fad4b12bSEdward Tomasz Napierala #define ARB_MINIDX(head) (head)->arb_min_idx 111fad4b12bSEdward Tomasz Napierala #define ARB_MAXIDX(head) (head)->arb_max_idx 112fad4b12bSEdward Tomasz Napierala #define ARB_SELFIDX(head, elm) \ 113fad4b12bSEdward Tomasz Napierala ((elm) ? ((intptr_t)((((const uint8_t *)(elm)) - \ 114fad4b12bSEdward Tomasz Napierala ((const uint8_t *)ARB_NODES(head))) / sizeof(*(elm)))) : \ 115fad4b12bSEdward Tomasz Napierala (intptr_t)ARB_NULLIDX) 116fad4b12bSEdward Tomasz Napierala #define ARB_LEFTIDX(elm, field) (elm)->field.arbe_left_idx 117fad4b12bSEdward Tomasz Napierala #define ARB_RIGHTIDX(elm, field) (elm)->field.arbe_right_idx 118fad4b12bSEdward Tomasz Napierala #define ARB_PARENTIDX(elm, field) (elm)->field.arbe_parent_idx 119fad4b12bSEdward Tomasz Napierala #define ARB_COLOR(elm, field) (elm)->field.arbe_color 120fad4b12bSEdward Tomasz Napierala #define ARB_PREVFREE(head, elm, field) \ 121fad4b12bSEdward Tomasz Napierala ARB_NODE(head, ARB_PREVFREEIDX(elm, field)) 122fad4b12bSEdward Tomasz Napierala #define ARB_PREVFREEIDX(elm, field) ARB_LEFTIDX(elm, field) 123fad4b12bSEdward Tomasz Napierala #define ARB_NEXTFREE(head, elm, field) \ 124fad4b12bSEdward Tomasz Napierala ARB_NODE(head, ARB_NEXTFREEIDX(elm, field)) 125fad4b12bSEdward Tomasz Napierala #define ARB_NEXTFREEIDX(elm, field) ARB_RIGHTIDX(elm, field) 126fad4b12bSEdward Tomasz Napierala #define ARB_ISFREE(elm, field) (ARB_COLOR(elm, field) == ARB_NULLCOL) 127fad4b12bSEdward Tomasz Napierala 128fad4b12bSEdward Tomasz Napierala #define ARB_SET(head, elm, parent, field) do { \ 129fad4b12bSEdward Tomasz Napierala ARB_PARENTIDX(elm, field) = \ 130fad4b12bSEdward Tomasz Napierala parent ? ARB_SELFIDX(head, parent) : ARB_NULLIDX; \ 131fad4b12bSEdward Tomasz Napierala ARB_LEFTIDX(elm, field) = ARB_RIGHTIDX(elm, field) = ARB_NULLIDX; \ 132fad4b12bSEdward Tomasz Napierala ARB_COLOR(elm, field) = ARB_RED; \ 133fad4b12bSEdward Tomasz Napierala } while (/*CONSTCOND*/ 0) 134fad4b12bSEdward Tomasz Napierala 135fad4b12bSEdward Tomasz Napierala #define ARB_SET_BLACKRED(black, red, field) do { \ 136fad4b12bSEdward Tomasz Napierala ARB_COLOR(black, field) = ARB_BLACK; \ 137fad4b12bSEdward Tomasz Napierala ARB_COLOR(red, field) = ARB_RED; \ 138fad4b12bSEdward Tomasz Napierala } while (/*CONSTCOND*/ 0) 139fad4b12bSEdward Tomasz Napierala 140fad4b12bSEdward Tomasz Napierala #ifndef ARB_AUGMENT 141fad4b12bSEdward Tomasz Napierala #define ARB_AUGMENT(x) do {} while (0) 142fad4b12bSEdward Tomasz Napierala #endif 143fad4b12bSEdward Tomasz Napierala 144fad4b12bSEdward Tomasz Napierala #define ARB_ROTATE_LEFT(head, elm, tmp, field) do { \ 145fad4b12bSEdward Tomasz Napierala __typeof(ARB_RIGHTIDX(elm, field)) _tmpidx; \ 146fad4b12bSEdward Tomasz Napierala (tmp) = ARB_RIGHT(head, elm, field); \ 147fad4b12bSEdward Tomasz Napierala _tmpidx = ARB_RIGHTIDX(elm, field); \ 148fad4b12bSEdward Tomasz Napierala ARB_RIGHTIDX(elm, field) = ARB_LEFTIDX(tmp, field); \ 149fad4b12bSEdward Tomasz Napierala if (ARB_RIGHTIDX(elm, field) != ARB_NULLIDX) { \ 150fad4b12bSEdward Tomasz Napierala ARB_PARENTIDX(ARB_LEFT(head, tmp, field), field) = \ 151fad4b12bSEdward Tomasz Napierala ARB_SELFIDX(head, elm); \ 152fad4b12bSEdward Tomasz Napierala } \ 153fad4b12bSEdward Tomasz Napierala ARB_AUGMENT(elm); \ 154fad4b12bSEdward Tomasz Napierala ARB_PARENTIDX(tmp, field) = ARB_PARENTIDX(elm, field); \ 155fad4b12bSEdward Tomasz Napierala if (ARB_PARENTIDX(tmp, field) != ARB_NULLIDX) { \ 156fad4b12bSEdward Tomasz Napierala if (ARB_SELFIDX(head, elm) == \ 157fad4b12bSEdward Tomasz Napierala ARB_LEFTIDX(ARB_PARENT(head, elm, field), field)) \ 158fad4b12bSEdward Tomasz Napierala ARB_LEFTIDX(ARB_PARENT(head, elm, field), \ 159fad4b12bSEdward Tomasz Napierala field) = _tmpidx; \ 160fad4b12bSEdward Tomasz Napierala else \ 161fad4b12bSEdward Tomasz Napierala ARB_RIGHTIDX(ARB_PARENT(head, elm, field), \ 162fad4b12bSEdward Tomasz Napierala field) = _tmpidx; \ 163fad4b12bSEdward Tomasz Napierala } else \ 164fad4b12bSEdward Tomasz Napierala ARB_ROOTIDX(head) = _tmpidx; \ 165fad4b12bSEdward Tomasz Napierala ARB_LEFTIDX(tmp, field) = ARB_SELFIDX(head, elm); \ 166fad4b12bSEdward Tomasz Napierala ARB_PARENTIDX(elm, field) = _tmpidx; \ 167fad4b12bSEdward Tomasz Napierala ARB_AUGMENT(tmp); \ 168fad4b12bSEdward Tomasz Napierala if (ARB_PARENTIDX(tmp, field) != ARB_NULLIDX) \ 169fad4b12bSEdward Tomasz Napierala ARB_AUGMENT(ARB_PARENT(head, tmp, field)); \ 170fad4b12bSEdward Tomasz Napierala } while (/*CONSTCOND*/ 0) 171fad4b12bSEdward Tomasz Napierala 172fad4b12bSEdward Tomasz Napierala #define ARB_ROTATE_RIGHT(head, elm, tmp, field) do { \ 173fad4b12bSEdward Tomasz Napierala __typeof(ARB_LEFTIDX(elm, field)) _tmpidx; \ 174fad4b12bSEdward Tomasz Napierala (tmp) = ARB_LEFT(head, elm, field); \ 175fad4b12bSEdward Tomasz Napierala _tmpidx = ARB_LEFTIDX(elm, field); \ 176fad4b12bSEdward Tomasz Napierala ARB_LEFTIDX(elm, field) = ARB_RIGHTIDX(tmp, field); \ 177fad4b12bSEdward Tomasz Napierala if (ARB_LEFTIDX(elm, field) != ARB_NULLIDX) { \ 178fad4b12bSEdward Tomasz Napierala ARB_PARENTIDX(ARB_RIGHT(head, tmp, field), field) = \ 179fad4b12bSEdward Tomasz Napierala ARB_SELFIDX(head, elm); \ 180fad4b12bSEdward Tomasz Napierala } \ 181fad4b12bSEdward Tomasz Napierala ARB_AUGMENT(elm); \ 182fad4b12bSEdward Tomasz Napierala ARB_PARENTIDX(tmp, field) = ARB_PARENTIDX(elm, field); \ 183fad4b12bSEdward Tomasz Napierala if (ARB_PARENTIDX(tmp, field) != ARB_NULLIDX) { \ 184fad4b12bSEdward Tomasz Napierala if (ARB_SELFIDX(head, elm) == \ 185fad4b12bSEdward Tomasz Napierala ARB_LEFTIDX(ARB_PARENT(head, elm, field), field)) \ 186fad4b12bSEdward Tomasz Napierala ARB_LEFTIDX(ARB_PARENT(head, elm, field), \ 187fad4b12bSEdward Tomasz Napierala field) = _tmpidx; \ 188fad4b12bSEdward Tomasz Napierala else \ 189fad4b12bSEdward Tomasz Napierala ARB_RIGHTIDX(ARB_PARENT(head, elm, field), \ 190fad4b12bSEdward Tomasz Napierala field) = _tmpidx; \ 191fad4b12bSEdward Tomasz Napierala } else \ 192fad4b12bSEdward Tomasz Napierala ARB_ROOTIDX(head) = _tmpidx; \ 193fad4b12bSEdward Tomasz Napierala ARB_RIGHTIDX(tmp, field) = ARB_SELFIDX(head, elm); \ 194fad4b12bSEdward Tomasz Napierala ARB_PARENTIDX(elm, field) = _tmpidx; \ 195fad4b12bSEdward Tomasz Napierala ARB_AUGMENT(tmp); \ 196fad4b12bSEdward Tomasz Napierala if (ARB_PARENTIDX(tmp, field) != ARB_NULLIDX) \ 197fad4b12bSEdward Tomasz Napierala ARB_AUGMENT(ARB_PARENT(head, tmp, field)); \ 198fad4b12bSEdward Tomasz Napierala } while (/*CONSTCOND*/ 0) 199fad4b12bSEdward Tomasz Napierala 200fad4b12bSEdward Tomasz Napierala #define ARB_RETURNFREE(head, elm, field) \ 201fad4b12bSEdward Tomasz Napierala ({ \ 202fad4b12bSEdward Tomasz Napierala ARB_COLOR(elm, field) = ARB_NULLCOL; \ 203fad4b12bSEdward Tomasz Napierala ARB_NEXTFREEIDX(elm, field) = ARB_FREEIDX(head); \ 204fad4b12bSEdward Tomasz Napierala ARB_FREEIDX(head) = ARB_SELFIDX(head, elm); \ 205fad4b12bSEdward Tomasz Napierala elm; \ 206fad4b12bSEdward Tomasz Napierala }) 207fad4b12bSEdward Tomasz Napierala 208fad4b12bSEdward Tomasz Napierala #define ARB_GETFREEAT(head, field, fidx) \ 209fad4b12bSEdward Tomasz Napierala ({ \ 210fad4b12bSEdward Tomasz Napierala __typeof(ARB_NODE(head, 0)) _elm, _prevelm; \ 211fad4b12bSEdward Tomasz Napierala int _idx = fidx; \ 212fad4b12bSEdward Tomasz Napierala if (ARB_FREEIDX(head) == ARB_NULLIDX && !ARB_FULL(head)) { \ 213fad4b12bSEdward Tomasz Napierala /* Populate the free list. */ \ 214fad4b12bSEdward Tomasz Napierala ARB_ARRFOREACH_REVERSE(_elm, field, head) { \ 215fad4b12bSEdward Tomasz Napierala if (ARB_ISFREE(_elm, field)) \ 216fad4b12bSEdward Tomasz Napierala ARB_RETURNFREE(head, _elm, field); \ 217fad4b12bSEdward Tomasz Napierala } \ 218fad4b12bSEdward Tomasz Napierala } \ 219fad4b12bSEdward Tomasz Napierala _elm = _prevelm = ARB_NODE(head, ARB_FREEIDX(head)); \ 220fad4b12bSEdward Tomasz Napierala for (; _idx > 0 && _elm != NULL; _idx--, _prevelm = _elm) \ 221fad4b12bSEdward Tomasz Napierala _elm = ARB_NODE(head, ARB_NEXTFREEIDX(_elm, field)); \ 222fad4b12bSEdward Tomasz Napierala if (_elm) { \ 223fad4b12bSEdward Tomasz Napierala if (fidx == 0) \ 224fad4b12bSEdward Tomasz Napierala ARB_FREEIDX(head) = \ 225fad4b12bSEdward Tomasz Napierala ARB_NEXTFREEIDX(_elm, field); \ 226fad4b12bSEdward Tomasz Napierala else \ 227fad4b12bSEdward Tomasz Napierala ARB_NEXTFREEIDX(_prevelm, field) = \ 228fad4b12bSEdward Tomasz Napierala ARB_NEXTFREEIDX(_elm, field); \ 229fad4b12bSEdward Tomasz Napierala } \ 230fad4b12bSEdward Tomasz Napierala _elm; \ 231fad4b12bSEdward Tomasz Napierala }) 232fad4b12bSEdward Tomasz Napierala #define ARB_GETFREE(head, field) ARB_GETFREEAT(head, field, 0) 233fad4b12bSEdward Tomasz Napierala 234fad4b12bSEdward Tomasz Napierala /* Generates prototypes and inline functions */ 235fad4b12bSEdward Tomasz Napierala #define ARB_PROTOTYPE(name, type, field, cmp) \ 236fad4b12bSEdward Tomasz Napierala ARB_PROTOTYPE_INTERNAL(name, type, field, cmp,) 237fad4b12bSEdward Tomasz Napierala #define ARB_PROTOTYPE_STATIC(name, type, field, cmp) \ 238fad4b12bSEdward Tomasz Napierala ARB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static) 239fad4b12bSEdward Tomasz Napierala #define ARB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ 240fad4b12bSEdward Tomasz Napierala ARB_PROTOTYPE_INSERT_COLOR(name, type, attr); \ 241fad4b12bSEdward Tomasz Napierala ARB_PROTOTYPE_REMOVE_COLOR(name, type, attr); \ 242fad4b12bSEdward Tomasz Napierala ARB_PROTOTYPE_INSERT(name, type, attr); \ 243fad4b12bSEdward Tomasz Napierala ARB_PROTOTYPE_REMOVE(name, type, attr); \ 244fad4b12bSEdward Tomasz Napierala ARB_PROTOTYPE_CFIND(name, type, attr); \ 245fad4b12bSEdward Tomasz Napierala ARB_PROTOTYPE_FIND(name, type, attr); \ 246fad4b12bSEdward Tomasz Napierala ARB_PROTOTYPE_NFIND(name, type, attr); \ 247fad4b12bSEdward Tomasz Napierala ARB_PROTOTYPE_CNEXT(name, type, attr); \ 248fad4b12bSEdward Tomasz Napierala ARB_PROTOTYPE_NEXT(name, type, attr); \ 249fad4b12bSEdward Tomasz Napierala ARB_PROTOTYPE_CPREV(name, type, attr); \ 250fad4b12bSEdward Tomasz Napierala ARB_PROTOTYPE_PREV(name, type, attr); \ 251fad4b12bSEdward Tomasz Napierala ARB_PROTOTYPE_CMINMAX(name, type, attr); \ 252fad4b12bSEdward Tomasz Napierala ARB_PROTOTYPE_MINMAX(name, type, attr); \ 253a5adff0eSEdward Tomasz Napierala ARB_PROTOTYPE_REINSERT(name, type, attr); 254fad4b12bSEdward Tomasz Napierala #define ARB_PROTOTYPE_INSERT_COLOR(name, type, attr) \ 255fad4b12bSEdward Tomasz Napierala attr void name##_ARB_INSERT_COLOR(struct name *, struct type *) 256fad4b12bSEdward Tomasz Napierala #define ARB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \ 257fad4b12bSEdward Tomasz Napierala attr void name##_ARB_REMOVE_COLOR(struct name *, struct type *, struct type *) 258fad4b12bSEdward Tomasz Napierala #define ARB_PROTOTYPE_REMOVE(name, type, attr) \ 259fad4b12bSEdward Tomasz Napierala attr struct type *name##_ARB_REMOVE(struct name *, struct type *) 260fad4b12bSEdward Tomasz Napierala #define ARB_PROTOTYPE_INSERT(name, type, attr) \ 261fad4b12bSEdward Tomasz Napierala attr struct type *name##_ARB_INSERT(struct name *, struct type *) 262fad4b12bSEdward Tomasz Napierala #define ARB_PROTOTYPE_CFIND(name, type, attr) \ 263fad4b12bSEdward Tomasz Napierala attr const struct type *name##_ARB_CFIND(const struct name *, \ 264fad4b12bSEdward Tomasz Napierala const struct type *) 265fad4b12bSEdward Tomasz Napierala #define ARB_PROTOTYPE_FIND(name, type, attr) \ 266fad4b12bSEdward Tomasz Napierala attr struct type *name##_ARB_FIND(const struct name *, \ 267fad4b12bSEdward Tomasz Napierala const struct type *) 268fad4b12bSEdward Tomasz Napierala #define ARB_PROTOTYPE_NFIND(name, type, attr) \ 269fad4b12bSEdward Tomasz Napierala attr struct type *name##_ARB_NFIND(struct name *, struct type *) 270fad4b12bSEdward Tomasz Napierala #define ARB_PROTOTYPE_CNFIND(name, type, attr) \ 271fad4b12bSEdward Tomasz Napierala attr const struct type *name##_ARB_CNFIND(const struct name *, \ 272fad4b12bSEdward Tomasz Napierala const struct type *) 273fad4b12bSEdward Tomasz Napierala #define ARB_PROTOTYPE_CNEXT(name, type, attr) \ 274fad4b12bSEdward Tomasz Napierala attr const struct type *name##_ARB_CNEXT(const struct name *head,\ 275fad4b12bSEdward Tomasz Napierala const struct type *) 276fad4b12bSEdward Tomasz Napierala #define ARB_PROTOTYPE_NEXT(name, type, attr) \ 277fad4b12bSEdward Tomasz Napierala attr struct type *name##_ARB_NEXT(const struct name *, \ 278fad4b12bSEdward Tomasz Napierala const struct type *) 279fad4b12bSEdward Tomasz Napierala #define ARB_PROTOTYPE_CPREV(name, type, attr) \ 280fad4b12bSEdward Tomasz Napierala attr const struct type *name##_ARB_CPREV(const struct name *, \ 281fad4b12bSEdward Tomasz Napierala const struct type *) 282fad4b12bSEdward Tomasz Napierala #define ARB_PROTOTYPE_PREV(name, type, attr) \ 283fad4b12bSEdward Tomasz Napierala attr struct type *name##_ARB_PREV(const struct name *, \ 284fad4b12bSEdward Tomasz Napierala const struct type *) 285fad4b12bSEdward Tomasz Napierala #define ARB_PROTOTYPE_CMINMAX(name, type, attr) \ 286fad4b12bSEdward Tomasz Napierala attr const struct type *name##_ARB_CMINMAX(const struct name *, int) 287fad4b12bSEdward Tomasz Napierala #define ARB_PROTOTYPE_MINMAX(name, type, attr) \ 288fad4b12bSEdward Tomasz Napierala attr struct type *name##_ARB_MINMAX(const struct name *, int) 289a5adff0eSEdward Tomasz Napierala #define ARB_PROTOTYPE_REINSERT(name, type, attr) \ 290a5adff0eSEdward Tomasz Napierala attr struct type *name##_ARB_REINSERT(struct name *, struct type *) 291fad4b12bSEdward Tomasz Napierala 292fad4b12bSEdward Tomasz Napierala #define ARB_GENERATE(name, type, field, cmp) \ 293fad4b12bSEdward Tomasz Napierala ARB_GENERATE_INTERNAL(name, type, field, cmp,) 294fad4b12bSEdward Tomasz Napierala #define ARB_GENERATE_STATIC(name, type, field, cmp) \ 295fad4b12bSEdward Tomasz Napierala ARB_GENERATE_INTERNAL(name, type, field, cmp, __unused static) 296fad4b12bSEdward Tomasz Napierala #define ARB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ 297fad4b12bSEdward Tomasz Napierala ARB_GENERATE_INSERT_COLOR(name, type, field, attr) \ 298fad4b12bSEdward Tomasz Napierala ARB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ 299fad4b12bSEdward Tomasz Napierala ARB_GENERATE_INSERT(name, type, field, cmp, attr) \ 300fad4b12bSEdward Tomasz Napierala ARB_GENERATE_REMOVE(name, type, field, attr) \ 301fad4b12bSEdward Tomasz Napierala ARB_GENERATE_CFIND(name, type, field, cmp, attr) \ 302fad4b12bSEdward Tomasz Napierala ARB_GENERATE_FIND(name, type, field, cmp, attr) \ 303fad4b12bSEdward Tomasz Napierala ARB_GENERATE_CNEXT(name, type, field, attr) \ 304fad4b12bSEdward Tomasz Napierala ARB_GENERATE_NEXT(name, type, field, attr) \ 305fad4b12bSEdward Tomasz Napierala ARB_GENERATE_CPREV(name, type, field, attr) \ 306fad4b12bSEdward Tomasz Napierala ARB_GENERATE_PREV(name, type, field, attr) \ 307fad4b12bSEdward Tomasz Napierala ARB_GENERATE_CMINMAX(name, type, field, attr) \ 308fad4b12bSEdward Tomasz Napierala ARB_GENERATE_MINMAX(name, type, field, attr) \ 309a5adff0eSEdward Tomasz Napierala ARB_GENERATE_REINSERT(name, type, field, cmp, attr) 310fad4b12bSEdward Tomasz Napierala 311fad4b12bSEdward Tomasz Napierala #define ARB_GENERATE_INSERT_COLOR(name, type, field, attr) \ 312fad4b12bSEdward Tomasz Napierala attr void \ 313fad4b12bSEdward Tomasz Napierala name##_ARB_INSERT_COLOR(struct name *head, struct type *elm) \ 314fad4b12bSEdward Tomasz Napierala { \ 315fad4b12bSEdward Tomasz Napierala struct type *parent, *gparent, *tmp; \ 316fad4b12bSEdward Tomasz Napierala while ((parent = ARB_PARENT(head, elm, field)) != NULL && \ 317fad4b12bSEdward Tomasz Napierala ARB_COLOR(parent, field) == ARB_RED) { \ 318fad4b12bSEdward Tomasz Napierala gparent = ARB_PARENT(head, parent, field); \ 319fad4b12bSEdward Tomasz Napierala if (parent == ARB_LEFT(head, gparent, field)) { \ 320fad4b12bSEdward Tomasz Napierala tmp = ARB_RIGHT(head, gparent, field); \ 321fad4b12bSEdward Tomasz Napierala if (tmp && ARB_COLOR(tmp, field) == ARB_RED) { \ 322fad4b12bSEdward Tomasz Napierala ARB_COLOR(tmp, field) = ARB_BLACK; \ 323fad4b12bSEdward Tomasz Napierala ARB_SET_BLACKRED(parent, gparent, field); \ 324fad4b12bSEdward Tomasz Napierala elm = gparent; \ 325fad4b12bSEdward Tomasz Napierala continue; \ 326fad4b12bSEdward Tomasz Napierala } \ 327fad4b12bSEdward Tomasz Napierala if (ARB_RIGHT(head, parent, field) == elm) { \ 328fad4b12bSEdward Tomasz Napierala ARB_ROTATE_LEFT(head, parent, tmp, field); \ 329fad4b12bSEdward Tomasz Napierala tmp = parent; \ 330fad4b12bSEdward Tomasz Napierala parent = elm; \ 331fad4b12bSEdward Tomasz Napierala elm = tmp; \ 332fad4b12bSEdward Tomasz Napierala } \ 333fad4b12bSEdward Tomasz Napierala ARB_SET_BLACKRED(parent, gparent, field); \ 334fad4b12bSEdward Tomasz Napierala ARB_ROTATE_RIGHT(head, gparent, tmp, field); \ 335fad4b12bSEdward Tomasz Napierala } else { \ 336fad4b12bSEdward Tomasz Napierala tmp = ARB_LEFT(head, gparent, field); \ 337fad4b12bSEdward Tomasz Napierala if (tmp && ARB_COLOR(tmp, field) == ARB_RED) { \ 338fad4b12bSEdward Tomasz Napierala ARB_COLOR(tmp, field) = ARB_BLACK; \ 339fad4b12bSEdward Tomasz Napierala ARB_SET_BLACKRED(parent, gparent, field); \ 340fad4b12bSEdward Tomasz Napierala elm = gparent; \ 341fad4b12bSEdward Tomasz Napierala continue; \ 342fad4b12bSEdward Tomasz Napierala } \ 343fad4b12bSEdward Tomasz Napierala if (ARB_LEFT(head, parent, field) == elm) { \ 344fad4b12bSEdward Tomasz Napierala ARB_ROTATE_RIGHT(head, parent, tmp, field); \ 345fad4b12bSEdward Tomasz Napierala tmp = parent; \ 346fad4b12bSEdward Tomasz Napierala parent = elm; \ 347fad4b12bSEdward Tomasz Napierala elm = tmp; \ 348fad4b12bSEdward Tomasz Napierala } \ 349fad4b12bSEdward Tomasz Napierala ARB_SET_BLACKRED(parent, gparent, field); \ 350fad4b12bSEdward Tomasz Napierala ARB_ROTATE_LEFT(head, gparent, tmp, field); \ 351fad4b12bSEdward Tomasz Napierala } \ 352fad4b12bSEdward Tomasz Napierala } \ 353fad4b12bSEdward Tomasz Napierala ARB_COLOR(ARB_ROOT(head), field) = ARB_BLACK; \ 354fad4b12bSEdward Tomasz Napierala } 355fad4b12bSEdward Tomasz Napierala 356fad4b12bSEdward Tomasz Napierala #define ARB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ 357fad4b12bSEdward Tomasz Napierala attr void \ 358fad4b12bSEdward Tomasz Napierala name##_ARB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ 359fad4b12bSEdward Tomasz Napierala { \ 360fad4b12bSEdward Tomasz Napierala struct type *tmp; \ 361fad4b12bSEdward Tomasz Napierala while ((elm == NULL || ARB_COLOR(elm, field) == ARB_BLACK) && \ 362fad4b12bSEdward Tomasz Napierala elm != ARB_ROOT(head)) { \ 363fad4b12bSEdward Tomasz Napierala if (ARB_LEFT(head, parent, field) == elm) { \ 364fad4b12bSEdward Tomasz Napierala tmp = ARB_RIGHT(head, parent, field); \ 365fad4b12bSEdward Tomasz Napierala if (ARB_COLOR(tmp, field) == ARB_RED) { \ 366fad4b12bSEdward Tomasz Napierala ARB_SET_BLACKRED(tmp, parent, field); \ 367fad4b12bSEdward Tomasz Napierala ARB_ROTATE_LEFT(head, parent, tmp, field); \ 368fad4b12bSEdward Tomasz Napierala tmp = ARB_RIGHT(head, parent, field); \ 369fad4b12bSEdward Tomasz Napierala } \ 370fad4b12bSEdward Tomasz Napierala if ((ARB_LEFT(head, tmp, field) == NULL || \ 371fad4b12bSEdward Tomasz Napierala ARB_COLOR(ARB_LEFT(head, tmp, field), field) == ARB_BLACK) && \ 372fad4b12bSEdward Tomasz Napierala (ARB_RIGHT(head, tmp, field) == NULL || \ 373fad4b12bSEdward Tomasz Napierala ARB_COLOR(ARB_RIGHT(head, tmp, field), field) == ARB_BLACK)) { \ 374fad4b12bSEdward Tomasz Napierala ARB_COLOR(tmp, field) = ARB_RED; \ 375fad4b12bSEdward Tomasz Napierala elm = parent; \ 376fad4b12bSEdward Tomasz Napierala parent = ARB_PARENT(head, elm, field); \ 377fad4b12bSEdward Tomasz Napierala } else { \ 378fad4b12bSEdward Tomasz Napierala if (ARB_RIGHT(head, tmp, field) == NULL || \ 379fad4b12bSEdward Tomasz Napierala ARB_COLOR(ARB_RIGHT(head, tmp, field), field) == ARB_BLACK) { \ 380fad4b12bSEdward Tomasz Napierala struct type *oleft; \ 381fad4b12bSEdward Tomasz Napierala if ((oleft = ARB_LEFT(head, tmp, field)) \ 382fad4b12bSEdward Tomasz Napierala != NULL) \ 383fad4b12bSEdward Tomasz Napierala ARB_COLOR(oleft, field) = ARB_BLACK; \ 384fad4b12bSEdward Tomasz Napierala ARB_COLOR(tmp, field) = ARB_RED; \ 385fad4b12bSEdward Tomasz Napierala ARB_ROTATE_RIGHT(head, tmp, oleft, field); \ 386fad4b12bSEdward Tomasz Napierala tmp = ARB_RIGHT(head, parent, field); \ 387fad4b12bSEdward Tomasz Napierala } \ 388fad4b12bSEdward Tomasz Napierala ARB_COLOR(tmp, field) = ARB_COLOR(parent, field); \ 389fad4b12bSEdward Tomasz Napierala ARB_COLOR(parent, field) = ARB_BLACK; \ 390fad4b12bSEdward Tomasz Napierala if (ARB_RIGHT(head, tmp, field)) \ 391fad4b12bSEdward Tomasz Napierala ARB_COLOR(ARB_RIGHT(head, tmp, field), field) = ARB_BLACK; \ 392fad4b12bSEdward Tomasz Napierala ARB_ROTATE_LEFT(head, parent, tmp, field); \ 393fad4b12bSEdward Tomasz Napierala elm = ARB_ROOT(head); \ 394fad4b12bSEdward Tomasz Napierala break; \ 395fad4b12bSEdward Tomasz Napierala } \ 396fad4b12bSEdward Tomasz Napierala } else { \ 397fad4b12bSEdward Tomasz Napierala tmp = ARB_LEFT(head, parent, field); \ 398fad4b12bSEdward Tomasz Napierala if (ARB_COLOR(tmp, field) == ARB_RED) { \ 399fad4b12bSEdward Tomasz Napierala ARB_SET_BLACKRED(tmp, parent, field); \ 400fad4b12bSEdward Tomasz Napierala ARB_ROTATE_RIGHT(head, parent, tmp, field); \ 401fad4b12bSEdward Tomasz Napierala tmp = ARB_LEFT(head, parent, field); \ 402fad4b12bSEdward Tomasz Napierala } \ 403fad4b12bSEdward Tomasz Napierala if ((ARB_LEFT(head, tmp, field) == NULL || \ 404fad4b12bSEdward Tomasz Napierala ARB_COLOR(ARB_LEFT(head, tmp, field), field) == ARB_BLACK) && \ 405fad4b12bSEdward Tomasz Napierala (ARB_RIGHT(head, tmp, field) == NULL || \ 406fad4b12bSEdward Tomasz Napierala ARB_COLOR(ARB_RIGHT(head, tmp, field), field) == ARB_BLACK)) { \ 407fad4b12bSEdward Tomasz Napierala ARB_COLOR(tmp, field) = ARB_RED; \ 408fad4b12bSEdward Tomasz Napierala elm = parent; \ 409fad4b12bSEdward Tomasz Napierala parent = ARB_PARENT(head, elm, field); \ 410fad4b12bSEdward Tomasz Napierala } else { \ 411fad4b12bSEdward Tomasz Napierala if (ARB_LEFT(head, tmp, field) == NULL || \ 412fad4b12bSEdward Tomasz Napierala ARB_COLOR(ARB_LEFT(head, tmp, field), field) == ARB_BLACK) { \ 413fad4b12bSEdward Tomasz Napierala struct type *oright; \ 414fad4b12bSEdward Tomasz Napierala if ((oright = ARB_RIGHT(head, tmp, field)) \ 415fad4b12bSEdward Tomasz Napierala != NULL) \ 416fad4b12bSEdward Tomasz Napierala ARB_COLOR(oright, field) = ARB_BLACK; \ 417fad4b12bSEdward Tomasz Napierala ARB_COLOR(tmp, field) = ARB_RED; \ 418fad4b12bSEdward Tomasz Napierala ARB_ROTATE_LEFT(head, tmp, oright, field); \ 419fad4b12bSEdward Tomasz Napierala tmp = ARB_LEFT(head, parent, field); \ 420fad4b12bSEdward Tomasz Napierala } \ 421fad4b12bSEdward Tomasz Napierala ARB_COLOR(tmp, field) = ARB_COLOR(parent, field); \ 422fad4b12bSEdward Tomasz Napierala ARB_COLOR(parent, field) = ARB_BLACK; \ 423fad4b12bSEdward Tomasz Napierala if (ARB_LEFT(head, tmp, field)) \ 424fad4b12bSEdward Tomasz Napierala ARB_COLOR(ARB_LEFT(head, tmp, field), field) = ARB_BLACK; \ 425fad4b12bSEdward Tomasz Napierala ARB_ROTATE_RIGHT(head, parent, tmp, field); \ 426fad4b12bSEdward Tomasz Napierala elm = ARB_ROOT(head); \ 427fad4b12bSEdward Tomasz Napierala break; \ 428fad4b12bSEdward Tomasz Napierala } \ 429fad4b12bSEdward Tomasz Napierala } \ 430fad4b12bSEdward Tomasz Napierala } \ 431fad4b12bSEdward Tomasz Napierala if (elm) \ 432fad4b12bSEdward Tomasz Napierala ARB_COLOR(elm, field) = ARB_BLACK; \ 433fad4b12bSEdward Tomasz Napierala } 434fad4b12bSEdward Tomasz Napierala 435fad4b12bSEdward Tomasz Napierala #define ARB_GENERATE_REMOVE(name, type, field, attr) \ 436fad4b12bSEdward Tomasz Napierala attr struct type * \ 437fad4b12bSEdward Tomasz Napierala name##_ARB_REMOVE(struct name *head, struct type *elm) \ 438fad4b12bSEdward Tomasz Napierala { \ 439fad4b12bSEdward Tomasz Napierala struct type *child, *parent, *old = elm; \ 440fad4b12bSEdward Tomasz Napierala int color; \ 441fad4b12bSEdward Tomasz Napierala if (ARB_LEFT(head, elm, field) == NULL) \ 442fad4b12bSEdward Tomasz Napierala child = ARB_RIGHT(head, elm, field); \ 443fad4b12bSEdward Tomasz Napierala else if (ARB_RIGHT(head, elm, field) == NULL) \ 444fad4b12bSEdward Tomasz Napierala child = ARB_LEFT(head, elm, field); \ 445fad4b12bSEdward Tomasz Napierala else { \ 446fad4b12bSEdward Tomasz Napierala struct type *left; \ 447fad4b12bSEdward Tomasz Napierala elm = ARB_RIGHT(head, elm, field); \ 448fad4b12bSEdward Tomasz Napierala while ((left = ARB_LEFT(head, elm, field)) != NULL) \ 449fad4b12bSEdward Tomasz Napierala elm = left; \ 450fad4b12bSEdward Tomasz Napierala child = ARB_RIGHT(head, elm, field); \ 451fad4b12bSEdward Tomasz Napierala parent = ARB_PARENT(head, elm, field); \ 452fad4b12bSEdward Tomasz Napierala color = ARB_COLOR(elm, field); \ 453fad4b12bSEdward Tomasz Napierala if (child) \ 454fad4b12bSEdward Tomasz Napierala ARB_PARENTIDX(child, field) = \ 455fad4b12bSEdward Tomasz Napierala ARB_SELFIDX(head, parent); \ 456fad4b12bSEdward Tomasz Napierala if (parent) { \ 457fad4b12bSEdward Tomasz Napierala if (ARB_LEFT(head, parent, field) == elm) \ 458fad4b12bSEdward Tomasz Napierala ARB_LEFTIDX(parent, field) = \ 459fad4b12bSEdward Tomasz Napierala ARB_SELFIDX(head, child); \ 460fad4b12bSEdward Tomasz Napierala else \ 461fad4b12bSEdward Tomasz Napierala ARB_RIGHTIDX(parent, field) = \ 462fad4b12bSEdward Tomasz Napierala ARB_SELFIDX(head, child); \ 463fad4b12bSEdward Tomasz Napierala ARB_AUGMENT(parent); \ 464fad4b12bSEdward Tomasz Napierala } else \ 465fad4b12bSEdward Tomasz Napierala ARB_ROOTIDX(head) = ARB_SELFIDX(head, child); \ 466fad4b12bSEdward Tomasz Napierala if (ARB_PARENT(head, elm, field) == old) \ 467fad4b12bSEdward Tomasz Napierala parent = elm; \ 468fad4b12bSEdward Tomasz Napierala (elm)->field = (old)->field; \ 469fad4b12bSEdward Tomasz Napierala if (ARB_PARENT(head, old, field)) { \ 470fad4b12bSEdward Tomasz Napierala if (ARB_LEFT(head, ARB_PARENT(head, old, field), \ 471fad4b12bSEdward Tomasz Napierala field) == old) \ 472fad4b12bSEdward Tomasz Napierala ARB_LEFTIDX(ARB_PARENT(head, old, field), \ 473fad4b12bSEdward Tomasz Napierala field) = ARB_SELFIDX(head, elm); \ 474fad4b12bSEdward Tomasz Napierala else \ 475fad4b12bSEdward Tomasz Napierala ARB_RIGHTIDX(ARB_PARENT(head, old, field),\ 476fad4b12bSEdward Tomasz Napierala field) = ARB_SELFIDX(head, elm); \ 477fad4b12bSEdward Tomasz Napierala ARB_AUGMENT(ARB_PARENT(head, old, field)); \ 478fad4b12bSEdward Tomasz Napierala } else \ 479fad4b12bSEdward Tomasz Napierala ARB_ROOTIDX(head) = ARB_SELFIDX(head, elm); \ 480fad4b12bSEdward Tomasz Napierala ARB_PARENTIDX(ARB_LEFT(head, old, field), field) = \ 481fad4b12bSEdward Tomasz Napierala ARB_SELFIDX(head, elm); \ 482fad4b12bSEdward Tomasz Napierala if (ARB_RIGHT(head, old, field)) \ 483fad4b12bSEdward Tomasz Napierala ARB_PARENTIDX(ARB_RIGHT(head, old, field), \ 484fad4b12bSEdward Tomasz Napierala field) = ARB_SELFIDX(head, elm); \ 485fad4b12bSEdward Tomasz Napierala if (parent) { \ 486fad4b12bSEdward Tomasz Napierala left = parent; \ 487fad4b12bSEdward Tomasz Napierala do { \ 488fad4b12bSEdward Tomasz Napierala ARB_AUGMENT(left); \ 489fad4b12bSEdward Tomasz Napierala } while ((left = ARB_PARENT(head, left, field)) \ 490fad4b12bSEdward Tomasz Napierala != NULL); \ 491fad4b12bSEdward Tomasz Napierala } \ 492fad4b12bSEdward Tomasz Napierala goto color; \ 493fad4b12bSEdward Tomasz Napierala } \ 494fad4b12bSEdward Tomasz Napierala parent = ARB_PARENT(head, elm, field); \ 495fad4b12bSEdward Tomasz Napierala color = ARB_COLOR(elm, field); \ 496fad4b12bSEdward Tomasz Napierala if (child) \ 497fad4b12bSEdward Tomasz Napierala ARB_PARENTIDX(child, field) = ARB_SELFIDX(head, parent);\ 498fad4b12bSEdward Tomasz Napierala if (parent) { \ 499fad4b12bSEdward Tomasz Napierala if (ARB_LEFT(head, parent, field) == elm) \ 500fad4b12bSEdward Tomasz Napierala ARB_LEFTIDX(parent, field) = \ 501fad4b12bSEdward Tomasz Napierala ARB_SELFIDX(head, child); \ 502fad4b12bSEdward Tomasz Napierala else \ 503fad4b12bSEdward Tomasz Napierala ARB_RIGHTIDX(parent, field) = \ 504fad4b12bSEdward Tomasz Napierala ARB_SELFIDX(head, child); \ 505fad4b12bSEdward Tomasz Napierala ARB_AUGMENT(parent); \ 506fad4b12bSEdward Tomasz Napierala } else \ 507fad4b12bSEdward Tomasz Napierala ARB_ROOTIDX(head) = ARB_SELFIDX(head, child); \ 508fad4b12bSEdward Tomasz Napierala color: \ 509fad4b12bSEdward Tomasz Napierala if (color == ARB_BLACK) \ 510fad4b12bSEdward Tomasz Napierala name##_ARB_REMOVE_COLOR(head, parent, child); \ 511fad4b12bSEdward Tomasz Napierala ARB_CURNODES(head) -= 1; \ 512fad4b12bSEdward Tomasz Napierala if (ARB_MINIDX(head) == ARB_SELFIDX(head, old)) \ 513fad4b12bSEdward Tomasz Napierala ARB_MINIDX(head) = ARB_PARENTIDX(old, field); \ 514fad4b12bSEdward Tomasz Napierala if (ARB_MAXIDX(head) == ARB_SELFIDX(head, old)) \ 515fad4b12bSEdward Tomasz Napierala ARB_MAXIDX(head) = ARB_PARENTIDX(old, field); \ 516fad4b12bSEdward Tomasz Napierala ARB_RETURNFREE(head, old, field); \ 517fad4b12bSEdward Tomasz Napierala return (old); \ 518fad4b12bSEdward Tomasz Napierala } \ 519fad4b12bSEdward Tomasz Napierala 520fad4b12bSEdward Tomasz Napierala #define ARB_GENERATE_INSERT(name, type, field, cmp, attr) \ 521fad4b12bSEdward Tomasz Napierala /* Inserts a node into the RB tree */ \ 522fad4b12bSEdward Tomasz Napierala attr struct type * \ 523fad4b12bSEdward Tomasz Napierala name##_ARB_INSERT(struct name *head, struct type *elm) \ 524fad4b12bSEdward Tomasz Napierala { \ 525fad4b12bSEdward Tomasz Napierala struct type *tmp; \ 526fad4b12bSEdward Tomasz Napierala struct type *parent = NULL; \ 527fad4b12bSEdward Tomasz Napierala int comp = 0; \ 528fad4b12bSEdward Tomasz Napierala tmp = ARB_ROOT(head); \ 529fad4b12bSEdward Tomasz Napierala while (tmp) { \ 530fad4b12bSEdward Tomasz Napierala parent = tmp; \ 531fad4b12bSEdward Tomasz Napierala comp = (cmp)(elm, parent); \ 532fad4b12bSEdward Tomasz Napierala if (comp < 0) \ 533fad4b12bSEdward Tomasz Napierala tmp = ARB_LEFT(head, tmp, field); \ 534fad4b12bSEdward Tomasz Napierala else if (comp > 0) \ 535fad4b12bSEdward Tomasz Napierala tmp = ARB_RIGHT(head, tmp, field); \ 536fad4b12bSEdward Tomasz Napierala else \ 537fad4b12bSEdward Tomasz Napierala return (tmp); \ 538fad4b12bSEdward Tomasz Napierala } \ 539fad4b12bSEdward Tomasz Napierala ARB_SET(head, elm, parent, field); \ 540fad4b12bSEdward Tomasz Napierala if (parent != NULL) { \ 541fad4b12bSEdward Tomasz Napierala if (comp < 0) \ 542fad4b12bSEdward Tomasz Napierala ARB_LEFTIDX(parent, field) = \ 543fad4b12bSEdward Tomasz Napierala ARB_SELFIDX(head, elm); \ 544fad4b12bSEdward Tomasz Napierala else \ 545fad4b12bSEdward Tomasz Napierala ARB_RIGHTIDX(parent, field) = \ 546fad4b12bSEdward Tomasz Napierala ARB_SELFIDX(head, elm); \ 547fad4b12bSEdward Tomasz Napierala ARB_AUGMENT(parent); \ 548fad4b12bSEdward Tomasz Napierala } else \ 549fad4b12bSEdward Tomasz Napierala ARB_ROOTIDX(head) = ARB_SELFIDX(head, elm); \ 550fad4b12bSEdward Tomasz Napierala name##_ARB_INSERT_COLOR(head, elm); \ 551fad4b12bSEdward Tomasz Napierala ARB_CURNODES(head) += 1; \ 552fad4b12bSEdward Tomasz Napierala if (ARB_MINIDX(head) == ARB_NULLIDX || \ 553fad4b12bSEdward Tomasz Napierala (ARB_PARENTIDX(elm, field) == ARB_MINIDX(head) && \ 554fad4b12bSEdward Tomasz Napierala ARB_LEFTIDX(parent, field) == ARB_SELFIDX(head, elm))) \ 555fad4b12bSEdward Tomasz Napierala ARB_MINIDX(head) = ARB_SELFIDX(head, elm); \ 556fad4b12bSEdward Tomasz Napierala if (ARB_MAXIDX(head) == ARB_NULLIDX || \ 557fad4b12bSEdward Tomasz Napierala (ARB_PARENTIDX(elm, field) == ARB_MAXIDX(head) && \ 558fad4b12bSEdward Tomasz Napierala ARB_RIGHTIDX(parent, field) == ARB_SELFIDX(head, elm))) \ 559fad4b12bSEdward Tomasz Napierala ARB_MAXIDX(head) = ARB_SELFIDX(head, elm); \ 560fad4b12bSEdward Tomasz Napierala return (NULL); \ 561fad4b12bSEdward Tomasz Napierala } 562fad4b12bSEdward Tomasz Napierala 563fad4b12bSEdward Tomasz Napierala #define ARB_GENERATE_CFIND(name, type, field, cmp, attr) \ 564fad4b12bSEdward Tomasz Napierala /* Finds the node with the same key as elm */ \ 565fad4b12bSEdward Tomasz Napierala attr const struct type * \ 566fad4b12bSEdward Tomasz Napierala name##_ARB_CFIND(const struct name *head, const struct type *elm) \ 567fad4b12bSEdward Tomasz Napierala { \ 568fad4b12bSEdward Tomasz Napierala const struct type *tmp = ARB_ROOT(head); \ 569fad4b12bSEdward Tomasz Napierala int comp; \ 570fad4b12bSEdward Tomasz Napierala while (tmp) { \ 571fad4b12bSEdward Tomasz Napierala comp = cmp(elm, tmp); \ 572fad4b12bSEdward Tomasz Napierala if (comp < 0) \ 573fad4b12bSEdward Tomasz Napierala tmp = ARB_LEFT(head, tmp, field); \ 574fad4b12bSEdward Tomasz Napierala else if (comp > 0) \ 575fad4b12bSEdward Tomasz Napierala tmp = ARB_RIGHT(head, tmp, field); \ 576fad4b12bSEdward Tomasz Napierala else \ 577fad4b12bSEdward Tomasz Napierala return (tmp); \ 578fad4b12bSEdward Tomasz Napierala } \ 579fad4b12bSEdward Tomasz Napierala return (NULL); \ 580fad4b12bSEdward Tomasz Napierala } 581fad4b12bSEdward Tomasz Napierala 582fad4b12bSEdward Tomasz Napierala #define ARB_GENERATE_FIND(name, type, field, cmp, attr) \ 583fad4b12bSEdward Tomasz Napierala attr struct type * \ 584fad4b12bSEdward Tomasz Napierala name##_ARB_FIND(const struct name *head, const struct type *elm) \ 585fad4b12bSEdward Tomasz Napierala { return (__DECONST(struct type *, name##_ARB_CFIND(head, elm))); } 586fad4b12bSEdward Tomasz Napierala 587fad4b12bSEdward Tomasz Napierala #define ARB_GENERATE_CNFIND(name, type, field, cmp, attr) \ 588fad4b12bSEdward Tomasz Napierala /* Finds the first node greater than or equal to the search key */ \ 589fad4b12bSEdward Tomasz Napierala attr const struct type * \ 590fad4b12bSEdward Tomasz Napierala name##_ARB_CNFIND(const struct name *head, const struct type *elm) \ 591fad4b12bSEdward Tomasz Napierala { \ 592fad4b12bSEdward Tomasz Napierala const struct type *tmp = ARB_ROOT(head); \ 593fad4b12bSEdward Tomasz Napierala const struct type *res = NULL; \ 594fad4b12bSEdward Tomasz Napierala int comp; \ 595fad4b12bSEdward Tomasz Napierala while (tmp) { \ 596fad4b12bSEdward Tomasz Napierala comp = cmp(elm, tmp); \ 597fad4b12bSEdward Tomasz Napierala if (comp < 0) { \ 598fad4b12bSEdward Tomasz Napierala res = tmp; \ 599fad4b12bSEdward Tomasz Napierala tmp = ARB_LEFT(head, tmp, field); \ 600fad4b12bSEdward Tomasz Napierala } \ 601fad4b12bSEdward Tomasz Napierala else if (comp > 0) \ 602fad4b12bSEdward Tomasz Napierala tmp = ARB_RIGHT(head, tmp, field); \ 603fad4b12bSEdward Tomasz Napierala else \ 604fad4b12bSEdward Tomasz Napierala return (tmp); \ 605fad4b12bSEdward Tomasz Napierala } \ 606fad4b12bSEdward Tomasz Napierala return (res); \ 607fad4b12bSEdward Tomasz Napierala } 608fad4b12bSEdward Tomasz Napierala 609fad4b12bSEdward Tomasz Napierala #define ARB_GENERATE_NFIND(name, type, field, cmp, attr) \ 610fad4b12bSEdward Tomasz Napierala attr struct type * \ 611fad4b12bSEdward Tomasz Napierala name##_ARB_NFIND(const struct name *head, const struct type *elm) \ 612fad4b12bSEdward Tomasz Napierala { return (__DECONST(struct type *, name##_ARB_CNFIND(head, elm))); } 613fad4b12bSEdward Tomasz Napierala 614fad4b12bSEdward Tomasz Napierala #define ARB_GENERATE_CNEXT(name, type, field, attr) \ 615fad4b12bSEdward Tomasz Napierala /* ARGSUSED */ \ 616fad4b12bSEdward Tomasz Napierala attr const struct type * \ 617fad4b12bSEdward Tomasz Napierala name##_ARB_CNEXT(const struct name *head, const struct type *elm) \ 618fad4b12bSEdward Tomasz Napierala { \ 619fad4b12bSEdward Tomasz Napierala if (ARB_RIGHT(head, elm, field)) { \ 620fad4b12bSEdward Tomasz Napierala elm = ARB_RIGHT(head, elm, field); \ 621fad4b12bSEdward Tomasz Napierala while (ARB_LEFT(head, elm, field)) \ 622fad4b12bSEdward Tomasz Napierala elm = ARB_LEFT(head, elm, field); \ 623fad4b12bSEdward Tomasz Napierala } else { \ 624fad4b12bSEdward Tomasz Napierala if (ARB_PARENT(head, elm, field) && \ 625fad4b12bSEdward Tomasz Napierala (elm == ARB_LEFT(head, ARB_PARENT(head, elm, field),\ 626fad4b12bSEdward Tomasz Napierala field))) \ 627fad4b12bSEdward Tomasz Napierala elm = ARB_PARENT(head, elm, field); \ 628fad4b12bSEdward Tomasz Napierala else { \ 629fad4b12bSEdward Tomasz Napierala while (ARB_PARENT(head, elm, field) && \ 630fad4b12bSEdward Tomasz Napierala (elm == ARB_RIGHT(head, ARB_PARENT(head, \ 631fad4b12bSEdward Tomasz Napierala elm, field), field))) \ 632fad4b12bSEdward Tomasz Napierala elm = ARB_PARENT(head, elm, field); \ 633fad4b12bSEdward Tomasz Napierala elm = ARB_PARENT(head, elm, field); \ 634fad4b12bSEdward Tomasz Napierala } \ 635fad4b12bSEdward Tomasz Napierala } \ 636fad4b12bSEdward Tomasz Napierala return (elm); \ 637fad4b12bSEdward Tomasz Napierala } 638fad4b12bSEdward Tomasz Napierala 639fad4b12bSEdward Tomasz Napierala #define ARB_GENERATE_NEXT(name, type, field, attr) \ 640fad4b12bSEdward Tomasz Napierala attr struct type * \ 641fad4b12bSEdward Tomasz Napierala name##_ARB_NEXT(const struct name *head, const struct type *elm) \ 642fad4b12bSEdward Tomasz Napierala { return (__DECONST(struct type *, name##_ARB_CNEXT(head, elm))); } 643fad4b12bSEdward Tomasz Napierala 644fad4b12bSEdward Tomasz Napierala #define ARB_GENERATE_CPREV(name, type, field, attr) \ 645fad4b12bSEdward Tomasz Napierala /* ARGSUSED */ \ 646fad4b12bSEdward Tomasz Napierala attr const struct type * \ 647fad4b12bSEdward Tomasz Napierala name##_ARB_CPREV(const struct name *head, const struct type *elm) \ 648fad4b12bSEdward Tomasz Napierala { \ 649fad4b12bSEdward Tomasz Napierala if (ARB_LEFT(head, elm, field)) { \ 650fad4b12bSEdward Tomasz Napierala elm = ARB_LEFT(head, elm, field); \ 651fad4b12bSEdward Tomasz Napierala while (ARB_RIGHT(head, elm, field)) \ 652fad4b12bSEdward Tomasz Napierala elm = ARB_RIGHT(head, elm, field); \ 653fad4b12bSEdward Tomasz Napierala } else { \ 654fad4b12bSEdward Tomasz Napierala if (ARB_PARENT(head, elm, field) && \ 655fad4b12bSEdward Tomasz Napierala (elm == ARB_RIGHT(head, ARB_PARENT(head, elm, \ 656fad4b12bSEdward Tomasz Napierala field), field))) \ 657fad4b12bSEdward Tomasz Napierala elm = ARB_PARENT(head, elm, field); \ 658fad4b12bSEdward Tomasz Napierala else { \ 659fad4b12bSEdward Tomasz Napierala while (ARB_PARENT(head, elm, field) && \ 660fad4b12bSEdward Tomasz Napierala (elm == ARB_LEFT(head, ARB_PARENT(head, elm,\ 661fad4b12bSEdward Tomasz Napierala field), field))) \ 662fad4b12bSEdward Tomasz Napierala elm = ARB_PARENT(head, elm, field); \ 663fad4b12bSEdward Tomasz Napierala elm = ARB_PARENT(head, elm, field); \ 664fad4b12bSEdward Tomasz Napierala } \ 665fad4b12bSEdward Tomasz Napierala } \ 666fad4b12bSEdward Tomasz Napierala return (elm); \ 667fad4b12bSEdward Tomasz Napierala } 668fad4b12bSEdward Tomasz Napierala 669fad4b12bSEdward Tomasz Napierala #define ARB_GENERATE_PREV(name, type, field, attr) \ 670fad4b12bSEdward Tomasz Napierala attr struct type * \ 671fad4b12bSEdward Tomasz Napierala name##_ARB_PREV(const struct name *head, const struct type *elm) \ 672fad4b12bSEdward Tomasz Napierala { return (__DECONST(struct type *, name##_ARB_CPREV(head, elm))); } 673fad4b12bSEdward Tomasz Napierala 674fad4b12bSEdward Tomasz Napierala #define ARB_GENERATE_CMINMAX(name, type, field, attr) \ 675fad4b12bSEdward Tomasz Napierala attr const struct type * \ 676fad4b12bSEdward Tomasz Napierala name##_ARB_CMINMAX(const struct name *head, int val) \ 677fad4b12bSEdward Tomasz Napierala { \ 678fad4b12bSEdward Tomasz Napierala const struct type *tmp = ARB_EMPTY(head) ? NULL : ARB_ROOT(head);\ 679fad4b12bSEdward Tomasz Napierala const struct type *parent = NULL; \ 680fad4b12bSEdward Tomasz Napierala while (tmp) { \ 681fad4b12bSEdward Tomasz Napierala parent = tmp; \ 682fad4b12bSEdward Tomasz Napierala if (val < 0) \ 683fad4b12bSEdward Tomasz Napierala tmp = ARB_LEFT(head, tmp, field); \ 684fad4b12bSEdward Tomasz Napierala else \ 685fad4b12bSEdward Tomasz Napierala tmp = ARB_RIGHT(head, tmp, field); \ 686fad4b12bSEdward Tomasz Napierala } \ 687fad4b12bSEdward Tomasz Napierala return (__DECONST(struct type *, parent)); \ 688fad4b12bSEdward Tomasz Napierala } 689fad4b12bSEdward Tomasz Napierala 690fad4b12bSEdward Tomasz Napierala #define ARB_GENERATE_MINMAX(name, type, field, attr) \ 691fad4b12bSEdward Tomasz Napierala attr struct type * \ 692fad4b12bSEdward Tomasz Napierala name##_ARB_MINMAX(const struct name *head, int val) \ 693fad4b12bSEdward Tomasz Napierala { return (__DECONST(struct type *, name##_ARB_CMINMAX(head, val))); } 694fad4b12bSEdward Tomasz Napierala 695a5adff0eSEdward Tomasz Napierala #define ARB_GENERATE_REINSERT(name, type, field, cmp, attr) \ 696fad4b12bSEdward Tomasz Napierala attr struct type * \ 697a5adff0eSEdward Tomasz Napierala name##_ARB_REINSERT(struct name *head, struct type *elm) \ 698fad4b12bSEdward Tomasz Napierala { \ 699fad4b12bSEdward Tomasz Napierala struct type *cmpelm; \ 700fad4b12bSEdward Tomasz Napierala if (((cmpelm = ARB_PREV(name, head, elm)) != NULL && \ 701fad4b12bSEdward Tomasz Napierala (cmp)(cmpelm, elm) >= 0) || \ 702fad4b12bSEdward Tomasz Napierala ((cmpelm = ARB_NEXT(name, head, elm)) != NULL && \ 703fad4b12bSEdward Tomasz Napierala (cmp)(elm, cmpelm) >= 0)) { \ 704fad4b12bSEdward Tomasz Napierala /* XXXLAS: Remove/insert is heavy handed. */ \ 705fad4b12bSEdward Tomasz Napierala ARB_REMOVE(name, head, elm); \ 706fad4b12bSEdward Tomasz Napierala /* Remove puts elm on the free list. */ \ 707fad4b12bSEdward Tomasz Napierala elm = ARB_GETFREE(head, field); \ 708fad4b12bSEdward Tomasz Napierala return (ARB_INSERT(name, head, elm)); \ 709fad4b12bSEdward Tomasz Napierala } \ 710fad4b12bSEdward Tomasz Napierala return (NULL); \ 711fad4b12bSEdward Tomasz Napierala } \ 712fad4b12bSEdward Tomasz Napierala 713fad4b12bSEdward Tomasz Napierala #define ARB_INSERT(name, x, y) name##_ARB_INSERT(x, y) 714fad4b12bSEdward Tomasz Napierala #define ARB_REMOVE(name, x, y) name##_ARB_REMOVE(x, y) 715fad4b12bSEdward Tomasz Napierala #define ARB_CFIND(name, x, y) name##_ARB_CFIND(x, y) 716fad4b12bSEdward Tomasz Napierala #define ARB_FIND(name, x, y) name##_ARB_FIND(x, y) 717fad4b12bSEdward Tomasz Napierala #define ARB_CNFIND(name, x, y) name##_ARB_CNFIND(x, y) 718fad4b12bSEdward Tomasz Napierala #define ARB_NFIND(name, x, y) name##_ARB_NFIND(x, y) 719fad4b12bSEdward Tomasz Napierala #define ARB_CNEXT(name, x, y) name##_ARB_CNEXT(x, y) 720fad4b12bSEdward Tomasz Napierala #define ARB_NEXT(name, x, y) name##_ARB_NEXT(x, y) 721fad4b12bSEdward Tomasz Napierala #define ARB_CPREV(name, x, y) name##_ARB_CPREV(x, y) 722fad4b12bSEdward Tomasz Napierala #define ARB_PREV(name, x, y) name##_ARB_PREV(x, y) 723fad4b12bSEdward Tomasz Napierala #define ARB_CMIN(name, x) (ARB_MINIDX(x) == ARB_NULLIDX ? \ 724fad4b12bSEdward Tomasz Napierala name##_ARB_CMINMAX(x, ARB_NEGINF) : ARB_CNODE(x, ARB_MINIDX(x))) 725fad4b12bSEdward Tomasz Napierala #define ARB_MIN(name, x) (ARB_MINIDX(x) == ARB_NULLIDX ? \ 726fad4b12bSEdward Tomasz Napierala name##_ARB_MINMAX(x, ARB_NEGINF) : ARB_NODE(x, ARB_MINIDX(x))) 727fad4b12bSEdward Tomasz Napierala #define ARB_CMAX(name, x) (ARB_MAXIDX(x) == ARB_NULLIDX ? \ 728fad4b12bSEdward Tomasz Napierala name##_ARB_CMINMAX(x, ARB_INF) : ARB_CNODE(x, ARB_MAXIDX(x))) 729fad4b12bSEdward Tomasz Napierala #define ARB_MAX(name, x) (ARB_MAXIDX(x) == ARB_NULLIDX ? \ 730fad4b12bSEdward Tomasz Napierala name##_ARB_MINMAX(x, ARB_INF) : ARB_NODE(x, ARB_MAXIDX(x))) 731a5adff0eSEdward Tomasz Napierala #define ARB_REINSERT(name, x, y) name##_ARB_REINSERT(x, y) 732fad4b12bSEdward Tomasz Napierala 733fad4b12bSEdward Tomasz Napierala #define ARB_FOREACH(x, name, head) \ 734fad4b12bSEdward Tomasz Napierala for ((x) = ARB_MIN(name, head); \ 735fad4b12bSEdward Tomasz Napierala (x) != NULL; \ 736fad4b12bSEdward Tomasz Napierala (x) = name##_ARB_NEXT(head, x)) 737fad4b12bSEdward Tomasz Napierala 738fad4b12bSEdward Tomasz Napierala #define ARB_FOREACH_FROM(x, name, y) \ 739fad4b12bSEdward Tomasz Napierala for ((x) = (y); \ 740fad4b12bSEdward Tomasz Napierala ((x) != NULL) && ((y) = name##_ARB_NEXT(x), (x) != NULL); \ 741fad4b12bSEdward Tomasz Napierala (x) = (y)) 742fad4b12bSEdward Tomasz Napierala 743fad4b12bSEdward Tomasz Napierala #define ARB_FOREACH_SAFE(x, name, head, y) \ 744fad4b12bSEdward Tomasz Napierala for ((x) = ARB_MIN(name, head); \ 745fad4b12bSEdward Tomasz Napierala ((x) != NULL) && ((y) = name##_ARB_NEXT(x), (x) != NULL); \ 746fad4b12bSEdward Tomasz Napierala (x) = (y)) 747fad4b12bSEdward Tomasz Napierala 748fad4b12bSEdward Tomasz Napierala #define ARB_FOREACH_REVERSE(x, name, head) \ 749fad4b12bSEdward Tomasz Napierala for ((x) = ARB_MAX(name, head); \ 750fad4b12bSEdward Tomasz Napierala (x) != NULL; \ 751fad4b12bSEdward Tomasz Napierala (x) = name##_ARB_PREV(x)) 752fad4b12bSEdward Tomasz Napierala 753fad4b12bSEdward Tomasz Napierala #define ARB_FOREACH_REVERSE_FROM(x, name, y) \ 754fad4b12bSEdward Tomasz Napierala for ((x) = (y); \ 755fad4b12bSEdward Tomasz Napierala ((x) != NULL) && ((y) = name##_ARB_PREV(x), (x) != NULL); \ 756fad4b12bSEdward Tomasz Napierala (x) = (y)) 757fad4b12bSEdward Tomasz Napierala 758fad4b12bSEdward Tomasz Napierala #define ARB_FOREACH_REVERSE_SAFE(x, name, head, y) \ 759fad4b12bSEdward Tomasz Napierala for ((x) = ARB_MAX(name, head); \ 760fad4b12bSEdward Tomasz Napierala ((x) != NULL) && ((y) = name##_ARB_PREV(x), (x) != NULL); \ 761fad4b12bSEdward Tomasz Napierala (x) = (y)) 762fad4b12bSEdward Tomasz Napierala 763fad4b12bSEdward Tomasz Napierala #define ARB_ARRFOREACH(x, field, head) \ 764fad4b12bSEdward Tomasz Napierala for ((x) = ARB_NODES(head); \ 765fad4b12bSEdward Tomasz Napierala ARB_SELFIDX(head, x) < ARB_MAXNODES(head); \ 766fad4b12bSEdward Tomasz Napierala (x)++) 767fad4b12bSEdward Tomasz Napierala 768fad4b12bSEdward Tomasz Napierala #define ARB_ARRFOREACH_REVWCOND(x, field, head, extracond) \ 769fad4b12bSEdward Tomasz Napierala for ((x) = ARB_NODES(head) + (ARB_MAXNODES(head) - 1); \ 770fad4b12bSEdward Tomasz Napierala (x) >= ARB_NODES(head) && (extracond); \ 771fad4b12bSEdward Tomasz Napierala (x)--) 772fad4b12bSEdward Tomasz Napierala 773fad4b12bSEdward Tomasz Napierala #define ARB_ARRFOREACH_REVERSE(x, field, head) \ 774fad4b12bSEdward Tomasz Napierala ARB_ARRFOREACH_REVWCOND(x, field, head, 1) 775fad4b12bSEdward Tomasz Napierala 7761a13f2e6SEdward Tomasz Napierala #define ARB_RESET_TREE(head, name, maxn) \ 7771a13f2e6SEdward Tomasz Napierala *(head) = ARB_INITIALIZER(name, maxn) 7781a13f2e6SEdward Tomasz Napierala 779fad4b12bSEdward Tomasz Napierala #endif /* _SYS_ARB_H_ */ 780