Untitled

//===----------------------------------------------------------------------===//
//
//                         BusTub
//
// lru_k_replacer.cpp
//
// Identification: src/buffer/lru_k_replacer.cpp
//
// Copyright (c) 2015-2022, Carnegie Mellon University Database Group
//
//===----------------------------------------------------------------------===//

#include "buffer/lru_k_replacer.h"
#include "common/exception.h"

namespace bustub {

LRUKReplacer::LRUKReplacer(size_t num_frames, size_t k) : replacer_size_(num_frames), k_(k) {}

auto LRUKReplacer::Evict(frame_id_t *frame_id) -> bool {
  std::lock_guard<std::mutex> lock(latch_);

  if (curr_size_ == 0) {
    return false;
  }

  // assume the list is sorted
  if (!smaller_than_k_.empty()) {
    for (auto n : smaller_than_k_) {
      if (n->is_evictable_) {
        *frame_id = n->fid_;
        this->MyRemove(n->fid_);
        return true;
      }
    }
  }

  if (!larger_than_k_.empty()) {
    for (auto n : larger_than_k_) {
      if (n->is_evictable_) {
        *frame_id = n->fid_;
        this->MyRemove(n->fid_);
        return true;
      }
    }
  }

  return false;
}

void LRUKReplacer::RecordAccess(frame_id_t frame_id, [[maybe_unused]] AccessType access_type) {
  std::lock_guard<std::mutex> lock(latch_);
  if (frame_id > static_cast<int>(replacer_size_)) {
    throw Exception("frame id is invalid");
  }

  current_timestamp_++;

  if (node_store_.find(frame_id) == node_store_.end()) {  // new frame
    node_store_[frame_id] = LRUKNode();
    node_store_[frame_id].fid_ = frame_id;
  }
  auto &temp = node_store_[frame_id];
  auto original_size = (temp.history_).size();

  if (original_size >= k_) {  // current in larger_than_k, so need to remove
    larger_than_k_.erase(&temp);
    temp.history_.pop_front();
  }

  temp.history_.emplace_back(current_timestamp_);

  if (original_size == k_) {
    larger_than_k_.insert(&temp);
  } else if (original_size == k_ - 1) {
    smaller_than_k_.erase(smaller_iterators_[frame_id]);
    smaller_iterators_.erase(frame_id);
    larger_than_k_.insert(&temp);
  } else if (original_size == 0) {
    smaller_than_k_.push_back(&temp);
    auto it = smaller_than_k_.end();
    --it;
    smaller_iterators_[frame_id] = it;
  }
}

void LRUKReplacer::SetEvictable(frame_id_t frame_id, bool set_evictable) {
  std::lock_guard<std::mutex> lock(latch_);
  if (frame_id > static_cast<int>(replacer_size_)) {
    throw Exception("frame id is invalid");
  }

  if (node_store_.find(frame_id) == node_store_.end()) {
    return;
  }

  if (set_evictable && !node_store_[frame_id].is_evictable_) {
    curr_size_++;
  } else if (!set_evictable && node_store_[frame_id].is_evictable_) {
    curr_size_--;
  }
  node_store_[frame_id].is_evictable_ = set_evictable;
}

void LRUKReplacer::MyRemove(frame_id_t frame_id) {
  auto &temp = node_store_[frame_id];
  if (temp.history_.size() < k_) {
    smaller_than_k_.erase(smaller_iterators_[frame_id]);
    smaller_iterators_.erase(frame_id);
  } else {
    larger_than_k_.erase(&temp);
  }

  node_store_.erase(frame_id);
  curr_size_--;
}

void LRUKReplacer::Remove(frame_id_t frame_id) {
  std::lock_guard<std::mutex> lock(latch_);
  if (node_store_.find(frame_id) == node_store_.end()) {
    return;
  }

  auto &temp = node_store_[frame_id];
  if (!temp.is_evictable_) {
    throw Exception("This frame is not evictable");
  }

  this->MyRemove(frame_id);
}

auto LRUKReplacer::Size() -> size_t {
  std::lock_guard<std::mutex> lock(latch_);
  return curr_size_;
}

}  // namespace bustub