(See http://codereview.appspot.com/5431064/ for review of patch)
authorKonrad Kleine <konrad.wilhelm.kleine@gmail.com>
Thu, 24 Nov 2011 14:58:42 +0000 (14:58 +0000)
committerKonrad Kleine <konrad.wilhelm.kleine@gmail.com>
Thu, 24 Nov 2011 14:58:42 +0000 (14:58 +0000)
I've written a convenient function that returns the sibling of a node in the
red-black tree implementation originally implemented by Joshua Leung.

I want to use this get_sibling() function in the future to implement the missing
removal function of the red-black tree implementation.

For now the get_sibling() function just simplifies the get_uncle() function.

Just like the rest of the red-black tree implementation this diff is based on
Wikipedia: http://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Removal

source/blender/blenlib/intern/DLRB_tree.c

index 4507d70e3394facdf68fc2740d08a652db1e84c6..b7df06bbf24442a44b51c2c3065e319457a0daa4 100644 (file)
@@ -287,20 +287,28 @@ static DLRBT_Node *get_grandparent (DLRBT_Node *node)
                return NULL;
 }
 
-/* get the 'uncle' - the sibling of the parent - of the given node */
-static DLRBT_Node *get_uncle (DLRBT_Node *node)
+/* get the sibling node (e.g. if node is left child of parent, return right child of parent) */
+static DLRBT_Node *get_sibling(DLRBT_Node *node)
 {
-       DLRBT_Node *gpn= get_grandparent(node);
-       
-       /* return the child of the grandparent which isn't the node's parent */
-       if (gpn) {
-               if (gpn->left == node->parent)
-                       return gpn->right;
+       if (node && node->parent) {
+               if (node == node->parent->left)
+                       return node->parent->right;
                else
-                       return gpn->left;
+                       return node->parent->left;
        }
+
+       /* sibling not found */
+       return NULL;
+}
+
+/* get the 'uncle' - the sibling of the parent - of the given node */
+static DLRBT_Node *get_uncle (DLRBT_Node *node)
+{
+       if (node)
+               /* return the child of the grandparent which isn't the node's parent */
+               return get_sibling(node->parent);
        
-       /* not found */
+       /* uncle not found */
        return NULL;
 }