Annotation of libaitio/inc/atree.h, revision 1.4

1.2       misho       1: /*************************************************************************
                      2: * (C) 2011 AITNET ltd - Sofia/Bulgaria - <misho@aitnet.org>
                      3: *  by Michael Pounov <misho@elwix.org>
                      4: *
                      5: * $Author: misho $
1.4     ! misho       6: * $Id: atree.h,v 1.3.28.2 2012/08/17 22:00:03 misho Exp $
1.2       misho       7: *
                      8: **************************************************************************
                      9: The ELWIX and AITNET software is distributed under the following
                     10: terms:
                     11: 
                     12: All of the documentation and software included in the ELWIX and AITNET
                     13: Releases is copyrighted by ELWIX - Sofia/Bulgaria <info@elwix.org>
                     14: 
1.4     ! misho      15: Copyright 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
1.2       misho      16:        by Michael Pounov <misho@elwix.org>.  All rights reserved.
                     17: 
                     18: Redistribution and use in source and binary forms, with or without
                     19: modification, are permitted provided that the following conditions
                     20: are met:
                     21: 1. Redistributions of source code must retain the above copyright
                     22:    notice, this list of conditions and the following disclaimer.
                     23: 2. Redistributions in binary form must reproduce the above copyright
                     24:    notice, this list of conditions and the following disclaimer in the
                     25:    documentation and/or other materials provided with the distribution.
                     26: 3. All advertising materials mentioning features or use of this software
                     27:    must display the following acknowledgement:
                     28: This product includes software developed by Michael Pounov <misho@elwix.org>
                     29: ELWIX - Embedded LightWeight unIX and its contributors.
                     30: 4. Neither the name of AITNET nor the names of its contributors
                     31:    may be used to endorse or promote products derived from this software
                     32:    without specific prior written permission.
                     33: 
                     34: THIS SOFTWARE IS PROVIDED BY AITNET AND CONTRIBUTORS ``AS IS'' AND
                     35: ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
                     36: IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
                     37: ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
                     38: FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
                     39: DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
                     40: OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
                     41: HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
                     42: LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
                     43: OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
                     44: SUCH DAMAGE.
                     45: */
                     46: /*
                     47:  *
                     48:  * AVL tree implementation, changes in other trees and file are
                     49:  * Copyrighted 2011 Michael Pounov <misho@elwix.org>
                     50:  * All rights reserved.
                     51:  *
                     52:  */
                     53: /*     $OpenBSD: tree.h,v 1.12 2009/03/02 09:42:55 mikeb Exp $ */
                     54: /*
                     55:  * Copyright 2002 Niels Provos <provos@citi.umich.edu>
                     56:  * All rights reserved.
                     57:  *
                     58:  * Redistribution and use in source and binary forms, with or without
                     59:  * modification, are permitted provided that the following conditions
                     60:  * are met:
                     61:  * 1. Redistributions of source code must retain the above copyright
                     62:  *    notice, this list of conditions and the following disclaimer.
                     63:  * 2. Redistributions in binary form must reproduce the above copyright
                     64:  *    notice, this list of conditions and the following disclaimer in the
                     65:  *    documentation and/or other materials provided with the distribution.
                     66:  *
                     67:  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
                     68:  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
                     69:  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
                     70:  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
                     71:  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
                     72:  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
                     73:  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
                     74:  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
                     75:  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
                     76:  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
                     77:  */
                     78: 
                     79: #ifndef        _SYS_TREE_H_
                     80: #define        _SYS_TREE_H_
                     81: 
                     82: /*
                     83:  * This file defines data structures for different types of trees:
                     84:  * splay trees and red-black trees.
                     85:  *
                     86:  * A splay tree is a self-organizing data structure.  Every operation
                     87:  * on the tree causes a splay to happen.  The splay moves the requested
                     88:  * node to the root of the tree and partly rebalances it.
                     89:  *
                     90:  * This has the benefit that request locality causes faster lookups as
                     91:  * the requested nodes move to the top of the tree.  On the other hand,
                     92:  * every lookup causes memory writes.
                     93:  *
                     94:  * The Balance Theorem bounds the total access time for m operations
                     95:  * and n inserts on an initially empty tree as O((m + n)lg n).  The
                     96:  * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
                     97:  *
                     98:  * A red-black tree is a binary search tree with the node color as an
                     99:  * extra attribute.  It fulfills a set of conditions:
                    100:  *     - every search path from the root to a leaf consists of the
                    101:  *       same number of black nodes,
                    102:  *     - each red node (except for the root) has a black parent,
                    103:  *     - each leaf node is black.
                    104:  *
                    105:  * Every operation on a red-black tree is bounded as O(lg n).
                    106:  * The maximum height of a red-black tree is 2lg (n+1).
                    107:  */
                    108: 
                    109: #define SPLAY_HEAD(name, type)                                         \
                    110: struct name {                                                          \
                    111:        struct type *sph_root; /* root of the tree */                   \
                    112: }
                    113: 
                    114: #define SPLAY_INITIALIZER(root)                                                \
                    115:        { NULL }
                    116: 
                    117: #define SPLAY_INIT(root) do {                                          \
                    118:        (root)->sph_root = NULL;                                        \
                    119: } while (0)
                    120: 
                    121: #define SPLAY_ENTRY(type)                                              \
                    122: struct {                                                               \
                    123:        struct type *spe_left; /* left element */                       \
                    124:        struct type *spe_right; /* right element */                     \
                    125: }
                    126: 
                    127: #define SPLAY_LEFT(elm, field)         (elm)->field.spe_left
                    128: #define SPLAY_RIGHT(elm, field)                (elm)->field.spe_right
                    129: #define SPLAY_ROOT(head)               (head)->sph_root
                    130: #define SPLAY_EMPTY(head)              (SPLAY_ROOT(head) == NULL)
                    131: 
                    132: /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
                    133: #define SPLAY_ROTATE_RIGHT(head, tmp, field) do {                      \
                    134:        SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field);  \
                    135:        SPLAY_RIGHT(tmp, field) = (head)->sph_root;                     \
                    136:        (head)->sph_root = tmp;                                         \
                    137: } while (0)
1.3       misho     138: 
1.2       misho     139: #define SPLAY_ROTATE_LEFT(head, tmp, field) do {                       \
                    140:        SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field);  \
                    141:        SPLAY_LEFT(tmp, field) = (head)->sph_root;                      \
                    142:        (head)->sph_root = tmp;                                         \
                    143: } while (0)
                    144: 
                    145: #define SPLAY_LINKLEFT(head, tmp, field) do {                          \
                    146:        SPLAY_LEFT(tmp, field) = (head)->sph_root;                      \
                    147:        tmp = (head)->sph_root;                                         \
                    148:        (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);         \
                    149: } while (0)
                    150: 
                    151: #define SPLAY_LINKRIGHT(head, tmp, field) do {                         \
                    152:        SPLAY_RIGHT(tmp, field) = (head)->sph_root;                     \
                    153:        tmp = (head)->sph_root;                                         \
                    154:        (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);        \
                    155: } while (0)
                    156: 
                    157: #define SPLAY_ASSEMBLE(head, node, left, right, field) do {            \
                    158:        SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
                    159:        SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
                    160:        SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
                    161:        SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
                    162: } while (0)
                    163: 
                    164: /* Generates prototypes and inline functions */
                    165: 
                    166: #define SPLAY_PROTOTYPE(name, type, field, cmp)                                \
                    167: void name##_SPLAY(struct name *, struct type *);                       \
                    168: void name##_SPLAY_MINMAX(struct name *, int);                          \
                    169: struct type *name##_SPLAY_INSERT(struct name *, struct type *);                \
                    170: struct type *name##_SPLAY_REMOVE(struct name *, struct type *);                \
                    171:                                                                        \
                    172: /* Finds the node with the same key as elm */                          \
                    173: static __inline struct type *                                          \
                    174: name##_SPLAY_FIND(struct name *head, struct type *elm)                 \
                    175: {                                                                      \
                    176:        if (SPLAY_EMPTY(head))                                          \
                    177:                return(NULL);                                           \
                    178:        name##_SPLAY(head, elm);                                        \
                    179:        if ((cmp)(elm, (head)->sph_root) == 0)                          \
                    180:                return (head->sph_root);                                \
                    181:        return (NULL);                                                  \
                    182: }                                                                      \
                    183:                                                                        \
                    184: static __inline struct type *                                          \
                    185: name##_SPLAY_NEXT(struct name *head, struct type *elm)                 \
                    186: {                                                                      \
                    187:        name##_SPLAY(head, elm);                                        \
                    188:        if (SPLAY_RIGHT(elm, field) != NULL) {                          \
                    189:                elm = SPLAY_RIGHT(elm, field);                          \
                    190:                while (SPLAY_LEFT(elm, field) != NULL) {                \
                    191:                        elm = SPLAY_LEFT(elm, field);                   \
                    192:                }                                                       \
                    193:        } else                                                          \
                    194:                elm = NULL;                                             \
                    195:        return (elm);                                                   \
                    196: }                                                                      \
                    197:                                                                        \
                    198: static __inline struct type *                                          \
                    199: name##_SPLAY_MIN_MAX(struct name *head, int val)                       \
                    200: {                                                                      \
                    201:        name##_SPLAY_MINMAX(head, val);                                 \
                    202:         return (SPLAY_ROOT(head));                                     \
                    203: }
                    204: 
                    205: /* Main splay operation.
                    206:  * Moves node close to the key of elm to top
                    207:  */
                    208: #define SPLAY_GENERATE(name, type, field, cmp)                         \
                    209: struct type *                                                          \
                    210: name##_SPLAY_INSERT(struct name *head, struct type *elm)               \
                    211: {                                                                      \
                    212:     if (SPLAY_EMPTY(head)) {                                           \
                    213:            SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL;    \
                    214:     } else {                                                           \
                    215:            int __comp;                                                 \
                    216:            name##_SPLAY(head, elm);                                    \
                    217:            __comp = (cmp)(elm, (head)->sph_root);                      \
                    218:            if(__comp < 0) {                                            \
                    219:                    SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
                    220:                    SPLAY_RIGHT(elm, field) = (head)->sph_root;         \
                    221:                    SPLAY_LEFT((head)->sph_root, field) = NULL;         \
                    222:            } else if (__comp > 0) {                                    \
                    223:                    SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
                    224:                    SPLAY_LEFT(elm, field) = (head)->sph_root;          \
                    225:                    SPLAY_RIGHT((head)->sph_root, field) = NULL;        \
                    226:            } else                                                      \
                    227:                    return ((head)->sph_root);                          \
                    228:     }                                                                  \
                    229:     (head)->sph_root = (elm);                                          \
                    230:     return (NULL);                                                     \
                    231: }                                                                      \
                    232:                                                                        \
                    233: struct type *                                                          \
                    234: name##_SPLAY_REMOVE(struct name *head, struct type *elm)               \
                    235: {                                                                      \
                    236:        struct type *__tmp;                                             \
                    237:        if (SPLAY_EMPTY(head))                                          \
                    238:                return (NULL);                                          \
                    239:        name##_SPLAY(head, elm);                                        \
                    240:        if ((cmp)(elm, (head)->sph_root) == 0) {                        \
                    241:                if (SPLAY_LEFT((head)->sph_root, field) == NULL) {      \
                    242:                        (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
                    243:                } else {                                                \
                    244:                        __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
                    245:                        (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
                    246:                        name##_SPLAY(head, elm);                        \
                    247:                        SPLAY_RIGHT((head)->sph_root, field) = __tmp;   \
                    248:                }                                                       \
                    249:                return (elm);                                           \
                    250:        }                                                               \
                    251:        return (NULL);                                                  \
                    252: }                                                                      \
                    253:                                                                        \
                    254: void                                                                   \
                    255: name##_SPLAY(struct name *head, struct type *elm)                      \
                    256: {                                                                      \
                    257:        struct type __node, *__left, *__right, *__tmp;                  \
                    258:        int __comp;                                                     \
                    259: \
                    260:        SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
                    261:        __left = __right = &__node;                                     \
                    262: \
                    263:        while ((__comp = (cmp)(elm, (head)->sph_root))) {               \
                    264:                if (__comp < 0) {                                       \
                    265:                        __tmp = SPLAY_LEFT((head)->sph_root, field);    \
                    266:                        if (__tmp == NULL)                              \
                    267:                                break;                                  \
                    268:                        if ((cmp)(elm, __tmp) < 0){                     \
                    269:                                SPLAY_ROTATE_RIGHT(head, __tmp, field); \
                    270:                                if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
                    271:                                        break;                          \
                    272:                        }                                               \
                    273:                        SPLAY_LINKLEFT(head, __right, field);           \
                    274:                } else if (__comp > 0) {                                \
                    275:                        __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
                    276:                        if (__tmp == NULL)                              \
                    277:                                break;                                  \
                    278:                        if ((cmp)(elm, __tmp) > 0){                     \
                    279:                                SPLAY_ROTATE_LEFT(head, __tmp, field);  \
                    280:                                if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
                    281:                                        break;                          \
                    282:                        }                                               \
                    283:                        SPLAY_LINKRIGHT(head, __left, field);           \
                    284:                }                                                       \
                    285:        }                                                               \
                    286:        SPLAY_ASSEMBLE(head, &__node, __left, __right, field);          \
                    287: }                                                                      \
                    288:                                                                        \
                    289: /* Splay with either the minimum or the maximum element                        \
                    290:  * Used to find minimum or maximum element in tree.                    \
                    291:  */                                                                    \
                    292: void name##_SPLAY_MINMAX(struct name *head, int __comp) \
                    293: {                                                                      \
                    294:        struct type __node, *__left, *__right, *__tmp;                  \
                    295: \
                    296:        SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
                    297:        __left = __right = &__node;                                     \
                    298: \
                    299:        while (1) {                                                     \
                    300:                if (__comp < 0) {                                       \
                    301:                        __tmp = SPLAY_LEFT((head)->sph_root, field);    \
                    302:                        if (__tmp == NULL)                              \
                    303:                                break;                                  \
                    304:                        if (__comp < 0){                                \
                    305:                                SPLAY_ROTATE_RIGHT(head, __tmp, field); \
                    306:                                if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
                    307:                                        break;                          \
                    308:                        }                                               \
                    309:                        SPLAY_LINKLEFT(head, __right, field);           \
                    310:                } else if (__comp > 0) {                                \
                    311:                        __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
                    312:                        if (__tmp == NULL)                              \
                    313:                                break;                                  \
                    314:                        if (__comp > 0) {                               \
                    315:                                SPLAY_ROTATE_LEFT(head, __tmp, field);  \
                    316:                                if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
                    317:                                        break;                          \
                    318:                        }                                               \
                    319:                        SPLAY_LINKRIGHT(head, __left, field);           \
                    320:                }                                                       \
                    321:        }                                                               \
                    322:        SPLAY_ASSEMBLE(head, &__node, __left, __right, field);          \
                    323: }
                    324: 
                    325: #define SPLAY_NEGINF   -1
                    326: #define SPLAY_INF      1
                    327: 
                    328: #define SPLAY_INSERT(name, x, y)       name##_SPLAY_INSERT(x, y)
                    329: #define SPLAY_REMOVE(name, x, y)       name##_SPLAY_REMOVE(x, y)
                    330: #define SPLAY_FIND(name, x, y)         name##_SPLAY_FIND(x, y)
                    331: #define SPLAY_NEXT(name, x, y)         name##_SPLAY_NEXT(x, y)
                    332: #define SPLAY_MIN(name, x)             (SPLAY_EMPTY(x) ? NULL  \
                    333:                                        : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
                    334: #define SPLAY_MAX(name, x)             (SPLAY_EMPTY(x) ? NULL  \
                    335:                                        : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
                    336: 
                    337: #define SPLAY_FOREACH(x, name, head)                                   \
                    338:        for ((x) = SPLAY_MIN(name, head);                               \
                    339:             (x) != NULL;                                               \
                    340:             (x) = SPLAY_NEXT(name, head, x))
                    341: 
1.4     ! misho     342: #define SPLAY_FOREACH_SAFE(x, name, head, y)                           \
        !           343:        for ((x) = SPLAY_MIN(name, head);                               \
        !           344:            ((x) != NULL) &&                                            \
        !           345:                        ((y) = SPLAY_NEXT(name, head, x), (x) != NULL); \
        !           346:             (x) = (y))
        !           347: 
        !           348: 
1.2       misho     349: /* Macros that define a red-black tree */
                    350: #define RB_HEAD(name, type)                                            \
                    351: struct name {                                                          \
                    352:        struct type *rbh_root; /* root of the tree */                   \
                    353: }
                    354: 
                    355: #define RB_INITIALIZER(root)                                           \
                    356:        { NULL }
                    357: 
                    358: #define RB_INIT(root) do {                                             \
                    359:        (root)->rbh_root = NULL;                                        \
                    360: } while (0)
                    361: 
                    362: #define RB_BLACK       0
                    363: #define RB_RED         1
                    364: #define RB_ENTRY(type)                                                 \
                    365: struct {                                                               \
                    366:        struct type *rbe_left;          /* left element */              \
                    367:        struct type *rbe_right;         /* right element */             \
                    368:        struct type *rbe_parent;        /* parent element */            \
                    369:        int rbe_color;                  /* node color */                \
                    370: }
                    371: 
                    372: #define RB_LEFT(elm, field)            (elm)->field.rbe_left
                    373: #define RB_RIGHT(elm, field)           (elm)->field.rbe_right
                    374: #define RB_PARENT(elm, field)          (elm)->field.rbe_parent
                    375: #define RB_COLOR(elm, field)           (elm)->field.rbe_color
                    376: #define RB_ROOT(head)                  (head)->rbh_root
                    377: #define RB_EMPTY(head)                 (RB_ROOT(head) == NULL)
                    378: 
                    379: #define RB_SET(elm, parent, field) do {                                        \
                    380:        RB_PARENT(elm, field) = parent;                                 \
                    381:        RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL;              \
                    382:        RB_COLOR(elm, field) = RB_RED;                                  \
                    383: } while (0)
                    384: 
                    385: #define RB_SET_BLACKRED(black, red, field) do {                                \
                    386:        RB_COLOR(black, field) = RB_BLACK;                              \
                    387:        RB_COLOR(red, field) = RB_RED;                                  \
                    388: } while (0)
                    389: 
                    390: #ifndef RB_AUGMENT
1.3       misho     391: #define RB_AUGMENT(x) (void)(x)
1.2       misho     392: #endif
                    393: 
                    394: #define RB_ROTATE_LEFT(head, elm, tmp, field) do {                     \
                    395:        (tmp) = RB_RIGHT(elm, field);                                   \
                    396:        if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) {             \
                    397:                RB_PARENT(RB_LEFT(tmp, field), field) = (elm);          \
                    398:        }                                                               \
                    399:        RB_AUGMENT(elm);                                                \
                    400:        if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) {          \
                    401:                if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))     \
                    402:                        RB_LEFT(RB_PARENT(elm, field), field) = (tmp);  \
                    403:                else                                                    \
                    404:                        RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
                    405:        } else                                                          \
                    406:                (head)->rbh_root = (tmp);                               \
                    407:        RB_LEFT(tmp, field) = (elm);                                    \
                    408:        RB_PARENT(elm, field) = (tmp);                                  \
                    409:        RB_AUGMENT(tmp);                                                \
                    410:        if ((RB_PARENT(tmp, field)))                                    \
                    411:                RB_AUGMENT(RB_PARENT(tmp, field));                      \
                    412: } while (0)
                    413: 
                    414: #define RB_ROTATE_RIGHT(head, elm, tmp, field) do {                    \
                    415:        (tmp) = RB_LEFT(elm, field);                                    \
                    416:        if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) {             \
                    417:                RB_PARENT(RB_RIGHT(tmp, field), field) = (elm);         \
                    418:        }                                                               \
                    419:        RB_AUGMENT(elm);                                                \
                    420:        if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) {          \
                    421:                if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))     \
                    422:                        RB_LEFT(RB_PARENT(elm, field), field) = (tmp);  \
                    423:                else                                                    \
                    424:                        RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
                    425:        } else                                                          \
                    426:                (head)->rbh_root = (tmp);                               \
                    427:        RB_RIGHT(tmp, field) = (elm);                                   \
                    428:        RB_PARENT(elm, field) = (tmp);                                  \
                    429:        RB_AUGMENT(tmp);                                                \
                    430:        if ((RB_PARENT(tmp, field)))                                    \
                    431:                RB_AUGMENT(RB_PARENT(tmp, field));                      \
                    432: } while (0)
                    433: 
                    434: /* Generates prototypes and inline functions */
1.3       misho     435: #define RB_PROTOTYPE(name, type, field, cmp)                           \
1.2       misho     436:        RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
                    437: #define        RB_PROTOTYPE_STATIC(name, type, field, cmp)                     \
                    438:        RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
                    439: #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr)            \
                    440: attr void name##_RB_INSERT_COLOR(struct name *, struct type *);                \
                    441: attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
                    442: attr struct type *name##_RB_REMOVE(struct name *, struct type *);      \
                    443: attr struct type *name##_RB_INSERT(struct name *, struct type *);      \
                    444: attr struct type *name##_RB_FIND(struct name *, struct type *);                \
                    445: attr struct type *name##_RB_NFIND(struct name *, struct type *);       \
                    446: attr struct type *name##_RB_NEXT(struct type *);                       \
                    447: attr struct type *name##_RB_PREV(struct type *);                       \
                    448: attr struct type *name##_RB_MINMAX(struct name *, int);                        \
                    449:                                                                        \
                    450: 
                    451: /* Main rb operation.
                    452:  * Moves node close to the key of elm to top
                    453:  */
                    454: #define        RB_GENERATE(name, type, field, cmp)                             \
                    455:        RB_GENERATE_INTERNAL(name, type, field, cmp,)
                    456: #define        RB_GENERATE_STATIC(name, type, field, cmp)                      \
                    457:        RB_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
                    458: #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr)             \
                    459: attr void                                                              \
                    460: name##_RB_INSERT_COLOR(struct name *head, struct type *elm)            \
                    461: {                                                                      \
                    462:        struct type *parent, *gparent, *tmp;                            \
                    463:        while ((parent = RB_PARENT(elm, field)) &&                      \
                    464:            RB_COLOR(parent, field) == RB_RED) {                        \
                    465:                gparent = RB_PARENT(parent, field);                     \
                    466:                if (parent == RB_LEFT(gparent, field)) {                \
                    467:                        tmp = RB_RIGHT(gparent, field);                 \
                    468:                        if (tmp && RB_COLOR(tmp, field) == RB_RED) {    \
                    469:                                RB_COLOR(tmp, field) = RB_BLACK;        \
                    470:                                RB_SET_BLACKRED(parent, gparent, field);\
                    471:                                elm = gparent;                          \
                    472:                                continue;                               \
                    473:                        }                                               \
                    474:                        if (RB_RIGHT(parent, field) == elm) {           \
                    475:                                RB_ROTATE_LEFT(head, parent, tmp, field);\
                    476:                                tmp = parent;                           \
                    477:                                parent = elm;                           \
                    478:                                elm = tmp;                              \
                    479:                        }                                               \
                    480:                        RB_SET_BLACKRED(parent, gparent, field);        \
                    481:                        RB_ROTATE_RIGHT(head, gparent, tmp, field);     \
                    482:                } else {                                                \
                    483:                        tmp = RB_LEFT(gparent, field);                  \
                    484:                        if (tmp && RB_COLOR(tmp, field) == RB_RED) {    \
                    485:                                RB_COLOR(tmp, field) = RB_BLACK;        \
                    486:                                RB_SET_BLACKRED(parent, gparent, field);\
                    487:                                elm = gparent;                          \
                    488:                                continue;                               \
                    489:                        }                                               \
                    490:                        if (RB_LEFT(parent, field) == elm) {            \
                    491:                                RB_ROTATE_RIGHT(head, parent, tmp, field);\
                    492:                                tmp = parent;                           \
                    493:                                parent = elm;                           \
                    494:                                elm = tmp;                              \
                    495:                        }                                               \
                    496:                        RB_SET_BLACKRED(parent, gparent, field);        \
                    497:                        RB_ROTATE_LEFT(head, gparent, tmp, field);      \
                    498:                }                                                       \
                    499:        }                                                               \
                    500:        RB_COLOR(head->rbh_root, field) = RB_BLACK;                     \
                    501: }                                                                      \
                    502:                                                                        \
                    503: attr void                                                              \
                    504: name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
                    505: {                                                                      \
                    506:        struct type *tmp;                                               \
                    507:        while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) &&     \
                    508:            elm != RB_ROOT(head)) {                                     \
                    509:                if (RB_LEFT(parent, field) == elm) {                    \
                    510:                        tmp = RB_RIGHT(parent, field);                  \
                    511:                        if (RB_COLOR(tmp, field) == RB_RED) {           \
                    512:                                RB_SET_BLACKRED(tmp, parent, field);    \
                    513:                                RB_ROTATE_LEFT(head, parent, tmp, field);\
                    514:                                tmp = RB_RIGHT(parent, field);          \
                    515:                        }                                               \
                    516:                        if ((RB_LEFT(tmp, field) == NULL ||             \
                    517:                            RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
                    518:                            (RB_RIGHT(tmp, field) == NULL ||            \
                    519:                            RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
                    520:                                RB_COLOR(tmp, field) = RB_RED;          \
                    521:                                elm = parent;                           \
                    522:                                parent = RB_PARENT(elm, field);         \
                    523:                        } else {                                        \
                    524:                                if (RB_RIGHT(tmp, field) == NULL ||     \
                    525:                                    RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
                    526:                                        struct type *oleft;             \
1.3       misho     527:                                        if ((oleft = RB_LEFT(tmp, field))) \
1.2       misho     528:                                                RB_COLOR(oleft, field) = RB_BLACK;\
                    529:                                        RB_COLOR(tmp, field) = RB_RED;  \
                    530:                                        RB_ROTATE_RIGHT(head, tmp, oleft, field);\
                    531:                                        tmp = RB_RIGHT(parent, field);  \
                    532:                                }                                       \
                    533:                                RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
                    534:                                RB_COLOR(parent, field) = RB_BLACK;     \
                    535:                                if (RB_RIGHT(tmp, field))               \
                    536:                                        RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
                    537:                                RB_ROTATE_LEFT(head, parent, tmp, field);\
                    538:                                elm = RB_ROOT(head);                    \
                    539:                                break;                                  \
                    540:                        }                                               \
                    541:                } else {                                                \
                    542:                        tmp = RB_LEFT(parent, field);                   \
                    543:                        if (RB_COLOR(tmp, field) == RB_RED) {           \
                    544:                                RB_SET_BLACKRED(tmp, parent, field);    \
                    545:                                RB_ROTATE_RIGHT(head, parent, tmp, field);\
                    546:                                tmp = RB_LEFT(parent, field);           \
                    547:                        }                                               \
                    548:                        if ((RB_LEFT(tmp, field) == NULL ||             \
                    549:                            RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
                    550:                            (RB_RIGHT(tmp, field) == NULL ||            \
                    551:                            RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
                    552:                                RB_COLOR(tmp, field) = RB_RED;          \
                    553:                                elm = parent;                           \
                    554:                                parent = RB_PARENT(elm, field);         \
                    555:                        } else {                                        \
                    556:                                if (RB_LEFT(tmp, field) == NULL ||      \
                    557:                                    RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
                    558:                                        struct type *oright;            \
1.3       misho     559:                                        if ((oright = RB_RIGHT(tmp, field))) \
1.2       misho     560:                                                RB_COLOR(oright, field) = RB_BLACK;\
                    561:                                        RB_COLOR(tmp, field) = RB_RED;  \
                    562:                                        RB_ROTATE_LEFT(head, tmp, oright, field);\
                    563:                                        tmp = RB_LEFT(parent, field);   \
                    564:                                }                                       \
                    565:                                RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
                    566:                                RB_COLOR(parent, field) = RB_BLACK;     \
                    567:                                if (RB_LEFT(tmp, field))                \
                    568:                                        RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
                    569:                                RB_ROTATE_RIGHT(head, parent, tmp, field);\
                    570:                                elm = RB_ROOT(head);                    \
                    571:                                break;                                  \
                    572:                        }                                               \
                    573:                }                                                       \
                    574:        }                                                               \
                    575:        if (elm)                                                        \
                    576:                RB_COLOR(elm, field) = RB_BLACK;                        \
                    577: }                                                                      \
                    578:                                                                        \
                    579: attr struct type *                                                     \
                    580: name##_RB_REMOVE(struct name *head, struct type *elm)                  \
                    581: {                                                                      \
                    582:        struct type *child, *parent, *old = elm;                        \
                    583:        int color;                                                      \
                    584:        if (RB_LEFT(elm, field) == NULL)                                \
                    585:                child = RB_RIGHT(elm, field);                           \
                    586:        else if (RB_RIGHT(elm, field) == NULL)                          \
                    587:                child = RB_LEFT(elm, field);                            \
                    588:        else {                                                          \
                    589:                struct type *left;                                      \
                    590:                elm = RB_RIGHT(elm, field);                             \
                    591:                while ((left = RB_LEFT(elm, field)))                    \
                    592:                        elm = left;                                     \
                    593:                child = RB_RIGHT(elm, field);                           \
                    594:                parent = RB_PARENT(elm, field);                         \
                    595:                color = RB_COLOR(elm, field);                           \
                    596:                if (child)                                              \
                    597:                        RB_PARENT(child, field) = parent;               \
                    598:                if (parent) {                                           \
                    599:                        if (RB_LEFT(parent, field) == elm)              \
                    600:                                RB_LEFT(parent, field) = child;         \
                    601:                        else                                            \
                    602:                                RB_RIGHT(parent, field) = child;        \
                    603:                        RB_AUGMENT(parent);                             \
                    604:                } else                                                  \
                    605:                        RB_ROOT(head) = child;                          \
                    606:                if (RB_PARENT(elm, field) == old)                       \
                    607:                        parent = elm;                                   \
                    608:                (elm)->field = (old)->field;                            \
                    609:                if (RB_PARENT(old, field)) {                            \
                    610:                        if (RB_LEFT(RB_PARENT(old, field), field) == old)\
                    611:                                RB_LEFT(RB_PARENT(old, field), field) = elm;\
                    612:                        else                                            \
                    613:                                RB_RIGHT(RB_PARENT(old, field), field) = elm;\
                    614:                        RB_AUGMENT(RB_PARENT(old, field));              \
                    615:                } else                                                  \
                    616:                        RB_ROOT(head) = elm;                            \
                    617:                RB_PARENT(RB_LEFT(old, field), field) = elm;            \
                    618:                if (RB_RIGHT(old, field))                               \
                    619:                        RB_PARENT(RB_RIGHT(old, field), field) = elm;   \
                    620:                if (parent) {                                           \
                    621:                        left = parent;                                  \
                    622:                        do {                                            \
                    623:                                RB_AUGMENT(left);                       \
                    624:                        } while ((left = RB_PARENT(left, field)));      \
                    625:                }                                                       \
                    626:                goto color;                                             \
                    627:        }                                                               \
                    628:        parent = RB_PARENT(elm, field);                                 \
                    629:        color = RB_COLOR(elm, field);                                   \
                    630:        if (child)                                                      \
                    631:                RB_PARENT(child, field) = parent;                       \
                    632:        if (parent) {                                                   \
                    633:                if (RB_LEFT(parent, field) == elm)                      \
                    634:                        RB_LEFT(parent, field) = child;                 \
                    635:                else                                                    \
                    636:                        RB_RIGHT(parent, field) = child;                \
                    637:                RB_AUGMENT(parent);                                     \
                    638:        } else                                                          \
                    639:                RB_ROOT(head) = child;                                  \
                    640: color:                                                                 \
                    641:        if (color == RB_BLACK)                                          \
                    642:                name##_RB_REMOVE_COLOR(head, parent, child);            \
                    643:        return (old);                                                   \
                    644: }                                                                      \
                    645:                                                                        \
                    646: /* Inserts a node into the RB tree */                                  \
                    647: attr struct type *                                                     \
                    648: name##_RB_INSERT(struct name *head, struct type *elm)                  \
                    649: {                                                                      \
                    650:        struct type *tmp;                                               \
                    651:        struct type *parent = NULL;                                     \
                    652:        int comp = 0;                                                   \
                    653:        tmp = RB_ROOT(head);                                            \
                    654:        while (tmp) {                                                   \
                    655:                parent = tmp;                                           \
                    656:                comp = (cmp)(elm, parent);                              \
                    657:                if (comp < 0)                                           \
                    658:                        tmp = RB_LEFT(tmp, field);                      \
                    659:                else if (comp > 0)                                      \
                    660:                        tmp = RB_RIGHT(tmp, field);                     \
                    661:                else                                                    \
                    662:                        return (tmp);                                   \
                    663:        }                                                               \
                    664:        RB_SET(elm, parent, field);                                     \
                    665:        if (parent != NULL) {                                           \
                    666:                if (comp < 0)                                           \
                    667:                        RB_LEFT(parent, field) = elm;                   \
                    668:                else                                                    \
                    669:                        RB_RIGHT(parent, field) = elm;                  \
                    670:                RB_AUGMENT(parent);                                     \
                    671:        } else                                                          \
                    672:                RB_ROOT(head) = elm;                                    \
                    673:        name##_RB_INSERT_COLOR(head, elm);                              \
                    674:        return (NULL);                                                  \
                    675: }                                                                      \
                    676:                                                                        \
                    677: /* Finds the node with the same key as elm */                          \
                    678: attr struct type *                                                     \
                    679: name##_RB_FIND(struct name *head, struct type *elm)                    \
                    680: {                                                                      \
                    681:        struct type *tmp = RB_ROOT(head);                               \
                    682:        int comp;                                                       \
                    683:        while (tmp) {                                                   \
                    684:                comp = cmp(elm, tmp);                                   \
                    685:                if (comp < 0)                                           \
                    686:                        tmp = RB_LEFT(tmp, field);                      \
                    687:                else if (comp > 0)                                      \
                    688:                        tmp = RB_RIGHT(tmp, field);                     \
                    689:                else                                                    \
                    690:                        return (tmp);                                   \
                    691:        }                                                               \
                    692:        return (NULL);                                                  \
                    693: }                                                                      \
                    694:                                                                        \
                    695: /* Finds the first node greater than or equal to the search key */     \
                    696: attr struct type *                                                     \
                    697: name##_RB_NFIND(struct name *head, struct type *elm)                   \
                    698: {                                                                      \
                    699:        struct type *tmp = RB_ROOT(head);                               \
                    700:        struct type *res = NULL;                                        \
                    701:        int comp;                                                       \
                    702:        while (tmp) {                                                   \
                    703:                comp = cmp(elm, tmp);                                   \
                    704:                if (comp < 0) {                                         \
                    705:                        res = tmp;                                      \
                    706:                        tmp = RB_LEFT(tmp, field);                      \
                    707:                }                                                       \
                    708:                else if (comp > 0)                                      \
                    709:                        tmp = RB_RIGHT(tmp, field);                     \
                    710:                else                                                    \
                    711:                        return (tmp);                                   \
                    712:        }                                                               \
                    713:        return (res);                                                   \
                    714: }                                                                      \
                    715:                                                                        \
                    716: /* ARGSUSED */                                                         \
                    717: attr struct type *                                                     \
                    718: name##_RB_NEXT(struct type *elm)                                       \
                    719: {                                                                      \
                    720:        if (RB_RIGHT(elm, field)) {                                     \
                    721:                elm = RB_RIGHT(elm, field);                             \
                    722:                while (RB_LEFT(elm, field))                             \
                    723:                        elm = RB_LEFT(elm, field);                      \
                    724:        } else {                                                        \
                    725:                if (RB_PARENT(elm, field) &&                            \
                    726:                    (elm == RB_LEFT(RB_PARENT(elm, field), field)))     \
                    727:                        elm = RB_PARENT(elm, field);                    \
                    728:                else {                                                  \
                    729:                        while (RB_PARENT(elm, field) &&                 \
                    730:                            (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
                    731:                                elm = RB_PARENT(elm, field);            \
                    732:                        elm = RB_PARENT(elm, field);                    \
                    733:                }                                                       \
                    734:        }                                                               \
                    735:        return (elm);                                                   \
                    736: }                                                                      \
                    737:                                                                        \
                    738: /* ARGSUSED */                                                         \
                    739: attr struct type *                                                     \
                    740: name##_RB_PREV(struct type *elm)                                       \
                    741: {                                                                      \
                    742:        if (RB_LEFT(elm, field)) {                                      \
                    743:                elm = RB_LEFT(elm, field);                              \
                    744:                while (RB_RIGHT(elm, field))                            \
                    745:                        elm = RB_RIGHT(elm, field);                     \
                    746:        } else {                                                        \
                    747:                if (RB_PARENT(elm, field) &&                            \
                    748:                    (elm == RB_RIGHT(RB_PARENT(elm, field), field)))    \
                    749:                        elm = RB_PARENT(elm, field);                    \
                    750:                else {                                                  \
                    751:                        while (RB_PARENT(elm, field) &&                 \
                    752:                            (elm == RB_LEFT(RB_PARENT(elm, field), field)))\
                    753:                                elm = RB_PARENT(elm, field);            \
                    754:                        elm = RB_PARENT(elm, field);                    \
                    755:                }                                                       \
                    756:        }                                                               \
                    757:        return (elm);                                                   \
                    758: }                                                                      \
                    759:                                                                        \
                    760: attr struct type *                                                     \
                    761: name##_RB_MINMAX(struct name *head, int val)                           \
                    762: {                                                                      \
                    763:        struct type *tmp = RB_ROOT(head);                               \
                    764:        struct type *parent = NULL;                                     \
                    765:        while (tmp) {                                                   \
                    766:                parent = tmp;                                           \
                    767:                if (val < 0)                                            \
                    768:                        tmp = RB_LEFT(tmp, field);                      \
                    769:                else                                                    \
                    770:                        tmp = RB_RIGHT(tmp, field);                     \
                    771:        }                                                               \
                    772:        return (parent);                                                \
                    773: }
                    774: 
                    775: #define RB_NEGINF      -1
                    776: #define RB_INF 1
                    777: 
                    778: #define RB_INSERT(name, x, y)  name##_RB_INSERT(x, y)
                    779: #define RB_REMOVE(name, x, y)  name##_RB_REMOVE(x, y)
                    780: #define RB_FIND(name, x, y)    name##_RB_FIND(x, y)
                    781: #define RB_NFIND(name, x, y)   name##_RB_NFIND(x, y)
                    782: #define RB_NEXT(name, x, y)    name##_RB_NEXT(y)
                    783: #define RB_PREV(name, x, y)    name##_RB_PREV(y)
                    784: #define RB_MIN(name, x)                name##_RB_MINMAX(x, RB_NEGINF)
                    785: #define RB_MAX(name, x)                name##_RB_MINMAX(x, RB_INF)
                    786: 
                    787: #define RB_FOREACH(x, name, head)                                      \
                    788:        for ((x) = RB_MIN(name, head);                                  \
                    789:             (x) != NULL;                                               \
                    790:             (x) = name##_RB_NEXT(x))
                    791: 
                    792: #define RB_FOREACH_FROM(x, name, y)                                    \
                    793:        for ((x) = (y);                                                 \
                    794:            ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL);    \
                    795:             (x) = (y))
                    796: 
                    797: #define RB_FOREACH_SAFE(x, name, head, y)                              \
                    798:        for ((x) = RB_MIN(name, head);                                  \
                    799:            ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL);    \
                    800:             (x) = (y))
                    801: 
                    802: #define RB_FOREACH_REVERSE(x, name, head)                              \
                    803:        for ((x) = RB_MAX(name, head);                                  \
                    804:             (x) != NULL;                                               \
                    805:             (x) = name##_RB_PREV(x))
                    806: 
                    807: #define RB_FOREACH_REVERSE_FROM(x, name, y)                            \
                    808:        for ((x) = (y);                                                 \
                    809:            ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL);    \
                    810:             (x) = (y))
                    811: 
                    812: #define RB_FOREACH_REVERSE_SAFE(x, name, head, y)                      \
                    813:        for ((x) = RB_MAX(name, head);                                  \
                    814:            ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL);    \
                    815:             (x) = (y))
                    816: 
                    817: /* Macros that define a avl tree */
1.4     ! misho     818: #ifndef AVL_MAX_HEIGHT
        !           819: #define AVL_MAX_HEIGHT 32
        !           820: #endif
1.2       misho     821: #define AVL_HEAD(name, type)                                           \
                    822: struct name {                                                          \
1.4     ! misho     823:        struct type     *avlh_root;     /* root of the tree */          \
1.2       misho     824: }
                    825: 
                    826: #define AVL_INITIALIZER(root)                                          \
1.4     ! misho     827:        { NULL }
1.2       misho     828: 
1.4     ! misho     829: #define AVL_INIT(root) do {                                            \
1.2       misho     830:        (root)->avlh_root = NULL;                                       \
                    831: } while (0)
                    832: 
                    833: #define AVL_ENTRY(type)                                                        \
                    834: struct {                                                               \
1.4     ! misho     835:        struct type     *avle_left;             /* left element */      \
        !           836:        struct type     *avle_right;            /* right element */     \
        !           837:        int             avle_height;            /* node height */       \
1.2       misho     838: }
                    839: 
                    840: #define AVL_LEFT(elm, field)           (elm)->field.avle_left
                    841: #define AVL_RIGHT(elm, field)          (elm)->field.avle_right
                    842: #define AVL_HEIGHT(elm, field)         (elm)->field.avle_height
                    843: #define AVL_ROOT(head)                 (head)->avlh_root
                    844: #define AVL_EMPTY(head)                        (AVL_ROOT(head) == NULL)
                    845: 
                    846: /* Generates prototypes and inline functions */
                    847: #define        AVL_PROTOTYPE(name, type, field, cmp)                           \
                    848:        AVL_PROTOTYPE_INTERNAL(name, type, field, cmp,)
                    849: #define        AVL_PROTOTYPE_STATIC(name, type, field, cmp)                    \
                    850:        AVL_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
                    851: #define AVL_PROTOTYPE_INTERNAL(name, type, field, cmp, attr)           \
                    852: attr struct type *name##_AVL_REMOVE(struct name *, struct type *);     \
                    853: attr struct type *name##_AVL_INSERT(struct name *, struct type *);     \
                    854: attr struct type *name##_AVL_FIND(struct name *, struct type *);       \
                    855: attr struct type *name##_AVL_NFIND(struct name *, struct type *);      \
                    856: attr struct type *name##_AVL_NEXT(struct name *, struct type *);       \
                    857: attr struct type *name##_AVL_PREV(struct name *, struct type *);       \
                    858: attr struct type *name##_AVL_MIN(struct name *);                       \
                    859: attr struct type *name##_AVL_MAX(struct name *);                       
                    860: 
                    861: #define AVL_ROTATE_LEFT(parent, elm, type, field) do {                                 \
                    862:        struct type *_rl = AVL_LEFT(elm, field);                                        \
                    863:        struct type *_rr = AVL_RIGHT(elm, field);                                       \
                    864:        int _l = !_rl ? 0 : AVL_HEIGHT(_rl, field);                                     \
                    865:                                                                                        \
                    866:        if (_rr && AVL_HEIGHT(_rr, field) >= _l) {                                      \
                    867:                AVL_RIGHT(*parent, field) = _rl;                                        \
                    868:                AVL_HEIGHT(*parent, field) = _l + 1;                                    \
                    869:                AVL_LEFT(elm, field) = (*parent);                                       \
                    870:                AVL_HEIGHT(elm, field) = _l + 2;                                        \
                    871:                (*parent) = (elm);                                                      \
                    872:        } else {                                                                        \
                    873:                AVL_RIGHT(*parent, field) = AVL_LEFT(_rl, field);                       \
                    874:                AVL_HEIGHT(*parent, field) = _l;                                        \
                    875:                AVL_LEFT(elm, field) = AVL_RIGHT(_rl, field);                           \
                    876:                AVL_HEIGHT(elm, field) = _l;                                            \
                    877:                AVL_LEFT(_rl, field) = (*parent);                                       \
                    878:                AVL_RIGHT(_rl, field) = (elm);                                          \
                    879:                AVL_HEIGHT(_rl, field) = _l + 1;                                        \
                    880:                (*parent) = _rl;                                                        \
                    881:        }                                                                               \
                    882: } while (0)
                    883: 
                    884: #define AVL_ROTATE_RIGHT(parent, elm, type, field) do {                                        \
                    885:        struct type *_ll = AVL_LEFT(elm, field);                                        \
                    886:        struct type *_lr = AVL_RIGHT(elm, field);                                       \
                    887:        int _r = !_lr ? 0 : AVL_HEIGHT(_lr, field);                                     \
                    888:                                                                                        \
                    889:        if (_ll && AVL_HEIGHT(_ll, field) >= _r) {                                      \
                    890:                AVL_LEFT(*(parent), field) = _lr;                                       \
                    891:                AVL_HEIGHT(*(parent), field) = _r + 1;                                  \
                    892:                AVL_RIGHT(elm, field) = *parent;                                        \
                    893:                AVL_HEIGHT(elm, field) = _r + 2;                                        \
                    894:                *(parent) = (elm);                                                      \
                    895:        } else {                                                                        \
                    896:                AVL_RIGHT(elm, field) = AVL_LEFT(_lr, field);                           \
                    897:                AVL_HEIGHT(elm, field) = _r;                                            \
                    898:                AVL_LEFT(*parent, field) = AVL_RIGHT(_lr, field);                       \
                    899:                AVL_HEIGHT(*parent, field) = _r;                                        \
                    900:                AVL_LEFT(_lr, field) = (elm);                                           \
                    901:                AVL_RIGHT(_lr, field) = (*parent);                                      \
                    902:                AVL_HEIGHT(_lr, field) = _r + 1;                                        \
                    903:                (*parent) = _lr;                                                        \
                    904:        }                                                                               \
                    905: } while (0)
                    906: 
                    907: #define AVL_REBALANCE(_anc, type, field, count)        while (count-- > 0) {                   \
                    908:        int _lh, _rh;                                                                   \
                    909:        struct type *_el = NULL;                                                        \
                    910:                                                                                        \
                    911:        _lh = !AVL_LEFT(*_anc[count], field) ? 0 :                                      \
                    912:                AVL_HEIGHT(AVL_LEFT(*_anc[count], field), field);                       \
                    913:        _rh = !AVL_RIGHT(*_anc[count], field) ? 0 :                                     \
                    914:                AVL_HEIGHT(AVL_RIGHT(*_anc[count], field), field);                      \
                    915:                                                                                        \
                    916:        if (_rh - _lh < -1) {                                                           \
                    917:                _el = AVL_LEFT(*_anc[count], field);                                    \
                    918:                AVL_ROTATE_RIGHT(_anc[count], _el, type, field);                        \
                    919:        } else if (_rh - _lh > 1) {                                                     \
                    920:                _el = AVL_RIGHT(*_anc[count], field);                                   \
                    921:                AVL_ROTATE_LEFT(_anc[count], _el, type, field);                         \
                    922:        } else if (AVL_HEIGHT(*_anc[count], field) != ((_rh > _lh) ? _rh : _lh) + 1)    \
                    923:                AVL_HEIGHT(*_anc[count], field) = ((_rh > _lh) ? _rh : _lh) + 1;        \
                    924:        else                                                                            \
                    925:                break;                                                                  \
                    926: }
                    927: 
                    928: /* Main avl operation.
                    929:  * Moves node close to the key of elm to top
                    930:  */
                    931: #define        AVL_GENERATE(name, type, field, cmp)                                            \
                    932:        AVL_GENERATE_INTERNAL(name, type, field, cmp,)
                    933: #define        AVL_GENERATE_STATIC(name, type, field, cmp)                                     \
                    934:        AVL_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
                    935: #define AVL_GENERATE_INTERNAL(name, type, field, cmp, attr)                            \
                    936: attr struct type *                                                                     \
                    937: name##_AVL_MIN(struct name *head)                                                      \
                    938: {                                                                                      \
                    939:        struct type *t = AVL_ROOT(head);                                                \
                    940:                                                                                        \
                    941:        while (t && AVL_LEFT(t, field))                                                 \
                    942:                t = AVL_LEFT(t, field);                                                 \
                    943:        return (t);                                                                     \
                    944: }                                                                                      \
                    945:                                                                                        \
                    946: attr struct type *                                                                     \
                    947: name##_AVL_MAX(struct name *head)                                                      \
                    948: {                                                                                      \
                    949:        struct type *t = AVL_ROOT(head);                                                \
                    950:                                                                                        \
                    951:        while (t && AVL_RIGHT(t, field))                                                \
                    952:                t = AVL_RIGHT(t, field);                                                \
                    953:        return (t);                                                                     \
                    954: }                                                                                      \
                    955:                                                                                        \
                    956: /* Finds the node with the same key as elm */                                          \
                    957: attr struct type *                                                                     \
                    958: name##_AVL_FIND(struct name *head, struct type *elm)                                   \
                    959: {                                                                                      \
                    960:        struct type *t = AVL_ROOT(head);                                                \
                    961:        int comp;                                                                       \
                    962:        while (t) {                                                                     \
                    963:                comp = cmp(t, elm);                                                     \
                    964:                if (!comp)                                                              \
                    965:                        return (t);                                                     \
                    966:                else if (comp < 0)                                                      \
                    967:                        t = AVL_LEFT(t, field);                                         \
                    968:                else                                                                    \
                    969:                        t = AVL_RIGHT(t, field);                                        \
                    970:        }                                                                               \
                    971:        return (NULL);                                                                  \
                    972: }                                                                                      \
                    973:                                                                                        \
                    974: /* Finds the first node less than or equal to the search key */                                \
                    975: attr struct type *                                                                     \
                    976: name##_AVL_NFIND(struct name *head, struct type *elm)                                  \
                    977: {                                                                                      \
                    978:        struct type *t = AVL_ROOT(head);                                                \
                    979:        struct type *res = NULL;                                                        \
                    980:        int comp;                                                                       \
                    981:        while (t) {                                                                     \
                    982:                comp = cmp(t, elm);                                                     \
                    983:                if (!comp)                                                              \
                    984:                        return (t);                                                     \
                    985:                else if (comp < 0) {                                                    \
                    986:                        res = t;                                                        \
                    987:                        t = AVL_LEFT(t, field);                                         \
                    988:                } else                                                                  \
                    989:                        t = AVL_RIGHT(t, field);                                        \
                    990:        }                                                                               \
                    991:        return (res);                                                                   \
                    992: }                                                                                      \
                    993:                                                                                        \
                    994: /* ARGSUSED */                                                                         \
                    995: attr struct type *                                                                     \
                    996: name##_AVL_NEXT(struct name *head, struct type *elm)                                   \
                    997: {                                                                                      \
                    998:        struct type *t = AVL_ROOT(head);                                                \
                    999:        struct type *res = NULL;                                                        \
                   1000:        int comp;                                                                       \
                   1001:        while (t) {                                                                     \
                   1002:                comp = cmp(t, elm);                                                     \
                   1003:                if (comp < 0) {                                                         \
                   1004:                        res = t;                                                        \
                   1005:                        t = AVL_LEFT(t, field);                                         \
                   1006:                } else                                                                  \
                   1007:                        t = AVL_RIGHT(t, field);                                        \
                   1008:        }                                                                               \
                   1009:        return (res);                                                                   \
                   1010: }                                                                                      \
                   1011:                                                                                        \
                   1012: /* ARGSUSED */                                                                         \
                   1013: attr struct type *                                                                     \
                   1014: name##_AVL_PREV(struct name *head, struct type *elm)                                   \
                   1015: {                                                                                      \
                   1016:        struct type *t = AVL_ROOT(head);                                                \
                   1017:        struct type *res = NULL;                                                        \
                   1018:        int comp;                                                                       \
                   1019:        while (t) {                                                                     \
                   1020:                comp = cmp(t, elm);                                                     \
                   1021:                if (comp > 0) {                                                         \
                   1022:                        res = t;                                                        \
                   1023:                        t = AVL_RIGHT(t, field);                                        \
                   1024:                } else                                                                  \
                   1025:                        t = AVL_LEFT(t, field);                                         \
                   1026:        }                                                                               \
                   1027:        return (res);                                                                   \
                   1028: }                                                                                      \
                   1029:                                                                                        \
                   1030: /* Inserts a node into the AVL tree */                                                 \
                   1031: attr struct type *                                                                     \
                   1032: name##_AVL_INSERT(struct name *head, struct type *elm)                                 \
                   1033: {                                                                                      \
                   1034:        struct type *temp, **pt;                                                        \
1.4     ! misho    1035:        struct type **ancestors[AVL_MAX_HEIGHT] = { 0 };                                \
1.2       misho    1036:        register int i;                                                                 \
                   1037:        int comp;                                                                       \
                   1038:                                                                                        \
1.4     ! misho    1039:        for (i = 0, pt = &AVL_ROOT(head); i < AVL_MAX_HEIGHT && *pt; i++) {             \
1.2       misho    1040:                temp = *pt;                                                             \
                   1041:                ancestors[i] = pt;                                                      \
                   1042:                comp = (cmp)(temp, elm);                                                \
                   1043:                if (!comp)                                                              \
                   1044:                        return temp;                                                    \
                   1045:                else if (comp < 0)                                                      \
                   1046:                        pt = &AVL_LEFT(temp, field);                                    \
                   1047:                else                                                                    \
                   1048:                        pt = &AVL_RIGHT(temp, field);                                   \
                   1049:        }                                                                               \
                   1050:        *pt = elm;                                                                      \
                   1051:                                                                                        \
                   1052:        AVL_LEFT(elm, field) = AVL_RIGHT(elm, field) = (struct type *) NULL;            \
                   1053:        AVL_HEIGHT(elm, field) = 1;                                                     \
                   1054:                                                                                        \
                   1055:        AVL_REBALANCE(ancestors, type, field, i);                                       \
                   1056:        return (NULL);                                                                  \
                   1057: }                                                                                      \
                   1058:                                                                                        \
                   1059: attr struct type *                                                                     \
                   1060: name##_AVL_REMOVE(struct name *head, struct type *elm)                                 \
                   1061: {                                                                                      \
                   1062:        struct type *temp, *old, **dp, **pt;                                            \
1.4     ! misho    1063:        struct type **ancestors[AVL_MAX_HEIGHT] = { 0 };                                \
1.2       misho    1064:        register int i;                                                                 \
                   1065:        int comp, delcnt;                                                               \
                   1066:                                                                                        \
1.4     ! misho    1067:        for (i = 0, pt = &AVL_ROOT(head); i < AVL_MAX_HEIGHT; i++) {                    \
1.2       misho    1068:                if (!*pt)                                                               \
                   1069:                        return (NULL);                                                  \
                   1070:                else                                                                    \
                   1071:                        temp = *pt;                                                     \
                   1072:                ancestors[i] = pt;                                                      \
                   1073:                comp = (cmp)(temp, elm);                                                \
                   1074:                if (!comp)                                                              \
                   1075:                        break;                                                          \
                   1076:                else if (comp < 0)                                                      \
                   1077:                        pt = &AVL_LEFT(temp, field);                                    \
                   1078:                else                                                                    \
                   1079:                        pt = &AVL_RIGHT(temp, field);                                   \
                   1080:        }                                                                               \
                   1081:        old = temp;                                                                     \
                   1082:                                                                                        \
                   1083:        if (!AVL_LEFT(temp, field)) {                                                   \
                   1084:                *pt = AVL_RIGHT(temp, field);                                           \
                   1085:                i--;                                                                    \
                   1086:        } else {                                                                        \
                   1087:                delcnt = i;                                                             \
                   1088:                dp = pt;                                                                \
1.4     ! misho    1089:                for (pt = &AVL_LEFT(temp, field); i < AVL_MAX_HEIGHT &&                 \
1.2       misho    1090:                                AVL_RIGHT(temp, field); i++) {                          \
                   1091:                        temp = *pt;                                                     \
                   1092:                        ancestors[i] = pt;                                              \
                   1093:                        pt = &AVL_RIGHT(temp, field);                                   \
                   1094:                }                                                                       \
                   1095:                *pt = AVL_LEFT(temp, field);                                            \
                   1096:                                                                                        \
                   1097:                AVL_LEFT(temp, field) = AVL_LEFT(old, field);                           \
                   1098:                AVL_RIGHT(temp, field) = AVL_RIGHT(old, field);                         \
                   1099:                AVL_HEIGHT(temp, field) = AVL_HEIGHT(old, field);                       \
                   1100:                *dp = temp;                                                             \
                   1101:                                                                                        \
                   1102:                ancestors[delcnt] = &AVL_LEFT(temp, field);                             \
                   1103:        }                                                                               \
                   1104:                                                                                        \
                   1105:        AVL_REBALANCE(ancestors, type, field, i);                                       \
                   1106:        return (old);                                                                   \
                   1107: }
                   1108: 
                   1109: #define AVL_INSERT(name, x, y) name##_AVL_INSERT(x, y)
                   1110: #define AVL_REMOVE(name, x, y) name##_AVL_REMOVE(x, y)
                   1111: #define AVL_FIND(name, x, y)   name##_AVL_FIND(x, y)
                   1112: #define AVL_NFIND(name, x, y)  name##_AVL_NFIND(x, y)
                   1113: #define AVL_NEXT(name, x, y)   name##_AVL_NEXT(x, y)
                   1114: #define AVL_PREV(name, x, y)   name##_AVL_PREV(x, y)
                   1115: #define AVL_MIN(name, x)       name##_AVL_MIN(x)
                   1116: #define AVL_MAX(name, x)       name##_AVL_MAX(x)
                   1117: 
                   1118: #define AVL_FOREACH(x, name, head)                                                     \
                   1119:        for ((x) = name##_AVL_MIN(head);                                                \
                   1120:             (x) != NULL;                                                               \
                   1121:             (x) = name##_AVL_NEXT(head, x))
                   1122: 
                   1123: #define AVL_FOREACH_REVERSE(x, name, head)                                             \
                   1124:        for ((x) = name##_AVL_MAX(head);                                                \
                   1125:             (x) != NULL;                                                               \
                   1126:             (x) = name##_AVL_PREV(head, x))
                   1127: 
                   1128: #define AVL_FOREACH_SAFE(x, name, head, y)                                             \
                   1129:        for ((x) = name##_AVL_MIN(head);                                                \
                   1130:             (x) && ((y) = name##_AVL_NEXT(head, x), (x));                              \
                   1131:             (x) = (y))
                   1132: 
                   1133: #define AVL_FOREACH_REVERSE_SAFE(x, name, head, y)                                     \
                   1134:        for ((x) = name##_AVL_MAX(head);                                                \
                   1135:             (x) && ((y) = name##_AVL_PREV(head, x), (x));                              \
                   1136:             (x) = (y))
                   1137: 
                   1138: 
                   1139: #endif /* _SYS_TREE_H_ */

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>