参考 & 鸣谢
前言
git clone --branch v20221128-2022fall https://github.com/cmu-db/bustub.git
测试
某一个模块的代码我们写完后需要进行测试,项目中有用GTest写好的测试程序,将第二个参数的**DISABLE_**前缀去掉即可运行。 通过本地测试用例后,提交到测试网站上进行最终的评分。
调试
set(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS_DEBUG} -D_GLIBCXX_DEBUG")
注意在提交前需要先检测代码风格,否则提交上去是没分的。
mkdir build
cd build
cmake ..
make
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> * {
// 略
}
然后提交到测试网站上
zip project0-submission.zip \ src/include/primer/p0_trie.h
unzip -l project0-submission.zip
OK,现在我们进入到具体的实验环节,我会先说明实验要干什么,然后依次给出一些说明和解释。
根据给出的代码,实现一个可满足并发要求的字典树,相关类的的代码已经在/bustub/src/include/primer/p0_trie.h中给出,需要我们给出具体函数的定义,可以在其中添加一些需要的辅助变量/函数。
什么是字典树?
字典树又称前缀树,是一种有序树,用于保存关联数组,其中的键通常是字符串.——Wiki百科-Trie
如下图所示
到此,我们对字典树有了一个大致的了解,这就足以实现我们本次的实验了。
任务一让我们实现的有关字典树的三个类
TrieNode
成员变量
成员函数
TrieNodeWithValue
成员变量
成员函数
Trie
成员变量
std::unique_ptr<TrieNode> root_ = std::make_unique<TrieNode>(' ');
成员函数
**bool Insert(const std::string &key, T value); **
bool Remove(const std::string &key);
做动画太累了,大家结合上面插入后的图理解一下吧。
删除abcd
删除ef
*T GetValue(const std::string &key, bool success);
任务二在上面的基础上,对字典树类Trie加锁,实现并发访问。
避免所有权转义
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引用
#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方法
#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;
}
std::shared_mutex mutex_;
mutex_.lock();// 获取唯一锁,确保只有一个线程可以写入受保护的数据
mutex_.unlock();// 释放唯一锁
mutex_.lock_shared();// 获取共享锁,允许多个线程同时可以读取受保护的对象
mutex_.unlock_shared();// 释放共享锁
// 在具体的底层实现上,当有线程持有共享锁时,其它线程将写锁无法被获取。
// 同样的,当线程持有写锁时,其它线程将无法获取写锁或共享锁。
判断是子类还是父类,将某一指针转换为指定类型, 转换成功说明它本来就是这种类型,反正则不是,失败返回nullptr
// cur 是TrieNode*
// 使用dynamic_cast判断cur 是否是TrieNodeWithValue*
if (dynamic_cast<TrieNodeWithValue<T> *>(cur) == nullptr) {
*success = false;
latch_.RUnlock();
return T();
}