CMU 15-445 Project 0 实现字典树

本文对应 2022 年的课程，Project 0 已经更新为实现字典树了。C++17 的开发环境建议直接下载 CLion，不建议自己瞎折腾。

测试

$ mkdir build && cd build
$ cmake -DCMAKE_BUILD_TYPE=DEBUG ..
$ make starter_trie_test 
$ ./test/starter_trie_test
复制代码

运行上面的指令，你会得到如下输出，这不表示该项目的 5 个测试用例没过，而是没有执行。

[==========] Running 0 tests from 0 test suites.
[==========] 0 tests from 0 test suites ran. (0 ms total)
[ PASSED ] 0 tests.
 
YOU HAVE 5 DISABLED TESTS
复制代码

需要修改 test/primer/starter_trie_test.cpp 文件，移除测试名 DISABLED_ 前缀。

// TEST(StarterTest, DISABLED_TrieNodeInsertTest)
TEST(StarterTest, TrieNodeInsertTest)
复制代码

格式化

$ make format 
$ make check-lint 
$ make check-clang-tidy-p0
复制代码

调试日志

LOG_INFO("# Pages: %d", num_pages);
LOG_DEBUG("Fetching page %d", page_id);
复制代码

项目介绍

使用支持并发的字典树实现一个键值存储，字典树是一种高效的排序树，用于检索指定键值。这里假设键都是非空的可变长度字符串，但事实上键可以是任意类型。

上图所示字典树中存储了：HAT、HAVE、HELLO 三个键。

上图所示字典树存储了：ab=1、ac="val" 两组键值。

项目实现

只需要修改一个文件：src/include/primer/p0_trie.h

项目已经定义好了类和成员变量，以及需要实现的成员函数的签名，可以添加辅助变量或函数，但不能修改已有变量和函数签名。

任务一

文件中定义了 Trie、TrieNode、TrieNodeWithValue 三个类，建议先实现单线程版本，再改并发版本，类中的成员变量和成员函数都有注释。

任务二

实现并发安全的字典树，可以使用 BusTub 的 RwLatch 或 C++ 的 std::shared_mutex。

一些 C++ 的基操

一年多没写 C++ 了，用惯了 Go，突然用 C++ 写的脑壳疼，没用过 C++ 的小伙伴可能想编译通过都费劲，这里贴一下需要了解的 C++ 特性。

移动语义

std::unique_ptr 表示唯一的指向类型为 T 的对象的指针，因此需要使用移动语义 std::move，代码中 children_ 的类型嵌套了 std::unique_ptr，也需要使用移动语义。

TrieNode(TrieNode &&other_trie_node) noexcept {
    key_char_ = other_trie_node.key_char_;
    is_end_ = other_trie_node.is_end_;
    children_ = std::move(other_trie_node.children_);
}
复制代码

构造父类

TrieNodeWithValue 是 TrieNode 的子类，构造子类时，如果没有手动在子类的构造函数中构造父类，就会调用父类的默认构造函数，而代码中父类是没有默认构造函数的，所以需要手动在子类中构造父类。

需要使用 std::forward 转发右值引用。

TrieNodeWithValue(TrieNode &&trieNode, T value) : TrieNode(std::forward<TrieNode>(trieNode)) {
    this->value_ = value;
    this->is_end_ = true;
}
复制代码

父子指针转换

TrieNodeWithValue 是模板类，没法办使用多态，Trie::GetValue 需要将 unique_ptr 转换为 TrieNodeWithValue* 后调用 TrieNodeWithValue::GetValue。

std::unique_ptr<TrieNode> uptr = std::make_unique<TrieNodeWithValue<T>>('a', T());
dynamic_cast<TrieNodeWithValue<T>*>(&(*uptr))->GetValue();
复制代码

可能有更优雅的办法，但我实在是想不出来了，C++ 可真难写啊。

所有权规避

std::unique_ptr 的传递一定是使用移动语义转移 T 对象地址的所有权，但也可以不获取所有权访问 T 对象的地址，代码里的注释也引导我们使用这种方式。

std::unique_ptr<int> uptr(new int(1));
std::cout << *uptr << std::endl; // 1
 
auto *p = &uptr;
*(*p) = 2;
std::cout << *uptr << std::endl; // 2
复制代码

代码实现

大部分代码按照注释一步一步来就没问题，课程规定不公开代码，所以这里只列一些难点。

循环迭代

这里给出一个模版，对于尾节点和非尾节点，一般需要不同的操作。

auto curr = &root_;
size_t i = 0;
 
while (i + 1 < key.size()) {
    curr = (*curr)->GetChildNode(key[i]);
    i++;
}
// end_node
curr = (*curr)->GetChildNode(key[i]);
复制代码

节点转换

在插入流程中，当迭代到最后一个字符时，发现已经有了一个 TrieNode 类型的节点，需要转换为 TrieNodeWithValue 类型。

* When you reach the ending character of a key:
* 2. If the terminal node is a TrieNode, then convert it into TrieNodeWithValue by
* invoking the appropriate constructor.
复制代码

不熟悉 C++ 的话这个操作可能有点困难，这里给出代码，这一层又一层的括号和解引用确实不够优雅，但一时间也想不到其他好办法。

(*curr) = std::make_unique<TrieNodeWithValue<T>>(std::move(*(*curr)), value);
复制代码

节点删除

根据代码注释的提示，Remove 函数是要递归删除的，这里给出递归的框架。

bool remove_inner(const std::string &key, size_t i, std::unique_ptr<TrieNode> *curr, bool *success) {
  if (i == key.size()) {
    *success = true; // Remove 的返回值，表示成功删除
    (*curr)->SetEndNode(false);
    return !(*curr)->HasChildren() && !(*curr)->IsEndNode();
  }
 
  bool can_remove = remove_inner(key, i + 1, (*curr)->GetChildNode(key[i]), success);
 
  if (can_remove) {
    (*curr)->RemoveChildNode(key[i]);
  }
  return !(*curr)->HasChildren() && !(*curr)->IsEndNode();
}
复制代码

remove_innner 的返回值表示传入节点是否可以删除，可以删除的条件是该节点无子节点且非尾节点。函数内判断当前节点的子节点是否可以删除，并返回当前节点是否可以删除。出口是递归到了传入 key 的尾节点，取消尾节点标记，并返回是否可以删除。该函数调用前还需要判断一下 key 是否存在。

空模板变量值

GetValue 的返回值是一个模板类型，错误的时候直接 return T()，正常情况下，需要转换 TrieNode 为 TrieNodeWithValue 中获取值，上文提过该父子类转换的办法。

template <typename T>
T GetValue(const std::string &key, bool *success) {
    return T();
    return dynamic_cast<TrieNodeWithValue<T> *>(&(*(*curr)))->GetValue();
}
复制代码

并发安全

这个其实很简单，前 4 个测试都通过了，Insert、Remove、GetValue 三个函数开始和结束位置加锁和解锁就可以了，需要注意的是这三个函数如果彼此调用会死锁，比如 Insert 里面调用 GetValue 判断 key 是否存在。

这里提供一个 Go 语言中 defer 解锁的简易实现，如果你不知道 defer 就在每个返回的地方都解锁就可以。

class RLock {
  ReaderWriterLatch *latch_;
 
 public:
  RLock(ReaderWriterLatch *latch) : latch_(latch) { latch_->RLock(); }
  ~RLock() { latch_->RUnlock(); }
};
 
class WLock {
  ReaderWriterLatch *latch_;
 
 public:
  WLock(ReaderWriterLatch *latch) : latch_(latch) { latch_->WLock(); }
  ~WLock() { latch_->WUnlock(); }
};
复制代码

使用方式如下，以 Remove 为例。

bool Remove(const std::string &key) {
  WLock w(&latch_);
 
  if (!Exist(key)) {
    return false;
  }
  bool success = false;
  remove_inner(key, 0, &root_, &success);
  return success;
}
复制代码

写在最后

动手开始项目前，可以先去 leetcode 过一遍 实现 Trie (前缀树)先能写出简单的字典树再动手。如果需要代码的话可以私信我。如果想做数据库的工作欢迎找我内推（恰点内推奖金）。