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
11namespace leveldb {
12
13class SnapshotList;
14
15// Snapshots are kept in a doubly-linked list in the DB.
16// Each SnapshotImpl corresponds to a particular sequence number.
17class SnapshotImpl : public Snapshot {
18 public:
19 SnapshotImpl(SequenceNumber sequence_number)
20 : sequence_number_(sequence_number) {}
21
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 directly.
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
39class SnapshotList {
40 public:
41 SnapshotList() : head_(0) {
42 head_.prev_ = &head_;
43 head_.next_ = &head_;
44 }
45
46 bool empty() const { return head_.next_ == &head_; }
47 SnapshotImpl* oldest() const {
48 assert(!empty());
49 return head_.next_;
50 }
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.
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.
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