aboutsummaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
authorPallipadi, Venkatesh <venkatesh.pallipadi@intel.com>2010-02-10 18:23:44 -0500
committerH. Peter Anvin <hpa@zytor.com>2010-02-18 18:40:56 -0500
commit17d9ddc72fb8bba0d4f67868c9c612e472a594a9 (patch)
tree51c5e50f91eb060e346c129aa7403624934966d8 /lib
parent724e6d3fe8003c3f60bf404bf22e4e331327c596 (diff)
rbtree: Add support for augmented rbtrees
Add support for augmented rbtrees in core rbtree code. This will be used in subsequent patches, in x86 PAT code, which needs interval trees to efficiently keep track of PAT ranges. Signed-off-by: Venkatesh Pallipadi <venkatesh.pallipadi@intel.com> LKML-Reference: <20100210232343.GA11465@linux-os.sc.intel.com> Signed-off-by: Suresh Siddha <suresh.b.siddha@intel.com> Signed-off-by: H. Peter Anvin <hpa@zytor.com>
Diffstat (limited to 'lib')
-rw-r--r--lib/rbtree.c48
1 files changed, 44 insertions, 4 deletions
diff --git a/lib/rbtree.c b/lib/rbtree.c
index e2aa3be29858..15e10b1afdd2 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -44,6 +44,11 @@ static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
44 else 44 else
45 root->rb_node = right; 45 root->rb_node = right;
46 rb_set_parent(node, right); 46 rb_set_parent(node, right);
47
48 if (root->augment_cb) {
49 root->augment_cb(node);
50 root->augment_cb(right);
51 }
47} 52}
48 53
49static void __rb_rotate_right(struct rb_node *node, struct rb_root *root) 54static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
@@ -67,12 +72,20 @@ static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
67 else 72 else
68 root->rb_node = left; 73 root->rb_node = left;
69 rb_set_parent(node, left); 74 rb_set_parent(node, left);
75
76 if (root->augment_cb) {
77 root->augment_cb(node);
78 root->augment_cb(left);
79 }
70} 80}
71 81
72void rb_insert_color(struct rb_node *node, struct rb_root *root) 82void rb_insert_color(struct rb_node *node, struct rb_root *root)
73{ 83{
74 struct rb_node *parent, *gparent; 84 struct rb_node *parent, *gparent;
75 85
86 if (root->augment_cb)
87 root->augment_cb(node);
88
76 while ((parent = rb_parent(node)) && rb_is_red(parent)) 89 while ((parent = rb_parent(node)) && rb_is_red(parent))
77 { 90 {
78 gparent = rb_parent(parent); 91 gparent = rb_parent(parent);
@@ -227,12 +240,15 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
227 else 240 else
228 { 241 {
229 struct rb_node *old = node, *left; 242 struct rb_node *old = node, *left;
243 int old_parent_cb = 0;
244 int successor_parent_cb = 0;
230 245
231 node = node->rb_right; 246 node = node->rb_right;
232 while ((left = node->rb_left) != NULL) 247 while ((left = node->rb_left) != NULL)
233 node = left; 248 node = left;
234 249
235 if (rb_parent(old)) { 250 if (rb_parent(old)) {
251 old_parent_cb = 1;
236 if (rb_parent(old)->rb_left == old) 252 if (rb_parent(old)->rb_left == old)
237 rb_parent(old)->rb_left = node; 253 rb_parent(old)->rb_left = node;
238 else 254 else
@@ -247,8 +263,10 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
247 if (parent == old) { 263 if (parent == old) {
248 parent = node; 264 parent = node;
249 } else { 265 } else {
266 successor_parent_cb = 1;
250 if (child) 267 if (child)
251 rb_set_parent(child, parent); 268 rb_set_parent(child, parent);
269
252 parent->rb_left = child; 270 parent->rb_left = child;
253 271
254 node->rb_right = old->rb_right; 272 node->rb_right = old->rb_right;
@@ -259,6 +277,24 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
259 node->rb_left = old->rb_left; 277 node->rb_left = old->rb_left;
260 rb_set_parent(old->rb_left, node); 278 rb_set_parent(old->rb_left, node);
261 279
280 if (root->augment_cb) {
281 /*
282 * Here, three different nodes can have new children.
283 * The parent of the successor node that was selected
284 * to replace the node to be erased.
285 * The node that is getting erased and is now replaced
286 * by its successor.
287 * The parent of the node getting erased-replaced.
288 */
289 if (successor_parent_cb)
290 root->augment_cb(parent);
291
292 root->augment_cb(node);
293
294 if (old_parent_cb)
295 root->augment_cb(rb_parent(old));
296 }
297
262 goto color; 298 goto color;
263 } 299 }
264 300
@@ -267,15 +303,19 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
267 303
268 if (child) 304 if (child)
269 rb_set_parent(child, parent); 305 rb_set_parent(child, parent);
270 if (parent) 306
271 { 307 if (parent) {
272 if (parent->rb_left == node) 308 if (parent->rb_left == node)
273 parent->rb_left = child; 309 parent->rb_left = child;
274 else 310 else
275 parent->rb_right = child; 311 parent->rb_right = child;
276 } 312
277 else 313 if (root->augment_cb)
314 root->augment_cb(parent);
315
316 } else {
278 root->rb_node = child; 317 root->rb_node = child;
318 }
279 319
280 color: 320 color:
281 if (color == RB_BLACK) 321 if (color == RB_BLACK)