2018q1 Homework3 (prefix-search) === contributed by <`blake11235`> --- ## 系統環境 ``` $ lscpu Architecture: x86_64 CPU 作業模式： 32-bit, 64-bit Byte Order: Little Endian CPU(s): 4 On-line CPU(s) list: 0-3 每核心執行緒數：1 每通訊端核心數：4 Socket(s): 1 NUMA 節點： 1 供應商識別號： GenuineIntel CPU 家族： 6 型號： 158 Model name: Intel(R) Core(TM) i5-7300HQ CPU @ 2.50GHz 製程： 9 CPU MHz： 800.000 CPU max MHz: 3500.0000 CPU min MHz: 800.0000 BogoMIPS: 4991.82 虛擬： VT-x L1d 快取： 32K L1i 快取： 32K L2 快取： 256K L3 快取： 6144K NUMA node0 CPU(s): 0-3 ``` --- ## Ternary Search Tree * 感謝 <[`rex662624`](https://hackmd.io/K4v3wF-8SFudCT2-ckK9Hg?view#%E4%BD%95%E8%AC%82-Ternary-search-tree)> 的詳細介紹 * [Trie](https://zh.wikipedia.org/wiki/Trie) --- ## 原程式碼 BUG 在做程式碼測試時，意外發現了一個奇怪的問題 ``` Commands: a add word to the tree f find word in tree s search words matching prefix d delete word from the tree q quit, freeing all data choice: d enter word to del: qq deleting qq delete failed. Commands: a add word to the tree f find word in tree s search words matching prefix d delete word from the tree q quit, freeing all data choice: f find word in tree: qq found qq in 0.000003 sec. ``` **若是刪除原本不存在的字串時，會直接變成輸入字串** 原來也有其他人發現了[一樣的問題](https://hackmd.io/s/rJd31ZRYz#Prefix-%E7%BC%BA%E9%99%B7) 解決方式其實不難，只要多一個條件判斷就可以了 ``` if(del) return"" ``` 放在 tst_ins_del() 裡面 ...結果反而延伸出另一個問題，程式可以刪除不存在的字了... :::danger how to fix it ? ::: ## test_ref.c 程式碼分析與修改 首先找到在 test_ref.c FIXME 的部份，修改程式內容 ```=c /* FIXME: insert reference to each string */ if (!tst_ins_del(&root, &p, INS, CPY)) { fprintf(stderr, "error: memory exhausted, tst_insert.\n"); fclose(fp); return 1; } ``` 由於要分析 CPY 和 REF 的不同，在有 `tst_ins_del()` 函式的地方進行修改 ```=c - tst_ins_del(&root, &p, INS, CPY) + tst_ins_del(&root, &p, INS, REF) ``` 結果 make 之後出現了幾個問題 * s serach words matching prefix ``` find words matching prefix (at least 1 char): Tai Tai - searched prefix in 0.000515 sec suggest[0] : Tai suggest[1] : Tai suggest[2] : Tai suggest[3] : Tai suggest[4] : Tai suggest[5] : Tai ... ``` 使用 prefix search 時無法正確找到 * d delete words from tree ``` *** Error in `./test_ref': free(): invalid pointer: 0x00007fffa910a720 *** ======= Backtrace: ========= /lib/x86_64-linux-gnu/libc.so.6(+0x777e5)[0x7f6bbaeea7e5] /lib/x86_64-linux-gnu/libc.so.6(+0x8037a)[0x7f6bbaef337a] /lib/x86_64-linux-gnu/libc.so.6(cfree+0x4c)[0x7f6bbaef753c] ./test_ref[0x4012b6] ./test_ref[0x4019d8] ./test_ref[0x4010e4] /lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf0)[0x7f6bbae93830] ./test_ref[0x4008e9] ``` 刪除字的時候會 core dumped * q quit, free all data ``` *** Error in `./test_ref': free(): invalid pointer: 0x00007ffe279ca700 *** ======= Backtrace: ========= /lib/x86_64-linux-gnu/libc.so.6(+0x777e5)[0x7fe95af287e5] /lib/x86_64-linux-gnu/libc.so.6(+0x8037a)[0x7fe95af3137a] /lib/x86_64-linux-gnu/libc.so.6(cfree+0x4c)[0x7fe95af3553c] ./test_ref[0x401fdb] ./test_ref[0x401fb0] ``` 找到 tst_ins_del() 的程式碼 並且找到了有 REF 的地方 ```=c /* Place nodes until end of the string, at end of stign allocate * space for data, copy data as final eqkid, and return. */ if (*p++ == 0) { if (cpy) { /* allocate storage for 's' */ const char *eqdata = strdup(*s); if (!eqdata) return NULL; curr->eqkid = (tst_node *) eqdata; return (void *) eqdata; } else { /* save pointer to 's' (allocated elsewhere) */ curr->eqkid = (tst_node *) *s; return (void *) *s; } } ``` 這段程式碼主要是在 tree 字元一個個數入之後，在字串全部輸完之後在最後一個結點 allocte 一個存放位置的空間並且回傳位置。 * 原本的 cpy 版本使用 [strdup()](http://c.biancheng.net/cpp/html/166.html) 動態宣告一個空間存放字串並且給定新的一個位置，再將其位置輸入當前節點的 eqkid，最後回傳其位置。 * 原本的 ref 版本並沒有重新宣告一個新的位置，導致所有的字串最後回傳的位置都是同一個，全部都指向同一塊記憶體。 首先先嘗試[前人](https://hackmd.io/s/SkEFpwh2-#%E7%90%86%E8%A7%A3%E5%8F%8A%E6%9B%B4%E6%94%B9-FIXME-%E7%A8%8B%E5%BC%8F%E7%A2%BC)的作法，在 test_ref.c 當中一開始建立 TST 的時候使用 strdup() 動態分配一個位置給 p ```=c while ((rtn = fscanf(fp, "%s", word)) != EOF) { char *p = strdp(word); /* FIXME: insert reference to each string */ if (!tst_ins_del(&root, &p, INS, REF)) { fprintf(stderr, "error: memory exhausted, tst_insert.\n"); fclose(fp); return 1; } idx++; } ``` 原本以為程式碼完整了，但竟然還是有問題！！ * 使用 add word to the tree 之後，search words matching prefix 會產生錯誤，會針對所有新輸入的 char 產生一個節點 那麼就針對所有會使用到 tst_ins_del() 前面的 word 使用 strdup() 給他一個新的空間 完成了最基本的程式修改，可以進行效能分析了 ## Makefile 修改 :::info city輸入方式 :::