diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-21 11:54:28 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-21 11:54:28 +0000 |
commit | e6918187568dbd01842d8d1d2c808ce16a894239 (patch) | |
tree | 64f88b554b444a49f656b6c656111a145cbbaa28 /src/rocksdb/util/vector_iterator.h | |
parent | Initial commit. (diff) | |
download | ceph-upstream/18.2.2.tar.xz ceph-upstream/18.2.2.zip |
Adding upstream version 18.2.2.upstream/18.2.2
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to '')
-rw-r--r-- | src/rocksdb/util/vector_iterator.h | 118 |
1 files changed, 118 insertions, 0 deletions
diff --git a/src/rocksdb/util/vector_iterator.h b/src/rocksdb/util/vector_iterator.h new file mode 100644 index 000000000..c4cc01d56 --- /dev/null +++ b/src/rocksdb/util/vector_iterator.h @@ -0,0 +1,118 @@ +// Copyright (c) Facebook, Inc. and its affiliates. All Rights Reserved. +#pragma once + +#include <algorithm> +#include <string> +#include <vector> + +#include "db/dbformat.h" +#include "rocksdb/comparator.h" +#include "rocksdb/iterator.h" +#include "rocksdb/slice.h" +#include "table/internal_iterator.h" + +namespace ROCKSDB_NAMESPACE { + +// Iterator over a vector of keys/values +class VectorIterator : public InternalIterator { + public: + VectorIterator(std::vector<std::string> keys, std::vector<std::string> values, + const CompareInterface* icmp = nullptr) + : keys_(std::move(keys)), + values_(std::move(values)), + current_(keys_.size()), + indexed_cmp_(icmp, &keys_) { + assert(keys_.size() == values_.size()); + + indices_.reserve(keys_.size()); + for (size_t i = 0; i < keys_.size(); i++) { + indices_.push_back(i); + } + if (icmp != nullptr) { + std::sort(indices_.begin(), indices_.end(), indexed_cmp_); + } + } + + virtual bool Valid() const override { + return !indices_.empty() && current_ < indices_.size(); + } + + virtual void SeekToFirst() override { current_ = 0; } + virtual void SeekToLast() override { current_ = indices_.size() - 1; } + + virtual void Seek(const Slice& target) override { + if (indexed_cmp_.cmp != nullptr) { + current_ = std::lower_bound(indices_.begin(), indices_.end(), target, + indexed_cmp_) - + indices_.begin(); + } else { + current_ = + std::lower_bound(keys_.begin(), keys_.end(), target.ToString()) - + keys_.begin(); + } + } + + virtual void SeekForPrev(const Slice& target) override { + if (indexed_cmp_.cmp != nullptr) { + current_ = std::upper_bound(indices_.begin(), indices_.end(), target, + indexed_cmp_) - + indices_.begin(); + } else { + current_ = + std::upper_bound(keys_.begin(), keys_.end(), target.ToString()) - + keys_.begin(); + } + if (!Valid()) { + SeekToLast(); + } else { + Prev(); + } + } + + virtual void Next() override { current_++; } + virtual void Prev() override { current_--; } + + virtual Slice key() const override { + return Slice(keys_[indices_[current_]]); + } + virtual Slice value() const override { + return Slice(values_[indices_[current_]]); + } + + virtual Status status() const override { return Status::OK(); } + + virtual bool IsKeyPinned() const override { return true; } + virtual bool IsValuePinned() const override { return true; } + + protected: + std::vector<std::string> keys_; + std::vector<std::string> values_; + size_t current_; + + private: + struct IndexedKeyComparator { + IndexedKeyComparator(const CompareInterface* c, + const std::vector<std::string>* ks) + : cmp(c), keys(ks) {} + + bool operator()(size_t a, size_t b) const { + return cmp->Compare((*keys)[a], (*keys)[b]) < 0; + } + + bool operator()(size_t a, const Slice& b) const { + return cmp->Compare((*keys)[a], b) < 0; + } + + bool operator()(const Slice& a, size_t b) const { + return cmp->Compare(a, (*keys)[b]) < 0; + } + + const CompareInterface* cmp; + const std::vector<std::string>* keys; + }; + + IndexedKeyComparator indexed_cmp_; + std::vector<size_t> indices_; +}; + +} // namespace ROCKSDB_NAMESPACE |