HackMD
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
原程式碼 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.
若是刪除原本不存在的字串時，會直接變成輸入字串
原來也有其他人發現了一樣的問題
解決方式其實不難，只要多一個條件判斷就可以了
if(del)
return""
放在 tst_ins_del() 裡面
…結果反而延伸出另一個問題，程式可以刪除不存在的字了…
how to fix it ?
test_ref.c 程式碼分析與修改
首先找到在 test_ref.c FIXME 的部份，修改程式內容
/* 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() 函式的地方進行修改
- 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 的地方
/* 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() 動態宣告一個空間存放字串並且給定新的一個位置，再將其位置輸入當前節點的 eqkid，最後回傳其位置。
- 原本的 ref 版本並沒有重新宣告一個新的位置，導致所有的字串最後回傳的位置都是同一個，全部都指向同一塊記憶體。
首先先嘗試前人的作法，在 test_ref.c 當中一開始建立 TST 的時候使用 strdup() 動態分配一個位置給 p
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 修改
city輸入方式
