Factor out unique store compare class.

Use same template parameters for unique store dictionary btree, regardless
of unique store entry type.
Instantiate unique store btree related classes in one compilation unit.

10 files changed, 144 insertions, 42 deletions

diff --git a/vespalib/src/vespa/vespalib/datastore/CMakeLists.txt b/vespalib/src/vespa/vespalib/datastore/CMakeLists.txt
index 30c451bb191..f342ffea706 100644
--- a/vespalib/src/vespa/vespalib/datastore/CMakeLists.txt
+++ b/vespalib/src/vespa/vespalib/datastore/CMakeLists.txt
@@ -7,5 +7,6 @@ vespa_add_library(vespalib_vespalib_datastore OBJECT
     datastore.cpp
     datastorebase.cpp
     entryref.cpp
+    unique_store.cpp
     DEPENDS
 )
diff --git a/vespalib/src/vespa/vespalib/datastore/entry_comparator.h b/vespalib/src/vespa/vespalib/datastore/entry_comparator.h
new file mode 100644
index 00000000000..a1b95d656d5
--- /dev/null
+++ b/vespalib/src/vespa/vespalib/datastore/entry_comparator.h
@@ -0,0 +1,23 @@
+// Copyright 2019 Oath Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#pragma once
+
+namespace search::datastore {
+
+class EntryRef;
+
+/*
+ * Compare two entries based on entry refs.  Valid entry ref is mapped
+ * to an entry in a data store.  Invalid entry ref is mapped to a
+ * temporary entry owned or referenced by comparator instance.
+ */
+class EntryComparator {
+public:
+    virtual ~EntryComparator() {}
+    /**
+     * Compare the values represented by the given unique store entry refs.
+     **/
+    virtual bool operator()(const EntryRef lhs, const EntryRef rhs) const = 0;
+};
+
+}
diff --git a/vespalib/src/vespa/vespalib/datastore/entry_comparator_wrapper.h b/vespalib/src/vespa/vespalib/datastore/entry_comparator_wrapper.h
new file mode 100644
index 00000000000..c84f81f9d6e
--- /dev/null
+++ b/vespalib/src/vespa/vespalib/datastore/entry_comparator_wrapper.h
@@ -0,0 +1,23 @@
+// Copyright 2019 Oath Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#pragma once
+
+#include "entry_comparator.h"
+
+namespace search::datastore {
+
+/*
+ * Copyable comparator wrapper.
+ */
+class EntryComparatorWrapper {
+    const EntryComparator &_comp;
+public:
+    EntryComparatorWrapper(const EntryComparator &comp)
+        : _comp(comp)
+    { }
+    bool operator()(const EntryRef &lhs, const EntryRef &rhs) const {
+        return _comp(lhs, rhs);
+    }
+};
+
+}
diff --git a/vespalib/src/vespa/vespalib/datastore/entryref.cpp b/vespalib/src/vespa/vespalib/datastore/entryref.cpp
index 649bfa7e4e9..e90afb877bd 100644
--- a/vespalib/src/vespa/vespalib/datastore/entryref.cpp
+++ b/vespalib/src/vespa/vespalib/datastore/entryref.cpp
@@ -1,6 +1,7 @@
 // Copyright 2019 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
 
 #include "entryref.hpp"
+#include <vespa/vespalib/stllike/asciistream.h>
 
 namespace search::datastore {
 
@@ -14,4 +15,8 @@ template EntryRefT<10u,22u>::EntryRefT(size_t, uint32_t);
 template EntryRefT<10u,10u>::EntryRefT(size_t, uint32_t);
 template EntryRefT< 3u, 2u>::EntryRefT(size_t, uint32_t);
 
+vespalib::asciistream & operator << (vespalib::asciistream & os, const EntryRef &ref) {
+    return os << "EntryRef(" << ref.ref() << ")";
+}
+
 }
diff --git a/vespalib/src/vespa/vespalib/datastore/entryref.h b/vespalib/src/vespa/vespalib/datastore/entryref.h
index a582d2020f9..9b265abafd3 100644
--- a/vespalib/src/vespa/vespalib/datastore/entryref.h
+++ b/vespalib/src/vespa/vespalib/datastore/entryref.h
@@ -5,6 +5,8 @@
 #include <cstddef>
 #include <cstdint>
 
+namespace vespalib { class asciistream; }
+
 namespace search::datastore {
 
 class EntryRef {
@@ -61,4 +63,6 @@ public:
     static constexpr bool isAlignedType = true;
 };
 
+vespalib::asciistream& operator<<(vespalib::asciistream& os, const EntryRef& ref);
+
 }
diff --git a/vespalib/src/vespa/vespalib/datastore/unique_store.cpp b/vespalib/src/vespa/vespalib/datastore/unique_store.cpp
new file mode 100644
index 00000000000..5c402933ae1
--- /dev/null
+++ b/vespalib/src/vespa/vespalib/datastore/unique_store.cpp
@@ -0,0 +1,38 @@
+// Copyright 2019 Oath Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#include "unique_store.h"
+#include "datastore.hpp"
+#include <vespa/vespalib/btree/btree.hpp>
+#include <vespa/vespalib/btree/btreebuilder.hpp>
+#include <vespa/vespalib/btree/btreeroot.hpp>
+#include <vespa/vespalib/btree/btreenodeallocator.hpp>
+#include <vespa/vespalib/btree/btreeiterator.hpp>
+#include <vespa/vespalib/btree/btreenode.hpp>
+
+namespace search::btree {
+
+// Instantiate classes related to unique store dictionary btree
+
+using EntryRef = datastore::EntryRef;
+using EntryComparatorWrapper = datastore::EntryComparatorWrapper;
+using DictionaryTraits = BTreeTraits<32, 32, 7, true>;
+
+template class BTreeNodeDataWrap<uint32_t, DictionaryTraits::LEAF_SLOTS>;
+template class BTreeNodeT<EntryRef, DictionaryTraits::INTERNAL_SLOTS>;
+template class BTreeNodeTT<EntryRef, uint32_t, NoAggregated, DictionaryTraits::LEAF_SLOTS>;
+template class BTreeNodeTT<EntryRef, EntryRef, NoAggregated, DictionaryTraits::INTERNAL_SLOTS>;
+template class BTreeInternalNode<EntryRef, NoAggregated, DictionaryTraits::INTERNAL_SLOTS>;
+template class BTreeLeafNode<EntryRef, uint32_t, NoAggregated, DictionaryTraits::LEAF_SLOTS>;
+template class BTreeLeafNodeTemp<EntryRef, uint32_t, NoAggregated, DictionaryTraits::LEAF_SLOTS>;
+template class BTreeRootBase<EntryRef, uint32_t, NoAggregated, DictionaryTraits::INTERNAL_SLOTS, DictionaryTraits::LEAF_SLOTS>;
+template class BTreeRootT<EntryRef, uint32_t, NoAggregated, EntryComparatorWrapper, DictionaryTraits>;
+template class BTreeRoot<EntryRef, uint32_t, NoAggregated, EntryComparatorWrapper, DictionaryTraits>;
+template class BTree<EntryRef, uint32_t, NoAggregated, EntryComparatorWrapper, DictionaryTraits>;
+template class BTreeBuilder<EntryRef, uint32_t, NoAggregated, DictionaryTraits::INTERNAL_SLOTS, DictionaryTraits::LEAF_SLOTS>;
+template class BTreeNodeAllocator<EntryRef, uint32_t, NoAggregated, DictionaryTraits::INTERNAL_SLOTS, DictionaryTraits::LEAF_SLOTS>;
+template class BTreeNodeStore<EntryRef, uint32_t, NoAggregated, DictionaryTraits::INTERNAL_SLOTS, DictionaryTraits::LEAF_SLOTS>;
+template class BTreeIteratorBase<EntryRef, uint32_t, NoAggregated, DictionaryTraits::INTERNAL_SLOTS, DictionaryTraits::LEAF_SLOTS, DictionaryTraits::PATH_SIZE>;
+template class BTreeConstIterator<EntryRef, uint32_t, NoAggregated, EntryComparatorWrapper, DictionaryTraits>;
+template class BTreeIterator<EntryRef, uint32_t, NoAggregated, EntryComparatorWrapper, DictionaryTraits>;
+
+}
diff --git a/vespalib/src/vespa/vespalib/datastore/unique_store.h b/vespalib/src/vespa/vespalib/datastore/unique_store.h
index 3da4ff941b5..d5ae495a698 100644
--- a/vespalib/src/vespa/vespalib/datastore/unique_store.h
+++ b/vespalib/src/vespa/vespalib/datastore/unique_store.h
@@ -6,6 +6,8 @@
 #include "bufferstate.h"
 #include "datastore.h"
 #include "entryref.h"
+#include "entry_comparator_wrapper.h"
+#include "unique_store_comparator.h"
 #include "i_compaction_context.h"
 #include <vespa/vespalib/util/array.h>
 #include <vespa/vespalib/btree/btree.h>
@@ -31,40 +33,12 @@ public:
     using RefType = RefT;
     using Saver = UniqueStoreSaver<EntryT, RefT>;
     using Builder = UniqueStoreBuilder<EntryT, RefT>;
-    /*
-     * Compare two values in data store based on reference.  Invalid
-     * reference is mapped to local value reference to support
-     * comparing with new value candidate outside data store.
-     */
-    class Compare {
-        const DataStoreType &_store;
-        const EntryType &_value;
-public:
-        Compare(const DataStoreType &store, const EntryType &value)
-            : _store(store),
-              _value(value)
-        {
-        }
-        inline const EntryType &get(EntryRef ref) const {
-            if (ref.valid()) {
-                RefType iRef(ref);
-                return *_store.template getEntry<EntryType>(iRef);
-            } else {
-                return _value;
-            }
-        }
-        inline bool operator()(const EntryRef lhs, const EntryRef rhs) const
-        {
-            const EntryType &lhsValue = get(lhs);
-            const EntryType &rhsValue = get(rhs);
-            return lhsValue < rhsValue;
-        }
-    };
+    using Compare = UniqueStoreComparator<EntryType, RefType>;
     using UniqueStoreBufferType = BufferType<EntryType>;
     using DictionaryTraits = btree::BTreeTraits<32, 32, 7, true>;
     using Dictionary = btree::BTree<EntryRef, uint32_t,
                                     btree::NoAggregated,
-                                    Compare,
+                                    EntryComparatorWrapper,
                                     DictionaryTraits>;
     class AddResult {
         EntryRef _ref;
diff --git a/vespalib/src/vespa/vespalib/datastore/unique_store.hpp b/vespalib/src/vespa/vespalib/datastore/unique_store.hpp
index 0f1f73f3205..9530072eae9 100644
--- a/vespalib/src/vespa/vespalib/datastore/unique_store.hpp
+++ b/vespalib/src/vespa/vespalib/datastore/unique_store.hpp
@@ -4,16 +4,11 @@
 
 #include "unique_store.h"
 #include "datastore.hpp"
-#include <vespa/vespalib/btree/btree.hpp>
-#include <vespa/vespalib/btree/btreebuilder.hpp>
-#include <vespa/vespalib/btree/btreeroot.hpp>
-#include <vespa/vespalib/btree/btreenodeallocator.hpp>
-#include <vespa/vespalib/btree/btreeiterator.hpp>
-#include <vespa/vespalib/btree/btreenode.hpp>
 #include <vespa/vespalib/util/bufferwriter.h>
 #include "unique_store_builder.hpp"
 #include "unique_store_saver.hpp"
 #include <atomic>
+#include <algorithm>
 
 namespace search::datastore {
 
diff --git a/vespalib/src/vespa/vespalib/datastore/unique_store_builder.hpp b/vespalib/src/vespa/vespalib/datastore/unique_store_builder.hpp
index 8b75b147655..a5ad7673f51 100644
--- a/vespalib/src/vespa/vespalib/datastore/unique_store_builder.hpp
+++ b/vespalib/src/vespa/vespalib/datastore/unique_store_builder.hpp
@@ -4,12 +4,12 @@
 
 #include "unique_store_builder.h"
 #include "datastore.hpp"
-#include <vespa/vespalib/btree/btree.hpp>
-#include <vespa/vespalib/btree/btreebuilder.hpp>
-#include <vespa/vespalib/btree/btreeroot.hpp>
-#include <vespa/vespalib/btree/btreenodeallocator.hpp>
-#include <vespa/vespalib/btree/btreeiterator.hpp>
-#include <vespa/vespalib/btree/btreenode.hpp>
+#include <vespa/vespalib/btree/btree.h>
+#include <vespa/vespalib/btree/btreebuilder.h>
+#include <vespa/vespalib/btree/btreeroot.h>
+#include <vespa/vespalib/btree/btreenodeallocator.h>
+#include <vespa/vespalib/btree/btreeiterator.h>
+#include <vespa/vespalib/btree/btreenode.h>
 
 namespace search::datastore {
 
diff --git a/vespalib/src/vespa/vespalib/datastore/unique_store_comparator.h b/vespalib/src/vespa/vespalib/datastore/unique_store_comparator.h
new file mode 100644
index 00000000000..e71ce973f29
--- /dev/null
+++ b/vespalib/src/vespa/vespalib/datastore/unique_store_comparator.h
@@ -0,0 +1,39 @@
+// Copyright 2019 Oath Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#pragma once
+
+#include "entry_comparator.h"
+#include "datastore.h"
+
+namespace search::datastore {
+
+template <typename EntryT, typename RefT>
+class UniqueStoreComparator : public EntryComparator {
+    using EntryType = EntryT;
+    using RefType = RefT;
+    using DataStoreType = DataStoreT<RefT>;
+    const DataStoreType &_store;
+    const EntryType &_value;
+public:
+    UniqueStoreComparator(const DataStoreType &store, const EntryType &value)
+        : _store(store),
+          _value(value)
+    {
+    }
+    inline const EntryType &get(EntryRef ref) const {
+        if (ref.valid()) {
+            RefType iRef(ref);
+            return *_store.template getEntry<EntryType>(iRef);
+        } else {
+            return _value;
+        }
+    }
+    bool operator()(const EntryRef lhs, const EntryRef rhs) const override
+    {
+        const EntryType &lhsValue = get(lhs);
+        const EntryType &rhsValue = get(rhs);
+        return lhsValue < rhsValue;
+    }
+};
+
+}