• R/O
  • SSH
  • HTTPS

eirrepo: Commit


Commit MetaInfo

Revision97 (tree)
Time2018-05-13 18:41:26
Authorquiret

Log Message

- fixed a bug in AVLTree::remove_node where height was not updated for the closestReplacement node
- optimized AVLTree implementation in general, now without any recursive function calls
- improved the AVL tree unit tests

Change Summary

Incremental Difference

--- common/sdk/AVLTree.h (revision 96)
+++ common/sdk/AVLTree.h (revision 97)
@@ -3,7 +3,7 @@
33 * PROJECT: Multi Theft Auto v1.2
44 * LICENSE: See LICENSE in the top level directory
55 * FILE: Shared/core/OSUtils.avltree.h
6-* PURPOSE: AVL-tree implementation for the native heap allocator
6+* PURPOSE: AVL-tree implementation (for the native heap allocator)
77 *
88 * Multi Theft Auto is available from http://www.multitheftauto.com/
99 *
@@ -23,6 +23,7 @@
2323 // possible.
2424 // YOU CANNOT STORE SAME VALUES IN AN AVL TREE!
2525
26+// Useful to fetch an actual struct if AVLNode is a struct-member.
2627 #define AVL_GETITEM( type, nodePtr, nodeMemb ) ( (type*)( (char*)nodePtr - offsetof(type, nodeMemb) ) )
2728
2829 // Has to be less-than comparable, in a total order.
@@ -33,10 +34,17 @@
3334 AVLNode *left, *right;
3435 };
3536
37+// Should never be thrown, but who knows?
38+struct avl_runtime_exception
39+{};
40+
3641 template <typename dispatcherType>
3742 struct AVLTree
3843 {
44+ // This class is NOT THREAD-SAFE.
45+
3946 private:
47+ // Here is a list of things we want to query the dispatcherType for.
4048 static AINLINE bool is_node_less_than( const AVLNode *node, const AVLNode *compareWith )
4149 {
4250 return dispatcherType::IsNodeLessThan( node, compareWith );
@@ -58,11 +66,14 @@
5866 private:
5967 AINLINE size_t height_func( size_t leftHeight, size_t rightHeight )
6068 {
69+ // So that we can choose a specific implementation of max function.
6170 return std::max( leftHeight, rightHeight );
6271 }
6372
6473 AINLINE size_t calc_height_of_node( AVLNode *firstNode, AVLNode *secondNode )
6574 {
75+ // Calculate the maximum number of nodes that are on a path to the bottom in a binary tree.
76+
6677 if ( firstNode == nullptr && secondNode == nullptr )
6778 {
6879 return 0;
@@ -83,9 +94,43 @@
8394 height_of_nodes_underneath = height_func( firstNode->height, secondNode->height );
8495 }
8596
97+ // We include the node that starts of our child.
98+ // THIS IS NOT THE ROOT NODE THAT IS INCLUDED.
8699 return ( 1 + height_of_nodes_underneath );
87100 }
88101
102+ AINLINE AVLNode** get_node_src_ptr( AVLNode *parent, AVLNode *node )
103+ {
104+ AVLNode **nodePtr;
105+
106+ if ( parent )
107+ {
108+ if ( parent->left == node )
109+ {
110+ nodePtr = &parent->left;
111+ }
112+ else if ( parent->right == node )
113+ {
114+ nodePtr = &parent->right;
115+ }
116+ else
117+ {
118+ throw avl_runtime_exception();
119+ }
120+ }
121+ else
122+ {
123+ if ( this->root != node )
124+ {
125+ throw avl_runtime_exception();
126+ }
127+
128+ nodePtr = &this->root;
129+ }
130+
131+ return nodePtr;
132+ }
133+
89134 AINLINE void rotate( AVLNode *node, AVLNode *moveToUsNeighbor, bool leftTrueRightFalse )
90135 {
91136 // Both node and moveToUsNeighbor must not be nullptr.
@@ -140,36 +185,13 @@
140185
141186 moveToUsNeighbor->parent = prevParentOfMainNode;
142187
143- // Is it the new root?
144- if ( prevParentOfMainNode == nullptr )
188+ // Update the node pointer.
145189 {
146- assert( node == this->root );
190+ AVLNode **nodePtr = get_node_src_ptr( prevParentOfMainNode, node );
147191
148- this->root = moveToUsNeighbor;
192+ *nodePtr = moveToUsNeighbor;
149193 }
150- else
151- {
152- // Then the node has to be some sort of child.
153- // Update the relationship depending on what actual child it is.
154- if ( prevParentOfMainNode->left == node )
155- {
156- assert( is_node_less_than( node, prevParentOfMainNode ) == true );
157194
158- prevParentOfMainNode->left = moveToUsNeighbor;
159- }
160- else if ( prevParentOfMainNode->right == node )
161- {
162- assert( is_node_less_than( prevParentOfMainNode, node ) == true );
163-
164- prevParentOfMainNode->right = moveToUsNeighbor;
165- }
166- else
167- {
168- // AVL TREES CANNOT STORE SAME VALUES.
169- assert( 0 );
170- }
171- }
172-
173195 node->parent = moveToUsNeighbor;
174196
175197 // Need to update node heights.
@@ -177,6 +199,7 @@
177199
178200 node->height = subHeight;
179201
202+ // Height of the node on top.
180203 size_t fullHeight = 1;
181204
182205 if ( tuggedWithNode == nullptr )
@@ -191,8 +214,10 @@
191214 moveToUsNeighbor->height = fullHeight;
192215 }
193216
194- AINLINE bool detect_tree_two_imbalance( AVLNode *maybeBigger, AVLNode *maybeSmaller )
217+ static AINLINE bool detect_tree_two_imbalance( AVLNode *maybeBigger, AVLNode *maybeSmaller )
195218 {
219+ // Calculates the first imbalance equation of the AVL balance method,
220+
196221 if ( maybeBigger == nullptr )
197222 {
198223 return false;
@@ -210,8 +235,10 @@
210235 return ( maybeBiggerHeight > ( 1 + maybeSmallerHeight ) );
211236 }
212237
213- AINLINE bool detect_tree_one_imbalance( AVLNode *maybeSmaller, AVLNode *maybeBigger )
238+ static AINLINE bool detect_tree_one_imbalance( AVLNode *maybeSmaller, AVLNode *maybeBigger )
214239 {
240+ // Calculates the second imbalance equation of the AVL balance method,
241+
215242 if ( maybeBigger == nullptr )
216243 {
217244 return false;
@@ -300,6 +327,18 @@
300327 return iter;
301328 }
302329
330+ AINLINE void update_invalidated_tree_height( AVLNode *parent )
331+ {
332+ while ( parent != nullptr )
333+ {
334+ parent->height = calc_height_of_node( parent->left, parent->right );
335+
336+ balance( parent );
337+
338+ parent = parent->parent;
339+ }
340+ }
341+
303342 public:
304343 inline bool Insert( AVLNode *node )
305344 {
@@ -325,21 +364,16 @@
325364 node->right = nullptr;
326365 node->parent = parent;
327366
328- // Update to the very top.
329- while ( parent != nullptr )
330- {
331- parent->height = calc_height_of_node( parent->left, parent->right );
367+ // Update to the very top all trees that have been modified.
368+ // This is much more efficient than doing a recursive method.
369+ update_invalidated_tree_height( parent );
332370
333- balance( parent );
334-
335- parent = parent->parent;
336- }
337-
338371 return true;
339372 }
340373
341374 private:
342- static AINLINE AVLNode* FindMaxNode( AVLNode *searchFrom, AVLNode** &searchFromPtrInOut )
375+ // Simple method that is compatible with any binary tree. :)
376+ static AINLINE AVLNode* FindMaxNode( AVLNode *searchFrom, AVLNode**& searchFromPtrInOut )
343377 {
344378 AVLNode *curMax = searchFrom;
345379 AVLNode **searchFromPtr = searchFromPtrInOut;
@@ -390,41 +424,34 @@
390424 AVLNode **closestReplacementPtr = &node->left;
391425 AVLNode *closestReplacement = FindMaxNode( leftChild, closestReplacementPtr );
392426
427+ // Now we perform what someone usually has to do when updating the value of a node.
428+ // But this is optimized to keep the pointers valid.
429+
393430 // Remove the closest node.
394- remove_node( closestReplacement, closestReplacementPtr, closestReplacement->parent );
431+ // We know that the node has no right child, because it is the maximum in its subtree.
432+ {
433+ *closestReplacementPtr = closestReplacement->left;
395434
435+ update_invalidated_tree_height( closestReplacement->parent );
436+ }
437+
396438 // We need to update members because they could be out-of-date.
397439 parent = node->parent;
398440 leftChild = node->left;
399441 rightChild = node->right;
400442
401- if ( parent )
402- {
403- if ( parent->left == node )
404- {
405- nodePtr = &parent->left;
406- }
407- else if ( parent->right == node )
408- {
409- nodePtr = &parent->right;
410- }
411- else
412- {
413- assert( 0 );
414- }
415- }
416- else
417- {
418- nodePtr = &this->root;
419- }
443+ nodePtr = get_node_src_ptr( parent, node );
420444
421445 // Replace nodes.
422446 closestReplacement->parent = parent;
423447 closestReplacement->left = leftChild;
424448 closestReplacement->right = rightChild;
449+ closestReplacement->height = node->height;
425450
426451 *nodePtr = closestReplacement;
427452
453+ // Now closestReplacement takes the role of node.
454+
428455 // Update parents.
429456 if ( leftChild != nullptr )
430457 {
@@ -438,22 +465,39 @@
438465 }
439466
440467 // Update height of the changed tree.
441- while ( parent != nullptr )
442- {
443- parent->height = calc_height_of_node( parent->left, parent->right );
468+ update_invalidated_tree_height( parent );
469+ }
444470
445- balance( parent );
471+public:
472+ inline bool IsNodeInsideTree( AVLNode *node )
473+ {
474+ AVLNode *parent;
475+ AVLNode **iterPtr;
446476
447- parent = parent->parent;
477+ AVLNode *iter = ScanForNodePosition( node, iterPtr, parent );
478+
479+ if ( iter == nullptr || iter != node )
480+ {
481+ return false;
448482 }
483+
484+ return true;
449485 }
486+
487+ inline void RemoveByNodeFast( AVLNode *node )
488+ {
489+ // A faster removal method which assumes that node does really reside inside this AVL tree.
490+ AVLNode *parent = node->parent;
491+ AVLNode **iterPtr = get_node_src_ptr( parent, node );
450492
451-public:
493+ remove_node( node, iterPtr, parent );
494+ }
495+
452496 inline bool RemoveByNode( AVLNode *node )
453497 {
454498 // Find the node we are talking about.
455499 // This is basically just verification that the node is inside this tree, meow.
456- // We could create another function that just assumes the node really inside.
500+ // Use RemoveByNodeFast if you know for sure that the node is inside this tree.
457501 AVLNode *parent;
458502 AVLNode **iterPtr;
459503 {
@@ -479,31 +523,125 @@
479523
480524 private:
481525 template <typename callbackType>
482- void walk_recursively( AVLNode *walkNode, const callbackType& cb )
526+ static AINLINE void walk_iteratively( AVLNode *walkNode, const callbackType& cb )
483527 {
484- if ( AVLNode *leftChild = walkNode->left )
528+ AVLNode *curNode = walkNode;
529+
530+ while ( true )
485531 {
486- walk_recursively( leftChild, cb );
487- }
532+ // First iterate the left child, then current node and then the right node.
533+ if ( AVLNode *leftChild = curNode->left )
534+ {
535+ curNode = leftChild;
536+ }
537+ else
538+ {
539+ // Now we can iterate this node.
540+ cb( curNode );
488541
489- cb( walkNode );
542+ // Iterate the right.
543+ if ( AVLNode *rightNode = curNode->right )
544+ {
545+ curNode = rightNode;
546+ }
547+ else
548+ {
549+ // Go up until we find a branch to the right again.
550+ // On this way up call for each node when we come from a left branch.
551+ AVLNode *parent = curNode->parent;
490552
491- if ( AVLNode *rightChild = walkNode->right )
492- {
493- walk_recursively( rightChild, cb );
553+ while ( parent != nullptr )
554+ {
555+ AVLNode *nextChild = nullptr;
556+
557+ if ( curNode == parent->left )
558+ {
559+ cb( parent );
560+
561+ nextChild = parent->right;
562+ }
563+
564+ if ( nextChild != nullptr )
565+ {
566+ curNode = nextChild;
567+ break;
568+ }
569+
570+ // Go up one more.
571+ curNode = parent;
572+ parent = parent->parent;
573+ }
574+
575+ if ( parent == nullptr )
576+ {
577+ break;
578+ }
579+ }
580+ }
494581 }
495582 }
496583
497584 public:
585+ // Goes through each node in sorted order.
498586 template <typename callbackType>
499587 inline void Walk( const callbackType& cb )
500588 {
501589 if ( AVLNode *rootNode = this->root )
502590 {
503- walk_recursively( rootNode, cb );
591+ walk_iteratively( rootNode, cb );
504592 }
505593 }
506594
595+ // Returns the maximum path length to the botton of the tree.
596+ inline size_t GetTreeHeight( void ) const
597+ {
598+ if ( AVLNode *rootNode = this->root )
599+ {
600+ return ( 1 + rootNode->height );
601+ }
602+
603+ return 0;
604+ }
605+
606+ // Should always succeed.
607+ inline void Validate( void )
608+ {
609+ Walk(
610+ []( AVLNode *node )
611+ {
612+ if ( AVLNode *parent = node->parent )
613+ {
614+ if ( parent->left == node )
615+ {
616+ assert( is_node_less_than( node, parent ) == true );
617+ }
618+ else if ( parent->right == node )
619+ {
620+ assert( is_node_less_than( parent, node ) == true );
621+ }
622+ else
623+ {
624+ assert( 0 );
625+ }
626+ }
627+
628+ if ( AVLNode *leftNode = node->left )
629+ {
630+ assert( leftNode->parent == node );
631+ assert( is_node_less_than( leftNode, node ) == true );
632+ }
633+
634+ if ( AVLNode *rightNode = node->right )
635+ {
636+ assert( rightNode->parent == node );
637+ assert( is_node_less_than( node, rightNode ) == true );
638+ }
639+
640+ // TODO: verify the height.
641+ });
642+ }
643+
644+
507645 private:
508646 AVLNode *root;
509647 };
--- common/sdk/OSUtils.memheap.h (revision 96)
+++ common/sdk/OSUtils.memheap.h (revision 97)
@@ -25,7 +25,7 @@
2525
2626 // Heap allocator class that provides sized memory chunks from OS-provided virtual memory.
2727 // Version 2.
28-// * now using RVL trees in free-bytes lists to optimize allocation performance
28+// * now using AVL trees in free-bytes lists to optimize allocation performance
2929 struct NativeHeapAllocator
3030 {
3131 // Allocations are made on virtual memory islands that bundle many together. Each vmem island
--- unittests/src/avltree.cpp (revision 96)
+++ unittests/src/avltree.cpp (revision 97)
@@ -17,6 +17,31 @@
1717 }
1818 };
1919
20+static void check_avl_sort( AVLTree <IntegerItem>& tree )
21+{
22+ bool hadLastValue = false;
23+ int last_int;
24+
25+ tree.Walk(
26+ [&]( AVLNode *node )
27+ {
28+ IntegerItem *curItem = AVL_GETITEM( IntegerItem, node, node );
29+
30+ if ( !hadLastValue )
31+ {
32+ last_int = curItem->my_number;
33+ }
34+ else
35+ {
36+ assert( last_int < curItem->my_number );
37+
38+ last_int = curItem->my_number;
39+ }
40+
41+ hadLastValue = true;
42+ });
43+}
44+
2045 void AVLTREE_TESTS( void )
2146 {
2247 printf( "testing simple AVLTree number sort..." );
@@ -23,7 +48,7 @@
2348 {
2449 AVLTree <IntegerItem> tree;
2550
26- static const int my_nums[] = { 43, 12, 74, 4235, 7856, 1232, 44, 623, 754 };
51+ static const int my_nums[] = { 43, 12, 74, 4235, 7856, 1232, 44, 623, 754, 4, 1, 7, 42, 482, 111, 321, 0, 88, 3 };
2752
2853 constexpr size_t num_ints = countof(my_nums);
2954
@@ -35,45 +60,70 @@
3560
3661 curItem.my_number = my_nums[n];
3762
38- tree.Insert( &curItem.node );
63+ bool didInsert = tree.Insert( &curItem.node );
64+
65+ assert( didInsert == true );
66+
67+ tree.Validate();
3968 }
4069
4170 // Check that items are sorted
42- auto check_sort = [&]( void )
71+ check_avl_sort( tree );
72+
73+ // Remove all items again.
74+ for ( IntegerItem& curItem : int_items )
4375 {
44- bool hadLastValue = false;
45- int last_int;
76+ tree.RemoveByNodeFast( &curItem.node );
4677
78+ check_avl_sort( tree );
79+
80+ tree.Validate();
81+ }
82+ }
83+ printf( "ok.\n" );
84+
85+ printf( "testing massive AVL tree insert..." );
86+ {
87+ AVLTree <IntegerItem> tree;
88+
89+ static constexpr size_t NUM_ITEMS_TO_INSERT = 1000000;
90+
91+ IntegerItem *items = new IntegerItem[ NUM_ITEMS_TO_INSERT ];
92+
93+ for ( size_t n = 0; n < NUM_ITEMS_TO_INSERT; n++ )
94+ {
95+ IntegerItem& my_item = items[n];
96+
97+ my_item.my_number = (int)n;
98+
99+ bool didInsert = tree.Insert( &my_item.node );
100+
101+ assert( didInsert == true );
102+ }
103+
104+ size_t curHeight = tree.GetTreeHeight();
105+
106+ assert( curHeight < std::log2( NUM_ITEMS_TO_INSERT ) * 2 );
107+
108+ // Check sort, hard.
109+ {
110+ size_t lastnum = 0;
111+
47112 tree.Walk(
48113 [&]( AVLNode *node )
49114 {
50- IntegerItem *curItem = AVL_GETITEM( IntegerItem, node, node );
115+ IntegerItem *intItem = AVL_GETITEM( IntegerItem, node, node );
51116
52- if ( !hadLastValue )
53- {
54- last_int = curItem->my_number;
55- }
56- else
57- {
58- assert( last_int < curItem->my_number );
117+ assert( intItem->my_number == (int)lastnum );
59118
60- last_int = curItem->my_number;
61- }
62-
63- hadLastValue = true;
119+ lastnum++;
64120 });
65- };
66- check_sort();
67121
68- // Remove all items again.
69- for ( IntegerItem& curItem : int_items )
70- {
71- bool gotToRemove = tree.RemoveByNode( &curItem.node );
122+ assert( lastnum == NUM_ITEMS_TO_INSERT );
123+ }
72124
73- assert( gotToRemove == true );
74-
75- check_sort();
76- }
125+ // Should be okay to just free this thing.
126+ delete [] items;
77127 }
78128 printf( "ok.\n" );
79129 }
\ No newline at end of file
Show on old repository browser