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 #ifndef STORAGE_LEVELDB_DB_SNAPSHOT_H_ 6 #define STORAGE_LEVELDB_DB_SNAPSHOT_H_ 7 8 #include "db/dbformat.h" 9 #include "leveldb/db.h" 10 11 namespace leveldb { 12 13 class SnapshotList; 14 15 // Snapshots are kept in a doubly-linked list in the DB. 16 // Each SnapshotImpl corresponds to a particular sequence number. 17 class SnapshotImpl : public Snapshot { 18 public: SnapshotImpl(SequenceNumber sequence_number)19 SnapshotImpl(SequenceNumber sequence_number) 20 : sequence_number_(sequence_number) {} 21 sequence_number()22 SequenceNumber sequence_number() const { return sequence_number_; } 23 24 private: 25 friend class SnapshotList; 26 27 // SnapshotImpl is kept in a doubly-linked circular list. The SnapshotList 28 // implementation operates on the next/previous fields direcly. 29 SnapshotImpl* prev_; 30 SnapshotImpl* next_; 31 32 const SequenceNumber sequence_number_; 33 34 #if !defined(NDEBUG) 35 SnapshotList* list_ = nullptr; 36 #endif // !defined(NDEBUG) 37 }; 38 39 class SnapshotList { 40 public: SnapshotList()41 SnapshotList() : head_(0) { 42 head_.prev_ = &head_; 43 head_.next_ = &head_; 44 } 45 empty()46 bool empty() const { return head_.next_ == &head_; } oldest()47 SnapshotImpl* oldest() const { 48 assert(!empty()); 49 return head_.next_; 50 } newest()51 SnapshotImpl* newest() const { 52 assert(!empty()); 53 return head_.prev_; 54 } 55 56 // Creates a SnapshotImpl and appends it to the end of the list. New(SequenceNumber sequence_number)57 SnapshotImpl* New(SequenceNumber sequence_number) { 58 assert(empty() || newest()->sequence_number_ <= sequence_number); 59 60 SnapshotImpl* snapshot = new SnapshotImpl(sequence_number); 61 62 #if !defined(NDEBUG) 63 snapshot->list_ = this; 64 #endif // !defined(NDEBUG) 65 snapshot->next_ = &head_; 66 snapshot->prev_ = head_.prev_; 67 snapshot->prev_->next_ = snapshot; 68 snapshot->next_->prev_ = snapshot; 69 return snapshot; 70 } 71 72 // Removes a SnapshotImpl from this list. 73 // 74 // The snapshot must have been created by calling New() on this list. 75 // 76 // The snapshot pointer should not be const, because its memory is 77 // deallocated. However, that would force us to change DB::ReleaseSnapshot(), 78 // which is in the API, and currently takes a const Snapshot. Delete(const SnapshotImpl * snapshot)79 void Delete(const SnapshotImpl* snapshot) { 80 #if !defined(NDEBUG) 81 assert(snapshot->list_ == this); 82 #endif // !defined(NDEBUG) 83 snapshot->prev_->next_ = snapshot->next_; 84 snapshot->next_->prev_ = snapshot->prev_; 85 delete snapshot; 86 } 87 88 private: 89 // Dummy head of doubly-linked list of snapshots 90 SnapshotImpl head_; 91 }; 92 93 } // namespace leveldb 94 95 #endif // STORAGE_LEVELDB_DB_SNAPSHOT_H_ 96