# CMU-15445-Lab0-primer

# 环境配置

使用的是 Ubuntu 22.04

编译器版本为 clang-14

实验设定的语法标志为 C++17

源码下载地址： https://github.com/cmu-db/bustub/releases/tag/v20221128-2022fall

需要下载压缩包进行解压使用，要不然有一些地方已经有了新的更新已经和课程的代码不一样了

其他的就是跟着说明过一遍命令即可

最后测试环境是否搭建完成

	cd bulid/test/
	make starter_trie_test
	./starter_trie_test

出现如下内容即表示搭建完成，便可以愉快的食用了

完整代码查看：https://github.com/charmber/basedata

首先需要完成的是 TrieNode 这个类

# TrieNodeInsertTest

是测试插入一个节点，所以直接找到 InsertChildNode 这个成员函数，通过注释了解到，需要传入一个 key ，作为这个节点的键名，然后再传入一个这个 TrieNode 类节点， key 和类当中的成员变量 key_char_ 要保持一致，并且在类成员变量哈希表 children_ 当中不能已经存在，那么就可以创建这个树节点

children_[key_char] = std::move(child);

因为传入的为智能指针，所以需要使用 move 来转移所有权

# RemoveChildNode

测试删除一个节点，存在就删除

	if (children_.count(key_char) == 0) {
	return;
	}
	children_.erase(key_char);

其他的函数没啥难度，根据注释完成就可以

# TrieInsertTest

在完成 Insert 函数之前需要先完成 Trie() 的构造函数，把首位节点的 key 置为 '\0'

Trie() { children_ = std::make_unique<TrieNode>('\0'); }

根据要求可以知道，

如果传入 key 为空则返回 false

传入的 key 已经存在值也返回 false

如果传入的 key 存在，但没有值，则更新他的值

如果传入的 key 不存在，则创建并更新他的值

那么只需要遍历 key 的每一个字符串，并使用函数 GetChildNode(key[i]); 获取是否存在该 key[i]

auto tmp = new_children->get()->GetChildNode(key[i]);

如果存在，那么就把该 k[i] 的节点给保存，以便下一次循环使用

如果不存在，则创建该节点

tmp = new_children->get()->InsertChildNode(key[i], std::make_unique<TrieNode>(key[i]));

但是注意，只能遍历到倒数第二个字符，因为最后一个字符需要单独判断以下两种情况

最后一个字符节点存在，那么只需要判断 is_end_ 该变量是否是可赋值状态
auto q = new TrieNodeWithValue<T>(std::move(*(cur->get())), value);
cur->reset(q);
创建一个新的节点，然后使用原来节点 cur->reset() 重新指向新的节点即完成值的更新

如果不存在，那么就直接创建并插入该节点，并赋值

new_children->get()->InsertChildNode(key[l - 1], std::make_unique<TrieNodeWithValue<T>>(key[l - 1], value));

# GetValue

该函数是为了获取传入 key 的值，只需要遍历 key 的每一个字符即可，如果其中任意一个字符不存在，则返回空

因为遍历的是基类 TrieNode , 而值存在子类 TrieNodeWithValue 当中，存在从基类向子类进行向下强制转换关系，使用 dynamic_cast<TrieNodeWithValue<T> *> 函数进行强制类型转换

eg：基类向子类向下强制转换需要要求基类必须存在虚函数，原因可以看我另一篇博客

auto cur = dynamic_cast<TrieNodeWithValue<T> *>(tmp->get());

# RemoveTest

该函数是为了测试删除某一个键

如果需要删除的键的最后一个字符还存在子节点，那么则不可以删除该节点，只需要把 is_end 置为 false 即可，下次在插入的时候就可以重新赋值

	if (node->get()->HasChildren()) {
	node->get()->SetEndNode(false);
	}

否则，则依次递归从最后一个字符开始删除，每一次删除该字符前都需要先判断是否存在其他子节点

	if (node->get()->HasChildren()) {
	break;
	}

递归的方法可以使用遍历该键的每一个字符，并获取该节点，然后保存到栈或者容器当中，在删除时候从最后一个节点从后往前遍历，然后依次重复上述两个判断即可

	for (auto i : key) {
	tmp.emplace_back(node);
	auto next = node->get()->GetChildNode(i);
	if (next == nullptr) {
	return false;
	}
	node = next;
	}

依次存入 tmp 当中，如果中途出现任何一个字符没有节点则直接返回 false，删除失败

	tmp[i]->get()->RemoveChildNode(key[i]);
	node = tmp[i];

调用 RemoveChildNode 函数删除，并保存上一个节点的值

# ConcurrentTest1

该函数主要是测试多线程情况下的增删节点

按照多线程的处理方法在共享数据的地方加入 latch_.WLock(); 和 latch_.WUnlock(); 即可

在函数返回的时候别忘记解锁

	auto q = new TrieNodeWithValue<T>(std::move(*(cur->get())), value);
	cur->reset(q);