diff options
author | Konrad Kleine <konrad.wilhelm.kleine@gmail.com> | 2011-11-24 18:58:42 +0400 |
---|---|---|
committer | Konrad Kleine <konrad.wilhelm.kleine@gmail.com> | 2011-11-24 18:58:42 +0400 |
commit | 03398cfa8846e37fe88c8b992f2b7efb4d7b2a20 (patch) | |
tree | 1feb28d9cfa30d001d35a4f4af28e033b091f74a /source/blender/blenlib/intern/DLRB_tree.c | |
parent | 5acde0d24c72a4ee2149d1105986f5f119231686 (diff) |
(See http://codereview.appspot.com/5431064/ for review of patch)
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
Diffstat (limited to 'source/blender/blenlib/intern/DLRB_tree.c')
-rw-r--r-- | source/blender/blenlib/intern/DLRB_tree.c | 28 |
1 files changed, 18 insertions, 10 deletions
diff --git a/source/blender/blenlib/intern/DLRB_tree.c b/source/blender/blenlib/intern/DLRB_tree.c index 4507d70e339..b7df06bbf24 100644 --- a/source/blender/blenlib/intern/DLRB_tree.c +++ b/source/blender/blenlib/intern/DLRB_tree.c @@ -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; } |