B+ tree: Experimenting with replacement of BigPtrArray.

The BigPtrArray implementation does not seem to be entirely optimal from the
data structure point of view.  Let's experiment with a drop-in replacement
using a B+ tree (not B-tree!) that seems to be much more fit for the purpose -
it nicely handles holes in the indices (ie. does not eat your entire memory if
you insert just one entry at 1000000), and allows traversing all the data in
O(n).

From reading the code, I believe these were the only requirements for
BigPtrArray.  Eg. seeing that BigPtrArray::Insert() can lead to copying of the
entire content of the BlockInfo array makes me feel a bit dizzy.  Other
aspects of BigPtrArray remind of a naive B+ tree (without the actual tree)
implementation, see eg. BigPtrArray::Index2Block() and its binary search.

The other advantage is that if the B+ tree implementation works (ie. compares
well with BigPtrArray from the performance point of view), I believe it will
allow larger update of the entire Writer core, mainly in the area of undo,
redo, and change tracking - via copy-on-write, and remembering the entire B+
trees (with most of the metadata + data shared).

This commit only copies the BigPtrArray API to a new header.  The
implementation itself will reuse no code from BigPtrArray.

Change-Id: I65f97f26439a29edbbbac3f48a94aa007a8ef1ea

3 files changed, 90 insertions, 0 deletions

diff --git a/sw/Library_sw.mk b/sw/Library_sw.mk
index 264e35a707e4..6690cc0195de 100644
--- a/sw/Library_sw.mk
+++ b/sw/Library_sw.mk
@@ -116,6 +116,7 @@ $(eval $(call gb_Library_add_exception_objects,sw,\
     sw/source/core/attr/swatrset \
     sw/source/core/bastyp/SwSmartTagMgr \
     sw/source/core/bastyp/bparr \
+    sw/source/core/bastyp/bplustree \
     sw/source/core/bastyp/breakit \
     sw/source/core/bastyp/calc \
     sw/source/core/bastyp/checkit \
diff --git a/sw/inc/bplustree.hxx b/sw/inc/bplustree.hxx
new file mode 100644
index 000000000000..cd62f4a186cb
--- /dev/null
+++ b/sw/inc/bplustree.hxx
@@ -0,0 +1,77 @@
+/* -*- 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/.
+ *
+ * This file incorporates work covered by the following license notice:
+ *
+ *   Licensed to the Apache Software Foundation (ASF) under one or more
+ *   contributor license agreements. See the NOTICE file distributed
+ *   with this work for additional information regarding copyright
+ *   ownership. The ASF licenses this file to you under the Apache
+ *   License, Version 2.0 (the "License"); you may not use this file
+ *   except in compliance with the License. You may obtain a copy of
+ *   the License at http://www.apache.org/licenses/LICENSE-2.0 .
+ */
+
+#ifndef SW_BPLUSTREE_HXX
+#define SW_BPLUSTREE_HXX
+
+#include <tools/solar.h>
+#include <osl/diagnose.h>
+#include <swdllapi.h>
+
+/** B+ Tree implementation (to replace the original BigPtrArray).
+
+For more information about B+ Tree, please see eg. wikipedia:
+http://en.wikipedia.org/wiki/B%2B_tree
+
+As part of the removal of BigPtrArray (and consequent refactor of the related
+code), this BPlusTree is supposed to be a drop-in replacement, with some of
+the functionality templatized for easier use.
+
+Key is sal_uLong in the BigPtrArray implementation.
+Value is supposed to be SwNodePtr initially.
+*/
+template < class Key, class Value >
+class SW_DLLPUBLIC BPlusTree
+{
+public:
+    /// Callback function to be called during ForEach.
+    typedef bool (*FnForEach)( const Value&, void* pArgs );
+
+public:
+    BPlusTree();
+    ~BPlusTree();
+
+    /// Number of elements.
+    Key Count() const;
+
+    /// Insert entry at the specified position.
+    void Insert( const Value& r, Key pos );
+
+    /// Remove n entries starting with the position pos.
+    void Remove( Key pos, Key n = 1 );
+
+    /// Insert the value of 'from' to the position 'to', and remove the original value.
+    void Move( Key from, Key to );
+
+    /// Exchange the value on position pos with the new one.
+    void Replace( Key pos, const Value& r);
+
+    /// Field access.
+    const Value& operator[]( Key ) 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 );
+};
+
+#endif // SW_BPLUSTREE_HXX
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sw/source/core/bastyp/bplustree.cxx b/sw/source/core/bastyp/bplustree.cxx
new file mode 100644
index 000000000000..a94ab56f2a2c
--- /dev/null
+++ b/sw/source/core/bastyp/bplustree.cxx
@@ -0,0 +1,12 @@
+/* -*- 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 <bplustree.hxx>
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */