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