Why Front::insertPlaceholder() executes twice as a result of a single call?

I'm programming a massive point cloud renderer for my Phd. thesis, where I maintain a spatial tree structure (octree) of the points in the cloud. In order to optimize code, I also maintain the Front of the octree, which is a list containing the octree nodes rendered in the last frame and placeholders for new nodes read from the disk, which are not known yet to be temporary or not. The bottom-up octree creation is performed by the HierarchyCreator, which also inserts placeholders into the Front whenever it processes a new node read from disk. The node processing is parallel and is as simple as grouping sibling nodes and defining its parent, which is processed in later iterations. An invariant of the Front is that all nodes should remain sorted by Morton code id. The nodes are expected to be read in this order. The method to insert placeholders and validate the Front order is: template< typename Morton, typename Point > inline void Front< Morton, Point >::insertPlaceholder( const Morton& morton, int threadIdx ) { #ifdef DEBUG { stringstream ss; ss << "Placeholder insertion t " << threadIdx << " ( thread id " << this_thread::get_id() << " ): " << morton.getPathToRoot( true ) << endl; HierarchyCreationLog::logDebugMsg( ss.str() ); if( !m_currentIterPlaceholders[ threadIdx ].empty() && morton <= m_currentIterPlaceholders[ threadIdx ].back().m_morton ) { ss << "Placeholder insertion compromises ordering" << endl << endl; HierarchyCreationLog::logAndFail( ss.str() ); } } #endif assert( morton.getLevel() == m_leafLvlDim.m_nodeLvl && "Placeholders should be in hierarchy's deepest level." ); FrontList& list = m_currentIterPlaceholders[ threadIdx ]; list.push_back( FrontNode( m_placeholder, morton ) ); } This method is called whenever a parent node is created, after its children are assembled. The related code is bellow: template< typename Morton, typename Point > inline typename HierarchyCreator< Morton, Point >::Node HierarchyCreator< Morton, Point > ::createInnerNode( NodeArray&& inChildren, uint nChildren, const int threadIdx, const bool setParentFlag ) /*const*/ { if( nChildren == 1 ) { return createNodeFromSingleChild( std::move( inChildren[ 0 ] ), false, threadIdx, setParentFlag ); } else { NodeArray children( nChildren ); // Verify if placeholders are necessary. bool frontPlaceholdersOn = ( m_octreeDim.calcMorton( inChildren[ 0 ] ).getLevel() == m_leafLvlDim.m_nodeLvl ); int nPoints = 0; SiblingPointsPrefixMap prefixMap; for( int i = 0; i < children.size(); ++i ) { children[ i ] = std::move( inChildren[ i ] ); if( frontPlaceholdersOn ) { #ifdef DEBUG { stringstream ss; ss << "T " << threadIdx << " inner" << endl << endl; HierarchyCreationLog::logDebugMsg( ss.str() ); } #endif m_front.insertPlaceholder( m_octreeDim.calcMorton( children[ i ] ), threadIdx ); } ... Irrelevant ... } ... Irrelevant ... } ... Irrelevant ... } template< typename Morton, typename Point > inline typename HierarchyCreator< Morton, Point >::Node HierarchyCreator< Morton, Point > ::createNodeFromSingleChild( Node&& child, bool isLeaf, const int threadIdx, const bool setParentFlag ) /*const*/ { // Setup a placeholder in front if the node is in the leaf level. Morton childMorton = m_octreeDim.calcMorton( child ); if( childMorton.getLevel() == m_leafLvlDim.m_nodeLvl ) { #ifdef DEBUG { stringstream ss; ss << "T " << threadIdx << " node from single" << endl << endl; HierarchyCreationLog::logDebugMsg( ss.str() ); } #endif m_front.insertPlaceholder( childMorton, threadIdx ); } ... Irrelevant ... } I have sucessfully tested my system with several datasets, however in one case, the Front sort invariant is violated. The log for this case is shown bellow. The entries of the type T 0 sib[ 0 ]: 0x8024100000->0x1004820000->0x200904000->0x40120800->0x8024100->0x1004820->0x200904->0x40120->0x8024->0x1004->0x200->0x40->0x8->0x1 are generated from the HierarchyCreator at the time it starts processing the node and just show which thread is processing the node and its id. The hierarchy of the Morton code id is shown in the logs, but the first hexadecimal value is enough to identify the node. Log: T 0 sib[ 0 ]: 0x8024100000->0x1004820000->0x200904000->0x40120800->0x8024100->0x1004820->0x200904->0x40120->0x8024->0x1004->0x200->0x40->0x8->0x1 T 0 node from single Placeholder insertion t 0 ( thread id 140736761321216 ): 0x8024100000->0x1004820000->0x200904000->0x40120800->0x8024100->0x1004820->0x200904->0x40120->0x8024->0x1004->0x200->0x40->0x8->0x1 T 0 sib[ 0 ]: 0xc804824100->0x1900904820->0x320120904->0x64024120->0xc804824->0x1900904->0x320120->0x64024->0xc804->0x1900->0x320->0x64->0xc->0x1 T 0 node from single Placeholder insertion t 0 ( thread id 140736761321216 ): 0xc804824100->0x1900904820->0x320120904->0x64024120->0xc804824->0x1900904->0x320120->0x64024->0xc804->0x1900->0x320->0x64->0xc->0x1 T 0 sib[ 0 ]: 0x8120804900->0x1024100920->0x204820124->0x40904024->0x8120804->0x1024100->0x204820->0x40904->0x8120->0x1024->0x204->0x40->0x8->0x1 T 0 node from single Placeholder insertion t 0 ( thread id 140736761321216 ): 0x8120804900->0x1024100920->0x204820124->0x40904024->0x8120804->0x1024100->0x204820->0x40904->0x8120->0x1024->0x204->0x40->0x8->0x1 Placeholder insertion t 0 ( thread id 140736761321216 ): 0x8120804900->0x1024100920->0x204820124->0x40904024->0x8120804->0x1024100->0x204820->0x40904->0x8120->0x1024->0x204->0x40->0x8->0x1 Placeholder insertion compromises ordering As can be seen, Front::insertPlaceholder() is called twice for the node with code 0x8120804900. However, that makes no sense, since there is just one call to HierarchyCreator ::createNodeFromSingleChild() with that node as parameter. It seems that a single call is resulting in two. I couldn't track the reasons for this behavior, so I'm posting it in order to get feedback from other minds. Any help would be really appreciated.