# 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

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

image-20230428153407457

完整代码查看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(); 即可

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

image-20230428180714737

阅读次数

请我喝[茶]~( ̄▽ ̄)~*

Charmber 微信支付

微信支付

Charmber 支付宝

支付宝

Charmber 贝宝

贝宝