Author: omtcyfz Date: Mon Aug 20 01:47:30 2018 New Revision: 340155 URL: http://llvm.org/viewvc/llvm-project?rev=340155&view=rev Log: [clangd] Implement TRUE Iterator
This patch introduces TRUE Iterator which efficiently handles posting lists containing all items within `[0, Size)` range. Reviewed by: ioeric Differential Revision: https://reviews.llvm.org/D50955 Modified: clang-tools-extra/trunk/clangd/index/dex/Iterator.cpp clang-tools-extra/trunk/clangd/index/dex/Iterator.h clang-tools-extra/trunk/unittests/clangd/DexIndexTests.cpp Modified: clang-tools-extra/trunk/clangd/index/dex/Iterator.cpp URL: http://llvm.org/viewvc/llvm-project/clang-tools-extra/trunk/clangd/index/dex/Iterator.cpp?rev=340155&r1=340154&r2=340155&view=diff ============================================================================== --- clang-tools-extra/trunk/clangd/index/dex/Iterator.cpp (original) +++ clang-tools-extra/trunk/clangd/index/dex/Iterator.cpp Mon Aug 20 01:47:30 2018 @@ -225,6 +225,41 @@ private: std::vector<std::unique_ptr<Iterator>> Children; }; +/// TrueIterator handles PostingLists which contain all items of the index. It +/// stores size of the virtual posting list, and all operations are performed +/// in O(1). +class TrueIterator : public Iterator { +public: + TrueIterator(DocID Size) : Size(Size) {} + + bool reachedEnd() const override { return Index >= Size; } + + void advance() override { + assert(!reachedEnd() && "Can't advance iterator after it reached the end."); + ++Index; + } + + void advanceTo(DocID ID) override { + assert(!reachedEnd() && "Can't advance iterator after it reached the end."); + Index = std::min(ID, Size); + } + + DocID peek() const override { + assert(!reachedEnd() && "TrueIterator can't call peek() at the end."); + return Index; + } + +private: + llvm::raw_ostream &dump(llvm::raw_ostream &OS) const override { + OS << "(TRUE {" << Index << "} out of " << Size << ")"; + return OS; + } + + DocID Index = 0; + /// Size of the underlying virtual PostingList. + DocID Size; +}; + } // end namespace std::vector<DocID> consume(Iterator &It, size_t Limit) { @@ -249,6 +284,10 @@ createOr(std::vector<std::unique_ptr<Ite return llvm::make_unique<OrIterator>(move(Children)); } +std::unique_ptr<Iterator> createTrue(DocID Size) { + return llvm::make_unique<TrueIterator>(Size); +} + } // namespace dex } // namespace clangd } // namespace clang Modified: clang-tools-extra/trunk/clangd/index/dex/Iterator.h URL: http://llvm.org/viewvc/llvm-project/clang-tools-extra/trunk/clangd/index/dex/Iterator.h?rev=340155&r1=340154&r2=340155&view=diff ============================================================================== --- clang-tools-extra/trunk/clangd/index/dex/Iterator.h (original) +++ clang-tools-extra/trunk/clangd/index/dex/Iterator.h Mon Aug 20 01:47:30 2018 @@ -129,6 +129,10 @@ createAnd(std::vector<std::unique_ptr<It std::unique_ptr<Iterator> createOr(std::vector<std::unique_ptr<Iterator>> Children); +/// Returns TRUE Iterator which iterates over "virtual" PostingList containing +/// all items in range [0, Size) in an efficient manner. +std::unique_ptr<Iterator> createTrue(DocID Size); + /// This allows createAnd(create(...), create(...)) syntax. template <typename... Args> std::unique_ptr<Iterator> createAnd(Args... args) { std::vector<std::unique_ptr<Iterator>> Children; Modified: clang-tools-extra/trunk/unittests/clangd/DexIndexTests.cpp URL: http://llvm.org/viewvc/llvm-project/clang-tools-extra/trunk/unittests/clangd/DexIndexTests.cpp?rev=340155&r1=340154&r2=340155&view=diff ============================================================================== --- clang-tools-extra/trunk/unittests/clangd/DexIndexTests.cpp (original) +++ clang-tools-extra/trunk/unittests/clangd/DexIndexTests.cpp Mon Aug 20 01:47:30 2018 @@ -262,6 +262,19 @@ TEST(DexIndexIterators, Limit) { EXPECT_THAT(consume(*DocIterator, 0), ElementsAre()); } +TEST(DexIndexIterators, True) { + auto TrueIterator = createTrue(0U); + EXPECT_THAT(TrueIterator->reachedEnd(), true); + EXPECT_THAT(consume(*TrueIterator), ElementsAre()); + + PostingList L0 = {1, 2, 5, 7}; + TrueIterator = createTrue(7U); + EXPECT_THAT(TrueIterator->peek(), 0); + auto AndIterator = createAnd(create(L0), move(TrueIterator)); + EXPECT_THAT(AndIterator->reachedEnd(), false); + EXPECT_THAT(consume(*AndIterator), ElementsAre(1, 2, 5)); +} + testing::Matcher<std::vector<Token>> trigramsAre(std::initializer_list<std::string> Trigrams) { std::vector<Token> Tokens; _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
