CMU 15-445 Database Systems Project #0 - C++ Primer

在线测试需要使用 Gradescope，使用课程提供的课程码 PXWVR5，学校填 Carnegie Mellon University，Student ID 不需要。

Project #0 - C++ Primer

既然这门课用的 C++，那么就需要考察学生的 C++ 水平。CMU 15-445 的要求：C++17, GDB。

鉴于课程使用的工具，最好在 Linux 下做此课程实验。

首先需要 clone 一份 CMU 的 bustub（需要去 Release 手动下载 Fall2022 版本，或者手动 reset 到对应的 commit d830931a9b2aca66c0589de67b5d7a5fd2c87a79，否则内容对应不上）。

Task #1 - Templated Trie

在原有模板上实现一颗 Trie 树。

没什么好说的，只要知道 Trie 树是个什么东西就行了，直接模拟，总共就几十行代码。

在写的时候可能遇到的主要问题：不会用智能指针等现代 C++ 内容，只能边查边写，多用用就会了。

（不过我一直感觉 C++ 的智能指针用着怪难受的，Rust 写着就挺舒服）

似乎在 C++17 后 Clang 会提示将函数写为类型后置的形式，虽然感觉完全没必要。。

int func() {} → auto func() -> int {}

Task #2 - Concurrent Trie

在 Task #1 的基础上通过加锁实现并发。

因为项目本身已经提供了一个 RWLatch (std::shared_mutex)，可以直接用。

具体实现只需要在函数开始的时候获取锁，离开时释放即可。因为读操作可以同时进行，需要注意不同操作是使用 .RLock() 还是 .WLock()。

---

写完之后测试发现，这个 OJ 提示信息基本等于没有，基本没法调试，于是可能会用到提供的本地测试，注意需要把相应测试的 TEST(StarterTest, DISABLED_xxx) 改成 TEST(StarterTest, xxx)，否则会忽略掉

测试的时候发现有大量的内存泄露，发现是智能指针使用不当造成的

其中有一段如下的代码：

*position = std::make_unique<TrieNode>(std::move(*position->release()));

其中 position 是一个 std::unique_ptr<TrieNode>，因为 release() 后没有释放对应指针的值，于是造成内存泄露。需要改成：

auto ptr = position->release();
*position = std::make_unique<TrieNode>(std::move(*ptr));
delete ptr;

另外自己在 DEBUG 的时候犯了个蠢，子类需要重载析构函数，否则也会内存泄漏（这不废话）

最终代码

// @MizukiCry
#pragma once

#include <memory>
#include <stack>
#include <stdexcept>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>

#include "common/exception.h"
#include "common/rwlatch.h"

namespace bustub {
class TrieNode {
 public:

  explicit TrieNode(char key_char) : key_char_(key_char) {}

  TrieNode(TrieNode &&other_trie_node) noexcept
      : key_char_(other_trie_node.key_char_),
        children_(std::move(other_trie_node.children_)) {}

  auto HasChild(char key_char) const -> bool { return children_.count(key_char) != 0; }

  auto HasChildren() const -> bool { return !children_.empty(); }

  auto IsEndNode() const -> bool { return is_end_; }


  auto GetKeyChar() const -> char { return key_char_; }

  auto InsertChildNode(char key_char, std::unique_ptr<TrieNode> &&child) -> std::unique_ptr<TrieNode> * {
    if (HasChild(key_char) || child->GetKeyChar() != key_char) {
      return nullptr;
    }
    return &(children_[key_char] = std::move(child));
  }

  auto GetChildNode(char key_char) -> std::unique_ptr<TrieNode> * {
    if (!HasChild(key_char)) {
      return nullptr;
    }
    return &children_[key_char];
  }

  void RemoveChildNode(char key_char) { children_.erase(key_char); }

  void SetEndNode(bool is_end) { is_end_ = is_end; }

 protected:
  char key_char_;
  bool is_end_{false};
  std::unordered_map<char, std::unique_ptr<TrieNode>> children_;
};

template <typename T>
class TrieNodeWithValue : public TrieNode {
 private:
  T value_;

 public:

  TrieNodeWithValue(TrieNode &&trieNode, T value) : TrieNode(std::move(trieNode)), value_(value) { SetEndNode(true); }

  TrieNodeWithValue(char key_char, T value) : TrieNode(key_char), value_(value) { SetEndNode(true); }

  ~TrieNodeWithValue() override = default;

  auto GetValue() const -> T { return value_; }
};

class Trie {
 private:
  std::unique_ptr<TrieNode> root_;
  ReaderWriterLatch latch_;

 public:
  Trie() { root_ = std::make_unique<TrieNode>('\0'); }

  template <typename T>
  auto Insert(const std::string &key, T value) -> bool {
    if (key.empty()) {
      return false;
    }
    latch_.WLock();
    auto position = &root_;
    for (const auto c : key) {
      if (!position->get()->HasChild(c)) {
        position->get()->InsertChildNode(c, std::make_unique<TrieNode>(c));
      }
      position = position->get()->GetChildNode(c);
    }
    if (position->get()->IsEndNode()) {
      latch_.WUnlock();
      return false;
    }
    if (dynamic_cast<TrieNodeWithValue<T> *>(position->get()) == nullptr) {
      auto ptr = position->release();
      *position = std::make_unique<TrieNodeWithValue<T>>(std::move(*ptr), value);
      delete ptr;
    }
    latch_.WUnlock();
    return true;
  }

  auto Remove(const std::string &key) -> bool {
    if (key.empty()) {
      return false;
    }
    latch_.WLock();
    auto position = &root_;
    std::stack<std::unique_ptr<TrieNode> *> trace;
    trace.push(position);
    for (const auto c : key) {
      if (!position->get()->HasChild(c)) {
        latch_.WUnlock();
        return false;
      }
      position = position->get()->GetChildNode(c);
      trace.push(position);
    }
    if (!position->get()->IsEndNode()) {
      latch_.WUnlock();
      return false;
    }
    auto ptr = position->release();
    *position = std::make_unique<TrieNode>(std::move(*ptr));
    delete ptr;
    while (trace.size() > 1) {
      auto p = trace.top()->get();
      if (p->HasChildren() || p->IsEndNode()) {
        break;
      }
      auto child_char = p->GetKeyChar();
      trace.pop();
      trace.top()->get()->RemoveChildNode(child_char);
    }
    latch_.WUnlock();
    return true;
  }

  template <typename T>
  auto GetValue(const std::string &key, bool *success) -> T {
    if (key.empty()) {
      *success = false;
      return {};
    }
    latch_.RLock();
    auto position = &root_;
    for (const char c : key) {
      if (!position->get()->HasChild(c)) {
        *success = false;
        latch_.RUnlock();
        return {};
      }
      position = position->get()->GetChildNode(c);
    }
    if (!position->get()->IsEndNode()) {
      *success = false;
      latch_.RUnlock();
      return {};
    }
    TrieNodeWithValue<T> *ptr = dynamic_cast<TrieNodeWithValue<T> *>(position->get());  // NOLINT
    if (!ptr) {
      *success = false;
      latch_.RUnlock();
      return {};
    }
    *success = true;
    latch_.RUnlock();
    return ptr->GetValue();
  }
};
}  // namespace bustub