[Libreoffice-commits] .: Branch 'feature/bplustree' - 6 commits - Repository.mk sw/inc sw/Library_sw.mk sw/Module_sw.mk sw/qa sw/source
Libreoffice Gerrit user
logerrit at kemper.freedesktop.org
Wed Jan 30 17:38:06 PST 2013
Repository.mk | 1
sw/Library_sw.mk | 1
sw/Module_sw.mk | 1
sw/inc/bplustree.hxx | 82 -------
sw/inc/densebplustree.cxx | 384 ++++++++++++++++++++++++++++++++++++
sw/inc/densebplustree.hxx | 134 ++++++++++++
sw/qa/core/densebplustree-test.cxx | 88 ++++++++
sw/source/core/bastyp/bplustree.cxx | 134 ------------
8 files changed, 608 insertions(+), 217 deletions(-)
New commits:
commit f9f33617b45dc927b5605baf8c07da7664ec1b83
Author: Jan Holesovsky <kendy at suse.cz>
Date: Thu Jan 31 02:18:05 2013 +0100
Dense B+ tree: A small optimization of appends.
Append (ie. Insert() at Count()) is supposedly a critical operation, so let's
optimize for that a bit - cache the last leaf. And this gets us where we want
to be (1000000 of operations):
BigPtrArray - append: 45 msec
BigPtrArray - insert at front: 6541 msec
DenseBPlusTree - append: 59 msec
DenseBPlusTree - insert at front: 169 msec
Change-Id: Id66ad6f37b8a08416a874af6397e113aecfd6b0e
diff --git a/sw/inc/densebplustree.cxx b/sw/inc/densebplustree.cxx
index 62c2394..c936ad8 100644
--- a/sw/inc/densebplustree.cxx
+++ b/sw/inc/densebplustree.cxx
@@ -146,6 +146,7 @@ struct DBPTreeNode
template < class Key, class Value >
DenseBPlusTree< Key, Value >::DenseBPlusTree()
: m_pRoot( new DBPTreeNode< Key, Value > ),
+ m_pLastLeaf( m_pRoot ),
m_nCount( 0 ),
m_nDepth( 1 )
{
@@ -161,8 +162,12 @@ template < class Key, class Value >
void DenseBPlusTree< Key, Value >::Insert( const Value& rValue, Key nPos )
{
NodeWithIndex pParents[ m_nDepth ];
- int nParentsLength;
- NodeWithIndex aLeaf = findLeaf( nPos, pParents, nParentsLength );
+ int nParentsLength = 0;
+ NodeWithIndex aLeaf( m_pLastLeaf, m_pLastLeaf->m_nUsed );
+
+ // if we are lucky, we just append, otherwise do the full job
+ if ( nPos != m_nCount || m_pLastLeaf->m_nUsed == sOrder )
+ aLeaf = findLeaf( nPos, pParents, nParentsLength );
if ( aLeaf.pNode->m_nUsed < sOrder )
{
@@ -316,6 +321,10 @@ DBPTreeNode< Key, Value >* DenseBPlusTree< Key, Value >::splitNode( DBPTreeNode<
DBPTreeNode< Key, Value > *pNewNode = new DBPTreeNode< Key, Value >;
int offset = pNewNode->copyFromSplitNode( pNode );
+ // update the last leaf if necessary
+ if ( pNode == m_pLastLeaf )
+ m_pLastLeaf = pNewNode;
+
if ( nParentsLength == 0 )
{
// we have to create a new root
diff --git a/sw/inc/densebplustree.hxx b/sw/inc/densebplustree.hxx
index 26d1dfbd0..027e2d8 100644
--- a/sw/inc/densebplustree.hxx
+++ b/sw/inc/densebplustree.hxx
@@ -103,6 +103,9 @@ private:
/// Root of the tree.
DBPTreeNode< Key, Value > *m_pRoot;
+ /// The last leaf node - only a small optimization for appends.
+ DBPTreeNode< Key, Value > *m_pLastLeaf;
+
/// Amount of values that we contain.
Key m_nCount;
commit e11ca8aa63172c5b0d30f68fd9c796f276c3dd26
Author: Jan Holesovsky <kendy at suse.cz>
Date: Thu Jan 31 01:39:03 2013 +0100
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
diff --git a/sw/inc/densebplustree.cxx b/sw/inc/densebplustree.cxx
index dd76077..62c2394 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 e7362d2..26d1dfbd0 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
commit a97920e95ba4a3684321cd2d74f283849e62991b
Author: Jan Holesovsky <kendy at suse.cz>
Date: Wed Jan 30 18:28:23 2013 +0100
Dense B+ tree: Splitting of nodes seems to work now, ie. Insert() functional.
Of course, more testing still needed.
Change-Id: I7e3bef1d5096e4d332f3a00d11fa13b59a4a03bf
diff --git a/sw/inc/densebplustree.cxx b/sw/inc/densebplustree.cxx
index 3f8a1a3..dd76077 100644
--- a/sw/inc/densebplustree.cxx
+++ b/sw/inc/densebplustree.cxx
@@ -21,9 +21,9 @@ This affects how big are the metadata and data nodes; the higher the value,
the flatter the structure is. It is necessary to find a good compromise
between fragmentation (too low value) and not being too flat (too high value).
-50 seems to be a good value so far, but we can change it easily.
+50 seems to be a good value so far, but we can change it easily if necessary.
*/
-static const int sOrder = 7;
+static const int sOrder = 50;
/** B+ tree node implementation.
@@ -78,6 +78,29 @@ struct DBPTreeNode
++m_nUsed;
}
+ /// Insert a new child node (for internal nodes only).
+ void insert( int nWhere, int nOffset, DBPTreeNode* pNewNode )
+ {
+ assert( m_bIsInternal );
+ assert( nWhere <= m_nUsed );
+ assert( nWhere < sOrder );
+ assert( nWhere > 0 ); // we always add the node to the right when splitting
+
+ for ( int i = m_nUsed; i > nWhere; --i )
+ {
+ m_pChildren[ i ] = m_pChildren[ i - 1 ];
+ m_pKeys[ i - 1 ] = m_pKeys[ i - 2 ];
+ }
+
+ m_pChildren[ nWhere ] = pNewNode;
+ if ( nWhere - 2 >= 0 )
+ m_pKeys[ nWhere - 1 ] = m_pKeys[ nWhere - 2 ] + nOffset;
+ else
+ m_pKeys[ nWhere - 1 ] = nOffset;
+
+ ++m_nUsed;
+ }
+
/** Split node, and make the original one smaller.
@return relative key shift of the node.
@@ -86,35 +109,35 @@ struct DBPTreeNode
{
assert( pNode->m_nUsed == sOrder );
- const int offset = sOrder / 2;
- int nKeyShift = 0;
+ const int sKeep = sOrder / 2;
+ int offset = 0;
m_bIsInternal = pNode->m_bIsInternal;
if ( m_bIsInternal )
{
- for ( int i = 0; i < sOrder - offset; ++i )
- m_pChildren[ i ] = pNode->m_pChildren[ i + offset ];
+ for ( int i = sKeep; i < pNode->m_nUsed; ++i )
+ m_pChildren[ i - sKeep ] = pNode->m_pChildren[ i ];
// we have to 'relativize' the keys
- nKeyShift = pNode->m_pKeys[ offset - 1 ];
- for ( int i = 0; i < sOrder - offset - 1; ++i )
- m_pKeys[ i ] = pNode->m_pKeys[ i + offset ] - nKeyShift;
+ offset = pNode->m_pKeys[ sKeep - 1 ];
+ for ( int i = sKeep; i < pNode->m_nUsed - 1; ++i )
+ m_pKeys[ i - sKeep ] = pNode->m_pKeys[ i ] - offset;
}
else
{
- for ( int i = 0; i < sOrder - offset; ++i )
- m_pValues[ i ] = pNode->m_pValues[ i + offset ];
+ for ( int i = sKeep; i < pNode->m_nUsed; ++i )
+ m_pValues[ i - sKeep ] = pNode->m_pValues[ i ];
- nKeyShift = offset;
+ offset = sKeep;
m_pNext = pNode->m_pNext;
pNode->m_pNext = this;
}
- m_nUsed = sOrder - offset;
- pNode->m_nUsed = offset;
+ m_nUsed = pNode->m_nUsed - sKeep;
+ pNode->m_nUsed = sKeep;
- return nKeyShift;
+ return offset;
}
};
@@ -137,7 +160,7 @@ void DenseBPlusTree< Key, Value >::Insert( const Value& rValue, Key nPos )
stack< NodeWithIndex > aParents;
NodeWithIndex aLeaf = findLeaf( nPos, &aParents );
- if ( aLeaf.pNode->m_nUsed < sOrder - 1 )
+ if ( aLeaf.pNode->m_nUsed < sOrder )
{
// there's still space in the current node
aLeaf.pNode->insert( aLeaf.nIndex, rValue );
@@ -148,16 +171,15 @@ void DenseBPlusTree< Key, Value >::Insert( const Value& rValue, Key nPos )
stack< NodeWithIndex > aNewParents;
DBPTreeNode< Key, Value > *pNewLeaf = splitNode( aLeaf.pNode, aParents, aNewParents );
- if ( aLeaf.nIndex < aLeaf.pNode->m_nUsed )
- {
+ if ( aLeaf.nIndex <= aLeaf.pNode->m_nUsed )
aLeaf.pNode->insert( aLeaf.nIndex, rValue );
- shiftNodes( aParents, 1 );
- }
else
{
- pNewLeaf->insert( aLeaf.nIndex - pNewLeaf->m_nUsed, rValue );
- shiftNodes( aNewParents, 1 );
+ pNewLeaf->insert( aLeaf.nIndex - aLeaf.pNode->m_nUsed, rValue );
+ ++aNewParents.top().nIndex;
}
+
+ shiftNodes( aNewParents, 1 );
}
++m_nCount;
@@ -210,6 +232,7 @@ void DenseBPlusTree< Key, Value >::ForEach( Key nStart, Key nEnd, FnForEach fn,
template < class Key, class Value >
void DenseBPlusTree< Key, Value >::dump() const
{
+ printf( "======================\nCount: %d\n", Count() );
vector< DBPTreeNode< Key, Value >* > aLifo;
aLifo.push_back( m_pRoot );
@@ -220,7 +243,11 @@ void DenseBPlusTree< Key, Value >::dump() const
if ( pNode->m_bIsInternal )
{
- printf( "internal node: %p\nchildren: ", pNode );
+ printf( "internal node: %p\nkeys: ", pNode );
+ for ( int i = 0; i < pNode->m_nUsed - 1; ++i )
+ printf( "%d, ", pNode->m_pKeys[ i ] );
+
+ printf( "\nchildren: " );
for ( int i = 0; i < pNode->m_nUsed; ++i )
{
printf( "%p, ", pNode->m_pChildren[ i ] );
@@ -273,7 +300,7 @@ void DenseBPlusTree< Key, Value >::shiftNodes( const std::stack< NodeWithIndex >
NodeWithIndex aNode = aParents.top();
aParents.pop();
- for ( int i = aNode.nIndex; i < aNode.pNode->m_nUsed - 1; ++i )
+ for ( int i = aNode.nIndex + 1; i < aNode.pNode->m_nUsed - 1; ++i )
aNode.pNode->m_pKeys[ i ] += nHowMuch;
}
}
@@ -281,66 +308,58 @@ void DenseBPlusTree< Key, Value >::shiftNodes( const std::stack< NodeWithIndex >
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 )
{
-#if 0
- stack< NodeWithIndex > aParents( rParents );
-
- struct Split {
- NodeWithIndex aOriginal;
- DBPTreeNode< Key, Value >* pNewNode;
- int nOffset;
+ assert( pNode->m_nUsed == sOrder );
- Split( NodeWithIndex &rOrig, DBPTreeNode< Key, Value > *pNew, int nOff ) : aOriginal( rOrig ), pNewNode( pNew ), nOffset( nOff ) {}
- };
+ DBPTreeNode< Key, Value > *pNewNode = new DBPTreeNode< Key, Value >;
+ int offset = pNewNode->copyFromSplitNode( pNode );
- stack< Split > aSplit;
-
- while ( pNode->m_nUsed == sOrder )
+ if ( rParents.empty() )
{
- DBPTreeNode< Key, Value > *pNewNode = new DBPTreeNode< Key, Value >;
+ // 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;
- int offset = pNewNode->copyFromSplitNode( pNode );
+ m_pRoot->insert( 1, offset, pNewNode );
- NodeWithIndex aNode = aParents.top();
- aParents.pop();
-
- aSplit.push( Split( aNode, pNewNode, offset ) );
-
- pNode = aNode.pNode;
+ rNewParents = stack< NodeWithIndex >();
+ rNewParents.push( NodeWithIndex( m_pRoot, 0 ) );
}
-
- // copy the common (not split) part of parents
- rNewParents = aParents;
-
- // create new root if we have split even that
- if ( rNewParents.empty() )
- {
- DBPTreeNode< Key, Value > *pNewNode = new DBPTreeNode< Key, Value >;
- pNewNode->m_bIsInternal = true;
- pNewNode->m_pChildren[ 0 ] = m_pRoot;
- pNewNode->m_nUsed = 1;
-
- m_pRoot = pNewNode;
- rNewParents.push( NodeWithIndex( m_pRoot, 1 ) );
- }
-
- DBPTreeNode< Key, Value > *pNewNode;
- while ( !aSplit.empty() )
+ else
{
- Split aEntry = aSplit.top();
- pNewNode = aEntry.pNewNode;
- aSplit.pop();
-
- // insert the new node to the parent (there is enough space now)
- rNewParents.top().pNode->insert( rNewParents.top().nIndex, aEntry.nOffset, aSplit.pNewNode );
+ stack< NodeWithIndex > aParents( rParents );
+ NodeWithIndex aParent = aParents.top();
+ aParents.pop();
- if ( aEntry.aOriginal.nIndex < aEntry.aOriginal.pNode->m_nUsed )
- rNewParents.push( aEntry.aOriginal );
+ if ( aParent.pNode->m_nUsed < sOrder )
+ {
+ aParent.pNode->insert( aParent.nIndex + 1, offset, pNewNode );
+ rNewParents = aParents;
+ rNewParents.push( aParent );
+ }
else
- rNewParents.push( NodeWithIndex( pNewNode, aEntry.aOriginal.nIndex - aEntry.nOffset ) );
+ {
+ stack< NodeWithIndex > aNewParents;
+ DBPTreeNode< Key, Value > *pNewParent = splitNode( aParent.pNode, aParents, aNewParents );
+
+ if ( aParent.nIndex <= aParent.pNode->m_nUsed )
+ {
+ aParent.pNode->insert( aParent.nIndex + 1, offset, pNewNode );
+ rNewParents = aParents;
+ rNewParents.push( 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 ) );
+ }
+ }
}
return pNewNode;
-#endif
}
/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
commit f9c991c8f812440ab68938b1facfed3796a817d0
Author: Jan Holesovsky <kendy at suse.cz>
Date: Wed Jan 30 14:22:53 2013 +0100
Dense B+ tree: Implemented Insert(), and can start testing.
The trivial case works now, but splitting nodes does not do yet.
Change-Id: Ife452fc164ab786ac9e1dc9cabe9ea1a2e78231a
diff --git a/Repository.mk b/Repository.mk
index 19e9c4d..4374068 100644
--- a/Repository.mk
+++ b/Repository.mk
@@ -96,6 +96,7 @@ $(eval $(call gb_Helper_register_executables,SDK, \
endif
$(eval $(call gb_Helper_register_executables,OOO, \
+ dbptree-test \
gnome-open-url.bin \
spadmin.bin \
$(if $(filter $(GUIBASE)$(ENABLE_TDE),unxTRUE), \
diff --git a/sw/Module_sw.mk b/sw/Module_sw.mk
index 6abd321..5ed6a47 100644
--- a/sw/Module_sw.mk
+++ b/sw/Module_sw.mk
@@ -21,6 +21,7 @@ $(eval $(call gb_Module_Module,sw))
$(eval $(call gb_Module_add_targets,sw,\
AllLangResTarget_sw \
+ Executable_dbptreetest \
Library_msword \
Library_sw \
Library_swd \
diff --git a/sw/inc/densebplustree.cxx b/sw/inc/densebplustree.cxx
index ec779bd..3f8a1a3 100644
--- a/sw/inc/densebplustree.cxx
+++ b/sw/inc/densebplustree.cxx
@@ -10,6 +10,10 @@
#include <densebplustree.hxx>
#include <cassert>
+#include <cstdio>
+#include <vector>
+
+using namespace std;
/** The tree node order
@@ -26,7 +30,7 @@ static const int sOrder = 7;
It has to be able to act as an internal node, as well as the leaf node.
*/
template < class Key, class Value >
-struct DenseBPlusTreeNode
+struct DBPTreeNode
{
/// The number of children / data entries.
int m_nUsed;
@@ -49,21 +53,75 @@ struct DenseBPlusTreeNode
union {
/// Internal node, contains only pointers to other nodes
- DenseBPlusTreeNode m_pChildren[ sOrder ];
+ DBPTreeNode* m_pChildren[ sOrder ];
/// Leaf node, contains data.
Value m_pValues[ sOrder ];
};
/// Pointer to the next node (valid only for the leaf nodes).
- DenseBPlusTreeNode *m_pNext;
+ DBPTreeNode *m_pNext;
+
+ DBPTreeNode() : m_nUsed( 0 ), m_bIsInternal( false ), m_pNext( NULL ) {}
+
+ /// Insert the value (for leaf nodes only).
+ void insert( int nWhere, const Value& rValue )
+ {
+ assert( !m_bIsInternal );
+ assert( nWhere <= m_nUsed );
+ assert( nWhere < sOrder );
+
+ for ( int i = m_nUsed; i > nWhere; --i )
+ m_pValues[ i ] = m_pValues[ i - 1 ];
+
+ m_pValues[ nWhere ] = rValue;
+ ++m_nUsed;
+ }
+
+ /** Split node, and make the original one smaller.
+
+ @return relative key shift of the node.
+ */
+ int copyFromSplitNode( DBPTreeNode *pNode )
+ {
+ assert( pNode->m_nUsed == sOrder );
+
+ const int offset = sOrder / 2;
+ int nKeyShift = 0;
+
+ m_bIsInternal = pNode->m_bIsInternal;
+ if ( m_bIsInternal )
+ {
+ for ( int i = 0; i < sOrder - offset; ++i )
+ m_pChildren[ i ] = pNode->m_pChildren[ i + offset ];
+
+ // we have to 'relativize' the keys
+ nKeyShift = pNode->m_pKeys[ offset - 1 ];
+ for ( int i = 0; i < sOrder - offset - 1; ++i )
+ m_pKeys[ i ] = pNode->m_pKeys[ i + offset ] - nKeyShift;
+ }
+ else
+ {
+ for ( int i = 0; i < sOrder - offset; ++i )
+ m_pValues[ i ] = pNode->m_pValues[ i + offset ];
- DenseBPlusTreeNode() : m_nUsed( 0 ), m_bIsInternal( false ), m_pNext( NULL ) {}
+ nKeyShift = offset;
+
+ m_pNext = pNode->m_pNext;
+ pNode->m_pNext = this;
+ }
+
+ m_nUsed = sOrder - offset;
+ pNode->m_nUsed = offset;
+
+ return nKeyShift;
+ }
};
template < class Key, class Value >
DenseBPlusTree< Key, Value >::DenseBPlusTree()
- : m_pRoot( new TreeNode )
+ : m_pRoot( new DBPTreeNode< Key, Value > ),
+ m_nCount( 0 )
{
}
@@ -74,15 +132,35 @@ DenseBPlusTree< Key, Value >::~DenseBPlusTree()
}
template < class Key, class Value >
-Key DenseBPlusTree< Key, Value >::Count() const
-{
- // TODO
-}
-
-template < class Key, class Value >
void DenseBPlusTree< Key, Value >::Insert( const Value& rValue, Key nPos )
{
- // TODO
+ stack< NodeWithIndex > aParents;
+ NodeWithIndex aLeaf = findLeaf( nPos, &aParents );
+
+ if ( aLeaf.pNode->m_nUsed < sOrder - 1 )
+ {
+ // there's still space in the current node
+ aLeaf.pNode->insert( aLeaf.nIndex, rValue );
+ shiftNodes( aParents, 1 );
+ }
+ else
+ {
+ stack< NodeWithIndex > aNewParents;
+ DBPTreeNode< Key, Value > *pNewLeaf = splitNode( aLeaf.pNode, aParents, aNewParents );
+
+ if ( aLeaf.nIndex < aLeaf.pNode->m_nUsed )
+ {
+ aLeaf.pNode->insert( aLeaf.nIndex, rValue );
+ shiftNodes( aParents, 1 );
+ }
+ else
+ {
+ pNewLeaf->insert( aLeaf.nIndex - pNewLeaf->m_nUsed, rValue );
+ shiftNodes( aNewParents, 1 );
+ }
+ }
+
+ ++m_nCount;
}
template < class Key, class Value >
@@ -102,7 +180,7 @@ void DenseBPlusTree< Key, Value >::Replace( Key nPos, const Value& rValue )
{
assert( m_pRoot->m_nUsed > 0 );
- NodeWithIndex aLeaf = searchLeaf( nPos, NULL );
+ NodeWithIndex aLeaf = findLeaf( nPos, NULL );
aLeaf.pNode->m_pValues[ aLeaf.nIndex ] = rValue;
}
@@ -112,7 +190,7 @@ const Value& DenseBPlusTree< Key, Value >::operator[]( Key nPos ) const
{
assert( m_pRoot->m_nUsed > 0 );
- NodeWithIndex aLeaf = searchLeaf( nPos, NULL );
+ NodeWithIndex aLeaf = findLeaf( nPos, NULL );
return aLeaf.pNode->m_pValues[ aLeaf.nIndex ];
}
@@ -130,12 +208,40 @@ void DenseBPlusTree< Key, Value >::ForEach( Key nStart, Key nEnd, FnForEach fn,
}
template < class Key, class Value >
-typename DenseBPlusTree< Key, Value >::NodeWithIndex DenseBPlusTree< Key, Value >::searchLeaf( Key nPos, std::stack< NodeWithIndex > *pParents )
+void DenseBPlusTree< Key, Value >::dump() const
{
- if ( m_pRoot->m_nUsed == 0 )
- return NodeWithIndex( m_pRoot, -1 );
+ vector< DBPTreeNode< Key, Value >* > aLifo;
+ aLifo.push_back( m_pRoot );
+
+ while ( !aLifo.empty() )
+ {
+ DBPTreeNode< Key, Value > *pNode = aLifo.front();
+ aLifo.erase( aLifo.begin() );
+
+ if ( pNode->m_bIsInternal )
+ {
+ printf( "internal node: %p\nchildren: ", pNode );
+ for ( int i = 0; i < pNode->m_nUsed; ++i )
+ {
+ printf( "%p, ", pNode->m_pChildren[ i ] );
+ aLifo.push_back( pNode->m_pChildren[ i ] );
+ }
+ printf( "\n\n" );
+ }
+ else
+ {
+ printf( "leaf node: %p\nvalues: ", pNode );
+ for ( int i = 0; i < pNode->m_nUsed; ++i )
+ printf( "%d, ", pNode->m_pValues[ i ] );
+ printf( "\n\n" );
+ }
+ }
+}
- TreeNode *pNode = m_pRoot;
+template < class Key, class Value >
+typename DenseBPlusTree< Key, Value >::NodeWithIndex DenseBPlusTree< Key, Value >::findLeaf( Key nPos, std::stack< NodeWithIndex > *pParents )
+{
+ DBPTreeNode< Key, Value > *pNode = m_pRoot;
// recursion is nice for the alg. description, but for implementation, we
// want to unwind it
@@ -150,15 +256,91 @@ typename DenseBPlusTree< Key, Value >::NodeWithIndex DenseBPlusTree< Key, Value
nPos -= pNode->m_pKeys[ i - 1 ];
if ( pParents )
- pParents->push_back( NodeWithIndex( pNode, i ) );
+ pParents->push( NodeWithIndex( pNode, i ) );
pNode = pNode->m_pChildren[ i ];
}
- // now we have the leaf node, check that we are not out of bounds
- assert( nPos < pNode->m_nUsed );
-
return NodeWithIndex( pNode, nPos );
}
+template < class Key, class Value >
+void DenseBPlusTree< Key, Value >::shiftNodes( const std::stack< NodeWithIndex >& rParents, int nHowMuch )
+{
+ stack< NodeWithIndex > aParents( rParents );
+ while ( !aParents.empty() )
+ {
+ NodeWithIndex aNode = aParents.top();
+ aParents.pop();
+
+ for ( int i = aNode.nIndex; i < aNode.pNode->m_nUsed - 1; ++i )
+ aNode.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 )
+{
+#if 0
+ stack< NodeWithIndex > aParents( rParents );
+
+ struct Split {
+ NodeWithIndex aOriginal;
+ DBPTreeNode< Key, Value >* pNewNode;
+ int nOffset;
+
+ Split( NodeWithIndex &rOrig, DBPTreeNode< Key, Value > *pNew, int nOff ) : aOriginal( rOrig ), pNewNode( pNew ), nOffset( nOff ) {}
+ };
+
+ stack< Split > aSplit;
+
+ while ( pNode->m_nUsed == sOrder )
+ {
+ DBPTreeNode< Key, Value > *pNewNode = new DBPTreeNode< Key, Value >;
+
+ int offset = pNewNode->copyFromSplitNode( pNode );
+
+ NodeWithIndex aNode = aParents.top();
+ aParents.pop();
+
+ aSplit.push( Split( aNode, pNewNode, offset ) );
+
+ pNode = aNode.pNode;
+ }
+
+ // copy the common (not split) part of parents
+ rNewParents = aParents;
+
+ // create new root if we have split even that
+ if ( rNewParents.empty() )
+ {
+ DBPTreeNode< Key, Value > *pNewNode = new DBPTreeNode< Key, Value >;
+ pNewNode->m_bIsInternal = true;
+ pNewNode->m_pChildren[ 0 ] = m_pRoot;
+ pNewNode->m_nUsed = 1;
+
+ m_pRoot = pNewNode;
+ rNewParents.push( NodeWithIndex( m_pRoot, 1 ) );
+ }
+
+ DBPTreeNode< Key, Value > *pNewNode;
+ while ( !aSplit.empty() )
+ {
+ Split aEntry = aSplit.top();
+ pNewNode = aEntry.pNewNode;
+ aSplit.pop();
+
+ // insert the new node to the parent (there is enough space now)
+ rNewParents.top().pNode->insert( rNewParents.top().nIndex, aEntry.nOffset, aSplit.pNewNode );
+
+ if ( aEntry.aOriginal.nIndex < aEntry.aOriginal.pNode->m_nUsed )
+ rNewParents.push( aEntry.aOriginal );
+ else
+ rNewParents.push( NodeWithIndex( pNewNode, aEntry.aOriginal.nIndex - aEntry.nOffset ) );
+ }
+
+ return pNewNode;
+#endif
+}
+
/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sw/inc/densebplustree.hxx b/sw/inc/densebplustree.hxx
index cf0c9ff..e7362d2 100644
--- a/sw/inc/densebplustree.hxx
+++ b/sw/inc/densebplustree.hxx
@@ -26,7 +26,7 @@
#include <stack>
-template < class Key, class Value > struct DenseBPlusTreeNode;
+template < class Key, class Value > struct DBPTreeNode;
/** Dense B+ tree implementation (to replace the original BigPtrArray).
@@ -66,7 +66,7 @@ public:
~DenseBPlusTree();
/// Number of elements.
- Key Count() const;
+ Key Count() const { return m_nCount; }
/// Insert entry at the specified position.
void Insert( const Value& rValue, Key nPos );
@@ -89,28 +89,41 @@ public:
/// Traverse over the specified range, and call fn on the data.
void ForEach( Key nStart, Key nEnd, FnForEach fn, void* pArgs = NULL );
-private:
- typedef DenseBPlusTreeNode< Key, Value > TreeNode;
+ /// For debugging.
+ void dump() const;
+private:
/// We need to know the exact path from the root to the leaf, including the indexes for various operations
struct NodeWithIndex {
- TreeNode *pNode;
+ DBPTreeNode< Key, Value > *pNode;
Key nIndex;
- NodeWithIndex( TreeNode *p, Key n ) : pNode( p ), nIndex( n ) {}
+ NodeWithIndex( DBPTreeNode< Key, Value > *p, Key n ) : pNode( p ), nIndex( n ) {}
};
/// Root of the tree.
- TreeNode *m_pRoot;
+ DBPTreeNode< Key, Value > *m_pRoot;
+
+ /// Amount of values that we contain.
+ Key m_nCount;
/** 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
*/
- NodeWithIndex searchLeaf( Key nPos, std::stack< NodeWithIndex > *pParents = NULL );
+ NodeWithIndex findLeaf( Key nPos, std::stack< NodeWithIndex > *pParents = NULL );
+
+ /// Shift the right side of the tree to left or right by nHowMuch.
+ void shiftNodes( const std::stack< NodeWithIndex > &rParents, 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 );
};
+// include the implementation
+#include <densebplustree.cxx>
+
#endif // SW_BPLUSTREE_HXX
/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sw/qa/core/densebplustree-test.cxx b/sw/qa/core/densebplustree-test.cxx
new file mode 100644
index 0000000..e270d09
--- /dev/null
+++ b/sw/qa/core/densebplustree-test.cxx
@@ -0,0 +1,88 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * This file is part of the LibreOffice project.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ */
+
+#include <densebplustree.hxx>
+#include <bparr.hxx>
+
+#include <sys/time.h>
+
+class BigPtrEntryMock : public BigPtrEntry
+{
+public:
+ BigPtrEntryMock(sal_uLong count) : count_(count)
+ {
+ }
+
+ ~BigPtrEntryMock()
+ {
+ }
+
+ sal_uLong getCount() const
+ {
+ return count_;
+ }
+
+ void setCount(sal_uLong newCount)
+ {
+ count_ = newCount;
+ }
+
+ sal_uLong Position() const
+ {
+ return GetPos();
+ }
+
+private:
+ sal_uLong count_;
+};
+
+void print_time( const char* msg, const struct timeval &before, const struct timeval &after )
+{
+ time_t sec = after.tv_sec - before.tv_sec;
+ suseconds_t usec = sec * 1000000 + after.tv_usec - before.tv_usec;
+
+ printf( "%s: %ld msec\n", msg, usec / 1000 );
+}
+
+int main( int, char** )
+{
+ struct timeval tv_before, tv_after;
+
+ gettimeofday( &tv_before, NULL );
+ BigPtrArray bparr;
+ for ( int i = 0; i < 1000000; i++ )
+ bparr.Insert( new BigPtrEntryMock(i), bparr.Count() );
+ gettimeofday( &tv_after, NULL );
+ print_time( "BigPtrArray - append", tv_before, tv_after );
+
+ gettimeofday( &tv_before, NULL );
+ BigPtrArray bparr2;
+ for ( int i = 0; i < 1000000; i++ )
+ bparr2.Insert( new BigPtrEntryMock(i), 0 );
+ gettimeofday( &tv_after, NULL );
+ print_time( "BigPtrArray - insert at front", tv_before, tv_after );
+
+ gettimeofday( &tv_before, NULL );
+ DenseBPlusTree< int, BigPtrEntryMock* > aTest;
+ for ( int i = 0; i < 1000000; ++i )
+ aTest.Insert( new BigPtrEntryMock(i), aTest.Count() );
+ gettimeofday( &tv_after, NULL );
+ print_time( "DenseBPlusTree - append", tv_before, tv_after );
+
+ gettimeofday( &tv_before, NULL );
+ DenseBPlusTree< int, BigPtrEntryMock* > aTest2;
+ for ( int i = 0; i < 1000000; ++i )
+ aTest2.Insert( new BigPtrEntryMock(i), 0 );
+ gettimeofday( &tv_after, NULL );
+ print_time( "DenseBPlusTree - insert at front", tv_before, tv_after );
+
+ return 0;
+}
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
commit a341d834d76b3c06e4e767efa2dc09f9ac8ca8ba
Author: Jan Holesovsky <kendy at suse.cz>
Date: Tue Jan 29 18:06:53 2013 +0100
Dense B+ tree: Data structure update from the B+ tree.
It turns out that the 'classic' B+ tree is not exactly what we need for the
BipPtrArray replacement; but when we do a small change, it fits perfectly.
The problem with B+ tree is that it is designed for non-sequential keys,
not for a sequence of keys (ints) without holes. Even worse - the insert() on
B+ tree does not shift the rest of the values 'to the right' which is what we
need here.
But if we modify the nodes so that instead of absolute key values we use
relative ones, and to count the exact index we de-facto sum the indexes of the
nodes that lead to the node, we get exactly what we want - insert that shifts
the rest of the values to the right is possible in O(log_order(n)).
Due to the lack of name for this B+ tree modification, I name it 'dense B+
tree' - maybe there already is an existing name for this structure, but I do
not recall one.
Change-Id: If1cd769760aa7a2a6b027b9fa54d883540d875ad
diff --git a/sw/inc/densebplustree.cxx b/sw/inc/densebplustree.cxx
index 93ecf1f..ec779bd 100644
--- a/sw/inc/densebplustree.cxx
+++ b/sw/inc/densebplustree.cxx
@@ -7,128 +7,158 @@
* file, You can obtain one at http://mozilla.org/MPL/2.0/.
*/
-#include <bplustree.hxx>
+#include <densebplustree.hxx>
#include <cassert>
+/** The tree node order
+
+This affects how big are the metadata and data nodes; the higher the value,
+the flatter the structure is. It is necessary to find a good compromise
+between fragmentation (too low value) and not being too flat (too high value).
+
+50 seems to be a good value so far, but we can change it easily.
+*/
+static const int sOrder = 7;
+
/** B+ tree node implementation.
It has to be able to act as an internal node, as well as the leaf node.
*/
template < class Key, class Value >
-struct BPlusTreeNode
+struct DenseBPlusTreeNode
{
- /// The tree node order
- static const int sOrder = 7; /// TODO find out the optimal value here :-)
-
/// The number of children / data entries.
int m_nUsed;
/// The B+ tree has the data only in leaves, so we have to distinguish between internal nodes and leaves.
bool m_bIsInternal : 1;
- /// Keys for this node (meaning intervals in case of internal nodes, real keys otherwise)
- Key m_pKeys[ sOrder ];
+ /** Keys for this node.
+
+ In the internal nodes, the appropriate values get incremented as we
+ insert more and more, and parts of the tree are shifted to the right.
+
+ The real index of a value (when we find it) is a sum of all the
+ appropriate m_pKey's that lead to the value.
+
+ In principle, the m_pKeys should always have 0 in m_pKeys[0], let's
+ implicitly assume that, and not store it at all.
+ */
+ Key m_pKeys[ sOrder - 1 ];
union {
/// Internal node, contains only pointers to other nodes
- BPlusTreeNode m_pChildren[ sOrder ];
+ DenseBPlusTreeNode m_pChildren[ sOrder ];
/// Leaf node, contains data.
Value m_pValues[ sOrder ];
};
/// Pointer to the next node (valid only for the leaf nodes).
- BPlusTreeNode *m_pNext;
+ DenseBPlusTreeNode *m_pNext;
- BPlusTreeNode() : m_nUsed( 0 ), m_pNext( NULL ) {}
+ DenseBPlusTreeNode() : m_nUsed( 0 ), m_bIsInternal( false ), m_pNext( NULL ) {}
};
template < class Key, class Value >
-BPlusTree< Key, Value >::BPlusTree()
- : m_pRoot( new BPlusTreeNode< Key, Value > )
+DenseBPlusTree< Key, Value >::DenseBPlusTree()
+ : m_pRoot( new TreeNode )
{
}
template < class Key, class Value >
-BPlusTree< Key, Value >::~BPlusTree()
+DenseBPlusTree< Key, Value >::~DenseBPlusTree()
{
// TODO
}
template < class Key, class Value >
-Key BPlusTree< Key, Value >::Count() const
+Key DenseBPlusTree< Key, Value >::Count() const
{
// TODO
}
template < class Key, class Value >
-void BPlusTree< Key, Value >::Insert( const Value& rValue, Key nPos )
+void DenseBPlusTree< Key, Value >::Insert( const Value& rValue, Key nPos )
{
// TODO
}
template < class Key, class Value >
-void BPlusTree< Key, Value >::Remove( Key nPos, Key nNumber )
+void DenseBPlusTree< Key, Value >::Remove( Key nPos, Key nNumber )
{
// TODO
}
template < class Key, class Value >
-void BPlusTree< Key, Value >::Move( Key nFrom, Key nTo )
+void DenseBPlusTree< Key, Value >::Move( Key nFrom, Key nTo )
{
// TODO
}
template < class Key, class Value >
-void BPlusTree< Key, Value >::Replace( Key nPos, const Value& rValue )
+void DenseBPlusTree< Key, Value >::Replace( Key nPos, const Value& rValue )
{
- // TODO
+ assert( m_pRoot->m_nUsed > 0 );
+
+ NodeWithIndex aLeaf = searchLeaf( nPos, NULL );
+
+ aLeaf.pNode->m_pValues[ aLeaf.nIndex ] = rValue;
}
template < class Key, class Value >
-const Value& BPlusTree< Key, Value >::operator[]( Key nPos ) const
+const Value& DenseBPlusTree< Key, Value >::operator[]( Key nPos ) const
{
assert( m_pRoot->m_nUsed > 0 );
- BPlusTreeNode< Key, Value > *pNode = m_pRoot;
+ NodeWithIndex aLeaf = searchLeaf( nPos, NULL );
- // recursion is nice for the alg. description, but for implementation, we
- // want to unwind it
- while ( pNode->m_bIsInternal )
- {
- for ( int i = 0; i < pNode->m_nUsed - 1 ; ++i )
- {
- if ( nPos < pNode->m_pKeys[ i ] )
- {
- pNode = pNode->m_pChildren[ i ];
- break;
- }
- }
- pNode = pNode->m_pChildren[ pNode->m_nUsed - 1 ];
- }
-
- // now we have the leaf node
- for ( int i = 0; i < pNode->m_nUsed; ++i )
- {
- if ( nPos == pNode->m_pKeys[ i ] )
- return pNode->m_pValues[ i ];
- }
-
- // we do not allow not finding a value so far
- assert( false );
+ return aLeaf.pNode->m_pValues[ aLeaf.nIndex ];
}
template < class Key, class Value >
-void BPlusTree< Key, Value >::ForEach( FnForEach fn, void* pArgs )
+void DenseBPlusTree< Key, Value >::ForEach( FnForEach fn, void* pArgs )
{
// TODO
}
template < class Key, class Value >
-void BPlusTree< Key, Value >::ForEach( Key nStart, Key nEnd, FnForEach fn, void* pArgs )
+void DenseBPlusTree< Key, Value >::ForEach( Key nStart, Key nEnd, FnForEach fn, void* pArgs )
{
// TODO
}
+template < class Key, class Value >
+typename DenseBPlusTree< Key, Value >::NodeWithIndex DenseBPlusTree< Key, Value >::searchLeaf( Key nPos, std::stack< NodeWithIndex > *pParents )
+{
+ if ( m_pRoot->m_nUsed == 0 )
+ return NodeWithIndex( m_pRoot, -1 );
+
+ TreeNode *pNode = m_pRoot;
+
+ // recursion is nice for the alg. description, but for implementation, we
+ // want to unwind it
+ while ( pNode->m_bIsInternal )
+ {
+ int i = 0;
+ while ( i < pNode->m_nUsed - 1 && pNode->m_pKeys[ i ] <= nPos )
+ ++i;
+
+ // m_pKeys in children are relative
+ if ( i > 0 )
+ nPos -= pNode->m_pKeys[ i - 1 ];
+
+ if ( pParents )
+ pParents->push_back( NodeWithIndex( pNode, i ) );
+
+ pNode = pNode->m_pChildren[ i ];
+ }
+
+ // now we have the leaf node, check that we are not out of bounds
+ assert( nPos < pNode->m_nUsed );
+
+ return NodeWithIndex( pNode, nPos );
+}
+
/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sw/inc/densebplustree.hxx b/sw/inc/densebplustree.hxx
index c42d5d1..cf0c9ff 100644
--- a/sw/inc/densebplustree.hxx
+++ b/sw/inc/densebplustree.hxx
@@ -24,30 +24,46 @@
#include <osl/diagnose.h>
#include <swdllapi.h>
-template < class Key, class Value > struct BPlusTreeNode;
+#include <stack>
-/** B+ Tree implementation (to replace the original BigPtrArray).
+template < class Key, class Value > struct DenseBPlusTreeNode;
-For more information about B+ Tree, please see eg. wikipedia:
+/** Dense B+ tree implementation (to replace the original BigPtrArray).
+
+This structure is a modification of a B+ tree, see eg. wikipedia:
http://en.wikipedia.org/wiki/B%2B_tree
+for the B+ tree implementation.
+
+The problem with 'classic' B+ tree is that it is designed for key/value access
+where the key typically is not a sequence of numbers. Consequently, it does
+not easily allow inserting in a sense that 'the rest of the values shift to
+the right' - but that is the operation that we need to do effectively.
+
+We do a small modification to the B+ tree implementation to make it 'dense' -
+the keys are supposed to be a sequence, and if you insert a value, all shifts
+to the right. The trick to achieve it is that the values that are stored in
+the internal nodes are not absolute, but are relative; so whatever is in the
+parents is propagated to the children. That way, shifting half of the tree by
+1 to the right after insertion is just a matter of adding 1 to the appropriate
+parent.
As part of the removal of BigPtrArray (and consequent refactor of the related
-code), this BPlusTree is supposed to be a drop-in replacement, with some of
+code), this structur is supposed to be a drop-in replacement, with some of
the functionality templatized for easier use.
Key is sal_uLong in the BigPtrArray implementation.
Value is supposed to be SwNodePtr initially.
*/
template < class Key, class Value >
-class SW_DLLPUBLIC BPlusTree
+class SW_DLLPUBLIC DenseBPlusTree
{
public:
/// Callback function to be called during ForEach.
typedef bool (*FnForEach)( const Value&, void* pArgs );
public:
- BPlusTree();
- ~BPlusTree();
+ DenseBPlusTree();
+ ~DenseBPlusTree();
/// Number of elements.
Key Count() const;
@@ -74,7 +90,25 @@ public:
void ForEach( Key nStart, Key nEnd, FnForEach fn, void* pArgs = NULL );
private:
- BPlusTreeNode< Key, Value > *m_pRoot;
+ typedef DenseBPlusTreeNode< Key, Value > TreeNode;
+
+ /// We need to know the exact path from the root to the leaf, including the indexes for various operations
+ struct NodeWithIndex {
+ TreeNode *pNode;
+ Key nIndex;
+
+ NodeWithIndex( TreeNode *p, Key n ) : pNode( p ), nIndex( n ) {}
+ };
+
+ /// Root of the tree.
+ TreeNode *m_pRoot;
+
+ /** 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
+ */
+ NodeWithIndex searchLeaf( Key nPos, std::stack< NodeWithIndex > *pParents = NULL );
};
#endif // SW_BPLUSTREE_HXX
commit fe9d587d1b544a2faa1a994fdcfaee0bfa58210f
Author: Jan Holesovsky <kendy at suse.cz>
Date: Tue Jan 29 18:04:26 2013 +0100
Dense B+ tree: Rename the files, classic B+ tree is not enough.
Change-Id: If078d961e69eb79088a680cbec02036d75f064c7
diff --git a/sw/Library_sw.mk b/sw/Library_sw.mk
index 6690cc0..264e35a 100644
--- a/sw/Library_sw.mk
+++ b/sw/Library_sw.mk
@@ -116,7 +116,6 @@ $(eval $(call gb_Library_add_exception_objects,sw,\
sw/source/core/attr/swatrset \
sw/source/core/bastyp/SwSmartTagMgr \
sw/source/core/bastyp/bparr \
- sw/source/core/bastyp/bplustree \
sw/source/core/bastyp/breakit \
sw/source/core/bastyp/calc \
sw/source/core/bastyp/checkit \
diff --git a/sw/inc/bplustree.hxx b/sw/inc/bplustree.hxx
deleted file mode 100644
index c42d5d1..0000000
--- a/sw/inc/bplustree.hxx
+++ /dev/null
@@ -1,82 +0,0 @@
-/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
-/*
- * This file is part of the LibreOffice project.
- *
- * This Source Code Form is subject to the terms of the Mozilla Public
- * License, v. 2.0. If a copy of the MPL was not distributed with this
- * file, You can obtain one at http://mozilla.org/MPL/2.0/.
- *
- * This file incorporates work covered by the following license notice:
- *
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed
- * with this work for additional information regarding copyright
- * ownership. The ASF licenses this file to you under the Apache
- * License, Version 2.0 (the "License"); you may not use this file
- * except in compliance with the License. You may obtain a copy of
- * the License at http://www.apache.org/licenses/LICENSE-2.0 .
- */
-
-#ifndef SW_BPLUSTREE_HXX
-#define SW_BPLUSTREE_HXX
-
-#include <tools/solar.h>
-#include <osl/diagnose.h>
-#include <swdllapi.h>
-
-template < class Key, class Value > struct BPlusTreeNode;
-
-/** B+ Tree implementation (to replace the original BigPtrArray).
-
-For more information about B+ Tree, please see eg. wikipedia:
-http://en.wikipedia.org/wiki/B%2B_tree
-
-As part of the removal of BigPtrArray (and consequent refactor of the related
-code), this BPlusTree is supposed to be a drop-in replacement, with some of
-the functionality templatized for easier use.
-
-Key is sal_uLong in the BigPtrArray implementation.
-Value is supposed to be SwNodePtr initially.
-*/
-template < class Key, class Value >
-class SW_DLLPUBLIC BPlusTree
-{
-public:
- /// Callback function to be called during ForEach.
- typedef bool (*FnForEach)( const Value&, void* pArgs );
-
-public:
- BPlusTree();
- ~BPlusTree();
-
- /// Number of elements.
- Key Count() const;
-
- /// Insert entry at the specified position.
- void Insert( const Value& rValue, Key nPos );
-
- /// Remove nNumber entries starting at the position nPos.
- void Remove( Key nPos, Key nNumber = 1 );
-
- /// Insert the value of 'nFrom' to the position 'nTo', and remove the original value.
- void Move( Key nFrom, Key nTo );
-
- /// Exchange the value on position pos with the new one.
- void Replace( Key nPos, const Value& rValue );
-
- /// Field access.
- const Value& operator[]( Key nPos ) const;
-
- /// Traverse over the entire data, and call fn on the data.
- void ForEach( FnForEach fn, void* pArgs = NULL );
-
- /// Traverse over the specified range, and call fn on the data.
- void ForEach( Key nStart, Key nEnd, FnForEach fn, void* pArgs = NULL );
-
-private:
- BPlusTreeNode< Key, Value > *m_pRoot;
-};
-
-#endif // SW_BPLUSTREE_HXX
-
-/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sw/inc/densebplustree.cxx b/sw/inc/densebplustree.cxx
new file mode 100644
index 0000000..93ecf1f
--- /dev/null
+++ b/sw/inc/densebplustree.cxx
@@ -0,0 +1,134 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * This file is part of the LibreOffice project.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ */
+
+#include <bplustree.hxx>
+
+#include <cassert>
+
+/** B+ tree node implementation.
+
+It has to be able to act as an internal node, as well as the leaf node.
+*/
+template < class Key, class Value >
+struct BPlusTreeNode
+{
+ /// The tree node order
+ static const int sOrder = 7; /// TODO find out the optimal value here :-)
+
+ /// The number of children / data entries.
+ int m_nUsed;
+
+ /// The B+ tree has the data only in leaves, so we have to distinguish between internal nodes and leaves.
+ bool m_bIsInternal : 1;
+
+ /// Keys for this node (meaning intervals in case of internal nodes, real keys otherwise)
+ Key m_pKeys[ sOrder ];
+
+ union {
+ /// Internal node, contains only pointers to other nodes
+ BPlusTreeNode m_pChildren[ sOrder ];
+
+ /// Leaf node, contains data.
+ Value m_pValues[ sOrder ];
+ };
+
+ /// Pointer to the next node (valid only for the leaf nodes).
+ BPlusTreeNode *m_pNext;
+
+ BPlusTreeNode() : m_nUsed( 0 ), m_pNext( NULL ) {}
+};
+
+template < class Key, class Value >
+BPlusTree< Key, Value >::BPlusTree()
+ : m_pRoot( new BPlusTreeNode< Key, Value > )
+{
+}
+
+template < class Key, class Value >
+BPlusTree< Key, Value >::~BPlusTree()
+{
+ // TODO
+}
+
+template < class Key, class Value >
+Key BPlusTree< Key, Value >::Count() const
+{
+ // TODO
+}
+
+template < class Key, class Value >
+void BPlusTree< Key, Value >::Insert( const Value& rValue, Key nPos )
+{
+ // TODO
+}
+
+template < class Key, class Value >
+void BPlusTree< Key, Value >::Remove( Key nPos, Key nNumber )
+{
+ // TODO
+}
+
+template < class Key, class Value >
+void BPlusTree< Key, Value >::Move( Key nFrom, Key nTo )
+{
+ // TODO
+}
+
+template < class Key, class Value >
+void BPlusTree< Key, Value >::Replace( Key nPos, const Value& rValue )
+{
+ // TODO
+}
+
+template < class Key, class Value >
+const Value& BPlusTree< Key, Value >::operator[]( Key nPos ) const
+{
+ assert( m_pRoot->m_nUsed > 0 );
+
+ BPlusTreeNode< Key, Value > *pNode = m_pRoot;
+
+ // recursion is nice for the alg. description, but for implementation, we
+ // want to unwind it
+ while ( pNode->m_bIsInternal )
+ {
+ for ( int i = 0; i < pNode->m_nUsed - 1 ; ++i )
+ {
+ if ( nPos < pNode->m_pKeys[ i ] )
+ {
+ pNode = pNode->m_pChildren[ i ];
+ break;
+ }
+ }
+ pNode = pNode->m_pChildren[ pNode->m_nUsed - 1 ];
+ }
+
+ // now we have the leaf node
+ for ( int i = 0; i < pNode->m_nUsed; ++i )
+ {
+ if ( nPos == pNode->m_pKeys[ i ] )
+ return pNode->m_pValues[ i ];
+ }
+
+ // we do not allow not finding a value so far
+ assert( false );
+}
+
+template < class Key, class Value >
+void BPlusTree< Key, Value >::ForEach( FnForEach fn, void* pArgs )
+{
+ // TODO
+}
+
+template < class Key, class Value >
+void BPlusTree< Key, Value >::ForEach( Key nStart, Key nEnd, FnForEach fn, void* pArgs )
+{
+ // TODO
+}
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sw/inc/densebplustree.hxx b/sw/inc/densebplustree.hxx
new file mode 100644
index 0000000..c42d5d1
--- /dev/null
+++ b/sw/inc/densebplustree.hxx
@@ -0,0 +1,82 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * This file is part of the LibreOffice project.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ *
+ * This file incorporates work covered by the following license notice:
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed
+ * with this work for additional information regarding copyright
+ * ownership. The ASF licenses this file to you under the Apache
+ * License, Version 2.0 (the "License"); you may not use this file
+ * except in compliance with the License. You may obtain a copy of
+ * the License at http://www.apache.org/licenses/LICENSE-2.0 .
+ */
+
+#ifndef SW_BPLUSTREE_HXX
+#define SW_BPLUSTREE_HXX
+
+#include <tools/solar.h>
+#include <osl/diagnose.h>
+#include <swdllapi.h>
+
+template < class Key, class Value > struct BPlusTreeNode;
+
+/** B+ Tree implementation (to replace the original BigPtrArray).
+
+For more information about B+ Tree, please see eg. wikipedia:
+http://en.wikipedia.org/wiki/B%2B_tree
+
+As part of the removal of BigPtrArray (and consequent refactor of the related
+code), this BPlusTree is supposed to be a drop-in replacement, with some of
+the functionality templatized for easier use.
+
+Key is sal_uLong in the BigPtrArray implementation.
+Value is supposed to be SwNodePtr initially.
+*/
+template < class Key, class Value >
+class SW_DLLPUBLIC BPlusTree
+{
+public:
+ /// Callback function to be called during ForEach.
+ typedef bool (*FnForEach)( const Value&, void* pArgs );
+
+public:
+ BPlusTree();
+ ~BPlusTree();
+
+ /// Number of elements.
+ Key Count() const;
+
+ /// Insert entry at the specified position.
+ void Insert( const Value& rValue, Key nPos );
+
+ /// Remove nNumber entries starting at the position nPos.
+ void Remove( Key nPos, Key nNumber = 1 );
+
+ /// Insert the value of 'nFrom' to the position 'nTo', and remove the original value.
+ void Move( Key nFrom, Key nTo );
+
+ /// Exchange the value on position pos with the new one.
+ void Replace( Key nPos, const Value& rValue );
+
+ /// Field access.
+ const Value& operator[]( Key nPos ) const;
+
+ /// Traverse over the entire data, and call fn on the data.
+ void ForEach( FnForEach fn, void* pArgs = NULL );
+
+ /// Traverse over the specified range, and call fn on the data.
+ void ForEach( Key nStart, Key nEnd, FnForEach fn, void* pArgs = NULL );
+
+private:
+ BPlusTreeNode< Key, Value > *m_pRoot;
+};
+
+#endif // SW_BPLUSTREE_HXX
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sw/source/core/bastyp/bplustree.cxx b/sw/source/core/bastyp/bplustree.cxx
deleted file mode 100644
index 93ecf1f..0000000
--- a/sw/source/core/bastyp/bplustree.cxx
+++ /dev/null
@@ -1,134 +0,0 @@
-/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
-/*
- * This file is part of the LibreOffice project.
- *
- * This Source Code Form is subject to the terms of the Mozilla Public
- * License, v. 2.0. If a copy of the MPL was not distributed with this
- * file, You can obtain one at http://mozilla.org/MPL/2.0/.
- */
-
-#include <bplustree.hxx>
-
-#include <cassert>
-
-/** B+ tree node implementation.
-
-It has to be able to act as an internal node, as well as the leaf node.
-*/
-template < class Key, class Value >
-struct BPlusTreeNode
-{
- /// The tree node order
- static const int sOrder = 7; /// TODO find out the optimal value here :-)
-
- /// The number of children / data entries.
- int m_nUsed;
-
- /// The B+ tree has the data only in leaves, so we have to distinguish between internal nodes and leaves.
- bool m_bIsInternal : 1;
-
- /// Keys for this node (meaning intervals in case of internal nodes, real keys otherwise)
- Key m_pKeys[ sOrder ];
-
- union {
- /// Internal node, contains only pointers to other nodes
- BPlusTreeNode m_pChildren[ sOrder ];
-
- /// Leaf node, contains data.
- Value m_pValues[ sOrder ];
- };
-
- /// Pointer to the next node (valid only for the leaf nodes).
- BPlusTreeNode *m_pNext;
-
- BPlusTreeNode() : m_nUsed( 0 ), m_pNext( NULL ) {}
-};
-
-template < class Key, class Value >
-BPlusTree< Key, Value >::BPlusTree()
- : m_pRoot( new BPlusTreeNode< Key, Value > )
-{
-}
-
-template < class Key, class Value >
-BPlusTree< Key, Value >::~BPlusTree()
-{
- // TODO
-}
-
-template < class Key, class Value >
-Key BPlusTree< Key, Value >::Count() const
-{
- // TODO
-}
-
-template < class Key, class Value >
-void BPlusTree< Key, Value >::Insert( const Value& rValue, Key nPos )
-{
- // TODO
-}
-
-template < class Key, class Value >
-void BPlusTree< Key, Value >::Remove( Key nPos, Key nNumber )
-{
- // TODO
-}
-
-template < class Key, class Value >
-void BPlusTree< Key, Value >::Move( Key nFrom, Key nTo )
-{
- // TODO
-}
-
-template < class Key, class Value >
-void BPlusTree< Key, Value >::Replace( Key nPos, const Value& rValue )
-{
- // TODO
-}
-
-template < class Key, class Value >
-const Value& BPlusTree< Key, Value >::operator[]( Key nPos ) const
-{
- assert( m_pRoot->m_nUsed > 0 );
-
- BPlusTreeNode< Key, Value > *pNode = m_pRoot;
-
- // recursion is nice for the alg. description, but for implementation, we
- // want to unwind it
- while ( pNode->m_bIsInternal )
- {
- for ( int i = 0; i < pNode->m_nUsed - 1 ; ++i )
- {
- if ( nPos < pNode->m_pKeys[ i ] )
- {
- pNode = pNode->m_pChildren[ i ];
- break;
- }
- }
- pNode = pNode->m_pChildren[ pNode->m_nUsed - 1 ];
- }
-
- // now we have the leaf node
- for ( int i = 0; i < pNode->m_nUsed; ++i )
- {
- if ( nPos == pNode->m_pKeys[ i ] )
- return pNode->m_pValues[ i ];
- }
-
- // we do not allow not finding a value so far
- assert( false );
-}
-
-template < class Key, class Value >
-void BPlusTree< Key, Value >::ForEach( FnForEach fn, void* pArgs )
-{
- // TODO
-}
-
-template < class Key, class Value >
-void BPlusTree< Key, Value >::ForEach( Key nStart, Key nEnd, FnForEach fn, void* pArgs )
-{
- // TODO
-}
-
-/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
More information about the Libreoffice-commits
mailing list