Code & Func

💡 这个项目大概是 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
template <typename T>
2
bool Insert(const std::string &key, T value) {
3
  if (key.empty()) {
4
    return false;
5
  }
6
  TrieNode *parent = nullptr;
7
  TrieNode *node = root_.get();
8
  for (char key_char : key) {
9
    parent = node;
10
    if (node->HasChild(key_char)) {
11
      node = node->GetChildNode(key_char)->get();
12
    } else {
13
      std::unique_ptr<TrieNode> child = std::make_unique<TrieNode>(key_char);
14
      auto child_ptr = node->InsertChildNode(key_char, std::move(child));
15
      if (child_ptr == nullptr) {
18 collapsed lines
16
        return false;
17
      }
18
      node = child_ptr->get();
19
    }
20
  }
21

22
  // node is the last node of the key
23
  // 1. node is end node, return false
24
  if (node->IsEndNode()) {
25
    return false;
26
  }
27

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

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

1
bool Remove(const std::string &key) {
2
  if (key.empty()) {
3
    return false;
4
  }
5
  std::stack<TrieNode *> node_stack;
6
  TrieNode *node = root_.get();
7
  latch_.RLock();
8
  for (char key_char : key) {
9
    node_stack.push(node);
10
    if (node->HasChild(key_char)) {
11
      node = node->GetChildNode(key_char)->get();
12
    } else {
13
      latch_.RUnlock();
14
      return false;
15
    }
38 collapsed lines
16
  }
17

18
  // node is not end node, return false
19
  if (!node->IsEndNode()) {
20
    latch_.RUnlock();
21
    return false;
22
  }
23
  auto key_char_iter = key.rbegin();
24
  TrieNode *parent = node_stack.top();
25
  node_stack.pop();
26
  latch_.RUnlock();
27
  latch_.WLock();
28
  // remove end node
29
  if (node->HasChildren()) {
30
    // convert node to non-end node
31
    auto new_node = std::make_unique<TrieNode>(std::move(*node));
32
    parent->RemoveChildNode(*key_char_iter);
33
    parent->InsertChildNode(*key_char_iter, std::move(new_node));
34
  } else {
35
    parent->RemoveChildNode(*key_char_iter);
36
  }
37
  node = parent;
38
  ++key_char_iter;
39

40
  // Recursively remove nodes that have no children and are not terminal node
41
  while (!node_stack.empty()) {
42
    parent = node_stack.top();
43
    node_stack.pop();
44
    if (node->IsEndNode() || node->HasChildren()) {
45
      break;
46
    }
47
    parent->RemoveChildNode(*key_char_iter);
48
    node = parent;
49
    ++key_char_iter;
50
  }
51
  latch_.WUnlock();
52
  return true;
53
}

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

1
template <typename T>
2
T GetValue(const std::string &key, bool *success) {
3
  *success = false;
4
  if (key.empty()) {
5
    return T();
6
  }
7
  latch_.RLock();
8
  auto node = root_.get();
9
  for (char key_char : key) {
10
    if (node->HasChild(key_char)) {
11
      node = node->GetChildNode(key_char)->get();
12
    } else {
13
      latch_.RUnlock();
14
      return T();
15
    }
18 collapsed lines
16
  }
17

18
  if (!node->IsEndNode()) {
19
    latch_.RUnlock();
20
    return T();
21
  }
22

23
  auto node_with_value = dynamic_cast<TrieNodeWithValue<T> *>(node);
24
  if (node_with_value == nullptr) {
25
    latch_.RUnlock();
26
    return T();
27
  }
28

29
  *success = true;
30
  auto value = node_with_value->GetValue();
31
  latch_.RUnlock();
32
  return value;
33
}

Task 2 - Concurrent Tire

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

Testing

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

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

CMU15-445 Project0 Cpp Primer

Task 1 - Template Trie

Task 2 - Concurrent Tire

Testing