sw/inc/bplustree.hxx | 19 +++-- sw/source/core/bastyp/bplustree.cxx | 122 ++++++++++++++++++++++++++++++++++++ 2 files changed, 134 insertions(+), 7 deletions(-)
New commits: commit e556d42b538019f0314b0b74ad843a0c3ae149b8 Author: Jan Holesovsky <[email protected]> Date: Mon Jan 28 22:16:38 2013 +0100 B+ tree: Implement search. So far it only compiles, needs testing. Change-Id: Ia5633bfa6bc975067b15741df557ca0b70da56f9 diff --git a/sw/inc/bplustree.hxx b/sw/inc/bplustree.hxx index cd62f4a..c42d5d1 100644 --- a/sw/inc/bplustree.hxx +++ b/sw/inc/bplustree.hxx @@ -24,6 +24,8 @@ #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: @@ -51,25 +53,28 @@ public: Key Count() const; /// Insert entry at the specified position. - void Insert( const Value& r, Key pos ); + void Insert( const Value& rValue, Key nPos ); - /// Remove n entries starting with the position pos. - void Remove( Key pos, Key n = 1 ); + /// Remove nNumber entries starting at the position nPos. + void Remove( Key nPos, Key nNumber = 1 ); - /// Insert the value of 'from' to the position 'to', and remove the original value. - void Move( Key from, Key to ); + /// 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 pos, const Value& r); + void Replace( Key nPos, const Value& rValue ); /// Field access. - const Value& operator[]( Key ) const; + 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 diff --git a/sw/source/core/bastyp/bplustree.cxx b/sw/source/core/bastyp/bplustree.cxx index a94ab56..93ecf1f 100644 --- a/sw/source/core/bastyp/bplustree.cxx +++ b/sw/source/core/bastyp/bplustree.cxx @@ -9,4 +9,126 @@ #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: */ _______________________________________________ Libreoffice-commits mailing list [email protected] http://lists.freedesktop.org/mailman/listinfo/libreoffice-commits
