CMU15-445-Spring-2023-Project #0 - C++ Primer

前置任务。

Task #1 - Copy-On-Write Trie

Copy-on-write (COW) Trie 在进行修改时，不会立即复制整个数据结构。相反，它会在需要修改的节点被多个引用的时候才进行复制。当要对某个节点进行写操作（添加子节点或者继续向下insert）时，如果该节点不是唯一被引用的（即有子节点），那么会先进行复制，确保只有修改的那个副本被修改，而其他引用不受影响。这样做的好处是，可以节省内存并且减少不必要的复制操作，只有在需要的时候才进行实际的复制。
实现三种op：

• Get(key)
  • 注意指针的转换：const auto *res = dynamic_cast<const TrieNodeWithValue<T> *>(cur.get());
• Put(key, value)
  • 首先找到最后一个已有节点，这些节点用栈保存；
  • 创建TrieNodeWithValue，需要区分是否有children；
  • 从该节点向上创建不存在的节点；
  • 最后根据栈中信息，继续向上clone已有节点；
• Delete(key)
  • 与Put类似的思想，只是不需要创建新节点；

Task #2 - Concurrent Key-Value Store

实现多线程下的COW Trie，支持多个读者，单个写者的模式，当修改trie时也能够读取trie，write_lock_锁全局。

Task #3 - Debugging

vscode中添加codelldb配置信息进行debug。
注意wsl环境的随机数设置与GradeScope不同，按照discord上说的修改test内容：

  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);

Task #4 - SQL String Functions

需要实现upper和lower两个SQL函数。
（1）在string_expression.h中实现函数逻辑。
（2）在BusTub中注册函数，以便SQL框架可以在用户执行SQL时在plan_func_call.cpp中调用函数。

实验结果