2022_CMU15445_lab0笔记(Trie)

预备工作

环境我在windows wsl2中使用docker, docker是编译环境, wsl是编码环境，用共享目录的形式将docker目录和wsl2关联, 用vscode编码

剩下的环境配置直接参考https://github.com/cmu-db/bustub ,

系统环境使用ubuntu20.04LTS, 不要使用以下的版本
需要安装的工具

  apt-get -y update
  # Install packages.
  apt-get -y install \
      build-essential \
      clang-12 \
      clang-format-12 \
      clang-tidy-12 \
      cmake \
      doxygen \
      git \
      g++-12 \
      pkg-config \
      zlib1g-dev

题目，https://15445.courses.cs.cmu.edu/fall2022/project0/

实现Trie, 做lab前可以先做leetcode208:Implement Trie
https://leetcode.com/problems/implement-trie-prefix-tree/

实现

有三个class,

class TrieNode {
// 成员
 protected:
  /** Key character of this trie node */
  char key_char_;
  /** whether this node marks the end of a key */
  bool is_end_{false};
  /** A map of all child nodes of this trie node, which can be accessed by each
   * child node's key char. */
  std::unordered_map<char, std::unique_ptr<TrieNode>> children_;
}

template <typename T>
class TrieNodeWithValue : public TrieNode {
 private:
  /* Value held by this trie node. */
  T value_;
};

class Trie class Trie {
 private:
  /* Root node of the trie */
  std::unique_ptr<TrieNode> root_;
  /* Read-write lock for the trie */
  ReaderWriterLatch latch_;
};

• TrieNode

TrieNode 是一般的Trie节点，排布根据key的前缀字符串，需要注意的点

1. 移动构造函数

  TrieNode(TrieNode &&other_trie_node) noexcept
      : key_char_(other_trie_node.key_char_),
        is_end_(other_trie_node.is_end_),
        children_(std::move(other_trie_node.children_)) {}

2. InsertChildNode

意思是将TrieNode child插入到当前节点的children中, 如果children中的key_char存在, 则不能插入

（这个一开始半天才理解）

  auto InsertChildNode(char key_char, std::unique_ptr<TrieNode> &&child) -> std::unique_ptr<TrieNode> * {
    if (children_.count(key_char) > 0 || child->GetKeyChar() != key_char) {
      return nullptr;
    }
    children_[key_char] = std::move(child);
    return &children_[key_char];
  }

3. 智能指针对象的指针

使用智能指针对象的指针，既保证维护的对象析构，多线程安全，又提高了效率。在lab中经常使用

  auto GetChildNode(char key_char) -> std::unique_ptr<TrieNode> * {
    if (children_.count(key_char) == 0) {
      return nullptr;
    }
    return &children_[key_char];
  }

• TrieNodeWithValue

TrieNodeWithValue单指含有value的TrieNode, 也就是is_end为True的TrieNode, 因此构造函数会设置好SetEndNode(true)

TrieNodeWithValue(TrieNode &&trieNode, T value) : TrieNode(std::move(trieNode)), value_(value) { SetEndNode(true); }

另外注意TrieNodeWithValue是模板类，表示value的类型可以泛型，但key只能是string

• Trie

ReaderWriterLatch latch_;是读写锁, 实现如下

/**
 * Reader-Writer latch backed by std::mutex.
 */
class ReaderWriterLatch {
 public:
  /**
   * Acquire a write latch.
   */
  void WLock() { mutex_.lock(); }

  /**
   * Release a write latch.
   */
  void WUnlock() { mutex_.unlock(); }

  /**
   * Acquire a read latch.
   */
  void RLock() { mutex_.lock_shared(); }

  /**
   * Release a read latch.
   */
  void RUnlock() { mutex_.unlock_shared(); }

 private:
  std::shared_mutex mutex_;
};

Insert函数实现注意

  template <typename T>
  auto Insert(const std::string &key, T value) -> bool {
    auto *current = &root_;
    ...
  // current已经指向最后包含value的TrieNodeWithValue节点
    if (current == nullptr) {  // 不存在节点
      *current = std::make_unique<TrieNodeWithValue<T>>(key[idx], value);
      return true;
    }
    if (current->get()->IsEndNode()) {  // 已经存在TrieNode且该TrieNode是key的结尾, 因为key不能重复插入失败
      return false;
    }
    if (dynamic_cast<TrieNodeWithValue<T> *>(current->get()) == nullptr) {  // 已经存在TrieNode, 但该TrieNode并不是key的结尾, 换言之不是TrieNodeWithValue<T>对象
      *current = std::make_unique<TrieNodeWithValue<T>>(std::move(*(current->get())), value);
      return true;
    }
    return false;
}

GetValue函数实现注意

  template <typename T>
  auto GetValue(const std::string &key, bool *success) -> T {
    // LOG_INFO("# Trie::GetValue: %s", key.data());
    ...
    // current目前到达key的最后一个字符
    if (!current->get()->IsEndNode()) {
      // *success = false;
      return {};
    }
    // current应该可以dynamic_cast成TrieNodeWithValue<T>
    // 这里如果current指向TrieNodeWithValue<string> 但T这里是int, 也是会转型失败的，且在编译期就能发现错误
    auto* ret_value = dynamic_cast<TrieNodeWithValue<T> *>(current->get());
    if (ret_value == nullptr) {
      return {};
    }
    *success = true;
    return ret_value->GetValue();
  }

Remove函数实现注意, 比较复杂, 需要递归实现

// 递归函数
void RemoveNode(const std::string &key, bool *isfind, size_t idx, std::unique_ptr<TrieNode> *parent) {
    if (!*isfind) {  // 如果没有找到key
      if (idx >= key.size() || !parent->get()->HasChild(key[idx])) {
        return;
      }
      if (idx == key.size() - 1 && parent->get()->GetChildNode(key[idx])->get()->IsEndNode()) {
        *isfind = true;
      } else {
        RemoveNode(key, isfind, idx + 1, parent->get()->GetChildNode(key[idx]));
      }
    }
    if (*isfind) {  // 已经找到了key
      if (idx == key.size() - 1) {
        if (!parent->get()->GetChildNode(key[idx])->get()->HasChildren()) {
          parent->get()->RemoveChildNode(key[idx]);
        } else {
          parent->get()->GetChildNode(key[idx])->get()->SetEndNode(false);
        }
      } else {
        if (!parent->get()->GetChildNode(key[idx])->get()->IsEndNode() &&
            !parent->get()->GetChildNode(key[idx])->get()->HasChildren()) {
          parent->get()->RemoveChildNode(key[idx]);
        }
      }
    }
  }

测试结果

我又添加了几个case