Add unit test for posting list merger.

3 files changed, 276 insertions, 0 deletions

diff --git a/searchlib/CMakeLists.txt b/searchlib/CMakeLists.txt
index 0bd70592c3d..a39c158cd65 100644
--- a/searchlib/CMakeLists.txt
+++ b/searchlib/CMakeLists.txt
@@ -82,6 +82,7 @@ vespa_define_module(
     src/tests/attribute/extendattributes
     src/tests/attribute/guard
     src/tests/attribute/multi_value_mapping
+    src/tests/attribute/posting_list_merger
     src/tests/attribute/postinglist
     src/tests/attribute/postinglistattribute
     src/tests/attribute/reference_attribute
diff --git a/searchlib/src/tests/attribute/posting_list_merger/CMakeLists.txt b/searchlib/src/tests/attribute/posting_list_merger/CMakeLists.txt
new file mode 100644
index 00000000000..6e3cccf730f
--- /dev/null
+++ b/searchlib/src/tests/attribute/posting_list_merger/CMakeLists.txt
@@ -0,0 +1,8 @@
+# Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+vespa_add_executable(searchlib_posting_list_merger_test_app TEST
+    SOURCES
+    posting_list_merger_test.cpp
+    DEPENDS
+    searchlib
+)
+vespa_add_test(NAME searchlib_posting_list_merger_test_app COMMAND searchlib_posting_list_merger_test_app)
diff --git a/searchlib/src/tests/attribute/posting_list_merger/posting_list_merger_test.cpp b/searchlib/src/tests/attribute/posting_list_merger/posting_list_merger_test.cpp
new file mode 100644
index 00000000000..201bbffbe09
--- /dev/null
+++ b/searchlib/src/tests/attribute/posting_list_merger/posting_list_merger_test.cpp
@@ -0,0 +1,267 @@
+// Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#include <vespa/vespalib/testkit/testapp.h>
+#include <vespa/searchlib/attribute/posting_list_merger.h>
+#include <vespa/vespalib/test/insertion_operators.h>
+
+using search::btree::BTreeNoLeafData;
+using search::attribute::PostingListMerger;
+
+struct Posting {
+    uint32_t lid;
+    int32_t weight;
+    Posting(uint32_t lid_, int32_t weight_)
+        : lid(lid_),
+          weight(weight_)
+    {
+    }
+
+    bool operator==(const Posting &rhs) const {
+        return ((lid == rhs.lid) && (weight == rhs.weight));
+    }
+
+    bool operator<(const Posting &rhs) const { return lid < rhs.lid; }
+};
+
+std::ostream &operator<<(std::ostream &os, const Posting &posting)
+{
+    os << "{" << posting.lid << "," << posting.weight << "}";
+    return os;
+}
+
+
+class WeightedPostingList
+{
+    std::vector<Posting> _entries;
+public:
+    WeightedPostingList(std::vector<Posting> entries)
+        : _entries(std::move(entries))
+    {
+    }
+    ~WeightedPostingList() { }
+
+    template <typename Func>
+    void foreach(Func func) const {
+        for (const auto &posting : _entries) {
+            func(posting.lid, posting.weight);
+        }
+    }
+
+    template <typename Func>
+    void foreach_key(Func func) const {
+        for (const auto &posting : _entries) {
+            func(posting.lid);
+        }
+    }
+};
+
+class SimplePostingList
+{
+    std::vector<uint32_t> _entries;
+public:
+    SimplePostingList(std::vector<uint32_t> entries)
+        : _entries(std::move(entries))
+    {
+    }
+    ~SimplePostingList() { }
+
+    template <typename Func>
+    void foreach(Func func) const {
+        for (const auto &posting : _entries) {
+            func(posting, BTreeNoLeafData::_instance);
+        }
+    }
+
+    template <typename Func>
+    void foreach_key(Func func) const {
+        for (const auto &posting : _entries) {
+            func(posting);
+        }
+    }
+};
+
+class AddWeightPostingList : public SimplePostingList
+{
+    int32_t _weight;
+public:
+    AddWeightPostingList(std::vector<uint32_t> entries, int32_t weight)
+        : SimplePostingList(std::move(entries)),
+          _weight(weight)
+    {
+    }
+    ~AddWeightPostingList() { }
+    template <typename Func>
+    void foreach(Func func) const {
+        int32_t weight = _weight;
+        foreach_key([func, weight](uint32_t lid) { func(lid, weight); });
+    }
+};
+
+constexpr uint32_t docIdLimit = 16384;
+
+struct SimpleFixture
+{
+    PostingListMerger<BTreeNoLeafData> _merger;
+
+    SimpleFixture()
+        : _merger(docIdLimit)
+    {
+    }
+
+    ~SimpleFixture() { }
+
+    void reserveArray(uint32_t postingsCount, size_t postingsSize) { _merger.reserveArray(postingsCount, postingsSize); }
+
+    std::vector<uint32_t> asArray() {
+        const auto &llArray = _merger.getArray();
+        std::vector<uint32_t> result;
+        result.reserve(llArray.size());
+        for (auto &entry : llArray) {
+            result.emplace_back(entry._key);
+        }
+        return result;
+    }
+
+    std::vector<uint32_t> bvAsArray() {
+        const auto &bv = *_merger.getBitVector();
+        std::vector<uint32_t> result;
+        uint32_t lid = bv.getNextTrueBit(0);
+        while (lid + 1 < docIdLimit) {
+            result.emplace_back(lid);
+            lid = bv.getNextTrueBit(lid + 1);
+        }
+        return result;
+    }
+
+    void assertArray(std::vector<uint32_t> exp)
+    {
+        EXPECT_EQUAL(exp, asArray());
+    }
+
+    void assertBitVector(std::vector<uint32_t> exp)
+    {
+        EXPECT_EQUAL(exp, bvAsArray());
+    }
+};
+
+struct WeightedFixture
+{
+    PostingListMerger<int32_t> _merger;
+
+    WeightedFixture()
+        : _merger(docIdLimit)
+    {
+    }
+
+    ~WeightedFixture() { }
+
+    void reserveArray(uint32_t postingsCount, size_t postingsSize) { _merger.reserveArray(postingsCount, postingsSize); }
+
+    std::vector<Posting> asArray() {
+        const auto &llArray = _merger.getArray();
+        std::vector<Posting> result;
+        result.reserve(llArray.size());
+        for (auto &entry : llArray) {
+            result.emplace_back(entry._key, entry.getData());
+        }
+        return result;
+    }
+
+    std::vector<uint32_t> bvAsArray() {
+        const auto &bv = *_merger.getBitVector();
+        std::vector<uint32_t> result;
+        uint32_t lid = bv.getNextTrueBit(0);
+        while (lid + 1 < docIdLimit) {
+            result.emplace_back(lid);
+            lid = bv.getNextTrueBit(lid + 1);
+        }
+        return result;
+    }
+
+    void assertArray(std::vector<Posting> exp)
+    {
+        EXPECT_EQUAL(exp, asArray());
+    }
+
+    void assertBitVector(std::vector<uint32_t> exp)
+    {
+        EXPECT_EQUAL(exp, bvAsArray());
+    }
+};
+
+TEST_F("Single simple array", SimpleFixture)
+{
+    f._merger.reserveArray(1, 4);
+    f._merger.addToArray(SimplePostingList({2, 3, 5, 9}));
+    f._merger.merge();
+    TEST_DO(f.assertArray({2, 3, 5, 9}));
+}
+
+TEST_F("Single weighted array", WeightedFixture)
+{
+    f._merger.reserveArray(1, 4);
+    f._merger.addToArray(WeightedPostingList({{ 2, 102}, {3, 103}, { 5, 105}, {9, 109}}));
+    f._merger.merge();
+    TEST_DO(f.assertArray({{2, 102}, {3, 103}, {5, 105}, {9, 109}}));
+}
+
+TEST_F("Single weighted array with fixed weight", WeightedFixture)
+{
+    f._merger.reserveArray(1, 4);
+    f._merger.addToArray(AddWeightPostingList({2, 3, 5, 9}, 114));
+    f._merger.merge();
+    TEST_DO(f.assertArray({{2, 114}, {3, 114}, {5, 114}, {9, 114}}));
+}
+
+TEST_F("Merge array", WeightedFixture)
+{
+    f._merger.reserveArray(2, 8);
+    f._merger.addToArray(WeightedPostingList({{ 2, 102}, {3, 103}, { 5, 105}, {9, 109}}));
+    f._merger.addToArray(WeightedPostingList({{ 6, 106}, {8, 108}, { 14, 114}, {17, 117}}));
+    f._merger.merge();
+    TEST_DO(f.assertArray({{2, 102}, {3, 103}, {5, 105}, {6, 106}, {8, 108}, {9, 109}, {14, 114}, {17, 117}}));
+}
+
+TEST_F("Merge many arrays", WeightedFixture)
+{
+    std::vector<Posting> res;
+    f._merger.reserveArray(10, 100);
+    for (uint32_t i = 0; i < 10; ++i) {
+        std::vector<Posting> fragment;
+        for (uint32_t j = 0; j < 10; ++j) {
+            fragment.emplace_back(j * 100 + i, j * 200 + i);
+        }
+        f._merger.addToArray(WeightedPostingList(fragment));
+        res.insert(res.end(), fragment.begin(), fragment.end());
+    }
+    f._merger.merge();
+    std::sort(res.begin(), res.end());
+    TEST_DO(f.assertArray(res));
+}
+
+TEST_F("Single simple bitvector", SimpleFixture)
+{
+    f._merger.allocBitVector();
+    f._merger.addToBitVector(SimplePostingList({2, 3, 5, 9}));
+    f._merger.merge();
+    TEST_DO(f.assertBitVector({2, 3, 5, 9}));
+}
+
+
+TEST_F("Single weighted bitvector", WeightedFixture)
+{
+    f._merger.allocBitVector();
+    f._merger.addToBitVector(WeightedPostingList({{ 2, 102}, {3, 103}, { 5, 105}, {9, 109}}));
+    f._merger.merge();
+    TEST_DO(f.assertBitVector({2, 3, 5, 9}));
+}
+
+TEST_F("Single weighted bitvector with fixed weight", WeightedFixture)
+{
+    f._merger.allocBitVector();
+    f._merger.addToBitVector(AddWeightPostingList({2, 3, 5, 9}, 114));
+    f._merger.merge();
+    TEST_DO(f.assertBitVector({2, 3, 5, 9}));
+}
+
+TEST_MAIN() { TEST_RUN_ALL(); }