实验说明

实验主页https://15445.courses.cs.cmu.edu/spring2023/project0/
本次Proj主要完成copy-on-write trie前缀树
C++17

structure

Task #1 - Copy-On-Write Trie

Task 1要求完成一个copy-on-write前缀树，需要学习一下相关C++17的语法以及智能指针的使用，学习完成后此任务难度不高。

Get

Get函数主要是根据给定的key来查找是否有对应的value并返回，此部分不涉及copy-on-write。

设置一个std::shared_ptr node = 根节点
遍历key的每一个字符c，如果可以从node的children中找到对应的child，那么令node = next_node，否则返回nullptr
遍历至最后一个节点，判断是否是value节点，使用dynamic_cast<const TrieNodeWithValue
*>进行强制的类型转换获取value并返回
- dynamic_cast 只适用于指针和引用类型，不能用于普通对象
- dynamic_cast 在转换时，源类型必须至少含有一个虚函数，以确保运行时类型信息的存在
- dynamic_cast 的转换只能在具有多态关系的类层次结构中进行

Put

Put函数主要是将对应的key和value插入到前缀树中，在向下遍历的过程中，遇到已有的节点需要Clone一份新的节点。

需要三个新的变量new_root和前后指针parent和child
- std::shared_ptr new_root = this->root_ ? this->root_->Clone() : std::make_shared(); 因为是从根节点开始向下遍历，如果根节点存在的话也需要Clone一份，不存在的话就新建。
- 这里向下遍历用到了前后指针的技巧parent和child，初始parent指向nullptr，child指向new_root
通过遍历key的字符c向下遍历整个前缀树，如果当前parent的对应的孩子节点不为空，就需要copy(Clone)后赋值给child，并更新parent的children，然后令parent=child并继续下一轮迭代
遍历到最终字符时使用std::make_shared<TrieNodeWithValue
>(child->children_,std::make_shared
(std::move(value)));给最终的child赋值
- 该代码作用是创建一个TrieNodeWithValue类型的指针，括号内是初始化TrieNodeWithValue的构造函数的参数列表，其中需要传入child->children_因为当前节点可能不是叶子节点，需要把它的孩子节点拷贝进来
将最后更新的child节点更新到parent的children中，返回new_root构建的Trie即可(return Trie(new_root))

Remove

Remove操作也需要用到copy-on-write思想，不能在原来的树上直接进行操作，考虑到如果当前节点是叶子节点，删除后他的parent的children为空，这时parent也需要删除，继续向上迭代，这种方式很容易联想到使用stack来回溯解决。

初始化和Put中相同的三个变量，多加一个stack<std::pair<std::shared_ptr, char>> stk，用来保存访问过的node，便于回溯
遍历key的字符c，遍历的过程中copy-on-write，并将遍历过的node加入到stack中
- 如果找到空节点，说明要删除的节点根本不存在，直接return nullptr
找到了需要删除的节点
- 如果该节点没有孩子，直接将该节点置空
- 如果该节点有孩子，通过child = make_shared(nxt->children_)删除掉value
开始回溯
- 不断的获取栈顶元素parent，如果child==nullptr，erase掉parent的children中的对应元素，如果此时parent为空，则也将parent置空，令child=parent
- 重复上述过程，直到stack空为止

Task #2 - Concurrent Key-Value Store

Task 2需要学习一下C++中mutex的使用，难度属于简单，lab设置为多个读者和一个写者。

Get

首先lock root并获取当前的root，随即释放掉lock，不要直接在持有锁的情况下遍历前缀树来获取value，这样会非常影响性能
用刚才获取的root调用Get方法并返回即可，

Put

写者在Put过程中需要一直持有write_lock避免其他线程对临界区的访问
获取root的方式和Get相同，然后对root调用Put方法即可

Remove

流程和Put相同，只是调用的方法不同

Task #3 - Debugging

配置vscode debug文件完成，具体参照https://www.youtube.com/watch?v=G9gnSGKYIg4。

build项目，make trie_debug_test -j$(nproc)
将trie_debug_test配置到vscode的debug文件中
F5断点观察结果即可

个人配置文件如下所示

{
    // Use IntelliSense to learn about possible attributes.
    // Hover to view descriptions of existing attributes.
    // For more information, visit: https://go.microsoft.com/fwlink/?linkid=830387
    "version": "0.2.0",
    "configurations": [
        {
            "type": "lldb",
            "request": "launch",
            "name": "Debug",
            "program": "${workspaceFolder}/lab/build/test/trie_debug_test",
            "args": [],
            "cwd": "${workspaceFolder}"
        }
    ]
}