ceph/src/rocksdb/util/vector_iterator.h

   1 #pragma once
   2
   3 #include <algorithm>
   4 #include <string>
   5 #include <vector>
   6
   7 #include "db/dbformat.h"
   8 #include "rocksdb/iterator.h"
   9 #include "rocksdb/slice.h"
  10 #include "table/internal_iterator.h"
  11
  12 namespace rocksdb {
  13
  14 // Iterator over a vector of keys/values
  15 class VectorIterator : public InternalIterator {
  16  public:
  17   VectorIterator(std::vector<std::string> keys, std::vector<std::string> values,
  18                  const InternalKeyComparator* icmp)
  19       : keys_(std::move(keys)),
  20         values_(std::move(values)),
  21         indexed_cmp_(icmp, &keys_),
  22         current_(keys.size()) {
  23     assert(keys_.size() == values_.size());
  24
  25     indices_.reserve(keys_.size());
  26     for (size_t i = 0; i < keys_.size(); i++) {
  27       indices_.push_back(i);
  28     }
  29     std::sort(indices_.begin(), indices_.end(), indexed_cmp_);
  30   }
  31
  32   virtual bool Valid() const override {
  33     return !indices_.empty() && current_ < indices_.size();
  34   }
  35
  36   virtual void SeekToFirst() override { current_ = 0; }
  37   virtual void SeekToLast() override { current_ = indices_.size() - 1; }
  38
  39   virtual void Seek(const Slice& target) override {
  40     current_ = std::lower_bound(indices_.begin(), indices_.end(), target,
  41                                 indexed_cmp_) -
  42                indices_.begin();
  43   }
  44
  45   virtual void SeekForPrev(const Slice& target) override {
  46     current_ = std::lower_bound(indices_.begin(), indices_.end(), target,
  47                                 indexed_cmp_) -
  48                indices_.begin();
  49     if (!Valid()) {
  50       SeekToLast();
  51     } else {
  52       Prev();
  53     }
  54   }
  55
  56   virtual void Next() override { current_++; }
  57   virtual void Prev() override { current_--; }
  58
  59   virtual Slice key() const override {
  60     return Slice(keys_[indices_[current_]]);
  61   }
  62   virtual Slice value() const override {
  63     return Slice(values_[indices_[current_]]);
  64   }
  65
  66   virtual Status status() const override { return Status::OK(); }
  67
  68   virtual bool IsKeyPinned() const override { return true; }
  69   virtual bool IsValuePinned() const override { return true; }
  70
  71  private:
  72   struct IndexedKeyComparator {
  73     IndexedKeyComparator(const InternalKeyComparator* c,
  74                          const std::vector<std::string>* ks)
  75         : cmp(c), keys(ks) {}
  76
  77     bool operator()(size_t a, size_t b) const {
  78       return cmp->Compare((*keys)[a], (*keys)[b]) < 0;
  79     }
  80
  81     bool operator()(size_t a, const Slice& b) const {
  82       return cmp->Compare((*keys)[a], b) < 0;
  83     }
  84
  85     bool operator()(const Slice& a, size_t b) const {
  86       return cmp->Compare(a, (*keys)[b]) < 0;
  87     }
  88
  89     const InternalKeyComparator* cmp;
  90     const std::vector<std::string>* keys;
  91   };
  92
  93   std::vector<std::string> keys_;
  94   std::vector<std::string> values_;
  95   IndexedKeyComparator indexed_cmp_;
  96   std::vector<size_t> indices_;
  97   size_t current_;
  98 };
  99
 100 }  // namespace rocksdb