Update unordered dictionary.

8 files changed, 81 insertions, 14 deletions

diff --git a/vespalib/src/tests/datastore/fixed_size_hash_map/fixed_size_hash_map_test.cpp b/vespalib/src/tests/datastore/fixed_size_hash_map/fixed_size_hash_map_test.cpp
index 2f5e5b9295d..0fad98af10b 100644
--- a/vespalib/src/tests/datastore/fixed_size_hash_map/fixed_size_hash_map_test.cpp
+++ b/vespalib/src/tests/datastore/fixed_size_hash_map/fixed_size_hash_map_test.cpp
@@ -108,7 +108,7 @@ DataStoreFixedSizeHashTest::insert(uint32_t key)
 {
     MyCompare comp(_store, key);
     std::function<EntryRef(void)> insert_entry([this, key]() -> EntryRef { return _allocator.allocate(key); });
-    auto& result = _hash_map->add(comp, insert_entry);
+    auto& result = _hash_map->add(comp, EntryRef(), insert_entry);
     auto ref = result.first.load_relaxed();
     auto &wrapped_entry = _allocator.get_wrapped(ref);
     EXPECT_EQ(key, wrapped_entry.value());
diff --git a/vespalib/src/tests/datastore/simple_hash_map/simple_hash_map_test.cpp b/vespalib/src/tests/datastore/simple_hash_map/simple_hash_map_test.cpp
index e89a0aab038..4dbb35d8516 100644
--- a/vespalib/src/tests/datastore/simple_hash_map/simple_hash_map_test.cpp
+++ b/vespalib/src/tests/datastore/simple_hash_map/simple_hash_map_test.cpp
@@ -102,8 +102,8 @@ void
 DataStoreSimpleHashTest::insert(uint32_t key)
 {
     MyCompare comp(_store, key);
-std::function<EntryRef(void)> insert_entry([this, key]() -> EntryRef { return _allocator.allocate(key); });
-    auto& result = _hash_map.add(comp, insert_entry);
+    std::function<EntryRef(void)> insert_entry([this, key]() -> EntryRef { return _allocator.allocate(key); });
+    auto& result = _hash_map.add(comp, EntryRef(), insert_entry);
     auto ref = result.first.load_relaxed();
     auto &wrapped_entry = _allocator.get_wrapped(ref);
     EXPECT_EQ(key, wrapped_entry.value());
diff --git a/vespalib/src/vespa/vespalib/datastore/atomic_entry_ref.h b/vespalib/src/vespa/vespalib/datastore/atomic_entry_ref.h
index 3ec2d6b163e..f4724e563ca 100644
--- a/vespalib/src/vespa/vespalib/datastore/atomic_entry_ref.h
+++ b/vespalib/src/vespa/vespalib/datastore/atomic_entry_ref.h
@@ -34,6 +34,9 @@ public:
     void store_release(EntryRef ref) noexcept {
         _ref.store(ref.ref(), std::memory_order_release);
     }
+    void store_relaxed(EntryRef ref) noexcept {
+        _ref.store(ref.ref(), std::memory_order_relaxed);
+    }
     EntryRef load_acquire() const noexcept {
         return EntryRef(_ref.load(std::memory_order_acquire));
     }
diff --git a/vespalib/src/vespa/vespalib/datastore/fixed_size_hash_map.cpp b/vespalib/src/vespa/vespalib/datastore/fixed_size_hash_map.cpp
index 14dbc841691..be67e0b1863 100644
--- a/vespalib/src/vespa/vespalib/datastore/fixed_size_hash_map.cpp
+++ b/vespalib/src/vespa/vespalib/datastore/fixed_size_hash_map.cpp
@@ -62,15 +62,15 @@ FixedSizeHashMap::force_add(const EntryComparator& comp, const KvType& kv)
 }
 
 FixedSizeHashMap::KvType&
-FixedSizeHashMap::add(const EntryComparator& comp, std::function<EntryRef(void)>& insert_entry)
+FixedSizeHashMap::add(const EntryComparator& comp, EntryRef key_ref, std::function<EntryRef(void)>& insert_entry)
 {
-    size_t hash_idx = comp.hash(EntryRef()) / _num_stripes;
+    size_t hash_idx = comp.hash(key_ref) / _num_stripes;
     hash_idx %= _modulo;
     auto& chain_head = _chain_heads[hash_idx];
     uint32_t node_idx = chain_head.load_relaxed();
     while (node_idx != no_node_idx) {
         auto& node = _nodes[node_idx];
-        if (comp.equal(EntryRef(), node.get_kv().first.load_relaxed())) {
+        if (comp.equal(key_ref, node.get_kv().first.load_relaxed())) {
             return node.get_kv();
         }
         node_idx = node.get_next_node_idx().load(std::memory_order_relaxed);
@@ -153,8 +153,8 @@ FixedSizeHashMap::remove(const EntryComparator& comp, EntryRef key_ref)
     return nullptr;
 }
 
-const FixedSizeHashMap::KvType*
-FixedSizeHashMap::find(const EntryComparator& comp, EntryRef key_ref) const
+FixedSizeHashMap::KvType*
+FixedSizeHashMap::find(const EntryComparator& comp, EntryRef key_ref)
 {
     size_t hash_idx = comp.hash(key_ref) / _num_stripes;
     hash_idx %= _modulo;
diff --git a/vespalib/src/vespa/vespalib/datastore/fixed_size_hash_map.h b/vespalib/src/vespa/vespalib/datastore/fixed_size_hash_map.h
index 326c3cef765..72373f909df 100644
--- a/vespalib/src/vespa/vespalib/datastore/fixed_size_hash_map.h
+++ b/vespalib/src/vespa/vespalib/datastore/fixed_size_hash_map.h
@@ -96,9 +96,9 @@ public:
     FixedSizeHashMap(uint32_t module, uint32_t capacity, uint32_t num_stripes, const FixedSizeHashMap &orig, const EntryComparator& comp);
     ~FixedSizeHashMap();
 
-    KvType& add(const EntryComparator& comp, std::function<EntryRef(void)>& insert_entry);
+    KvType& add(const EntryComparator& comp, EntryRef key_ref, std::function<EntryRef(void)>& insert_entry);
     KvType* remove(const EntryComparator& comp, EntryRef key_ref);
-    const KvType* find(const EntryComparator& comp, EntryRef key_ref) const;
+    KvType* find(const EntryComparator& comp, EntryRef key_ref);
 
     void transfer_hold_lists(generation_t generation) {
         if (!_hold_1_list.empty()) {
diff --git a/vespalib/src/vespa/vespalib/datastore/simple_hash_map.cpp b/vespalib/src/vespa/vespalib/datastore/simple_hash_map.cpp
index e397eca579a..6995acc5bb4 100644
--- a/vespalib/src/vespa/vespalib/datastore/simple_hash_map.cpp
+++ b/vespalib/src/vespa/vespalib/datastore/simple_hash_map.cpp
@@ -31,6 +31,7 @@ SimpleHashMap::SimpleHashMap(std::unique_ptr<const EntryComparator> comp)
 
 SimpleHashMap::~SimpleHashMap()
 {
+    _gen_holder.clearHoldLists();
     for (size_t i = 0; i < num_stripes; ++i) {
         auto map = _maps[i].load(std::memory_order_relaxed);
         delete map;
@@ -66,15 +67,15 @@ SimpleHashMap::hold_stripe(std::unique_ptr<const FixedSizeHashMap> map)
 }
 
 SimpleHashMap::KvType&
-SimpleHashMap::add(const EntryComparator& comp, std::function<EntryRef(void)>& insert_entry)
+SimpleHashMap::add(const EntryComparator& comp, EntryRef key_ref, std::function<EntryRef(void)>& insert_entry)
 {
-    size_t stripe = get_stripe(comp, EntryRef());
+    size_t stripe = get_stripe(comp, key_ref);
     auto map = _maps[stripe].load(std::memory_order_relaxed);
     if (map == nullptr || map->full()) {
         alloc_stripe(stripe);
         map = _maps[stripe].load(std::memory_order_relaxed);
     }
-    return map->add(comp, insert_entry);
+    return map->add(comp, key_ref, insert_entry);
 }
 
 SimpleHashMap::KvType*
@@ -88,6 +89,17 @@ SimpleHashMap::remove(const EntryComparator& comp, EntryRef key_ref)
     return map->remove(comp, key_ref);
 }
 
+SimpleHashMap::KvType*
+SimpleHashMap::find(const EntryComparator& comp, EntryRef key_ref)
+{
+    size_t stripe = get_stripe(comp, key_ref);
+    auto map = _maps[stripe].load(std::memory_order_relaxed);
+    if (map == nullptr) {
+        return nullptr;
+    }
+    return map->find(comp, key_ref);
+}
+
 const SimpleHashMap::KvType*
 SimpleHashMap::find(const EntryComparator& comp, EntryRef key_ref) const
 {
diff --git a/vespalib/src/vespa/vespalib/datastore/simple_hash_map.h b/vespalib/src/vespa/vespalib/datastore/simple_hash_map.h
index 1acc11d50c8..78e224c65df 100644
--- a/vespalib/src/vespa/vespalib/datastore/simple_hash_map.h
+++ b/vespalib/src/vespa/vespalib/datastore/simple_hash_map.h
@@ -46,12 +46,14 @@ private:
 public:
     SimpleHashMap(std::unique_ptr<const EntryComparator> comp);
     ~SimpleHashMap();
-    KvType& add(const EntryComparator& comp, std::function<EntryRef(void)> &insert_entry);
+    KvType& add(const EntryComparator& comp, EntryRef key_ref, std::function<EntryRef(void)> &insert_entry);
     KvType* remove(const EntryComparator& comp, EntryRef key_ref);
+    KvType* find(const EntryComparator& comp, EntryRef key_ref);
     const KvType* find(const EntryComparator& comp, EntryRef key_ref) const;
     void transfer_hold_lists(generation_t generation);
     void trim_hold_lists(generation_t first_used);
     size_t size() const noexcept;
+    const EntryComparator &get_default_comparator() const noexcept { return *_comp; }
 };
 
 }
diff --git a/vespalib/src/vespa/vespalib/datastore/unique_store_dictionary.hpp b/vespalib/src/vespa/vespalib/datastore/unique_store_dictionary.hpp
index 713438f8419..2483ae9b4b2 100644
--- a/vespalib/src/vespa/vespalib/datastore/unique_store_dictionary.hpp
+++ b/vespalib/src/vespa/vespalib/datastore/unique_store_dictionary.hpp
@@ -80,6 +80,9 @@ void
 UniqueStoreDictionary<DictionaryT, ParentT, UnorderedDictionaryT>::transfer_hold_lists(generation_t generation)
 {
     _dict.getAllocator().transferHoldLists(generation);
+    if constexpr (has_unordered_dictionary) {
+        this->_unordered_dict.transfer_hold_lists(generation);
+    }
 }
 
 template <typename DictionaryT, typename ParentT, typename UnorderedDictionaryT>
@@ -87,6 +90,9 @@ void
 UniqueStoreDictionary<DictionaryT, ParentT, UnorderedDictionaryT>::trim_hold_lists(generation_t firstUsed)
 {
     _dict.getAllocator().trimHoldLists(firstUsed);
+    if constexpr (has_unordered_dictionary) {
+        this->_unordered_dict.trim_hold_lists(firstUsed);
+    }
 }
 
 template <typename DictionaryT, typename ParentT, typename UnorderedDictionaryT>
@@ -96,11 +102,20 @@ UniqueStoreDictionary<DictionaryT, ParentT, UnorderedDictionaryT>::add(const Ent
 {
     auto itr = _dict.lowerBound(EntryRef(), comp);
     if (itr.valid() && !comp.less(EntryRef(), itr.getKey())) {
+        if constexpr (has_unordered_dictionary) {
+            auto* result = this->_unordered_dict.find(comp, EntryRef());
+            assert(result != nullptr && result->first.load_relaxed() == itr.getKey());
+        }
         return UniqueStoreAddResult(itr.getKey(), false);
 
     } else {
         EntryRef newRef = insertEntry();
         _dict.insert(itr, newRef, DataType());
+        if constexpr (has_unordered_dictionary) {
+            std::function<EntryRef(void)> insert_unordered_entry([newRef]() -> EntryRef { return newRef; });
+            auto& add_result = this->_unordered_dict.add(comp, newRef, insert_unordered_entry);
+            assert(add_result.first.load_relaxed() == newRef);
+        }
         return UniqueStoreAddResult(newRef, true);
     }
 }
@@ -111,8 +126,16 @@ UniqueStoreDictionary<DictionaryT, ParentT, UnorderedDictionaryT>::find(const En
 {
     auto itr = _dict.lowerBound(EntryRef(), comp);
     if (itr.valid() && !comp.less(EntryRef(), itr.getKey())) {
+        if constexpr (has_unordered_dictionary) {
+            auto* result = this->_unordered_dict.find(comp, EntryRef());
+            assert(result != nullptr && result->first.load_relaxed() == itr.getKey());
+        }
         return itr.getKey();
     } else {
+        if constexpr (has_unordered_dictionary) {
+            auto* result = this->_unordered_dict.find(comp, EntryRef());
+            assert(result == nullptr);
+        }
         return EntryRef();
     }
 }
@@ -125,6 +148,10 @@ UniqueStoreDictionary<DictionaryT, ParentT, UnorderedDictionaryT>::remove(const
     auto itr = _dict.lowerBound(ref, comp);
     assert(itr.valid() && itr.getKey() == ref);
     _dict.remove(itr);
+    if constexpr (has_unordered_dictionary) {
+        auto *result = this->_unordered_dict.remove(comp, ref);
+        assert(result != nullptr && result->first.load_relaxed() == ref);
+    }
 }
 
 template <typename DictionaryT, typename ParentT, typename UnorderedDictionaryT>
@@ -138,6 +165,11 @@ UniqueStoreDictionary<DictionaryT, ParentT, UnorderedDictionaryT>::move_entries(
         if (newRef != oldRef) {
             _dict.thaw(itr);
             itr.writeKey(newRef);
+            if constexpr (has_unordered_dictionary) {
+                auto result = this->_unordered_dict.find(this->_unordered_dict.get_default_comparator(), oldRef);
+                assert(result != nullptr && result->first.load_relaxed() == oldRef);
+                result->first.store_release(newRef);
+            }
         }
         ++itr;
     }
@@ -185,6 +217,13 @@ UniqueStoreDictionary<DictionaryT, ParentT, UnorderedDictionaryT>::build(vespali
         builder.insert(ref, DataType());
     }
     _dict.assign(builder);
+    if constexpr (has_unordered_dictionary) {
+        for (const auto& ref : refs) {
+            std::function<EntryRef(void)> insert_unordered_entry([ref]() -> EntryRef { return ref; });
+            auto& add_result = this->_unordered_dict.add(this->_unordered_dict.get_default_comparator(), ref, insert_unordered_entry);
+            assert(add_result.first.load_relaxed() == ref);
+        }
+    }
 }
 
 template <typename DictionaryT, typename ParentT, typename UnorderedDictionaryT>
@@ -202,6 +241,17 @@ UniqueStoreDictionary<DictionaryT, ParentT, UnorderedDictionaryT>::build_with_pa
         }
     }
     _dict.assign(builder);
+    if constexpr (has_unordered_dictionary) {
+        for (size_t i = 0; i < refs.size(); ++i) {
+            EntryRef ref = refs[i];
+            std::function<EntryRef(void)> insert_unordered_entry([ref]() -> EntryRef { return ref; });
+            auto& add_result = this->_unordered_dict.add(this->_unordered_dict.get_default_comparator(), ref, insert_unordered_entry);
+            assert(add_result.first.load_relaxed() == refs[i]);
+            if constexpr (std::is_same_v<DataType, uint32_t>) {
+                add_result.second.store_relaxed(EntryRef(payloads[i]));
+            }
+        }
+    }
 }
 
 template <typename DictionaryT, typename ParentT, typename UnorderedDictionaryT>