• R/O
  • SSH
  • HTTPS

eirrepo: Commit


Commit MetaInfo

Revision177 (tree)
Time2018-12-26 23:17:33
Authorquiret

Log Message

- bugfix for the subtractRegion method of eir::mathSlice
- added support for "IsMergeable" method of eir::SortedSliceSector metaData; now only fitting things will merge (good for different byte-states on data buffers)

Change Summary

Incremental Difference

--- common/sdk/MathSlice.h (revision 176)
+++ common/sdk/MathSlice.h (revision 177)
@@ -770,6 +770,11 @@
770770 return ( result == INTERSECT_FLOATING_START || result == INTERSECT_FLOATING_END );
771771 }
772772
773+AINLINE bool isCoveredIntersect( eIntersectionResult result ) noexcept
774+{
775+ return ( result == INTERSECT_EQUAL || result == INTERSECT_INSIDE );
776+}
777+
773778 // Representation of a mathematical interval.
774779 template <typename numberType>
775780 class mathSlice
@@ -883,7 +888,7 @@
883888 AINLINE eIntersectionResult intersectWith( const mathSlice& right ) const noexcept
884889 {
885890 // Make sure the slice has a valid size.
886- if ( this->IsEmpty() == false )
891+ if ( this->IsEmpty() == false && right.IsEmpty() == false )
887892 {
888893 // Get generic stuff.
889894 lowerBound <numberType> sliceStartA = this->startBound;
@@ -1027,7 +1032,7 @@
10271032 // Just return the remainder.
10281033 const mathSlice remainder = fromOffsets( subEndBound.get_value(), ourEndBound.get_value(), !subEndBound.is_included(), ourEndBound.is_included() );
10291034
1030- cb( remainder, false );
1035+ cb( remainder, true );
10311036 }
10321037 else if ( intResult == INTERSECT_BORDER_END )
10331038 {
--- common/sdk/SortedSliceSector.h (revision 176)
+++ common/sdk/SortedSliceSector.h (revision 177)
@@ -14,6 +14,8 @@
1414 // memory buffer. When intersecting non-convex shapes you do get a list of
1515 // intervals. So you need a class that handles the building of intervals across
1616 // dynamic operations.
17+// When merging source code conflicts you have regions/intervals of code/strings
18+// that have to merged based on ratings/user choice.
1719
1820 // The difference between eir::Set and eir::SortedSliceSector is that sets do
1921 // check for equality only but SortedSliceSector does merge slices which
@@ -39,6 +41,11 @@
3941 return;
4042 }
4143
44+ AINLINE bool IsMergeable( void ) const
45+ {
46+ return true;
47+ }
48+
4249 AINLINE void Update( mathSlice <numberType> newSlice )
4350 {
4451 this->slice = std::move( newSlice );
@@ -54,6 +61,7 @@
5461 return slice;
5562 }
5663
64+ // Optional helper.
5765 AINLINE operator const mathSlice <numberType>& ( void ) const
5866 {
5967 return slice;
@@ -68,6 +76,8 @@
6876 {
6977 // REQUIREMENTS FOR metaDataType TYPE:
7078 // * sectorSlice_t GetNodeSlice( void ) const;
79+ // * template <typename... systemArgs> void Remove( systemArgs... args );
80+ // * template <typename... updateArgs> bool IsMergeable( updateArgs... args ) const;
7181 // * template <typename... updateArgs> void Update( const sectorSlice_t& newSlice, updateArgs... args );
7282
7383 typedef mathSlice <numberType> sectorSlice_t;
@@ -150,10 +160,6 @@
150160 template <typename... constrArgs>
151161 AINLINE void Insert( sectorSlice_t slice, constrArgs... args )
152162 {
153- // We are not going to insert empty slices.
154- if ( slice.IsEmpty() )
155- return;
156-
157163 // Check if our request would overlap with anything.
158164 // If it would then we have to merge instead.
159165 AVLNode *avlBeginMergeWithNode = this->data.avlSliceTree.FindMinimumNodeByCriteria(
@@ -164,55 +170,180 @@
164170
165171 if ( avlBeginMergeWithNode )
166172 {
167- // Need to count in all nodes that actually do meet the criteria, that is by iterating.
168- sliceNode *beginMergeWithNode = AVL_GETITEM( sliceNode, avlBeginMergeWithNode, node );
173+ // Collect the region that our new slice should be at.
174+ lowerBound <numberType> regionMin = slice.GetSliceStartBound();
175+ upperBound <numberType> regionMax = slice.GetSliceEndBound();
169176
170- // Need to collect the region minimum and maximum.
171- lowerBound <numberType> regionMin = beginMergeWithNode->GetNodeSlice().GetSliceStartBound();
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.
172181
173- AVLNode *avlEndMergeWithNode = this->data.avlSliceTree.FindMaximumNodeByCriteria(
174- [&]( AVLNode *leftNode )
182+ sliceNode *hostOfMerge = nullptr; // could find a node that is willing to merge, so pick it as memory.
183+ sectorSlice_t hostRegion;
184+
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;
175188 {
176- return _CompareNodeWithSlice( leftNode, slice, true );
177- });
189+ AVLNode *avlIntersectNode = avlBeginMergeWithNode;
190+ bool hasIntersectNode = true;
178191
179- assert( avlEndMergeWithNode != nullptr );
192+ while ( true )
193+ {
194+ // To remove certain redundancy checking.
195+ if ( !hasIntersectNode )
196+ {
197+ avlIntersectNode = this->data.avlSliceTree.FindMinimumNodeByCriteria(
198+ [&]( AVLNode *leftNode )
199+ {
200+ return _CompareNodeWithSlice( leftNode, slice, true );
201+ });
180202
181- sliceNode *endMergeWithNode = AVL_GETITEM( sliceNode, avlEndMergeWithNode, node );
203+ if ( avlIntersectNode == nullptr )
204+ {
205+ break;
206+ }
182207
183- upperBound <numberType> regionMax = endMergeWithNode->GetNodeSlice().GetSliceEndBound();
208+ hasIntersectNode = true;
209+ }
184210
185- // Now remove all nodes that intersect this region from the AVL tree.
186- this->data.avlSliceTree.RemoveByNode( avlBeginMergeWithNode ); // important so we do not delete the memory.
187- {
188- sectorSlice_t intersectSlice = sectorSlice_t::fromBounds( regionMin, regionMax );
189-
190- while ( AVLNode *avlIntersectNode = this->data.avlSliceTree.FindNodeCustom <nodeWithoutNeighborComparator> ( intersectSlice ) )
191- {
211+ // Remove it so we are done processing it.
192212 this->data.avlSliceTree.RemoveByNode( avlIntersectNode );
193213
194- // Also delete it.
214+ // Can we merge with this node?
195215 sliceNode *intersectNode = AVL_GETITEM( sliceNode, avlIntersectNode, node );
196216
197- eir::dyn_del_struct <sliceNode> ( this->data.allocData, this, intersectNode );
198- }
199- }
217+ sectorSlice_t intersectSlice = intersectNode->GetNodeSlice();
200218
201- sectorSlice_t newSlice = sectorSlice_t::fromBounds(
202- std::min( regionMin, slice.GetSliceStartBound() ),
203- std::max( regionMax, slice.GetSliceEndBound() )
204- );
219+ if ( intersectNode->metaData.IsMergeable( args... ) )
220+ {
221+ // Update our merge region.
222+ if ( intersectSlice.GetSliceStartBound() < regionMin )
223+ {
224+ regionMin = intersectSlice.GetSliceStartBound();
225+ }
205226
206- beginMergeWithNode->metaData.Update( std::move( newSlice ), std::forward <constrArgs> ( args )... );
227+ if ( regionMax < intersectSlice.GetSliceEndBound() )
228+ {
229+ regionMax = intersectSlice.GetSliceEndBound();
230+ }
207231
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+ }
244+ }
245+ else
246+ {
247+ // If not then we need to subtract it later, if we would not disappear of course.
248+ eIntersectionResult intResult = intersectSlice.intersectWith( slice );
249+
250+ bool hasRegistered = false;
251+
252+ if ( isCoveredIntersect( intResult ) == false )
253+ {
208254 #ifdef _DEBUG
209- assert( this->data.avlSliceTree.IsNodeInsideTree( avlBeginMergeWithNode ) == false );
255+ assert( numNodesToSubtract < 2 );
210256 #endif //_DEBUG
211257
258+ if ( numNodesToSubtract < 2 )
259+ {
260+ nodesToSubtract[ numNodesToSubtract ] = intersectNode;
261+ nodesToSubtractSlices[ numNodesToSubtract ] = intersectSlice;
262+
263+ numNodesToSubtract++;
264+
265+ hasRegistered = true;
266+ }
267+ }
268+
269+ // Either if we are covered or there was an error (graceful handling).
270+ if ( hasRegistered == false )
271+ {
272+ eir::dyn_del_struct <sliceNode> ( this->data.allocData, this, intersectNode );
273+ }
274+ }
275+
276+ // Go to next node.
277+ avlIntersectNode = nullptr;
278+ hasIntersectNode = false;
279+ }
280+ }
281+
282+ // Construct the slice of the merge region we decided on.
283+ sectorSlice_t newSlice = sectorSlice_t::fromBounds( regionMin, regionMax );
284+
285+ // Put in the other slices after subtraction.
286+ for ( size_t n = 0; n < numNodesToSubtract; n++ )
287+ {
288+ sliceNode *subtractNode = nodesToSubtract[ n ];
289+ sectorSlice_t subtractSlice = nodesToSubtractSlices[ n ];
290+
291+ bool hasFirst = false;
292+
293+ subtractSlice.subtractRegion( newSlice,
294+ [&]( const sectorSlice_t& remainder, bool isFirst )
295+ {
296+ sliceNode *insertToTreeNode = nullptr;
297+
298+ if ( isFirst )
299+ {
300+ // Did the validity region actually change?
301+ if ( subtractSlice != remainder )
302+ {
303+ // Set the new validity region.
304+ subtractNode->metaData.Update( remainder, args... );
305+ }
306+
307+ // Reinsert into the tree.
308+ insertToTreeNode = subtractNode;
309+
310+ hasFirst = true;
311+ }
312+ else
313+ {
314+ // Spawn a new node.
315+ insertToTreeNode = eir::dyn_new_struct <sliceNode> ( this->data.allocData, this, remainder, args... );
316+ }
317+
318+ this->data.avlSliceTree.Insert( &insertToTreeNode->node );
319+ });
320+
321+ if ( !hasFirst )
322+ {
323+ // Error handling, just in case (graceful).
324+ eir::dyn_del_struct <sliceNode> ( this->data.allocData, this, subtractNode );
325+ }
326+ }
327+
328+ // Put in our new node with the arguments forwarded-in.
329+ if ( hostOfMerge )
330+ {
331+ // Did the region actually change?
332+ if ( hostRegion != newSlice )
333+ {
334+ hostOfMerge->metaData.Update( std::move( newSlice ), std::forward <constrArgs> ( args )... );
335+ }
336+ }
337+ else
338+ {
339+ // Allocate a new node.
340+ hostOfMerge = eir::dyn_new_struct <sliceNode> ( this->data.allocData, this, std::move( newSlice ), std::forward <constrArgs> ( args )... );
341+ }
342+
212343 // Since this node has been removed we must reinsert it.
213- this->data.avlSliceTree.Insert( avlBeginMergeWithNode );
344+ this->data.avlSliceTree.Insert( &hostOfMerge->node );
214345 }
215- else
346+ else if ( slice.IsEmpty() == false ) // need to check because we could actually get empty requests.
216347 {
217348 // Create a new node and insert it into the tree, because
218349 // we do not overlap/neighbor with anything.
@@ -357,10 +488,6 @@
357488 template <typename callbackType>
358489 AINLINE void ScanSharedSlices( sectorSlice_t sliceShared, const callbackType& cb, bool includeNotPresent = false, bool availableSliceWhole = false )
359490 {
360- // Nothing to do if empty.
361- if ( sliceShared.IsEmpty() )
362- return;
363-
364491 AVLNode *avlBeginNode = this->data.avlSliceTree.FindMinimumNodeByCriteria(
365492 [&]( AVLNode *leftNode )
366493 {
@@ -459,6 +586,26 @@
459586 // Here we can have an intersection, so treat any intersection as equality.
460587 eir::eIntersectionResult intResult = leftSlice.intersectWith( rightSlice );
461588
589+ if ( intResult == eir::INTERSECT_UNKNOWN )
590+ {
591+ // Let's make ourselves more robust to hardware math errors and stuff.
592+ bool isLeftEmpty = leftSlice.IsEmpty();
593+ bool isRightEmpty = rightSlice.IsEmpty();
594+
595+ // Those empty cases are going to treat well empty-slice requests.
596+ if ( isLeftEmpty && !isRightEmpty )
597+ {
598+ return eCompResult::LEFT_LESS;
599+ }
600+ if ( isRightEmpty && !isLeftEmpty )
601+ {
602+ return eCompResult::LEFT_GREATER;
603+ }
604+
605+ // No idea. Just return something diverting.
606+ // As long as we do not return EQUAL it is fine.
607+ return eCompResult::LEFT_LESS;
608+ }
462609 if ( intResult == eir::INTERSECT_FLOATING_START )
463610 {
464611 if ( doCountInNeighbors )
--- unittests/src/sortedslicesector.cpp (revision 176)
+++ unittests/src/sortedslicesector.cpp (revision 177)
@@ -50,6 +50,22 @@
5050 }
5151 printf( "ok.\n" );
5252
53+ printf( "testing sorted-slice-sector no empty insertion..." );
54+ {
55+ eir::SortedSliceSector <int, EirHeapAllocator> slices;
56+
57+ slices.Insert( { 0, 0 } );
58+
59+ assert( slices.IsEmpty() == true );
60+
61+ slices.Insert( { 3, 2 } );
62+ slices.Insert( { 4, 0 } );
63+ slices.Insert( { 7, 0 } );
64+
65+ assert( slices.GetSliceCount() == 1 );
66+ }
67+ printf( "ok.\n" );
68+
5369 printf( "testing sorted-slice-sector clear..." );
5470 {
5571 eir::SortedSliceSector <int, EirHeapAllocator> slices;
@@ -257,6 +273,11 @@
257273 *hasCreated = true;
258274 }
259275
276+ bool IsMergeable( bool *isMergeable ) const
277+ {
278+ return true;
279+ }
280+
260281 void Update( sliceOfData <size_t> newSlice, bool *hasUpdated )
261282 {
262283 *hasUpdated = true;
@@ -525,6 +546,139 @@
525546 }
526547 printf( "ok.\n" );
527548
549+ printf( "testing sorted-slice-sector not-merging metadata..." );
550+ {
551+ struct non_merge_metadata
552+ {
553+ non_merge_metadata( eir::mathSlice <size_t> slice ) : slice( slice )
554+ {
555+ return;
556+ }
557+
558+ bool IsMergeable( void ) const
559+ {
560+ return false;
561+ }
562+
563+ void Update( eir::mathSlice <size_t> slice )
564+ {
565+ this->slice = std::move( slice );
566+ }
567+
568+ void Remove( void )
569+ {
570+ return;
571+ }
572+
573+ const eir::mathSlice <size_t>& GetNodeSlice( void ) const
574+ {
575+ return this->slice;
576+ }
577+
578+ eir::mathSlice <size_t> slice;
579+ };
580+
581+ eir::SortedSliceSector <size_t, EirHeapAllocator, non_merge_metadata> slices;
582+
583+ slices.Insert( { 5, 4 } );
584+
585+ assert( slices.GetSliceCount() == 1 );
586+
587+ slices.Insert( { 4, 3 } );
588+
589+ assert( slices.GetSliceCount() == 2 );
590+
591+ slices.Insert( { 4, 5 } );
592+
593+ assert( slices.GetSliceCount() == 1 );
594+
595+ slices.Insert( { 5, 3 } );
596+
597+ assert( slices.GetSliceCount() == 3 );
598+
599+ slices.Remove( { 5, 3 } );
600+
601+ assert( slices.GetSliceCount() == 2 );
602+
603+ slices.Insert( { 5, 3 } );
604+
605+ size_t idx = 0;
606+
607+ for ( const non_merge_metadata& data : slices )
608+ {
609+ if ( idx == 0 )
610+ {
611+ assert( data.slice == eir::mathSlice <size_t>::fromOffsets( 4, 4 ) );
612+ }
613+ else if ( idx == 1 )
614+ {
615+ assert( data.slice == eir::mathSlice <size_t>::fromOffsets( 5, 7 ) );
616+ }
617+ else if ( idx == 2 )
618+ {
619+ assert( data.slice == eir::mathSlice <size_t>::fromOffsets( 8, 8 ) );
620+ }
621+
622+ idx++;
623+ }
624+
625+ assert( idx == 3 );
626+ }
627+ printf( "ok.\n" );
628+
629+ printf( "testing sorted-slice-sector merging same-type metadata..." );
630+ {
631+ enum class data_type
632+ {
633+ TYPE_0,
634+ TYPE_1
635+ };
636+
637+ struct same_type_metadata
638+ {
639+ same_type_metadata( eir::mathSlice <float> slice, data_type type ) : slice( std::move( slice ) ), type( type )
640+ {
641+ return;
642+ }
643+
644+ bool IsMergeable( data_type type ) const
645+ {
646+ return ( this->type == type );
647+ }
648+
649+ void Update( eir::mathSlice <float> slice, data_type type )
650+ {
651+ this->slice = std::move( slice );
652+ }
653+
654+ void Remove( void )
655+ {
656+ return;
657+ }
658+
659+ const eir::mathSlice <float>& GetNodeSlice( void ) const
660+ {
661+ return this->slice;
662+ }
663+
664+ eir::mathSlice <float> slice;
665+ data_type type;
666+ };
667+
668+ eir::SortedSliceSector <float, EirHeapAllocator, same_type_metadata> slices;
669+
670+ slices.Insert( { 2, 2 }, data_type::TYPE_0 );
671+ slices.Insert( { 4, 2 }, data_type::TYPE_1 );
672+
673+ assert( slices.GetSliceCount() == 2 );
674+
675+ slices.Insert( { 0, 2 }, data_type::TYPE_0 );
676+ slices.Insert( { 6, 2 }, data_type::TYPE_1 );
677+
678+ assert( slices.GetSliceCount() == 2 );
679+ }
680+ printf( "ok.\n" );
681+
528682 printf( "testing sorted-slice-sector with object allocator..." );
529683 {
530684 eir::SortedSliceSector <size_t, EirHeapLinkAllocator> slices( eir::constr_with_alloc::DEFAULT, &globalHeapAlloc );
Show on old repository browser