Branch data     Line data    Source code

#       1                 :            : // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
#       2                 :            : // Use of this source code is governed by a BSD-style license that can be
#       3                 :            : // found in the LICENSE file. See the AUTHORS file for names of contributors.
#       4                 :            : 
#       5                 :            : #include "table/merger.h"
#       6                 :            : 
#       7                 :            : #include "leveldb/comparator.h"
#       8                 :            : #include "leveldb/iterator.h"
#       9                 :            : #include "table/iterator_wrapper.h"
#      10                 :            : 
#      11                 :            : namespace leveldb {
#      12                 :            : 
#      13                 :            : namespace {
#      14                 :            : class MergingIterator : public Iterator {
#      15                 :            :  public:
#      16                 :            :   MergingIterator(const Comparator* comparator, Iterator** children, int n)
#      17                 :            :       : comparator_(comparator),
#      18                 :            :         children_(new IteratorWrapper[n]),
#      19                 :            :         n_(n),
#      20                 :            :         current_(nullptr),
#      21                 :       1123 :         direction_(kForward) {
#      22         [ +  + ]:       4385 :     for (int i = 0; i < n; i++) {
#      23                 :       3262 :       children_[i].Set(children[i]);
#      24                 :       3262 :     }
#      25                 :       1123 :   }
#      26                 :            : 
#      27                 :       1123 :   ~MergingIterator() override { delete[] children_; }
#      28                 :            : 
#      29                 :     900854 :   bool Valid() const override { return (current_ != nullptr); }
#      30                 :            : 
#      31                 :        112 :   void SeekToFirst() override {
#      32         [ +  + ]:        541 :     for (int i = 0; i < n_; i++) {
#      33                 :        429 :       children_[i].SeekToFirst();
#      34                 :        429 :     }
#      35                 :        112 :     FindSmallest();
#      36                 :        112 :     direction_ = kForward;
#      37                 :        112 :   }
#      38                 :            : 
#      39                 :          0 :   void SeekToLast() override {
#      40         [ #  # ]:          0 :     for (int i = 0; i < n_; i++) {
#      41                 :          0 :       children_[i].SeekToLast();
#      42                 :          0 :     }
#      43                 :          0 :     FindLargest();
#      44                 :          0 :     direction_ = kReverse;
#      45                 :          0 :   }
#      46                 :            : 
#      47                 :       1011 :   void Seek(const Slice& target) override {
#      48         [ +  + ]:       3844 :     for (int i = 0; i < n_; i++) {
#      49                 :       2833 :       children_[i].Seek(target);
#      50                 :       2833 :     }
#      51                 :       1011 :     FindSmallest();
#      52                 :       1011 :     direction_ = kForward;
#      53                 :       1011 :   }
#      54                 :            : 
#      55                 :     134396 :   void Next() override {
#      56                 :     134396 :     assert(Valid());
#      57                 :            : 
#      58                 :            :     // Ensure that all children are positioned after key().
#      59                 :            :     // If we are moving in the forward direction, it is already
#      60                 :            :     // true for all of the non-current_ children since current_ is
#      61                 :            :     // the smallest child and key() == current_->key().  Otherwise,
#      62                 :            :     // we explicitly position the non-current_ children.
#      63         [ -  + ]:     134396 :     if (direction_ != kForward) {
#      64         [ #  # ]:          0 :       for (int i = 0; i < n_; i++) {
#      65                 :          0 :         IteratorWrapper* child = &children_[i];
#      66         [ #  # ]:          0 :         if (child != current_) {
#      67                 :          0 :           child->Seek(key());
#      68 [ #  # ][ #  # ]:          0 :           if (child->Valid() &&
#      69         [ #  # ]:          0 :               comparator_->Compare(key(), child->key()) == 0) {
#      70                 :          0 :             child->Next();
#      71                 :          0 :           }
#      72                 :          0 :         }
#      73                 :          0 :       }
#      74                 :          0 :       direction_ = kForward;
#      75                 :          0 :     }
#      76                 :            : 
#      77                 :     134396 :     current_->Next();
#      78                 :     134396 :     FindSmallest();
#      79                 :     134396 :   }
#      80                 :            : 
#      81                 :          0 :   void Prev() override {
#      82                 :          0 :     assert(Valid());
#      83                 :            : 
#      84                 :            :     // Ensure that all children are positioned before key().
#      85                 :            :     // If we are moving in the reverse direction, it is already
#      86                 :            :     // true for all of the non-current_ children since current_ is
#      87                 :            :     // the largest child and key() == current_->key().  Otherwise,
#      88                 :            :     // we explicitly position the non-current_ children.
#      89         [ #  # ]:          0 :     if (direction_ != kReverse) {
#      90         [ #  # ]:          0 :       for (int i = 0; i < n_; i++) {
#      91                 :          0 :         IteratorWrapper* child = &children_[i];
#      92         [ #  # ]:          0 :         if (child != current_) {
#      93                 :          0 :           child->Seek(key());
#      94         [ #  # ]:          0 :           if (child->Valid()) {
#      95                 :            :             // Child is at first entry >= key().  Step back one to be < key()
#      96                 :          0 :             child->Prev();
#      97                 :          0 :           } else {
#      98                 :            :             // Child has no entries >= key().  Position at last entry.
#      99                 :          0 :             child->SeekToLast();
#     100                 :          0 :           }
#     101                 :          0 :         }
#     102                 :          0 :       }
#     103                 :          0 :       direction_ = kReverse;
#     104                 :          0 :     }
#     105                 :            : 
#     106                 :          0 :     current_->Prev();
#     107                 :          0 :     FindLargest();
#     108                 :          0 :   }
#     109                 :            : 
#     110                 :     317146 :   Slice key() const override {
#     111                 :     317146 :     assert(Valid());
#     112                 :          0 :     return current_->key();
#     113                 :     317146 :   }
#     114                 :            : 
#     115                 :     222599 :   Slice value() const override {
#     116                 :     222599 :     assert(Valid());
#     117                 :          0 :     return current_->value();
#     118                 :     222599 :   }
#     119                 :            : 
#     120                 :        216 :   Status status() const override {
#     121                 :        216 :     Status status;
#     122         [ +  + ]:       1058 :     for (int i = 0; i < n_; i++) {
#     123                 :        842 :       status = children_[i].status();
#     124         [ -  + ]:        842 :       if (!status.ok()) {
#     125                 :          0 :         break;
#     126                 :          0 :       }
#     127                 :        842 :     }
#     128                 :        216 :     return status;
#     129                 :        216 :   }
#     130                 :            : 
#     131                 :            :  private:
#     132                 :            :   // Which direction is the iterator moving?
#     133                 :            :   enum Direction { kForward, kReverse };
#     134                 :            : 
#     135                 :            :   void FindSmallest();
#     136                 :            :   void FindLargest();
#     137                 :            : 
#     138                 :            :   // We might want to use a heap in case there are lots of children.
#     139                 :            :   // For now we use a simple array since we expect a very small number
#     140                 :            :   // of children in leveldb.
#     141                 :            :   const Comparator* comparator_;
#     142                 :            :   IteratorWrapper* children_;
#     143                 :            :   int n_;
#     144                 :            :   IteratorWrapper* current_;
#     145                 :            :   Direction direction_;
#     146                 :            : };
#     147                 :            : 
#     148                 :     135526 : void MergingIterator::FindSmallest() {
#     149                 :     135526 :   IteratorWrapper* smallest = nullptr;
#     150         [ +  + ]:     512726 :   for (int i = 0; i < n_; i++) {
#     151                 :     377200 :     IteratorWrapper* child = &children_[i];
#     152         [ +  + ]:     377200 :     if (child->Valid()) {
#     153         [ +  + ]:     288236 :       if (smallest == nullptr) {
#     154                 :     134886 :         smallest = child;
#     155         [ +  + ]:     153350 :       } else if (comparator_->Compare(child->key(), smallest->key()) < 0) {
#     156                 :      50725 :         smallest = child;
#     157                 :      50725 :       }
#     158                 :     288236 :     }
#     159                 :     377200 :   }
#     160                 :     135526 :   current_ = smallest;
#     161                 :     135526 : }
#     162                 :            : 
#     163                 :          0 : void MergingIterator::FindLargest() {
#     164                 :          0 :   IteratorWrapper* largest = nullptr;
#     165         [ #  # ]:          0 :   for (int i = n_ - 1; i >= 0; i--) {
#     166                 :          0 :     IteratorWrapper* child = &children_[i];
#     167         [ #  # ]:          0 :     if (child->Valid()) {
#     168         [ #  # ]:          0 :       if (largest == nullptr) {
#     169                 :          0 :         largest = child;
#     170         [ #  # ]:          0 :       } else if (comparator_->Compare(child->key(), largest->key()) > 0) {
#     171                 :          0 :         largest = child;
#     172                 :          0 :       }
#     173                 :          0 :     }
#     174                 :          0 :   }
#     175                 :          0 :   current_ = largest;
#     176                 :          0 : }
#     177                 :            : }  // namespace
#     178                 :            : 
#     179                 :            : Iterator* NewMergingIterator(const Comparator* comparator, Iterator** children,
#     180                 :       3487 :                              int n) {
#     181                 :       3487 :   assert(n >= 0);
#     182         [ -  + ]:       3487 :   if (n == 0) {
#     183                 :          0 :     return NewEmptyIterator();
#     184         [ +  + ]:       3487 :   } else if (n == 1) {
#     185                 :       2364 :     return children[0];
#     186                 :       2364 :   } else {
#     187                 :       1123 :     return new MergingIterator(comparator, children, n);
#     188                 :       1123 :   }
#     189                 :       3487 : }
#     190                 :            : 
#     191                 :            : }  // namespace leveldb