Merge pull request #10315 from vespa-engine/toregge/extend-unique-store-test

Extend unique store test to cover use of unique store string allocator

8 files changed, 197 insertions, 111 deletions

diff --git a/vespalib/src/tests/datastore/unique_store/unique_store_test.cpp b/vespalib/src/tests/datastore/unique_store/unique_store_test.cpp
index a585186aa3e..ba2c98a6d54 100644
--- a/vespalib/src/tests/datastore/unique_store/unique_store_test.cpp
+++ b/vespalib/src/tests/datastore/unique_store/unique_store_test.cpp
@@ -1,7 +1,9 @@
 // Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
 #include <vespa/vespalib/datastore/unique_store.hpp>
+#include <vespa/vespalib/datastore/unique_store_string_allocator.hpp>
+#include <vespa/vespalib/datastore/unique_store_string_comparator.h>
 #include <vespa/vespalib/gtest/gtest.h>
-#include <vespa/vespalib/test/datastore/memstats.h>
+#include <vespa/vespalib/test/datastore/buffer_stats.h>
 #include <vespa/vespalib/test/insertion_operators.h>
 #include <vespa/vespalib/util/traits.h>
 #include <vector>
@@ -10,43 +12,47 @@
 LOG_SETUP("unique_store_test");
 
 using namespace search::datastore;
-using vespalib::MemoryUsage;
 using vespalib::ArrayRef;
 using generation_t = vespalib::GenerationHandler::generation_t;
-using MemStats = search::datastore::test::MemStats;
+using search::datastore::test::BufferStats;
 
-template <typename EntryT, typename RefT = EntryRefT<22> >
+template <typename UniqueStoreT>
 struct TestBase : public ::testing::Test {
-    using EntryRefType = RefT;
-    using UniqueStoreType = UniqueStore<EntryT, RefT>;
-    using value_type = EntryT;
-    using ReferenceStore = std::map<EntryRef, std::pair<EntryT,uint32_t>>;
+    using EntryRefType = typename UniqueStoreT::RefType;
+    using UniqueStoreType = UniqueStoreT;
+    using ValueType = typename UniqueStoreT::EntryType;
+    using ValueConstRefType = typename UniqueStoreT::EntryConstRefType;
+    using ReferenceStoreValueType = std::conditional_t<std::is_same_v<ValueType, const char *>, std::string, ValueType>;
+    using ReferenceStore = std::map<EntryRef, std::pair<ReferenceStoreValueType,uint32_t>>;
 
     UniqueStoreType store;
     ReferenceStore refStore;
     generation_t generation;
+
+    static std::vector<ValueType> values;
+
     TestBase()
         : store(),
           refStore(),
           generation(1)
     {}
-    void assertAdd(const EntryT &input) {
+    void assertAdd(ValueConstRefType input) {
         EntryRef ref = add(input);
         assertGet(ref, input);
     }
-    EntryRef add(const EntryT &input) {
+    EntryRef add(ValueConstRefType input) {
         UniqueStoreAddResult addResult = store.add(input);
         EntryRef result = addResult.ref();
-        auto insres = refStore.insert(std::make_pair(result, std::make_pair(input, 1u)));
+        auto insres = refStore.insert(std::make_pair(result, std::make_pair(ReferenceStoreValueType(input), 1u)));
         EXPECT_EQ(insres.second, addResult.inserted());
         if (!insres.second) {
             ++insres.first->second.second;
         }
         return result;
     }
-    void alignRefStore(EntryRef ref, const EntryT &input, uint32_t refcnt) {
+    void alignRefStore(EntryRef ref, ValueConstRefType input, uint32_t refcnt) {
         if (refcnt > 0) {
-            auto insres = refStore.insert(std::make_pair(ref, std::make_pair(input, refcnt)));
+            auto insres = refStore.insert(std::make_pair(ref, std::make_pair(ReferenceStoreValueType(input), refcnt)));
             if (!insres.second) {
                 insres.first->second.second = refcnt;
             }
@@ -54,8 +60,8 @@ struct TestBase : public ::testing::Test {
             refStore.erase(ref);
         }
     }
-    void assertGet(EntryRef ref, const EntryT &exp) const {
-        EntryT act = store.get(ref);
+    void assertGet(EntryRef ref, ReferenceStoreValueType exp) const {
+        ReferenceStoreValueType act = store.get(ref);
         EXPECT_EQ(exp, act);
     }
     void remove(EntryRef ref) {
@@ -67,29 +73,23 @@ struct TestBase : public ::testing::Test {
             refStore.erase(ref);
         }
     }
-    void remove(const EntryT &input) {
+    void remove(ValueConstRefType input) {
         remove(getEntryRef(input));
     }
     uint32_t getBufferId(EntryRef ref) const {
         return EntryRefType(ref).bufferId();
     }
-    void assertBufferState(EntryRef ref, const MemStats expStats) const {
+    void assertBufferState(EntryRef ref, const BufferStats expStats) const {
         EXPECT_EQ(expStats._used, store.bufferState(ref).size());
         EXPECT_EQ(expStats._hold, store.bufferState(ref).getHoldElems());
         EXPECT_EQ(expStats._dead, store.bufferState(ref).getDeadElems());
     }
-    void assertMemoryUsage(const MemStats expStats) const {
-        MemoryUsage act = store.getMemoryUsage();
-        EXPECT_EQ(expStats._used, act.usedBytes());
-        EXPECT_EQ(expStats._hold, act.allocatedBytesOnHold());
-        EXPECT_EQ(expStats._dead, act.deadBytes());
-    }
     void assertStoreContent() const {
         for (const auto &elem : refStore) {
             assertGet(elem.first, elem.second.first);
         }
     }
-    EntryRef getEntryRef(const EntryT &input) {
+    EntryRef getEntryRef(ValueConstRefType input) {
         for (const auto &elem : refStore) {
             if (elem.second.first == input) {
                 return elem.first;
@@ -121,57 +121,79 @@ struct TestBase : public ::testing::Test {
         }
         refStore = compactedRefStore;
     }
-    size_t entrySize() const { return sizeof(EntryT); }
+    size_t entrySize() const { return sizeof(ValueType); }
     auto getBuilder(uint32_t uniqueValuesHint) { return store.getBuilder(uniqueValuesHint); }
     auto getSaver() { return store.getSaver(); }
+    size_t get_reserved(EntryRef ref) {
+        return store.bufferState(ref).getTypeHandler()->getReservedElements(getBufferId(ref));
+    }
+    size_t get_array_size(EntryRef ref) {
+        return store.bufferState(ref).getArraySize();
+    }
 };
 
-using NumberTest = TestBase<uint32_t>;
-using StringTest = TestBase<std::string>;
-using SmallOffsetNumberTest = TestBase<uint32_t, EntryRefT<10>>;
+using NumberUniqueStore  = UniqueStore<uint32_t>;
+using StringUniqueStore  = UniqueStore<std::string>;
+using CStringUniqueStore = UniqueStore<const char *, EntryRefT<22>, UniqueStoreStringComparator<EntryRefT<22>>, UniqueStoreStringAllocator<EntryRefT<22>>>;
+using SmallOffsetNumberUniqueStore = UniqueStore<uint32_t, EntryRefT<10,10>>;
 
-TEST(UniqueStoreTest, trivial_and_non_trivial_types_are_tested)
-{
-    EXPECT_TRUE(vespalib::can_skip_destruction<NumberTest::value_type>::value);
-    EXPECT_FALSE(vespalib::can_skip_destruction<StringTest::value_type>::value);
-}
+template <>
+std::vector<uint32_t> TestBase<NumberUniqueStore>::values{10, 20, 30, 10 };
+template <>
+std::vector<std::string> TestBase<StringUniqueStore>::values{ "aa", "bbb", "ccc", "aa" };
+template <>
+std::vector<const char *> TestBase<CStringUniqueStore>::values{ "aa", "bbb", "ccc", "aa" };
+
+using UniqueStoreTestTypes = ::testing::Types<NumberUniqueStore, StringUniqueStore, CStringUniqueStore>;
+TYPED_TEST_CASE(TestBase, UniqueStoreTestTypes);
 
-TEST_F(NumberTest, can_add_and_get_values_of_trivial_type)
+// Disable warnings emitted by gtest generated files when using typed tests
+#pragma GCC diagnostic push
+#ifndef __clang__
+#pragma GCC diagnostic ignored "-Wsuggest-override"
+#endif
+
+using NumberTest = TestBase<NumberUniqueStore>;
+using StringTest = TestBase<StringUniqueStore>;
+using CStringTest = TestBase<CStringUniqueStore>;
+using SmallOffsetNumberTest = TestBase<SmallOffsetNumberUniqueStore>;
+
+TEST(UniqueStoreTest, trivial_and_non_trivial_types_are_tested)
 {
-    assertAdd(1);
-    assertAdd(2);
-    assertAdd(3);
-    assertAdd(1);
+    EXPECT_TRUE(vespalib::can_skip_destruction<NumberTest::ValueType>::value);
+    EXPECT_FALSE(vespalib::can_skip_destruction<StringTest::ValueType>::value);
 }
 
-TEST_F(StringTest, can_add_and_get_values_of_non_trivial_type)
+TYPED_TEST(TestBase, can_add_and_get_values)
 {
-    assertAdd("aa");
-    assertAdd("bbb");
-    assertAdd("ccc");
-    assertAdd("aa");
+    for (auto &val : this->values) {
+        this->assertAdd(val);
+    }
 }
 
-TEST_F(NumberTest, elements_are_put_on_hold_when_value_is_removed)
+TYPED_TEST(TestBase, elements_are_put_on_hold_when_value_is_removed)
 {
-    EntryRef ref = add(1);
-    // Note: The first buffer have the first element reserved -> we expect 2 elements used here.
-    assertBufferState(ref, MemStats().used(2).hold(0).dead(1));
-    store.remove(ref);
-    assertBufferState(ref, MemStats().used(2).hold(1).dead(1));
+    EntryRef ref = this->add(this->values[0]);
+    size_t reserved = this->get_reserved(ref);
+    size_t array_size = this->get_array_size(ref);
+    this->assertBufferState(ref, BufferStats().used(array_size + reserved).hold(0).dead(reserved));
+    this->store.remove(ref);
+    this->assertBufferState(ref, BufferStats().used(array_size + reserved).hold(array_size).dead(reserved));
 }
 
-TEST_F(NumberTest, elements_are_reference_counted)
+TYPED_TEST(TestBase, elements_are_reference_counted)
 {
-    EntryRef ref = add(1);
-    EntryRef ref2 = add(1);
+    EntryRef ref = this->add(this->values[0]);
+    EntryRef ref2 = this->add(this->values[0]);
     EXPECT_EQ(ref.ref(), ref2.ref());
     // Note: The first buffer have the first element reserved -> we expect 2 elements used here.
-    assertBufferState(ref, MemStats().used(2).hold(0).dead(1));
-    store.remove(ref);
-    assertBufferState(ref, MemStats().used(2).hold(0).dead(1));
-    store.remove(ref);
-    assertBufferState(ref, MemStats().used(2).hold(1).dead(1));
+    size_t reserved = this->get_reserved(ref);
+    size_t array_size = this->get_array_size(ref);
+    this->assertBufferState(ref, BufferStats().used(array_size + reserved).hold(0).dead(reserved));
+    this->store.remove(ref);
+    this->assertBufferState(ref, BufferStats().used(array_size + reserved).hold(0).dead(reserved));
+    this->store.remove(ref);
+    this->assertBufferState(ref, BufferStats().used(array_size + reserved).hold(array_size).dead(reserved));
 }
 
 TEST_F(SmallOffsetNumberTest, new_underlying_buffer_is_allocated_when_current_is_full)
@@ -193,74 +215,80 @@ TEST_F(SmallOffsetNumberTest, new_underlying_buffer_is_allocated_when_current_is
     assertStoreContent();
 }
 
-TEST_F(NumberTest, store_can_be_compacted)
+TYPED_TEST(TestBase, store_can_be_compacted)
 {
-    EntryRef val1Ref = add(1);
-    EntryRef val2Ref = add(2);
-    remove(add(4));
-    trimHoldLists();
-    assertBufferState(val1Ref, MemStats().used(4).dead(2)); // Note: First element is reserved
-    uint32_t val1BufferId = getBufferId(val1Ref);
+    EntryRef val0Ref = this->add(this->values[0]);
+    EntryRef val1Ref = this->add(this->values[1]);
+    this->remove(this->add(this->values[2]));
+    this->trimHoldLists();
+    size_t reserved = this->get_reserved(val0Ref);
+    size_t array_size = this->get_array_size(val0Ref);
+    this->assertBufferState(val0Ref, BufferStats().used(reserved + 3 * array_size).dead(reserved + array_size));
+    uint32_t val1BufferId = this->getBufferId(val0Ref);
 
-    EXPECT_EQ(2u, refStore.size());
-    compactWorst();
-    EXPECT_EQ(2u, refStore.size());
-    assertStoreContent();
+    EXPECT_EQ(2u, this->refStore.size());
+    this->compactWorst();
+    EXPECT_EQ(2u, this->refStore.size());
+    this->assertStoreContent();
 
     // Buffer has been compacted
-    EXPECT_NE(val1BufferId, getBufferId(getEntryRef(1)));
+    EXPECT_NE(val1BufferId, this->getBufferId(this->getEntryRef(this->values[0])));
     // Old ref should still point to data.
-    assertGet(val1Ref, 1);
-    assertGet(val2Ref, 2);
-    EXPECT_TRUE(store.bufferState(val1Ref).isOnHold());
-    trimHoldLists();
-    EXPECT_TRUE(store.bufferState(val1Ref).isFree());
-    assertStoreContent();
+    this->assertGet(val0Ref, this->values[0]);
+    this->assertGet(val1Ref, this->values[1]);
+    EXPECT_TRUE(this->store.bufferState(val0Ref).isOnHold());
+    this->trimHoldLists();
+    EXPECT_TRUE(this->store.bufferState(val0Ref).isFree());
+    this->assertStoreContent();
 }
 
-TEST_F(NumberTest, store_can_be_instantiated_with_builder)
+TYPED_TEST(TestBase, store_can_be_instantiated_with_builder)
 {
-    auto builder = getBuilder(2);
-    builder.add(10);
-    builder.add(20);
+    auto builder = this->getBuilder(2);
+    builder.add(this->values[0]);
+    builder.add(this->values[1]);
     builder.setupRefCounts();
-    EntryRef val10Ref = builder.mapEnumValueToEntryRef(1);
-    EntryRef val20Ref = builder.mapEnumValueToEntryRef(2);
-    assertBufferState(val10Ref, MemStats().used(3).dead(1)); // Note: First element is reserved
-    EXPECT_TRUE(val10Ref.valid());
-    EXPECT_TRUE(val20Ref.valid());
-    EXPECT_NE(val10Ref.ref(), val20Ref.ref());
-    assertGet(val10Ref, 10);
-    assertGet(val20Ref, 20);
+    EntryRef val0Ref = builder.mapEnumValueToEntryRef(1);
+    EntryRef val1Ref = builder.mapEnumValueToEntryRef(2);
+    size_t reserved = this->get_reserved(val0Ref);
+    size_t array_size = this->get_array_size(val0Ref);
+    this->assertBufferState(val0Ref, BufferStats().used(2 * array_size + reserved).dead(reserved)); // Note: First element is reserved
+    EXPECT_TRUE(val0Ref.valid());
+    EXPECT_TRUE(val1Ref.valid());
+    EXPECT_NE(val0Ref.ref(), val1Ref.ref());
+    this->assertGet(val0Ref, this->values[0]);
+    this->assertGet(val1Ref, this->values[1]);
     builder.makeDictionary();
     // Align refstore with the two entries added by builder.
-    alignRefStore(val10Ref, 10, 1);
-    alignRefStore(val20Ref, 20, 1);
-    EXPECT_EQ(val10Ref.ref(), add(10).ref());
-    EXPECT_EQ(val20Ref.ref(), add(20).ref());
+    this->alignRefStore(val0Ref, this->values[0], 1);
+    this->alignRefStore(val1Ref, this->values[1], 1);
+    EXPECT_EQ(val0Ref.ref(), this->add(this->values[0]).ref());
+    EXPECT_EQ(val1Ref.ref(), this->add(this->values[1]).ref());
 }
 
-TEST_F(NumberTest, store_can_be_saved)
+TYPED_TEST(TestBase, store_can_be_saved)
 {
-    EntryRef val10Ref = add(10);
-    EntryRef val20Ref = add(20);
-    remove(add(40));
-    trimHoldLists();
+    EntryRef val0Ref = this->add(this->values[0]);
+    EntryRef val1Ref = this->add(this->values[1]);
+    this->remove(this->add(this->values[2]));
+    this->trimHoldLists();
 
-    auto saver = getSaver();
+    auto saver = this->getSaver();
     std::vector<uint32_t> refs;
     saver.foreach_key([&](EntryRef ref) { refs.push_back(ref.ref()); });
     std::vector<uint32_t> expRefs;
-    expRefs.push_back(val10Ref.ref());
-    expRefs.push_back(val20Ref.ref());
+    expRefs.push_back(val0Ref.ref());
+    expRefs.push_back(val1Ref.ref());
     EXPECT_EQ(expRefs, refs);
     saver.enumerateValues();
     uint32_t invalidEnum = saver.mapEntryRefToEnumValue(EntryRef());
-    uint32_t enumValue10 = saver.mapEntryRefToEnumValue(val10Ref);
-    uint32_t enumValue20 = saver.mapEntryRefToEnumValue(val20Ref);
+    uint32_t enumValue1 = saver.mapEntryRefToEnumValue(val0Ref);
+    uint32_t enumValue2 = saver.mapEntryRefToEnumValue(val1Ref);
     EXPECT_EQ(0u, invalidEnum);
-    EXPECT_EQ(1u, enumValue10);
-    EXPECT_EQ(2u, enumValue20);
+    EXPECT_EQ(1u, enumValue1);
+    EXPECT_EQ(2u, enumValue2);
 }
 
+#pragma GCC diagnostic pop
+
 GTEST_MAIN_RUN_ALL_TESTS()
diff --git a/vespalib/src/vespa/vespalib/datastore/unique_store.h b/vespalib/src/vespa/vespalib/datastore/unique_store.h
index 8a7f0e50845..a045da6ca1f 100644
--- a/vespalib/src/vespa/vespalib/datastore/unique_store.h
+++ b/vespalib/src/vespa/vespalib/datastore/unique_store.h
@@ -35,6 +35,7 @@ public:
     using RefType = RefT;
     using Saver = UniqueStoreSaver<EntryT, RefT>;
     using Builder = UniqueStoreBuilder<Allocator>;
+    using EntryConstRefType = typename Allocator::EntryConstRefType;
 private:
     Allocator _allocator;
     DataStoreType &_store;
@@ -44,9 +45,9 @@ private:
 public:
     UniqueStore();
     ~UniqueStore();
-    UniqueStoreAddResult add(const EntryType &value);
-    EntryRef find(const EntryType &value);
-    const EntryType &get(EntryRef ref) const { return _allocator.get(ref); }
+    UniqueStoreAddResult add(EntryConstRefType value);
+    EntryRef find(EntryConstRefType value);
+    EntryConstRefType get(EntryRef ref) const { return _allocator.get(ref); }
     void remove(EntryRef ref);
     ICompactionContext::UP compactWorst();
     vespalib::MemoryUsage getMemoryUsage() const;
diff --git a/vespalib/src/vespa/vespalib/datastore/unique_store.hpp b/vespalib/src/vespa/vespalib/datastore/unique_store.hpp
index bc1873a2c3a..e149f470bdf 100644
--- a/vespalib/src/vespa/vespalib/datastore/unique_store.hpp
+++ b/vespalib/src/vespa/vespalib/datastore/unique_store.hpp
@@ -27,7 +27,7 @@ UniqueStore<EntryT, RefT, Compare, Allocator>::~UniqueStore() = default;
 
 template <typename EntryT, typename RefT, typename Compare, typename Allocator>
 UniqueStoreAddResult
-UniqueStore<EntryT, RefT, Compare, Allocator>::add(const EntryType &value)
+UniqueStore<EntryT, RefT, Compare, Allocator>::add(EntryConstRefType value)
 {
     Compare comp(_store, value);
     UniqueStoreAddResult result = _dict->add(comp, [this, &value]() -> EntryRef { return _allocator.allocate(value); });
@@ -37,7 +37,7 @@ UniqueStore<EntryT, RefT, Compare, Allocator>::add(const EntryType &value)
 
 template <typename EntryT, typename RefT, typename Compare, typename Allocator>
 EntryRef
-UniqueStore<EntryT, RefT, Compare, Allocator>::find(const EntryType &value)
+UniqueStore<EntryT, RefT, Compare, Allocator>::find(EntryConstRefType value)
 {
     Compare comp(_store, value);
     return _dict->find(comp);
diff --git a/vespalib/src/vespa/vespalib/datastore/unique_store_allocator.h b/vespalib/src/vespa/vespalib/datastore/unique_store_allocator.h
index cadc2b09c0e..1981a190cc6 100644
--- a/vespalib/src/vespa/vespalib/datastore/unique_store_allocator.h
+++ b/vespalib/src/vespa/vespalib/datastore/unique_store_allocator.h
@@ -20,6 +20,7 @@ class UniqueStoreAllocator : public ICompactable
 public:
     using DataStoreType = DataStoreT<RefT>;
     using EntryType = EntryT;
+    using EntryConstRefType = const EntryType &;
     using WrappedEntryType = UniqueStoreEntry<EntryType>;
     using RefType = RefT;
     using UniqueStoreBufferType = BufferType<WrappedEntryType>;
diff --git a/vespalib/src/vespa/vespalib/datastore/unique_store_string_allocator.cpp b/vespalib/src/vespa/vespalib/datastore/unique_store_string_allocator.cpp
index 4c665ee0517..d7b79c439ef 100644
--- a/vespalib/src/vespa/vespalib/datastore/unique_store_string_allocator.cpp
+++ b/vespalib/src/vespa/vespalib/datastore/unique_store_string_allocator.cpp
@@ -4,6 +4,13 @@
 
 namespace search::datastore {
 
+namespace {
+
+constexpr size_t NUM_ARRAYS_FOR_NEW_UNIQUESTORE_BUFFER = 1024u;
+constexpr float ALLOC_GROW_FACTOR = 0.2;
+
+}
+
 namespace string_allocator {
 
 std::vector<size_t> array_sizes = { 16, 24, 32, 40, 48, 64, 80, 96, 112, 128, 144, 160, 176, 192, 208, 224, 256 };
diff --git a/vespalib/src/vespa/vespalib/datastore/unique_store_string_allocator.h b/vespalib/src/vespa/vespalib/datastore/unique_store_string_allocator.h
index afd0139db1b..f72b9c6119c 100644
--- a/vespalib/src/vespa/vespalib/datastore/unique_store_string_allocator.h
+++ b/vespalib/src/vespa/vespalib/datastore/unique_store_string_allocator.h
@@ -91,6 +91,7 @@ class UniqueStoreStringAllocator : public ICompactable
 public:
     using DataStoreType = DataStoreT<RefT>;
     using EntryType = const char *;
+    using EntryConstRefType = const char *;
     using WrappedExternalEntryType = UniqueStoreEntry<std::string>;
     using RefType = RefT;
 private:
diff --git a/vespalib/src/vespa/vespalib/datastore/unique_store_string_allocator.hpp b/vespalib/src/vespa/vespalib/datastore/unique_store_string_allocator.hpp
index 9bd2e050507..2b2af70439a 100644
--- a/vespalib/src/vespa/vespalib/datastore/unique_store_string_allocator.hpp
+++ b/vespalib/src/vespa/vespalib/datastore/unique_store_string_allocator.hpp
@@ -7,9 +7,6 @@
 
 namespace search::datastore {
 
-constexpr size_t NUM_ARRAYS_FOR_NEW_UNIQUESTORE_BUFFER = 1024u;
-constexpr float ALLOC_GROW_FACTOR = 0.2;
-
 template <typename RefT>
 UniqueStoreStringAllocator<RefT>::UniqueStoreStringAllocator()
     : ICompactable(),
diff --git a/vespalib/src/vespa/vespalib/datastore/unique_store_string_comparator.h b/vespalib/src/vespa/vespalib/datastore/unique_store_string_comparator.h
new file mode 100644
index 00000000000..e5d3888a5e2
--- /dev/null
+++ b/vespalib/src/vespa/vespalib/datastore/unique_store_string_comparator.h
@@ -0,0 +1,51 @@
+// 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 "unique_store_string_allocator.h"
+
+namespace search::datastore {
+
+/*
+ * Compare two strings based on entry refs.  Valid entry ref is mapped
+ * to a string in a data store.  Invalid entry ref is mapped to a
+ * temporary string pointed to by comparator instance.
+ */
+template <typename RefT>
+class UniqueStoreStringComparator : public EntryComparator {
+    using RefType = RefT;
+    using WrappedExternalEntryType = UniqueStoreEntry<std::string>;
+    using DataStoreType = DataStoreT<RefT>;
+    const DataStoreType &_store;
+    const char *_value;
+public:
+    UniqueStoreStringComparator(const DataStoreType &store, const char *value)
+        : _store(store),
+          _value(value)
+    {
+    }
+    const char *get(EntryRef ref) const {
+        if (ref.valid()) {
+            RefType iRef(ref);
+            auto &state = _store.getBufferState(iRef.bufferId());
+            auto type_id = state.getTypeId();
+            if (type_id != 0) {
+                return reinterpret_cast<const UniqueStoreSmallStringEntry *>(_store.template getEntryArray<char>(iRef, state.getArraySize()))->value();
+            } else {
+                return _store.template getEntry<WrappedExternalEntryType>(iRef)->value().c_str();
+            }
+        } else {
+            return _value;
+        }
+    }
+
+    bool operator()(const EntryRef lhs, const EntryRef rhs) const override
+    {
+        const char *lhs_value = get(lhs);
+        const char *rhs_value = get(rhs);
+        return (strcmp(lhs_value, rhs_value) < 0);
+    }
+};
+
+}