• R/O
  • SSH
  • HTTPS

eirrepo: Commit


Commit MetaInfo

Revision129 (tree)
Time2018-09-13 19:09:45
Authorquiret

Log Message

- added custom object allocator support for eir::Map (we are going to need this type in FileSystem module)
- added IsEmpty method to eir::Map

Change Summary

Incremental Difference

--- unittests/src/map.cpp (revision 128)
+++ unittests/src/map.cpp (revision 129)
@@ -162,4 +162,24 @@
162162 assert( map1 != map2 );
163163 }
164164 printf( "ok.\n" );
165+
166+ printf( "testing map with custom allocator link..." );
167+ {
168+ eir::Map <int, int, EirHeapLinkAllocator> customMap( eir::CONSTR_WITH_ALLOC, &globalHeapAlloc );
169+
170+ assert( customMap.IsEmpty() == true );
171+
172+ customMap[ 32 ] = 43;
173+ customMap[ 5328579 ] = 4238423;
174+
175+ MapWithHeap normalMap( customMap );
176+
177+ assert( normalMap == customMap );
178+ assert( !( normalMap != customMap ) );
179+
180+ // Test some size stuff, for optimization.
181+ static_assert( sizeof(normalMap) == sizeof(void*) );
182+ static_assert( sizeof(customMap) == sizeof(void*) + sizeof(void*) );
183+ }
184+ printf( "ok.\n" );
165185 }
\ No newline at end of file
--- common/sdk/eirutils.h (revision 128)
+++ common/sdk/eirutils.h (revision 129)
@@ -43,11 +43,6 @@
4343 template <bool trueRealMemberFalseStaticInline, typename structType, typename fieldsStruct>
4444 struct size_opt : public fieldsStruct
4545 {
46-};
47-
48-template <typename structType, typename fieldsStruct>
49-struct size_opt <false, structType, fieldsStruct> : public fieldsStruct
50-{
5146 AINLINE size_opt( int )
5247 {
5348 return;
--- common/sdk/Map.h (revision 128)
+++ common/sdk/Map.h (revision 129)
@@ -29,16 +29,35 @@
2929 namespace eir
3030 {
3131
32-template <typename keyType, typename valueType, typename allocatorType>
32+// A very special pass-in just for creation with the allocator initialization.
33+enum constr_with_alloc
34+{
35+ CONSTR_WITH_ALLOC
36+};
37+
38+// Default comparator for objects inside the Map.
39+struct MapDefaultComparator
40+{
41+ template <typename keyType>
42+ static AINLINE bool is_less_than( const keyType& left, const keyType& right )
43+ {
44+ // This is important because not all key types come with a usable "operator <" overload,
45+ // for example it is not really a good idea for eir::String because you ought to take
46+ // case-sensitivity into account!
47+ return ( left < right );
48+ }
49+};
50+
51+template <typename keyType, typename valueType, typename allocatorType, typename comparatorType = MapDefaultComparator>
3352 struct Map
3453 {
3554 // Make templates friends of each-other.
36- template <typename, typename, typename> friend struct Map;
55+ template <typename, typename, typename, typename> friend struct Map;
3756
3857 // Node inside this Map.
3958 struct Node
4059 {
41- friend struct Map <keyType, valueType, allocatorType>;
60+ template <typename, typename, typename, typename> friend struct Map;
4261
4362 // Get rid of the default things.
4463 inline Node( const Node& right ) = delete;
@@ -93,7 +112,7 @@
93112 const Node *leftNode = AVL_GETITEM( Node, left, sortedByKeyNode );
94113 const Node *rightNode = AVL_GETITEM( Node, right, sortedByKeyNode );
95114
96- return ( leftNode->key < rightNode->key );
115+ return comparatorType::is_less_than( leftNode->key, rightNode->key );
97116 }
98117
99118 static inline bool IsNodeLessThanValue( const AVLNode *left, const keyType& right )
@@ -100,7 +119,7 @@
100119 {
101120 const Node *leftNode = AVL_GETITEM( Node, left, sortedByKeyNode );
102121
103- return ( leftNode->key < right );
122+ return comparatorType::is_less_than( leftNode->key, right );
104123 }
105124
106125 static inline bool IsNodeGreaterThanValue( const AVLNode *left, const keyType& right )
@@ -107,20 +126,20 @@
107126 {
108127 const Node *leftNode = AVL_GETITEM( Node, left, sortedByKeyNode );
109128
110- return ( leftNode->key > right );
129+ return comparatorType::is_less_than( right, leftNode->key );
111130 }
112131 };
113132
114133 typedef AVLTree <avlKeyNodeDispatcher> MapAVLTree;
115134
116- static AINLINE void dismantle_node( void *objMem, Node *theNode )
135+ static AINLINE void dismantle_node( Map *refMem, Node *theNode )
117136 {
118137 theNode->~Node();
119138
120- allocatorType::Free( objMem, theNode );
139+ refMem->data.allocData.Free( refMem, theNode );
121140 }
122141
123- static AINLINE void release_nodes( void *objMem, MapAVLTree& workTree )
142+ static AINLINE void release_nodes( Map *refMem, MapAVLTree& workTree )
124143 {
125144 // Clear all allocated Nodes.
126145 while ( AVLNode *avlSomeNode = workTree.GetRootNode() )
@@ -129,13 +148,13 @@
129148
130149 workTree.RemoveByNodeFast( avlSomeNode );
131150
132- dismantle_node( objMem, someNode );
151+ dismantle_node( refMem, someNode );
133152 }
134153 }
135154
136- static AINLINE Node* NewNode( void *objMem, MapAVLTree& workTree, keyType key, valueType value )
155+ static AINLINE Node* NewNode( Map *refMem, MapAVLTree& workTree, keyType key, valueType value )
137156 {
138- void *newNodeMem = allocatorType::Allocate( objMem, sizeof(Node), alignof(Node) );
157+ void *newNodeMem = refMem->data.allocData.Allocate( refMem, sizeof(Node), alignof(Node) );
139158
140159 if ( newNodeMem == nullptr )
141160 {
@@ -142,28 +161,48 @@
142161 throw eir_exception();
143162 }
144163
145- Node *newNode = new (newNodeMem) Node( std::move( key ), std::move( value ) );
164+ try
165+ {
166+ Node *newNode = new (newNodeMem) Node( std::move( key ), std::move( value ) );
146167
147- // Link this node into our system.
148- workTree.Insert( &newNode->sortedByKeyNode );
168+ try
169+ {
170+ // Link this node into our system.
171+ workTree.Insert( &newNode->sortedByKeyNode );
172+ }
173+ catch( ... )
174+ {
175+ // Could receive an exception if the comparator of Node does throw.
176+ newNode->~Node();
149177
150- return newNode;
178+ throw;
179+ }
180+
181+ return newNode;
182+ }
183+ catch( ... )
184+ {
185+ refMem->data.allocData.Free( refMem, newNodeMem );
186+
187+ throw;
188+ }
151189 }
152190
153- static AINLINE MapAVLTree clone_key_tree( void *objMem, MapAVLTree& right )
191+ template <typename otherNodeType, typename otherAVLTreeType>
192+ static AINLINE MapAVLTree clone_key_tree( Map *refMem, otherAVLTreeType& right )
154193 {
155194 // We know that there cannot be two-same-value nodes, so we skip checking nodestacks.
156195 MapAVLTree newTree;
157196
158- MapAVLTree::diff_node_iterator iter( right );
197+ typename otherAVLTreeType::diff_node_iterator iter( right );
159198
160199 try
161200 {
162201 while ( !iter.IsEnd() )
163202 {
164- Node *rightNode = AVL_GETITEM( Node, iter.Resolve(), sortedByKeyNode );
203+ otherNodeType *rightNode = AVL_GETITEM( otherNodeType, iter.Resolve(), sortedByKeyNode );
165204
166- NewNode( objMem, newTree, rightNode->key, rightNode->value );
205+ NewNode( refMem, newTree, rightNode->key, rightNode->value );
167206
168207 iter.Increment();
169208 }
@@ -171,7 +210,7 @@
171210 catch( ... )
172211 {
173212 // Have to release all items again because one of them did not cooperate.
174- release_nodes( objMem, newTree );
213+ release_nodes( refMem, newTree );
175214
176215 throw;
177216 }
@@ -179,16 +218,34 @@
179218 return newTree;
180219 }
181220
221+ // Now decide if we need an object-allocator.
222+ INSTANCE_SUBSTRUCTCHECK( is_object );
223+
224+ static constexpr bool hasObjectAllocator = PERFORM_SUBSTRUCTCHECK( allocatorType, is_object );
225+
182226 public:
227+ template <typename... Args>
228+ inline Map( constr_with_alloc _, Args... allocArgs ) : data( MapAVLTree(), std::forward <Args> ( allocArgs )... )
229+ {
230+ return;
231+ }
232+
183233 inline Map( const Map& right )
184- : avlKeyTree( clone_key_tree( this, right.avlKeyTree ) )
234+ : data( clone_key_tree <Node> ( this, right.data.avlKeyTree ) )
185235 {
186236 return;
187237 }
188238
239+ template <typename otherAllocatorType>
240+ inline Map( const Map <keyType, valueType, otherAllocatorType, comparatorType>& right )
241+ : data( clone_key_tree <typename Map <keyType, valueType, otherAllocatorType, comparatorType>::Node> ( this, right.data.avlKeyTree ) )
242+ {
243+ return;
244+ }
245+
189246 // WARNING: only move-construct if you know that allocatorType matches in both objects.
190247 inline Map( Map&& right )
191- : avlKeyTree( std::move( right.avlKeyTree ) )
248+ : data( std::move( right.data ) )
192249 {
193250 return;
194251 }
@@ -195,26 +252,45 @@
195252
196253 inline ~Map( void )
197254 {
198- release_nodes( this, this->avlKeyTree );
255+ release_nodes( this, this->data.avlKeyTree );
199256 }
200257
201258 inline Map& operator = ( const Map& right )
202259 {
203260 // Clone the thing.
204- MapAVLTree newTree = clone_key_tree( this, right.avlKeyTree );
261+ MapAVLTree newTree = clone_key_tree <Node> ( this, right.data.avlKeyTree );
205262
206263 // Release the old.
207- release_nodes( this, this->avlKeyTree );
264+ release_nodes( this, this->data.avlKeyTree );
208265
209- this->avlKeyTree = std::move( newTree );
266+ this->data.avlKeyTree = std::move( newTree );
210267
268+ // TODO: think about copying the allocator aswell.
269+
211270 return *this;
212271 }
213272
273+ template <typename otherAllocatorType>
274+ inline Map& operator = ( const Map <keyType, valueType, otherAllocatorType, comparatorType>& right )
275+ {
276+ // Clone the thing.
277+ MapAVLTree newTree =
278+ clone_key_tree <typename Map <keyType, valueType, otherAllocatorType, comparatorType>::Node> ( this, right.data.avlKeyTree );
279+
280+ // Release the old.
281+ release_nodes( this, this->data.avlKeyTree );
282+
283+ this->data.avlKeyTree = std::move( newTree );
284+
285+ // TODO: think about copying the allocator aswell.
286+
287+ return *this;
288+ }
289+
214290 // WARNING: only move if allocatorType points to the same data-repository in both objects!
215291 inline Map& operator = ( Map&& right )
216292 {
217- this->avlKeyTree = std::move( right.avlKeyTree );
293+ this->data = std::move( right.data );
218294
219295 return *this;
220296 }
@@ -226,7 +302,7 @@
226302 inline void Set( const keyType& key, valueType value )
227303 {
228304 // Check if such a node exists.
229- if ( AVLNode *avlExistingNode = this->avlKeyTree.FindNode( key ) )
305+ if ( AVLNode *avlExistingNode = this->data.avlKeyTree.FindNode( key ) )
230306 {
231307 Node *existingNode = AVL_GETITEM( Node, avlExistingNode, sortedByKeyNode );
232308
@@ -235,19 +311,19 @@
235311 }
236312
237313 // We must create a new node.
238- NewNode( this, this->avlKeyTree, key, std::move( value ) );
314+ NewNode( this, this->data.avlKeyTree, key, std::move( value ) );
239315 }
240316
241317 // Erases any Node by key.
242318 inline void RemoveByKey( const keyType& key )
243319 {
244- AVLNode *avlExistingNode = this->avlKeyTree.FindNode( key );
320+ AVLNode *avlExistingNode = this->data.avlKeyTree.FindNode( key );
245321
246322 if ( avlExistingNode == nullptr )
247323 return;
248324
249325 // Remove it.
250- this->avlKeyTree.RemoveByNodeFast( avlExistingNode );
326+ this->data.avlKeyTree.RemoveByNodeFast( avlExistingNode );
251327
252328 Node *existingNode = AVL_GETITEM( Node, avlExistingNode, sortedByKeyNode );
253329
@@ -257,7 +333,7 @@
257333 // Clears all keys and values from this Map.
258334 inline void Clear( void )
259335 {
260- release_nodes( this, this->avlKeyTree );
336+ release_nodes( this, this->data.avlKeyTree );
261337 }
262338
263339 // Returns the amount of keys/values inside this Map.
@@ -265,7 +341,7 @@
265341 {
266342 size_t count = 0;
267343
268- MapAVLTree::diff_node_iterator iter( this->avlKeyTree );
344+ MapAVLTree::diff_node_iterator iter( this->data.avlKeyTree );
269345
270346 while ( !iter.IsEnd() )
271347 {
@@ -279,7 +355,7 @@
279355
280356 inline Node* Find( const keyType& key )
281357 {
282- if ( AVLNode *avlExistingNode = this->avlKeyTree.FindNode( key ) )
358+ if ( AVLNode *avlExistingNode = this->data.avlKeyTree.FindNode( key ) )
283359 {
284360 return AVL_GETITEM( Node, avlExistingNode, sortedByKeyNode );
285361 }
@@ -289,7 +365,7 @@
289365
290366 inline const Node* Find( const keyType& key ) const
291367 {
292- if ( const AVLNode *avlExistingNode = this->avlKeyTree.FindNode( key ) )
368+ if ( const AVLNode *avlExistingNode = this->data.avlKeyTree.FindNode( key ) )
293369 {
294370 return AVL_GETITEM( const Node, avlExistingNode, sortedByKeyNode );
295371 }
@@ -297,11 +373,17 @@
297373 return nullptr;
298374 }
299375
376+ // Returns true if there is nothing inside this Map/the AVL tree.
377+ inline bool IsEmpty( void ) const
378+ {
379+ return ( this->data.avlKeyTree.GetRootNode() == nullptr );
380+ }
381+
300382 // Walks through all nodes of this tree.
301383 template <typename callbackType>
302384 inline void WalkNodes( const callbackType& cb )
303385 {
304- MapAVLTree::diff_node_iterator iter( this->avlKeyTree );
386+ MapAVLTree::diff_node_iterator iter( this->data.avlKeyTree );
305387
306388 while ( !iter.IsEnd() )
307389 {
@@ -321,14 +403,18 @@
321403 return findNode->value;
322404 }
323405
324- return NewNode( this, this->avlKeyTree, key, valueType() )->value;
406+ return NewNode( this, this->data.avlKeyTree, key, valueType() )->value;
325407 }
326408
327- inline bool operator == ( const Map& right ) const
409+ template <typename otherAllocatorType>
410+ inline bool operator == ( const Map <keyType, valueType, otherAllocatorType, comparatorType>& right ) const
328411 {
329- MapAVLTree::diff_node_iterator left_iter( this->avlKeyTree );
330- MapAVLTree::diff_node_iterator right_iter( right.avlKeyTree );
412+ typedef typename decltype( right.data.avlKeyTree ) otherAVLTreeType;
413+ typedef typename Map <keyType, valueType, otherAllocatorType, comparatorType>::Node otherNodeType;
331414
415+ typename MapAVLTree::diff_node_iterator left_iter( this->data.avlKeyTree );
416+ typename otherAVLTreeType::diff_node_iterator right_iter( right.data.avlKeyTree );
417+
332418 while ( true )
333419 {
334420 bool isLeftEnd = left_iter.IsEnd();
@@ -345,7 +431,7 @@
345431
346432 // If any key is different then we do not match.
347433 const Node *leftNode = AVL_GETITEM( Node, left_iter.Resolve(), sortedByKeyNode );
348- const Node *rightNode = AVL_GETITEM( Node, right_iter.Resolve(), sortedByKeyNode );
434+ const otherNodeType *rightNode = AVL_GETITEM( otherNodeType, right_iter.Resolve(), sortedByKeyNode );
349435
350436 if ( leftNode->GetKey() != rightNode->GetKey() )
351437 {
@@ -366,13 +452,48 @@
366452 return false;
367453 }
368454
369- inline bool operator != ( const Map& right ) const
455+ template <typename otherAllocatorType>
456+ inline bool operator != ( const Map <keyType, valueType, otherAllocatorType, comparatorType>& right ) const
370457 {
371458 return !( operator == ( right ) );
372459 }
373460
374461 private:
375- mutable MapAVLTree avlKeyTree;
462+ template <bool isObjectAllocator>
463+ struct fields
464+ {
465+ AINLINE fields( void ) = default;
466+ AINLINE fields( MapAVLTree tree ) : avlKeyTree( std::move( tree ) )
467+ {
468+ return;
469+ }
470+ AINLINE fields( fields&& right ) = default;
471+
472+ AINLINE fields& operator = ( fields&& right ) = default;
473+
474+ mutable MapAVLTree avlKeyTree;
475+ inline static allocatorType allocData;
476+ };
477+
478+ template <>
479+ struct fields <true>
480+ {
481+ AINLINE fields( void ) = default;
482+
483+ template <typename... Args>
484+ AINLINE fields( MapAVLTree tree, Args... allocArgs ) : avlKeyTree( std::move( tree ) ), allocData( std::forward <Args> ( allocArgs )... )
485+ {
486+ return;
487+ }
488+ AINLINE fields( fields&& right ) = default;
489+
490+ AINLINE fields& operator = ( fields&& right ) = default;
491+
492+ mutable MapAVLTree avlKeyTree;
493+ allocatorType allocData;
494+ };
495+
496+ fields <hasObjectAllocator> data;
376497 };
377498
378499 }
Show on old repository browser