Project #0 - C++ Primer

注意

这是我在做 Project 时的思考，存在错误和不完整的地方，欢迎指正。

有剧透风险，如果你还没有完成 Project #0，强烈建议先尝试自己解决问题。

Task #1 - Copy-On-Write Trie

Trie 中文名为前缀树。同一个节点下的所有子节点拥有相同的前缀。从根节点到某一个节点的路径上的字符连接起来，即为该节点的前缀或键，节点里存储的是键的值，并不是所有的节点都有对应的值。

Trie 的一个常见应用是前缀匹配，比如浏览器搜索栏的自动补全功能。

Copy On Write 即写时复制，是一种延迟策略，当需要修改一个对象时，先将对象复制一份，然后再修改。这样做可以不破坏原有的对象。例如著名的文件系统 Btrfs 就是使用了 COW 策略。

这个任务的难点就是如何做到不破坏原有对象的情况下，实现 Trie 的 PUT/DETELE 操作, 同时尽可能的同用部分节点。

GET

GET 操作不会修改 Trie，按照键遍历，注意判断没找到的情况即可。

PUT

PUT 分为以下几种：

• 新增一个键值对，在中间节点，直接复用原有节点
• 新增一个键值对，在叶子节点，需要新建一个节点，从根节点到新节点的路径上的所有节点都需要复制一份
• 修改一个键值对，中间节点，需要新建一个节点，从根节点到新节点的路径上的所有节点都需要复制一份
• 修改一个键值对，叶子节点，需要新建一个节点，从根节点到新节点的路径上的所有节点都需要复制一份

按照以上思路，实现 PUT 操作，理论上可以做到不破坏原有对象，又能实现复用。

可以看到，大部分情况下，都需要复制一份路径上的所有节点，所以可以偷偷懒，第一种情况也复制一份，这样就可以统一处理了。

即，PUT 操作的时候，先复制一份路径上的所有节点，然后再修改。

过程中还涉及到了 CPP 的智能指针，move 语义，map 的使用，复杂的类型转换等等，做的有点晕。

DELETE

和 Put 一样，为了简化，可以在寻找目标节点过过程中一路复制节点，找到后删除目标节点。

目标节点有两种情况：

• 叶子节点，无子节点，删除后可能造成父节点无子节点，需要一路删除父节点，直到找到一个有子节点/值的节点
• 中间节点，直接改成不带值的节点即可

当然，也可以暂时不删除无用节点，但是这样会造成内存泄漏，即无用节点占用内存，不过我试了下测试检测不出来这种内存泄漏。

Task #2 - Concurrent Key-Value Store

在 Task #1 的基础上，这个比较简单，记得加锁即可。

Task #3 - Debugging

我常用的 Debug 方法是 Vscode + CodeLLDB + Cmake Tools, 写好 launch.json 和 tasks.json 后，基本上就可以直接用了。

launch.json

{
  // 使用 IntelliSense 了解相关属性。
  // 悬停以查看现有属性的描述。
  // 欲了解更多信息，请访问: https://go.microsoft.com/fwlink/?linkid=830387
  "version": "0.2.0",
  "configurations": [
    {
      "type": "lldb",
      "request": "launch",
      "name": "Bustub Shell",
      "program": "${workspaceFolder}/build/bin/bustub-shell",
      "args": [],
      "cwd": "${workspaceFolder}",
      "preLaunchTask": "Build bustub"
    },
    {
      "type": "lldb",
      "request": "launch",
      "name": "Test Debug",
      "program": "${workspaceFolder}/build/test/${fileBasenameNoExtension}",
      "args": [],
      "cwd": "${workspaceFolder}",
      "preLaunchTask": "Build Test"
    }
  ]
}

tasks.json

{
  "version": "2.0.0",
  "tasks": [
    {
      "type": "cmake",
      "label": "Build Test",
      "command": "build",
      "targets": ["build-tests"],
      "group": "build",
      "problemMatcher": [],
      "detail": "Cmake 生成测试"
    },
    {
      "type": "cmake",
      "label": "Build bustub",
      "command": "build",
      "targets": ["all"],
      "group": "build",
      "problemMatcher": [],
      "detail": "Cmake 生成 bustub"
    }
  ]
}

测试使用固定的种子的随机数发生器构造了一个 Trie, 需要依靠 Debug 回答三个问题：

1. 根节点下一共有多少子节点？
2. 有几个子节点前缀包含 '9'？
3. "93" 对应的值是多少？

我想麻烦了，其实只有在插入时打印插入的键和值即可，甚至不需要 Debug。

我最开始想的是 pdb 可以在 debug python 时执行代码，lldb 说不定也可以，查了下似乎使用 expr 命令可以执行代码，试了下报错找不到符号，可能是我姿势不对。

之后又尝试给 Trie 添加一个 GetRoot 函数，返回私有变量 root_，然后通过 dfs 遍历，计算子节点个数和有多少子节点前缀包含 '9'。

写 lambda 递归时可以先用 auto,写完后改为 std::function 即可

这个任务卡了我好久，交了好几次都不对，一度怀疑是不是理解错题目了，直到看 Discord 里有人说可能因为机器不同导致随机数不同，所有需要做些更改：

// In case your environment is producing different set of random numbers than our grader, replace your TrieDebugger test with:
auto trie = Trie();
trie = trie.Put<uint32_t>("65", 25);
trie = trie.Put<uint32_t>("61", 65);
trie = trie.Put<uint32_t>("82", 84);
trie = trie.Put<uint32_t>("2", 42);
trie = trie.Put<uint32_t>("16", 67);
trie = trie.Put<uint32_t>("94", 53);
trie = trie.Put<uint32_t>("20", 35);
trie = trie.Put<uint32_t>("3", 57);
trie = trie.Put<uint32_t>("93", 30);
trie = trie.Put<uint32_t>("75", 29);

// Put a breakpoint here.

改完后重新提交，终于通过了。

Task #4 - SQL String Functions

配置好了 Debug 后，找到对应的文件，打个断点，查看调用堆栈，大概就能理解主流程是什么了。

接着使用 std::transform 实现了 LOWER 和 UPPER 函数即可。