// 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.

#ifndef STORAGE_LEVELDB_DB_SNAPSHOT_H_

#define STORAGE_LEVELDB_DB_SNAPSHOT_H_

#include "db/dbformat.h"

#include "leveldb/db.h"

namespace leveldb {

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:

  SnapshotImpl(SequenceNumber sequence_number)

      : sequence_number_(sequence_number) {}

  SequenceNumber sequence_number() const { return sequence_number_; }

 private:

  friend class SnapshotList;

  // SnapshotImpl is kept in a doubly-linked circular list. The SnapshotList

  // implementation operates on the next/previous fields direcly.

  SnapshotImpl* prev_;

  SnapshotImpl* next_;

  const SequenceNumber sequence_number_;

#if !defined(NDEBUG)

  SnapshotList* list_ = nullptr;

#endif  // !defined(NDEBUG)

};

class SnapshotList {

 public:

  SnapshotList() : head_(0) {

    head_.prev_ = &head_;

    head_.next_ = &head_;

  }

  bool empty() const { return head_.next_ == &head_; }

  SnapshotImpl* oldest() const {

    assert(!empty());

    return head_.next_;

  }

  SnapshotImpl* newest() const {

    assert(!empty());

    return head_.prev_;

  }

  // Creates a SnapshotImpl and appends it to the end of the list.

  SnapshotImpl* New(SequenceNumber sequence_number) {

    assert(empty() || newest()->sequence_number_ <= sequence_number);

    SnapshotImpl* snapshot = new SnapshotImpl(sequence_number);

#if !defined(NDEBUG)

    snapshot->list_ = this;

#endif  // !defined(NDEBUG)

    snapshot->next_ = &head_;

    snapshot->prev_ = head_.prev_;

    snapshot->prev_->next_ = snapshot;

    snapshot->next_->prev_ = snapshot;

    return snapshot;

  }

  // Removes a SnapshotImpl from this list.

  //

  // The snapshot must have been created by calling New() on this list.

  //

  // The snapshot pointer should not be const, because its memory is

  // deallocated. However, that would force us to change DB::ReleaseSnapshot(),

  // which is in the API, and currently takes a const Snapshot.

  void Delete(const SnapshotImpl* snapshot) {

#if !defined(NDEBUG)

    assert(snapshot->list_ == this);

#endif  // !defined(NDEBUG)

    snapshot->prev_->next_ = snapshot->next_;

    snapshot->next_->prev_ = snapshot->prev_;

    delete snapshot;

  }

 private:

  // Dummy head of doubly-linked list of snapshots

  SnapshotImpl head_;

};

}  // namespace leveldb

#endif  // STORAGE_LEVELDB_DB_SNAPSHOT_H_