Project0 C++ Primer

相比于fall2022（Trie），spring2023（COW-Trie）的难度更大，算法更复杂【毕竟是要实现一个cow的数据结构】，我认为两个都很有意义，故而两个都做了。

其中在Trie中，由于我是第一次接触cpp，所以遇到了很多麻烦。好在经过18h+的cpp拷打后，cow-trie虽然难度大，语法也更复杂一些，但我还是很快（话虽如此也花了7、8小时23333）就完美pass了。不过效率可能还是不大高，毕竟我不熟悉cpp，很多地方可能都直接拷贝了emm希望后续学习可以加把劲。

Trie

In this project, you will implement a key-value store backed by a concurrent trie. 实现并发安全的trie

To simplify the explaination, we will assume tha the keys are all non-empty variable-length strings but in practice they can be any arbitrary type. key为非空变长字符串

The key-value store you will implement can store string keys mapped to values of any type. key必须是字符串类型，但value可以是任意类型

The value of a key is stored in the node representing the last character of that key.

心得

感想

本次实验完成时间总计18h+。是的，lab0就做了这么久【难绷】

其实光就实验内容来看，无非就是实现trie树，算法上没有很难，最难的应该是Remove函数的编写，因为它是个递归。

但正如本次实验的主题C++ Primer所揭示的那样，本次实验的真正难点在于C++……而在接触本实验之前，我对c++一无所知。

除了这个萌新debuf之外，我还不小心犯了另一件非常sb的乌龙，加上对cpp实在是太小白了，再加上这几天破事又贼多，更是让我心态大崩，差点一蹶不振不想写了（。

因而，整个实验在我看来十分痛苦。coding阶段，就是语法错误-看了半天报错信息才发现哪错了-改错误-改得不对-再改-再改-再改……这样的痛苦过程在循环往复；运行阶段，就是看着stack trace发呆、用gdb调来调去还不知道为什么错了这样的痛苦过程在循环往复。好在，我还是坚持下来了，虽然内心还是很浮躁很浮躁（

不过总而言之，我认为这次实验给我收获挺大的。它帮助我熟悉了C++，但我认为更重要的，是它帮我矫正了心态。做这个实验之前，我内心是很浮躁的（那会破事太多了），而且因为它是lab0所以有点轻敌（对不起。。），因而我所采取的策略是“错误驱动”，也即哪里报错就百度下怎么改就行。这样的心态就导致我的debug过程极度痛苦，因为完全看不懂报错信息，压根不知道错在哪里，百度也百度不出来。于是我被迫修改了战略，去看了我一直不想看的书，学了我一直很害怕的cpp，用了我一直很抗拒的gdb调试，才发现其实都没有我想象的这么恐怖。这期间、这几天的种种心路历程，我认为是十分可贵的。

错误集锦

sb错误

我下载下来starter code的时候，发现找不到它要我们实现的p0_trie.h，只有这几个：

我便觉得可能是实验代码改版了。但是我并没有多想，我觉得可能只是代码模板改版了但实验内容不变QAQ【为什么会这么觉得呢？因为我看到指导书的url为fall2022便以为这是最新版指导书，没有想到春季学期也可以开课，还有个spring2023呃呃】而且代码看起来也确实是要我们实现Trie树【虽然跟指导书说得不大一样】。故而，我就这么直接开干了。

写完了Tire树的逻辑【这部分确实挺简单的】之后，我就开始了漫长的痛苦且折磨的原地兜圈之旅。由于真正的spring2023的代码模板是实现COW-Trie，故而代码模板中很多地方都使用了const关键字，包括树结点以及树的children_成员。

// in class Trie
  std::shared_ptr<const TrieNode> root_{nullptr};
  template <class T> auto Get(std::string_view key) const -> const T *;
  template <class T> auto Put(std::string_view key, T value) const -> Trie;
  auto Remove(std::string_view key) const -> Trie;
// in class TrieNode
  std::map<char, std::shared_ptr<const TrieNode>> children_;

如上是spring2023的代码模板。

如果使用其给我们提供的COW-Tire接口来实现Trie树，就会产生巨大的矛盾。你无法在root_的孩子中插入或者删除一个树节点，因为root_指向一个const对象，其children_域也是const的。同样的，你也无法对root_的孩子的孩子集合做增删结点操作，因为它也是const的。

由于对C++不熟悉，通过满屏幕的报错从而搞清楚上面那些东西这件事，就花费了我很多很多时间。

1
2
3

error: no matching function for call to 
    ‘std::map<char, std::shared_ptr<const bustub::TrieNode> >
    ::insert(std::pair<char, std::shared_ptr<const bustub::TrieNode> >) const’

比如说这个错误我就看了半天完全不知道啥意思（

好在明白上面这点后，我很快就发现了spring2023的存在，然后切到了fall2022的正确分支【乐】

经过了此乌龙后，我深刻地意识到了我对C++一窍不通的程度（，比如说上面的这些const，还有比如说&是什么东西&&又是什么东西，shared_ptr又是什么东西等等等，我都不懂。故而，我压制了内心的浮躁，去简单看了一下书，了解了new的作用、左值引用右值引用、move、智能指针这几个地方，然后再去重新开始写本实验，最终果然好了不少。

错误使用unique_ptr::get

在Trie::GetValue中，我本来是这么写的：

	std::unique_ptr<TrieNode>* t = &root_;
	// ...
	std::unique_ptr<TrieNodeWithValue<T>> tmp(dynamic_cast<TrieNodeWithValue<T> *>(t->get()));
    // ...
}

这就会导致，tmp和(*t)会指向同一块内存区域，并且它们都是unique_ptr。随后，代码块遇到}结束，tmp的析构函数被调用，那块内存区域被free，但(*t)依然指向那块内存区域，随后在释放整个Trie树时这块区域就会被再次释放，然后寄（

共享unique_ptr

有一个方法可以在不剥夺某个unique_ptr的所有权的同时，又能用另一个变量来操作该指针所指向的对象。这个方法就是——使用指向unique_ptr的指针（。

也即比如：std::unique_ptr<TrieNode> *

代码规范

本次实验还格外要求了代码规范问题。

1
2
3

$ make format
$ make check-lint
$ make check-clang-tidy-p0

自测

我暂时没进行gradescope的自测，原因是它上面报了个跟我没啥关系的错，我不知道怎么改呃呃。

1
2
3

In file included from /autograder/bustub/src/common/bustub_instance.cpp:17:
/autograder/bustub/src/include/common/bustub_instance.h:30:10: fatal error: 'libfort/lib/fort.hpp' file not found
#include "libfort/lib/fort.hpp"

都指向说找不到这个fort。但我真的不知道它为啥找不到，因为我看CMakeLists.txt中已经加了third_party/这个include目录了，并且这个东西的路径也确实是third_party/libfort/lib/for.hpp。

我还在CMackLists.txt、src/CMackLists.txt、tools/shell/CMackLists.txt里面都加了include(${PROJECT_SOURCE_DIR}/third_party/libfort/lib/fort.hpp)，但是依然报了这样的错：

它这为啥找不到我是真的很不理解。

所以真的很奇怪。暂且先放着吧，之后有精力研究下这些编译链接过程。

COW-Trie

CMU 15445 Project 0 (Spring 2023) 学习记录参考了task2和一个bug

先放个通关截图~

总体用时（coding+debug+note）10h+

本次实验是在它给的接口的基础上，实现一株并发安全的cow的trie树，还有一个小小的实现upper和lower函数的实验用来熟悉我们之后要写的db的东西。算法难度还是有一些的，我的coding和debug时间估摸着可能有46开。

总体来说整个实验还是非常有价值的，相比往年难度和意义都更上了一层。感谢实验设计者让我做到设计得这么好的实验~

Task1 cow-trie

In this task, you will need to modify trie.h and trie.cpp to implement a copy-on-write trie.

下面举例说明

Consider inserting ("ad", 2) in the above example. We create a new Node2 by reusing two of the child nodes from the original tree, and creating a new value node 2. (See figure below)

If we then insert ("b", 3), we will create a new root, a new node and reuse the previous nodes. In this way, we can get the content of the trie before and after each insertion operation. As long as we have the root object (Trie class), we can access the data inside the trie at that time. (See figure below)

One more example: if we then insert ("a", "abc") and remove ("ab", 1), we can get the below trie. Note that parent nodes can have values, and you will need to purge all unnecessary nodes after removal.

To create a new node, you should use the Clone function on the TrieNode class. To reuse an existing node in the new trie, you can copy std::shared_ptr<TrieNode>: copying a shared pointer doesn’t copy the underlying data.

You should not manually allocate memory by using new and delete in this project. std::shared_ptr will deallocate the object when no one has a reference to the underlying object.

感想

task1的目标就是实现我们的cow-trie的主体，先不要求并发。

虽说算法上比较复杂，但是由于它图解以及代码中的注释解说都已经说得很详细了，再加上之前已经写过了trie树有一个大体框架，因而具体coding的时候思路还是比较清晰的。

我认为具体的难点还是在于cpp上。下面列出了几个比较有价值的错误和相关debug过程，其中const转移和显示保存is_value_node_是我认为两个比较难的点。

错误集锦

const转移

在trie.h中：

class Trie {
 private:
  // The root of the trie.
  std::shared_ptr<const TrieNode> root_{nullptr};
  // Create a new trie with the given root.
  explicit Trie(std::shared_ptr<const TrieNode> root) : root_(std::move(root)) {}

 public:
  // Create an empty trie.
  Trie() = default;

  // Get the value associated with the given key.
  // 1. If the key is not in the trie, return nullptr.
  // 2. If the key is in the trie but the type is mismatched, return nullptr.
  // 3. Otherwise, return the value.
  template <class T>
  auto Get(std::string_view key) const -> const T *;

  // Put a new key-value pair into the trie. If the key already exists, overwrite the value.
  // Returns the new trie.
  template <class T>
  auto Put(std::string_view key, T value) const -> Trie;

  // Remove the key from the trie. If the key does not exist, return the original trie.
  // Otherwise, returns the new trie.
  auto Remove(std::string_view key) const -> Trie;
};

可以看到，为了呼应我们的cow-trie，在语法上强制性要求不能“directly modify”，它将root_和children_->second同时设置为了一个指向对象为const的指针。而这意味着什么呢？意味着我们不能修改root_的内容，也不能修改root_->children_->second的内容，同样的孩子的孩子也不行。这就需要我们在Put方法中遍历trie时，对遍历路径上的每个结点都需要copy一次，故而我们的代码具体是如下实现的：

首先，利用TrieNode::Clone()方法来创造一个非const指针的新root：

1 2	// in trie.h TrieNode{} virtual auto Clone() const -> std::unique_ptr<TrieNode> { return std::make_unique<TrieNode>(children_); }

// 创造新的根节点，并且为非const类型
std::shared_ptr<TrieNode> root = std::shared_ptr<TrieNode>(root_->Clone());
// 使用t指针来遍历trie树
std::shared_ptr<TrieNode> t = root;

再然后，每次迭代的时候在遍历路径上创造新的结点，结点类型非const；再利用shared_ptr的共享复制（ t = tmp;），就能使得当前的t指针一直保持非const状态。

for (uint64_t i = 0; i < key.length(); i++) {
  auto it = t->children_.find(key.at(i));
  if (it == t->children_.end()) {
    if (i != key.length() - 1) {
      std::shared_ptr<TrieNode> tmp(new TrieNode());
      // ...
      t = tmp;
    } else {
      std::shared_ptr<TrieNodeWithValue<T>> tmp(new TrieNodeWithValue(std::make_shared<T>(std::move(value))));
      // ...
      t = tmp;
      break;
    }
  } else {
    if (i == key.length() - 1) {
      std::shared_ptr<TrieNodeWithValue<T>> node =
          std::make_shared<TrieNodeWithValue<T>>(it->second->children_, std::make_shared<T>(std::move(value)));
      // ...
      t = node;
      break;
    }
    std::shared_ptr<TrieNode> node = std::shared_ptr<TrieNode>(it->second->Clone());
    // ...
    t = node;
  }
}

注：我本来的写法是这样的：

for (uint64_t i = 0; i < key.length(); i++) {
  auto it = t->children_.find(key.at(i));
  if (it == t->children_.end()) {
    if (i != key.length() - 1) {
      std::shared_ptr<TrieNode> tmp(new TrieNode());
      // ...
    } else {
      std::shared_ptr<TrieNodeWithValue<T>> tmp(new TrieNodeWithValue(std::make_shared<T>(std::move(value))));
      // ...
      break;
    }
  } else {
    if (i == key.length() - 1) {
      std::shared_ptr<TrieNodeWithValue<T>> node =
          std::make_shared<TrieNodeWithValue<T>>(it->second->children_, std::make_shared<T>(std::move(value)));
      // ...
      break;
    }
    std::shared_ptr<TrieNode> node = std::shared_ptr<TrieNode>(it->second->Clone());
    // ...
  }
  it = t->children_.find(key.at(i));
  t = it->second;
}

也就是为了省事，将t指针的转移集中放在了循环体最后进行。但这样是不行的。

cpp中，可以将非const对象自然转移为const对象，比如代码中就将非const的新结点放进了children_中；但是不允许将const对象自然转移为非const对象，比如代码中的t = it->second;。因而，我们对t指针的转移不能在新结点放入其children_之后。

注2：在这里，我本来还多用了一个prev指针，因为在coding的时候用的是上面的本来的写法，误以为t指针只能是const，所以还得有父节点才能再把t指针复制一遍。但其实并非如此，而且就算如此prev指针也还是跟t指针一样的const的。。。不过还好编译前发现了上面那点改过来了，要不然就得面对编译大报错2333

make_shared

make_shared作用也类似于new，会在堆上开辟空间用以存放共享指针的base对象。这也让我想起来我在做上面那个实验时一个地方改成make_shared就对了，估计是犯了用栈中对象创建共享指针的错误。

官方鼓励用make_shared函数来创建对象，而不要手动去new。这一是因为，new出来的类型是原始指针，make_shared可以防止我们去使用原始指针创建多个引用计数体系；二是因为，make_shared可以防止内存碎片化。

一个奇妙的报错

在写这样的shared_ptr的共享转移时：

1
2
3

std::shared_ptr<TrieNode> tmp = make_shared<TrieNode>();
// ...
t = tmp;

会在t=tmp这里报错不能把int类型的tmp复制给t。我看了半天很奇怪哪来的int类型，查了半天怎么共享shared_ptr，最后才发现是因为这里：

1	std::make_shared<TrieNode>()

漏了个std::呃呃。

显式保存is_value_node_

在trie.cpp RemoveHelper()中：

if (i != key.length() - 1) {
    // 注意此处需要保留原来的is_value_node_，之后再赋值回去！！！
    bool tmp_val = node->second->is_value_node_;
    std::shared_ptr<TrieNode> tmp = std::shared_ptr<TrieNode>(node->second->Clone());
    tmp->is_value_node_ = tmp_val;
    
    root->children_.erase(key.at(i));
    root->children_.insert(std::make_pair(key.at(i), tmp));
    flag = RemoveHelper(tmp, key, i + 1);
}

否则会：

查看trie_test.cpp的代码：

TEST(TrieTest, BasicRemoveTest2) {
  auto trie = Trie();
  // Put something
  trie = trie.Put<uint32_t>("test", 2333);
  ASSERT_EQ(*trie.Get<uint32_t>("test"), 2333);
  trie = trie.Put<uint32_t>("te", 23);
  ASSERT_EQ(*trie.Get<uint32_t>("te"), 23);
  trie = trie.Put<uint32_t>("tes", 233);
  ASSERT_EQ(*trie.Get<uint32_t>("tes"), 233);

  // Delete something
  trie = trie.Remove("te");
  trie = trie.Remove("tes");
  trie = trie.Remove("test");

  ASSERT_EQ(trie.Get<uint32_t>("te"), nullptr);
  ASSERT_EQ(trie.Get<uint32_t>("tes"), nullptr);
  ASSERT_EQ(trie.Get<uint32_t>("test"), nullptr);
}

它是在ASSERT_EQ(trie.Get<uint32_t>("te"), nullptr);这句报错的。这确实很奇怪，因为“te”已经被remove了。这是为什么呢？

经过gdb调试，trie的Remove和Put功能都确实很正常，但是我发现了一个诡异的现象。

在经过trie = trie.Remove("te");这句话后，trie的状态是t-e-(s)-(t)【括号表示为有值结点，类型为TireNodeWithValue】，符合预期。但是，经过紧随其后的trie = trie.Remove("tes");之后，trie的状态却变成了t-(e)-s-(t)。

这实在是很诡异，为什么经过了一次Remove之后，trie = trie.Remove("te");这句话的效果就被重置了？

我想了挺久，最终认为这是构造方法的问题。

再次看一遍我们的Remove的代码：

if (i != key.length() - 1) {
    std::shared_ptr<TrieNode> tmp = std::shared_ptr<TrieNode>(node->second->Clone());
    
    root->children_.erase(key.at(i));
    root->children_.insert(std::make_pair(key.at(i), tmp));
    flag = RemoveHelper(tmp, key, i + 1);
} else {
    if (node->second->is_value_node_) {
      if (!node->second->children_.empty()) {
        std::shared_ptr<TrieNode> tmp = std::shared_ptr<TrieNode>(node->second->Clone());
        tmp->is_value_node_ = false;
        root->children_.erase(key.at(i));
        root->children_.insert(std::make_pair(key.at(i), tmp));
      } else {
        root->children_.erase(key.at(i));
      }
      return true;
    }
    return false;
}

以及TrieNodeWithValue::Clone()：

1
2
3

auto Clone() const -> std::unique_ptr<TrieNode> override {
  return std::make_unique<TrieNodeWithValue<T>>(children_, value_);
}

以及Clone()方法调用的TrieNodeWithValue的构造方法：

1	explicit TrieNodeWithValue(std::shared_ptr<T> value) : value_(std::move(value)) { this->is_value_node_ = true; }

可以发现，在多态作用下，e结点始终是一个TrieNodeWithValue的结点。

在我们去除tes这个key时，会到这个分支：

1 2	if (i != key.length() - 1) { std::shared_ptr<TrieNode> tmp = std::shared_ptr<TrieNode>(node->second->Clone());

Clone()中会调用node->second，也即e结点的构造方法，然后将e结点的is_value_node_设置为true，从而导致Get中无法通过这句代码返回nullptr。

1
2
3

if (!(t->is_value_node_)) {
  return nullptr;
}

因而，为了解决这个问题，我们就需要暂存is_value_node_，并在之后恢复它。

Task2 concurrency

In this task, you will need to modify trie_store.h and trie_store.cpp.需要实现并发安全版本。

For the original Trie class, everytime we modify the trie, we need to get the new root to access the new content. But for the concurrent key-value store, the put and delete methods do not have a return value. This requires you to use concurrency primitives to synchronize reads and writes so that no data is lost through the process.在并发安全版本中，Put和Get不会返回trie，而是应该修改包装类的base trie。

Your concurrent key-value store should concurrently serve multiple readers and a single writer. That is to say, when someone is modifying the trie, reads can still be performed on the old root. When someone is reading, writes can still be performed without waiting for reads.同一时刻可以有一个writer和多个reader。

Also, if we get a reference to a value from the trie, we should be able to access it no matter how we modify the trie. The Get function from Trie only returns a pointer. If the trie node storing this value has been removed, the pointer will be dangling. Therefore, in TrieStore, we return a ValueGuard which stores both a reference to the value and the TrieNode corresponding to the root of the trie structure, so that the value can be accessed as we store the ValueGuard.为我们提供了 ValueGuard用以确保return值长时间有效。

To achieve this, we have provided you with the pseudo code for TrieStore::Get in trie_store.cpp. Please read it carefully and think of how to implement TrieStore::Put and TrieStore::Remove.我们在Get方法中给出了详细的步骤引导。你需要依据它来对Put和Get进行修改。

感想

task2的内容是实现cow-trie并发安全版本的包装类TrieStore。

相比于fall2022的并发内容，由于加上了cow的特性，本次实验更加复杂。我写了三版都没写对，看到别人的才豁然开朗（很遗憾没有自己再多想会儿……）接下来就从我的错误版本开始，逐步过渡到正确版本吧。

错误集锦

版本1

Get的实现很简单，按他说的一步步做就行，在这边不做赘述。Put和Remove思路差不多，在此只放Put的代码。

这样看起来很合理：同一时刻似乎确实只有一个writer对root_进行修改，也似乎确实同时可以有别的线程获取root_lock_对其进行读取。但其实，前者是错误的。

假如说进程A和进程B都在Put逻辑中。进程A执行到了root_ = new_trie这句话，然后进程B进入到root_.Put中。

root_ = new_trie使用了运算符=的默认实现，进行浅拷贝，故而会修改root_->root_；root_.Put中会对root_->root_进行移动。

进程B在Put中执行std::move(root_)之后，进程A又让root_->root_变成了别的值（trie浅拷贝），导致原来的root_的引用计数变为0，自动释放（因为是智能指针shared_ptr），进程B在Put中再次访问就会寄。

注，此处是因为智能指针引用计数为零才释放的，cpp没有垃圾回收机制。

版本2

void TrieStore::Put(std::string_view key, T value) {
  // You will need to ensure there is only one writer at a time. Think of how you can achieve this.
  // The logic should be somehow similar to `TrieStore::Get`.
  root_lock_.lock();
  Trie tmp = root_;
  root_lock_.unlock();

  write_lock_.lock();
  Trie new_trie = tmp.Put(key, std::move(value));
  write_lock_.unlock();

  root_lock_.lock();
  root_ = new_trie;
  root_lock_.unlock();
}

版本1错误后，我发现我并没有按它强调的“somehow similar to Get”那样，模仿Get中的写法来做。于是我就修改了下，版本2诞生了。

但是这样的话，依然不能解决版本1中的问题。所以我又搞了个版本3.

版本3

void TrieStore::Put(std::string_view key, T value) {
  write_lock_.lock();
  Trie tmp = root_;
  Trie new_trie = tmp.Put(key, std::move(value));
  root_ = new_trie;
  write_lock_.unlock();
}

这样就能通过所有测试了。

但这样做虽然能解决多个writer的争夺问题，但不能解决一个writer和一个reader的争夺问题：因为两者都争夺同一个root_变量，但只有reader争夺root_lock_，这显然很不安全。因而，终极版本应该是这样：

正确版本

template <class T>
void TrieStore::Put(std::string_view key, T value) {
  write_lock_.lock();
  root_lock_.lock();
  Trie tmp = root_;
  root_lock_.unlock();

  Trie new_trie = tmp.Put(key, std::move(value));

  root_lock_.lock();
  root_ = new_trie;
  root_lock_.unlock();
  write_lock_.unlock();
}

可以看到整个思维过程是线性的，逐步改进下来，正确答案其实很容易想到。只可惜我太浮躁了，没有静下心来好好想，在版本3之后就去看了眼别人怎么写的（罪过）没有独立思考，算是一个小遗憾。

Task3 debugging

感想

一个考查我们debug入门技巧的小任务，简单，但我觉得形势很新颖。

debug过程

随便贴点debug过程的截图。

小问题

gdb：Attempt to take address of value not located in memory.

任务中，需要获取root_的孙子。所以我就这么写了个gdb指令：p root_->children_.find('9')->second，然后就爆出了标题这个错误。

百度了下看到了这个：

gdb调试时好用的命令

也许是因为我们通过.访问了children_的成员find吧（

总之，我最后是在trie_debug_test添加了这几行代码解决的：

// Put a breakpoint here.

// (1) How many children nodes are there on the root?
// Replace `CASE_1_YOUR_ANSWER` in `trie_answer.h` with the correct answer.
if (CASE_1_YOUR_ANSWER != Case1CorrectAnswer()) {
  ASSERT_TRUE(false);
}
auto it = trie.root_->children_.find('9');
// (2) How many children nodes are there on the node of prefix `9`?
// Replace `CASE_2_YOUR_ANSWER` in `trie_answer.h` with the correct answer.
if (CASE_2_YOUR_ANSWER != Case2CorrectAnswer()) {
  ASSERT_TRUE(false);
}
auto val = trie.Get<uint32_t>("93");
std::cout << val << it->first << std::endl;
// (3) What's the value for `93`?
// Replace `CASE_3_YOUR_ANSWER` in `trie_answer.h` with the correct answer.
if (CASE_3_YOUR_ANSWER != Case3CorrectAnswer()) {
  ASSERT_TRUE(false);
}

也即添加了it和val，以及防止unused报错的cout语句。gdb调试时打印it和val就行。

答案对但是过不了评测

来自CMU 15445 Project 0 (Spring 2023) 学习记录

在我本地的环境上，调试三问的答案分别是8 1 42，但该答案无法通过 Grade 平台的评测。发现在 Discord 上有人提出了同样的问题，助教 Alex Chi 给出了解答：

Alex Chi — 2023/02/15 23:29
It is possible that your environment produces different random numbers than the grading environment. In case your environment is producing different set of random numbers than our grader, replace your TrieDebugger test with:
1
2
3
4
5
6
7
8
9
10
11
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);

难绷，我反复确认了好几遍（。主要还是太相信cmu的权威了，觉得这实验都发布了好几个月了应该不会有错，就没想到是这个问题。我觉得最好还是把这个问题反应在指导书上吧。

Task4 SQL String Functions

Now it is time to dive into BusTub itself!

You will need to implement upper and lower SQL functions.

This can be done in 2 steps:

implement the function logic in string_expression.h.

register the function in BusTub, so that the SQL framework can call your function when the user executes a SQL, in plan_func_call.cpp.

To test your implementation, you can use bustub-shell:
1
2
3
4
5
cd build
make -j`nproc` shell
./bin/bustub-shell
bustub> select upper('AbCd'), lower('AbCd');
ABCD abcd

感想

说实话乍一看我还没看懂（。它放在这个位置，我还以为跟上面实现的cow-trie有什么关系，并且误以为这个upper和lower是什么上层接口底层接口的意思，跟它大眼瞪小眼了半天。直到看到了下面的案例，才发现跟trie似乎没有任何关系23333

本次实验内容其实就是实现sql的转换大小写的函数。知道了要做什么之后，任务就很简单了，按着它提示一步步做就行。

不过此task重点其实也是在稍微了解下我们接下来要打交道的sql框架的代码。比如说，此次我们的实现涉及到的，居然是一个差不多是工厂模式（其实更像策略模式？）的一部分：

外界传入想调用的函数名，通过GetFuncCallFromFactory获取对应的处理对象

得到处理对象后调用其Compute方法就行

第一次如此鲜明地看到一个设计模式在cpp的应用，真是让我非常震撼。

代码规范

依旧是这三件套：

1
2
3

make format
make check-lint
make check-clang-tidy-p0

错误集锦

关于sanitizer

执行了该命令：cmake -DCMAKE_BUILD_TYPE=Debug -DBUSTUB_SANITIZER= ..之后，执行make报错missing argument to '-fsanitize='

发生这个的原因是cmake的命令中将BUSTUB_SANITIZER设置成了空。解决方法就是将其设置为别的值就好了，具体想设置成什么值可以参见：关于GCC/LLVM编译器中的sanitize选项用处用法详解我这里姑且随便设置了个leak。