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輸入方式
:::