• R/O
  • SSH
  • HTTPS

eirrepo: Commit


Commit MetaInfo

Revision168 (tree)
Time2018-12-20 02:09:51
Authorquiret

Log Message

- added eir::SortedSliceSector in preparation for real FileSystem buffered stream wrap implementation
- various improvements/new algorithms

Change Summary

Incremental Difference

--- common/sdk/AVLTree.h (revision 167)
+++ common/sdk/AVLTree.h (revision 168)
@@ -1030,6 +1030,10 @@
10301030 {
10311031 return this->root;
10321032 }
1033+ inline const AVLNode* GetRootNode( void ) const
1034+ {
1035+ return this->root;
1036+ }
10331037
10341038 // Returns the node whose value is just above or equal to the given value.
10351039 template <typename valueType>
@@ -1069,8 +1073,8 @@
10691073 }
10701074
10711075 // Returns the node that matches the given value.
1072- template <typename valueType>
1073- inline AVLNode* FindNode( const valueType& value )
1076+ template <typename customDispatcherType, typename valueType>
1077+ inline AVLNode* FindNodeCustom( const valueType& value )
10741078 {
10751079 AVLNode *curNode = this->root;
10761080
@@ -1077,7 +1081,7 @@
10771081 while ( curNode )
10781082 {
10791083 // Check which one to go for next.
1080- eir::eCompResult cmpRes = dispatcherType::CompareNodeWithValue( curNode, value );
1084+ eir::eCompResult cmpRes = customDispatcherType::CompareNodeWithValue( curNode, value );
10811085
10821086 if ( cmpRes == eir::eCompResult::LEFT_LESS )
10831087 {
@@ -1096,10 +1100,12 @@
10961100
10971101 return curNode;
10981102 }
1103+ template <typename valueType>
1104+ inline AVLNode* FindNode( const valueType& value ) { return FindNodeCustom <dispatcherType> ( value ); }
10991105
11001106 // Returns the node that matches the given value, const-equivalent.
1101- template <typename valueType>
1102- inline const AVLNode* FindNode( const valueType& value ) const
1107+ template <typename customDispatcherType, typename valueType>
1108+ inline const AVLNode* FindNodeCustom( const valueType& value ) const
11031109 {
11041110 const AVLNode *curNode = this->root;
11051111
@@ -1106,7 +1112,7 @@
11061112 while ( curNode )
11071113 {
11081114 // Check which one to go for next.
1109- eir::eCompResult cmpRes = dispatcherType::CompareNodeWithValue( curNode, value );
1115+ eir::eCompResult cmpRes = customDispatcherType::CompareNodeWithValue( curNode, value );
11101116
11111117 if ( cmpRes == eir::eCompResult::LEFT_LESS )
11121118 {
@@ -1125,7 +1131,64 @@
11251131
11261132 return curNode;
11271133 }
1134+ template <typename valueType>
1135+ inline const AVLNode* FindNode( const valueType& value ) const { return FindNodeCustom <dispatcherType> ( value ); }
11281136
1137+ // Finds the minimum node that matches certain criteria.
1138+ // Returning eCompResult::EQUAL indicates a match but in this function multiple nodes are allowed to be equal, forming
1139+ // classes of values.
1140+ // IMPORTANT: node classes are supposed to be contiguous! meaning there cannot be a node not in the class between two
1141+ // nodes that instead are.
1142+ template <typename callbackType>
1143+ inline AVLNode* FindMinimumNodeByCriteria( const callbackType& cb )
1144+ {
1145+ // NOTE: cb is a virtual "right value-span". it is pretty complicated but just roll with it.
1146+
1147+ // We first try to find any node in the class.
1148+ AVLNode *curNode = this->root;
1149+
1150+ while ( curNode )
1151+ {
1152+ eir::eCompResult cmpRes = cb( curNode );
1153+
1154+ if ( cmpRes == eir::eCompResult::LEFT_LESS )
1155+ {
1156+ curNode = curNode->right;
1157+ }
1158+ else if ( cmpRes == eir::eCompResult::LEFT_GREATER )
1159+ {
1160+ curNode = curNode->left;
1161+ }
1162+ else
1163+ {
1164+ // Found any node.
1165+ break;
1166+ }
1167+ }
1168+
1169+ if ( curNode != nullptr )
1170+ {
1171+ // Now walk until we reach the smallest.
1172+ while ( AVLNode *leftNode = curNode->left )
1173+ {
1174+ eir::eCompResult cmpRes = cb( leftNode );
1175+
1176+ if ( cmpRes == eir::eCompResult::EQUAL )
1177+ {
1178+ // Still in the class.
1179+ curNode = leftNode;
1180+ }
1181+ else
1182+ {
1183+ assert( cmpRes == eir::eCompResult::LEFT_LESS );
1184+ break;
1185+ }
1186+ }
1187+ }
1188+
1189+ return curNode;
1190+ }
1191+
11291192 // Should always succeed.
11301193 inline void Validate( void )
11311194 {
--- common/sdk/MemoryRaw.h (revision 167)
+++ common/sdk/MemoryRaw.h (revision 168)
@@ -13,6 +13,9 @@
1313 #ifndef _MEMORY_RAW_DEFS_
1414 #define _MEMORY_RAW_DEFS_
1515
16+#include <type_traits>
17+#include <limits>
18+
1619 #include "MacroUtils.h"
1720
1821 // Mathematically correct data slice logic.
@@ -267,7 +270,7 @@
267270 else if ( intResult == INTERSECT_BORDER_START )
268271 {
269272 // Just return the remainder.
270- size_t oneAfterSubEndOffset = ( subEndOffset + 1 );
273+ numberType oneAfterSubEndOffset = ( subEndOffset + 1 );
271274 const sliceOfData remainder( oneAfterSubEndOffset, ourEndOffset - oneAfterSubEndOffset );
272275
273276 cb( remainder, false );
@@ -372,4 +375,40 @@
372375 return ( ALIGN( (num), (sector), (sector) ) );
373376 }
374377
378+// Neighborhood function.
379+template <typename leftNumberType, typename rightNumberType>
380+AINLINE bool IsNumberInNeighborhood( const leftNumberType& left, const rightNumberType& right )
381+{
382+ if constexpr ( std::is_floating_point <leftNumberType>::value || std::is_floating_point <rightNumberType>::value )
383+ {
384+ return ( left == right );
385+ }
386+
387+ if ( std::is_integral <leftNumberType>::value && std::is_integral <rightNumberType>::value )
388+ {
389+ if ( left == right )
390+ {
391+ return true;
392+ }
393+
394+ if ( left > std::numeric_limits <leftNumberType>::min() )
395+ {
396+ if ( left - 1 == right )
397+ {
398+ return true;
399+ }
400+ }
401+
402+ if ( left < std::numeric_limits <leftNumberType>::max() )
403+ {
404+ if ( left + 1 == right )
405+ {
406+ return true;
407+ }
408+ }
409+ }
410+
411+ return false;
412+}
413+
375414 #endif //_MEMORY_RAW_DEFS_
\ No newline at end of file
--- common/sdk/SortedSliceSector.h (nonexistent)
+++ common/sdk/SortedSliceSector.h (revision 168)
@@ -0,0 +1,427 @@
1+/*****************************************************************************
2+*
3+* PROJECT: Eir SDK
4+* LICENSE: See LICENSE in the top level directory
5+* FILE: eirrepo/sdk/SortedSliceSector.h
6+* PURPOSE: Sorted intrusion-interval region of memory
7+*
8+* Find the Eir SDK at: https://osdn.net/projects/eirrepo/
9+* Multi Theft Auto is available from http://www.multitheftauto.com/
10+*
11+*****************************************************************************/
12+
13+// In a stream buffer you must remember regions that you wrote across a limited
14+// memory buffer. When intersecting non-convex shapes you do get a list of
15+// intervals. So you need a class that handles the building of intervals across
16+// dynamic operations.
17+
18+// The difference between eir::Set and eir::SortedSliceSector is that sets do
19+// check for equality only but SortedSliceSector does merge slices which
20+// overlap thus this class is more powerful.
21+
22+#ifndef _EIR_SORTED_SLICE_SECTOR_HEADER_
23+#define _EIR_SORTED_SLICE_SECTOR_HEADER_
24+
25+#include "MemoryRaw.h"
26+#include "AVLTree.h"
27+#include "eirutils.h"
28+#include "MetaHelpers.h"
29+#include "avlsetmaputil.h"
30+
31+namespace eir
32+{
33+
34+template <typename numberType>
35+struct SortedSliceSectorStdMetadata
36+{
37+ AINLINE SortedSliceSectorStdMetadata( sliceOfData <numberType> slice ) : slice( std::move( slice ) )
38+ {
39+ return;
40+ }
41+
42+ AINLINE void Update( sliceOfData <numberType> newSlice )
43+ {
44+ this->slice = std::move( newSlice );
45+ }
46+
47+ AINLINE void Remove( void )
48+ {
49+ return;
50+ }
51+
52+ AINLINE sliceOfData <numberType> GetNodeSlice( void ) const
53+ {
54+ return slice;
55+ }
56+
57+ AINLINE operator const sliceOfData <numberType>& ( void ) const
58+ {
59+ return slice;
60+ }
61+
62+private:
63+ sliceOfData <numberType> slice;
64+};
65+
66+template <typename numberType, typename allocatorType, typename metaDataType = SortedSliceSectorStdMetadata <numberType>>
67+struct SortedSliceSector
68+{
69+ // REQUIREMENTS FOR metaDataType TYPE:
70+ // * sectorSlice_t GetNodeSlice( void ) const;
71+ // * template <typename... updateArgs> void Update( const sectorSlice_t& newSlice, updateArgs... args );
72+
73+ typedef sliceOfData <numberType> sectorSlice_t;
74+
75+private:
76+ struct sliceNode
77+ {
78+ template <typename, typename, typename> friend struct SortedSliceSector;
79+
80+ // DO NOT CONSTRUCT OR DESTROY THIS CLASS OUTSIDE OF SortedSliceSector !
81+
82+ template <typename... constrArgs>
83+ AINLINE sliceNode( sectorSlice_t slice, constrArgs... args ) : metaData( std::move( slice ), std::forward <constrArgs> ( args )... )
84+ {
85+ return;
86+ }
87+ AINLINE sliceNode( const sliceNode& ) = delete;
88+ AINLINE sliceNode( sliceNode&& ) = delete;
89+
90+ AINLINE ~sliceNode( void )
91+ {
92+ return;
93+ }
94+
95+ AINLINE sliceNode& operator = ( const sliceNode& ) = delete;
96+ AINLINE sliceNode& operator = ( sliceNode&& ) = delete;
97+
98+ AINLINE sectorSlice_t GetNodeSlice( void ) const
99+ {
100+ return metaData.GetNodeSlice();
101+ }
102+
103+ private:
104+ metaDataType metaData;
105+ AVLNode node;
106+ };
107+
108+ INSTANCE_SUBSTRUCTCHECK( is_object );
109+
110+ static constexpr bool hasObjectAllocator = PERFORM_SUBSTRUCTCHECK( allocatorType, is_object );
111+
112+public:
113+ AINLINE SortedSliceSector( void )
114+ {
115+ return;
116+ }
117+
118+ template <typename... allocArgs>
119+ AINLINE SortedSliceSector( eir::constr_with_alloc _, allocArgs... args ) : data( 0, std::forward <allocArgs> ( args )... )
120+ {
121+ return;
122+ }
123+
124+ AINLINE SortedSliceSector( const SortedSliceSector& ) = delete;
125+ AINLINE SortedSliceSector( SortedSliceSector&& right ) : data( std::move( right.data ) )
126+ {
127+ return;
128+ }
129+ AINLINE ~SortedSliceSector( void )
130+ {
131+ // Clean up memory.
132+ while ( AVLNode *avlNode = this->data.avlSliceTree.GetRootNode() )
133+ {
134+ sliceNode *node = AVL_GETITEM( sliceNode, avlNode, node );
135+
136+ this->data.avlSliceTree.RemoveByNode( avlNode );
137+
138+ eir::dyn_del_struct <sliceNode> ( this->data.allocData, this, node );
139+ }
140+ }
141+
142+ AINLINE SortedSliceSector& operator = ( const SortedSliceSector& ) = delete;
143+ AINLINE SortedSliceSector& operator = ( SortedSliceSector&& right )
144+ {
145+ this->avlSliceTree = std::move( right.avlSliceTree );
146+
147+ return *this;
148+ }
149+
150+ template <typename... constrArgs>
151+ AINLINE void Insert( sectorSlice_t slice, constrArgs... args )
152+ {
153+ // Check if our request would overlap with anything.
154+ // If it would then we have to merge instead.
155+ AVLNode *avlBeginMergeWithNode = this->data.avlSliceTree.FindMinimumNodeByCriteria(
156+ [&]( AVLNode *leftNode )
157+ {
158+ return _CompareNodeWithSlice( leftNode, slice, true );
159+ });
160+
161+ if ( avlBeginMergeWithNode )
162+ {
163+ // Need to count in all nodes that actually do meet the criteria, that is by iterating.
164+ avlSliceTree_t::diff_node_iterator crit_iter( avlBeginMergeWithNode );
165+
166+ sliceNode *beginMergeWithNode = AVL_GETITEM( sliceNode, avlBeginMergeWithNode, node );
167+
168+ sectorSlice_t beginMergeSlice = beginMergeWithNode->GetNodeSlice();
169+
170+ // Need to collect the region minimum and maximum.
171+ numberType regionMin = beginMergeSlice.GetSliceStartPoint();
172+ numberType regionMax = beginMergeSlice.GetSliceEndPoint();
173+
174+ crit_iter.Increment();
175+
176+ while ( !crit_iter.IsEnd() )
177+ {
178+ sliceNode *mergeWithNode = AVL_GETITEM( sliceNode, crit_iter.Resolve(), node );
179+ sectorSlice_t mergeSlice = mergeWithNode->GetNodeSlice();
180+
181+ // Do we really have to merge?
182+ {
183+ eCompResult cmpRes = _CompareSlices( mergeSlice, slice, true );
184+
185+ if ( cmpRes != eCompResult::EQUAL )
186+ {
187+ break;
188+ }
189+ }
190+
191+ // Actually update the region maximum.
192+ regionMax = mergeSlice.GetSliceEndPoint();
193+
194+ crit_iter.Increment();
195+ }
196+
197+ // Now remove all nodes that intersect this region from the AVL tree.
198+ this->data.avlSliceTree.RemoveByNode( &beginMergeWithNode->node ); // important so we do not delete the memory.
199+ {
200+ sectorSlice_t intersectSlice = sectorSlice_t::fromOffsets( regionMin, regionMax );
201+
202+ while ( AVLNode *avlIntersectNode = this->data.avlSliceTree.FindNodeCustom <nodeWithoutNeighborComparator> ( intersectSlice ) )
203+ {
204+ this->data.avlSliceTree.RemoveByNode( avlIntersectNode );
205+
206+ // Also delete it.
207+ sliceNode *intersectNode = AVL_GETITEM( sliceNode, avlIntersectNode, node );
208+
209+ eir::dyn_del_struct <sliceNode> ( this->data.allocData, this, intersectNode );
210+ }
211+ }
212+
213+ sectorSlice_t newSlice = sectorSlice_t::fromOffsets(
214+ std::min( regionMin, slice.GetSliceStartPoint() ),
215+ std::max( regionMax, slice.GetSliceEndPoint() )
216+ );
217+
218+ beginMergeWithNode->metaData.Update( std::move( newSlice ), std::forward <constrArgs> ( args )... );
219+
220+#ifdef _DEBUG
221+ assert( this->data.avlSliceTree.IsNodeInsideTree( &beginMergeWithNode->node ) == false );
222+#endif //_DEBUG
223+
224+ // Since this node has been removed we must reinsert it.
225+ this->data.avlSliceTree.Insert( &beginMergeWithNode->node );
226+ }
227+ else
228+ {
229+ // Create a new node and insert it into the tree, because
230+ // we do not overlap/neighbor with anything.
231+ sliceNode *newNode = eir::dyn_new_struct <sliceNode> ( this->data.allocData, this, std::move( slice ), std::forward <constrArgs> ( args )... );
232+
233+ try
234+ {
235+ this->data.avlSliceTree.Insert( &newNode->node );
236+ }
237+ catch( ... )
238+ {
239+ eir::dyn_del_struct <sliceNode> ( this->data.allocData, this, newNode );
240+
241+ throw;
242+ }
243+ }
244+ }
245+
246+ template <typename... constrArgs>
247+ AINLINE void Remove( sectorSlice_t slice, constrArgs... args )
248+ {
249+ // While we find any intersection we remove areas from said nodes.
250+ while ( AVLNode *avlFoundNode = this->data.avlSliceTree.FindNodeCustom <nodeWithoutNeighborComparator> ( slice ) )
251+ {
252+ sliceNode *foundNode = AVL_GETITEM( sliceNode, avlFoundNode, node );
253+
254+ // Perform a subtract.
255+ sectorSlice_t nodeSlice = foundNode->GetNodeSlice();
256+
257+ bool didHaveFirst = false;
258+
259+ // Need to update our region.
260+ this->data.avlSliceTree.RemoveByNode( avlFoundNode );
261+
262+ nodeSlice.subtractRegion( slice,
263+ [&]( const sectorSlice_t& newSlice, bool isFirst )
264+ {
265+ if ( isFirst )
266+ {
267+ foundNode->metaData.Update( newSlice, args... );
268+
269+ this->data.avlSliceTree.Insert( avlFoundNode );
270+
271+ didHaveFirst = true;
272+ }
273+ else
274+ {
275+ // Must spawn a new node.
276+ sliceNode *newNode = eir::dyn_new_struct <sliceNode> ( this->data.allocData, this, newSlice, args... );
277+
278+ try
279+ {
280+ this->data.avlSliceTree.Insert( &newNode->node );
281+ }
282+ catch( ... )
283+ {
284+ eir::dyn_del_struct <sliceNode> ( this->data.allocData, this, newNode );
285+
286+ throw;
287+ }
288+ }
289+ });
290+
291+ if ( !didHaveFirst )
292+ {
293+ // Remove us.
294+ foundNode->metaData.Remove( args... );
295+
296+ eir::dyn_del_struct <sliceNode> ( this->data.allocData, this, foundNode );
297+ }
298+ }
299+ }
300+
301+ AINLINE bool HasIntersection( const sectorSlice_t& slice ) const
302+ {
303+ return ( this->data.avlSliceTree.FindNodeCustom <nodeWithoutNeighborComparator> ( slice ) != nullptr );
304+ }
305+
306+ AINLINE bool IsEmpty( void ) const
307+ {
308+ return ( this->data.avlSliceTree.GetRootNode() == nullptr );
309+ }
310+
311+private:
312+ static AINLINE eCompResult _CompareSlices( const sectorSlice_t& leftSlice, const sectorSlice_t& rightSlice, bool doCountInNeighbors )
313+ {
314+ // Here we can have an intersection, so treat any intersection as equality.
315+ sectorSlice_t::eIntersectionResult intResult = leftSlice.intersectWith( rightSlice );
316+
317+ if ( intResult == sectorSlice_t::INTERSECT_FLOATING_START )
318+ {
319+ if ( doCountInNeighbors )
320+ {
321+ // We are also the same if we are neighboring slices.
322+ if ( IsNumberInNeighborhood( leftSlice.GetSliceEndPoint(), rightSlice.GetSliceStartPoint() ) )
323+ {
324+ return eCompResult::EQUAL;
325+ }
326+ }
327+
328+ return eCompResult::LEFT_LESS;
329+ }
330+ if ( intResult == sectorSlice_t::INTERSECT_FLOATING_END )
331+ {
332+ if ( doCountInNeighbors )
333+ {
334+ if ( IsNumberInNeighborhood( rightSlice.GetSliceEndPoint(), leftSlice.GetSliceStartPoint() ) )
335+ {
336+ return eCompResult::EQUAL;
337+ }
338+ }
339+
340+ return eCompResult::LEFT_GREATER;
341+ }
342+
343+ // Have to treat this specially.
344+ return eCompResult::EQUAL;
345+ }
346+
347+ static AINLINE eCompResult _CompareNodeWithSlice( const AVLNode *left, const sectorSlice_t& rightSlice, bool doCountInNeighbors )
348+ {
349+ const sliceNode *leftNode = AVL_GETITEM( sliceNode, left, node );
350+
351+ sectorSlice_t leftSlice = leftNode->GetNodeSlice();
352+
353+ return _CompareSlices( leftSlice, rightSlice, doCountInNeighbors );
354+ }
355+
356+ struct metaAVLNodeDispatcher
357+ {
358+ static AINLINE eCompResult CompareNodes( const AVLNode *left, const AVLNode *right )
359+ {
360+ const sliceNode *leftNode = AVL_GETITEM( sliceNode, left, node );
361+ const sliceNode *rightNode = AVL_GETITEM( sliceNode, right, node );
362+
363+ sectorSlice_t leftSlice = leftNode->GetNodeSlice();
364+ sectorSlice_t rightSlice = rightNode->GetNodeSlice();
365+
366+ // We assume that nodes never intersect, thus this operation fits perfectly.
367+ return eir::DefaultValueCompare( leftSlice.GetSliceStartPoint(), rightSlice.GetSliceStartPoint() );
368+ }
369+ };
370+
371+ struct nodeWithoutNeighborComparator
372+ {
373+ static AINLINE eCompResult CompareNodeWithValue( const AVLNode *left, const sectorSlice_t& rightSlice )
374+ {
375+ return _CompareNodeWithSlice( left, rightSlice, false );
376+ }
377+ };
378+
379+ typedef AVLTree <metaAVLNodeDispatcher> avlSliceTree_t;
380+
381+ struct fields
382+ {
383+ mutable avlSliceTree_t avlSliceTree;
384+ };
385+
386+ size_opt <hasObjectAllocator, allocatorType, fields> data;
387+
388+public:
389+ // We want to offer standard-iterator looping over slices.
390+ typedef const sliceNode constSliceNode;
391+ typedef const SortedSliceSector constSortedSliceSector;
392+ MAKE_SETMAP_ITERATOR( iterator, constSortedSliceSector, constSliceNode, node, data.avlSliceTree, avlSliceTree_t );
393+
394+ struct end_std_iterator {};
395+ struct std_iterator
396+ {
397+ AINLINE std_iterator( iterator&& iter ) : iter( std::move( iter ) )
398+ {
399+ return;
400+ }
401+
402+ AINLINE bool operator != ( const end_std_iterator& ) const
403+ {
404+ return ( iter.IsEnd() == false );
405+ }
406+
407+ AINLINE std_iterator& operator ++ ( void )
408+ {
409+ iter.Increment();
410+ return *this;
411+ }
412+
413+ AINLINE const metaDataType& operator * ( void )
414+ {
415+ return iter.Resolve()->metaData;
416+ }
417+
418+ private:
419+ iterator iter;
420+ };
421+ AINLINE std_iterator begin( void ) const { return std_iterator( iterator( *this ) ); }
422+ AINLINE end_std_iterator end( void ) const { return end_std_iterator(); }
423+};
424+
425+}
426+
427+#endif //_EIR_SORTED_SLICE_SECTOR_HEADER_
\ No newline at end of file
--- unittests/src/main.cpp (revision 167)
+++ unittests/src/main.cpp (revision 168)
@@ -22,6 +22,7 @@
2222 extern void MULTISTRING_TESTS( void );
2323 extern void PATTERN_TEST( void );
2424 extern void NUMFORMAT_TESTS( void );
25+extern void SORTEDSLICESECTOR_TESTS( void );
2526
2627 #ifdef _WIN32
2728 // Shell extension test.
@@ -44,6 +45,7 @@
4445 MULTISTRING_TESTS();
4546 PATTERN_TEST();
4647 NUMFORMAT_TESTS();
48+ SORTEDSLICESECTOR_TESTS();
4749
4850 // Done.
4951 return 0;
--- unittests/src/sortedslicesector.cpp (nonexistent)
+++ unittests/src/sortedslicesector.cpp (revision 168)
@@ -0,0 +1,349 @@
1+#include <sdk/SortedSliceSector.h>
2+
3+#include "alloc_helper.hxx"
4+
5+void SORTEDSLICESECTOR_TESTS( void )
6+{
7+ // In hindsight it has proven a very good idea to include the SortedSliceSector into the well-testable
8+ // Eir SDK because the object is more complicated than I thought.
9+ // Though we had to anyway because math stuff is gonna use it, too (we also need a proven-working static
10+ // allocator).
11+
12+ size_t prevMemCount = globalHeapAlloc.GetStatistics().usedBytes;
13+
14+ printf( "testing number neighbors..." );
15+ {
16+ assert( IsNumberInNeighborhood( 1, 1 ) == true );
17+ assert( IsNumberInNeighborhood( 1, 2 ) == true );
18+ assert( IsNumberInNeighborhood( 1, 0 ) == true );
19+ assert( IsNumberInNeighborhood( 1u, 1 ) == true );
20+ assert( IsNumberInNeighborhood( 1, 1u ) == true );
21+ assert( IsNumberInNeighborhood( 1, 0u ) == true );
22+ assert( IsNumberInNeighborhood( 1u, 0 ) == true );
23+
24+ assert( IsNumberInNeighborhood( 1, 3 ) == false );
25+ assert( IsNumberInNeighborhood( 1u, 3u ) == false );
26+ assert( IsNumberInNeighborhood( 1, 3u ) == false );
27+
28+ assert( IsNumberInNeighborhood( 3.f, 3u ) == true );
29+ assert( IsNumberInNeighborhood( 3.f, 3 ) == true );
30+ assert( IsNumberInNeighborhood( 3.f, 2u ) == false );
31+ assert( IsNumberInNeighborhood( 3.f, 4u ) == false );
32+ }
33+ printf( "ok.\n" );
34+
35+ printf( "testing sorted-slice-sector construction..." );
36+ {
37+ eir::SortedSliceSector <int, EirHeapAllocator> slices;
38+
39+ assert( slices.IsEmpty() == true );
40+ }
41+ printf( "ok.\n" );
42+
43+ printf( "testing sorted-slice-sector basic insertion..." );
44+ {
45+ eir::SortedSliceSector <int, EirHeapAllocator> slices;
46+
47+ slices.Insert( { 4, 6 } );
48+
49+ assert( slices.HasIntersection( { 4, 6 } ) == true );
50+ }
51+ printf( "ok.\n" );
52+
53+ printf( "testing sorted-slice-sector for-each..." );
54+ {
55+ eir::SortedSliceSector <int, EirHeapAllocator> slices;
56+
57+ slices.Insert( { 5, 2 } );
58+ slices.Insert( { 17, 9 } );
59+ slices.Insert( { 10, 4 } );
60+ slices.Insert( { 1, 1 } );
61+
62+ size_t idx = 0;
63+
64+ for ( const sliceOfData <int>& slice : slices )
65+ {
66+ if ( idx == 0 )
67+ {
68+ assert( slice.GetSliceStartPoint() == 1 && slice.GetSliceEndPoint() == 1 );
69+ }
70+ else if ( idx == 1 )
71+ {
72+ assert( slice.GetSliceStartPoint() == 5 && slice.GetSliceEndPoint() == 6 );
73+ }
74+ else if ( idx == 2 )
75+ {
76+ assert( slice.GetSliceStartPoint() == 10 && slice.GetSliceEndPoint() == 13 );
77+ }
78+ else if ( idx == 3 )
79+ {
80+ assert( slice.GetSliceStartPoint() == 17 && slice.GetSliceEndPoint() == 25 );
81+ }
82+
83+ idx++;
84+ }
85+
86+ assert( idx == 4 );
87+ }
88+ printf( "ok.\n" );
89+
90+ printf( "testing sorted-slice-sector merging neighbor (integral)..." );
91+ {
92+ eir::SortedSliceSector <int, EirHeapAllocator> slices;
93+
94+ slices.Insert( { 0, 5 } );
95+ slices.Insert( { 5, 5 } );
96+
97+ for ( const sliceOfData <int>& slice : slices )
98+ {
99+ assert( slice.GetSliceStartPoint() == 0 && slice.GetSliceEndPoint() == 9 );
100+ }
101+ }
102+ printf( "ok.\n" );
103+
104+ printf( "testing sorted-slice-sector merging neighbor (floating-point)..." );
105+ {
106+ eir::SortedSliceSector <float, EirHeapAllocator> slices;
107+
108+ slices.Insert( sliceOfData <float>::fromOffsets( 0, 5 ) );
109+ slices.Insert( sliceOfData <float>::fromOffsets( 5, 10 ) );
110+
111+ for ( const sliceOfData <float>& slice : slices )
112+ {
113+ assert( slice.GetSliceStartPoint() == 0 && slice.GetSliceEndPoint() == 10 );
114+ }
115+ }
116+ printf( "ok.\n" );
117+
118+ printf( "testing sorted-slice-sector incremental insertion (integral)..." );
119+ {
120+ eir::SortedSliceSector <size_t, EirHeapAllocator> slices;
121+
122+ static constexpr size_t NUM_INSERT = 100;
123+
124+ for ( size_t n = 0; n < NUM_INSERT; n++ )
125+ {
126+ slices.Insert( { n, 1 } );
127+ }
128+
129+ for ( sliceOfData <size_t> slice : slices )
130+ {
131+ assert( slice.GetSliceStartPoint() == 0 && slice.GetSliceEndPoint() == ( NUM_INSERT - 1 ) );
132+ }
133+ }
134+ printf( "ok.\n" );
135+
136+ printf( "testing sorted-slice-sector worst-case-merge insertion (integral)..." );
137+ {
138+ eir::SortedSliceSector <size_t, EirHeapAllocator> slices;
139+
140+ static constexpr size_t NUM_INSERT = 200;
141+
142+ for ( size_t n = 0; n < NUM_INSERT; n += 2 )
143+ {
144+ slices.Insert( { n, 1 } );
145+ }
146+
147+ for ( size_t n = 1; n < NUM_INSERT; n += 2 )
148+ {
149+ slices.Insert( { n, 1 } );
150+ }
151+
152+ for ( sliceOfData <size_t> slice : slices )
153+ {
154+ assert( slice.GetSliceStartPoint() == 0 && slice.GetSliceEndPoint() == ( NUM_INSERT - 1 ) );
155+ }
156+ }
157+ printf( "ok.\n" );
158+
159+ printf( "testing sorted-slice-sector worst-case-merge insertion backward (integral)..." );
160+ {
161+ eir::SortedSliceSector <size_t, EirHeapAllocator> slices;
162+
163+ static constexpr size_t NUM_INSERT = 125;
164+
165+ for ( size_t n = 0; n < NUM_INSERT; n += 2 )
166+ {
167+ slices.Insert( { n, 1 } );
168+ }
169+
170+ for ( size_t n = 1; n < NUM_INSERT; n += 2 )
171+ {
172+ slices.Insert( { NUM_INSERT - 1 - n, 1 } );
173+ }
174+
175+ for ( sliceOfData <size_t> slice : slices )
176+ {
177+ assert( slice.GetSliceStartPoint() == 0 && slice.GetSliceEndPoint() == ( NUM_INSERT - 1 ) );
178+ }
179+ }
180+ printf( "ok.\n" );
181+
182+ printf( "testing sorted-slice-sector merge all-in-one (integral)..." );
183+ {
184+ eir::SortedSliceSector <size_t, EirHeapAllocator> slices;
185+
186+ static constexpr size_t NUM_INSERT = 185;
187+
188+ for ( size_t n = 0; n < NUM_INSERT; n += 2 )
189+ {
190+ slices.Insert( { n, 1 } );
191+ }
192+
193+ slices.Insert( { 0, NUM_INSERT } );
194+
195+ for ( sliceOfData <size_t> slice : slices )
196+ {
197+ assert( slice.GetSliceStartPoint() == 0 && slice.GetSliceEndPoint() == ( NUM_INSERT - 1 ) );
198+ }
199+ }
200+ printf( "ok.\n" );
201+
202+ printf( "testing sorted-slice-sector with custom metadata..." );
203+ {
204+ struct some_metadata
205+ {
206+ some_metadata( sliceOfData <size_t> newSlice, bool *hasCreated ) : slice( std::move( newSlice ) )
207+ {
208+ *hasCreated = true;
209+ }
210+
211+ void Update( sliceOfData <size_t> newSlice, bool *hasUpdated )
212+ {
213+ *hasUpdated = true;
214+
215+ this->slice = std::move( newSlice );
216+ }
217+
218+ void Remove( bool *hasRemoved )
219+ {
220+ *hasRemoved = true;
221+ }
222+
223+ sliceOfData <size_t> GetNodeSlice( void ) const
224+ {
225+ return slice;
226+ }
227+
228+ sliceOfData <size_t> slice;
229+ };
230+
231+ eir::SortedSliceSector <size_t, EirHeapAllocator, some_metadata> slices;
232+
233+ bool hasCreated = false;
234+
235+ slices.Insert( { 0, 5 }, &hasCreated );
236+
237+ assert( hasCreated == true );
238+
239+ hasCreated = false;
240+
241+ slices.Insert( { 5, 5 }, &hasCreated );
242+
243+ assert( hasCreated == true );
244+
245+ for ( const some_metadata& data : slices )
246+ {
247+ assert( data.slice.GetSliceStartPoint() == 0 && data.slice.GetSliceEndPoint() == 9 );
248+ }
249+
250+ hasCreated = false;
251+
252+ slices.Remove( { 0, 10 }, &hasCreated );
253+
254+ assert( hasCreated == true );
255+ }
256+ printf( "ok.\n" );
257+
258+ printf( "testing sorted-slice-sector insert in-the-middle (integral)..." );
259+ {
260+ eir::SortedSliceSector <size_t, EirHeapAllocator> slices;
261+
262+ slices.Insert( { 0, 2 } );
263+ slices.Insert( { 3, 2 } );
264+ slices.Insert( { 6, 2 } );
265+ slices.Insert( { 9, 2 } );
266+ slices.Insert( { 12, 2 } );
267+
268+ slices.Insert( { 3, 8 } );
269+
270+ size_t idx = 0;
271+
272+ for ( const sliceOfData <size_t>& slice : slices )
273+ {
274+ if ( idx == 0 )
275+ {
276+ assert( slice.GetSliceStartPoint() == 0 && slice.GetSliceEndPoint() == 1 );
277+ }
278+ else if ( idx == 1 )
279+ {
280+ assert( slice.GetSliceStartPoint() == 3 && slice.GetSliceEndPoint() == 10 );
281+ }
282+ else if ( idx == 2 )
283+ {
284+ assert( slice.GetSliceStartPoint() == 12 && slice.GetSliceEndPoint() == 13 );
285+ }
286+
287+ idx++;
288+ }
289+
290+ assert( idx == 3 );
291+ }
292+ printf( "ok.\n" );
293+
294+ printf( "testing sorted-slice-sector insert and remove..." );
295+ {
296+ eir::SortedSliceSector <int, EirHeapAllocator> slices;
297+
298+ assert( slices.IsEmpty() == true );
299+
300+ slices.Insert( { 3, 3 } );
301+
302+ assert( slices.IsEmpty() == false );
303+
304+ slices.Remove( { 3, 3 } );
305+
306+ assert( slices.IsEmpty() == true );
307+ }
308+ printf( "ok.\n" );
309+
310+ printf( "testing sorted-slice-sector remove from middle..." );
311+ {
312+ eir::SortedSliceSector <int, EirHeapAllocator> slices;
313+
314+ slices.Insert( { 0, 10 } );
315+ slices.Remove( { 2, 6 } );
316+
317+ size_t idx = 0;
318+
319+ for ( const sliceOfData <int>& slice : slices )
320+ {
321+ if ( idx == 0 )
322+ {
323+ assert( slice.GetSliceStartPoint() == 0 && slice.GetSliceEndPoint() == 1 );
324+ }
325+ else if ( idx == 1 )
326+ {
327+ assert( slice.GetSliceStartPoint() == 8 && slice.GetSliceEndPoint() == 9 );
328+ }
329+
330+ idx++;
331+ }
332+
333+ assert( idx == 2 );
334+ }
335+ printf( "ok.\n" );
336+
337+ printf( "testing sorted-slice-sector with object allocator..." );
338+ {
339+ eir::SortedSliceSector <size_t, EirHeapLinkAllocator> slices( eir::constr_with_alloc::DEFAULT, &globalHeapAlloc );
340+
341+ slices.Insert( { 1, 4 } );
342+ slices.Remove( { 3, 1 } );
343+
344+ assert( slices.IsEmpty() == false );
345+ }
346+ printf( "ok.\n" );
347+
348+ assert( globalHeapAlloc.GetStatistics().usedBytes == prevMemCount );
349+}
\ No newline at end of file
Show on old repository browser