[Libreoffice-commits] .: Branch 'feature/bplustree' - sw/inc sw/source

[Libreoffice Gerrit user]

 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 <kendy at suse.cz>
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: */