关于
参考 & 鸣谢
- 课程官网
- CMU 15445 vscode/clion clang12 cmake环境配置
- C++ 调试窗口显示“ for string variable
- 【CMU15-445数据库】bustub Project #0：Trie 树实现（C++ Primer）
- 2022 CMU15-445学习群 —— 152391370
前言
- 按照课程要求，本文并不会给出实现代码，可以当做是我遇到问题的总结，一些理解 & 解释，希望能帮助到需要的读者。
- 具体的信息可以去课程官网的对应实验说明处寻找。
- 实验使用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> * {
// 略
}- 根据提示修改完成后，代码风格全部符合要求后，再次进行检测，结果如下图所示。
然后提交到测试网站上
- 需要先注册账号，注册账号时学校选择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： 存储当前节点所存的字符
- is_end_: 当前节点对应的字符是否是存储的某一字符串的结尾字符
- 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_
- 使用unique_ptr的问题，这里给出提示使用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; // 23unque_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();
}