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