]>
Commit | Line | Data |
---|---|---|
7c673cae | 1 | // Copyright (c) 2011-present, Facebook, Inc. All rights reserved. |
11fdf7f2 TL |
2 | // This source code is licensed under both the GPLv2 (found in the |
3 | // COPYING file in the root directory) and Apache 2.0 License | |
4 | // (found in the LICENSE.Apache file in the root directory). | |
7c673cae FG |
5 | // |
6 | // Copyright (c) 2011 The LevelDB Authors. All rights reserved. | |
7 | // Use of this source code is governed by a BSD-style license that can be | |
8 | // found in the LICENSE file. See the AUTHORS file for names of contributors. | |
9 | ||
10 | #pragma once | |
11 | #include <vector> | |
12 | ||
13 | #include "rocksdb/db.h" | |
14 | ||
f67539c2 | 15 | namespace ROCKSDB_NAMESPACE { |
7c673cae FG |
16 | |
17 | class SnapshotList; | |
18 | ||
19 | // Snapshots are kept in a doubly-linked list in the DB. | |
20 | // Each SnapshotImpl corresponds to a particular sequence number. | |
21 | class SnapshotImpl : public Snapshot { | |
22 | public: | |
23 | SequenceNumber number_; // const after creation | |
11fdf7f2 TL |
24 | // It indicates the smallest uncommitted data at the time the snapshot was |
25 | // taken. This is currently used by WritePrepared transactions to limit the | |
26 | // scope of queries to IsInSnpashot. | |
494da23a | 27 | SequenceNumber min_uncommitted_ = kMinUnCommittedSeq; |
7c673cae FG |
28 | |
29 | virtual SequenceNumber GetSequenceNumber() const override { return number_; } | |
30 | ||
31 | private: | |
32 | friend class SnapshotList; | |
33 | ||
34 | // SnapshotImpl is kept in a doubly-linked circular list | |
35 | SnapshotImpl* prev_; | |
36 | SnapshotImpl* next_; | |
37 | ||
38 | SnapshotList* list_; // just for sanity checks | |
39 | ||
40 | int64_t unix_time_; | |
41 | ||
42 | // Will this snapshot be used by a Transaction to do write-conflict checking? | |
43 | bool is_write_conflict_boundary_; | |
44 | }; | |
45 | ||
46 | class SnapshotList { | |
47 | public: | |
48 | SnapshotList() { | |
49 | list_.prev_ = &list_; | |
50 | list_.next_ = &list_; | |
51 | list_.number_ = 0xFFFFFFFFL; // placeholder marker, for debugging | |
11fdf7f2 TL |
52 | // Set all the variables to make UBSAN happy. |
53 | list_.list_ = nullptr; | |
54 | list_.unix_time_ = 0; | |
55 | list_.is_write_conflict_boundary_ = false; | |
7c673cae FG |
56 | count_ = 0; |
57 | } | |
58 | ||
11fdf7f2 TL |
59 | // No copy-construct. |
60 | SnapshotList(const SnapshotList&) = delete; | |
61 | ||
7c673cae FG |
62 | bool empty() const { return list_.next_ == &list_; } |
63 | SnapshotImpl* oldest() const { assert(!empty()); return list_.next_; } | |
64 | SnapshotImpl* newest() const { assert(!empty()); return list_.prev_; } | |
65 | ||
11fdf7f2 TL |
66 | SnapshotImpl* New(SnapshotImpl* s, SequenceNumber seq, uint64_t unix_time, |
67 | bool is_write_conflict_boundary) { | |
7c673cae FG |
68 | s->number_ = seq; |
69 | s->unix_time_ = unix_time; | |
70 | s->is_write_conflict_boundary_ = is_write_conflict_boundary; | |
71 | s->list_ = this; | |
72 | s->next_ = &list_; | |
73 | s->prev_ = list_.prev_; | |
74 | s->prev_->next_ = s; | |
75 | s->next_->prev_ = s; | |
76 | count_++; | |
77 | return s; | |
78 | } | |
79 | ||
80 | // Do not responsible to free the object. | |
81 | void Delete(const SnapshotImpl* s) { | |
82 | assert(s->list_ == this); | |
83 | s->prev_->next_ = s->next_; | |
84 | s->next_->prev_ = s->prev_; | |
85 | count_--; | |
86 | } | |
87 | ||
11fdf7f2 | 88 | // retrieve all snapshot numbers up until max_seq. They are sorted in |
494da23a | 89 | // ascending order (with no duplicates). |
7c673cae | 90 | std::vector<SequenceNumber> GetAll( |
11fdf7f2 TL |
91 | SequenceNumber* oldest_write_conflict_snapshot = nullptr, |
92 | const SequenceNumber& max_seq = kMaxSequenceNumber) const { | |
7c673cae | 93 | std::vector<SequenceNumber> ret; |
f67539c2 TL |
94 | GetAll(&ret, oldest_write_conflict_snapshot, max_seq); |
95 | return ret; | |
96 | } | |
97 | ||
98 | void GetAll(std::vector<SequenceNumber>* snap_vector, | |
99 | SequenceNumber* oldest_write_conflict_snapshot = nullptr, | |
100 | const SequenceNumber& max_seq = kMaxSequenceNumber) const { | |
101 | std::vector<SequenceNumber>& ret = *snap_vector; | |
102 | // So far we have no use case that would pass a non-empty vector | |
103 | assert(ret.size() == 0); | |
7c673cae FG |
104 | |
105 | if (oldest_write_conflict_snapshot != nullptr) { | |
106 | *oldest_write_conflict_snapshot = kMaxSequenceNumber; | |
107 | } | |
108 | ||
109 | if (empty()) { | |
f67539c2 | 110 | return; |
7c673cae | 111 | } |
11fdf7f2 | 112 | const SnapshotImpl* s = &list_; |
7c673cae | 113 | while (s->next_ != &list_) { |
11fdf7f2 TL |
114 | if (s->next_->number_ > max_seq) { |
115 | break; | |
116 | } | |
494da23a TL |
117 | // Avoid duplicates |
118 | if (ret.empty() || ret.back() != s->next_->number_) { | |
119 | ret.push_back(s->next_->number_); | |
120 | } | |
7c673cae FG |
121 | |
122 | if (oldest_write_conflict_snapshot != nullptr && | |
123 | *oldest_write_conflict_snapshot == kMaxSequenceNumber && | |
124 | s->next_->is_write_conflict_boundary_) { | |
125 | // If this is the first write-conflict boundary snapshot in the list, | |
126 | // it is the oldest | |
127 | *oldest_write_conflict_snapshot = s->next_->number_; | |
128 | } | |
129 | ||
130 | s = s->next_; | |
131 | } | |
f67539c2 | 132 | return; |
7c673cae FG |
133 | } |
134 | ||
135 | // get the sequence number of the most recent snapshot | |
136 | SequenceNumber GetNewest() { | |
137 | if (empty()) { | |
138 | return 0; | |
139 | } | |
140 | return newest()->number_; | |
141 | } | |
142 | ||
143 | int64_t GetOldestSnapshotTime() const { | |
144 | if (empty()) { | |
145 | return 0; | |
146 | } else { | |
147 | return oldest()->unix_time_; | |
148 | } | |
149 | } | |
150 | ||
f67539c2 TL |
151 | int64_t GetOldestSnapshotSequence() const { |
152 | if (empty()) { | |
153 | return 0; | |
154 | } else { | |
155 | return oldest()->GetSequenceNumber(); | |
156 | } | |
157 | } | |
158 | ||
7c673cae FG |
159 | uint64_t count() const { return count_; } |
160 | ||
161 | private: | |
162 | // Dummy head of doubly-linked list of snapshots | |
163 | SnapshotImpl list_; | |
164 | uint64_t count_; | |
165 | }; | |
166 | ||
f67539c2 | 167 | } // namespace ROCKSDB_NAMESPACE |