| // Copyright (c) 2011-present, Facebook, Inc. All rights reserved. |
| // This source code is licensed under both the GPLv2 (found in the |
| // COPYING file in the root directory) and Apache 2.0 License |
| // (found in the LICENSE.Apache file in the root directory). |
| // |
| // Copyright (c) 2011 The LevelDB Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. See the AUTHORS file for names of contributors. |
| |
| #pragma once |
| #include <vector> |
| |
| #include "rocksdb/db.h" |
| |
| namespace rocksdb { |
| |
| class SnapshotList; |
| |
| // Snapshots are kept in a doubly-linked list in the DB. |
| // Each SnapshotImpl corresponds to a particular sequence number. |
| class SnapshotImpl : public Snapshot { |
| public: |
| SequenceNumber number_; // const after creation |
| |
| virtual SequenceNumber GetSequenceNumber() const override { return number_; } |
| |
| private: |
| friend class SnapshotList; |
| |
| // SnapshotImpl is kept in a doubly-linked circular list |
| SnapshotImpl* prev_; |
| SnapshotImpl* next_; |
| |
| SnapshotList* list_; // just for sanity checks |
| |
| int64_t unix_time_; |
| |
| // Will this snapshot be used by a Transaction to do write-conflict checking? |
| bool is_write_conflict_boundary_; |
| }; |
| |
| class SnapshotList { |
| public: |
| SnapshotList() { |
| list_.prev_ = &list_; |
| list_.next_ = &list_; |
| list_.number_ = 0xFFFFFFFFL; // placeholder marker, for debugging |
| count_ = 0; |
| } |
| |
| bool empty() const { return list_.next_ == &list_; } |
| SnapshotImpl* oldest() const { assert(!empty()); return list_.next_; } |
| SnapshotImpl* newest() const { assert(!empty()); return list_.prev_; } |
| |
| const SnapshotImpl* New(SnapshotImpl* s, SequenceNumber seq, |
| uint64_t unix_time, bool is_write_conflict_boundary) { |
| s->number_ = seq; |
| s->unix_time_ = unix_time; |
| s->is_write_conflict_boundary_ = is_write_conflict_boundary; |
| s->list_ = this; |
| s->next_ = &list_; |
| s->prev_ = list_.prev_; |
| s->prev_->next_ = s; |
| s->next_->prev_ = s; |
| count_++; |
| return s; |
| } |
| |
| // Do not responsible to free the object. |
| void Delete(const SnapshotImpl* s) { |
| assert(s->list_ == this); |
| s->prev_->next_ = s->next_; |
| s->next_->prev_ = s->prev_; |
| count_--; |
| } |
| |
| // retrieve all snapshot numbers up until max_seq. They are sorted in |
| // ascending order. |
| std::vector<SequenceNumber> GetAll( |
| SequenceNumber* oldest_write_conflict_snapshot = nullptr, |
| const SequenceNumber& max_seq = kMaxSequenceNumber) const { |
| std::vector<SequenceNumber> ret; |
| |
| if (oldest_write_conflict_snapshot != nullptr) { |
| *oldest_write_conflict_snapshot = kMaxSequenceNumber; |
| } |
| |
| if (empty()) { |
| return ret; |
| } |
| const SnapshotImpl* s = &list_; |
| while (s->next_ != &list_) { |
| if (s->next_->number_ > max_seq) { |
| break; |
| } |
| ret.push_back(s->next_->number_); |
| |
| if (oldest_write_conflict_snapshot != nullptr && |
| *oldest_write_conflict_snapshot == kMaxSequenceNumber && |
| s->next_->is_write_conflict_boundary_) { |
| // If this is the first write-conflict boundary snapshot in the list, |
| // it is the oldest |
| *oldest_write_conflict_snapshot = s->next_->number_; |
| } |
| |
| s = s->next_; |
| } |
| return ret; |
| } |
| |
| // Whether there is an active snapshot in range [lower_bound, upper_bound). |
| bool HasSnapshotInRange(SequenceNumber lower_bound, |
| SequenceNumber upper_bound) { |
| if (empty()) { |
| return false; |
| } |
| const SnapshotImpl* s = &list_; |
| while (s->next_ != &list_) { |
| if (s->next_->number_ >= lower_bound) { |
| return s->next_->number_ < upper_bound; |
| } |
| s = s->next_; |
| } |
| return false; |
| } |
| |
| // get the sequence number of the most recent snapshot |
| SequenceNumber GetNewest() { |
| if (empty()) { |
| return 0; |
| } |
| return newest()->number_; |
| } |
| |
| int64_t GetOldestSnapshotTime() const { |
| if (empty()) { |
| return 0; |
| } else { |
| return oldest()->unix_time_; |
| } |
| } |
| |
| uint64_t count() const { return count_; } |
| |
| private: |
| // Dummy head of doubly-linked list of snapshots |
| SnapshotImpl list_; |
| uint64_t count_; |
| }; |
| |
| } // namespace rocksdb |