• R/O
  • SSH
  • HTTPS

eirrepo: Commit


Commit MetaInfo

Revision179 (tree)
Time2018-12-28 08:20:57
Authorquiret

Log Message

- added SortedSliceSector node auditing feature where you can DetachData nodes, change their attributes and reinsert them back into the tree
- fixed a bug where subtracted nodes would receive wrong attributes (the attributes of insertion request); new requirement to copy-construct metaData

Change Summary

Incremental Difference

--- common/sdk/SortedSliceSector.h (revision 178)
+++ common/sdk/SortedSliceSector.h (revision 179)
@@ -29,6 +29,7 @@
2929 #include "eirutils.h"
3030 #include "MetaHelpers.h"
3131 #include "avlsetmaputil.h"
32+#include "rwlist.hpp"
3233
3334 namespace eir
3435 {
@@ -75,6 +76,8 @@
7576 struct SortedSliceSector
7677 {
7778 // REQUIREMENTS FOR metaDataType TYPE:
79+ // * constructor( eir::mathSlice <numberType> slice, ... );
80+ // * constructor( const metaDataType& metaData );
7881 // * sectorSlice_t GetNodeSlice( void ) const;
7982 // * template <typename... systemArgs> void Remove( systemArgs... args );
8083 // * template <typename... updateArgs> bool IsMergeable( updateArgs... args ) const;
@@ -94,6 +97,10 @@
9497 {
9598 return;
9699 }
100+ AINLINE sliceNode( metaDataType metaData ) : metaData( std::move( metaData ) )
101+ {
102+ return;
103+ }
97104 AINLINE sliceNode( const sliceNode& ) = delete;
98105 AINLINE sliceNode( sliceNode&& ) = delete;
99106
@@ -119,6 +126,18 @@
119126
120127 static constexpr bool hasObjectAllocator = PERFORM_SUBSTRUCTCHECK( allocatorType, is_object );
121128
129+ // Node creation and destruction helpers.
130+ template <typename... constrArgs>
131+ AINLINE sliceNode* new_node( constrArgs... args )
132+ {
133+ return eir::dyn_new_struct <sliceNode> ( this->data.allocData, this, std::forward <constrArgs> ( args )... );
134+ }
135+
136+ AINLINE void del_node( sliceNode *node ) noexcept
137+ {
138+ eir::dyn_del_struct <sliceNode> ( this->data.allocData, this, node );
139+ }
140+
122141 public:
123142 AINLINE SortedSliceSector( void )
124143 {
@@ -145,7 +164,7 @@
145164
146165 this->data.avlSliceTree.RemoveByNode( avlNode );
147166
148- eir::dyn_del_struct <sliceNode> ( this->data.allocData, this, node );
167+ del_node( node );
149168 }
150169 }
151170
@@ -157,215 +176,197 @@
157176 return *this;
158177 }
159178
179+private:
160180 template <typename... constrArgs>
161- AINLINE void Insert( sectorSlice_t slice, constrArgs... args )
181+ AINLINE void MergeSlice( sectorSlice_t slice, sliceNode *hostOfMerge, sectorSlice_t hostRegion, constrArgs... args )
162182 {
163- // Check if our request would overlap with anything.
164- // If it would then we have to merge instead.
165- AVLNode *avlAnyMergeWithNode = this->data.avlSliceTree.FindAnyNodeByCriteria(
166- [&]( AVLNode *leftNode )
183+ // Special case: if we are told to merge in an empty slice, we discard it along with its node.
184+ if ( slice.IsEmpty() )
167185 {
168- return _CompareNodeWithSlice( leftNode, slice, true );
169- });
186+ // Since we require that hostOfMerge is sharing region with slice variable,
187+ // then it mus tmean that hostOfMerge is empty too.
188+ // Thus it can be deleted.
189+ if ( hostOfMerge )
190+ {
191+ del_node( hostOfMerge );
192+ }
170193
171- if ( avlAnyMergeWithNode )
172- {
173- // Collect the region that our new slice should be at.
174- lowerBound <numberType> regionMin = slice.GetSliceStartBound();
175- upperBound <numberType> regionMax = slice.GetSliceEndBound();
194+ return;
195+ }
176196
177- // Now process all nodes in the AVL tree that intersect the requested slice.
178- // * if a node is found not mergeable, it is removed/shrunk.
179- // * if a node is found mergeable, then it gives up its region to the new slice.
180- // As a result, (at least) the requested slice is placed available in our region.
197+ // Collect the region that our new slice should be at.
198+ lowerBound <numberType> regionMin = slice.GetSliceStartBound();
199+ upperBound <numberType> regionMax = slice.GetSliceEndBound();
181200
182- sliceNode *hostOfMerge = nullptr; // could find a node that is willing to merge, so pick it as memory.
183- sectorSlice_t hostRegion;
201+ // Now process all nodes in the AVL tree that intersect the requested slice.
202+ // * if a node is found not mergeable, it is removed/shrunk.
203+ // * if a node is found mergeable, then it gives up its region to the new slice.
204+ // As a result, (at least) the requested slice is placed available in our region.
184205
185- sliceNode* nodesToSubtract[ 2 ]; // there is a max of two nodes that can be alive after subtraction.
186- sectorSlice_t nodesToSubtractSlices[ 2 ];
187- size_t numNodesToSubtract = 0;
206+ sliceNode* nodesToSubtract[ 2 ]; // there is a max of two nodes that can be alive after subtraction.
207+ sectorSlice_t nodesToSubtractSlices[ 2 ];
208+ size_t numNodesToSubtract = 0;
209+ {
210+ while ( true )
188211 {
189- AVLNode *avlIntersectNode = avlAnyMergeWithNode;
190- bool hasIntersectNode = true;
212+ AVLNode *avlIntersectNode = this->data.avlSliceTree.FindAnyNodeByCriteria(
213+ [&]( AVLNode *leftNode )
214+ {
215+ return _CompareNodeWithSlice( leftNode, slice, true );
216+ });
191217
192- while ( true )
218+ if ( avlIntersectNode == nullptr )
193219 {
194- // To remove certain redundancy checking.
195- if ( !hasIntersectNode )
196- {
197- avlIntersectNode = this->data.avlSliceTree.FindAnyNodeByCriteria(
198- [&]( AVLNode *leftNode )
199- {
200- return _CompareNodeWithSlice( leftNode, slice, true );
201- });
220+ break;
221+ }
202222
203- if ( avlIntersectNode == nullptr )
204- {
205- break;
206- }
223+ // Remove it so we are done processing it.
224+ this->data.avlSliceTree.RemoveByNode( avlIntersectNode );
207225
208- hasIntersectNode = true;
209- }
226+ // Can we merge with this node?
227+ sliceNode *intersectNode = AVL_GETITEM( sliceNode, avlIntersectNode, node );
210228
211- // Remove it so we are done processing it.
212- this->data.avlSliceTree.RemoveByNode( avlIntersectNode );
229+ sectorSlice_t intersectSlice = intersectNode->GetNodeSlice();
213230
214- // Can we merge with this node?
215- sliceNode *intersectNode = AVL_GETITEM( sliceNode, avlIntersectNode, node );
231+ if ( intersectNode->metaData.IsMergeable( args... ) )
232+ {
233+ // Update our merge region.
234+ if ( intersectSlice.GetSliceStartBound() < regionMin )
235+ {
236+ regionMin = intersectSlice.GetSliceStartBound();
237+ }
216238
217- sectorSlice_t intersectSlice = intersectNode->GetNodeSlice();
239+ if ( regionMax < intersectSlice.GetSliceEndBound() )
240+ {
241+ regionMax = intersectSlice.GetSliceEndBound();
242+ }
218243
219- if ( intersectNode->metaData.IsMergeable( args... ) )
244+ // Remember the first one so we can use it as memory.
245+ if ( hostOfMerge == nullptr )
220246 {
221- // Update our merge region.
222- if ( intersectSlice.GetSliceStartBound() < regionMin )
223- {
224- regionMin = intersectSlice.GetSliceStartBound();
225- }
226-
227- if ( regionMax < intersectSlice.GetSliceEndBound() )
228- {
229- regionMax = intersectSlice.GetSliceEndBound();
230- }
231-
232- // Remember the first one so we can use it as memory.
233- if ( hostOfMerge == nullptr )
234- {
235- hostOfMerge = intersectNode;
236- hostRegion = intersectSlice;
237- }
238- // TODO: might make a selector here to pick a better one across all merge-candidates.
239- else
240- {
241- // Delete any non-candidates.
242- eir::dyn_del_struct <sliceNode> ( this->data.allocData, this, intersectNode );
243- }
247+ hostOfMerge = intersectNode;
248+ hostRegion = intersectSlice;
244249 }
250+ // TODO: might make a selector here to pick a better one across all merge-candidates.
245251 else
246252 {
247- // If not then we need to subtract it later, if we would not disappear of course.
248- eIntersectionResult intResult = intersectSlice.intersectWith( slice );
253+ // Delete any non-candidates.
254+ del_node( intersectNode );
255+ }
256+ }
257+ else
258+ {
259+ // If not then we need to subtract it later, if we would not disappear of course.
260+ eIntersectionResult intResult = intersectSlice.intersectWith( slice );
249261
250- bool hasRegistered = false;
262+ bool hasRegistered = false;
251263
252- // Graceful cleanup to handle the unknown case.
264+ // Graceful cleanup to handle the unknown case.
253265
254- if ( isCoveredIntersect( intResult ) == false && intResult != INTERSECT_UNKNOWN )
255- {
266+ if ( isCoveredIntersect( intResult ) == false && intResult != INTERSECT_UNKNOWN )
267+ {
256268 #ifdef _DEBUG
257- assert( numNodesToSubtract < 2 );
269+ assert( numNodesToSubtract < 2 );
258270 #endif //_DEBUG
259271
260- if ( numNodesToSubtract < 2 )
261- {
262- nodesToSubtract[ numNodesToSubtract ] = intersectNode;
263- nodesToSubtractSlices[ numNodesToSubtract ] = intersectSlice;
272+ if ( numNodesToSubtract < 2 )
273+ {
274+ nodesToSubtract[ numNodesToSubtract ] = intersectNode;
275+ nodesToSubtractSlices[ numNodesToSubtract ] = intersectSlice;
264276
265- numNodesToSubtract++;
277+ numNodesToSubtract++;
266278
267- hasRegistered = true;
268- }
279+ hasRegistered = true;
269280 }
281+ }
270282
271- // Either if we are covered or there was an error (graceful handling).
272- if ( hasRegistered == false )
273- {
274- eir::dyn_del_struct <sliceNode> ( this->data.allocData, this, intersectNode );
275- }
283+ // Either if we are covered or there was an error (graceful handling).
284+ if ( hasRegistered == false )
285+ {
286+ del_node( intersectNode );
276287 }
277-
278- // Go to next node.
279- avlIntersectNode = nullptr;
280- hasIntersectNode = false;
281288 }
282289 }
290+ }
283291
284- // Construct the slice of the merge region we decided on.
285- sectorSlice_t newSlice = sectorSlice_t::fromBounds( regionMin, regionMax );
292+ // Construct the slice of the merge region we decided on.
293+ sectorSlice_t newSlice = sectorSlice_t::fromBounds( regionMin, regionMax );
286294
287- // Put in the other slices after subtraction.
288- for ( size_t n = 0; n < numNodesToSubtract; n++ )
295+ // Put in the other slices after subtraction.
296+ for ( size_t n = 0; n < numNodesToSubtract; n++ )
297+ {
298+ sliceNode *subtractNode = nodesToSubtract[ n ];
299+ sectorSlice_t subtractSlice = nodesToSubtractSlices[ n ];
300+
301+ bool hasFirst = false;
302+
303+ subtractSlice.subtractRegion( newSlice,
304+ [&]( const sectorSlice_t& remainder, bool isFirst )
289305 {
290- sliceNode *subtractNode = nodesToSubtract[ n ];
291- sectorSlice_t subtractSlice = nodesToSubtractSlices[ n ];
306+ sliceNode *insertToTreeNode = nullptr;
292307
293- bool hasFirst = false;
294-
295- subtractSlice.subtractRegion( newSlice,
296- [&]( const sectorSlice_t& remainder, bool isFirst )
308+ if ( isFirst )
297309 {
298- sliceNode *insertToTreeNode = nullptr;
299-
300- if ( isFirst )
310+ // Did the validity region actually change?
311+ if ( subtractSlice != remainder )
301312 {
302- // Did the validity region actually change?
303- if ( subtractSlice != remainder )
304- {
305- // Set the new validity region.
306- subtractNode->metaData.Update( remainder, args... );
307- }
313+ // Set the new validity region.
314+ subtractNode->metaData.Update( remainder, args... );
315+ }
308316
309- // Reinsert into the tree.
310- insertToTreeNode = subtractNode;
317+ // Reinsert into the tree.
318+ insertToTreeNode = subtractNode;
311319
312- hasFirst = true;
313- }
314- else
315- {
316- // Spawn a new node.
317- insertToTreeNode = eir::dyn_new_struct <sliceNode> ( this->data.allocData, this, remainder, args... );
318- }
320+ hasFirst = true;
321+ }
322+ else
323+ {
324+ // Spawn a new node.
325+ metaDataType metaData( subtractNode->metaData );
319326
320- this->data.avlSliceTree.Insert( &insertToTreeNode->node );
321- });
327+ metaData.Update( remainder, args... );
322328
323- if ( !hasFirst )
324- {
325- // Error handling, just in case (graceful).
326- eir::dyn_del_struct <sliceNode> ( this->data.allocData, this, subtractNode );
329+ insertToTreeNode = new_node( std::move( metaData ) );
327330 }
328- }
329331
330- // Put in our new node with the arguments forwarded-in.
331- if ( hostOfMerge )
332+ this->data.avlSliceTree.Insert( &insertToTreeNode->node );
333+ });
334+
335+ if ( !hasFirst )
332336 {
333- // Did the region actually change?
334- if ( hostRegion != newSlice )
335- {
336- hostOfMerge->metaData.Update( std::move( newSlice ), std::forward <constrArgs> ( args )... );
337- }
337+ // Error handling, just in case (graceful).
338+ del_node( subtractNode );
338339 }
339- else
340+ }
341+
342+ // Put in our new node with the arguments forwarded-in.
343+ if ( hostOfMerge )
344+ {
345+ // Did the region actually change?
346+ if ( hostRegion != newSlice )
340347 {
341- // Allocate a new node.
342- hostOfMerge = eir::dyn_new_struct <sliceNode> ( this->data.allocData, this, std::move( newSlice ), std::forward <constrArgs> ( args )... );
348+ hostOfMerge->metaData.Update( std::move( newSlice ), std::forward <constrArgs> ( args )... );
343349 }
344-
345- // Since this node has been removed we must reinsert it.
346- this->data.avlSliceTree.Insert( &hostOfMerge->node );
347350 }
348- else if ( slice.IsEmpty() == false ) // need to check because we could actually get empty requests.
351+ else
349352 {
350- // Create a new node and insert it into the tree, because
351- // we do not overlap/neighbor with anything.
352- sliceNode *newNode = eir::dyn_new_struct <sliceNode> ( this->data.allocData, this, std::move( slice ), std::forward <constrArgs> ( args )... );
353+ // Allocate a new node.
354+ hostOfMerge = new_node( std::move( newSlice ), std::forward <constrArgs> ( args )... );
355+ }
353356
354- try
355- {
356- this->data.avlSliceTree.Insert( &newNode->node );
357- }
358- catch( ... )
359- {
360- eir::dyn_del_struct <sliceNode> ( this->data.allocData, this, newNode );
361-
362- throw;
363- }
364- }
357+ // Since this node has been removed we must reinsert it.
358+ this->data.avlSliceTree.Insert( &hostOfMerge->node );
365359 }
360+
361+public:
362+ template <typename... constrArgs>
363+ inline void Insert( sectorSlice_t slice, constrArgs... args )
364+ {
365+ MergeSlice( std::move( slice ), nullptr, sectorSlice_t(), std::forward <constrArgs> ( args )... );
366+ }
366367
367368 template <typename... constrArgs>
368- AINLINE void Remove( sectorSlice_t slice, constrArgs... args )
369+ inline void Remove( sectorSlice_t slice, constrArgs... args )
369370 {
370371 // While we find any intersection we remove areas from said nodes.
371372 while ( AVLNode *avlFoundNode = this->data.avlSliceTree.FindNodeCustom <nodeWithoutNeighborComparator> ( slice ) )
@@ -394,7 +395,7 @@
394395 else
395396 {
396397 // Must spawn a new node.
397- sliceNode *newNode = eir::dyn_new_struct <sliceNode> ( this->data.allocData, this, newSlice, args... );
398+ sliceNode *newNode = new_node( newSlice, args... );
398399
399400 try
400401 {
@@ -402,7 +403,7 @@
402403 }
403404 catch( ... )
404405 {
405- eir::dyn_del_struct <sliceNode> ( this->data.allocData, this, newNode );
406+ del_node( newNode );
406407
407408 throw;
408409 }
@@ -414,7 +415,7 @@
414415 // Remove us.
415416 foundNode->metaData.Remove( args... );
416417
417- eir::dyn_del_struct <sliceNode> ( this->data.allocData, this, foundNode );
418+ del_node( foundNode );
418419 }
419420 }
420421 }
@@ -440,7 +441,7 @@
440441
441442 this->data.avlSliceTree.RemoveByNode( avlCurNode );
442443
443- eir::dyn_del_struct <sliceNode> ( this->data.allocData, this, curNode );
444+ del_node( curNode );
444445 }
445446 }
446447
@@ -579,6 +580,34 @@
579580 }
580581 }
581582
583+ // TODO: create node Detach and node Recommit API that by principle avoids additional memory allocations
584+ // by removing and reinserting already-allocated nodes, just exposing the meta-data handle to the user.
585+ // * Of course additional memory allocation is only prevented if removal and reinsertion of nodes is atomic
586+ // but if the slice structure does change new memory allocation is handled properly.
587+
588+ AINLINE void DetachData( metaDataType *data )
589+ {
590+ sliceNode *node = LIST_GETITEM( sliceNode, data, metaData );
591+
592+ this->data.avlSliceTree.RemoveByNode( &node->node );
593+
594+ // You can not treat this structure as if the node never existed
595+ // inside it, like inserting new slices or removing some, etc.
596+ }
597+
598+ template <typename... constrArgs>
599+ inline void RecommitData( metaDataType *data, constrArgs... args )
600+ {
601+ // Remember to not use the data anymore after calling this function.
602+ // This includes removing the data out of any management structures.
603+
604+ sliceNode *node = LIST_GETITEM( sliceNode, data, metaData );
605+
606+ sectorSlice_t hostRegion = node->GetNodeSlice();
607+
608+ MergeSlice( hostRegion, node, hostRegion, std::forward <constrArgs> ( args )... );
609+ }
610+
582611 private:
583612 static AINLINE eCompResult _CompareSlices( const sectorSlice_t& leftSlice, const sectorSlice_t& rightSlice, bool doCountInNeighbors )
584613 {
--- unittests/src/sortedslicesector.cpp (revision 178)
+++ unittests/src/sortedslicesector.cpp (revision 179)
@@ -679,6 +679,88 @@
679679 }
680680 printf( "ok.\n" );
681681
682+ printf( "testing sorted-slice-sector node auditing..." );
683+ {
684+ enum class data_type
685+ {
686+ TYPE_0,
687+ TYPE_1
688+ };
689+
690+ struct same_type_metadata_2
691+ {
692+ same_type_metadata_2( eir::mathSlice <int> slice, data_type type ) : slice( std::move( slice ) ), type( type )
693+ {
694+ return;
695+ }
696+ same_type_metadata_2( const same_type_metadata_2& right ) : slice( right.slice ), type( right.type )
697+ {
698+ return;
699+ }
700+
701+ bool IsMergeable( data_type type ) const
702+ {
703+ return ( this->type == type );
704+ }
705+
706+ void Update( eir::mathSlice <int> slice, data_type type )
707+ {
708+ this->slice = std::move( slice );
709+ }
710+
711+ void Remove( void )
712+ {
713+ return;
714+ }
715+
716+ const eir::mathSlice <int>& GetNodeSlice( void ) const
717+ {
718+ return this->slice;
719+ }
720+
721+ eir::mathSlice <int> slice;
722+ data_type type;
723+
724+ mutable RwListEntry <same_type_metadata_2> node;
725+ };
726+
727+ eir::SortedSliceSector <int, EirHeapAllocator, same_type_metadata_2> slices;
728+
729+ slices.Insert( { 2, 2 }, data_type::TYPE_0 );
730+ slices.Insert( { 4, 2 }, data_type::TYPE_1 );
731+ slices.Insert( { 6, 2 }, data_type::TYPE_0 );
732+ slices.Insert( { 8, 2 }, data_type::TYPE_1 );
733+ slices.Insert( { 10, 2 }, data_type::TYPE_0 );
734+
735+ RwList <same_type_metadata_2> audit_list;
736+
737+ for ( const same_type_metadata_2& data : slices )
738+ {
739+ if ( data.type == data_type::TYPE_1 )
740+ {
741+ LIST_APPEND( audit_list.root, data.node );
742+ }
743+ }
744+
745+ while ( LIST_EMPTY( audit_list.root ) == false )
746+ {
747+ same_type_metadata_2 *data = LIST_GETITEM( same_type_metadata_2, audit_list.root.next, node );
748+
749+ LIST_REMOVE( data->node );
750+
751+ slices.DetachData( data );
752+
753+ data->type = data_type::TYPE_0;
754+
755+ slices.RecommitData( data, data_type::TYPE_0 );
756+ }
757+
758+ // All TYPE_1 nodes should have turned to TYPE_0.
759+ // Thus only one slice should remain.
760+ assert( slices.GetSliceCount() == 1 );
761+ }
762+ printf( "ok.\n" );
763+
682764 printf( "testing sorted-slice-sector with object allocator..." );
683765 {
684766 eir::SortedSliceSector <size_t, EirHeapLinkAllocator> slices( eir::constr_with_alloc::DEFAULT, &globalHeapAlloc );
Show on old repository browser