P0 - C++ Primer

Problem Description

在這個 project 中，我們需要實現一個 key-value store 的 copy-on-write 的 trie 並練習使用 debugger，總共有 4 個 Task :

Copy-On-Write Trie : 修改 /src/primer/trie.cpp 來實現一個 copy-on-write trie，有 GET、PUT、DELETE 三個操作。
Concurrent Key-Value Store : 修改 /src/primer/trie_store.cpp 來將原本 single-thread 的 trie 改成 concurrent 的版本，一樣有 GET、PUT、DELETE 三個操作。
Debugging : 在 /test/primer/trie_debug_test.cpp 中練習使用 debugger 來 debug，並在 /src/include/primer/trie_answer.h 中填入答案。
SQL String Functions : 在 src/execution/expressions/string_expression.h 和 src/planner/plan_func_call 中實現 lower 和 upper 兩個 SQL function。

Learning Resource

15-445 Bootcamp : 課程提供的一個簡單 bootcamp，裡面有一些範例程式碼
Debug a C++ project in VS Code : 在 VSCode 中 debug 的教學
CMake : CMake 的簡易教學
智慧指標、移動語意、同步原語 : 自己寫的 C++ 筆記

Environment Setup

我使用的環境是 WSL (Ubuntu 22.04) 和 VSCode
安裝 VSCode 套件 C/C++ Extension Pack 跟 clangd
將 bustub clone 下來，並且回退到 2023 Fall 的 commit，建議至少回退到 2023 12/27 的 add request signature script (#674)
安裝 package 並編譯 :

sudo build_support/packages.sh

mkdir build
cd build
cmake -DCMAKE_BUILD_TYPE=Debug ..
make -j`nproc`

如果出現 compiler 的版本警告，可以將 cmake 改成以下指令 :

cmake -DCMAKE_BUILD_TYPE=Release -DCMAKE_C_COMPILER=/usr/bin/clang-14 -DCMAKE_CXX_COMPILER=/usr/bin/clang++-14 ..

安裝 clangd (通常 VSCode 會提示安裝)
設定 formatter，這樣就可以在 save 的時候自動格式化 :

.vscode/settings.json
{
  "C_Cpp.clang_format_path": "/usr/bin/clang-format-14",
  "C_Cpp.formatting": "clangFormat",
  "C_Cpp.clang_format_style": "file",
  "editor.formatOnSave": true
}

接著設定 debugger，我使用的 debugger 是 GDB

sudo apt install gdb

以下這個設定可以幫助我們顯示 STL 容器的內容 :

.vscode/launch.json
{
  "version": "0.2.0",
  "configurations": [
    {
      "name": "C/C++: g++ build and debug active file",
      "type": "cppdbg",
      "request": "launch",
      "program": "${workspaceFolder}/build/test/${fileBasenameNoExtension}",
      "args": [],
      "cwd": "${workspaceFolder}",
      "stopAtEntry": false,
      "MIMode": "gdb",
      "miDebuggerPath": "/usr/bin/gdb",
      "setupCommands": [
        {
          "description": "Test",
          "text": "python import sys;sys.path.insert(0, '/usr/share/gcc/python');from libstdcxx.v6.printers import register_libstdcxx_printers;register_libstdcxx_printers(None)",
          "ignoreFailures": false
        },
        {
          "description": "Enable pretty-printing for gdb",
          "text": "-enable-pretty-printing",
          "ignoreFailures": true
        }
      ]
    }
  ]
}

Solution

Copy-On-Write Trie

GET : 需要處理 root 是 nullptr 的情況，其餘的情況就是從 root 開始往下找，最後用 dynamic_cast 來轉型。
PUT : 需要處理 key 是空的情況 (在 root 上直接插入)，其餘的情況就是從 root 開始往下找，並新增一個 TrieNodeWithValue。
DELETE : 需要先遍歷到要刪除的 node，並記錄中途經過的 node，最後再沿途刪除沒有 value 的 node，我的方法是使用 std::stack 來記錄。

接著在本地進行 trie_test 的單元測試 :

cd build
make trie_test trie_noncopy_test -j$(nproc)

./test/trie_test
./test/trie_noncopy_test

Concurrent Key-Value Store

GET : 使用 lock_guard 來獲取 root_lock_，並依據是否有這個 key 來決定要回傳 nullptr 或是 ValueGuard。
PUT : 使用 lock_guard 來獲取全局的 write_lock，並獲取 root_lock 來讀取 root 和寫入。
DELETE : 與 PUT 類似，也是使用 lock_guard 來獲取全局的 write_lock，並獲取 root_lock 來讀取 root 和刪除。

接著在本地進行 trie_store_test 的單元測試 :

cd build
make trie_store_test trie_store_noncopy_test -j$(nproc)

./test/trie_store_test
./test/trie_store_noncopy_test

Debugging

可以直接在 debugger 中看出答案，如下 :

SQL String Functions

在 string_expression.h 中依據 expr_type 來判斷要執行哪個 function，並使用 std::transform 來將字串轉換成大寫或小寫。

在 plan_func_call.cpp 中依據 func_name 和參數數量來判斷要執行哪個 function。

可以直接使用 shell 來測試，會顯示錯誤是正常的 :

cd build
make -j`nproc` shell

./bin/bustub-shell

select upper('AbCd'), lower('AbCd');
+-------------+-------------+
| __unnamed#0 | __unnamed#1 |
+-------------+-------------+
| ABCD        | abcd        |
+-------------+-------------+

同樣可以進行單元測試 :

make -j`nproc` sqllogictest

./bin/bustub-sqllogictest ../test/sql/p0.01-lower-upper.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p0.02-function-error.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p0.03-string-scan.slt --verbose

Submit

如果要註冊 GradeScope，可以參考這個網站

首先修改 CMakeLists.txt，將 P0_FILES 設定為以下 (需要重新執行 cmake 指令來更新 makefile):

CMakeLists.txt
set(P0_FILES
        "src/include/primer/trie_answer.h"
        "src/include/primer/trie_store.h"
        "src/include/primer/trie.h"
        "src/primer/trie_store.cpp"
        "src/primer/trie.cpp"
        "src/planner/plan_func_call.cpp"
        "src/include/execution/expressions/string_expression.h"
        "GRADESCOPE.md"
)

進行排版，確定消除所有 error 和 warning (特別是 check-clang-tidy-p0):

make format
make check-lint
make check-clang-tidy-p0

簽名，會產生一個 GRADESCOPE.md :

python3 gradescope_sign.py

繳交作業，可能需要先執行 sudo apt-get install zip 來安裝 zip，然後執行以下指令 :

make submit-p0

上傳 .zip 檔到 GradeScope

Problem Description​

Learning Resource​

Environment Setup​

Solution​

Copy-On-Write Trie​

Concurrent Key-Value Store​

Debugging​

SQL String Functions​

Submit​