summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJan Holesovsky <kendy@suse.cz>2013-01-28 22:16:38 +0100
committerJan Holesovsky <kendy@suse.cz>2013-01-28 22:16:38 +0100
commite556d42b538019f0314b0b74ad843a0c3ae149b8 (patch)
tree35e4403894e9db44023a3020c3da579b57651793
parentbfd8ba2869dacd0d6881332e7ab2e9d2f4597af6 (diff)
B+ tree: Implement search.
So far it only compiles, needs testing. Change-Id: Ia5633bfa6bc975067b15741df557ca0b70da56f9
-rw-r--r--sw/inc/bplustree.hxx19
-rw-r--r--sw/source/core/bastyp/bplustree.cxx122
2 files changed, 134 insertions, 7 deletions
diff --git a/sw/inc/bplustree.hxx b/sw/inc/bplustree.hxx
index cd62f4a186cb..c42d5d1e89ce 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 a94ab56f2a2c..93ecf1fc383d 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: */