Sierra Toolkit  Version of the Day
red_black_tree_eastl.cpp
1 /*
2 Copyright (C) 2005,2009-2010 Electronic Arts, Inc. All rights reserved.
3 
4 Redistribution and use in source and binary forms, with or without
5 modification, are permitted provided that the following conditions
6 are met:
7 
8 1. Redistributions of source code must retain the above copyright
9  notice, this list of conditions and the following disclaimer.
10 2. Redistributions in binary form must reproduce the above copyright
11  notice, this list of conditions and the following disclaimer in the
12  documentation and/or other materials provided with the distribution.
13 3. Neither the name of Electronic Arts, Inc. ("EA") nor the names of
14  its contributors may be used to endorse or promote products derived
15  from this software without specific prior written permission.
16 
17 THIS SOFTWARE IS PROVIDED BY ELECTRONIC ARTS AND ITS CONTRIBUTORS "AS IS" AND ANY
18 EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
19 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
20 DISCLAIMED. IN NO EVENT SHALL ELECTRONIC ARTS OR ITS CONTRIBUTORS BE LIABLE FOR ANY
21 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
23 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
24 ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28 
30 // EASTL/red_black_tree.cpp
31 //
32 // Written and maintained by Paul Pedriana - 2005.
34 
35 
37 // The tree insert and erase functions below are based on the original
38 // HP STL tree functions. Use of these functions was been approved by
39 // EA legal on November 4, 2005 and the approval documentation is available
40 // from the EASTL maintainer or from the EA legal deparatment on request.
41 //
42 // Copyright (c) 1994
43 // Hewlett-Packard Company
44 //
45 // Permission to use, copy, modify, distribute and sell this software
46 // and its documentation for any purpose is hereby granted without fee,
47 // provided that the above copyright notice appear in all copies and
48 // that both that copyright notice and this permission notice appear
49 // in supporting documentation. Hewlett-Packard Company makes no
50 // representations about the suitability of this software for any
51 // purpose. It is provided "as is" without express or implied warranty.
53 
54 
55 
56 
57 #include <stk_util/util/config_eastl.h>
58 #include <stk_util/util/red_black_tree_eastl.h>
59 #include <stddef.h>
60 
61 
62 
63 namespace eastl
64 {
65  // Forward declarations
66  rbtree_node_base* RBTreeRotateLeft(rbtree_node_base* pNode, rbtree_node_base* pNodeRoot);
67  rbtree_node_base* RBTreeRotateRight(rbtree_node_base* pNode, rbtree_node_base* pNodeRoot);
68 
69 
70 
75  {
76  if(pNode->mpNodeRight)
77  {
78  pNode = pNode->mpNodeRight;
79 
80  while(pNode->mpNodeLeft)
81  pNode = pNode->mpNodeLeft;
82  }
83  else
84  {
85  rbtree_node_base* pNodeTemp = pNode->mpNodeParent;
86 
87  while(pNode == pNodeTemp->mpNodeRight)
88  {
89  pNode = pNodeTemp;
90  pNodeTemp = pNodeTemp->mpNodeParent;
91  }
92 
93  if(pNode->mpNodeRight != pNodeTemp)
94  pNode = pNodeTemp;
95  }
96 
97  return const_cast<rbtree_node_base*>(pNode);
98  }
99 
100 
101 
106  {
107  if((pNode->mpNodeParent->mpNodeParent == pNode) && (pNode->mColor == kRBTreeColorRed))
108  return pNode->mpNodeRight;
109  else if(pNode->mpNodeLeft)
110  {
111  rbtree_node_base* pNodeTemp = pNode->mpNodeLeft;
112 
113  while(pNodeTemp->mpNodeRight)
114  pNodeTemp = pNodeTemp->mpNodeRight;
115 
116  return pNodeTemp;
117  }
118 
119  rbtree_node_base* pNodeTemp = pNode->mpNodeParent;
120 
121  while(pNode == pNodeTemp->mpNodeLeft)
122  {
123  pNode = pNodeTemp;
124  pNodeTemp = pNodeTemp->mpNodeParent;
125  }
126 
127  return const_cast<rbtree_node_base*>(pNodeTemp);
128  }
129 
130 
131 
138  EASTL_API size_t RBTreeGetBlackCount(const rbtree_node_base* pNodeTop, const rbtree_node_base* pNodeBottom)
139  {
140  size_t nCount = 0;
141 
142  for(; pNodeBottom; pNodeBottom = pNodeBottom->mpNodeParent)
143  {
144  if(pNodeBottom->mColor == kRBTreeColorBlack)
145  ++nCount;
146 
147  if(pNodeBottom == pNodeTop)
148  break;
149  }
150 
151  return nCount;
152  }
153 
154 
160  {
161  rbtree_node_base* const pNodeTemp = pNode->mpNodeRight;
162 
163  pNode->mpNodeRight = pNodeTemp->mpNodeLeft;
164 
165  if(pNodeTemp->mpNodeLeft)
166  pNodeTemp->mpNodeLeft->mpNodeParent = pNode;
167  pNodeTemp->mpNodeParent = pNode->mpNodeParent;
168 
169  if(pNode == pNodeRoot)
170  pNodeRoot = pNodeTemp;
171  else if(pNode == pNode->mpNodeParent->mpNodeLeft)
172  pNode->mpNodeParent->mpNodeLeft = pNodeTemp;
173  else
174  pNode->mpNodeParent->mpNodeRight = pNodeTemp;
175 
176  pNodeTemp->mpNodeLeft = pNode;
177  pNode->mpNodeParent = pNodeTemp;
178 
179  return pNodeRoot;
180  }
181 
182 
183 
189  {
190  rbtree_node_base* const pNodeTemp = pNode->mpNodeLeft;
191 
192  pNode->mpNodeLeft = pNodeTemp->mpNodeRight;
193 
194  if(pNodeTemp->mpNodeRight)
195  pNodeTemp->mpNodeRight->mpNodeParent = pNode;
196  pNodeTemp->mpNodeParent = pNode->mpNodeParent;
197 
198  if(pNode == pNodeRoot)
199  pNodeRoot = pNodeTemp;
200  else if(pNode == pNode->mpNodeParent->mpNodeRight)
201  pNode->mpNodeParent->mpNodeRight = pNodeTemp;
202  else
203  pNode->mpNodeParent->mpNodeLeft = pNodeTemp;
204 
205  pNodeTemp->mpNodeRight = pNode;
206  pNode->mpNodeParent = pNodeTemp;
207 
208  return pNodeRoot;
209  }
210 
211 
212 
213 
218  EASTL_API void RBTreeInsert(rbtree_node_base* pNode,
219  rbtree_node_base* pNodeParent,
220  rbtree_node_base* pNodeAnchor,
221  RBTreeSide insertionSide)
222  {
223  rbtree_node_base*& pNodeRootRef = pNodeAnchor->mpNodeParent;
224 
225  // Initialize fields in new node to insert.
226  pNode->mpNodeParent = pNodeParent;
227  pNode->mpNodeRight = NULL;
228  pNode->mpNodeLeft = NULL;
229  pNode->mColor = kRBTreeColorRed;
230 
231  // Insert the node.
232  if(insertionSide == kRBTreeSideLeft)
233  {
234  pNodeParent->mpNodeLeft = pNode; // Also makes (leftmost = pNode) when (pNodeParent == pNodeAnchor)
235 
236  if(pNodeParent == pNodeAnchor)
237  {
238  pNodeAnchor->mpNodeParent = pNode;
239  pNodeAnchor->mpNodeRight = pNode;
240  }
241  else if(pNodeParent == pNodeAnchor->mpNodeLeft)
242  pNodeAnchor->mpNodeLeft = pNode; // Maintain leftmost pointing to min node
243  }
244  else
245  {
246  pNodeParent->mpNodeRight = pNode;
247 
248  if(pNodeParent == pNodeAnchor->mpNodeRight)
249  pNodeAnchor->mpNodeRight = pNode; // Maintain rightmost pointing to max node
250  }
251 
252  // Rebalance the tree.
253  while((pNode != pNodeRootRef) && (pNode->mpNodeParent->mColor == kRBTreeColorRed))
254  {
255  rbtree_node_base* const pNodeParentParent = pNode->mpNodeParent->mpNodeParent;
256 
257  if(pNode->mpNodeParent == pNodeParentParent->mpNodeLeft)
258  {
259  rbtree_node_base* const pNodeTemp = pNodeParentParent->mpNodeRight;
260 
261  if(pNodeTemp && (pNodeTemp->mColor == kRBTreeColorRed))
262  {
263  pNode->mpNodeParent->mColor = kRBTreeColorBlack;
264  pNodeTemp->mColor = kRBTreeColorBlack;
265  pNodeParentParent->mColor = kRBTreeColorRed;
266  pNode = pNodeParentParent;
267  }
268  else
269  {
270  if(pNode == pNode->mpNodeParent->mpNodeRight)
271  {
272  pNode = pNode->mpNodeParent;
273  pNodeRootRef = RBTreeRotateLeft(pNode, pNodeRootRef);
274  }
275 
276  pNode->mpNodeParent->mColor = kRBTreeColorBlack;
277  pNodeParentParent->mColor = kRBTreeColorRed;
278  pNodeRootRef = RBTreeRotateRight(pNodeParentParent, pNodeRootRef);
279  }
280  }
281  else
282  {
283  rbtree_node_base* const pNodeTemp = pNodeParentParent->mpNodeLeft;
284 
285  if(pNodeTemp && (pNodeTemp->mColor == kRBTreeColorRed))
286  {
287  pNode->mpNodeParent->mColor = kRBTreeColorBlack;
288  pNodeTemp->mColor = kRBTreeColorBlack;
289  pNodeParentParent->mColor = kRBTreeColorRed;
290  pNode = pNodeParentParent;
291  }
292  else
293  {
294  if(pNode == pNode->mpNodeParent->mpNodeLeft)
295  {
296  pNode = pNode->mpNodeParent;
297  pNodeRootRef = RBTreeRotateRight(pNode, pNodeRootRef);
298  }
299 
300  pNode->mpNodeParent->mColor = kRBTreeColorBlack;
301  pNodeParentParent->mColor = kRBTreeColorRed;
302  pNodeRootRef = RBTreeRotateLeft(pNodeParentParent, pNodeRootRef);
303  }
304  }
305  }
306 
307  pNodeRootRef->mColor = kRBTreeColorBlack;
308 
309  } // RBTreeInsert
310 
311 
312 
313 
317  EASTL_API void RBTreeErase(rbtree_node_base* pNode, rbtree_node_base* pNodeAnchor)
318  {
319  rbtree_node_base*& pNodeRootRef = pNodeAnchor->mpNodeParent;
320  rbtree_node_base*& pNodeLeftmostRef = pNodeAnchor->mpNodeLeft;
321  rbtree_node_base*& pNodeRightmostRef = pNodeAnchor->mpNodeRight;
322  rbtree_node_base* pNodeSuccessor = pNode;
323  rbtree_node_base* pNodeChild = NULL;
324  rbtree_node_base* pNodeChildParent = NULL;
325 
326  if(pNodeSuccessor->mpNodeLeft == NULL) // pNode has at most one non-NULL child.
327  pNodeChild = pNodeSuccessor->mpNodeRight; // pNodeChild might be null.
328  else if(pNodeSuccessor->mpNodeRight == NULL) // pNode has exactly one non-NULL child.
329  pNodeChild = pNodeSuccessor->mpNodeLeft; // pNodeChild is not null.
330  else
331  {
332  // pNode has two non-null children. Set pNodeSuccessor to pNode's successor. pNodeChild might be NULL.
333  pNodeSuccessor = pNodeSuccessor->mpNodeRight;
334 
335  while(pNodeSuccessor->mpNodeLeft)
336  pNodeSuccessor = pNodeSuccessor->mpNodeLeft;
337 
338  pNodeChild = pNodeSuccessor->mpNodeRight;
339  }
340 
341  // Here we remove pNode from the tree and fix up the node pointers appropriately around it.
342  if(pNodeSuccessor == pNode) // If pNode was a leaf node (had both NULL children)...
343  {
344  pNodeChildParent = pNodeSuccessor->mpNodeParent; // Assign pNodeReplacement's parent.
345 
346  if(pNodeChild)
347  pNodeChild->mpNodeParent = pNodeSuccessor->mpNodeParent;
348 
349  if(pNode == pNodeRootRef) // If the node being deleted is the root node...
350  pNodeRootRef = pNodeChild; // Set the new root node to be the pNodeReplacement.
351  else
352  {
353  if(pNode == pNode->mpNodeParent->mpNodeLeft) // If pNode is a left node...
354  pNode->mpNodeParent->mpNodeLeft = pNodeChild; // Make pNode's replacement node be on the same side.
355  else
356  pNode->mpNodeParent->mpNodeRight = pNodeChild;
357  // Now pNode is disconnected from the bottom of the tree (recall that in this pathway pNode was determined to be a leaf).
358  }
359 
360  if(pNode == pNodeLeftmostRef) // If pNode is the tree begin() node...
361  {
362  // Because pNode is the tree begin(), pNode->mpNodeLeft must be NULL.
363  // Here we assign the new begin() (first node).
364  if(pNode->mpNodeRight)
365  pNodeLeftmostRef = RBTreeGetMinChild(pNodeChild);
366  else
367  pNodeLeftmostRef = pNode->mpNodeParent; // This makes (pNodeLeftmostRef == end()) if (pNode == root node)
368  }
369 
370  if(pNode == pNodeRightmostRef) // If pNode is the tree last (rbegin()) node...
371  {
372  // Because pNode is the tree rbegin(), pNode->mpNodeRight must be NULL.
373  // Here we assign the new rbegin() (last node)
374  if(pNode->mpNodeLeft)
375  pNodeRightmostRef = RBTreeGetMaxChild(pNodeChild);
376  else // pNodeChild == pNode->mpNodeLeft
377  pNodeRightmostRef = pNode->mpNodeParent; // makes pNodeRightmostRef == &mAnchor if pNode == pNodeRootRef
378  }
379  }
380  else // else (pNodeSuccessor != pNode)
381  {
382  // Relink pNodeSuccessor in place of pNode. pNodeSuccessor is pNode's successor.
383  // We specifically set pNodeSuccessor to be on the right child side of pNode, so fix up the left child side.
384  pNode->mpNodeLeft->mpNodeParent = pNodeSuccessor;
385  pNodeSuccessor->mpNodeLeft = pNode->mpNodeLeft;
386 
387  if(pNodeSuccessor == pNode->mpNodeRight) // If pNode's successor was at the bottom of the tree... (yes that's effectively what this statement means)
388  pNodeChildParent = pNodeSuccessor; // Assign pNodeReplacement's parent.
389  else
390  {
391  pNodeChildParent = pNodeSuccessor->mpNodeParent;
392 
393  if(pNodeChild)
394  pNodeChild->mpNodeParent = pNodeChildParent;
395 
396  pNodeChildParent->mpNodeLeft = pNodeChild;
397 
398  pNodeSuccessor->mpNodeRight = pNode->mpNodeRight;
399  pNode->mpNodeRight->mpNodeParent = pNodeSuccessor;
400  }
401 
402  if(pNode == pNodeRootRef)
403  pNodeRootRef = pNodeSuccessor;
404  else if(pNode == pNode->mpNodeParent->mpNodeLeft)
405  pNode->mpNodeParent->mpNodeLeft = pNodeSuccessor;
406  else
407  pNode->mpNodeParent->mpNodeRight = pNodeSuccessor;
408 
409  // Now pNode is disconnected from the tree.
410 
411  pNodeSuccessor->mpNodeParent = pNode->mpNodeParent;
412  eastl::swap(pNodeSuccessor->mColor, pNode->mColor);
413  }
414 
415  // Here we do tree balancing as per the conventional red-black tree algorithm.
416  if(pNode->mColor == kRBTreeColorBlack)
417  {
418  while((pNodeChild != pNodeRootRef) && ((pNodeChild == NULL) || (pNodeChild->mColor == kRBTreeColorBlack)))
419  {
420  if(pNodeChild == pNodeChildParent->mpNodeLeft)
421  {
422  rbtree_node_base* pNodeTemp = pNodeChildParent->mpNodeRight;
423 
424  if(pNodeTemp->mColor == kRBTreeColorRed)
425  {
426  pNodeTemp->mColor = kRBTreeColorBlack;
427  pNodeChildParent->mColor = kRBTreeColorRed;
428  pNodeRootRef = RBTreeRotateLeft(pNodeChildParent, pNodeRootRef);
429  pNodeTemp = pNodeChildParent->mpNodeRight;
430  }
431 
432  if(((pNodeTemp->mpNodeLeft == NULL) || (pNodeTemp->mpNodeLeft->mColor == kRBTreeColorBlack)) &&
433  ((pNodeTemp->mpNodeRight == NULL) || (pNodeTemp->mpNodeRight->mColor == kRBTreeColorBlack)))
434  {
435  pNodeTemp->mColor = kRBTreeColorRed;
436  pNodeChild = pNodeChildParent;
437  pNodeChildParent = pNodeChildParent->mpNodeParent;
438  }
439  else
440  {
441  if((pNodeTemp->mpNodeRight == NULL) || (pNodeTemp->mpNodeRight->mColor == kRBTreeColorBlack))
442  {
443  pNodeTemp->mpNodeLeft->mColor = kRBTreeColorBlack;
444  pNodeTemp->mColor = kRBTreeColorRed;
445  pNodeRootRef = RBTreeRotateRight(pNodeTemp, pNodeRootRef);
446  pNodeTemp = pNodeChildParent->mpNodeRight;
447  }
448 
449  pNodeTemp->mColor = pNodeChildParent->mColor;
450  pNodeChildParent->mColor = kRBTreeColorBlack;
451 
452  if(pNodeTemp->mpNodeRight)
453  pNodeTemp->mpNodeRight->mColor = kRBTreeColorBlack;
454 
455  pNodeRootRef = RBTreeRotateLeft(pNodeChildParent, pNodeRootRef);
456  break;
457  }
458  }
459  else
460  {
461  // The following is the same as above, with mpNodeRight <-> mpNodeLeft.
462  rbtree_node_base* pNodeTemp = pNodeChildParent->mpNodeLeft;
463 
464  if(pNodeTemp->mColor == kRBTreeColorRed)
465  {
466  pNodeTemp->mColor = kRBTreeColorBlack;
467  pNodeChildParent->mColor = kRBTreeColorRed;
468 
469  pNodeRootRef = RBTreeRotateRight(pNodeChildParent, pNodeRootRef);
470  pNodeTemp = pNodeChildParent->mpNodeLeft;
471  }
472 
473  if(((pNodeTemp->mpNodeRight == NULL) || (pNodeTemp->mpNodeRight->mColor == kRBTreeColorBlack)) &&
474  ((pNodeTemp->mpNodeLeft == NULL) || (pNodeTemp->mpNodeLeft->mColor == kRBTreeColorBlack)))
475  {
476  pNodeTemp->mColor = kRBTreeColorRed;
477  pNodeChild = pNodeChildParent;
478  pNodeChildParent = pNodeChildParent->mpNodeParent;
479  }
480  else
481  {
482  if((pNodeTemp->mpNodeLeft == NULL) || (pNodeTemp->mpNodeLeft->mColor == kRBTreeColorBlack))
483  {
484  pNodeTemp->mpNodeRight->mColor = kRBTreeColorBlack;
485  pNodeTemp->mColor = kRBTreeColorRed;
486 
487  pNodeRootRef = RBTreeRotateLeft(pNodeTemp, pNodeRootRef);
488  pNodeTemp = pNodeChildParent->mpNodeLeft;
489  }
490 
491  pNodeTemp->mColor = pNodeChildParent->mColor;
492  pNodeChildParent->mColor = kRBTreeColorBlack;
493 
494  if(pNodeTemp->mpNodeLeft)
495  pNodeTemp->mpNodeLeft->mColor = kRBTreeColorBlack;
496 
497  pNodeRootRef = RBTreeRotateRight(pNodeChildParent, pNodeRootRef);
498  break;
499  }
500  }
501  }
502 
503  if(pNodeChild)
504  pNodeChild->mColor = kRBTreeColorBlack;
505  }
506 
507  } // RBTreeErase
508 
509 
510 
511 } // namespace eastl
EASTL_API void RBTreeErase(rbtree_node_base *pNode, rbtree_node_base *pNodeAnchor)
rbtree_node_base * RBTreeRotateLeft(rbtree_node_base *pNode, rbtree_node_base *pNodeRoot)
EASTL_API size_t RBTreeGetBlackCount(const rbtree_node_base *pNodeTop, const rbtree_node_base *pNodeBottom)
EASTL_API rbtree_node_base * RBTreeIncrement(const rbtree_node_base *pNode)
rbtree_node_base * RBTreeRotateRight(rbtree_node_base *pNode, rbtree_node_base *pNodeRoot)
EASTL_API void RBTreeInsert(rbtree_node_base *pNode, rbtree_node_base *pNodeParent, rbtree_node_base *pNodeAnchor, RBTreeSide insertionSide)
void swap(T &a, T &b)
EASTL_API rbtree_node_base * RBTreeDecrement(const rbtree_node_base *pNode)
EA Standard Template Library.