• R/O
  • SSH
  • HTTPS

eirrepo: Commit


Commit MetaInfo

Revision118 (tree)
Time2018-09-07 06:52:46
Authorquiret

Log Message

- added eir::Map object for sorted key-value pair management
- added more helpers to AVLTree
- improved the eir::Vector class, added comparator functionality
- added first unit tests for Map object

Change Summary

Incremental Difference

--- common/sdk/AVLTree.h (revision 117)
+++ common/sdk/AVLTree.h (revision 118)
@@ -883,6 +883,12 @@
883883 return curNode;
884884 }
885885
886+ // Returns the node at the top of the tree.
887+ inline AVLNode* GetRootNode( void )
888+ {
889+ return this->root;
890+ }
891+
886892 // Returns the node whose value is just above or equal to the given value.
887893 template <typename valueType>
888894 inline AVLNode* GetJustAboveOrEqualNode( const valueType& theValue )
@@ -915,6 +921,60 @@
915921 return closestAboveNode;
916922 }
917923
924+ // Returns the node that matches the given value.
925+ template <typename valueType>
926+ inline AVLNode* FindNode( const valueType& value )
927+ {
928+ AVLNode *curNode = this->root;
929+
930+ while ( curNode )
931+ {
932+ // Check which one to go for next.
933+ if ( dispatcherType::IsNodeLessThanValue( curNode, value ) )
934+ {
935+ curNode = curNode->right;
936+ }
937+ else if ( dispatcherType::IsNodeGreaterThanValue( curNode, value ) )
938+ {
939+ curNode = curNode->left;
940+ }
941+ else
942+ {
943+ // We found it.
944+ break;
945+ }
946+ }
947+
948+ return curNode;
949+ }
950+
951+ // Returns the node that matches the given value, const-equivalent.
952+ template <typename valueType>
953+ inline const AVLNode* FindNode( const valueType& value ) const
954+ {
955+ const AVLNode *curNode = this->root;
956+
957+ while ( curNode )
958+ {
959+ // Check which one to go for next.
960+ if ( dispatcherType::IsNodeLessThanValue( curNode, value ) )
961+ {
962+ curNode = curNode->right;
963+ }
964+ else if ( dispatcherType::IsNodeGreaterThanValue( curNode, value ) )
965+ {
966+ curNode = curNode->left;
967+ }
968+ else
969+ {
970+ // We found it.
971+ break;
972+ }
973+ }
974+
975+ return curNode;
976+ }
977+
918978 // Should always succeed.
919979 inline void Validate( void )
920980 {
--- common/sdk/Map.h (revision 117)
+++ common/sdk/Map.h (revision 118)
@@ -19,12 +19,291 @@
1919
2020 #include "eirutils.h"
2121 #include "MacroUtils.h"
22+#include "AVLTree.h"
2223
2324 namespace eir
2425 {
2526
26-// TODO.
27+template <typename keyType, typename valueType, typename allocatorType>
28+struct Map
29+{
30+ // Node inside this Map.
31+ struct Node
32+ {
33+ friend struct Map <keyType, valueType, allocatorType>;
2734
35+ // Get rid of the default things.
36+ inline Node( const Node& right ) = delete;
37+ inline Node( Node&& right ) = delete;
38+
39+ inline Node& operator = ( const Node& ) = delete;
40+ inline Node& operator = ( Node&& right ) = delete;
41+
42+ // The public access stuff.
43+ inline const keyType& GetKey( void ) const
44+ {
45+ return this->key;
46+ }
47+
48+ inline valueType& GetValue( void )
49+ {
50+ return this->value;
51+ }
52+
53+ inline const valueType& GetValue( void ) const
54+ {
55+ return this->value;
56+ }
57+
58+ private:
59+ // Not available to things that just use Map.
60+ // But the friend class does have access.
61+ inline Node( keyType key, valueType value )
62+ : key( std::move( key ) ), value( std::move( value ) )
63+ {
64+ return;
65+ }
66+ inline ~Node( void ) = default;
67+
68+ keyType key;
69+ valueType value;
70+
71+ AVLNode sortedByKeyNode;
72+ };
73+
74+ inline Map( void )
75+ {
76+ // Really nothing to do, I swear!
77+ return;
78+ }
79+
80+private:
81+ struct avlKeyNodeDispatcher
82+ {
83+ static inline bool IsNodeLessThan( const AVLNode *left, const AVLNode *right )
84+ {
85+ const Node *leftNode = AVL_GETITEM( Node, left, sortedByKeyNode );
86+ const Node *rightNode = AVL_GETITEM( Node, right, sortedByKeyNode );
87+
88+ return ( leftNode->key < rightNode->key );
89+ }
90+
91+ static inline bool IsNodeLessThanValue( const AVLNode *left, const keyType& right )
92+ {
93+ const Node *leftNode = AVL_GETITEM( Node, left, sortedByKeyNode );
94+
95+ return ( leftNode->key < right );
96+ }
97+
98+ static inline bool IsNodeGreaterThanValue( const AVLNode *left, const keyType& right )
99+ {
100+ const Node *leftNode = AVL_GETITEM( Node, left, sortedByKeyNode );
101+
102+ return ( leftNode->key > right );
103+ }
104+ };
105+
106+ typedef AVLTree <avlKeyNodeDispatcher> MapAVLTree;
107+
108+ static AINLINE void dismantle_node( void *objMem, Node *theNode )
109+ {
110+ theNode->~Node();
111+
112+ allocatorType::Free( objMem, theNode );
113+ }
114+
115+ static AINLINE void release_nodes( void *objMem, MapAVLTree& workTree )
116+ {
117+ // Clear all allocated Nodes.
118+ while ( AVLNode *avlSomeNode = workTree.GetRootNode() )
119+ {
120+ Node *someNode = AVL_GETITEM( Node, avlSomeNode, sortedByKeyNode );
121+
122+ workTree.RemoveByNodeFast( avlSomeNode );
123+
124+ dismantle_node( objMem, someNode );
125+ }
126+ }
127+
128+ static AINLINE Node* NewNode( void *objMem, MapAVLTree& workTree, keyType key, valueType value )
129+ {
130+ void *newNodeMem = allocatorType::Allocate( objMem, sizeof(Node), alignof(Node) );
131+
132+ if ( newNodeMem == nullptr )
133+ {
134+ throw eir_exception();
135+ }
136+
137+ Node *newNode = new (newNodeMem) Node( std::move( key ), std::move( value ) );
138+
139+ // Link this node into our system.
140+ workTree.Insert( &newNode->sortedByKeyNode );
141+
142+ return newNode;
143+ }
144+
145+ static AINLINE MapAVLTree clone_key_tree( MapAVLTree& right )
146+ {
147+ // We know that there cannot be two-same-value nodes, so we skip checking nodestacks.
148+ MapAVLTree newTree;
149+
150+ MapAVLTree::diff_node_iterator iter( right );
151+
152+ try
153+ {
154+ while ( !iter.IsEnd() )
155+ {
156+ Node *rightNode = AVL_GETITEM( Node, iter.Resolve(), sortedByKeyNode );
157+
158+ NewNode( this, newTree, rightNode->key, rightNode->value );
159+
160+ iter.Increment();
161+ }
162+ }
163+ catch( ... )
164+ {
165+ // Have to release all items again because one of them did not cooperate.
166+ release_nodes( this, newTree );
167+
168+ throw;
169+ }
170+
171+ return newTree;
172+ }
173+
174+public:
175+ inline Map( const Map& right )
176+ : avlKeyTree( clone_key_tree( right.avlKeyTree ) )
177+ {
178+ return;
179+ }
180+
181+ // WARNING: only move-construct if you know that allocatorType matches in both objects.
182+ inline Map( Map&& right )
183+ : avlKeyTree( std::move( right.avlKeyTree ) )
184+ {
185+ return;
186+ }
187+
188+ inline ~Map( void )
189+ {
190+ release_nodes( this, this->avlKeyTree );
191+ }
192+
193+ inline Map& operator = ( const Map& right )
194+ {
195+ // Clone the thing.
196+ MapAVLTree newTree = clone_key_tree( right );
197+
198+ // Release the old.
199+ release_nodes( this, this->avlKeyTree );
200+
201+ this->avlKeyTree = std::move( newTree );
202+
203+ return *this;
204+ }
205+
206+ // WARNING: only move if allocatorType points to the same data-repository in both objects!
207+ inline Map& operator = ( Map&& right )
208+ {
209+ this->avlKeyTree = std::move( right.avlKeyTree );
210+
211+ return *this;
212+ }
213+
214+ // *** Management methods.
215+
216+ // Sets a new value to the tree.
217+ // Overrides any Node that previously existed.
218+ inline void Set( const keyType& key, valueType value )
219+ {
220+ // Check if such a node exists.
221+ if ( AVLNode *avlExistingNode = this->avlKeyTree.FindNode( key ) )
222+ {
223+ Node *existingNode = AVL_GETITEM( Node, avlExistingNode, sortedByKeyNode );
224+
225+ existingNode->value = std::move( value );
226+ return;
227+ }
228+
229+ // We must create a new node.
230+ NewNode( this, this->avlKeyTree, key, std::move( value ) );
231+ }
232+
233+ // Clears all keys and values from this Map.
234+ inline void Clear( void )
235+ {
236+ this->release_nodes();
237+ }
238+
239+ // Returns the amount of keys/values inside this Map.
240+ inline size_t GetKeyValueCount( void ) const
241+ {
242+ size_t count = 0;
243+
244+ MapAVLTree::diff_node_iterator iter( this->avlKeyTree );
245+
246+ while ( !iter.IsEnd() )
247+ {
248+ count++;
249+
250+ iter.Increment();
251+ }
252+
253+ return count;
254+ }
255+
256+ inline Node* Find( const keyType& key )
257+ {
258+ if ( AVLNode *avlExistingNode = this->avlKeyTree.FindNode( key ) )
259+ {
260+ return AVL_GETITEM( Node, avlExistingNode, sortedByKeyNode );
261+ }
262+
263+ return nullptr;
264+ }
265+
266+ inline const Node* Find( const keyType& key ) const
267+ {
268+ if ( const AVLNode *avlExistingNode = this->avlKeyTree.FindNode( key ) )
269+ {
270+ return AVL_GETITEM( const Node, avlExistingNode, sortedByKeyNode );
271+ }
272+
273+ return nullptr;
274+ }
275+
276+ // Walks through all nodes of this tree.
277+ template <typename callbackType>
278+ inline void WalkNodes( const callbackType& cb )
279+ {
280+ MapAVLTree::diff_node_iterator iter( this->avlKeyTree );
281+
282+ while ( !iter.IsEnd() )
283+ {
284+ Node *curNode = AVL_GETITEM( Node, iter.Resolve(), sortedByKeyNode );
285+
286+ cb( curNode );
287+
288+ iter.Increment();
289+ }
290+ }
291+
292+ // Nice helpers using operators.
293+ inline valueType& operator [] ( const keyType& key )
294+ {
295+ if ( Node *findNode = this->Find( key ) )
296+ {
297+ return findNode->value;
298+ }
299+
300+ return NewNode( this, this->avlKeyTree, key, valueType() )->value;
301+ }
302+
303+private:
304+ mutable MapAVLTree avlKeyTree;
305+};
306+
28307 }
29308
30309 #endif //_EIR_MAP_HEADER_
\ No newline at end of file
--- common/sdk/Vector.h (revision 117)
+++ common/sdk/Vector.h (revision 118)
@@ -269,11 +269,47 @@
269269 this->data_count = newCount;
270270 }
271271
272+ // Removes all items from this array by release the back-end memory.
273+ inline void Clear( void )
274+ {
275+ release_data( this, this->data_entries, this->data_count );
276+
277+ this->data_entries = nullptr;
278+ this->data_count = 0;
279+ }
280+
272281 inline size_t GetCount( void ) const
273282 {
274283 return this->data_count;
275284 }
276285
286+ // Walks all items of this object.
287+ template <typename callbackType>
288+ AINLINE void Walk( const callbackType& cb )
289+ {
290+ structType *data = this->data_entries;
291+ size_t num_data = this->data_count;
292+
293+ for ( size_t n = 0; n < num_data; n++ )
294+ {
295+ cb( n, data[ n ] );
296+ }
297+ }
298+
299+ // Walks all items of this object, constant.
300+ template <typename callbackType>
301+ AINLINE void Walk( const callbackType& cb ) const
302+ {
303+ const structType *data = this->data_entries;
304+ size_t num_data = this->data_count;
305+
306+ for ( size_t n = 0; n < num_data; n++ )
307+ {
308+ cb( n, data[ n ] );
309+ }
310+ }
311+
312+ // Indexing operators.
277313 inline structType& operator [] ( size_t idx )
278314 {
279315 if ( idx >= this->data_count )
@@ -318,6 +354,35 @@
318354 return this->data_entries[ curCount - 1 ];
319355 }
320356
357+ // Implement some comparison operators.
358+ inline bool operator == ( const Vector& right ) const
359+ {
360+ size_t leftCount = this->data_count;
361+ size_t rightCount = right.data_count;
362+
363+ if ( leftCount != rightCount )
364+ return false;
365+
366+ for ( size_t n = 0; n < leftCount; n++ )
367+ {
368+ const structType& leftData = this->data_entries[ n ];
369+ const structType& rightData = right.data_entries[ n ];
370+
371+ // Actually use the item comparator.
372+ if ( leftData != rightData )
373+ {
374+ return false;
375+ }
376+ }
377+
378+ return true;
379+ }
380+
381+ inline bool operator != ( const Vector& right ) const
382+ {
383+ return !( operator == ( right ) );
384+ }
385+
321386 private:
322387 structType *data_entries;
323388 size_t data_count;
--- unittests/src/alloc_helper.hxx (nonexistent)
+++ unittests/src/alloc_helper.hxx (revision 118)
@@ -0,0 +1,27 @@
1+// Allocation helpers for unit tests.
2+#ifndef _ALLOC_HELPERS_
3+#define _ALLOC_HELPERS_
4+
5+#include <sdk/OSUtils.memheap.h>
6+
7+extern NativeHeapAllocator globalHeapAlloc;
8+
9+struct EirHeapAllocator
10+{
11+ static void* Allocate( void *objPtr, size_t memSize, size_t alignment )
12+ {
13+ return globalHeapAlloc.Allocate( memSize, alignment );
14+ }
15+
16+ static bool Resize( void *objPtr, void *memPtr, size_t memSize )
17+ {
18+ return globalHeapAlloc.SetAllocationSize( memPtr, memSize );
19+ }
20+
21+ static void Free( void *objPtr, void *memPtr )
22+ {
23+ globalHeapAlloc.Free( memPtr );
24+ }
25+};
26+
27+#endif //_ALLOC_HELPERS_
\ No newline at end of file
--- unittests/src/main.cpp (revision 117)
+++ unittests/src/main.cpp (revision 118)
@@ -2,7 +2,11 @@
22 // Please compile and run if major changes have been done to eirrepo!
33
44 #include "StdInc.h"
5+#include <sdk/OSUtils.memheap.h>
56
7+// The heap allocator that should be used for our tests.
8+NativeHeapAllocator globalHeapAlloc;
9+
610 // We put this into a seperate file because there are IDEs which simply break character encodings
711 // because they store things in incompatible internal formats.
812 extern void UNICODE_TEST( void );
@@ -12,6 +16,7 @@
1216 extern void DTS_TESTS( void );
1317 extern void AVLTREE_TESTS( void );
1418 extern void VECTOR_TESTS( void );
19+extern void MAP_TESTS( void );
1520
1621 #ifdef _WIN32
1722 // Shell extension test.
@@ -28,6 +33,7 @@
2833 DTS_TESTS();
2934 AVLTREE_TESTS();
3035 VECTOR_TESTS();
36+ MAP_TESTS();
3137
3238 //Test_DTSConditionalStructing();
3339
--- unittests/src/map.cpp (nonexistent)
+++ unittests/src/map.cpp (revision 118)
@@ -0,0 +1,36 @@
1+// Unit tests for the Eir Map object.
2+#include <sdk/Map.h>
3+
4+#include "alloc_helper.hxx"
5+
6+typedef eir::Map <int, int, EirHeapAllocator> MapWithHeap;
7+
8+void MAP_TESTS( void )
9+{
10+ printf( "testing map simple item add..." );
11+ {
12+ MapWithHeap map;
13+
14+ map.Set( 1, 55 );
15+ map.Set( 2, 33 );
16+
17+ assert( map.GetKeyValueCount() == 2 );
18+ assert( map[1] == 55 );
19+ assert( map[2] == 33 );
20+ }
21+ printf( "ok.\n" );
22+
23+ printf( "testing map override item..." );
24+ {
25+ MapWithHeap map;
26+
27+ map[1] = 1337;
28+
29+ assert( map[1] == 1337 );
30+
31+ map[1] = 9001;
32+
33+ assert( map[1] == 9001 );
34+ }
35+ printf( "ok.\n" );
36+}
\ No newline at end of file
--- unittests/src/vector.cpp (revision 117)
+++ unittests/src/vector.cpp (revision 118)
@@ -1,30 +1,10 @@
11 // Eir Vector tests.
22 #include <sdk/Vector.h>
3-#include <sdk/OSUtils.memheap.h>
43
5-// The heap allocator that should be used for our tests.
6-static NativeHeapAllocator heapAlloc;
4+#include "alloc_helper.hxx"
75
8-struct VectorHeapAllocator
9-{
10- static void* Allocate( void *objPtr, size_t memSize, size_t alignment )
11- {
12- return heapAlloc.Allocate( memSize, alignment );
13- }
6+typedef eir::Vector <long long, EirHeapAllocator> VectorWithHeap;
147
15- static bool Resize( void *objPtr, void *memPtr, size_t memSize )
16- {
17- return heapAlloc.SetAllocationSize( memPtr, memSize );
18- }
19-
20- static void Free( void *objPtr, void *memPtr )
21- {
22- heapAlloc.Free( memPtr );
23- }
24-};
25-
26-typedef eir::Vector <long long, VectorHeapAllocator> VectorWithHeap;
27-
288 void VECTOR_TESTS( void )
299 {
3010 printf( "testing vector simple item add and remove..." );
@@ -89,6 +69,33 @@
8969 }
9070 printf( "ok.\n" );
9171
72+ printf( "testing vector comparator..." );
73+ {
74+ VectorWithHeap vec1, vec2;
75+
76+ assert( vec1 == vec1 );
77+
78+ vec1.AddToBack( 1337 );
79+ vec1.AddToBack( 20 );
80+
81+ assert( vec1 == vec1 );
82+
83+ vec2.AddToBack( 51 );
84+
85+ assert( vec1 != vec2 );
86+
87+ vec2.AddToBack( 66 );
88+
89+ assert( vec1 != vec2 );
90+
91+ vec2.Clear();
92+ vec2.AddToBack( 1337 );
93+ vec2.AddToBack( 20 );
94+
95+ assert( vec1 == vec2 );
96+ }
97+ printf( "ok.\n" );
98+
9299 printf( "testing vector copy..." );
93100 {
94101 VectorWithHeap vh1, vh2;
@@ -102,6 +109,7 @@
102109 assert( vh1.GetCount() == 2 );
103110 assert( vh1[0] == 2 );
104111 assert( vh1[1] == 3 );
112+ assert( vh1 == vh2 );
105113 }
106114 printf( "ok.\n" );
107115
@@ -127,10 +135,10 @@
127135
128136 printf( "testing vector alignment guarantees..." );
129137 {
130- eir::Vector <char, VectorHeapAllocator> byteVector;
131- eir::Vector <short, VectorHeapAllocator> wordVector;
132- eir::Vector <int, VectorHeapAllocator> dwordVector;
133- eir::Vector <long long, VectorHeapAllocator> qwordVector;
138+ eir::Vector <char, EirHeapAllocator> byteVector;
139+ eir::Vector <short, EirHeapAllocator> wordVector;
140+ eir::Vector <int, EirHeapAllocator> dwordVector;
141+ eir::Vector <long long, EirHeapAllocator> qwordVector;
134142
135143 byteVector.AddToBack( 1 );
136144 wordVector.AddToBack( 1 );
@@ -144,4 +152,23 @@
144152 qwordVector.RemoveFromBack();
145153 }
146154 printf( "ok.\n" );
155+
156+ printf( "testing vector item walking..." );
157+ {
158+ VectorWithHeap vec;
159+
160+ int values[] = { 1, 5, 11 };
161+
162+ for ( int val : values )
163+ {
164+ vec.AddToBack( val );
165+ }
166+
167+ vec.Walk(
168+ [&]( size_t idx, const long long& value )
169+ {
170+ assert( values[idx] == value );
171+ });
172+ }
173+ printf( "ok.\n" );
147174 }
\ No newline at end of file
Show on old repository browser