diff options
author | Campbell Barton <ideasman42@gmail.com> | 2012-05-12 19:02:10 +0400 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2012-05-12 19:02:10 +0400 |
commit | 2f2b15bbb2a30ee312d65c627d54a12445f4b987 (patch) | |
tree | 7d2d442d5351a04887bbe4aac0f039c3f1d416cd /source/blender/blenlib/intern/DLRB_tree.c | |
parent | 23c0d49a7c6aacde784843b14d5b3eece7fe61df (diff) |
style cleanup: whitespace, bli & makesdna
Diffstat (limited to 'source/blender/blenlib/intern/DLRB_tree.c')
-rw-r--r-- | source/blender/blenlib/intern/DLRB_tree.c | 188 |
1 files changed, 94 insertions, 94 deletions
diff --git a/source/blender/blenlib/intern/DLRB_tree.c b/source/blender/blenlib/intern/DLRB_tree.c index 6398bd863db..bed5750ad44 100644 --- a/source/blender/blenlib/intern/DLRB_tree.c +++ b/source/blender/blenlib/intern/DLRB_tree.c @@ -37,7 +37,7 @@ /* Tree API */ /* Create a new tree, and initialize as necessary */ -DLRBT_Tree *BLI_dlrbTree_new (void) +DLRBT_Tree *BLI_dlrbTree_new(void) { /* just allocate for now */ return MEM_callocN(sizeof(DLRBT_Tree), "DLRBT_Tree"); @@ -49,11 +49,11 @@ void BLI_dlrbTree_init(DLRBT_Tree *tree) if (tree == NULL) return; - tree->first= tree->last= tree->root= NULL; + tree->first = tree->last = tree->root = NULL; } /* Helper for traversing tree and freeing sub-nodes */ -static void recursive_tree_free_nodes (DLRBT_Node *node) +static void recursive_tree_free_nodes(DLRBT_Node *node) { /* sanity check */ if (node == NULL) @@ -86,13 +86,13 @@ void BLI_dlrbTree_free(DLRBT_Tree *tree) } /* clear pointers */ - tree->first= tree->last= tree->root= NULL; + tree->first = tree->last = tree->root = NULL; } /* ------- */ /* Helper function - used for traversing down the tree from the root to add nodes in order */ -static void linkedlist_sync_add_node (DLRBT_Tree *tree, DLRBT_Node *node) +static void linkedlist_sync_add_node(DLRBT_Tree *tree, DLRBT_Node *node) { /* sanity checks */ if ((tree == NULL) || (node == NULL)) @@ -105,7 +105,7 @@ static void linkedlist_sync_add_node (DLRBT_Tree *tree, DLRBT_Node *node) * - must remove detach from other links first * (for now, only clear own pointers) */ - node->prev= node->next= NULL; + node->prev = node->next = NULL; BLI_addtail((ListBase *)tree, (Link *)node); /* finally, add right node (and its subtree) */ @@ -120,7 +120,7 @@ void BLI_dlrbTree_linkedlist_sync(DLRBT_Tree *tree) return; /* clear list-base pointers so that the new list can be added properly */ - tree->first= tree->last= NULL; + tree->first = tree->last = NULL; /* start adding items from the root */ linkedlist_sync_add_node(tree, tree->root); @@ -130,10 +130,10 @@ void BLI_dlrbTree_linkedlist_sync(DLRBT_Tree *tree) /* Tree Search Utilities */ /* Find the node which matches or is the closest to the requested node */ -DLRBT_Node *BLI_dlrbTree_search (DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data) +DLRBT_Node *BLI_dlrbTree_search(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data) { DLRBT_Node *node = (tree) ? tree->root : NULL; - short found= 0; + short found = 0; /* check that there is a comparator to use */ // TODO: if no comparator is supplied, try using the one supplied with the tree... @@ -146,22 +146,22 @@ DLRBT_Node *BLI_dlrbTree_search (DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, v * NOTE: it is assumed that the values will be unit values only */ switch (cmp_cb(node, search_data)) { - case -1: /* data less than node */ + case -1: /* data less than node */ if (node->left) - node= node->left; + node = node->left; else - found= 1; + found = 1; break; - case 1: /* data greater than node */ + case 1: /* data greater than node */ if (node->right) - node= node->right; + node = node->right; else - found= 1; + found = 1; break; - default: /* data equals node */ - found= 1; + default: /* data equals node */ + found = 1; break; } } @@ -171,10 +171,10 @@ DLRBT_Node *BLI_dlrbTree_search (DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, v } /* Find the node which exactly matches the required data */ -DLRBT_Node *BLI_dlrbTree_search_exact (DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data) +DLRBT_Node *BLI_dlrbTree_search_exact(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data) { DLRBT_Node *node = (tree) ? tree->root : NULL; - short found= 0; + short found = 0; /* check that there is a comparator to use */ // TODO: if no comparator is supplied, try using the one supplied with the tree... @@ -182,27 +182,27 @@ DLRBT_Node *BLI_dlrbTree_search_exact (DLRBT_Tree *tree, DLRBT_Comparator_FP cmp return NULL; /* iteratively perform this search */ - while (node && found==0) { + while (node && found == 0) { /* check if traverse further or not * NOTE: it is assumed that the values will be unit values only */ switch (cmp_cb(node, search_data)) { - case -1: /* data less than node */ + case -1: /* data less than node */ if (node->left) - node= node->left; + node = node->left; else - found= -1; + found = -1; break; - case 1: /* data greater than node */ + case 1: /* data greater than node */ if (node->right) - node= node->right; + node = node->right; else - found= -1; + found = -1; break; - default: /* data equals node */ - found= 1; + default: /* data equals node */ + found = 1; break; } } @@ -212,7 +212,7 @@ DLRBT_Node *BLI_dlrbTree_search_exact (DLRBT_Tree *tree, DLRBT_Comparator_FP cmp } /* Find the node which occurs immediately before the best matching node */ -DLRBT_Node *BLI_dlrbTree_search_prev (DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data) +DLRBT_Node *BLI_dlrbTree_search_prev(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data) { DLRBT_Node *node; @@ -222,7 +222,7 @@ DLRBT_Node *BLI_dlrbTree_search_prev (DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_ return NULL; /* get the node which best matches this description */ - node= BLI_dlrbTree_search(tree, cmp_cb, search_data); + node = BLI_dlrbTree_search(tree, cmp_cb, search_data); if (node) { /* if the item we're searching for is greater than the node found, we've found the match */ @@ -239,7 +239,7 @@ DLRBT_Node *BLI_dlrbTree_search_prev (DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_ } /* Find the node which occurs immediately after the best matching node */ -DLRBT_Node *BLI_dlrbTree_search_next (DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data) +DLRBT_Node *BLI_dlrbTree_search_next(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data) { DLRBT_Node *node; @@ -249,7 +249,7 @@ DLRBT_Node *BLI_dlrbTree_search_next (DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_ return NULL; /* get the node which best matches this description */ - node= BLI_dlrbTree_search(tree, cmp_cb, search_data); + node = BLI_dlrbTree_search(tree, cmp_cb, search_data); if (node) { /* if the item we're searching for is less than the node found, we've found the match */ @@ -277,7 +277,7 @@ short BLI_dlrbTree_contains(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void * /* Tree Relationships Utilities */ /* get the 'grandparent' - the parent of the parent - of the given node */ -static DLRBT_Node *get_grandparent (DLRBT_Node *node) +static DLRBT_Node *get_grandparent(DLRBT_Node *node) { if (node && node->parent) return node->parent->parent; @@ -300,7 +300,7 @@ static DLRBT_Node *get_sibling(DLRBT_Node *node) } /* get the 'uncle' - the sibling of the parent - of the given node */ -static DLRBT_Node *get_uncle (DLRBT_Node *node) +static DLRBT_Node *get_uncle(DLRBT_Node *node) { if (node) /* return the child of the grandparent which isn't the node's parent */ @@ -314,71 +314,71 @@ static DLRBT_Node *get_uncle (DLRBT_Node *node) /* Tree Rotation Utilities */ /* make right child of 'root' the new root */ -static void rotate_left (DLRBT_Tree *tree, DLRBT_Node *root) +static void rotate_left(DLRBT_Tree *tree, DLRBT_Node *root) { DLRBT_Node **root_slot, *pivot; /* pivot is simply the root's right child, to become the root's parent */ - pivot= root->right; + pivot = root->right; if (pivot == NULL) return; if (root->parent) { if (root == root->parent->left) - root_slot= &root->parent->left; + root_slot = &root->parent->left; else - root_slot= &root->parent->right; + root_slot = &root->parent->right; } else - root_slot= ((DLRBT_Node**)&tree->root);//&((DLRBT_Node*)tree->root); + root_slot = ((DLRBT_Node **)&tree->root); //&((DLRBT_Node*)tree->root); /* - pivot's left child becomes root's right child * - root now becomes pivot's left child */ - root->right= pivot->left; - if (pivot->left) pivot->left->parent= root; + root->right = pivot->left; + if (pivot->left) pivot->left->parent = root; - pivot->left= root; - pivot->parent= root->parent; - root->parent= pivot; + pivot->left = root; + pivot->parent = root->parent; + root->parent = pivot; /* make the pivot the new root */ if (root_slot) - *root_slot= pivot; + *root_slot = pivot; } /* make the left child of the 'root' the new root */ -static void rotate_right (DLRBT_Tree *tree, DLRBT_Node *root) +static void rotate_right(DLRBT_Tree *tree, DLRBT_Node *root) { DLRBT_Node **root_slot, *pivot; /* pivot is simply the root's left child, to become the root's parent */ - pivot= root->left; + pivot = root->left; if (pivot == NULL) return; if (root->parent) { if (root == root->parent->left) - root_slot= &root->parent->left; + root_slot = &root->parent->left; else - root_slot= &root->parent->right; + root_slot = &root->parent->right; } else - root_slot= ((DLRBT_Node**)&tree->root);//&((DLRBT_Node*)tree->root); + root_slot = ((DLRBT_Node **)&tree->root); //&((DLRBT_Node*)tree->root); /* - pivot's right child becomes root's left child * - root now becomes pivot's right child */ - root->left= pivot->right; - if (pivot->right) pivot->right->parent= root; + root->left = pivot->right; + if (pivot->right) pivot->right->parent = root; - pivot->right= root; - pivot->parent= root->parent; - root->parent= pivot; + pivot->right = root; + pivot->parent = root->parent; + root->parent = pivot; /* make the pivot the new root */ if (root_slot) - *root_slot= pivot; + *root_slot = pivot; } /* *********************************************** */ @@ -392,41 +392,41 @@ static void insert_check_3(DLRBT_Tree *tree, DLRBT_Node *node); /* ----- */ /* W. 1) Root must be black (so that the 2nd-generation can have a black parent) */ -static void insert_check_1 (DLRBT_Tree *tree, DLRBT_Node *node) +static void insert_check_1(DLRBT_Tree *tree, DLRBT_Node *node) { if (node) { /* if this is the root, just ensure that it is black */ if (node->parent == NULL) - node->tree_col= DLRBT_BLACK; + node->tree_col = DLRBT_BLACK; else insert_check_2(tree, node); } } /* W. 2+3) Parent of node must be black, otherwise recolor and flush */ -static void insert_check_2 (DLRBT_Tree *tree, DLRBT_Node *node) +static void insert_check_2(DLRBT_Tree *tree, DLRBT_Node *node) { /* if the parent is not black, we need to change that... */ if (node && node->parent && node->parent->tree_col) { - DLRBT_Node *unc= get_uncle(node); + DLRBT_Node *unc = get_uncle(node); /* if uncle and parent are both red, need to change them to black and make * the parent black in order to satisfy the criteria of each node having the * same number of black nodes to its leaves */ if (unc && unc->tree_col) { - DLRBT_Node *gp= get_grandparent(node); + DLRBT_Node *gp = get_grandparent(node); /* make the n-1 generation nodes black */ - node->parent->tree_col= unc->tree_col= DLRBT_BLACK; + node->parent->tree_col = unc->tree_col = DLRBT_BLACK; /* - make the grandparent red, so that we maintain alternating red/black property * (it must exist, so no need to check for NULL here), * - as the grandparent may now cause inconsistencies with the rest of the tree, * we must flush up the tree and perform checks/rebalancing/repainting, using the - * grandparent as the node of interest + * grandparent as the node of interest */ - gp->tree_col= DLRBT_RED; + gp->tree_col = DLRBT_RED; insert_check_1(tree, gp); } else { @@ -439,9 +439,9 @@ static void insert_check_2 (DLRBT_Tree *tree, DLRBT_Node *node) } /* W. 4+5) Perform rotation on sub-tree containing the 'new' node, then do any */ -static void insert_check_3 (DLRBT_Tree *tree, DLRBT_Node *node) +static void insert_check_3(DLRBT_Tree *tree, DLRBT_Node *node) { - DLRBT_Node *gp= get_grandparent(node); + DLRBT_Node *gp = get_grandparent(node); /* check that grandparent and node->parent exist (jut in case... really shouldn't happen on a good tree) */ if (node && node->parent && gp) { @@ -451,11 +451,11 @@ static void insert_check_3 (DLRBT_Tree *tree, DLRBT_Node *node) */ if ((node == node->parent->right) && (node->parent == gp->left)) { rotate_left(tree, node); - node= node->left; + node = node->left; } else if ((node == node->parent->left) && (node->parent == gp->right)) { rotate_right(tree, node); - node= node->right; + node = node->right; } /* fix old parent's color-tagging, and perform rotation on the old parent in the @@ -464,11 +464,11 @@ static void insert_check_3 (DLRBT_Tree *tree, DLRBT_Node *node) */ if (node) { /* get 'new' grandparent (i.e. grandparent for old-parent (node)) */ - gp= get_grandparent(node); + gp = get_grandparent(node); /* modify the coloring of the grandparent and parent so that they still satisfy the constraints */ - node->parent->tree_col= DLRBT_BLACK; - gp->tree_col= DLRBT_RED; + node->parent->tree_col = DLRBT_BLACK; + gp->tree_col = DLRBT_RED; /* if there are several nodes that all form a left chain, do a right rotation to correct this * (or a rotation in the opposite direction if they all form a right chain) @@ -493,7 +493,7 @@ void BLI_dlrbTree_insert(DLRBT_Tree *tree, DLRBT_Node *node) return; /* firstly, the node we just added should be red by default */ - node->tree_col= DLRBT_RED; + node->tree_col = DLRBT_RED; /* start from case 1, an trek through the tail-recursive insertion checks */ insert_check_1(tree, node); @@ -504,9 +504,9 @@ void BLI_dlrbTree_insert(DLRBT_Tree *tree, DLRBT_Node *node) /* Add the given data to the tree, and return the node added */ // NOTE: for duplicates, the update_cb is called (if available), and the existing node is returned DLRBT_Node *BLI_dlrbTree_add(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, - DLRBT_NAlloc_FP new_cb, DLRBT_NUpdate_FP update_cb, void *data) + DLRBT_NAlloc_FP new_cb, DLRBT_NUpdate_FP update_cb, void *data) { - DLRBT_Node *parNode, *node=NULL; + DLRBT_Node *parNode, *node = NULL; short new_node = 0; /* sanity checks */ @@ -522,7 +522,7 @@ DLRBT_Node *BLI_dlrbTree_add(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, // TODO: if no updater is supplied, try using the one supplied with the tree... /* try to find the nearest node to this one */ - parNode= BLI_dlrbTree_search(tree, cmp_cb, data); + parNode = BLI_dlrbTree_search(tree, cmp_cb, data); /* add new node to the BST in the 'standard way' as appropriate * NOTE: we do not support duplicates in our tree... @@ -532,49 +532,49 @@ DLRBT_Node *BLI_dlrbTree_add(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, * NOTE: it is assumed that the values will be unit values only */ switch (cmp_cb(parNode, data)) { - case -1: /* add new node as left child */ + case -1: /* add new node as left child */ { - node= new_cb(data); - new_node= 1; + node = new_cb(data); + new_node = 1; - parNode->left= node; - node->parent= parNode; + parNode->left = node; + node->parent = parNode; } - break; + break; - case 1: /* add new node as right child */ + case 1: /* add new node as right child */ { - node= new_cb(data); - new_node= 1; + node = new_cb(data); + new_node = 1; - parNode->right= node; - node->parent= parNode; + parNode->right = node; + node->parent = parNode; } - break; + break; - default: /* update the duplicate node as appropriate */ + default: /* update the duplicate node as appropriate */ { if (update_cb) update_cb(parNode, data); } - break; + break; } } else { /* no nodes in the tree yet... add a new node as the root */ - node= new_cb(data); - new_node= 1; + node = new_cb(data); + new_node = 1; - tree->root= node; + tree->root = node; } /* if a new node was added, it should be tagged as red, and then balanced as appropriate */ if (new_node) { /* tag this new node as being 'red' */ - node->tree_col= DLRBT_RED; + node->tree_col = DLRBT_RED; /* perform BST balancing steps: - * start from case 1, an trek through the tail-recursive insertion checks + * start from case 1, an trek through the tail-recursive insertion checks */ insert_check_1(tree, node); } |