sw/inc/densebplustree.cxx | 230 +++++++++++++++++++++++++++++-----------------
sw/inc/densebplustree.hxx | 21 ++--
2 files changed, 160 insertions(+), 91 deletions(-)
New commits:
commit 8636a6d557772e6d566d59151b5ba559993faf0b
Author: Jan Holesovsky <ke...@suse.cz>
Date: Wed Feb 6 22:31:43 2013 +0100
Dense B+ tree: Remove root / one level if possible.
Change-Id: Icf76e6c711f43daa021baae47cb54cc2e4e5b0d4
diff --git a/sw/inc/densebplustree.cxx b/sw/inc/densebplustree.cxx
index a4469c2..b0b034c 100644
--- a/sw/inc/densebplustree.cxx
+++ b/sw/inc/densebplustree.cxx
@@ -308,6 +308,15 @@ void DenseBPlusTree< Key, Value, Order >::Remove( Key
nPos, Key nNumber )
}
m_nCount -= nNumber;
+
+ // remove one level, if needed
+ if ( m_pRoot->m_nUsed == 1 )
+ {
+ DBPTreeNode< Key, Value, Order > *pToDelete = m_pRoot;
+ m_pRoot = m_pRoot->m_pChildren[0];
+ delete pToDelete;
+ --m_nDepth;
+ }
}
template < class Key, class Value, int Order >
commit 53b715fc8afcd1f901d4a3e061255bec73f52668
Author: Jan Holesovsky <ke...@suse.cz>
Date: Wed Feb 6 22:24:07 2013 +0100
Dense B+ tree: Joining during Delete() partially works.
More work & testing still needed to make it really good, though.
Change-Id: Ia2f0c24fd1a71a58a5fea948afaa41adcc9ac66a
diff --git a/sw/inc/densebplustree.cxx b/sw/inc/densebplustree.cxx
index fa9156f..a4469c2 100644
--- a/sw/inc/densebplustree.cxx
+++ b/sw/inc/densebplustree.cxx
@@ -163,6 +163,58 @@ struct DBPTreeNode
return offset;
}
+
+ /** Move nCount data from pNode.
+
+ Join them into one node, in case we fit there.
+
+ @param offset the parent offsed of the pNode
+ @return we have joined the nodes into one, and deleted pNode
+ */
+ bool moveFromNextOrJoin( int nCount, int offset )
+ {
+ assert( nCount > 0 );
+ assert( m_nUsed < Order );
+
+ printf( "moveFromNextOrJoin()\n" );
+
+ if ( m_nUsed + m_pNext->m_nUsed < Order )
+ nCount = m_pNext->m_nUsed;
+
+ if ( m_bIsInternal )
+ {
+ for ( int i = 0; i < nCount; ++i )
+ m_pChildren[ m_nUsed + i ] = m_pNext->m_pChildren[ i ];
+ for ( int i = 0; i < m_pNext->m_nUsed - nCount; ++i )
+ m_pNext->m_pChildren[ i ] = m_pNext->m_pChildren[ i + nCount ];
+
+ m_pKeys[ m_nUsed - 1 ] = offset;
+ for ( int i = 0; i < nCount - 1; ++i )
+ m_pKeys[ m_nUsed + i ] = m_pNext->m_pKeys[ i ] + offset;
+ for ( int i = 0; i < m_pNext->m_nUsed - nCount - 1; ++i )
+ m_pNext->m_pKeys[ i ] = m_pNext->m_pKeys[ i + nCount ];
+ }
+ else
+ {
+ for ( int i = 0; i < nCount; ++i )
+ m_pValues[ m_nUsed + i ] = m_pNext->m_pValues[ i ];
+ for ( int i = 0; i < m_pNext->m_nUsed - nCount; ++i )
+ m_pNext->m_pValues[ i ] = m_pNext->m_pValues[ i + nCount ];
+ }
+
+ bool bJoining = false;
+ m_pNext->m_nUsed -= nCount;
+ if ( m_pNext->m_nUsed == 0 )
+ {
+ DBPTreeNode *pNode = m_pNext;
+ m_pNext = pNode->m_pNext;
+ delete pNode;
+ bJoining = true;
+ }
+
+ m_nUsed += nCount;
+ return bJoining;
+ }
};
template < class Key, class Value, int Order >
@@ -223,7 +275,7 @@ void DenseBPlusTree< Key, Value, Order >::Remove( Key nPos,
Key nNumber )
assert( nNumber > 0 );
assert( nPos + nNumber <= m_nCount );
- const int sMinFill = ( Order / 2 ) - 1;
+ const int sMinFill = ( Order / 2 );
NodeWithIndex pParents[ m_nDepth ];
int nParentsLength = 0;
@@ -252,13 +304,7 @@ void DenseBPlusTree< Key, Value, Order >::Remove( Key
nPos, Key nNumber )
removeBetween( pParents, pAfterParents, nParentsLength + 1 );
// update indexes
- shiftNodes( pParents, nParentsLength, aAfter.nIndex - nNumber );
-
- // FIXME we have to create a function that walks up the parents to do
- // this right even in the case nIndex == m_nUsed
- if ( pParents[ nParentsLength - 1 ].nIndex < pParents[ nParentsLength
- 1 ].pNode->m_nUsed - 1 )
- ++pParents[ nParentsLength - 1 ].nIndex;
- shiftNodes( pParents, nParentsLength, -aAfter.nIndex );
+ shiftNodes( pAfterParents, nAfterParentsLength, -nNumber );
}
m_nCount -= nNumber;
@@ -454,21 +500,42 @@ DBPTreeNode< Key, Value, Order >* DenseBPlusTree< Key,
Value, Order >::splitNode
template < class Key, class Value, int Order >
void DenseBPlusTree< Key, Value, Order >::removeBetween( const NodeWithIndex
pFrom[], const NodeWithIndex pTo[], int nLength )
{
- for ( int p = 0; p < nLength; ++p )
+ const int sMinFill = ( Order / 2 );
+ bool bJoined = false;
+
+ for ( int p = nLength - 1; p >= 0; --p )
{
const NodeWithIndex &rLeaf = pFrom[ p ];
const NodeWithIndex &rAfter = pTo[ p ];
if ( rLeaf.pNode == rAfter.pNode )
{
+ if ( rLeaf.nIndex == rAfter.nIndex && !bJoined )
+ return; // we are done
+
// we need to keep parents of the 'from' branch too
- if ( rLeaf.pNode->m_bIsInternal )
+ DBPTreeNode< Key, Value, Order > *pNode = rLeaf.pNode;
+ if ( !rLeaf.pNode->m_bIsInternal || ( rLeaf.pNode->m_bIsInternal
&& !bJoined ) )
+ rLeaf.pNode->remove( rLeaf.nIndex, rAfter.nIndex -
rLeaf.nIndex );
+ else
{
- if ( rAfter.nIndex - rLeaf.nIndex - 1 > 0 )
- rLeaf.pNode->remove( rLeaf.nIndex + 1, rAfter.nIndex -
rLeaf.nIndex - 1 );
+ if ( rLeaf.nIndex + 1 < rLeaf.pNode->m_nUsed )
+ rLeaf.pNode->remove( rLeaf.nIndex + 1, rAfter.nIndex -
rLeaf.nIndex + 1 );
+ else
+ {
+ pNode = rLeaf.pNode->m_pNext;
+ pNode->remove( 0, rAfter.nIndex - rLeaf.nIndex + 1 );
+ }
+ }
+
+ if ( pNode->m_nUsed < sMinFill && pNode->m_pNext != NULL && p > 0 )
+ {
+ const NodeWithIndex &rParent = pFrom[ p - 1 ];
+ bJoined = pNode->moveFromNextOrJoin( sMinFill - pNode->m_nUsed,
+ rParent.pNode->m_pKeys[ rParent.nIndex ] );
}
else
- rLeaf.pNode->remove( rLeaf.nIndex, rAfter.nIndex -
rLeaf.nIndex );
+ bJoined = false;
}
else
{
@@ -489,6 +556,8 @@ void DenseBPlusTree< Key, Value, Order >::removeBetween(
const NodeWithIndex pFr
// reconnect
rLeaf.pNode->m_pNext = rAfter.pNode;
+
+ // FIXME not finished - need to moveFromNextOrJoin() too
}
}
}
commit 6363355f56062c6cb566ed27d8cb847d8c919c00
Author: Jan Holesovsky <ke...@suse.cz>
Date: Tue Feb 5 22:04:49 2013 +0100
Dense B+ tree: Get the order as a template parameter.
For testing, we need some small order (6 or so) so that the structure is
very
tree-ish. For real use, we want something like 50, so that it is a bit more
flat.
Change-Id: If1a24d57bcb29b6381f7a5b1114a29dcf15533aa
diff --git a/sw/inc/densebplustree.cxx b/sw/inc/densebplustree.cxx
index bb00a7a..fa9156f 100644
--- a/sw/inc/densebplustree.cxx
+++ b/sw/inc/densebplustree.cxx
@@ -17,27 +17,11 @@
using namespace std;
-/** 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 if necessary.
-*/
-static const int sOrder = 50;
-
-/** Minimum fill of a node.
-
-Nodes except the rightmost ones will never have less than this number.
-*/
-static const int sMinFill = ( sOrder / 2 ) - 1;
-
/** 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 >
+template < class Key, class Value, int Order >
struct DBPTreeNode
{
/// The number of children / data entries.
@@ -57,14 +41,14 @@ struct DBPTreeNode
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 ];
+ Key m_pKeys[ Order - 1 ];
union {
/// Internal node, contains only pointers to other nodes
- DBPTreeNode* m_pChildren[ sOrder ];
+ DBPTreeNode* m_pChildren[ Order ];
/// Leaf node, contains data.
- Value m_pValues[ sOrder ];
+ Value m_pValues[ Order ];
};
/// Pointer to the next node (valid only for the leaf nodes).
@@ -77,7 +61,7 @@ struct DBPTreeNode
{
assert( !m_bIsInternal );
assert( nWhere <= m_nUsed );
- assert( nWhere < sOrder );
+ assert( nWhere < Order );
for ( int i = m_nUsed; i > nWhere; --i )
m_pValues[ i ] = m_pValues[ i - 1 ];
@@ -91,7 +75,7 @@ struct DBPTreeNode
{
assert( m_bIsInternal );
assert( nWhere <= m_nUsed );
- assert( nWhere < sOrder );
+ assert( nWhere < Order );
assert( nWhere > 0 ); // we always add the node to the right when
splitting
for ( int i = m_nUsed; i > nWhere; --i )
@@ -140,15 +124,15 @@ struct DBPTreeNode
*/
int copyFromSplitNode( DBPTreeNode *pNode, bool bIsAppend )
{
- assert( sOrder > 2 );
- assert( pNode->m_nUsed == sOrder );
+ assert( Order > 2 );
+ assert( pNode->m_nUsed == Order );
// we optimize for the case of appending
// it is expected that we first create the entire structure (so want
// it to be dense from the space point of view), but when performing
// later, the distribution has to be 'fair', because the access is
// more or less random
- int nHowMuchKeep = bIsAppend? sOrder - 2: sOrder / 2;
+ int nHowMuchKeep = bIsAppend? Order - 2: Order / 2;
int offset = 0;
@@ -181,34 +165,33 @@ struct DBPTreeNode
}
};
-template < class Key, class Value >
-DenseBPlusTree< Key, Value >::DenseBPlusTree()
- : m_pRoot( new DBPTreeNode< Key, Value > ),
+template < class Key, class Value, int Order >
+DenseBPlusTree< Key, Value, Order >::DenseBPlusTree()
+ : m_pRoot( new DBPTreeNode< Key, Value, Order > ),
m_pLastLeaf( m_pRoot ),
m_nCount( 0 ),
m_nDepth( 1 )
{
- assert( sMinFill > 0 ); // just to be sure ;-)
}
-template < class Key, class Value >
-DenseBPlusTree< Key, Value >::~DenseBPlusTree()
+template < class Key, class Value, int Order >
+DenseBPlusTree< Key, Value, Order >::~DenseBPlusTree()
{
// TODO
}
-template < class Key, class Value >
-void DenseBPlusTree< Key, Value >::Insert( const Value& rValue, Key nPos )
+template < class Key, class Value, int Order >
+void DenseBPlusTree< Key, Value, Order >::Insert( const Value& rValue, Key
nPos )
{
NodeWithIndex pParents[ m_nDepth ];
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 )
+ if ( nPos != m_nCount || m_pLastLeaf->m_nUsed == Order )
aLeaf = findLeaf( nPos, pParents, nParentsLength );
- if ( aLeaf.pNode->m_nUsed < sOrder )
+ if ( aLeaf.pNode->m_nUsed < Order )
{
// there's still space in the current node
aLeaf.pNode->insert( aLeaf.nIndex, rValue );
@@ -218,7 +201,7 @@ void DenseBPlusTree< Key, Value >::Insert( const Value&
rValue, Key nPos )
{
NodeWithIndex pNewParents[ m_nDepth ];
int nNewParentsLength;
- DBPTreeNode< Key, Value > *pNewLeaf = splitNode( aLeaf.pNode, nPos ==
m_nCount, pParents, nParentsLength, pNewParents, nNewParentsLength );
+ DBPTreeNode< Key, Value, Order > *pNewLeaf = splitNode( aLeaf.pNode,
nPos == m_nCount, pParents, nParentsLength, pNewParents, nNewParentsLength );
if ( aLeaf.nIndex <= aLeaf.pNode->m_nUsed )
aLeaf.pNode->insert( aLeaf.nIndex, rValue );
@@ -234,12 +217,14 @@ void DenseBPlusTree< Key, Value >::Insert( const Value&
rValue, Key nPos )
++m_nCount;
}
-template < class Key, class Value >
-void DenseBPlusTree< Key, Value >::Remove( Key nPos, Key nNumber )
+template < class Key, class Value, int Order >
+void DenseBPlusTree< Key, Value, Order >::Remove( Key nPos, Key nNumber )
{
assert( nNumber > 0 );
assert( nPos + nNumber <= m_nCount );
+ const int sMinFill = ( Order / 2 ) - 1;
+
NodeWithIndex pParents[ m_nDepth ];
int nParentsLength = 0;
NodeWithIndex aLeaf = findLeaf( nPos, pParents, nParentsLength );
@@ -279,14 +264,14 @@ void DenseBPlusTree< Key, Value >::Remove( Key nPos, Key
nNumber )
m_nCount -= nNumber;
}
-template < class Key, class Value >
-void DenseBPlusTree< Key, Value >::Move( Key nFrom, Key nTo )
+template < class Key, class Value, int Order >
+void DenseBPlusTree< Key, Value, Order >::Move( Key nFrom, Key nTo )
{
// TODO
}
-template < class Key, class Value >
-void DenseBPlusTree< Key, Value >::Replace( Key nPos, const Value& rValue )
+template < class Key, class Value, int Order >
+void DenseBPlusTree< Key, Value, Order >::Replace( Key nPos, const Value&
rValue )
{
assert( m_pRoot->m_nUsed > 0 );
@@ -295,8 +280,8 @@ void DenseBPlusTree< Key, Value >::Replace( Key nPos, const
Value& rValue )
aLeaf.pNode->m_pValues[ aLeaf.nIndex ] = rValue;
}
-template < class Key, class Value >
-const Value& DenseBPlusTree< Key, Value >::operator[]( Key nPos ) const
+template < class Key, class Value, int Order >
+const Value& DenseBPlusTree< Key, Value, Order >::operator[]( Key nPos ) const
{
assert( m_pRoot->m_nUsed > 0 );
@@ -305,28 +290,28 @@ const Value& DenseBPlusTree< Key, Value >::operator[](
Key nPos ) const
return aLeaf.pNode->m_pValues[ aLeaf.nIndex ];
}
-template < class Key, class Value >
-void DenseBPlusTree< Key, Value >::ForEach( FnForEach fn, void* pArgs )
+template < class Key, class Value, int Order >
+void DenseBPlusTree< Key, Value, Order >::ForEach( FnForEach fn, void* pArgs )
{
// TODO
}
-template < class Key, class Value >
-void DenseBPlusTree< Key, Value >::ForEach( Key nStart, Key nEnd, FnForEach
fn, void* pArgs )
+template < class Key, class Value, int Order >
+void DenseBPlusTree< Key, Value, Order >::ForEach( Key nStart, Key nEnd,
FnForEach fn, void* pArgs )
{
// TODO
}
-template < class Key, class Value >
-void DenseBPlusTree< Key, Value >::dump() const
+template < class Key, class Value, int Order >
+void DenseBPlusTree< Key, Value, Order >::dump() const
{
printf( "======================\nCount: %d\n", Count() );
- vector< DBPTreeNode< Key, Value >* > aLifo;
+ vector< DBPTreeNode< Key, Value, Order >* > aLifo;
aLifo.push_back( m_pRoot );
while ( !aLifo.empty() )
{
- DBPTreeNode< Key, Value > *pNode = aLifo.front();
+ DBPTreeNode< Key, Value, Order > *pNode = aLifo.front();
aLifo.erase( aLifo.begin() );
if ( pNode->m_bIsInternal )
@@ -353,10 +338,10 @@ void DenseBPlusTree< Key, Value >::dump() const
}
}
-template < class Key, class Value >
-typename DenseBPlusTree< Key, Value >::NodeWithIndex DenseBPlusTree< Key,
Value >::findLeaf( Key nPos, NodeWithIndex pParents[], int &rParentsLength )
+template < class Key, class Value, int Order >
+typename DenseBPlusTree< Key, Value, Order >::NodeWithIndex DenseBPlusTree<
Key, Value, Order >::findLeaf( Key nPos, NodeWithIndex pParents[], int
&rParentsLength )
{
- DBPTreeNode< Key, Value > *pNode = m_pRoot;
+ DBPTreeNode< Key, Value, Order > *pNode = m_pRoot;
rParentsLength = 0;
// traverse from the root to the leaves
@@ -395,8 +380,8 @@ typename DenseBPlusTree< Key, Value >::NodeWithIndex
DenseBPlusTree< Key, Value
return NodeWithIndex( pNode, nPos );
}
-template < class Key, class Value >
-void DenseBPlusTree< Key, Value >::shiftNodes( const NodeWithIndex pParents[],
int nParentsLength, int nHowMuch )
+template < class Key, class Value, int Order >
+void DenseBPlusTree< Key, Value, Order >::shiftNodes( const NodeWithIndex
pParents[], int nParentsLength, int nHowMuch )
{
for ( int p = nParentsLength - 1; p >= 0; --p )
{
@@ -406,12 +391,12 @@ void DenseBPlusTree< Key, Value >::shiftNodes( const
NodeWithIndex pParents[], i
}
}
-template < class Key, class Value >
-DBPTreeNode< Key, Value >* DenseBPlusTree< Key, Value >::splitNode(
DBPTreeNode< Key, Value > *pNode, bool bIsAppend, const NodeWithIndex
pParents[], int nParentsLength, NodeWithIndex pNewParents[], int
&rNewParentsLength )
+template < class Key, class Value, int Order >
+DBPTreeNode< Key, Value, Order >* DenseBPlusTree< Key, Value, Order
>::splitNode( DBPTreeNode< Key, Value, Order > *pNode, bool bIsAppend, const
NodeWithIndex pParents[], int nParentsLength, NodeWithIndex pNewParents[], int
&rNewParentsLength )
{
- assert( pNode->m_nUsed == sOrder );
+ assert( pNode->m_nUsed == Order );
- DBPTreeNode< Key, Value > *pNewNode = new DBPTreeNode< Key, Value >;
+ DBPTreeNode< Key, Value, Order > *pNewNode = new DBPTreeNode< Key, Value,
Order >;
int offset = pNewNode->copyFromSplitNode( pNode, bIsAppend );
// update the last leaf if necessary
@@ -421,7 +406,7 @@ DBPTreeNode< Key, Value >* DenseBPlusTree< Key, Value
>::splitNode( DBPTreeNode<
if ( nParentsLength == 0 )
{
// we have to create a new root
- DBPTreeNode< Key, Value > *pNewRoot = new DBPTreeNode< Key, Value >;
+ DBPTreeNode< Key, Value, Order > *pNewRoot = new DBPTreeNode< Key,
Value, Order >;
pNewRoot->m_bIsInternal = true;
pNewRoot->m_pChildren[ 0 ] = m_pRoot;
pNewRoot->m_nUsed = 1;
@@ -438,7 +423,7 @@ DBPTreeNode< Key, Value >* DenseBPlusTree< Key, Value
>::splitNode( DBPTreeNode<
{
NodeWithIndex aParent = pParents[ nParentsLength - 1 ];
- if ( aParent.pNode->m_nUsed < sOrder )
+ if ( aParent.pNode->m_nUsed < Order )
{
aParent.pNode->insert( aParent.nIndex + 1, offset, pNewNode );
@@ -448,7 +433,7 @@ DBPTreeNode< Key, Value >* DenseBPlusTree< Key, Value
>::splitNode( DBPTreeNode<
}
else
{
- DBPTreeNode< Key, Value > *pNewParent = splitNode( aParent.pNode,
bIsAppend, pParents, nParentsLength - 1, pNewParents, rNewParentsLength );
+ DBPTreeNode< Key, Value, Order > *pNewParent = splitNode(
aParent.pNode, bIsAppend, pParents, nParentsLength - 1, pNewParents,
rNewParentsLength );
if ( aParent.nIndex <= aParent.pNode->m_nUsed )
{
@@ -466,8 +451,8 @@ DBPTreeNode< Key, Value >* DenseBPlusTree< Key, Value
>::splitNode( DBPTreeNode<
return pNewNode;
}
-template < class Key, class Value >
-void DenseBPlusTree< Key, Value >::removeBetween( const NodeWithIndex pFrom[],
const NodeWithIndex pTo[], int nLength )
+template < class Key, class Value, int Order >
+void DenseBPlusTree< Key, Value, Order >::removeBetween( const NodeWithIndex
pFrom[], const NodeWithIndex pTo[], int nLength )
{
for ( int p = 0; p < nLength; ++p )
{
@@ -491,9 +476,9 @@ void DenseBPlusTree< Key, Value >::removeBetween( const
NodeWithIndex pFrom[], c
rLeaf.pNode->remove( rLeaf.nIndex, rLeaf.pNode->m_nUsed -
rLeaf.nIndex );
// delete all nodes between from and to on the given level
- for ( DBPTreeNode< Key, Value > *pNode = rLeaf.pNode->m_pNext;
pNode != rAfter.pNode; )
+ for ( DBPTreeNode< Key, Value, Order > *pNode =
rLeaf.pNode->m_pNext; pNode != rAfter.pNode; )
{
- DBPTreeNode< Key, Value > *pToDelete = pNode;
+ DBPTreeNode< Key, Value, Order > *pToDelete = pNode;
pNode = pNode->m_pNext;
delete pToDelete;
}
diff --git a/sw/inc/densebplustree.hxx b/sw/inc/densebplustree.hxx
index 874af3e..0679767 100644
--- a/sw/inc/densebplustree.hxx
+++ b/sw/inc/densebplustree.hxx
@@ -24,7 +24,7 @@
#include <osl/diagnose.h>
#include <swdllapi.h>
-template < class Key, class Value > struct DBPTreeNode;
+template < class Key, class Value, int Order > struct DBPTreeNode;
/** Dense B+ tree implementation (to replace the original BigPtrArray).
@@ -50,9 +50,16 @@ 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.
+
+Order 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 for production, 5 is great for testing, so that
+the tree becomes deeper quickly.
*/
-template < class Key, class Value >
+template < class Key, class Value, int Order >
class SW_DLLPUBLIC DenseBPlusTree
{
public:
@@ -93,18 +100,18 @@ public:
private:
/// We need to know the exact path from the root to the leaf, including
the indexes for various operations
struct NodeWithIndex {
- DBPTreeNode< Key, Value > *pNode;
+ DBPTreeNode< Key, Value, Order > *pNode;
Key nIndex;
NodeWithIndex() {}
- NodeWithIndex( DBPTreeNode< Key, Value > *p, Key n ) : pNode( p ),
nIndex( n ) {}
+ NodeWithIndex( DBPTreeNode< Key, Value, Order > *p, Key n ) : pNode( p
), nIndex( n ) {}
};
/// Root of the tree.
- DBPTreeNode< Key, Value > *m_pRoot;
+ DBPTreeNode< Key, Value, Order > *m_pRoot;
/// The last leaf node - only a small optimization for appends.
- DBPTreeNode< Key, Value > *m_pLastLeaf;
+ DBPTreeNode< Key, Value, Order > *m_pLastLeaf;
/// Amount of values that we contain.
Key m_nCount;
@@ -123,7 +130,7 @@ private:
void shiftNodes( const NodeWithIndex pParents[], int nParentsLength, int
nHowMuch );
/// Split the node, and adjust parents accordingly.
- DBPTreeNode< Key, Value >* splitNode( DBPTreeNode< Key, Value > *pNode,
bool bIsAppend, const NodeWithIndex pParents[], int nParentsLength,
NodeWithIndex *pNewParents, int &rNewParentsLength );
+ DBPTreeNode< Key, Value, Order >* splitNode( DBPTreeNode< Key, Value,
Order > *pNode, bool bIsAppend, const NodeWithIndex pParents[], int
nParentsLength, NodeWithIndex *pNewParents, int &rNewParentsLength );
/** Remove nodes between two arrays of NodeWithIndex.
commit 67e88e4d23dce884d69c309c9babd0c1c6b3884a
Author: Jan Holesovsky <ke...@suse.cz>
Date: Tue Feb 5 21:47:39 2013 +0100
Dense B+ tree: Move m_pNext handling to a more suitable place.
Change-Id: I0fcf63c7c3559b0ee61cfb0a84d79e90399cf857
diff --git a/sw/inc/densebplustree.cxx b/sw/inc/densebplustree.cxx
index 68af75d..bb00a7a 100644
--- a/sw/inc/densebplustree.cxx
+++ b/sw/inc/densebplustree.cxx
@@ -169,14 +169,14 @@ struct DBPTreeNode
m_pValues[ i - nHowMuchKeep ] = pNode->m_pValues[ i ];
offset = nHowMuchKeep;
-
- m_pNext = pNode->m_pNext;
- pNode->m_pNext = this;
}
m_nUsed = pNode->m_nUsed - nHowMuchKeep;
pNode->m_nUsed = nHowMuchKeep;
+ m_pNext = pNode->m_pNext;
+ pNode->m_pNext = this;
+
return offset;
}
};
@@ -268,11 +268,12 @@ void DenseBPlusTree< Key, Value >::Remove( Key nPos, Key
nNumber )
// update indexes
shiftNodes( pParents, nParentsLength, aAfter.nIndex - nNumber );
+
+ // FIXME we have to create a function that walks up the parents to do
+ // this right even in the case nIndex == m_nUsed
if ( pParents[ nParentsLength - 1 ].nIndex < pParents[ nParentsLength
- 1 ].pNode->m_nUsed - 1 )
++pParents[ nParentsLength - 1 ].nIndex;
shiftNodes( pParents, nParentsLength, -aAfter.nIndex );
-
- // FIXME now make sure every node contains at least sMinFill data
}
m_nCount -= nNumber;
@@ -507,6 +508,4 @@ void DenseBPlusTree< Key, Value >::removeBetween( const
NodeWithIndex pFrom[], c
}
}
-// method name: balanceOrMerge()
-
/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
_______________________________________________
Libreoffice-commits mailing list
libreoffice-comm...@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/libreoffice-commits
