Return to rbtree_i.h CVS log

Up to [GnuMach] / Gnu-Mach / kern

Annotation of Gnu-Mach/kern/rbtree_i.h, revision 1.1

1.1     ! root        1: /*
        !             2:  * Copyright (c) 2010, 2011 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: #ifndef _KERN_RBTREE_I_H
        !            27: #define _KERN_RBTREE_I_H
        !            28: 
        !            29: #include <kern/assert.h>
        !            30: 
        !            31: /*
        !            32:  * Red-black node structure.
        !            33:  *
        !            34:  * To reduce the number of branches and the instruction cache footprint,
        !            35:  * the left and right child pointers are stored in an array, and the symmetry
        !            36:  * of most tree operations is exploited by using left/right variables when
        !            37:  * referring to children.
        !            38:  *
        !            39:  * In addition, this implementation assumes that all nodes are 4-byte aligned,
        !            40:  * so that the least significant bit of the parent member can be used to store
        !            41:  * the color of the node. This is true for all modern 32 and 64 bits
        !            42:  * architectures, as long as the nodes aren't embedded in structures with
        !            43:  * special alignment constraints such as member packing.
        !            44:  */
        !            45: struct rbtree_node {
        !            46:     unsigned long parent;
        !            47:     struct rbtree_node *children[2];
        !            48: };
        !            49: 
        !            50: /*
        !            51:  * Red-black tree structure.
        !            52:  */
        !            53: struct rbtree {
        !            54:     struct rbtree_node *root;
        !            55: };
        !            56: 
        !            57: /*
        !            58:  * Masks applied on the parent member of a node to obtain either the
        !            59:  * color or the parent address.
        !            60:  */
        !            61: #define RBTREE_COLOR_MASK   0x1UL
        !            62: #define RBTREE_PARENT_MASK  (~0x3UL)
        !            63: 
        !            64: /*
        !            65:  * Node colors.
        !            66:  */
        !            67: #define RBTREE_COLOR_RED    0
        !            68: #define RBTREE_COLOR_BLACK  1
        !            69: 
        !            70: /*
        !            71:  * Masks applied on slots to obtain either the child index or the parent
        !            72:  * address.
        !            73:  */
        !            74: #define RBTREE_SLOT_INDEX_MASK  0x1UL
        !            75: #define RBTREE_SLOT_PARENT_MASK (~RBTREE_SLOT_INDEX_MASK)
        !            76: 
        !            77: /*
        !            78:  * Return true if the given pointer is suitably aligned.
        !            79:  */
        !            80: static inline int rbtree_check_alignment(const struct rbtree_node *node)
        !            81: {
        !            82:     return ((unsigned long)node & (~RBTREE_PARENT_MASK)) == 0;
        !            83: }
        !            84: 
        !            85: /*
        !            86:  * Return true if the given index is a valid child index.
        !            87:  */
        !            88: static inline int rbtree_check_index(int index)
        !            89: {
        !            90:     return index == (index & 1);
        !            91: }
        !            92: 
        !            93: /*
        !            94:  * Convert the result of a comparison into an index in the children array
        !            95:  * (0 or 1).
        !            96:  *
        !            97:  * This function is mostly used when looking up a node.
        !            98:  */
        !            99: static inline int rbtree_d2i(int diff)
        !           100: {
        !           101:     return !(diff <= 0);
        !           102: }
        !           103: 
        !           104: /*
        !           105:  * Return the parent of a node.
        !           106:  */
        !           107: static inline struct rbtree_node * rbtree_parent(const struct rbtree_node *node)
        !           108: {
        !           109:     return (struct rbtree_node *)(node->parent & RBTREE_PARENT_MASK);
        !           110: }
        !           111: 
        !           112: /*
        !           113:  * Translate an insertion point into a slot.
        !           114:  */
        !           115: static inline unsigned long rbtree_slot(struct rbtree_node *parent, int index)
        !           116: {
        !           117:     assert(rbtree_check_alignment(parent));
        !           118:     assert(rbtree_check_index(index));
        !           119:     return (unsigned long)parent | index;
        !           120: }
        !           121: 
        !           122: /*
        !           123:  * Extract the parent address from a slot.
        !           124:  */
        !           125: static inline struct rbtree_node * rbtree_slot_parent(unsigned long slot)
        !           126: {
        !           127:     return (struct rbtree_node *)(slot & RBTREE_SLOT_PARENT_MASK);
        !           128: }
        !           129: 
        !           130: /*
        !           131:  * Extract the index from a slot.
        !           132:  */
        !           133: static inline int rbtree_slot_index(unsigned long slot)
        !           134: {
        !           135:     return slot & RBTREE_SLOT_INDEX_MASK;
        !           136: }
        !           137: 
        !           138: /*
        !           139:  * Insert a node in a tree, rebalancing it if necessary.
        !           140:  *
        !           141:  * The index parameter is the index in the children array of the parent where
        !           142:  * the new node is to be inserted. It is ignored if the parent is null.
        !           143:  *
        !           144:  * This function is intended to be used by the rbtree_insert() macro only.
        !           145:  */
        !           146: void rbtree_insert_rebalance(struct rbtree *tree, struct rbtree_node *parent,
        !           147:                              int index, struct rbtree_node *node);
        !           148: 
        !           149: /*
        !           150:  * Return the previous or next node relative to a location in a tree.
        !           151:  *
        !           152:  * The parent and index parameters define the location, which can be empty.
        !           153:  * The direction parameter is either RBTREE_LEFT (to obtain the previous
        !           154:  * node) or RBTREE_RIGHT (to obtain the next one).
        !           155:  */
        !           156: struct rbtree_node * rbtree_nearest(struct rbtree_node *parent, int index,
        !           157:                                     int direction);
        !           158: 
        !           159: /*
        !           160:  * Return the first or last node of a tree.
        !           161:  *
        !           162:  * The direction parameter is either RBTREE_LEFT (to obtain the first node)
        !           163:  * or RBTREE_RIGHT (to obtain the last one).
        !           164:  */
        !           165: struct rbtree_node * rbtree_firstlast(const struct rbtree *tree, int direction);
        !           166: 
        !           167: /*
        !           168:  * Return the node next to, or previous to the given node.
        !           169:  *
        !           170:  * The direction parameter is either RBTREE_LEFT (to obtain the previous node)
        !           171:  * or RBTREE_RIGHT (to obtain the next one).
        !           172:  */
        !           173: struct rbtree_node * rbtree_walk(struct rbtree_node *node, int direction);
        !           174: 
        !           175: /*
        !           176:  * Return the left-most deepest node of a tree, which is the starting point of
        !           177:  * the postorder traversal performed by rbtree_for_each_remove().
        !           178:  */
        !           179: struct rbtree_node * rbtree_postwalk_deepest(const struct rbtree *tree);
        !           180: 
        !           181: /*
        !           182:  * Unlink a node from its tree and return the next (right) node in postorder.
        !           183:  */
        !           184: struct rbtree_node * rbtree_postwalk_unlink(struct rbtree_node *node);
        !           185: 
        !           186: #endif /* _KERN_RBTREE_I_H */

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