【CMU15-445 Fall2023】Project0 C++ Primer 小结
该系列博客只是为了记录自己在写Lab时的思路，按照课程要求不会在Github和博客中公开源代码。欢迎与我一起讨论交流！
project0只在task4中浅浅涉及了一点BusTub的内容，其他都是检测我们对于C的一个掌握，主要涉及智能指针和C的常用特性（dynamic_cast、std::move、并发与锁等）。
Task1 - Copy-On-Write Trie
如果做过力扣上的208. 实现 Trie (前缀树)，实现Get和Put这两个操作会更容易。虽然这个task要求我们要使用COW，但是总体的思路是差不多的。
Get
这个比较简单，顺序遍历key去找节点的子节点就行。值得注意的是有值节点的类型为TrieNodeWithValue，其继承自TrieNode。当遍历玩key并找到节点后，使用dynamic_cast将其转换为TrieNodeWithValue*，如果这个节点不是一个有值的节点，则dynamic_cast会转换失败返回nullptr，否则会返回转换后的指针，通过这个指针获取最终的值即可。
Put
Put的基本思路就是遍历key的同时创建相应的节点，难点在于如何实现“copy on write”。
看官网的描述，我们要做的就是在需要修改Trie树（例如进行Put操作或者Remove操作）时，需要返回一颗新的Trie树，也就是我们当前的操作不能影响之前的Trie树的结构，这就需要使用到TrieNode::Clone()函数来拷贝一份需要修改的节点，这样才不会影响之前Trie树中的节点。同时，在这个过程中，我们需要尽可能地使用已有节点，举个🌰：
只需记住：
- 本次的插入或删除操作不会影响上次的Trie树的结构，例如上图如果我使用root来访问还是原来的结构，而用new root来访问就可以访问key值为“ad”的节点的值；
- 尽可能利用已有的节点，上图我们为了不影响之前的Trie树，我们必须拷贝根节点下“a”路径的子节点，插入一个新的节点也需要创建，但是值为“233”和“C++”的节点我们可以利用。
Remove
与Put不同，我使用递归来进行删除，这是因为Put可以顺序遍历key值并不断向下添加节点，而Remove需要从要删除的节点不断向上进行删除。
删除不合法的情况有：
- 碰到空节点
- 无法再继续往下查找key（key不存在）
这时按照任务要求应该返回原来的Trie树。
Task2 - Concurrent Key-Value Store
Get
加锁获取root_，然后调用之前再Task1中实现的Get操作获取key对应的value，如果value不为nullptr，则将root和value封装为ValueGuard。
Put、Remove
这两个操作的逻辑相同。由于之前我们实现Trie的三个操作时用到了COW，因此每次Put、Remove时返回的都是一个新的Trie，那么我们在Task2中的操作中要用全程获取写锁（ensure there is only one writer at a time），然后使用Put or Remove获取新的Trie，接着获取root_lock_，最后用获取的新的Trie更新root_。
Task3 - Debugging
这个没什么太多需要说明的。选择Clion或VSCode配置好环境打断点Debug就行，当然使用print大法也是可以的haha。注意这个task虽然有给你单元测试文件，但是运行肯定是不通过，因为问题答案并不在源码中，我们只能在gradescope才能检测自己做的是否正确。
（我所做的project所属课程是fall2023版本，如果是spring2023版本，task3在本地测试和gradescope上的测试可能会有区别，是随机数的问题，相关老师有在Discord上说明）
Task4 - SQL String Functions
这个task需要我们为BusTub实现两个简单的函数：lower和upper。实现并不难，找到需要修改的位置，添加相关处理逻辑和异常操作。
完成这个task我认为需要对string_expression.h这个文件的内容有一定理解，要明白如何判断获取的操作是lower还是upper，还有在plan_func_call.cpp中处理非法操作。总体来说不难。
提交
本地跑了测试代码还不够，课程有为我们这些非CMU的学生准备检测平台gradescope，如何加入课程可以看这里。
在提交之前，需要使用进行clang-tidy检测，并通过python3 gradescope_sign.py生成签名，这样才能通过平台的预检测。
这里贴一个通关的截图hh：
总结
这个project0我也是做了两三天（还是太菜了），在其中我更好地巩固了C++中的一些知识，例如智能指针、移动赋值、dynamic_cast。与之前做Xv6的Lab不同，这次的CMU15-445在网上基本没有关于实现的源代码，这就让我无法直接通过代码来学习了。当然这是课程的要求，希望我们能一起构建一个良好的学习氛围，鼓励我们独立思考完成，与他人交流而不是直接要代码，我觉得这是一个很锻炼自己的过程，网上大多是一些思路的介绍（我写的这篇博客也是自己实现的简单思路，希望没有违反课程的要求），我们在没思路时参考一下这些博客，然后再通过自己来完成代码，这比直接看别人写好的代码来说更能够提升自己！希望我能把接下来的几个project都完成，尽量不烂尾！