bustub 项目用 C++ 17 编写,但 C++ 11 已经够用。
C++ 相关教程:
关于GDB调试:
- Debugging Under Unix: gdb Tutorial
- GDB Tutorial: Advanced Debugging Tips For C/C++ Programmers
- Give me 15 minutes & I'll change your view of GDB [VIDEO]
git 命令:
PROJECT SPECIFICATION
该项目中,实现一个由并发 Trie 支持的kv存储。Trie 是一种有效的 ordered-tree 数据结构,用于检索给定键的值。为了简化解释,我们假设键都是非空的可变长度字符串,但实际上它们可以是任意类型。
Trie 中的每个节点存储一个键的单个字符,并且可以有多个子节点,这些子节点表示不同的可能的下一个字符。当到达一个键的结尾时,将设置一个标志来指示其对应的节点是一个结束节点。
在下面的示例中,trie 存储键 HELLO
、 HAT
和 HAVE
。
![image-20221013195202758](https://fastly.jsdelivr.net/gh/Angelia-Wang/blogImage/img/image-20221013195202758.png)
你将实现的kv存储能存储 map 到任何类型的 value 的 string key。key 对应的 value 值存储在表示该 key 的最后一个字符的结点(又称 terminal node)中。
例如,考虑在 trie 中插入 kv 对(“ ab”,1)和(“ ac”,“ val”)。这两个键共享同一个父节点 “a”
。在左边的子节点中,与键 “ab”
对应的值 1
存储在节点 “b”
中,与键 “ac”
对应的值 “val”
存储在节点 “c”
中。
![](https://15445.courses.cs.cmu.edu/fall2022/project0/graph.png)
IMPLEMENTATION
您只需要修改 BusTub 中的一个文件 p0_ trie.h
(src/include/primer/p0 _ trie.h)。除了测试代码之外,您不需要修改存储库中的任何其他文件。
函数原型和成员变量在文件中指定。该项目要求您填写所有构造函数、析构函数和成员函数的实现。如果您认为合适,可以添加任何其他的辅助函数和成员变量,但不要修改现有的函数和变量。
Task #1 - Templated Trie
在这个头文件中,我们定义了三个必须实现的类。我们建议您首先实现 Trie 类的单线程版本,然后再转向并发版本。
TrieNode Class
TrieNode
类在 Trie 中定义单个节点。TrieNode
保存 key 的一个字符,is_end
flag 指示它是否标记 key string 的结束。child nodes 的 key 字符从成员变量 children_
这个map 访问得到,它存储char
到 unique_ptr<TrieNode>
的映射。
注意:child node 为 unique_ptr
,因此将它们分配给其他变量时需要小心。InsertChildNode
和 GetChildNode
都返回一个指向 unique_ptr
的指针,这样就可以在不制作 copy 或放弃所有权的情况下访问 unique_ptr
的数据。
最后,移动构造函数 TrieNode(TrieNode &&other_trie_node)
用于将旧 TrieNode 的 unique pointer 传输到新的 TrieNode。确保在传输数据时没有复制唯一指针。
TrieNodeWithValue Class
TrieNodeWithValue
类继承自 TrieNode
,表示一个 terminal node,它的 key_char
是 key 的最后一个字符,该结点可保存任意类型 T
的 value ,is_end_
flag 始终为 true。
当使用给定的 key 迭代一个 trie 树并到达最终字符时,你将根据不同场景调用 TrieNodeWithValue
的不同构造函数(详见 Trie Class 部分)。现在,你需要知道的是,TrieNodeWithValue (char key_char,T value)
构造函数根据给定的 key 的字符和 value 构建一个 TrieNodeWithValue
。TrieNodeWithValue (TrieNode &&trieNode,T value)
构造函数从给定的 trieNode 中获取 unique_ptr
的所有权,并将它自己的 value_
设置为给定的值。
Trie Class
Trie
类定义支持 insert、search、remove 操作的实际 Trie 树。Trie 树的根节点是所有 key 的起始节点,它本身不应该存储任何键字符。
Insert
要在 Trie 树中插入一个kv,首先要使用给定的 key 遍历该 Trie 树,若不存在 TrieNode
,则插入。⚠️ 不允许插入一个重复的 key,应该返回 false。一旦到达 key 的最后一个字符,会有三种情况:
- 具有该字符的
TrieNode
不存在。则需要调用TrieNodeWithValue (char key_char,T value)
构造函数来创建具有指定 key_char 和 value 的 trie node。利用多态性 ——TrieNode
类的unique_ptr
也可存储TrieNodeWithValue
类的unique_ptr
。 - 具有该字符的
TrieNode
存在,但不是 terminal node(is_end_==false
)。这意味着unique_ptr
指向的是TrieNode
类对象而不是TrieNodeWithValue
类对象。需要调用TrieNodeWithValue (TrieNode &&trieNode,T value)
构造函数将旧TrieNode
对象转为新的TrieNodeWithValue
。 - 具有该字符的
TrieNode
存在,且已是 terminal node(is_end_==true
)这意味着unique_ptr
已经指向一个TrieNodeWithValue
类对象。应该立即返回 false,因为 key 不允许重复。
Remove
从 Trie 树中删除一个kv:
- 根据给定的 key 遍历该 Trie 树,若该 key 不存在,立即 return。
- 将 terminal node 的
is_end_
flag 变为 false。 - 若 terminal node 没有任何child结点,将它从父结点的
children_
map 中移除。 - 遍历 Trie 树并递归删除没有子结点的结点,当遇到有子结点的结点时就停止。
GetValue
对于给定的 key,返回对应的 value。若找不到 key 或提供的 type 与结点 value 的 type 不匹配,则将 success
设为 false。要检查这两种 type 是否相同,dynamic_cast raw TrieNode
pointer to TrieNodeWithValue<T>
pointer. 若转换结果为 nullptr
则 type T 与结点存储的 value 的类型不匹配。
Task #2 - Concurrent Trie
Trie 树需要保证 insert、search、remove 操作在多线程环境中工作。可使用 RwLatch
(BusTub 对 readers-writer lock 的实现)或 C++ STL 的std::shared_mutex
来实现。
这个项目只需要你通过获取根节点的 read/write lock 来实现简单的并发控制。
GetValue
函数应该从根结点获取一个 read lock(通过调用RwLatch
的RLock
方法)Insert
和Remove
操作应该从根结点获取一个 write lock(通过调用RwLatch
的WLock
方法)
若使用 RWLatch
,请确保在函数返回之前解锁所有获取的锁,以避免死锁。
Testing
可以使用我们的测试框架来测试此任务的各个组件。我们对单元测试用例使用 GTest。
test/primer/starter_trie_test.cpp
文件包含了对以上三个类的测试。
测试前要删掉测试文件中各函数前的 DISABLED_
前缀。
$ cd build
$ make starter_trie_test
$ ./test/starter_trie_test
提交
您将把您的实现提交给 Grescope:https://www.gradescope.com/courses/424375/
您只需在提交的 zip 文件中包含以下文件及其完整路径:
- src/include/primer/p0_trie.h
或者,在你的工作目录 (aka bustub
, bustub-private
, etc.) 运行