![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to rbtree_i.h CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [GnuMach] / Gnu-Mach / kern|
Return to rbtree_i.h CVS log | Up to [GnuMach] / Gnu-Mach / kern |
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.