#pragma once
#ifndef READER_WRITER_QUEUE_H
#define READER_WRITER_QUEUE_H
// INSPIRED BY CMU15445 fall2023 watermark
#include <cassert>
#include <unordered_map>
class ReaderWriterQueue {
 public:
  void AddReader(int tid) {
    assert(tid_ts.count(tid) == 0);
    ts_tt[next_timestamp] = {tid, TidType::kRead};
    tid_ts[tid] = next_timestamp;
    next_timestamp++;
  }
  void AddWriter(int tid) {
    assert(tid_ts.count(tid) == 0);
    ts_tt[next_timestamp] = {tid, TidType::kWrite};
    tid_ts[tid] = next_timestamp;
    next_timestamp++;
  }
  void Remove(int tid) {
    auto ts = tid_ts.find(tid);
    if (ts == tid_ts.end()) return;
    assert(ts_tt.count(ts->second) == 1);
    ts_tt.erase(ts->second);
    tid_ts.erase(ts);
  }
  bool ShallBlock(int tid) {
    ResetMinWriteTimestamp();
    ResetMinTimestamp(); // 這兩個(gè)timestamp處理可以合并
    auto iter = tid_ts.find(tid);
    assert(iter != tid_ts.end());
    assert(ts_tt.count(iter->second) == 1);
    auto ts = iter->second;
    auto [_, type] = ts_tt[ts];
    // 如果讀者之前有寫(xiě)者，那么就需要阻塞等待
    if (type == TidType::kRead) return ts > min_write_ts;
    // 如果寫(xiě)者之前有讀者，那么就需要阻塞等待
    if (min_ts < min_write_ts) return true;
    // 如果寫(xiě)者之前有寫(xiě)者，那么就需要阻塞等待
    return ts_tt[min_write_ts].tid != tid;
  }
 private:
  void ResetMinWriteTimestamp() {
    for (; min_write_ts < next_timestamp; min_write_ts++) {
      auto iter = ts_tt.find(min_write_ts);
      if (iter == ts_tt.end()) {
        continue;
      } else if (iter->second.type == TidType::kWrite) {
        break;
      } else { // iter->second.type == TidType::kRead
        continue;
      }
    }
  }
  void ResetMinTimestamp() {
    for (; min_ts < next_timestamp; min_ts++) {
      auto iter = ts_tt.find(min_ts);
      if (iter != ts_tt.end())
        break;
    }
  }
  long next_timestamp = 0;
  long min_write_ts = 0;
  long min_ts = 0;
  struct TidType {
    int tid;
    enum LockType {kRead, kWrite} type;
    bool operator==(const TidType &rhs) const {
      return tid == rhs.tid && type == rhs.type;
    }
  };
  std::unordered_map<long, TidType> ts_tt;
  std::unordered_map<int, long> tid_ts;
};
#endif // READER_WRITER_QUEUE_H

#pragma once
#ifndef SIMPLE_SHARED_MUTEX_H
#define SIMPLE_SHARED_MUTEX_H
#include <condition_variable>
#include <ctime>
#include <cstdio>
#include <mutex>
#include <unistd.h>
#include "reader_writer_queue.h"
class SimpleSharedMutex {
 public:
  void lock() {
    std::unique_lock lock{mtx};
    auto tid = ::gettid();
    queue.AddWriter(tid);
    while (queue.ShallBlock(tid)) cv.wait(lock);
    // printf("lock %d\n", tid);
  }
  void shared_lock() {
    std::unique_lock lock{mtx};
    auto tid = ::gettid();
    queue.AddReader(tid);
    while (queue.ShallBlock(tid)) cv.wait(lock);
    // printf("slock %d\n", tid);
  }
  void unlock() {
    std::unique_lock lock{mtx};
    queue.Remove(::gettid());
    cv.notify_all();
    // printf("ulock %d\n", ::gettid());
  }
  void shared_unlock() {
    std::unique_lock lock{mtx};
    queue.Remove(::gettid());
    cv.notify_all();
    // printf("uslock %d\n", ::gettid());
  }
 private:
  std::mutex mtx;
  ReaderWriterQueue queue;
  std::condition_variable cv;
};
#endif // SIMPLE_SHARED_MUTEX_H