summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJan Holesovsky <kendy@suse.cz>2013-01-30 14:22:53 +0100
committerJan Holesovsky <kendy@suse.cz>2013-01-31 02:36:05 +0100
commitf9c991c8f812440ab68938b1facfed3796a817d0 (patch)
tree274bc9c880b2545526bed8a5545f95cb11a23faf
parenta341d834d76b3c06e4e767efa2dc09f9ac8ca8ba (diff)
Dense B+ tree: Implemented Insert(), and can start testing.
The trivial case works now, but splitting nodes does not do yet. Change-Id: Ife452fc164ab786ac9e1dc9cabe9ea1a2e78231a
-rw-r--r--Repository.mk1
-rw-r--r--sw/Module_sw.mk1
-rw-r--r--sw/inc/densebplustree.cxx226
-rw-r--r--sw/inc/densebplustree.hxx29
-rw-r--r--sw/qa/core/densebplustree-test.cxx88
5 files changed, 315 insertions, 30 deletions
diff --git a/Repository.mk b/Repository.mk
index 19e9c4d51e75..4374068e60a8 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 6abd3212cc7b..5ed6a47db67d 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 ec779bd10ea9..3f8a1a3b1daa 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 cf0c9ff0571a..e7362d25fc53 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 000000000000..e270d0949608
--- /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: */