这个项目大概是 1月 19 号时完成的了，但是一直没有时间好好梳理一遍，拖到了年后了。

虽然是 Project 0，但是如果对 C++ 的一些新语法不熟悉的话，还是会有点难受的。这里只是简单的记录过程和一些实现时的想法，不会公开所有源码。

Task 1 - Template Trie

这个任务主要实现三个类，TrieNode，TrieNodeWithValue 和 Trie。

TrieNode 是节点基类，它的实现就比较简单，只需要按照注释写就行，没有很复杂。这个基类存储了 TireNode 中的key_char，is_end和子节点指针children。并主要维护这三个成员的相关函数。

TrieNodeWithValue 这是继承了TireNode的==模板类==，首先它既是TireNode的子类，所以它的指针可以存储在TireNode的子节点指针map中，与普通的TireNode链接在一起。同时它又是一个模板类，模板参数是存储的Value的类型，因此通过特化TireNodeWithValue可以将不同类型的值存储在该节点中。

同时代码里还约定了，TireNodeWithValue的is_end为true，而不包含值的is_end为false，这样在运行期也可以方便的判断是否为EndNode。

Tire 是这个 Task 的主要难点，几乎所有代码量都在这个类中了，它主要包含以下几个接口Insert<T>(key, value)，Remove(key)和GetValue<T>(key)。

首先是Insert<T>(key, value)，这里需要遍历key中所有字符，然后逐步沿着树进行查找或者插入操作。这里为了方便实现，所以在查找中进行插入时直接TireNode插入到树中，没有对最后一个字符进行特殊处理（最后一个字符需要插入的是TireNodeWithValue），而是在完成遍历后，再将最后一个节点转换为TireNodeWithValue。这里给出代码实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

template <typename T>
bool Insert(const std::string &key, T value) {
  if (key.empty()) {
    return false;
  }
  TrieNode *parent = nullptr;
  TrieNode *node = root_.get();
  for (char key_char : key) {
    parent = node;
    if (node->HasChild(key_char)) {
      node = node->GetChildNode(key_char)->get();
    } else {
      std::unique_ptr<TrieNode> child = std::make_unique<TrieNode>(key_char);
      auto child_ptr = node->InsertChildNode(key_char, std::move(child));
      if (child_ptr == nullptr) {
        return false;
      }
      node = child_ptr->get();
    }
  }

  // node is the last node of the key
  // 1. node is end node, return false
  if (node->IsEndNode()) {
    return false;
  }

  // 2. node is not end node, convert it to end node
  auto child_with_value = std::make_unique<TrieNodeWithValue<T>>(std::move(*node), value);
  parent->RemoveChildNode(key.back());
  parent->InsertChildNode(key.back(), std::move(child_with_value));
  return true;
}

然后是Remove(key)接口，这个接口应该是最复杂的一个接口了。它先需要和Insert一样进行一次查找操作，不同的是这里需要用栈存储住所有遍历过的节点，然后再尝试移除最后一个节点，如果最后一个节点没有子节点，就直接删除该节点，如果有则需要把该节点转换为TireNode。最后再从栈中不停pop节点出来，看当前节点是否为 EndNode 或者存在子节点，如果是就直接退出即可，否则就需要删除该节点，并继续从栈中 pop 节点。

最后是GetValue这个接口，这个就比较简单了，只需要按key的字符不断在Tire中进行查找即可，最好再将TireNode转换为TireNodeWithValue再取值即可。这里还学到了一个技巧：dynamic_cast转换失败时返回的是nullptr。

Task 2 - Concurrent Tire

让Tire支持并发，只需要在Tire三个接口上获取对应的锁并在退出时释放即可，这个只需要注意一下别因为没有释放锁导致死锁的情况即可。

Testing

文档已经写得比较全面了，但是在MacOS上似乎还有点问题，因为默认安装了 clang@14，所以得修改一下CMakeLists.txt：

1
2

set(BUSTUB_CLANG_SEARCH_PATH "/usr/local/bin" "/usr/bin" "/usr/local/opt/llvm/bin" "/usr/local/opt/llvm@14/bin"
        "/usr/local/Cellar/llvm/12.0.1/bin" "/opt/homebrew/opt/llvm@12/bin/")

![[CMU15445-Project0-test.png]]