diff options
10 files changed, 128 insertions, 51 deletions
diff --git a/searchlib/src/vespa/searchlib/attribute/enumhintsearchcontext.cpp b/searchlib/src/vespa/searchlib/attribute/enumhintsearchcontext.cpp index db63ddbb3ff..4fec660468b 100644 --- a/searchlib/src/vespa/searchlib/attribute/enumhintsearchcontext.cpp +++ b/searchlib/src/vespa/searchlib/attribute/enumhintsearchcontext.cpp @@ -13,8 +13,7 @@ EnumHintSearchContext:: EnumHintSearchContext(const EnumStoreDictBase &dictionary, uint32_t docIdLimit, uint64_t numValues) - : _dictionary(dictionary), - _frozenRootRef(dictionary.get_frozen_root()), + : _dict_snapshot(dictionary.get_read_snapshot()), _uniqueValues(0u), _docIdLimit(docIdLimit), _numValues(numValues) @@ -28,7 +27,7 @@ EnumHintSearchContext::~EnumHintSearchContext() = default; void EnumHintSearchContext::lookupTerm(const EnumStoreComparator &comp) { - _uniqueValues = _dictionary.lookupFrozenTerm(_frozenRootRef, comp); + _uniqueValues = _dict_snapshot->count(comp); } @@ -36,7 +35,7 @@ void EnumHintSearchContext::lookupRange(const EnumStoreComparator &low, const EnumStoreComparator &high) { - _uniqueValues = _dictionary.lookupFrozenRange(_frozenRootRef, low, high); + _uniqueValues = _dict_snapshot->count_in_range(low, high); } void diff --git a/searchlib/src/vespa/searchlib/attribute/enumhintsearchcontext.h b/searchlib/src/vespa/searchlib/attribute/enumhintsearchcontext.h index 7d6d31fce50..1844c228014 100644 --- a/searchlib/src/vespa/searchlib/attribute/enumhintsearchcontext.h +++ b/searchlib/src/vespa/searchlib/attribute/enumhintsearchcontext.h @@ -15,8 +15,7 @@ namespace search::attribute { class EnumHintSearchContext : public IPostingListSearchContext { - const EnumStoreDictBase &_dictionary; - const btree::BTreeNode::Ref _frozenRootRef; + const EnumStoreDictBase::ReadSnapshot::UP _dict_snapshot; uint32_t _uniqueValues; uint32_t _docIdLimit; uint64_t _numValues; // attr.getStatus().getNumValues(); diff --git a/searchlib/src/vespa/searchlib/attribute/enumstorebase.cpp b/searchlib/src/vespa/searchlib/attribute/enumstorebase.cpp index a7a6a9a692d..196a1ee056a 100644 --- a/searchlib/src/vespa/searchlib/attribute/enumstorebase.cpp +++ b/searchlib/src/vespa/searchlib/attribute/enumstorebase.cpp @@ -435,37 +435,6 @@ EnumStoreDict<Dictionary>::onReset() this->_dict.clear(); } -template <typename Dictionary> -uint32_t -EnumStoreDict<Dictionary>::lookupFrozenTerm(BTreeNode::Ref frozenRootRef, - const datastore::EntryComparator &comp) const -{ - typename Dictionary::ConstIterator itr(BTreeNode::Ref(), - this->_dict.getAllocator()); - itr.lower_bound(frozenRootRef, Index(), comp); - if (itr.valid() && !comp(Index(), itr.getKey())) { - return 1u; - } - return 0u; -} - -template <typename Dictionary> -uint32_t -EnumStoreDict<Dictionary>:: -lookupFrozenRange(BTreeNode::Ref frozenRootRef, - const datastore::EntryComparator &low, - const datastore::EntryComparator &high) const -{ - typename Dictionary::ConstIterator lowerDictItr(BTreeNode::Ref(), - this->_dict.getAllocator()); - lowerDictItr.lower_bound(frozenRootRef, Index(), low); - auto upperDictItr = lowerDictItr; - if (upperDictItr.valid() && !high(Index(), upperDictItr.getKey())) { - upperDictItr.seekPast(Index(), high); - } - return upperDictItr - lowerDictItr; -} - template <> EnumPostingTree & diff --git a/searchlib/src/vespa/searchlib/attribute/enumstorebase.h b/searchlib/src/vespa/searchlib/attribute/enumstorebase.h index 2b4d0d4b110..02fd97d7321 100644 --- a/searchlib/src/vespa/searchlib/attribute/enumstorebase.h +++ b/searchlib/src/vespa/searchlib/attribute/enumstorebase.h @@ -81,13 +81,6 @@ public: virtual void onReset() = 0; virtual btree::BTreeNode::Ref getFrozenRootRef() const = 0; - virtual uint32_t lookupFrozenTerm(btree::BTreeNode::Ref frozenRootRef, - const datastore::EntryComparator &comp) const = 0; - - virtual uint32_t lookupFrozenRange(btree::BTreeNode::Ref frozenRootRef, - const datastore::EntryComparator &low, - const datastore::EntryComparator &high) const = 0; - virtual EnumPostingTree &getPostingDictionary() = 0; virtual const EnumPostingTree &getPostingDictionary() const = 0; virtual bool hasData() const = 0; @@ -139,13 +132,6 @@ public: void onReset() override; btree::BTreeNode::Ref getFrozenRootRef() const override { return this->get_frozen_root(); } - uint32_t lookupFrozenTerm(btree::BTreeNode::Ref frozenRootRef, - const datastore::EntryComparator &comp) const override; - - uint32_t lookupFrozenRange(btree::BTreeNode::Ref frozenRootRef, - const datastore::EntryComparator &low, - const datastore::EntryComparator &high) const override; - EnumPostingTree & getPostingDictionary() override; const EnumPostingTree & getPostingDictionary() const override; diff --git a/vespalib/CMakeLists.txt b/vespalib/CMakeLists.txt index 041b2ccaba0..1a111ed49ef 100644 --- a/vespalib/CMakeLists.txt +++ b/vespalib/CMakeLists.txt @@ -42,6 +42,7 @@ vespa_define_module( src/tests/datastore/buffer_type src/tests/datastore/datastore src/tests/datastore/unique_store + src/tests/datastore/unique_store_dictionary src/tests/datastore/unique_store_string_allocator src/tests/delegatelist src/tests/dotproduct diff --git a/vespalib/src/tests/datastore/unique_store_dictionary/CMakeLists.txt b/vespalib/src/tests/datastore/unique_store_dictionary/CMakeLists.txt new file mode 100644 index 00000000000..b1478dea22c --- /dev/null +++ b/vespalib/src/tests/datastore/unique_store_dictionary/CMakeLists.txt @@ -0,0 +1,9 @@ +# Copyright 2019 Oath Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +vespa_add_executable(vespalib_unique_store_dictionary_test_app TEST + SOURCES + unique_store_dictionary_test.cpp + DEPENDS + vespalib + gtest +) +vespa_add_test(NAME vespalib_unique_store_dictionary_test_app COMMAND vespalib_unique_store_dictionary_test_app) diff --git a/vespalib/src/tests/datastore/unique_store_dictionary/unique_store_dictionary_test.cpp b/vespalib/src/tests/datastore/unique_store_dictionary/unique_store_dictionary_test.cpp new file mode 100644 index 00000000000..8b963dbf007 --- /dev/null +++ b/vespalib/src/tests/datastore/unique_store_dictionary/unique_store_dictionary_test.cpp @@ -0,0 +1,84 @@ +// Copyright 2019 Oath Inc. 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_dictionary.hpp> +#include <vespa/vespalib/gtest/gtest.h> + +#include <vespa/log/log.h> +LOG_SETUP("unique_store_dictionary_test"); + +using namespace search::datastore; +using namespace search::datastore::uniquestore; + +class Comparator : public EntryComparator { +private: + EntryRef _to_find; + + EntryRef resolve(EntryRef ref) const { + if (ref == EntryRef()) { + return _to_find; + } + return ref; + } + +public: + Comparator(uint32_t to_find) + : _to_find(to_find) + {} + bool operator()(const EntryRef lhs, const EntryRef rhs) const override { + return resolve(lhs).ref() < resolve(rhs).ref(); + } +}; + +struct DictionaryReadTest : public ::testing::Test { + DefaultUniqueStoreDictionary dict; + UniqueStoreDictionaryBase::ReadSnapshot::UP snapshot; + + DictionaryReadTest() + : dict(), + snapshot() + { + } + DictionaryReadTest& add(uint32_t value) { + auto result = dict.add(Comparator(value), [=]() { return EntryRef(value); }); + assert(result.inserted()); + return *this; + } + void take_snapshot() { + dict.freeze(); + snapshot = dict.get_read_snapshot(); + } +}; + +TEST_F(DictionaryReadTest, can_count_occurrences_of_a_key) +{ + add(3).add(5).take_snapshot(); + EXPECT_EQ(0, snapshot->count(Comparator(2))); + EXPECT_EQ(1, snapshot->count(Comparator(3))); + EXPECT_EQ(0, snapshot->count(Comparator(4))); + EXPECT_EQ(1, snapshot->count(Comparator(5))); +} + +TEST_F(DictionaryReadTest, can_count_occurrences_of_keys_in_a_range) +{ + add(3).add(5).add(7).add(9).take_snapshot(); + EXPECT_EQ(1, snapshot->count_in_range(Comparator(3), Comparator(3))); + EXPECT_EQ(1, snapshot->count_in_range(Comparator(3), Comparator(4))); + EXPECT_EQ(2, snapshot->count_in_range(Comparator(3), Comparator(5))); + EXPECT_EQ(3, snapshot->count_in_range(Comparator(3), Comparator(7))); + EXPECT_EQ(4, snapshot->count_in_range(Comparator(3), Comparator(9))); + EXPECT_EQ(4, snapshot->count_in_range(Comparator(3), Comparator(10))); + + EXPECT_EQ(0, snapshot->count_in_range(Comparator(5), Comparator(3))); +} + +TEST_F(DictionaryReadTest, can_iterate_all_keys) +{ + using EntryRefVector = std::vector<EntryRef>; + add(3).add(5).add(7).take_snapshot(); + EntryRefVector refs; + snapshot->foreach_key([&](EntryRef ref){ refs.emplace_back(ref); }); + EXPECT_EQ(EntryRefVector({EntryRef(3), EntryRef(5), EntryRef(7)}), refs); +} + +GTEST_MAIN_RUN_ALL_TESTS() diff --git a/vespalib/src/vespa/vespalib/datastore/unique_store_dictionary.h b/vespalib/src/vespa/vespalib/datastore/unique_store_dictionary.h index becd1fd4450..cd13e88c77e 100644 --- a/vespalib/src/vespa/vespalib/datastore/unique_store_dictionary.h +++ b/vespalib/src/vespa/vespalib/datastore/unique_store_dictionary.h @@ -28,6 +28,8 @@ protected: public: ReadSnapshotImpl(FrozenView frozen_view); EntryRef get_frozen_root() const override { return _frozen_view.getRoot(); } + size_t count(const EntryComparator& comp) const override; + size_t count_in_range(const EntryComparator& low, const EntryComparator& high) const override; void foreach_key(std::function<void(EntryRef)> callback) const override; }; diff --git a/vespalib/src/vespa/vespalib/datastore/unique_store_dictionary.hpp b/vespalib/src/vespa/vespalib/datastore/unique_store_dictionary.hpp index 49ffc337206..f3087bc5610 100644 --- a/vespalib/src/vespa/vespalib/datastore/unique_store_dictionary.hpp +++ b/vespalib/src/vespa/vespalib/datastore/unique_store_dictionary.hpp @@ -24,6 +24,32 @@ ReadSnapshotImpl::ReadSnapshotImpl(FrozenView frozen_view) } template <typename DictionaryT, typename ParentT> +size_t +UniqueStoreDictionary<DictionaryT, ParentT>:: +ReadSnapshotImpl::count(const EntryComparator& comp) const +{ + auto itr = _frozen_view.lowerBound(EntryRef(), comp); + if (itr.valid() && !comp(EntryRef(), itr.getKey())) { + return 1u; + } + return 0u; +} + +template <typename DictionaryT, typename ParentT> +size_t +UniqueStoreDictionary<DictionaryT, ParentT>:: +ReadSnapshotImpl::count_in_range(const EntryComparator& low, + const EntryComparator& high) const +{ + auto low_itr = _frozen_view.lowerBound(EntryRef(), low); + auto high_itr = low_itr; + if (high_itr.valid() && !high(EntryRef(), high_itr.getKey())) { + high_itr.seekPast(EntryRef(), high); + } + return high_itr - low_itr; +} + +template <typename DictionaryT, typename ParentT> void UniqueStoreDictionary<DictionaryT, ParentT>:: ReadSnapshotImpl::foreach_key(std::function<void(EntryRef)> callback) const diff --git a/vespalib/src/vespa/vespalib/datastore/unique_store_dictionary_base.h b/vespalib/src/vespa/vespalib/datastore/unique_store_dictionary_base.h index be1b6c8b5a6..e09fdc6093c 100644 --- a/vespalib/src/vespa/vespalib/datastore/unique_store_dictionary_base.h +++ b/vespalib/src/vespa/vespalib/datastore/unique_store_dictionary_base.h @@ -28,6 +28,8 @@ public: virtual ~ReadSnapshot() = default; // TODO: Remove when all relevant functions have been migrated to this API. virtual EntryRef get_frozen_root() const = 0; + virtual size_t count(const EntryComparator& comp) const = 0; + virtual size_t count_in_range(const EntryComparator& low, const EntryComparator& high) const = 0; virtual void foreach_key(std::function<void(EntryRef)> callback) const = 0; }; |