• R/O
  • SSH
  • HTTPS

eirrepo: Commit


Commit MetaInfo

Revision170 (tree)
Time2018-12-20 19:29:08
Authorquiret

Log Message

- optimized the eir::SortedSliceSector::Insert method a little by doing two tree-path-scans instead of iterating through all items (min and max of region)

Change Summary

Incremental Difference

--- common/sdk/AVLTree.h (revision 169)
+++ common/sdk/AVLTree.h (revision 170)
@@ -1134,17 +1134,10 @@
11341134 template <typename valueType>
11351135 inline const AVLNode* FindNode( const valueType& value ) const { return FindNodeCustom <dispatcherType> ( value ); }
11361136
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.
1137+private:
11421138 template <typename callbackType>
1143- inline AVLNode* FindMinimumNodeByCriteria( const callbackType& cb )
1139+ AINLINE AVLNode* FindAnyNodeByCriteria( const callbackType& cb )
11441140 {
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.
11481141 AVLNode *curNode = this->root;
11491142
11501143 while ( curNode )
@@ -1166,6 +1159,23 @@
11661159 }
11671160 }
11681161
1162+ return curNode;
1163+ }
1164+
1165+public:
1166+ // Finds the minimum node that matches certain criteria.
1167+ // Returning eCompResult::EQUAL indicates a match but in this function multiple nodes are allowed to be equal, forming
1168+ // classes of values.
1169+ // IMPORTANT: node classes are supposed to be contiguous! meaning there cannot be a node not in the class between two
1170+ // nodes that instead are.
1171+ template <typename callbackType>
1172+ inline AVLNode* FindMinimumNodeByCriteria( const callbackType& cb )
1173+ {
1174+ // NOTE: cb is a virtual "right value-span". it is pretty complicated but just roll with it.
1175+
1176+ // We first try to find any node in the class.
1177+ AVLNode *curNode = FindAnyNodeByCriteria( cb );
1178+
11691179 if ( curNode != nullptr )
11701180 {
11711181 // Now walk until we reach the smallest.
@@ -1189,6 +1199,32 @@
11891199 return curNode;
11901200 }
11911201
1202+ template <typename callbackType>
1203+ inline AVLNode* FindMaximumNodeByCriteria( const callbackType& cb )
1204+ {
1205+ AVLNode *curNode = FindAnyNodeByCriteria( cb );
1206+
1207+ if ( curNode != nullptr )
1208+ {
1209+ while ( AVLNode *rightNode = curNode->right )
1210+ {
1211+ eir::eCompResult cmpRes = cb( rightNode );
1212+
1213+ if ( cmpRes == eir::eCompResult::EQUAL )
1214+ {
1215+ curNode = rightNode;
1216+ }
1217+ else
1218+ {
1219+ assert( cmpRes == eir::eCompResult::LEFT_GREATER );
1220+ break;
1221+ }
1222+ }
1223+ }
1224+
1225+ return curNode;
1226+ }
1227+
11921228 // Should always succeed.
11931229 inline void Validate( void )
11941230 {
--- common/sdk/SortedSliceSector.h (revision 169)
+++ common/sdk/SortedSliceSector.h (revision 170)
@@ -160,44 +160,26 @@
160160
161161 if ( avlBeginMergeWithNode )
162162 {
163- // TODO: maybe optimize this by doing another maximum-by-criteria scan.
164-
165163 // Need to count in all nodes that actually do meet the criteria, that is by iterating.
166- avlSliceTree_t::diff_node_iterator crit_iter( avlBeginMergeWithNode );
167-
168164 sliceNode *beginMergeWithNode = AVL_GETITEM( sliceNode, avlBeginMergeWithNode, node );
169165
170- sectorSlice_t beginMergeSlice = beginMergeWithNode->GetNodeSlice();
171-
172166 // Need to collect the region minimum and maximum.
173- numberType regionMin = beginMergeSlice.GetSliceStartPoint();
174- numberType regionMax = beginMergeSlice.GetSliceEndPoint();
167+ numberType regionMin = beginMergeWithNode->GetNodeSlice().GetSliceStartPoint();
175168
176- crit_iter.Increment();
177-
178- while ( !crit_iter.IsEnd() )
169+ AVLNode *avlEndMergeWithNode = this->data.avlSliceTree.FindMaximumNodeByCriteria(
170+ [&]( AVLNode *leftNode )
179171 {
180- sliceNode *mergeWithNode = AVL_GETITEM( sliceNode, crit_iter.Resolve(), node );
181- sectorSlice_t mergeSlice = mergeWithNode->GetNodeSlice();
172+ return _CompareNodeWithSlice( leftNode, slice, true );
173+ });
182174
183- // Do we really have to merge?
184- {
185- eCompResult cmpRes = _CompareSlices( mergeSlice, slice, true );
175+ assert( avlEndMergeWithNode != nullptr );
186176
187- if ( cmpRes != eCompResult::EQUAL )
188- {
189- break;
190- }
191- }
177+ sliceNode *endMergeWithNode = AVL_GETITEM( sliceNode, avlEndMergeWithNode, node );
192178
193- // Actually update the region maximum.
194- regionMax = mergeSlice.GetSliceEndPoint();
179+ numberType regionMax = endMergeWithNode->GetNodeSlice().GetSliceEndPoint();
195180
196- crit_iter.Increment();
197- }
198-
199181 // Now remove all nodes that intersect this region from the AVL tree.
200- this->data.avlSliceTree.RemoveByNode( &beginMergeWithNode->node ); // important so we do not delete the memory.
182+ this->data.avlSliceTree.RemoveByNode( avlBeginMergeWithNode ); // important so we do not delete the memory.
201183 {
202184 sectorSlice_t intersectSlice = sectorSlice_t::fromOffsets( regionMin, regionMax );
203185
@@ -220,11 +202,11 @@
220202 beginMergeWithNode->metaData.Update( std::move( newSlice ), std::forward <constrArgs> ( args )... );
221203
222204 #ifdef _DEBUG
223- assert( this->data.avlSliceTree.IsNodeInsideTree( &beginMergeWithNode->node ) == false );
205+ assert( this->data.avlSliceTree.IsNodeInsideTree( avlBeginMergeWithNode ) == false );
224206 #endif //_DEBUG
225207
226208 // Since this node has been removed we must reinsert it.
227- this->data.avlSliceTree.Insert( &beginMergeWithNode->node );
209+ this->data.avlSliceTree.Insert( avlBeginMergeWithNode );
228210 }
229211 else
230212 {
Show on old repository browser