• R/O
  • SSH
  • HTTPS

eirrepo: Commit


Commit MetaInfo

Revision94 (tree)
Time2018-05-11 03:27:45
Authorquiret

Log Message

- added AVL tree implementation using dispatchable nodes (AVLTree.h with AVLTree and AVLNode classes)
- added AVLTree unit tests
- preparing to use AVLTree inside of NativePageAllocator

Change Summary

Incremental Difference

--- common/sdk/OSUtils.memheap.h (revision 93)
+++ common/sdk/OSUtils.memheap.h (revision 94)
@@ -24,6 +24,8 @@
2424 }
2525
2626 // Heap allocator class that provides sized memory chunks from OS-provided virtual memory.
27+// Version 2.
28+// * now using RVL trees in free-bytes lists to optimize allocation performance
2729 struct NativeHeapAllocator
2830 {
2931 // Allocations are made on virtual memory islands that bundle many together. Each vmem island
--- common/sdk/AVLTree.h (revision 0)
+++ common/sdk/AVLTree.h (revision 94)
@@ -0,0 +1,499 @@
1+/*****************************************************************************
2+*
3+* PROJECT: Multi Theft Auto v1.2
4+* LICENSE: See LICENSE in the top level directory
5+* FILE: Shared/core/OSUtils.avltree.h
6+* PURPOSE: AVL-tree implementation for the native heap allocator
7+*
8+* Multi Theft Auto is available from http://www.multitheftauto.com/
9+*
10+*****************************************************************************/
11+
12+#ifndef _AVL_TREE_IMPLEMENTATION_
13+#define _AVL_TREE_IMPLEMENTATION_
14+
15+#include <sdk/MacroUtils.h>
16+#include <assert.h>
17+#include <algorithm>
18+
19+// AVL tree is a sorted data structure that guarantees logarithmic-in-size add and
20+// remove operations while keeping item order intact. We realized that we needed
21+// this struct because the NativeHeapAllocator is being issued with random memory
22+// request sizes and we ought to decide fast in which free slot allocation might be
23+// possible.
24+// YOU CANNOT STORE SAME VALUES IN AN AVL TREE!
25+
26+#define AVL_GETITEM( type, nodePtr, nodeMemb ) ( (type*)( (char*)nodePtr - offsetof(type, nodeMemb) ) )
27+
28+// Has to be less-than comparable, in a total order.
29+struct AVLNode
30+{
31+ size_t height;
32+ AVLNode *parent;
33+ AVLNode *left, *right;
34+};
35+
36+template <typename dispatcherType>
37+struct AVLTree
38+{
39+private:
40+ static AINLINE bool is_node_less_than( const AVLNode *node, const AVLNode *compareWith )
41+ {
42+ return dispatcherType::IsNodeLessThan( node, compareWith );
43+ }
44+
45+public:
46+ inline AVLTree( void )
47+ {
48+ this->root = nullptr;
49+ }
50+
51+ inline ~AVLTree( void )
52+ {
53+ // Cleanup is done by all the systems that created node memory themselves.
54+ // We do never allocate memory in this data structure anyway.
55+ return;
56+ }
57+
58+private:
59+ AINLINE size_t height_func( size_t leftHeight, size_t rightHeight )
60+ {
61+ return std::max( leftHeight, rightHeight );
62+ }
63+
64+ AINLINE size_t calc_height_of_node( AVLNode *firstNode, AVLNode *secondNode )
65+ {
66+ if ( firstNode == nullptr && secondNode == nullptr )
67+ {
68+ return 0;
69+ }
70+
71+ size_t height_of_nodes_underneath;
72+
73+ if ( firstNode == nullptr )
74+ {
75+ height_of_nodes_underneath = secondNode->height;
76+ }
77+ else if ( secondNode == nullptr )
78+ {
79+ height_of_nodes_underneath = firstNode->height;
80+ }
81+ else
82+ {
83+ height_of_nodes_underneath = height_func( firstNode->height, secondNode->height );
84+ }
85+
86+ return ( 1 + height_of_nodes_underneath );
87+ }
88+
89+ AINLINE void rotate( AVLNode *node, AVLNode *moveToUsNeighbor, bool leftTrueRightFalse )
90+ {
91+ // Both node and moveToUsNeighbor must not be nullptr.
92+ assert( node != nullptr );
93+ assert( moveToUsNeighbor != nullptr );
94+
95+ // Set the new direct node which would be empty if the tree performed rotation.
96+ AVLNode *newDirectNodeChild;
97+ AVLNode *otherDirectChild;
98+ AVLNode *tuggedWithNode;
99+
100+ if ( leftTrueRightFalse )
101+ {
102+ assert( node->right == moveToUsNeighbor );
103+
104+ // If we move to the left, then the left subtree of our right child is bigger than us,
105+ // thus is becomes our right subtree.
106+
107+ newDirectNodeChild = moveToUsNeighbor->left;
108+
109+ node->right = newDirectNodeChild;
110+
111+ // Do not forget to update the direct relationship!
112+ moveToUsNeighbor->left = node;
113+
114+ otherDirectChild = node->left;
115+
116+ tuggedWithNode = moveToUsNeighbor->right;
117+ }
118+ else
119+ {
120+ assert( node->left == moveToUsNeighbor );
121+
122+ newDirectNodeChild = moveToUsNeighbor->right;
123+
124+ node->left = newDirectNodeChild;
125+
126+ moveToUsNeighbor->right = node;
127+
128+ otherDirectChild = node->right;
129+
130+ tuggedWithNode = moveToUsNeighbor->left;
131+ }
132+
133+ // Update the parents.
134+ if ( newDirectNodeChild != nullptr )
135+ {
136+ newDirectNodeChild->parent = node;
137+ }
138+
139+ AVLNode *prevParentOfMainNode = node->parent;
140+
141+ moveToUsNeighbor->parent = prevParentOfMainNode;
142+
143+ // Is it the new root?
144+ if ( prevParentOfMainNode == nullptr )
145+ {
146+ assert( node == this->root );
147+
148+ this->root = moveToUsNeighbor;
149+ }
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 );
157+
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+
173+ node->parent = moveToUsNeighbor;
174+
175+ // Need to update node heights.
176+ size_t subHeight = calc_height_of_node( newDirectNodeChild, otherDirectChild );
177+
178+ node->height = subHeight;
179+
180+ size_t fullHeight = 1;
181+
182+ if ( tuggedWithNode == nullptr )
183+ {
184+ fullHeight += subHeight;
185+ }
186+ else
187+ {
188+ fullHeight += height_func( subHeight, tuggedWithNode->height );
189+ }
190+
191+ moveToUsNeighbor->height = fullHeight;
192+ }
193+
194+ AINLINE bool detect_tree_two_imbalance( AVLNode *maybeBigger, AVLNode *maybeSmaller )
195+ {
196+ if ( maybeBigger == nullptr )
197+ {
198+ return false;
199+ }
200+
201+ size_t maybeBiggerHeight = maybeBigger->height;
202+
203+ if ( maybeSmaller == nullptr )
204+ {
205+ return ( maybeBiggerHeight > 0 );
206+ }
207+
208+ size_t maybeSmallerHeight = maybeSmaller->height;
209+
210+ return ( maybeBiggerHeight > ( 1 + maybeSmallerHeight ) );
211+ }
212+
213+ AINLINE bool detect_tree_one_imbalance( AVLNode *maybeSmaller, AVLNode *maybeBigger )
214+ {
215+ if ( maybeBigger == nullptr )
216+ {
217+ return false;
218+ }
219+ if ( maybeSmaller == nullptr )
220+ {
221+ return true;
222+ }
223+
224+ return ( maybeSmaller->height < maybeBigger->height );
225+ }
226+
227+ AINLINE void balance( AVLNode *node )
228+ {
229+ AVLNode *leftNode = node->left;
230+ AVLNode *rightNode = node->right;
231+
232+ if ( leftNode != nullptr && detect_tree_two_imbalance( leftNode, rightNode ) )
233+ {
234+ AVLNode *rightNodeOfLeftNode = leftNode->right;
235+
236+ if ( rightNodeOfLeftNode != nullptr && detect_tree_one_imbalance( leftNode->left, rightNodeOfLeftNode ) )
237+ {
238+ rotate( leftNode, rightNodeOfLeftNode, true );
239+
240+ leftNode = rightNodeOfLeftNode;
241+ }
242+
243+ rotate( node, leftNode, false );
244+ }
245+ else if ( rightNode != nullptr && detect_tree_two_imbalance( rightNode, leftNode ) )
246+ {
247+ AVLNode *leftNodeOfRightNode = rightNode->left;
248+
249+ if ( leftNodeOfRightNode != nullptr && detect_tree_one_imbalance( rightNode->right, leftNodeOfRightNode ) )
250+ {
251+ rotate( rightNode, leftNodeOfRightNode, false );
252+
253+ rightNode = leftNodeOfRightNode;
254+ }
255+
256+ rotate( node, rightNode, true );
257+ }
258+ }
259+
260+ AINLINE AVLNode* ScanForNodePosition( AVLNode *node, AVLNode**& iterPtrOut, AVLNode*& parentOut )
261+ {
262+ // Find the position to insert our new node at.
263+ AVLNode *parent = nullptr;
264+ AVLNode **iterPtr = &this->root;
265+ AVLNode *iter = *iterPtr;
266+
267+ while ( true )
268+ {
269+ if ( iter == nullptr )
270+ {
271+ // Quit because we hit rock bottom.
272+ break;
273+ }
274+
275+ // Set a new parent.
276+ parent = iter;
277+
278+ // Check key condition.
279+ if ( is_node_less_than( node, iter ) )
280+ {
281+ iterPtr = &iter->left;
282+ iter = iter->left;
283+ }
284+ else if ( is_node_less_than( iter, node ) )
285+ {
286+ iterPtr = &iter->right;
287+ iter = iter->right;
288+ }
289+ else
290+ {
291+ // Quit because we found the node.
292+ break;
293+ }
294+ }
295+
296+ iterPtrOut = iterPtr;
297+ parentOut = parent;
298+ return iter;
299+ }
300+
301+public:
302+ inline bool Insert( AVLNode *node )
303+ {
304+ // Find the position to insert our new node at.
305+ AVLNode *parent;
306+ AVLNode **iterPtr;
307+ {
308+ AVLNode *iter = ScanForNodePosition( node, iterPtr, parent );
309+
310+ if ( iter != nullptr )
311+ {
312+ // We already have found a node, so quit.
313+ return false;
314+ }
315+ }
316+
317+ // Just put the node here.
318+ *iterPtr = node;
319+
320+ // Initialize the node properly.
321+ node->height = 0;
322+ node->left = nullptr;
323+ node->right = nullptr;
324+ node->parent = parent;
325+
326+ // Update to the very top.
327+ while ( parent != nullptr )
328+ {
329+ parent->height = calc_height_of_node( parent->left, parent->right );
330+
331+ balance( parent );
332+
333+ parent = parent->parent;
334+ }
335+
336+ return true;
337+ }
338+
339+private:
340+ static AINLINE AVLNode* FindMaxNode( AVLNode *searchFrom, AVLNode** &searchFromPtrInOut )
341+ {
342+ AVLNode *curMax = searchFrom;
343+ AVLNode **searchFromPtr = searchFromPtrInOut;
344+
345+ while ( true )
346+ {
347+ AVLNode *nextBigger = curMax->right;
348+
349+ if ( nextBigger == nullptr )
350+ {
351+ break;
352+ }
353+
354+ searchFromPtr = &curMax->right;
355+ curMax = nextBigger;
356+ }
357+
358+ searchFromPtrInOut = searchFromPtr;
359+ return curMax;
360+ }
361+
362+ AINLINE void remove_node( AVLNode *node, AVLNode **nodePtr, AVLNode *parent )
363+ {
364+ AVLNode *leftChild = node->left;
365+ AVLNode *rightChild = node->right;
366+
367+ if ( leftChild == nullptr )
368+ {
369+ *nodePtr = rightChild;
370+ }
371+ else if ( rightChild == nullptr )
372+ {
373+ *nodePtr = leftChild;
374+ }
375+ else
376+ {
377+ // Pretty complicated situation.
378+ AVLNode **closestReplacementPtr = &node->left;
379+ AVLNode *closestReplacement = FindMaxNode( leftChild, closestReplacementPtr );
380+
381+ // Remove the closest node.
382+ remove_node( closestReplacement, closestReplacementPtr, closestReplacement->parent );
383+
384+ // We need to update members because they could be out-of-date.
385+ parent = node->parent;
386+ leftChild = node->left;
387+ rightChild = node->right;
388+
389+ if ( parent )
390+ {
391+ if ( parent->left == node )
392+ {
393+ nodePtr = &parent->left;
394+ }
395+ else if ( parent->right == node )
396+ {
397+ nodePtr = &parent->right;
398+ }
399+ else
400+ {
401+ assert( 0 );
402+ }
403+ }
404+ else
405+ {
406+ nodePtr = &this->root;
407+ }
408+
409+ // Replace nodes.
410+ closestReplacement->parent = parent;
411+ closestReplacement->left = leftChild;
412+ closestReplacement->right = rightChild;
413+
414+ *nodePtr = closestReplacement;
415+
416+ // Update parents.
417+ if ( leftChild != nullptr )
418+ {
419+ leftChild->parent = closestReplacement;
420+ }
421+
422+ if ( rightChild != nullptr )
423+ {
424+ rightChild->parent = closestReplacement;
425+ }
426+ }
427+
428+ // Update height of the changed tree.
429+ while ( parent != nullptr )
430+ {
431+ parent->height = calc_height_of_node( parent->left, parent->right );
432+
433+ balance( parent );
434+
435+ parent = parent->parent;
436+ }
437+ }
438+
439+public:
440+ inline bool RemoveByNode( AVLNode *node )
441+ {
442+ // Find the node we are talking about.
443+ // This is basically just verification that the node is inside this tree, meow.
444+ // We could create another function that just assumes the node really inside.
445+ AVLNode *parent;
446+ AVLNode **iterPtr;
447+ {
448+ AVLNode *iter = ScanForNodePosition( node, iterPtr, parent );
449+
450+ if ( iter == nullptr )
451+ {
452+ // We could not find the node, so quit.
453+ return false;
454+ }
455+
456+ if ( node != iter )
457+ {
458+ // It is not the same node!
459+ return false;
460+ }
461+ }
462+
463+ remove_node( node, iterPtr, parent );
464+
465+ return true;
466+ }
467+
468+private:
469+ template <typename callbackType>
470+ void walk_recursively( AVLNode *walkNode, const callbackType& cb )
471+ {
472+ if ( AVLNode *leftChild = walkNode->left )
473+ {
474+ walk_recursively( leftChild, cb );
475+ }
476+
477+ cb( walkNode );
478+
479+ if ( AVLNode *rightChild = walkNode->right )
480+ {
481+ walk_recursively( rightChild, cb );
482+ }
483+ }
484+
485+public:
486+ template <typename callbackType>
487+ inline void Walk( const callbackType& cb )
488+ {
489+ if ( AVLNode *rootNode = this->root )
490+ {
491+ walk_recursively( rootNode, cb );
492+ }
493+ }
494+
495+private:
496+ AVLNode *root;
497+};
498+
499+#endif //_AVL_TREE_IMPLEMENTATION_
\ No newline at end of file
--- unittests/src/avltree.cpp (revision 0)
+++ unittests/src/avltree.cpp (revision 94)
@@ -0,0 +1,79 @@
1+// AVL tree unittest file.
2+// We want to make sure that this thing properly sorts numbers.
3+
4+#include <sdk/AVLTree.h>
5+
6+struct IntegerItem
7+{
8+ int my_number;
9+ AVLNode node;
10+
11+ static AINLINE bool IsNodeLessThan( const AVLNode *left, const AVLNode *right )
12+ {
13+ IntegerItem *leftItem = AVL_GETITEM( IntegerItem, left, node );
14+ IntegerItem *rightItem = AVL_GETITEM( IntegerItem, right, node );
15+
16+ return ( leftItem->my_number < rightItem->my_number );
17+ }
18+};
19+
20+void AVLTREE_TESTS( void )
21+{
22+ printf( "testing simple AVLTree number sort..." );
23+ {
24+ AVLTree <IntegerItem> tree;
25+
26+ static const int my_nums[] = { 43, 12, 74, 4235, 7856, 1232, 44, 623, 754 };
27+
28+ constexpr size_t num_ints = countof(my_nums);
29+
30+ IntegerItem int_items[ num_ints ];
31+
32+ for ( size_t n = 0; n < num_ints; n++ )
33+ {
34+ IntegerItem& curItem = int_items[n];
35+
36+ curItem.my_number = my_nums[n];
37+
38+ tree.Insert( &curItem.node );
39+ }
40+
41+ // Check that items are sorted
42+ auto check_sort = [&]( void )
43+ {
44+ bool hadLastValue = false;
45+ int last_int;
46+
47+ tree.Walk(
48+ [&]( AVLNode *node )
49+ {
50+ IntegerItem *curItem = AVL_GETITEM( IntegerItem, node, node );
51+
52+ if ( !hadLastValue )
53+ {
54+ last_int = curItem->my_number;
55+ }
56+ else
57+ {
58+ assert( last_int < curItem->my_number );
59+
60+ last_int = curItem->my_number;
61+ }
62+
63+ hadLastValue = true;
64+ });
65+ };
66+ check_sort();
67+
68+ // Remove all items again.
69+ for ( IntegerItem& curItem : int_items )
70+ {
71+ bool gotToRemove = tree.RemoveByNode( &curItem.node );
72+
73+ assert( gotToRemove == true );
74+
75+ check_sort();
76+ }
77+ }
78+ printf( "OK.\n" );
79+}
\ No newline at end of file
--- unittests/src/main.cpp (revision 93)
+++ unittests/src/main.cpp (revision 94)
@@ -10,6 +10,7 @@
1010 extern void MEM_TESTS( void );
1111 extern void HEAP_TESTS( void );
1212 extern void DTS_TESTS( void );
13+extern void AVLTREE_TESTS( void );
1314
1415 #ifdef _WIN32
1516 // Shell extension test.
@@ -24,6 +25,7 @@
2425 MEM_TESTS();
2526 HEAP_TESTS();
2627 DTS_TESTS();
28+ AVLTREE_TESTS();
2729
2830 //Test_DTSConditionalStructing();
2931
Show on old repository browser