2022 CMU15-445 Project0 Trie

通过截图

在线测试

本地测试

总览

代码风格

我们的代码必须遵循 Google C++ Style Guide。在线检测网站使用 Clang 自动检查源代码的质量。如果我们的提交未通过任何这些检查，您的项目成绩将为零。
对于 Google C++ Style Guide ，我们可以看这里 google-styleguide
对于如何测试，我们可以在 build 目录下，执行以下代码

$ make format
$ make check-lint
$ make check-clang-tidy-p0
1
2
3

以下命令会提示你哪里需要修正，但这不重要，我们先得实现功能，然后再去改这些，这里推荐 vscode 一键格式化代码，把风格设置为 Google，可以避免很多麻烦。

如何测试

test/primer/starter_test.cpp：测试代码
src/include/primer/p0_starter.h：实现代码
1
2

本地测试

我们先需要取把测试代码中的 DISABLED_ 前缀去掉，直接查找替换很快的。
在主目录下：

cd build
make starter_trie_test
./test/starter_trie_test
1
2
3

便可看见 project0的本地测试结果

在线测试

登录 https://www.gradescope.com/
注册
入口代码：PXWVR5
学校选 Carnegie Mellon University
还有一些问题可以看这里 https://15445.courses.cs.cmu.edu/fall2022/faq.html
登录进去大概你们就知道怎么测试了，总之在线测试比本地测试更加严格！但是在线测试毕竟没有本地测试那么方便，我们可以根据一些技巧将在线测试集拉下来。
这是这位大佬发出来的：https://blog.csdn.net/freedom1523646952/article/details/122274850

#pragma once
#include 
#include 
#include 
#include 

void GetTestFileContent() {
  static bool first_enter = true;
  if (first_enter) {
    //  截取gradescope日志输出文件名
    /*
    std::vector all_filenames = {
        "/autograder/bustub/test/primer/grading_starter_test.cpp",
        "/autograder/bustub/test/execution/grading_update_executor_test.cpp",
        "/autograder/bustub/test/execution/grading_nested_loop_join_executor_test.cpp",
        "/autograder/bustub/test/execution/grading_limit_executor_test.cpp",
        "/autograder/bustub/test/execution/grading_executor_benchmark_test.cpp",
        "/autograder/bustub/test/concurrency/grading_lock_manager_3_test.cpp",
        "/autograder/bustub/test/buffer/grading_parallel_buffer_pool_manager_test.cpp",
        "/autograder/bustub/test/buffer/grading_lru_replacer_test.cpp",
        "/autograder/bustub/test/execution/grading_executor_integrated_test.cpp",
        "/autograder/bustub/test/execution/grading_sequential_scan_executor_test.cpp",
        "/autograder/bustub/test/concurrency/grading_lock_manager_1_test.cpp",
        "/autograder/bustub/test/execution/grading_distinct_executor_test.cpp",
        "/autograder/bustub/test/buffer/grading_buffer_pool_manager_instance_test.cpp",
        "/autograder/bustub/test/concurrency/grading_lock_manager_2_test.cpp",
        "/autograder/bustub/test/concurrency/grading_transaction_test.cpp",
        "/autograder/bustub/test/buffer/grading_leaderboard_test.cpp",
        "/autograder/bustub/test/container/grading_hash_table_verification_test.cpp",
        "/autograder/bustub/test/concurrency/grading_rollback_test.cpp",
        "/autograder/bustub/test/container/grading_hash_table_concurrent_test.cpp",
        "/autograder/bustub/test/container/grading_hash_table_page_test.cpp",
        "/autograder/bustub/test/concurrency/grading_lock_manager_detection_test.cpp",
        "/autograder/bustub/test/container/grading_hash_table_leaderboard_test.cpp",
        "/autograder/bustub/test/container/grading_hash_table_scale_test.cpp",
        "/autograder/bustub/test/container/grading_hash_table_test.cpp",
        "/autograder/bustub/test/execution/grading_aggregation_executor_test.cpp",
        "/autograder/bustub/test/execution/grading_insert_executor_test.cpp",
        "/autograder/bustub/test/execution/grading_delete_executor_test.cpp",
        "/autograder/bustub/test/execution/grading_hash_join_executor_test.cpp"
        "/autograder/bustub/test/execution/grading_sequential_scan_executor_test.cpp",
        "/autograder/bustub/test/execution/grading_update_executor_test.cpp",
        "/autograder/bustub/test/execution/grading_executor_test_util.h",
        "/autograder/bustub/src/include/execution/plans/mock_scan_plan.h",
        };
    */
    std::vector<std::string> filenames = {
        "/autograder/bustub/test/execution/grading_executor_integrated_test.cpp",
        "/autograder/bustub/test/execution/grading_executor_benchmark_test.cpp",
    };
    std::ifstream fin;
    for (const std::string &filename : filenames) {
      fin.open(filename, std::ios::in);
      if (!fin.is_open()) {
        std::cout << "cannot open the file:" << filename << std::endl;
        continue;
      }
      char buf[200] = {0};
      std::cout << filename << std::endl;
      while (fin.getline(buf, sizeof(buf))) {
        std::cout << buf << std::endl;
      }
      fin.close();
    }
    first_enter = false;
  }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

我们可以将它插入到我们的测试文件，filenames 写在线测试集文件的位置信息，这个一般在你提交一次后的报错信息中会有，然后就可以得到测试文件了，复制下来替换本地测试文件便可接着 Debug。

Trie

注意事项

Trie 也叫字典树，讲解我主要看的是这个：https://zhuanlan.zhihu.com/p/67431582
官方讲解也很重要：
https://15445.courses.cs.cmu.edu/fall2022/project0/
然后便可以根据每个函数上面的 TODO 提示，进行Coding了。
这里讲几个我碰到的点：

1. 不需要再添加成员变量了，文件中已经提供了所需要的文件。
2. vscode 远程开发不会提示报错，所以需要经常执行测试文件进行查看哪里出错。
3. 当传入参数为指针，且为判断标志的变量，在函数初始时应该初始化为 false，当满足条件的时候才能返回 true
4. 对 unique_ptr 可以采用 get 成员函数增加美观性
5. 寻找目标 value 时，不要光看是不是 endNode，也要看 key 是否对应。

代码实现

// ===----------------------------------------------------------------------===//
//
//                          BusTub
//
//  p0_trie.h
//
//  Identification: src/include/primer/p0_trie.h
//
//  Copyright (c) 2015-2022, Carnegie Mellon University Database Group
//
// ===----------------------------------------------------------------------===//

#pragma once

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include "common/exception.h"
#include "common/rwlatch.h"

namespace bustub {
/**
 * TrieNode is a generic container for any node in Trie.
 */
class TrieNode {
 public:
  /**
   * TODO(P0): Add implementation
   *
   * @brief Construct a new Trie Node object with the given key char.
   * is_end_ flag should be initialized to false in this constructor.
   *
   * @param key_char Key character of this trie node
   */
  explicit TrieNode(char key_char) {
    this->key_char_ = key_char;
    this->is_end_ = false;
    this->children_.clear();
  }

  /**
   * TODO(P0): Add implementation
   *
   * @brief Move constructor for trie node object. The unique pointers stored
   * in children_ should be moved from other_trie_node to new trie node.
   *
   * @param other_trie_node Old trie node.
   */

  TrieNode(TrieNode &&other_trie_node) noexcept {
    this->key_char_ = other_trie_node.key_char_;
    this->is_end_ = other_trie_node.is_end_;
    this->children_.swap(other_trie_node.children_);
  }

  /**
   * @brief Destroy the TrieNode object.
   */
  virtual ~TrieNode() = default;

  /**
   * TODO(P0): Add implementation
   *
   * @brief Whether this trie node has a child node with specified key char.
   *
   * @param key_char Key char of child node.
   * @return True if this trie node has a child with given key, false otherwise.
   */
  bool HasChild(char key_char) const { return children_.find(key_char) != children_.end(); }

  /**
   * TODO(P0): Add implementation
   *
   * @brief Whether this trie node has any children at all. This is useful
   * when implementing 'Remove' functionality.
   *
   * @return True if this trie node has any child node, false if it has no child node.
   */
  bool HasChildren() const { return !children_.empty(); }

  /**
   * TODO(P0): Add implementation
   *
   * @brief Whether this trie node is the ending character of a key string.
   *
   * @return True if is_end_ flag is true, false if is_end_ is false.
   */
  bool IsEndNode() const { return this->is_end_; }

  /**
   * TODO(P0): Add implementation
   *
   * @brief Return key char of this trie node.
   *
   * @return key_char_ of this trie node.
   */
  char GetKeyChar() const { return this->key_char_; }

  /**
   * TODO(P0): Add implementation
   *
   * @brief Insert a child node for this trie node into children_ map, given the key char and
   * unique_ptr of the child node. If specified key_char already exists in children_,
   * return nullptr. If parameter `child`'s key char is different than parameter
   * `key_char`, return nullptr.
   *
   * Note that parameter `child` is rvalue and should be moved when it is
   * inserted into children_map.
   *
   * The return value is a pointer to unique_ptr because pointer to unique_ptr can access the
   * underlying data without taking ownership of the unique_ptr. Further, we can set the return
   * value to nullptr when error occurs.
   *
   * @param key Key of child node
   * @param child Unique pointer created for the child node. This should be added to children_ map.
   * @return Pointer to unique_ptr of the inserted child node. If insertion fails, return nullptr.
   */
  std::unique_ptr<TrieNode> *InsertChildNode(char key_char, std::unique_ptr<TrieNode> &&child) {
    if (HasChild(key_char) || key_char != child->key_char_) {
      return nullptr;
    }
    children_[key_char] = std::forward<std::unique_ptr<TrieNode>>(child);
    return &children_[key_char];
  }

  /**
   * TODO(P0): Add implementation
   *
   * @brief Get the child node given its key char. If child node for given key char does
   * not exist, return nullptr.
   *
   * @param key Key of child node
   * @return Pointer to unique_ptr of the child node, nullptr if child
   *         node does not exist.
   */
  std::unique_ptr<TrieNode> *GetChildNode(char key_char) {
    auto node = children_.find(key_char);
    if (node != children_.end()) {
      return &(node->second);
    }
    return nullptr;
  }

  /**
   * TODO(P0): Add implementation
   *
   * @brief Remove child node from children_ map.
   * If key_char does not exist in children_, return immediately.
   *
   * @param key_char Key char of child node to be removed
   */
  void RemoveChildNode(char key_char) {
    auto node = children_.find(key_char);
    if (node != children_.end()) {
      children_.erase(key_char);
    }
  }

  /**
   * TODO(P0): Add implementation
   *
   * @brief Set the is_end_ flag to true or false.
   *
   * @param is_end Whether this trie node is ending char of a key string
   */
  void SetEndNode(bool is_end) { this->is_end_ = is_end; }

 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_;
};

/**
 * TrieNodeWithValue is a node that mark the ending of a key, and it can
 * hold a value of any type T.
 */
template <typename T>
class TrieNodeWithValue : public TrieNode {
 private:
  /* Value held by this trie node. */
  T value_;

 public:
  /**
   * TODO(P0): Add implementation
   *
   * @brief Construct a new TrieNodeWithValue object from a TrieNode object and specify its value.
   * This is used when a non-terminal TrieNode is converted to terminal TrieNodeWithValue.
   *
   * The children_ map of TrieNode should be moved to the new TrieNodeWithValue object.
   * Since it contains unique pointers, the first parameter is a rvalue reference.
   *
   * You should:
   * 1) invoke TrieNode's move constructor to move data from TrieNode to
   * TrieNodeWithValue.
   * 2) set value_ member variable of this node to parameter `value`.
   * 3) set is_end_ to true
   *
   * @param trieNode TrieNode whose data is to be moved to TrieNodeWithValue
   * @param value
   */
  TrieNodeWithValue(TrieNode &&trieNode, T value) : TrieNode(std::forward<TrieNode>(trieNode)) {
    this->value_ = value;
    SetEndNode(true);
  }

  /**
   * TODO(P0): Add implementation
   *
   * @brief Construct a new TrieNodeWithValue. This is used when a new terminal node is constructed.
   *
   * You should:
   * 1) Invoke the constructor for TrieNode with given key_char.
   * 2) Set value_ for this node.
   * 3) set is_end_ to true.
   *
   * @param key_char Key char of this node
   * @param value Value of this node
   */
  TrieNodeWithValue(char key_char, T value) : TrieNode(key_char) {
    this->value_ = value;
    SetEndNode(true);
  }

  /**
   * @brief Destroy the Trie Node With Value object
   */
  ~TrieNodeWithValue() override = default;

  /**
   * @brief Get the stored value_.
   *
   * @return Value of type T stored in this node
   */
  T GetValue() const { return value_; }
};

/**
 * Trie is a concurrent key-value store. Each key is string and its corresponding
 * value can be any type.
 */
class Trie {
 private:
  /* Root node of the trie */
  std::unique_ptr<TrieNode> root_;
  /* Read-write lock for the trie */
  ReaderWriterLatch latch_;

 public:
  /**
   * TODO(P0): Add implementation
   *
   * @brief Construct a new Trie object. Initialize the root node with '\0'
   * character.
   */
  Trie() {
    auto *root = new TrieNode('\0');
    root_.reset(root);
  }

  /**
   * TODO(P0): Add implementation
   *
   * @brief Insert key-value pair into the trie.
   *
   * If key is empty string, return false immediately.
   *
   * If key alreadys exists, return false. Duplicated keys are not allowed and
   * you should never overwrite value of an existing key.
   *
   * When you reach the ending character of a key:
   * 1. If TrieNode with this ending character does not exist, create new TrieNodeWithValue
   * and add it to parent node's children_ map.
   * 2. If the terminal node is a TrieNode, then convert it into TrieNodeWithValue by
   * invoking the appropriate constructor.
   * 3. If it is already a TrieNodeWithValue,
   * then insertion fails and return false. Do not overwrite existing data with new data.
   *
   * You can quickly check whether a TrieNode pointer holds TrieNode or TrieNodeWithValue
   * by checking the is_end_ flag. If is_end_ == false, then it points to TrieNode. If
   * is_end_ == true, it points to TrieNodeWithValue.
   *
   * @param key Key used to traverse the trie and find correct node
   * @param value Value to be inserted
   * @return True if insertion succeeds, false if key already exists
   */
  template <typename T>
  bool Insert(const std::string &key, T value) {
    if (key.empty()) {
      return false;
    }
    latch_.WLock();
    auto c = key.begin();
    auto pre_child = &root_;
    while (c != key.end()) {
      auto cur = c++;
      // 若当前节点将为 end 节点，跳出循环进行特殊处理
      if (c == key.end()) {
        break;
      }

      // 如果该字符不存在 则直接创建
      if (!pre_child->get()->HasChild(*cur)) {
        pre_child = pre_child->get()->InsertChildNode(*cur, std::make_unique<TrieNode>(*cur));
      } else {
        // 存在则直接跳过
        pre_child = pre_child->get()->GetChildNode(*cur);
      }
    }

    // 此时c为end 退回一个
    c--;

    auto end_node = pre_child->get()->GetChildNode(*c);
    // 若最后一个节点存在，且已经为 end 则插入失败
    if (end_node != nullptr && end_node->get()->IsEndNode()) {
      latch_.WUnlock();
      return false;
    }
    // 若最后一个节点存在，且不为 end 则转为 TrieNodeWithValue
    if (end_node != nullptr) {
      auto new_node = new TrieNodeWithValue(std::move(**end_node), value);
      end_node->reset(new_node);
      latch_.WUnlock();
      return true;
    }
    //  节点不存在，则直接插入
    pre_child = pre_child->get()->InsertChildNode(*c, std::make_unique<TrieNode>(*c));
    auto new_node = new TrieNodeWithValue(std::move(**pre_child), value);
    pre_child->reset(new_node);
    latch_.WUnlock();
    return true;
  }

  /**
   * TODO(P0): Add implementation
   *
   * @brief Remove key value pair from the trie.
   * This function should also remove nodes that are no longer part of another
   * key. If key is empty or not found, return false.
   *
   * You should:
   * 1) Find the terminal node for the given key.
   * 2) If this terminal node does not have any children, remove it from its
   * parent's children_ map.
   * 3) Recursively remove nodes that have no children and is not terminal node
   * of another key.
   *
   * @param key Key used to traverse the trie and find correct node
   * @return True if key exists and is removed, false otherwise
   */
  bool Remove(const std::string &key) {
    // 为空返回
    if (key.empty()) {
      return false;
    }
    latch_.WLock();
    // 含义为，第二个元素 TrieNode 需要删除 keyChar 等于第一个元素的节点
    std::stack<std::tuple<char, std::unique_ptr<TrieNode> *>> s;
    auto c = key.begin();
    auto pre_child = &root_;
    while (c != key.end()) {
      auto cur = c++;
      if (pre_child->get()->HasChild(*cur)) {
        s.push(std::make_tuple(*cur, pre_child));
        // 到下一个 key
        pre_child = pre_child->get()->GetChildNode(*cur);
        continue;
      }
      // 存在key没有的现象
      latch_.WUnlock();
      return false;
    }

    // 开始删除
    while (!s.empty()) {
      std::tuple<char, std::unique_ptr<TrieNode> *> temp = s.top();
      s.pop();
      auto key = std::get<0>(temp);
      auto del_node = std::get<1>(temp);
      // 若被删除的节点没有孩子，则可以直接删除
      auto flag = (*del_node)->GetChildNode(key);
      if (flag != nullptr && (*flag)->HasChildren()) {
        continue;
      }
      (*del_node)->RemoveChildNode(key);
    }
    latch_.WUnlock();

    return true;
  }

  /**
   * TODO(P0): Add implementation
   *
   * @brief Get the corresponding value of type T given its key.
   * If key is empty, set success to false.
   * If key does not exist in trie, set success to false.
   * If given type T is not the same as the value type stored in TrieNodeWithValue
   * (ie. GetValue is called but terminal node holds std::string),
   * set success to false.
   *
   * To check whether the two types are the same, dynamic_cast
   * the terminal TrieNode to TrieNodeWithValue. If the casted result
   * is not nullptr, then type T is the correct type.
   *
   * @param key Key used to traverse the trie and find correct node
   * @param success Whether GetValue is successful or not
   * @return Value of type T if type matches
   */
  template <typename T>
  T GetValue(const std::string &key, bool *success) {
    // 这个初始化很重要，如果没有找到就直接返回 false,卡这里好久
    *success = false;
    latch_.RLock();

    auto pre_child = &root_;
    auto c = key.begin();
    while (c != key.end()) {
      auto cur = c++;
      auto next_node = pre_child->get()->GetChildNode(*cur);

      if (!next_node) {
        *success = false;
        break;
      }
      // 若是目标尾节点，返回值
      // 这里犯了个错，并非只要是 end 节点就是所需要的节点，key也得对，所以要 key == end 时
      if (next_node->get()->IsEndNode() && c == key.end()) {
        // 若所需要类型和存储的类型不同也失败
        auto flag_node = dynamic_cast<TrieNodeWithValue<T> *>(next_node->get());
        if (!flag_node) {
          *success = false;
          break;
        }
        *success = true;
        latch_.RUnlock();
        return flag_node->GetValue();
      }
      // 切换到下个
      pre_child = next_node;
    }
    latch_.RUnlock();
    return {};
  }
};
}  //  namespace bustub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458