SVN maintenance.
[blender-staging.git] / source / blender / blenlib / intern / DLRB_tree.c
1 /**
2  * $Id$
3  *
4  * ***** BEGIN GPL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software Foundation,
18  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
19  *
20  * The Original Code is Copyright (C) 2009 Blender Foundation, Joshua Leung
21  * All rights reserved.
22  *
23  * Contributor(s): Joshua Leung (original author)
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 #include <stdlib.h>
29 #include <stdio.h>
30 #include <string.h>
31
32 #include "MEM_guardedalloc.h"
33
34 #include "BLI_blenlib.h"
35 #include "BLI_dlrbTree.h"
36
37 #include "DNA_listBase.h"
38
39 /* *********************************************** */
40 /* Tree API */
41
42 /* Create a new tree, and initialise as necessary */
43 DLRBT_Tree *BLI_dlrbTree_new (void)
44 {
45         /* just allocate for now */
46         return MEM_callocN(sizeof(DLRBT_Tree), "DLRBT_Tree");
47 }
48
49 /* Just zero out the pointers used */
50 void BLI_dlrbTree_init (DLRBT_Tree *tree) 
51 {
52         if (tree == NULL)
53                 return;
54                 
55         tree->first= tree->last= tree->root= NULL;
56 }
57
58 /* Helper for traversing tree and freeing sub-nodes */
59 static void recursive_tree_free_nodes (DLRBT_Node *node)
60 {
61         /* sanity check */
62         if (node == NULL)
63                 return;
64         
65         /* free child nodes + subtrees */
66         recursive_tree_free_nodes(node->left);
67         recursive_tree_free_nodes(node->right);
68         
69         /* free self */
70         MEM_freeN(node);
71 }
72
73 /* Free the given tree's data but not the tree itself */
74 void BLI_dlrbTree_free (DLRBT_Tree *tree)
75 {
76         if (tree == NULL)
77                 return;
78         
79         /* if the list-base stuff is set, just use that (and assume its set), 
80          * otherwise, we'll need to traverse the tree...
81          */
82         if (tree->first) {
83                 /* free list */
84                 BLI_freelistN((ListBase *)tree);
85         }
86         else {
87                 /* traverse tree, freeing sub-nodes */
88                 recursive_tree_free_nodes(tree->root);
89         }
90         
91         /* clear pointers */
92         tree->first= tree->last= tree->root= NULL;
93 }
94
95 /* ------- */
96
97 /* Helper function - used for traversing down the tree from the root to add nodes in order */
98 static void linkedlist_sync_add_node (DLRBT_Tree *tree, DLRBT_Node *node)
99 {
100         /* sanity checks */
101         if ((tree == NULL) || (node == NULL))
102                 return;
103         
104         /* add left-node (and its subtree) */
105         linkedlist_sync_add_node(tree, node->left);
106         
107         /* now add self
108          *      - must remove detach from other links first
109          *        (for now, only clear own pointers)
110          */
111         node->prev= node->next= NULL;
112         BLI_addtail((ListBase *)tree, (Link *)node);
113         
114         /* finally, add right node (and its subtree) */
115         linkedlist_sync_add_node(tree, node->right);
116 }
117
118 /* Make sure the tree's Double-Linked list representation is valid */
119 void BLI_dlrbTree_linkedlist_sync (DLRBT_Tree *tree)
120 {
121         /* sanity checks */
122         if (tree == NULL)
123                 return;
124                 
125         /* clear list-base pointers so that the new list can be added properly */
126         tree->first= tree->last= NULL;
127         
128         /* start adding items from the root */
129         linkedlist_sync_add_node(tree, tree->root);
130 }
131
132 /* *********************************************** */
133 /* Tree Relationships Utilities */
134
135 /* get the 'grandparent' - the parent of the parent - of the given node */
136 static DLRBT_Node *get_grandparent (DLRBT_Node *node)
137 {
138         if (node && node->parent)
139                 return node->parent->parent;
140         else
141                 return NULL;
142 }
143
144 /* get the 'uncle' - the sibling of the parent - of the given node */
145 static DLRBT_Node *get_uncle (DLRBT_Node *node)
146 {
147         DLRBT_Node *gpn= get_grandparent(node);
148         
149         /* return the child of the grandparent which isn't the node's parent */
150         if (gpn) {
151                 if (gpn->left == node->parent)
152                         return gpn->right;
153                 else
154                         return gpn->left;
155         }
156         
157         /* not found */
158         return NULL;
159 }
160
161 /* *********************************************** */
162 /* Tree Rotation Utilities */
163
164 /* Left Rotation is only done for Right-Right Case, and Left-Right Case */
165 static void rotate_left (DLRBT_Tree *tree, DLRBT_Node *root)
166 {
167         DLRBT_Node **root_slot, *pivot;
168         
169         /* pivot is simply the root's right child, to become the root's parent */
170         pivot= root->right;
171         if (pivot == NULL)
172                 return;
173         
174         if (root->parent) {
175                 if (root == root->parent->left)
176                         root_slot= &root->parent->left;
177                 else
178                         root_slot= &root->parent->right;
179         }
180         else
181                 root_slot= ((DLRBT_Node**)&tree->root);//&((DLRBT_Node*)tree->root);
182                 
183         /* - pivot's left child becomes root's right child
184          * - root now becomes pivot's left child  
185          */
186         root->right= pivot->left;       
187         if (pivot->left) pivot->left->parent= root;
188         
189         pivot->left= root;
190         pivot->parent= root->parent;
191         root->parent= pivot;
192         
193         /* make the pivot the new root */
194         if (root_slot)
195                 *root_slot= pivot;
196 }
197
198 static void rotate_right (DLRBT_Tree *tree, DLRBT_Node *root)
199 {
200         DLRBT_Node **root_slot, *pivot;
201         
202         /* pivot is simply the root's left child, to become the root's parent */
203         pivot= root->left;
204         if (pivot == NULL)
205                 return;
206         
207         if (root->parent) {
208                 if (root == root->parent->left)
209                         root_slot= &root->parent->left;
210                 else
211                         root_slot= &root->parent->right;
212         }
213         else
214                 root_slot= ((DLRBT_Node**)&tree->root);//&((DLRBT_Node*)tree->root);
215                 
216         /* - pivot's right child becomes root's left child
217          * - root now becomes pivot's right child  
218          */
219         root->left= pivot->right;       
220         if (pivot->right) pivot->right->parent= root;
221         
222         pivot->right= root;
223         pivot->parent= root->parent;
224         root->parent= pivot;
225         
226         /* make the pivot the new root */
227         if (root_slot)
228                 *root_slot= pivot;
229 }
230
231 /* *********************************************** */
232 /* Post-Insertion Balancing  */
233
234 /* forward defines for insertion checks */
235 static void insert_check_1(DLRBT_Tree *tree, DLRBT_Node *node);
236 static void insert_check_2(DLRBT_Tree *tree, DLRBT_Node *node);
237 static void insert_check_3(DLRBT_Tree *tree, DLRBT_Node *node);
238 static void insert_check_4(DLRBT_Tree *tree, DLRBT_Node *node);
239
240 /* ----- */
241
242 /* W. 1) Root must be black (so that the 2nd-generation can have a black parent) */
243 static void insert_check_1 (DLRBT_Tree *tree, DLRBT_Node *node)
244 {
245         if (node) {
246                 /* if this is the root, just ensure that it is black */
247                 if (node->parent == NULL)
248                         node->tree_col= DLRBT_BLACK;
249                 else
250                         insert_check_2(tree, node);
251         }
252 }
253
254 /* W. 2+3) Parent of node must be black, otherwise recolor and flush */
255 static void insert_check_2 (DLRBT_Tree *tree, DLRBT_Node *node)
256 {
257         /* if the parent is not black, we need to change that... */
258         if (node && node->parent && node->parent->tree_col) {
259                 DLRBT_Node *unc= get_uncle(node);
260                 
261                 /* if uncle and parent are both red, need to change them to black and make 
262                  * the parent black in order to satisfy the criteria of each node having the
263                  * same number of black nodes to its leaves
264                  */
265                 if (unc && unc->tree_col) {
266                         DLRBT_Node *gp= get_grandparent(node);
267                         
268                         /* make the n-1 generation nodes black */
269                         node->parent->tree_col= unc->tree_col= DLRBT_BLACK;
270                         
271                         /* - make the grandparent red, so that we maintain alternating red/black property 
272                          *  (it must exist, so no need to check for NULL here),
273                          * - as the grandparent may now cause inconsistencies with the rest of the tree, 
274                          *   we must flush up the tree and perform checks/rebalancing/repainting, using the 
275                          *      grandparent as the node of interest
276                          */
277                         gp->tree_col= DLRBT_RED;
278                         insert_check_1(tree, gp);
279                 }
280                 else {
281                         /* we've got an unbalanced branch going down the grandparent to the parent,
282                          * so need to perform some rotations to re-balance the tree
283                          */
284                         insert_check_3(tree, node);
285                 }
286         }
287 }
288
289 /* W. 4) Perform rotation on sub-tree containing the 'new' node */
290 static void insert_check_3 (DLRBT_Tree *tree, DLRBT_Node *node)
291 {
292         DLRBT_Node *gp= get_grandparent(node);
293         
294         /* check that grandparent and node->parent exist (jut in case... really shouldn't happen on a good tree) */
295         if (node && node->parent && gp) {
296                 /* a left rotation will switch the roles of node and its parent, assuming that
297                  * the parent is the left child of the grandparent... otherwise, rotation direction
298                  * should be swapped
299                  */
300                 if ((node == node->parent->right) && (node->parent == gp->left)) {
301                         rotate_left(tree, node);
302                         node= node->left;
303                 }
304                 else if ((node == node->parent->left) && (node->parent == gp->right)) {
305                         rotate_right(tree, node); 
306                         node= node->right;
307                 }
308                 // TODO: what about other cases?
309                 
310                 /* fix old parent's color-tagging */
311                 insert_check_4(tree, node);
312         }
313 }
314
315 /* W. 5) Perform rotation in the opposite direction on the parent of the given node */
316 static void insert_check_4 (DLRBT_Tree *tree, DLRBT_Node *node)
317 {
318         DLRBT_Node *gp= get_grandparent(node);
319         
320         if (node == NULL)
321                 return;
322         
323         /* modify the coloring of the grandparent and parent so that they still satisfy the constraints */
324         node->parent->tree_col= DLRBT_BLACK;
325         gp->tree_col= DLRBT_RED;
326         
327         /* if there are several nodes that all form a left chain, do a right rotation to correct this
328          * (or a rotation in the opposite direction if they all form a right chain)
329          */
330         if ((node == node->parent->left) && (node->parent == gp->left))
331                 rotate_right(tree, gp);
332         else /* ((node == node->parent->right) && (node->parent == gp->right)) */
333                 rotate_left(tree, gp);
334 }
335
336 /* ----- */
337
338 /* Balance the tree after the given element has been added to it 
339  * (using custom code, in the Binary Tree way).
340  */
341 void BLI_dlrbTree_insert(DLRBT_Tree *tree, DLRBT_Node *node)
342 {
343         /* sanity checks */
344         if ((tree == NULL) || (node == NULL))
345                 return;
346                 
347         /* firstly, the node we just added should be red by default */
348         node->tree_col= DLRBT_RED;
349                 
350         /* start from case 1, an trek through the tail-recursive insertion checks */
351         insert_check_1(tree, node);
352 }
353
354 /* *********************************************** */
355 /* Remove */
356
357 // TODO: this hasn't been coded yet, since this functionality was not needed by the author
358
359 /* *********************************************** */