关于

参考 & 鸣谢

前言

  • 按照课程要求，本文并不会给出实现代码，可以当做是我遇到问题的总结，一些理解 & 解释，希望能帮助到需要的读者。
  • 具体的信息可以去课程官网的对应实验说明处寻找。
  • 实验使用C++实现，设定的标准是C++17，对C++语法不了解的小伙伴需要自行学习下，Project 0中需要的一些用法在本文中会有所标注，需要特别强调的在【补充】处说明。
  • 还是希望先自己尝试去做，如果没有思路，再来参考我的实现思路。

环境配置

  • clone指定版本，因为官方github该仓库每年都会进行更新。(从群内的聊天记录中翻到的。)
    • 我们需要的是 Faill 2022最后一版
git clone --branch v20221128-2022fall https://github.com/cmu-db/bustub.git
  • 这里我使用CLion + WSL作为本项目的开发环境，环境配置详见上方引出来的环境配置文章。
    • 这两个一开，跑项目时还是挺占内存的。

测试 & 调试

测试

某一个模块的代码我们写完后需要进行测试，项目中有用GTest写好的测试程序，将第二个参数的DISABLE_前缀去掉即可运行。 通过本地测试用例后，提交到测试网站上进行最终的评分。

  • 这里还是推荐使用CLion,它可以只运行某一个测试用例。其他的貌似只能通过编译运行整个文件。

调试

  • 我依然是使用CLion内进行打断点调试。
  • 在项目的顶级CMakeLists.txt中添加，如下行代码，以便于可以在调试时显示更多信息。
    • 如下图所示
set(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS_DEBUG} -D_GLIBCXX_DEBUG")

  • 调试按钮如下图所示

  • 从左到右分别是
    • 执行一行
    • 进入这行
    • 用的少，不是很了解
    • 从这个进入中出来
  • 这是我大致的理解，其实自己打个断点用用就会了，具体请网上自行搜索。

提交

注意在提交前需要先检测代码风格，否则提交上去是没分的。

  • 如果你跟我一样是直接使用CLion编译运行的，首先进入到项目文件夹/bustub文件夹下，依次执行如下命令，编译项目。
mkdir build
cd build
cmake ..
make
  • 然后执行格式检查
    • 应该要安装clang-fromat,clang-tidy,自行网上搜索安装。
    • 然后依次执行以下命令
make format
make check-lint
make check-clang-tidy-p0
  • 如果代码风格不符合要求，如下图所示，会给出错误说明。

这里说明我遇到的一些格式问题

某一块语句要写在{}内

// 将
if(a == 1)return ;
// 替换为
if(a == 1){
    return 0;
}

if else语句中 if返回了，不能使用else

// 将
if(a == 1){
    return 0;
}else{
    std::cout << "test" <<std::endl;
}
// 替换为
if(a == 1){
    return 0;
}
std::cout << "test" <<std::endl;

判断语句尽可能的要写简洁

// 使用
if(!cur->get()->IsEndNode())
// 替换
if(cur->get()->IsEndNode() == false)

函数返回值使用auto类型，注意: 如果函数的返回类型依赖于函数体中的操作，后置声明语法是必要的。

  auto InsertChildNode(char key_char, std::unique_ptr<TrieNode> &&child) -> std::unique_ptr<TrieNode> * {
    // 略
  }
  • 根据提示修改完成后，代码风格全部符合要求后，再次进行检测，结果如下图所示。

然后提交到测试网站上

测试网站 —— https://www.gradescope.com/courses/425272

  • 需要先注册账号，注册账号时学校选择CMU(全称)，详见其他博主的文章。
  • 然后将代码打包
 zip project0-submission.zip \     src/include/primer/p0_trie.h
  • 可以通过以下命令验证文件内容，结果如下图所示
unzip -l project0-submission.zip

  • 最终在测试网站上选择对应的lab，将压缩包上传即可，然后等待结果。
    • 如下图所示，通过全部测试，100分啦。

实验

OK，现在我们进入到具体的实验环节，我会先说明实验要干什么，然后依次给出一些说明和解释。

实验要求

根据给出的代码，实现一个可满足并发要求的字典树，相关类的的代码已经在/bustub/src/include/primer/p0_trie.h中给出，需要我们给出具体函数的定义，可以在其中添加一些需要的辅助变量/函数。

什么是字典树？

字典树又称前缀树,是一种有序树,用于保存关联数组,其中的键通常是字符串.——Wiki百科-Trie

  • 通俗的来说，就是将一串字符串依次拆分成字符存储到一棵的节点上，依次相连，前一个字符是后一个字符的父亲。从这个树中，查找是否有对应的字符串。
    • 字典是干嘛的，就是方便我们寻找对应的字的解释的。
    • 具体到本项目中就是存储对应的string及其value
  • 解释一下查找指定字符串过程
    • 在查找的时候从根节点的孩子开始查找；
    • (因为本项目的实现，根节点不存储数据，所以我们下面都以这个情况进行解释。)
    • 从孩子中寻找对应的下一个字符，沿着树向下靠近，直到找到对应的结尾字符,如果不存在该结尾字符或者该存在该结尾字符，但是它并没有被标记为【结尾节点】，说明这个字符串也不存在于我们这棵字典树上。
    • 反之，沿着节点找到了该字符串的所有字符，并且结尾字符被标记为【结尾节点】，说明找大了这个字符串，存在于我们这棵字典树上。

如下图所示

  • 这棵字典树中存储了，"abc","abcd","ace","ef",这三个字符串。
    • 其中 'c','d','e','f',被标记为是结尾字符。
    • 注意重复的情况，如果字符串的开头可以覆盖，则可以共用前面的节点，如"abcd","abc"，"ace";
    • 反之，需要另起开头，如"ef"。

到此，我们对字典树有了一个大致的了解，这就足以实现我们本次的实验了。

实验内容

Task #1 - Templated Trie

任务一让我们实现的有关字典树的三个类

  • TrieNode
    • 字典树节点类
  • TrieNodeWithValue
    • 继承自TrieNode,特指结尾字符
  • Trie
    • 字典树类

TrieNode

成员变量

  • key_char： 存储当前节点所存的字符
  • isend: 当前节点对应的字符是否是存储的某一字符串的结尾字符
  • chaildren_: 存储当前节点孩子对应的char，以及指向它的指针，使用哈希表存储

成员函数

  • TrieNode(char);
    • 构造函数，使用一个char构造当前节点
  • TrieNode(TrieNode &&);
    • 移动构造函数，使用一个TrieNode来构造本TrieNode
    • 通过移动语义构造对象，避免不必要复制操作，以提高代码效率。
  • bool HashChild(char key_char);
    • 检查当前节点是否存在某个节点对应的字符为key_char的节点
  • bool HashChild();
    • 上一个函数的重载函数，检查当前节点有没有孩子。
  • bool IsEndNode()
    • 判断当前节点是否是结尾字符节点
  • char GetKeyChar();
    • 返回当前节点的对应的字符
  • std::unique_ptr * InsertChildNode(char key_char, std::unique_ptr &&child);
    • 插入到当前节点后面，即放入到当前节点的children_中
    • 不允许重复，如果要放入的key_char已经存在了，return nullptr
    • 反之，返回指向对应节点的unique_ptr 指针
  • std::unique_ptr * GetChild(char key_char);
    • 根据给定的key_char在当前节点的孩子中寻找这个节点，找到返回指向其的unique_ptr *指针，反之返回nullptr
  • void RemoveChildNode(char key_char);
    • 删除key_char对应的节点，在当前节点的孩子中寻找
  • void SetEndNode(bool is_end) ;
    • 设置当前节点的结尾字符标记为is_end

TrieNodeWithValue

  • 继承自TrieNode

成员变量

  • value: 存储当前节点对应的value,结尾节点才存储。即该字符串对应的value

成员函数

  • TrieNodeWithValue(TrieNode &&trieNode, T value)；
    • 构造函数
    • 使用一个TrieNode节点和一个value值构造
    • 实际上其中调用的就是TrieNode的移动构造函数
    • TrieNode(std::move(trieNode))；
  • TrieNodeWithValue(char key_char, T value)；
    • 构造函数
    • 使用一个key_char 和一个value构造。
  • T GetValue();
    • 返回当前结尾节点对应的value

Trie

  • 字典树类。

成员变量

  • root_
    • 一颗字典树的根节点。不存储任何数据。
    • 注意: 根节点需要创建，C++11开始可以直接在成员变量声明处，直接初始化。
std::unique_ptr<TrieNode> root_ = std::make_unique<TrieNode>(' ');
  • latch_
    • 当前字典树的读写锁，对shared_mutex进行了一层封装。用于并发访问控制。

成员函数

bool Insert(const std::string &key, T value);

  • 在当前字典树上插入一个单词(key)
  • 实现思路
    • 遍历key的每一个字符，同时从root_孩子开始遍历，找到对应字符就继续往下走，反之为当前字符创建节点，存储到当前节点的孩子中， 更新遍历指针。
    • 最终到达末尾，判断是否已经被标记为结尾字符节点，因为不能重复，如果已被标记，返回false;
    • 未被标记，将当前TrieNode节点转换为TrieNodeWithValue节点。
  • 注意
    • 判断key是否为空
    • 注意创建root_
    • 使用uniqueptr的问题，这里给出提示使用auto cur = &root; cur为unique_ptr 指针，调用get()，获取TrieNode裸指针，详见下方补充。
  • 插入过程如下面动画所示

  • 最终结果如下图所示

bool Remove(const std::string &key);

  • 在字典树中删除对应的字符串
  • 实现思路
    • 遍历每个字符，如果没找全，说明不存在，return false
    • 找全了，但是结尾字符，没有被标记为结尾字符，return false
    • 找到指定字符串了，结尾字符所在节点也被标记了，开始进行删除。
    • 把结尾字符节点标记为false
    • 在遍历每个字符之前，这里我使用一个vector<unque_ptr*>nodes保存走过的路径。
      • 即，保存，该key的每个字符的父节点。用于后序删除操作。
    • 开始删除
    • 反向遍历nodes,同时判断当前要删除的节点，如果被标记为了结尾节点，或者还有孩子。就不能删除了，删除过程终止。
    • 反之，不断从父节点的children_中，将该孩子的映射删除，一层一层向上朝root_前进。

做动画太累了，大家结合上面插入后的图理解一下吧。

  • 用两个例子简单说明下

删除abcd

  • 遍历过程省略
  • 将d节点 is_end_置为false。
  • 判断不是结尾字符啦，同时也没有孩子，将其从c几点的children_中删除，所对应内存会被自动释放。
  • 再判断c节点，虽然没有孩子，但是被标记为了结尾节点，过程终止。删除完毕。

删除ef

  • 过程同上。
  • 由于e没有孩子了，也不是结尾字符，所以它也会被从root_的children_中删除。

*T GetValue(const std::string &key, bool success);**

  • 查找指定字符串是否在
  • 遍历字符沿着字典树寻找。
    • 找全了，并且结尾字符被置为结尾字符节点，说明找到，反之没找到。
  • 相比与前面两个，这个就简单多了，略......

Task #2 - Concurrent Trie

任务二在上面的基础上，对字典树类Trie加锁，实现并发访问。

  • 根据函数目的，调用读锁还是写锁。
    • 注意每个return 前记得开锁。

补充

unique_ptr

避免所有权转义

  • 使用unique_ptr指针，例如unique_ptr* p
  • 或者，使用get方法获取其裸指针
unique<TrieNode> p;
auto t = p.get();

容易混淆的一点，unique_ptr* 问题

// a 是 unique_ptr<int>
auto a  = make_unique<int>(32);//c++14
// b是 unque_Ptr<int>*
auto b = & a;
// 注意b就是一个普通的指针，类似于int* 不要混淆了，以为它是unique_ptr
b->reset(new int(23));
cout << *a << endl; // 23

unque_ptr引用

  • 使用引用并不会导致所有权的转移。只能通过reset()或是std::move()
  • 可以通过调用get()，获取裸指针，判断是否为nullptr来判断，所有权是否被转移
#include <iostream>
#include <memory>
#include <algorithm>
using namespace std;

int main(void){

    auto a = make_unique<int>(32);

    if(a.get() == nullptr){
        cout << "transfer1" <<endl;
    }
    // 使用引用，并不会转移所有权
    auto &b = a;
    if(a.get() == nullptr){
        cout << "transfer2" <<endl;   
    }

    // 将资源所权转移
    auto c(move(a));
    if(a.get() == nullptr){
        cout << "transfer3" <<endl;   // 这行最终输出
    }
    return 0;
}

reset方法

  • reset后会将原来指向的内存释放， 转为指向现在所给定的。
    • 不传参数会将对应内存提前释放。
#include <iostream>
#include <memory>
#include <algorithm>
using namespace std;

class test{
public:
    test(){}
    ~test(){cout <<"see you" << endl;}
};

int main(void){

    auto t1 = make_unique<test>();

    // 
    t1.reset(new test());// 输出see you
    while(1){}//将程序卡住
    return 0;
}

mutex & shared_mutex

std::shared_mutex mutex_;
mutex_.lock();// 获取唯一锁，确保只有一个线程可以写入受保护的数据
mutex_.unlock();// 释放唯一锁

mutex_.lock_shared();// 获取共享锁，允许多个线程同时可以读取受保护的对象
mutex_.unlock_shared();// 释放共享锁

// 在具体的底层实现上，当有线程持有共享锁时，其它线程将写锁无法被获取。
// 同样的，当线程持有写锁时，其它线程将无法获取写锁或共享锁。

dynamic_cast

判断是子类还是父类，将某一指针转换为指定类型， 转换成功说明它本来就是这种类型，反正则不是,失败返回nullptr

// cur 是TrieNode*
// 使用dynamic_cast判断cur 是否是TrieNodeWithValue* 
if (dynamic_cast<TrieNodeWithValue<T> *>(cur) == nullptr) {
  *success = false;
  latch_.RUnlock();
  return T();
}