X-Git-Url: http://git.tuebingen.mpg.de/?p=osl.git;a=blobdiff_plain;f=rbtree.c;h=3cad749620a769b637d68c2dd277d244190b57ec;hp=5d24aeb5063a788215eca93a73698f50a68b0bc2;hb=HEAD;hpb=5952112a37ecdaedf3b76e08f97d307f1056c512

diff --git a/rbtree.c b/rbtree.c
index 5d24aeb..3cad749 100644
--- a/rbtree.c
+++ b/rbtree.c
@@ -2,7 +2,7 @@
   Red Black Trees
   (C) 1999  Andrea Arcangeli <andrea@suse.de>
   (C) 2002  David Woodhouse <dwmw2@infradead.org>
-  (C) 2007  Andre Noll <maan@systemlinux.org>
+  (C) 2007  Andre Noll <maan@tuebingen.mpg.de>
   
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
@@ -306,7 +306,7 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
 /*
  * This function returns the first node (in sort order) of the tree.
  */
-struct rb_node *rb_first(struct rb_root *root)
+struct rb_node *rb_first(const struct rb_root *root)
 {
 	struct rb_node	*n;
 
@@ -318,7 +318,7 @@ struct rb_node *rb_first(struct rb_root *root)
 	return n;
 }
 
-struct rb_node *rb_last(struct rb_root *root)
+struct rb_node *rb_last(const struct rb_root *root)
 {
 	struct rb_node	*n;
 
@@ -330,7 +330,7 @@ struct rb_node *rb_last(struct rb_root *root)
 	return n;
 }
 
-struct rb_node *rb_next(struct rb_node *node)
+struct rb_node *rb_next(const struct rb_node *node)
 {
 	struct rb_node *parent;
 
@@ -343,7 +343,7 @@ struct rb_node *rb_next(struct rb_node *node)
 		node = node->rb_right; 
 		while (node->rb_left)
 			node=node->rb_left;
-		return node;
+		return (struct rb_node *)node;
 	}
 
 	/* No right-hand children.  Everything down and left is
@@ -358,7 +358,7 @@ struct rb_node *rb_next(struct rb_node *node)
 	return parent;
 }
 
-struct rb_node *rb_prev(struct rb_node *node)
+struct rb_node *rb_prev(const struct rb_node *node)
 {
 	struct rb_node *parent;
 
@@ -371,7 +371,7 @@ struct rb_node *rb_prev(struct rb_node *node)
 		node = node->rb_left; 
 		while (node->rb_right)
 			node=node->rb_right;
-		return node;
+		return (struct rb_node *)node;
 	}
 
 	/* No left-hand children. Go up till we find an ancestor which
@@ -382,29 +382,6 @@ struct rb_node *rb_prev(struct rb_node *node)
 	return parent;
 }
 
-void rb_replace_node(struct rb_node *victim, struct rb_node *new,
-		     struct rb_root *root)
-{
-	struct rb_node *parent = rb_parent(victim);
-
-	/* Set the surrounding nodes to point to the replacement */
-	if (parent) {
-		if (victim == parent->rb_left)
-			parent->rb_left = new;
-		else
-			parent->rb_right = new;
-	} else {
-		root->rb_node = new;
-	}
-	if (victim->rb_left)
-		rb_set_parent(victim->rb_left, new);
-	if (victim->rb_right)
-		rb_set_parent(victim->rb_right, new);
-
-	/* Copy the pointers/colour from the victim to the replacement */
-	*new = *victim;
-}
-
 /**
  * Get the n-th node (in sort order) of the tree.
  *
@@ -413,7 +390,7 @@ void rb_replace_node(struct rb_node *victim, struct rb_node *new,
  *
  * \return Pointer to the \a n th greatest node on success, \p NULL on errors.
  */
-struct rb_node *rb_nth(struct rb_node *node, unsigned n)
+struct rb_node *rb_nth(const struct rb_node *node, unsigned n)
 {
 	unsigned size = 1;
 
@@ -422,7 +399,7 @@ struct rb_node *rb_nth(struct rb_node *node, unsigned n)
 	if (node->rb_left)
 		size += node->rb_left->size;
 	if (n == size)
-		return node;
+		return (struct rb_node *)node;
 	if (n < size)
 		return rb_nth(node->rb_left, n);
 	return rb_nth(node->rb_right, n - size);
@@ -436,7 +413,7 @@ struct rb_node *rb_nth(struct rb_node *node, unsigned n)
  *
  * \return Positive on success, -1 on errors.
  */
-int rb_rank(struct rb_node *node, unsigned *rank)
+int rb_rank(const struct rb_node *node, unsigned *rank)
 {
 	*rank = 1;
 	struct rb_node *parent;