Return to rbtree.c CVS log

Up to [GnuMach] / Gnu-Mach / kern

Annotation of Gnu-Mach/kern/rbtree.c, revision 1.1

1.1     ! root        1: /*
        !             2:  * Copyright (c) 2010, 2012 Richard Braun.
        !             3:  * All rights reserved.
        !             4:  *
        !             5:  * Redistribution and use in source and binary forms, with or without
        !             6:  * modification, are permitted provided that the following conditions
        !             7:  * are met:
        !             8:  * 1. Redistributions of source code must retain the above copyright
        !             9:  *    notice, this list of conditions and the following disclaimer.
        !            10:  * 2. Redistributions in binary form must reproduce the above copyright
        !            11:  *    notice, this list of conditions and the following disclaimer in the
        !            12:  *    documentation and/or other materials provided with the distribution.
        !            13:  *
        !            14:  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
        !            15:  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
        !            16:  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
        !            17:  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
        !            18:  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
        !            19:  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
        !            20:  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
        !            21:  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
        !            22:  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
        !            23:  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
        !            24:  */
        !            25: 
        !            26: #include <kern/assert.h>
        !            27: #include <kern/rbtree.h>
        !            28: #include <kern/rbtree_i.h>
        !            29: #include <sys/types.h>
        !            30: 
        !            31: #define unlikely(expr) __builtin_expect(!!(expr), 0)
        !            32: 
        !            33: /*
        !            34:  * Return the index of a node in the children array of its parent.
        !            35:  *
        !            36:  * The parent parameter must not be null, and must be the parent of the
        !            37:  * given node.
        !            38:  */
        !            39: static inline int rbtree_index(const struct rbtree_node *node,
        !            40:                                const struct rbtree_node *parent)
        !            41: {
        !            42:     assert(parent != NULL);
        !            43:     assert((node == NULL) || (rbtree_parent(node) == parent));
        !            44: 
        !            45:     if (parent->children[RBTREE_LEFT] == node)
        !            46:         return RBTREE_LEFT;
        !            47: 
        !            48:     assert(parent->children[RBTREE_RIGHT] == node);
        !            49: 
        !            50:     return RBTREE_RIGHT;
        !            51: }
        !            52: 
        !            53: /*
        !            54:  * Return the color of a node.
        !            55:  */
        !            56: static inline int rbtree_color(const struct rbtree_node *node)
        !            57: {
        !            58:     return node->parent & RBTREE_COLOR_MASK;
        !            59: }
        !            60: 
        !            61: /*
        !            62:  * Return true if the node is red.
        !            63:  */
        !            64: static inline int rbtree_is_red(const struct rbtree_node *node)
        !            65: {
        !            66:     return rbtree_color(node) == RBTREE_COLOR_RED;
        !            67: }
        !            68: 
        !            69: /*
        !            70:  * Return true if the node is black.
        !            71:  */
        !            72: static inline int rbtree_is_black(const struct rbtree_node *node)
        !            73: {
        !            74:     return rbtree_color(node) == RBTREE_COLOR_BLACK;
        !            75: }
        !            76: 
        !            77: /*
        !            78:  * Set the parent of a node, retaining its current color.
        !            79:  */
        !            80: static inline void rbtree_set_parent(struct rbtree_node *node,
        !            81:                                      struct rbtree_node *parent)
        !            82: {
        !            83:     assert(rbtree_check_alignment(node));
        !            84:     assert(rbtree_check_alignment(parent));
        !            85: 
        !            86:     node->parent = (unsigned long)parent | (node->parent & RBTREE_COLOR_MASK);
        !            87: }
        !            88: 
        !            89: /*
        !            90:  * Set the color of a node, retaining its current parent.
        !            91:  */
        !            92: static inline void rbtree_set_color(struct rbtree_node *node, int color)
        !            93: {
        !            94:     assert((color & ~RBTREE_COLOR_MASK) == 0);
        !            95:     node->parent = (node->parent & RBTREE_PARENT_MASK) | color;
        !            96: }
        !            97: 
        !            98: /*
        !            99:  * Set the color of a node to red, retaining its current parent.
        !           100:  */
        !           101: static inline void rbtree_set_red(struct rbtree_node *node)
        !           102: {
        !           103:     rbtree_set_color(node, RBTREE_COLOR_RED);
        !           104: }
        !           105: 
        !           106: /*
        !           107:  * Set the color of a node to black, retaining its current parent.
        !           108:  */
        !           109: static inline void rbtree_set_black(struct rbtree_node *node)
        !           110: {
        !           111:     rbtree_set_color(node, RBTREE_COLOR_BLACK);
        !           112: }
        !           113: 
        !           114: /*
        !           115:  * Perform a tree rotation, rooted at the given node.
        !           116:  *
        !           117:  * The direction parameter defines the rotation direction and is either
        !           118:  * RBTREE_LEFT or RBTREE_RIGHT.
        !           119:  */
        !           120: static void rbtree_rotate(struct rbtree *tree, struct rbtree_node *node,
        !           121:                           int direction)
        !           122: {
        !           123:     struct rbtree_node *parent, *rnode;
        !           124:     int left, right;
        !           125: 
        !           126:     left = direction;
        !           127:     right = 1 - left;
        !           128:     parent = rbtree_parent(node);
        !           129:     rnode = node->children[right];
        !           130: 
        !           131:     node->children[right] = rnode->children[left];
        !           132: 
        !           133:     if (rnode->children[left] != NULL)
        !           134:         rbtree_set_parent(rnode->children[left], node);
        !           135: 
        !           136:     rnode->children[left] = node;
        !           137:     rbtree_set_parent(rnode, parent);
        !           138: 
        !           139:     if (unlikely(parent == NULL))
        !           140:         tree->root = rnode;
        !           141:     else
        !           142:         parent->children[rbtree_index(node, parent)] = rnode;
        !           143: 
        !           144:     rbtree_set_parent(node, rnode);
        !           145: }
        !           146: 
        !           147: void rbtree_insert_rebalance(struct rbtree *tree, struct rbtree_node *parent,
        !           148:                              int index, struct rbtree_node *node)
        !           149: {
        !           150:     struct rbtree_node *grand_parent, *uncle, *tmp;
        !           151:     int left, right;
        !           152: 
        !           153:     assert(rbtree_check_alignment(parent));
        !           154:     assert(rbtree_check_alignment(node));
        !           155: 
        !           156:     node->parent = (unsigned long)parent | RBTREE_COLOR_RED;
        !           157:     node->children[RBTREE_LEFT] = NULL;
        !           158:     node->children[RBTREE_RIGHT] = NULL;
        !           159: 
        !           160:     if (unlikely(parent == NULL))
        !           161:         tree->root = node;
        !           162:     else
        !           163:         parent->children[index] = node;
        !           164: 
        !           165:     for (;;) {
        !           166:         if (parent == NULL) {
        !           167:             rbtree_set_black(node);
        !           168:             break;
        !           169:         }
        !           170: 
        !           171:         if (rbtree_is_black(parent))
        !           172:             break;
        !           173: 
        !           174:         grand_parent = rbtree_parent(parent);
        !           175:         assert(grand_parent != NULL);
        !           176: 
        !           177:         left = rbtree_index(parent, grand_parent);
        !           178:         right = 1 - left;
        !           179: 
        !           180:         uncle = grand_parent->children[right];
        !           181: 
        !           182:         /*
        !           183:          * Uncle is red. Flip colors and repeat at grand parent.
        !           184:          */
        !           185:         if ((uncle != NULL) && rbtree_is_red(uncle)) {
        !           186:             rbtree_set_black(uncle);
        !           187:             rbtree_set_black(parent);
        !           188:             rbtree_set_red(grand_parent);
        !           189:             node = grand_parent;
        !           190:             parent = rbtree_parent(node);
        !           191:             continue;
        !           192:         }
        !           193: 
        !           194:         /*
        !           195:          * Node is the right child of its parent. Rotate left at parent.
        !           196:          */
        !           197:         if (parent->children[right] == node) {
        !           198:             rbtree_rotate(tree, parent, left);
        !           199:             tmp = node;
        !           200:             node = parent;
        !           201:             parent = tmp;
        !           202:         }
        !           203: 
        !           204:         /*
        !           205:          * Node is the left child of its parent. Handle colors, rotate right
        !           206:          * at grand parent, and leave.
        !           207:          */
        !           208:         rbtree_set_black(parent);
        !           209:         rbtree_set_red(grand_parent);
        !           210:         rbtree_rotate(tree, grand_parent, right);
        !           211:         break;
        !           212:     }
        !           213: 
        !           214:     assert(rbtree_is_black(tree->root));
        !           215: }
        !           216: 
        !           217: void rbtree_remove(struct rbtree *tree, struct rbtree_node *node)
        !           218: {
        !           219:     struct rbtree_node *child, *parent, *brother;
        !           220:     int color, left, right;
        !           221: 
        !           222:     if (node->children[RBTREE_LEFT] == NULL)
        !           223:         child = node->children[RBTREE_RIGHT];
        !           224:     else if (node->children[RBTREE_RIGHT] == NULL)
        !           225:         child = node->children[RBTREE_LEFT];
        !           226:     else {
        !           227:         struct rbtree_node *successor;
        !           228: 
        !           229:         /*
        !           230:          * Two-children case: replace the node with its successor.
        !           231:          */
        !           232: 
        !           233:         successor = node->children[RBTREE_RIGHT];
        !           234: 
        !           235:         while (successor->children[RBTREE_LEFT] != NULL)
        !           236:             successor = successor->children[RBTREE_LEFT];
        !           237: 
        !           238:         color = rbtree_color(successor);
        !           239:         child = successor->children[RBTREE_RIGHT];
        !           240:         parent = rbtree_parent(node);
        !           241: 
        !           242:         if (unlikely(parent == NULL))
        !           243:             tree->root = successor;
        !           244:         else
        !           245:             parent->children[rbtree_index(node, parent)] = successor;
        !           246: 
        !           247:         parent = rbtree_parent(successor);
        !           248: 
        !           249:         /*
        !           250:          * Set parent directly to keep the original color.
        !           251:          */
        !           252:         successor->parent = node->parent;
        !           253:         successor->children[RBTREE_LEFT] = node->children[RBTREE_LEFT];
        !           254:         rbtree_set_parent(successor->children[RBTREE_LEFT], successor);
        !           255: 
        !           256:         if (node == parent)
        !           257:             parent = successor;
        !           258:         else {
        !           259:             successor->children[RBTREE_RIGHT] = node->children[RBTREE_RIGHT];
        !           260:             rbtree_set_parent(successor->children[RBTREE_RIGHT], successor);
        !           261:             parent->children[RBTREE_LEFT] = child;
        !           262: 
        !           263:             if (child != NULL)
        !           264:                 rbtree_set_parent(child, parent);
        !           265:         }
        !           266: 
        !           267:         goto update_color;
        !           268:     }
        !           269: 
        !           270:     /*
        !           271:      * Node has at most one child.
        !           272:      */
        !           273: 
        !           274:     color = rbtree_color(node);
        !           275:     parent = rbtree_parent(node);
        !           276: 
        !           277:     if (child != NULL)
        !           278:         rbtree_set_parent(child, parent);
        !           279: 
        !           280:     if (unlikely(parent == NULL))
        !           281:         tree->root = child;
        !           282:     else
        !           283:         parent->children[rbtree_index(node, parent)] = child;
        !           284: 
        !           285:     /*
        !           286:      * The node has been removed, update the colors. The child pointer can
        !           287:      * be null, in which case it is considered a black leaf.
        !           288:      */
        !           289: update_color:
        !           290:     if (color == RBTREE_COLOR_RED)
        !           291:         return;
        !           292: 
        !           293:     for (;;) {
        !           294:         if ((child != NULL) && rbtree_is_red(child)) {
        !           295:             rbtree_set_black(child);
        !           296:             break;
        !           297:         }
        !           298: 
        !           299:         if (parent == NULL)
        !           300:             break;
        !           301: 
        !           302:         left = rbtree_index(child, parent);
        !           303:         right = 1 - left;
        !           304: 
        !           305:         brother = parent->children[right];
        !           306: 
        !           307:         /*
        !           308:          * Brother is red. Recolor and rotate left at parent so that brother
        !           309:          * becomes black.
        !           310:          */
        !           311:         if (rbtree_is_red(brother)) {
        !           312:             rbtree_set_black(brother);
        !           313:             rbtree_set_red(parent);
        !           314:             rbtree_rotate(tree, parent, left);
        !           315:             brother = parent->children[right];
        !           316:         }
        !           317: 
        !           318:         /*
        !           319:          * Brother has no red child. Recolor and repeat at parent.
        !           320:          */
        !           321:         if (((brother->children[RBTREE_LEFT] == NULL)
        !           322:              || rbtree_is_black(brother->children[RBTREE_LEFT]))
        !           323:             && ((brother->children[RBTREE_RIGHT] == NULL)
        !           324:                 || rbtree_is_black(brother->children[RBTREE_RIGHT]))) {
        !           325:             rbtree_set_red(brother);
        !           326:             child = parent;
        !           327:             parent = rbtree_parent(child);
        !           328:             continue;
        !           329:         }
        !           330: 
        !           331:         /*
        !           332:          * Brother's right child is black. Recolor and rotate right at brother.
        !           333:          */
        !           334:         if ((brother->children[right] == NULL)
        !           335:             || rbtree_is_black(brother->children[right])) {
        !           336:             rbtree_set_black(brother->children[left]);
        !           337:             rbtree_set_red(brother);
        !           338:             rbtree_rotate(tree, brother, right);
        !           339:             brother = parent->children[right];
        !           340:         }
        !           341: 
        !           342:         /*
        !           343:          * Brother's left child is black. Exchange parent and brother colors
        !           344:          * (we already know brother is black), set brother's right child black,
        !           345:          * rotate left at parent and leave.
        !           346:          */
        !           347:         rbtree_set_color(brother, rbtree_color(parent));
        !           348:         rbtree_set_black(parent);
        !           349:         rbtree_set_black(brother->children[right]);
        !           350:         rbtree_rotate(tree, parent, left);
        !           351:         break;
        !           352:     }
        !           353: 
        !           354:     assert((tree->root == NULL) || rbtree_is_black(tree->root));
        !           355: }
        !           356: 
        !           357: struct rbtree_node * rbtree_nearest(struct rbtree_node *parent, int index,
        !           358:                                     int direction)
        !           359: {
        !           360:     assert(rbtree_check_index(direction));
        !           361: 
        !           362:     if (parent == NULL)
        !           363:         return NULL;
        !           364: 
        !           365:     assert(rbtree_check_index(index));
        !           366: 
        !           367:     if (index != direction)
        !           368:         return parent;
        !           369: 
        !           370:     return rbtree_walk(parent, direction);
        !           371: }
        !           372: 
        !           373: struct rbtree_node * rbtree_firstlast(const struct rbtree *tree, int direction)
        !           374: {
        !           375:     struct rbtree_node *prev, *cur;
        !           376: 
        !           377:     assert(rbtree_check_index(direction));
        !           378: 
        !           379:     prev = NULL;
        !           380: 
        !           381:     for (cur = tree->root; cur != NULL; cur = cur->children[direction])
        !           382:         prev = cur;
        !           383: 
        !           384:     return prev;
        !           385: }
        !           386: 
        !           387: struct rbtree_node * rbtree_walk(struct rbtree_node *node, int direction)
        !           388: {
        !           389:     int left, right;
        !           390: 
        !           391:     assert(rbtree_check_index(direction));
        !           392: 
        !           393:     left = direction;
        !           394:     right = 1 - left;
        !           395: 
        !           396:     if (node == NULL)
        !           397:         return NULL;
        !           398: 
        !           399:     if (node->children[left] != NULL) {
        !           400:         node = node->children[left];
        !           401: 
        !           402:         while (node->children[right] != NULL)
        !           403:             node = node->children[right];
        !           404:     } else {
        !           405:         struct rbtree_node *parent;
        !           406:         int index;
        !           407: 
        !           408:         for (;;) {
        !           409:             parent = rbtree_parent(node);
        !           410: 
        !           411:             if (parent == NULL)
        !           412:                 return NULL;
        !           413: 
        !           414:             index = rbtree_index(node, parent);
        !           415:             node = parent;
        !           416: 
        !           417:             if (index == right)
        !           418:                 break;
        !           419:         }
        !           420:     }
        !           421: 
        !           422:     return node;
        !           423: }
        !           424: 
        !           425: /*
        !           426:  * Return the left-most deepest child node of the given node.
        !           427:  */
        !           428: static struct rbtree_node * rbtree_find_deepest(struct rbtree_node *node)
        !           429: {
        !           430:     struct rbtree_node *parent;
        !           431: 
        !           432:     assert(node != NULL);
        !           433: 
        !           434:     for (;;) {
        !           435:         parent = node;
        !           436:         node = node->children[RBTREE_LEFT];
        !           437: 
        !           438:         if (node == NULL) {
        !           439:             node = parent->children[RBTREE_RIGHT];
        !           440: 
        !           441:             if (node == NULL)
        !           442:                 return parent;
        !           443:         }
        !           444:     }
        !           445: }
        !           446: 
        !           447: struct rbtree_node * rbtree_postwalk_deepest(const struct rbtree *tree)
        !           448: {
        !           449:     struct rbtree_node *node;
        !           450: 
        !           451:     node = tree->root;
        !           452: 
        !           453:     if (node == NULL)
        !           454:         return NULL;
        !           455: 
        !           456:     return rbtree_find_deepest(node);
        !           457: }
        !           458: 
        !           459: struct rbtree_node * rbtree_postwalk_unlink(struct rbtree_node *node)
        !           460: {
        !           461:     struct rbtree_node *parent;
        !           462:     int index;
        !           463: 
        !           464:     if (node == NULL)
        !           465:         return NULL;
        !           466: 
        !           467:     assert(node->children[RBTREE_LEFT] == NULL);
        !           468:     assert(node->children[RBTREE_RIGHT] == NULL);
        !           469: 
        !           470:     parent = rbtree_parent(node);
        !           471: 
        !           472:     if (parent == NULL)
        !           473:         return NULL;
        !           474: 
        !           475:     index = rbtree_index(node, parent);
        !           476:     parent->children[index] = NULL;
        !           477:     node = parent->children[RBTREE_RIGHT];
        !           478: 
        !           479:     if (node == NULL)
        !           480:         return parent;
        !           481: 
        !           482:     return rbtree_find_deepest(node);
        !           483: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.