Return to rbtree.h CVS log

Up to [GnuMach] / Gnu-Mach / kern

Annotation of Gnu-Mach/kern/rbtree.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:  * Red-black tree.
        !            27:  */
        !            28: 
        !            29: #ifndef _KERN_RBTREE_H
        !            30: #define _KERN_RBTREE_H
        !            31: 
        !            32: #include <stddef.h>
        !            33: #include <kern/assert.h>
        !            34: #include <kern/macro_help.h>
        !            35: #include <kern/rbtree.h>
        !            36: #include <sys/types.h>
        !            37: 
        !            38: #define structof(ptr, type, member) \
        !            39:     ((type *)((char *)ptr - offsetof(type, member)))
        !            40: 
        !            41: /*
        !            42:  * Indexes of the left and right nodes in the children array of a node.
        !            43:  */
        !            44: #define RBTREE_LEFT     0
        !            45: #define RBTREE_RIGHT    1
        !            46: 
        !            47: /*
        !            48:  * Red-black node.
        !            49:  */
        !            50: struct rbtree_node;
        !            51: 
        !            52: /*
        !            53:  * Red-black tree.
        !            54:  */
        !            55: struct rbtree;
        !            56: 
        !            57: /*
        !            58:  * Static tree initializer.
        !            59:  */
        !            60: #define RBTREE_INITIALIZER { NULL }
        !            61: 
        !            62: #include "rbtree_i.h"
        !            63: 
        !            64: /*
        !            65:  * Initialize a tree.
        !            66:  */
        !            67: static inline void rbtree_init(struct rbtree *tree)
        !            68: {
        !            69:     tree->root = NULL;
        !            70: }
        !            71: 
        !            72: /*
        !            73:  * Initialize a node.
        !            74:  *
        !            75:  * A node is in no tree when its parent points to itself.
        !            76:  */
        !            77: static inline void rbtree_node_init(struct rbtree_node *node)
        !            78: {
        !            79:     assert(rbtree_check_alignment(node));
        !            80: 
        !            81:     node->parent = (unsigned long)node | RBTREE_COLOR_RED;
        !            82:     node->children[RBTREE_LEFT] = NULL;
        !            83:     node->children[RBTREE_RIGHT] = NULL;
        !            84: }
        !            85: 
        !            86: /*
        !            87:  * Return true if node is in no tree.
        !            88:  */
        !            89: static inline int rbtree_node_unlinked(const struct rbtree_node *node)
        !            90: {
        !            91:     return rbtree_parent(node) == node;
        !            92: }
        !            93: 
        !            94: /*
        !            95:  * Macro that evaluates to the address of the structure containing the
        !            96:  * given node based on the given type and member.
        !            97:  */
        !            98: #define rbtree_entry(node, type, member) structof(node, type, member)
        !            99: 
        !           100: /*
        !           101:  * Return true if tree is empty.
        !           102:  */
        !           103: static inline int rbtree_empty(const struct rbtree *tree)
        !           104: {
        !           105:     return tree->root == NULL;
        !           106: }
        !           107: 
        !           108: /*
        !           109:  * Look up a node in a tree.
        !           110:  *
        !           111:  * Note that implementing the lookup algorithm as a macro gives two benefits:
        !           112:  * First, it avoids the overhead of a callback function. Next, the type of the
        !           113:  * cmp_fn parameter isn't rigid. The only guarantee offered by this
        !           114:  * implementation is that the key parameter is the first parameter given to
        !           115:  * cmp_fn. This way, users can pass only the value they need for comparison
        !           116:  * instead of e.g. allocating a full structure on the stack.
        !           117:  *
        !           118:  * See rbtree_insert().
        !           119:  */
        !           120: #define rbtree_lookup(tree, key, cmp_fn)                \
        !           121: MACRO_BEGIN                                             \
        !           122:     struct rbtree_node *___cur;                         \
        !           123:     int ___diff;                                        \
        !           124:                                                         \
        !           125:     ___cur = (tree)->root;                              \
        !           126:                                                         \
        !           127:     while (___cur != NULL) {                            \
        !           128:         ___diff = cmp_fn(key, ___cur);                  \
        !           129:                                                         \
        !           130:         if (___diff == 0)                               \
        !           131:             break;                                      \
        !           132:                                                         \
        !           133:         ___cur = ___cur->children[rbtree_d2i(___diff)]; \
        !           134:     }                                                   \
        !           135:                                                         \
        !           136:     ___cur;                                             \
        !           137: MACRO_END
        !           138: 
        !           139: /*
        !           140:  * Look up a node or one of its nearest nodes in a tree.
        !           141:  *
        !           142:  * This macro essentially acts as rbtree_lookup() but if no entry matched
        !           143:  * the key, an additional step is performed to obtain the next or previous
        !           144:  * node, depending on the direction (left or right).
        !           145:  *
        !           146:  * The constraints that apply to the key parameter are the same as for
        !           147:  * rbtree_lookup().
        !           148:  */
        !           149: #define rbtree_lookup_nearest(tree, key, cmp_fn, dir)       \
        !           150: MACRO_BEGIN                                                 \
        !           151:     struct rbtree_node *___cur, *___prev;                   \
        !           152:     int ___diff, ___index;                                  \
        !           153:                                                             \
        !           154:     ___prev = NULL;                                         \
        !           155:     ___index = -1;                                          \
        !           156:     ___cur = (tree)->root;                                  \
        !           157:                                                             \
        !           158:     while (___cur != NULL) {                                \
        !           159:         ___diff = cmp_fn(key, ___cur);                      \
        !           160:                                                             \
        !           161:         if (___diff == 0)                                   \
        !           162:             break;                                          \
        !           163:                                                             \
        !           164:         ___prev = ___cur;                                   \
        !           165:         ___index = rbtree_d2i(___diff);                     \
        !           166:         ___cur = ___cur->children[___index];                \
        !           167:     }                                                       \
        !           168:                                                             \
        !           169:     if (___cur == NULL)                                     \
        !           170:         ___cur = rbtree_nearest(___prev, ___index, dir);    \
        !           171:                                                             \
        !           172:     ___cur;                                                 \
        !           173: MACRO_END
        !           174: 
        !           175: /*
        !           176:  * Insert a node in a tree.
        !           177:  *
        !           178:  * This macro performs a standard lookup to obtain the insertion point of
        !           179:  * the given node in the tree (it is assumed that the inserted node never
        !           180:  * compares equal to any other entry in the tree) and links the node. It
        !           181:  * then It then checks red-black rules violations, and rebalances the tree
        !           182:  * if necessary.
        !           183:  *
        !           184:  * Unlike rbtree_lookup(), the cmp_fn parameter must compare two complete
        !           185:  * entries, so it is suggested to use two different comparison inline
        !           186:  * functions, such as myobj_cmp_lookup() and myobj_cmp_insert(). There is no
        !           187:  * guarantee about the order of the nodes given to the comparison function.
        !           188:  *
        !           189:  * See rbtree_lookup().
        !           190:  */
        !           191: #define rbtree_insert(tree, node, cmp_fn)                   \
        !           192: MACRO_BEGIN                                                 \
        !           193:     struct rbtree_node *___cur, *___prev;                   \
        !           194:     int ___diff, ___index;                                  \
        !           195:                                                             \
        !           196:     ___prev = NULL;                                         \
        !           197:     ___index = -1;                                          \
        !           198:     ___cur = (tree)->root;                                  \
        !           199:                                                             \
        !           200:     while (___cur != NULL) {                                \
        !           201:         ___diff = cmp_fn(node, ___cur);                     \
        !           202:         assert(___diff != 0);                               \
        !           203:         ___prev = ___cur;                                   \
        !           204:         ___index = rbtree_d2i(___diff);                     \
        !           205:         ___cur = ___cur->children[___index];                \
        !           206:     }                                                       \
        !           207:                                                             \
        !           208:     rbtree_insert_rebalance(tree, ___prev, ___index, node); \
        !           209: MACRO_END
        !           210: 
        !           211: /*
        !           212:  * Look up a node/slot pair in a tree.
        !           213:  *
        !           214:  * This macro essentially acts as rbtree_lookup() but in addition to a node,
        !           215:  * it also returns a slot, which identifies an insertion point in the tree.
        !           216:  * If the returned node is null, the slot can be used by rbtree_insert_slot()
        !           217:  * to insert without the overhead of an additional lookup. The slot is a
        !           218:  * simple unsigned long integer.
        !           219:  *
        !           220:  * The constraints that apply to the key parameter are the same as for
        !           221:  * rbtree_lookup().
        !           222:  */
        !           223: #define rbtree_lookup_slot(tree, key, cmp_fn, slot) \
        !           224: MACRO_BEGIN                                         \
        !           225:     struct rbtree_node *___cur, *___prev;           \
        !           226:     int ___diff, ___index;                          \
        !           227:                                                     \
        !           228:     ___prev = NULL;                                 \
        !           229:     ___index = 0;                                   \
        !           230:     ___cur = (tree)->root;                          \
        !           231:                                                     \
        !           232:     while (___cur != NULL) {                        \
        !           233:         ___diff = cmp_fn(key, ___cur);              \
        !           234:                                                     \
        !           235:         if (___diff == 0)                           \
        !           236:             break;                                  \
        !           237:                                                     \
        !           238:         ___prev = ___cur;                           \
        !           239:         ___index = rbtree_d2i(___diff);             \
        !           240:         ___cur = ___cur->children[___index];        \
        !           241:     }                                               \
        !           242:                                                     \
        !           243:     (slot) = rbtree_slot(___prev, ___index);        \
        !           244:     ___cur;                                         \
        !           245: MACRO_END
        !           246: 
        !           247: /*
        !           248:  * Insert a node at an insertion point in a tree.
        !           249:  *
        !           250:  * This macro essentially acts as rbtree_insert() except that it doesn't
        !           251:  * obtain the insertion point with a standard lookup. The insertion point
        !           252:  * is obtained by calling rbtree_lookup_slot(). In addition, the new node
        !           253:  * must not compare equal to an existing node in the tree (i.e. the slot
        !           254:  * must denote a null node).
        !           255:  */
        !           256: static inline void
        !           257: rbtree_insert_slot(struct rbtree *tree, unsigned long slot,
        !           258:                    struct rbtree_node *node)
        !           259: {
        !           260:     struct rbtree_node *parent;
        !           261:     int index;
        !           262: 
        !           263:     parent = rbtree_slot_parent(slot);
        !           264:     index = rbtree_slot_index(slot);
        !           265:     rbtree_insert_rebalance(tree, parent, index, node);
        !           266: }
        !           267: 
        !           268: /*
        !           269:  * Remove a node from a tree.
        !           270:  *
        !           271:  * After completion, the node is stale.
        !           272:  */
        !           273: void rbtree_remove(struct rbtree *tree, struct rbtree_node *node);
        !           274: 
        !           275: /*
        !           276:  * Return the first node of a tree.
        !           277:  */
        !           278: #define rbtree_first(tree) rbtree_firstlast(tree, RBTREE_LEFT)
        !           279: 
        !           280: /*
        !           281:  * Return the last node of a tree.
        !           282:  */
        !           283: #define rbtree_last(tree) rbtree_firstlast(tree, RBTREE_RIGHT)
        !           284: 
        !           285: /*
        !           286:  * Return the node previous to the given node.
        !           287:  */
        !           288: #define rbtree_prev(node) rbtree_walk(node, RBTREE_LEFT)
        !           289: 
        !           290: /*
        !           291:  * Return the node next to the given node.
        !           292:  */
        !           293: #define rbtree_next(node) rbtree_walk(node, RBTREE_RIGHT)
        !           294: 
        !           295: /*
        !           296:  * Forge a loop to process all nodes of a tree, removing them when visited.
        !           297:  *
        !           298:  * This macro can only be used to destroy a tree, so that the resources used
        !           299:  * by the entries can be released by the user. It basically removes all nodes
        !           300:  * without doing any color checking.
        !           301:  *
        !           302:  * After completion, all nodes and the tree root member are stale.
        !           303:  */
        !           304: #define rbtree_for_each_remove(tree, node, tmp)         \
        !           305: for (node = rbtree_postwalk_deepest(tree),              \
        !           306:      tmp = rbtree_postwalk_unlink(node);                \
        !           307:      node != NULL;                                      \
        !           308:      node = tmp, tmp = rbtree_postwalk_unlink(node))    \
        !           309: 
        !           310: #endif /* _KERN_RBTREE_H */

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