OpenBarnyard
 
Loading...
Searching...
No Matches
Protected Member Functions | Static Protected Member Functions | Protected Attributes | Static Protected Attributes | List of all members
T2GenericRedBlackTree Class Reference

#include <T2RedBlackTree.h>

Inheritance diagram for T2GenericRedBlackTree:
T2RedBlackTree< Pair >::Iterator< Pair > T2RedBlackTree< Pair >::CIterator< Pair > Node< Pair > T2RedBlackTree< Pair > T2RedBlackTree< T2Pair< KeyType, ValueType, TComparator< KeyType > > > T2RedBlackTree< T2Pair< const TCHAR *, TPooledString8 *, T2StringComparator< T2StringTraits< TCHAR > > > > T2RedBlackTree< T >

Protected Member Functions

 T2GenericRedBlackTree (T2Allocator *pAllocator)
 
 ~T2GenericRedBlackTree ()
 
T2Allocator * GetAllocator () const
 
size_t GetNumElements () const
 
T2GenericRedBlackTreeNode * GetFirstNode () const
 
T2GenericRedBlackTreeNode * Insert (T2GenericRedBlackTreeNode *pNode)
 
void DeleteFixUp (T2GenericRedBlackTreeNode *pNode)
 
T2GenericRedBlackTreeNode * DeleteNode (T2GenericRedBlackTreeNode *pNode)
 
void LeftRotate (T2GenericRedBlackTreeNode *pNode)
 
void RightRotate (T2GenericRedBlackTreeNode *pNode)
 

Static Protected Member Functions

static T2GenericRedBlackTreeNode * GetSuccessorOf (const T2GenericRedBlackTreeNode *pNode)
 
static T2GenericRedBlackTreeNode * GetPredecessorOf (const T2GenericRedBlackTreeNode *pNode)
 

Protected Attributes

T2Allocator * m_pAllocator
 
T2GenericRedBlackTreeNode m_oRoot
 
size_t m_iNumElements
 

Static Protected Attributes

static constinit T2GenericRedBlackTreeNode ms_oNil
 

Detailed Description

Definition at line 50 of file T2RedBlackTree.h.

Constructor & Destructor Documentation

◆ T2GenericRedBlackTree()

T2GenericRedBlackTree::T2GenericRedBlackTree ( T2Allocator * pAllocator)
inlineprotected

Definition at line 53 of file T2RedBlackTree.h.

54 : m_oRoot( ms_oNil )
55 {
56 m_pAllocator = pAllocator;
57 m_iNumElements = 0;
58 }
T2GenericRedBlackTree::ms_oNil
static constinit T2GenericRedBlackTreeNode ms_oNil
Definition T2RedBlackTree.h:93
T2GenericRedBlackTree::m_pAllocator
T2Allocator * m_pAllocator
Definition T2RedBlackTree.h:96
T2GenericRedBlackTree::m_oRoot
T2GenericRedBlackTreeNode m_oRoot
Definition T2RedBlackTree.h:97

◆ ~T2GenericRedBlackTree()

T2GenericRedBlackTree::~T2GenericRedBlackTree ( )
inlineprotected

Definition at line 60 of file T2RedBlackTree.h.

61 {
62 TASSERT( m_iNumElements == 0 );
63 }
TASSERT
#define TASSERT(X,...)
Definition Defines.h:138

Member Function Documentation

◆ DeleteFixUp()

void T2GenericRedBlackTree::DeleteFixUp ( T2GenericRedBlackTreeNode * pNode)
protected

Definition at line 92 of file T2RedBlackTree.cpp.

93{
94 TINT uVar2;
95 T2GenericRedBlackTreeNode* pTVar1;
96 T2GenericRedBlackTreeNode* pTVar3;
97 T2GenericRedBlackTreeNode* pTVar4;
98
99 pTVar4 = m_oRoot.m_pLeft;
100 while ( pNode->red == 0 && pTVar4 != pNode )
101 {
102 pTVar3 = pNode->m_pParent;
103 pTVar1 = pTVar3->m_pLeft;
104
105 if ( pNode == pTVar1 )
106 {
107 pTVar1 = pTVar3->m_pRight;
108
109 if ( pTVar1->red != 0 )
110 {
111 pTVar1->red = 0;
112 pNode->m_pParent->red = 1;
113 LeftRotate( pNode->m_pParent );
114 pTVar3 = pNode->m_pParent;
115 pTVar1 = pTVar3->m_pRight;
116 }
117
118 uVar2 = pTVar1->m_pRight->red;
119 if ( ( uVar2 == 0 ) && ( pTVar1->m_pLeft->red == 0 ) )
120 {
121 pTVar1->red = 1;
122 pNode = pNode->m_pParent;
123 }
124 else
125 {
126 if ( uVar2 == 0 )
127 {
128 pTVar1->m_pLeft->red = 0;
129 pTVar1->red = 1;
130 RightRotate( pTVar1 );
131 pTVar3 = pNode->m_pParent;
132 pTVar1 = pTVar3->m_pRight;
133 }
134
135 pTVar1->red = pTVar3->red;
136 pNode->m_pParent->red = 0;
137 pTVar1->m_pRight->red = 0;
138 LeftRotate( pNode->m_pParent );
139 pNode = pTVar4;
140 }
141 }
142 else
143 {
144 if ( pTVar1->red != 0 )
145 {
146 pTVar1->red = 0;
147 pNode->m_pParent->red = 1;
148 RightRotate( pNode->m_pParent );
149 pTVar3 = pNode->m_pParent;
150 pTVar1 = pTVar3->m_pLeft;
151 }
152
153 if ( pTVar1->m_pRight->red == 0 && pTVar1->m_pLeft->red == 0 )
154 {
155 pTVar1->red = 1;
156 pNode = pNode->m_pParent;
157 }
158 else
159 {
160 if ( pTVar1->m_pLeft->red == 0 )
161 {
162 pTVar1->m_pRight->red = 0;
163 pTVar1->red = 1;
164 LeftRotate( pTVar1 );
165 pTVar3 = pNode->m_pParent;
166 pTVar1 = pTVar3->m_pLeft;
167 }
168
169 pTVar1->red = pTVar3->red;
170 pNode->m_pParent->red = 0;
171 pTVar1->m_pLeft->red = 0;
172 RightRotate( pNode->m_pParent );
173 pNode = pTVar4;
174 }
175 }
176 }
177
178 pNode->red = 0;
179 CheckValid();
180}
TINT
int TINT
Definition Typedefs.h:7
T2GenericRedBlackTreeNode::m_pParent
T2GenericRedBlackTreeNode * m_pParent
Definition T2RedBlackTree.h:47
T2GenericRedBlackTreeNode::m_pRight
T2GenericRedBlackTreeNode * m_pRight
Definition T2RedBlackTree.h:46
T2GenericRedBlackTreeNode::m_pLeft
T2GenericRedBlackTreeNode * m_pLeft
Definition T2RedBlackTree.h:45
T2GenericRedBlackTree::LeftRotate
void LeftRotate(T2GenericRedBlackTreeNode *pNode)
Definition T2RedBlackTree.cpp:267
T2GenericRedBlackTree::RightRotate
void RightRotate(T2GenericRedBlackTreeNode *pNode)
Definition T2RedBlackTree.cpp:297

◆ DeleteNode()

T2GenericRedBlackTreeNode * T2GenericRedBlackTree::DeleteNode ( T2GenericRedBlackTreeNode * pNode)
protected

Definition at line 182 of file T2RedBlackTree.cpp.

183{
184 T2GenericRedBlackTreeNode* pTVar1;
185 T2GenericRedBlackTreeNode* y;
186 T2GenericRedBlackTreeNode* pTVar3;
187
188 y = pNode;
189 if ( ( pNode->m_pLeft != &ms_oNil ) && ( pNode->m_pRight != &ms_oNil ) )
190 {
191 y = GetSuccessorOf( pNode );
192 }
193
194 pTVar3 = y->m_pLeft;
195 if ( pTVar3 == &ms_oNil )
196 {
197 pTVar3 = y->m_pRight;
198 }
199
200 pTVar1 = y->m_pParent;
201 pTVar3->m_pParent = pTVar1;
202
203 if ( &m_oRoot == pTVar1 )
204 {
205 m_oRoot.m_pLeft = pTVar3;
206 }
207 else
208 {
209 pTVar1 = y->m_pParent;
210
211 if ( y == pTVar1->m_pLeft )
212 {
213 pTVar1->m_pLeft = pTVar3;
214 }
215 else
216 {
217 pTVar1->m_pRight = pTVar3;
218 }
219 }
220
221 if ( y == pNode )
222 {
223 if ( y->red == 0 )
224 {
225 DeleteFixUp( pTVar3 );
226 }
227
228 CheckValid();
229 TASSERT( 0 == ms_oNil.red );
230 m_iNumElements -= 1;
231
232 return y;
233 }
234
235 TASSERT( y != &ms_oNil );
236
237 y->m_pLeft = pNode->m_pLeft;
238 y->m_pRight = pNode->m_pRight;
239 y->m_pParent = pNode->m_pParent;
240 pNode->m_pRight->m_pParent = y;
241 pNode->m_pLeft->m_pParent = y;
242 pTVar1 = pNode->m_pParent;
243
244 if ( pNode == pTVar1->m_pLeft )
245 {
246 pTVar1->m_pLeft = y;
247 }
248 else
249 {
250 pTVar1->m_pRight = y;
251 }
252
253 TINT oldRedValue = y->red;
254 y->red = pNode->red;
255
256 if ( oldRedValue == 0 )
257 {
258 DeleteFixUp( pTVar3 );
259 }
260
261 CheckValid();
262 TASSERT( 0 == ms_oNil.red );
263 m_iNumElements -= 1;
264 return pNode;
265}
T2GenericRedBlackTree::GetSuccessorOf
static T2GenericRedBlackTreeNode * GetSuccessorOf(const T2GenericRedBlackTreeNode *pNode)
Definition T2RedBlackTree.cpp:327
T2GenericRedBlackTree::DeleteFixUp
void DeleteFixUp(T2GenericRedBlackTreeNode *pNode)
Definition T2RedBlackTree.cpp:92

◆ GetAllocator()

T2Allocator * T2GenericRedBlackTree::GetAllocator ( ) const
inlineprotected

Definition at line 65 of file T2RedBlackTree.h.

66 {
67 return m_pAllocator;
68 }

◆ GetFirstNode()

T2GenericRedBlackTreeNode * T2GenericRedBlackTree::GetFirstNode ( ) const
protected

Definition at line 14 of file T2RedBlackTree.cpp.

15{
16 T2GenericRedBlackTreeNode* pCurrentNode = &m_oRoot;
17 T2GenericRedBlackTreeNode* pResult = TNULL;
18
19 while ( pCurrentNode != &ms_oNil )
20 {
21 pResult = pCurrentNode;
22 pCurrentNode = pResult->m_pLeft;
23 }
24
25 return pResult;
26}
TNULL
#define TNULL
Definition Typedefs.h:23

◆ GetNumElements()

size_t T2GenericRedBlackTree::GetNumElements ( ) const
inlineprotected

Definition at line 70 of file T2RedBlackTree.h.

71 {
72 return m_iNumElements;
73 }

◆ GetPredecessorOf()

T2GenericRedBlackTreeNode * T2GenericRedBlackTree::GetPredecessorOf ( const T2GenericRedBlackTreeNode * pNode)
staticprotected

Definition at line 366 of file T2RedBlackTree.cpp.

367{
368 T2GenericRedBlackTreeNode* pTVar1;
369 T2GenericRedBlackTreeNode* pTVar2 = pNode->m_pLeft;
370 TBOOL bVar3;
371
372 if ( pTVar2 == &ms_oNil )
373 {
374 pTVar2 = pNode->m_pParent;
375 if ( pNode == pTVar2->m_pLeft )
376 {
377 do
378 {
379 pTVar1 = pTVar2->m_pParent;
380
381 if ( pTVar1 == pTVar2 )
382 {
383 return &ms_oNil;
384 }
385
386 bVar3 = pTVar2 == pTVar1->m_pLeft;
387 pTVar2 = pTVar1;
388 } while ( bVar3 );
389
390 return pTVar1;
391 }
392 }
393 else
394 {
395 pTVar1 = pTVar2->m_pRight;
396
397 if ( pTVar2->m_pRight != &ms_oNil )
398 {
399 do
400 {
401 pTVar2 = pTVar1;
402 pTVar1 = pTVar2->m_pRight;
403 } while ( pTVar2->m_pRight != &ms_oNil );
404 }
405 }
406
407 return pTVar2;
408}
TBOOL
bool TBOOL
Definition Typedefs.h:6

◆ GetSuccessorOf()

T2GenericRedBlackTreeNode * T2GenericRedBlackTree::GetSuccessorOf ( const T2GenericRedBlackTreeNode * pNode)
staticprotected

Definition at line 327 of file T2RedBlackTree.cpp.

328{
329 T2GenericRedBlackTreeNode* pTVar1;
330 T2GenericRedBlackTreeNode* pTVar2;
331 bool bVar3;
332
333 pTVar1 = pNode->m_pRight;
334 if ( pTVar1 == &ms_oNil )
335 {
336 pTVar1 = pNode->m_pParent;
337 pTVar2 = pTVar1;
338 if ( pNode == pTVar1->m_pRight )
339 {
340 do {
341 pTVar1 = pTVar2->m_pParent;
342 bVar3 = pTVar2 == pTVar1->m_pRight;
343 pTVar2 = pTVar1;
344 } while ( bVar3 );
345 }
346 if ( pTVar1->m_pParent == pTVar1 )
347 {
348 pTVar1 = &ms_oNil;
349 }
350 }
351 else
352 {
353 pTVar2 = pTVar1->m_pLeft;
354 if ( pTVar2 != &ms_oNil )
355 {
356 do {
357 pTVar1 = pTVar2;
358 pTVar2 = pTVar2->m_pLeft;
359 } while ( pTVar2 != &ms_oNil );
360 return pTVar1;
361 }
362 }
363 return pTVar1;
364}

◆ Insert()

T2GenericRedBlackTreeNode * T2GenericRedBlackTree::Insert ( T2GenericRedBlackTreeNode * pNode)
protected

Definition at line 28 of file T2RedBlackTree.cpp.

29{
30 T2GenericRedBlackTreeNode* pNode_00;
31 T2GenericRedBlackTreeNode* pTVar1;
32 T2GenericRedBlackTreeNode* node;
33
34 m_iNumElements += 1;
35 pNode->red = 1;
36 node = pNode;
37
38 while ( pNode_00 = node->m_pParent, pNode_00->red != 0 )
39 {
40 pTVar1 = pNode_00->m_pParent->m_pLeft;
41 if ( pNode_00 == pTVar1 )
42 {
43 pTVar1 = pNode_00->m_pParent->m_pRight;
44
45 if ( pTVar1->red == 0 )
46 {
47 if ( node == pNode_00->m_pRight )
48 {
49 LeftRotate( pNode_00 );
50 node = pNode_00;
51 }
52
53 node->m_pParent->red = 0;
54 node->m_pParent->m_pParent->red = 1;
55 RightRotate( node->m_pParent->m_pParent );
56 }
57 else
58 {
59 pNode_00->red = 0;
60 pTVar1->red = 0;
61 node->m_pParent->m_pParent->red = 1;
62 node = node->m_pParent->m_pParent;
63 }
64 }
65 else if ( pTVar1->red == 0 )
66 {
67 if ( node == pNode_00->m_pLeft )
68 {
69 RightRotate( pNode_00 );
70 node = pNode_00;
71 }
72
73 node->m_pParent->red = 0;
74 node->m_pParent->m_pParent->red = 1;
75 LeftRotate( node->m_pParent->m_pParent );
76 }
77 else
78 {
79 pNode_00->red = 0;
80 pTVar1->red = 0;
81 node->m_pParent->m_pParent->red = 1;
82 node = node->m_pParent->m_pParent;
83 }
84 }
85
86 m_oRoot.m_pLeft->red = 0;
87 CheckValid();
88
89 return pNode;
90}

◆ LeftRotate()

void T2GenericRedBlackTree::LeftRotate ( T2GenericRedBlackTreeNode * pNode)
protected

Definition at line 267 of file T2RedBlackTree.cpp.

268{
269 T2GenericRedBlackTreeNode* pTVar1;
270 T2GenericRedBlackTreeNode* pTVar2;
271
272 pTVar2 = pNode->m_pRight;
273 pNode->m_pRight = pTVar2->m_pLeft;
274
275 if ( pTVar2->m_pLeft != &ms_oNil )
276 {
277 pTVar2->m_pLeft->m_pParent = pNode;
278 }
279
280 pTVar2->m_pParent = pNode->m_pParent;
281 pTVar1 = pNode->m_pParent;
282
283 if ( pNode == pTVar1->m_pLeft )
284 {
285 pTVar1->m_pLeft = pTVar2;
286 }
287 else
288 {
289 pTVar1->m_pRight = pTVar2;
290 }
291
292 pTVar2->m_pLeft = pNode;
293 pNode->m_pParent = pTVar2;
294 CheckValid();
295}

◆ RightRotate()

void T2GenericRedBlackTree::RightRotate ( T2GenericRedBlackTreeNode * pNode)
protected

Definition at line 297 of file T2RedBlackTree.cpp.

298{
299 T2GenericRedBlackTreeNode* pTVar1;
300 T2GenericRedBlackTreeNode* pTVar2;
301
302 pTVar2 = pNode->m_pLeft;
303 pNode->m_pLeft = pTVar2->m_pRight;
304
305 if ( pTVar2->m_pRight != &ms_oNil )
306 {
307 pTVar2->m_pRight->m_pParent = pNode;
308 }
309
310 pTVar2->m_pParent = pNode->m_pParent;
311 pTVar1 = pNode->m_pParent;
312
313 if ( pNode == pTVar1->m_pLeft )
314 {
315 pTVar1->m_pLeft = pTVar2;
316 }
317 else
318 {
319 pTVar1->m_pRight = pTVar2;
320 }
321
322 pTVar2->m_pRight = pNode;
323 pNode->m_pParent = pTVar2;
324 CheckValid();
325}

Member Data Documentation

◆ m_iNumElements

size_t T2GenericRedBlackTree::m_iNumElements
protected

Definition at line 98 of file T2RedBlackTree.h.

◆ m_oRoot

T2GenericRedBlackTreeNode T2GenericRedBlackTree::m_oRoot
mutableprotected

Definition at line 97 of file T2RedBlackTree.h.

◆ m_pAllocator

T2Allocator* T2GenericRedBlackTree::m_pAllocator
protected

Definition at line 96 of file T2RedBlackTree.h.

◆ ms_oNil

T2GenericRedBlackTreeNode T2GenericRedBlackTree::ms_oNil
staticconstinitprotected

Definition at line 93 of file T2RedBlackTree.h.

The documentation for this class was generated from the following files: