Dense B+ tree: Get rid of std::stack usage, adds terrible overhead.

The results look pretty good so far - on 1000000 inserts, the DBP tree
is a bit slower on append, but many times faster when inserting at the
beginning:

BigPtrArray - append: 46 msec
BigPtrArray - insert at front: 6602 msec
DenseBPlusTree - append: 200 msec
DenseBPlusTree - insert at front: 165 msec

Change-Id: I3fbd00d90705928f57bcaa8a1ff4dfc38fd065ed

2 files changed, 51 insertions, 39 deletions

diff --git a/sw/inc/densebplustree.cxx b/sw/inc/densebplustree.cxx
index dd76077bab6a..62c2394a145c 100644
--- a/sw/inc/densebplustree.cxx
+++ b/sw/inc/densebplustree.cxx
@@ -11,6 +11,8 @@
 
 #include <cassert>
 #include <cstdio>
+#include <cstring>
+
 #include <vector>
 
 using namespace std;
@@ -144,7 +146,8 @@ struct DBPTreeNode
 template < class Key, class Value >
 DenseBPlusTree< Key, Value >::DenseBPlusTree()
     : m_pRoot( new DBPTreeNode< Key, Value > ),
-      m_nCount( 0 )
+      m_nCount( 0 ),
+      m_nDepth( 1 )
 {
 }
 
@@ -157,29 +160,31 @@ DenseBPlusTree< Key, Value >::~DenseBPlusTree()
 template < class Key, class Value >
 void DenseBPlusTree< Key, Value >::Insert( const Value& rValue, Key nPos )
 {
-    stack< NodeWithIndex > aParents;
-    NodeWithIndex aLeaf = findLeaf( nPos, &aParents );
+    NodeWithIndex pParents[ m_nDepth ];
+    int nParentsLength;
+    NodeWithIndex aLeaf = findLeaf( nPos, pParents, nParentsLength );
 
     if ( aLeaf.pNode->m_nUsed < sOrder )
     {
         // there's still space in the current node
         aLeaf.pNode->insert( aLeaf.nIndex, rValue );
-        shiftNodes( aParents, 1 );
+        shiftNodes( pParents, nParentsLength, 1 );
     }
     else
     {
-        stack< NodeWithIndex > aNewParents;
-        DBPTreeNode< Key, Value > *pNewLeaf = splitNode( aLeaf.pNode, aParents, aNewParents );
+        NodeWithIndex pNewParents[ m_nDepth ];
+        int nNewParentsLength;
+        DBPTreeNode< Key, Value > *pNewLeaf = splitNode( aLeaf.pNode, pParents, nParentsLength, pNewParents, nNewParentsLength );
 
         if ( aLeaf.nIndex <= aLeaf.pNode->m_nUsed )
             aLeaf.pNode->insert( aLeaf.nIndex, rValue );
         else
         {
             pNewLeaf->insert( aLeaf.nIndex - aLeaf.pNode->m_nUsed, rValue );
-            ++aNewParents.top().nIndex;
+            ++pNewParents[ nNewParentsLength - 1 ].nIndex;
         }
 
-        shiftNodes( aNewParents, 1 );
+        shiftNodes( pNewParents, nNewParentsLength, 1 );
     }
 
     ++m_nCount;
@@ -266,9 +271,10 @@ void DenseBPlusTree< Key, Value >::dump() const
 }
 
 template < class Key, class Value >
-typename DenseBPlusTree< Key, Value >::NodeWithIndex DenseBPlusTree< Key, Value >::findLeaf( Key nPos, std::stack< NodeWithIndex > *pParents )
+typename DenseBPlusTree< Key, Value >::NodeWithIndex DenseBPlusTree< Key, Value >::findLeaf( Key nPos, NodeWithIndex pParents[], int &rParentsLength )
 {
     DBPTreeNode< Key, Value > *pNode = m_pRoot;
+    rParentsLength = 0;
 
     // recursion is nice for the alg. description, but for implementation, we
     // want to unwind it
@@ -283,7 +289,7 @@ typename DenseBPlusTree< Key, Value >::NodeWithIndex DenseBPlusTree< Key, Value
             nPos -= pNode->m_pKeys[ i - 1 ];
 
         if ( pParents )
-            pParents->push( NodeWithIndex( pNode, i ) );
+            pParents[ rParentsLength++ ] = NodeWithIndex( pNode, i );
 
         pNode = pNode->m_pChildren[ i ];
     }
@@ -292,69 +298,73 @@ typename DenseBPlusTree< Key, Value >::NodeWithIndex DenseBPlusTree< Key, Value
 }
 
 template < class Key, class Value >
-void DenseBPlusTree< Key, Value >::shiftNodes( const std::stack< NodeWithIndex >& rParents, int nHowMuch )
+void DenseBPlusTree< Key, Value >::shiftNodes( const NodeWithIndex pParents[], int nParentsLength, int nHowMuch )
 {
-    stack< NodeWithIndex > aParents( rParents );
-    while ( !aParents.empty() )
+    for ( int p = nParentsLength - 1; p >= 0; --p )
     {
-        NodeWithIndex aNode = aParents.top();
-        aParents.pop();
-
-        for ( int i = aNode.nIndex + 1; i < aNode.pNode->m_nUsed - 1; ++i )
-            aNode.pNode->m_pKeys[ i ] += nHowMuch;
+        const NodeWithIndex &rNode = pParents[ p ];
+        for ( int i = rNode.nIndex + 1; i < rNode.pNode->m_nUsed - 1; ++i )
+            rNode.pNode->m_pKeys[ i ] += nHowMuch;
     }
 }
 
 template < class Key, class Value >
-DBPTreeNode< Key, Value >* DenseBPlusTree< Key, Value >::splitNode( DBPTreeNode< Key, Value > *pNode, const std::stack< NodeWithIndex > &rParents, std::stack< NodeWithIndex > &rNewParents )
+DBPTreeNode< Key, Value >* DenseBPlusTree< Key, Value >::splitNode( DBPTreeNode< Key, Value > *pNode, const NodeWithIndex pParents[], int nParentsLength, NodeWithIndex pNewParents[], int &rNewParentsLength )
 {
     assert( pNode->m_nUsed == sOrder );
 
     DBPTreeNode< Key, Value > *pNewNode = new DBPTreeNode< Key, Value >;
     int offset = pNewNode->copyFromSplitNode( pNode );
 
-    if ( rParents.empty() )
+    if ( nParentsLength == 0 )
     {
         // we have to create a new root
         DBPTreeNode< Key, Value > *pNewRoot = new DBPTreeNode< Key, Value >;
         pNewRoot->m_bIsInternal = true;
         pNewRoot->m_pChildren[ 0 ] = m_pRoot;
         pNewRoot->m_nUsed = 1;
+
         m_pRoot = pNewRoot;
+        ++m_nDepth;
 
         m_pRoot->insert( 1, offset, pNewNode );
 
-        rNewParents = stack< NodeWithIndex >();
-        rNewParents.push( NodeWithIndex( m_pRoot, 0 ) );
+        pNewParents[ 0 ] = NodeWithIndex( m_pRoot, 0 );
+        rNewParentsLength = 1;
     }
     else
     {
-        stack< NodeWithIndex > aParents( rParents );
-        NodeWithIndex aParent = aParents.top();
-        aParents.pop();
+        NodeWithIndex aParent = pParents[ nParentsLength - 1 ];
 
         if ( aParent.pNode->m_nUsed < sOrder )
         {
             aParent.pNode->insert( aParent.nIndex + 1, offset, pNewNode );
-            rNewParents = aParents;
-            rNewParents.push( aParent );
+
+            memcpy( pNewParents, pParents, sizeof( pParents[ 0 ] ) * nParentsLength );
+            rNewParentsLength = nParentsLength;
+            pNewParents[ rNewParentsLength - 1 ] = aParent;
         }
         else
         {
-            stack< NodeWithIndex > aNewParents;
-            DBPTreeNode< Key, Value > *pNewParent = splitNode( aParent.pNode, aParents, aNewParents );
+            NodeWithIndex pRetParents[ m_nDepth ];
+            int nRetParentsLength;
+            DBPTreeNode< Key, Value > *pNewParent = splitNode( aParent.pNode, pParents, nParentsLength - 1, pRetParents, nRetParentsLength );
 
             if ( aParent.nIndex <= aParent.pNode->m_nUsed )
             {
                 aParent.pNode->insert( aParent.nIndex + 1, offset, pNewNode );
-                rNewParents = aParents;
-                rNewParents.push( aParent );
+
+                memcpy( pNewParents, pParents, sizeof( pParents[ 0 ] ) * nParentsLength );
+                rNewParentsLength = nParentsLength;
+                pNewParents[ rNewParentsLength - 1 ] = aParent;
             }
             else
             {
                 pNewParent->insert( aParent.nIndex - aParent.pNode->m_nUsed + 1, offset, pNewNode );
-                rNewParents = aParents;
-                rNewParents.push( NodeWithIndex( pNewParent, aParent.nIndex - aParent.pNode->m_nUsed + 1 ) );
+
+                memcpy( pNewParents, pParents, sizeof( pParents[ 0 ] ) * nParentsLength );
+                rNewParentsLength = nParentsLength;
+                pNewParents[ rNewParentsLength - 1 ] = NodeWithIndex( pNewParent, aParent.nIndex - aParent.pNode->m_nUsed + 1 );
             }
         }
     }
diff --git a/sw/inc/densebplustree.hxx b/sw/inc/densebplustree.hxx
index e7362d25fc53..26d1dfbd0ccf 100644
--- a/sw/inc/densebplustree.hxx
+++ b/sw/inc/densebplustree.hxx
@@ -24,8 +24,6 @@
 #include <osl/diagnose.h>
 #include <swdllapi.h>
 
-#include <stack>
-
 template < class Key, class Value > struct DBPTreeNode;
 
 /** Dense B+ tree implementation (to replace the original BigPtrArray).
@@ -98,6 +96,7 @@ private:
         DBPTreeNode< Key, Value > *pNode;
         Key nIndex;
 
+        NodeWithIndex() : pNode( NULL ), nIndex( 0 ) {}
         NodeWithIndex( DBPTreeNode< Key, Value > *p, Key n ) : pNode( p ), nIndex( n ) {}
     };
 
@@ -107,18 +106,21 @@ private:
     /// Amount of values that we contain.
     Key m_nCount;
 
+    /// Depth of the tree - we need that to be able to store info about parents.
+    int m_nDepth;
+
     /** Search for the leaf node containing nPos.
 
         @return the leaf node containing nPos
-        @param pParents stack of parents of the returned tree node so that we can traverse it back to the root
+        @param pParents array of parents of the returned tree node so that we can traverse it back to the root
     */
-    NodeWithIndex findLeaf( Key nPos, std::stack< NodeWithIndex > *pParents = NULL );
+    NodeWithIndex findLeaf( Key nPos, NodeWithIndex pParents[] = NULL, int &rParentsLength = int() );
 
     /// Shift the right side of the tree to left or right by nHowMuch.
-    void shiftNodes( const std::stack< NodeWithIndex > &rParents, int nHowMuch );
+    void shiftNodes( const NodeWithIndex pParents[], int nParentsLength, int nHowMuch );
 
     /// Split the node, and adjust parents accordingly.
-    DBPTreeNode< Key, Value >* splitNode( DBPTreeNode< Key, Value > *pNode, const std::stack< NodeWithIndex > &rParents, std::stack< NodeWithIndex > &rNewParents );
+    DBPTreeNode< Key, Value >* splitNode( DBPTreeNode< Key, Value > *pNode, const NodeWithIndex pParents[], int nParentsLength, NodeWithIndex *pNewParents, int &rNewParentsLength );
 };
 
 // include the implementation