summaryrefslogtreecommitdiff
path: root/sw/source/core/bastyp/bplustree.cxx
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 /sw/source/core/bastyp/bplustree.cxx
parentbfd8ba2869dacd0d6881332e7ab2e9d2f4597af6 (diff)
B+ tree: Implement search.
So far it only compiles, needs testing. Change-Id: Ia5633bfa6bc975067b15741df557ca0b70da56f9
Diffstat (limited to 'sw/source/core/bastyp/bplustree.cxx')
-rw-r--r--sw/source/core/bastyp/bplustree.cxx122
1 files changed, 122 insertions, 0 deletions
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: */