【CMU15-445 FALL 2022】Project #0 - C++ Primer

关于

参考 & 鸣谢

  • 课程官网
  • CMU 15445 vscode/clion clang12 cmake环境配置
  • C++ 调试窗口显示“ for string variable
  • 【CMU15-445数据库】bustub Project #0:Trie 树实现(C++ Primer)

前言

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

环境配置

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

测试 & 调试

测试

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

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

调试

  • 我依然是使用CLion内进行打断点调试。
  • 在项目的顶级CMakeLists.txt中添加,如下行代码,以便于可以在调试时显示更多信息。
    • 如下图所示
代码语言:javascript
复制
set(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS_DEBUG} -D_GLIBCXX_DEBUG")
image.png
  • 调试按钮如下图所示
image.png
  • 从左到右分别是
    • 执行一行
    • 进入这行
    • 用的少,不是很了解
    • 从这个进入中出来
  • 这是我大致的理解,其实自己打个断点用用就会了,具体请网上自行搜索。

提交

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

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

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

某一块语句要写在{}内

代码语言:javascript
复制
// 将
if(a == 1)return ;
// 替换为
if(a == 1){
    return 0;
}

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

代码语言:javascript
复制
// 将
if(a == 1){
	return 0;
}else{
	std::cout << "test" <<std::endl;
}
// 替换为
if(a == 1){
	return 0;
}
std::cout << "test" <<std::endl;

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

代码语言:javascript
复制
// 使用
if(!cur->get()->IsEndNode())
// 替换
if(cur->get()->IsEndNode() == false)

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

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

然后提交到测试网站上

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

  • 需要先注册账号,注册账号时学校选择CMU(全称),详见其他博主的文章。
  • 然后将代码打包
代码语言:javascript
复制
 zip project0-submission.zip \     src/include/primer/p0_trie.h 
  • 可以通过以下命令验证文件内容,结果如下图所示
代码语言:javascript
复制
unzip -l project0-submission.zip
image.png
  • 最终在测试网站上选择对应的lab,将压缩包上传即可,然后等待结果。
    • 如下图所示,通过全部测试,100分啦。
image.png

实验

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

实验要求

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

什么是字典树?

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

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

如下图所示

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

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


实验内容

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开始可以直接在成员变量声明处,直接初始化。
代码语言:javascript
复制
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裸指针,详见下方补充。
  • 插入过程如下面动画所示
在这里插入图片描述
  • 最终结果如下图所示
image.png

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

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

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

  • 用两个例子简单说明下

删除abcd

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

删除ef

image.png
  • 过程同上。
  • 由于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方法获取其裸指针
代码语言:javascript
复制
unique<TrieNode> p;
auto t = p.get();

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

代码语言:javascript
复制
// 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来判断,所有权是否被转移
代码语言:javascript
复制
#include <iostream>
#include <memory>
#include <algorithm>
using namespace std;

int main(void){

auto a = make_unique&lt;int&gt;(32);

if(a.get() == nullptr){
	cout &lt;&lt; &#34;transfer1&#34; &lt;&lt;endl;
}
// 使用引用,并不会转移所有权
auto &amp;b = a;
if(a.get() == nullptr){
	cout &lt;&lt; &#34;transfer2&#34; &lt;&lt;endl;	
}

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

}

reset方法

  • reset后会将原来指向的内存释放, 转为指向现在所给定的。
    • 不传参数会将对应内存提前释放。
代码语言:javascript
复制
#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&lt;test&gt;();

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

}

mutex & shared_mutex

代码语言:javascript
复制
std::shared_mutex mutex_;
mutex_.lock();// 获取唯一锁,确保只有一个线程可以写入受保护的数据
mutex_.unlock();// 释放唯一锁

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

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

dynamic_cast

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

代码语言:javascript
复制
// cur 是TrieNode*
// 使用dynamic_cast判断cur 是否是TrieNodeWithValue* 
if (dynamic_cast<TrieNodeWithValue<T> *>(cur) == nullptr) {
  *success = false;
  latch_.RUnlock();
  return T();
}