![[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 <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.