• R/O
  • SSH
  • HTTPS

eirrepo: Commit


Commit MetaInfo

Revision119 (tree)
Time2018-09-08 05:49:34
Authorquiret

Log Message

- implemented assignment operators for AVLTree
- fleshed out the Map object
- fixed a bug in the native heap allocator where the free region that was growing was not updated in the AVL tree (we could optimize this in the future)
- added more Map unit tests

Change Summary

Incremental Difference

--- common/sdk/AVLTree.h (revision 118)
+++ common/sdk/AVLTree.h (revision 119)
@@ -73,6 +73,14 @@
7373 this->root = nullptr;
7474 }
7575
76+ inline AVLTree( const AVLTree& right ) = delete;
77+ inline AVLTree( AVLTree&& right )
78+ {
79+ this->root = right.root;
80+
81+ right.root = nullptr;
82+ }
83+
7684 inline ~AVLTree( void )
7785 {
7886 // Cleanup is done by all the systems that created node memory themselves.
@@ -80,6 +88,16 @@
8088 return;
8189 }
8290
91+ inline AVLTree& operator = ( const AVLTree& right ) = delete;
92+ inline AVLTree& operator = ( AVLTree&& right )
93+ {
94+ this->root = right.root;
95+
96+ right.root = nullptr;
97+
98+ return *this;
99+ }
100+
83101 private:
84102 static AINLINE size_t height_func( size_t leftHeight, size_t rightHeight )
85103 {
--- common/sdk/OSUtils.memheap.h (revision 118)
+++ common/sdk/OSUtils.memheap.h (revision 119)
@@ -634,9 +634,17 @@
634634
635635 if ( growSuccess )
636636 {
637+ if ( lastFreeBlock->freeRegion.IsEmpty() == false )
638+ {
639+ this->avlSortedBySize.RemoveByNodeFast( &lastFreeBlock->sortedBySizeNode );
640+ }
641+
637642 // Grow the available free space.
638643 lastFreeBlock->freeRegion.SetSliceEndPoint( finalMemEndOffset );
639644
645+ // Since we have grown we must have some space now.
646+ this->avlSortedBySize.Insert( &lastFreeBlock->sortedBySizeNode );
647+
640648 // Just return the new spot.
641649 // We will insert to the end node.
642650 allocPtr = (void*)tryNewMemOffset;
--- common/sdk/Map.h (revision 118)
+++ common/sdk/Map.h (revision 119)
@@ -142,7 +142,7 @@
142142 return newNode;
143143 }
144144
145- static AINLINE MapAVLTree clone_key_tree( MapAVLTree& right )
145+ static AINLINE MapAVLTree clone_key_tree( void *objMem, MapAVLTree& right )
146146 {
147147 // We know that there cannot be two-same-value nodes, so we skip checking nodestacks.
148148 MapAVLTree newTree;
@@ -155,7 +155,7 @@
155155 {
156156 Node *rightNode = AVL_GETITEM( Node, iter.Resolve(), sortedByKeyNode );
157157
158- NewNode( this, newTree, rightNode->key, rightNode->value );
158+ NewNode( objMem, newTree, rightNode->key, rightNode->value );
159159
160160 iter.Increment();
161161 }
@@ -163,7 +163,7 @@
163163 catch( ... )
164164 {
165165 // Have to release all items again because one of them did not cooperate.
166- release_nodes( this, newTree );
166+ release_nodes( objMem, newTree );
167167
168168 throw;
169169 }
@@ -193,7 +193,7 @@
193193 inline Map& operator = ( const Map& right )
194194 {
195195 // Clone the thing.
196- MapAVLTree newTree = clone_key_tree( right );
196+ MapAVLTree newTree = clone_key_tree( this, right.avlKeyTree );
197197
198198 // Release the old.
199199 release_nodes( this, this->avlKeyTree );
@@ -230,10 +230,26 @@
230230 NewNode( this, this->avlKeyTree, key, std::move( value ) );
231231 }
232232
233+ // Erases any Node by key.
234+ inline void RemoveByKey( const keyType& key )
235+ {
236+ AVLNode *avlExistingNode = this->avlKeyTree.FindNode( key );
237+
238+ if ( avlExistingNode == nullptr )
239+ return;
240+
241+ // Remove it.
242+ this->avlKeyTree.RemoveByNodeFast( avlExistingNode );
243+
244+ Node *existingNode = AVL_GETITEM( Node, avlExistingNode, sortedByKeyNode );
245+
246+ dismantle_node( this, existingNode );
247+ }
248+
233249 // Clears all keys and values from this Map.
234250 inline void Clear( void )
235251 {
236- this->release_nodes();
252+ release_nodes( this, this->avlKeyTree );
237253 }
238254
239255 // Returns the amount of keys/values inside this Map.
@@ -300,6 +316,53 @@
300316 return NewNode( this, this->avlKeyTree, key, valueType() )->value;
301317 }
302318
319+ inline bool operator == ( const Map& right ) const
320+ {
321+ MapAVLTree::diff_node_iterator left_iter( this->avlKeyTree );
322+ MapAVLTree::diff_node_iterator right_iter( right.avlKeyTree );
323+
324+ while ( true )
325+ {
326+ bool isLeftEnd = left_iter.IsEnd();
327+ bool isRightEnd = right_iter.IsEnd();
328+
329+ if ( isLeftEnd && isRightEnd )
330+ {
331+ return true;
332+ }
333+ else if ( isLeftEnd || isRightEnd )
334+ {
335+ return false;
336+ }
337+
338+ // If any key is different then we do not match.
339+ const Node *leftNode = AVL_GETITEM( Node, left_iter.Resolve(), sortedByKeyNode );
340+ const Node *rightNode = AVL_GETITEM( Node, right_iter.Resolve(), sortedByKeyNode );
341+
342+ if ( leftNode->GetKey() != rightNode->GetKey() )
343+ {
344+ return false;
345+ }
346+
347+ // If any value is different then we do not match.
348+ if ( leftNode->GetValue() != rightNode->GetValue() )
349+ {
350+ return false;
351+ }
352+
353+ left_iter.Increment();
354+ right_iter.Increment();
355+ }
356+
357+ // Never reaches this point.
358+ return false;
359+ }
360+
361+ inline bool operator != ( const Map& right ) const
362+ {
363+ return !( operator == ( right ) );
364+ }
365+
303366 private:
304367 mutable MapAVLTree avlKeyTree;
305368 };
--- unittests/src/map.cpp (revision 118)
+++ unittests/src/map.cpp (revision 119)
@@ -33,4 +33,122 @@
3333 assert( map[1] == 9001 );
3434 }
3535 printf( "ok.\n" );
36+
37+ printf( "testing map item removal..." );
38+ {
39+ MapWithHeap map;
40+
41+ map[-30] = 45;
42+
43+ assert( map.Find( -30 ) != nullptr );
44+ assert( map[-30] == 45 );
45+
46+ map.RemoveByKey( -30 );
47+
48+ assert( map.Find( -30 ) == nullptr );
49+ assert( map[-30] == int() );
50+ }
51+ printf( "ok.\n" );
52+
53+ printf( "testing map node walking..." );
54+ {
55+ MapWithHeap map;
56+
57+ int keys[] = { 66, 31, 691, 5230582, -77 };
58+
59+ for ( int key : keys )
60+ {
61+ map[ key ] = key;
62+ }
63+
64+ assert( map.GetKeyValueCount() == 5 );
65+
66+ int lastKey;
67+ bool hasLastKey = false;
68+
69+ map.WalkNodes(
70+ [&]( const MapWithHeap::Node *theNode )
71+ {
72+ if ( !hasLastKey )
73+ {
74+ lastKey = theNode->GetKey();
75+
76+ hasLastKey = true;
77+ }
78+ else
79+ {
80+ assert( lastKey < theNode->GetKey() );
81+
82+ lastKey = theNode->GetKey();
83+ }
84+ });
85+ }
86+ printf( "ok.\n" );
87+
88+ printf( "testing map clear..." );
89+ {
90+ MapWithHeap map;
91+
92+ map[ 66 ] = 33;
93+ map[ 0 ] = 1;
94+
95+ assert( map.GetKeyValueCount() == 2 );
96+
97+ map.Clear();
98+
99+ assert( map.GetKeyValueCount() == 0 );
100+ }
101+ printf( "ok.\n" );
102+
103+ printf( "testing map clone..." );
104+ {
105+ MapWithHeap map1, map2;
106+
107+ map1[ 1 ] = 2;
108+ map1[ 73 ] = 32;
109+
110+ map2 = map1;
111+
112+ assert( map2[ 1 ] == 2 );
113+ assert( map2[ 73 ] == 32 );
114+ }
115+ printf( "ok.\n" );
116+
117+ printf( "testing map move..." );
118+ {
119+ MapWithHeap map1, map2;
120+
121+ map1[ 59 ] = 44;
122+
123+ assert( map1.Find( 59 ) != nullptr );
124+
125+ map2 = std::move( map1 );
126+
127+ assert( map1.Find( 59 ) == nullptr );
128+ assert( map2.Find( 59 ) != nullptr );
129+ assert( map2[ 59 ] == 44 );
130+ }
131+ printf( "ok.\n" );
132+
133+ printf( "testing map comparator..." );
134+ {
135+ MapWithHeap map1, map2;
136+
137+ assert( map1 == map1 );
138+ assert( map1 == map2 );
139+
140+ map1[ 44 ] = 22;
141+ map2[ 44 ] = 21;
142+
143+ assert( map1 != map2 );
144+
145+ map1[ 44 ] = map2[ 44 ];
146+
147+ assert( map1 == map2 );
148+
149+ map1[ 23 ] = -1;
150+
151+ assert( map1 != map2 );
152+ }
153+ printf( "ok.\n" );
36154 }
\ No newline at end of file
Show on old repository browser