###### tags: `homework` `sysprog2017`
2017q3 Homework2(prefix-search)
===
contributed by <`Jetudie`>
>您是不是沒有填寫課程表單?
>[name=課程助教][color=red]
>>當初錯填帳號名稱，已找老師修改
>>若有需要，可再重填一份表單給您
>>[name=Jetudie][color=royalblue]

---
題目： [C04: prefix-search](https://hackmd.io/s/Bki0g_P3Z)
### Reviewed by `jackyhobingo`
* 實驗上發現會有 search 'A' 時會發生 segfault，解決了嗎？若沒有解決可以參考我的[解決方法](https://hackmd.io/s/B1V8tv33W)
* 查看原始資料會發現輸入是 "city, country" or "city, city, country"，會有逗號的都是城市，也許可以修改輸入時 split 的方法，將逗號處理掉

## 編譯及測試
+ 取得程式碼、編譯並執行

$ git clonehttps//github.com/sysprog21/prefix-search
$ cd prefix-search
$ make
$ ./test_cpy

+ 出現如下

ternary_tree, loaded 259112 words in 0.128302 sec

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: 

### 測試 find the word in tree
+ 輸入 `f` 按下 Enter, 輸入 `Taiwan`, 再按 Enter

find word on tree: Taiwan
  found Taiwan in 0.000002 sec.

+ 輸入 `f` 按下 Enter, 輸入 `Tai`, 再按 Enter

find word on tree: Tai
  Tai not found.

### 測試 search the words matching prefix
+ 接著又出現選擇畫面，輸入 `s` 按下 Enter, 再搜尋 `Tain`

find words matching prefix (at least 1 char): Tain
  Tain - seacjed prefix in 0.000013 sec
suggest[0] : Tain,
suggest[1] : Tainan,
suggest[2] : Taino,
suggest[3] : Tainter
suggest[4] : Taintrux,

發現==有些資料後面有逗號 (comma)，有些則無==

接著看到 [jackyhobingo 的分析](https://hackmd.io/s/B1V8tv33W)之後，也試試以單一字母開頭搜尋
+ 搜尋 `T` , 得到的結果為 1024 筆，末項是 `Tasqillo` 。發現其中==出現重複的資料==，差別只在後面有無 comma, 列出其中幾項示意

...
suggest[57] : Tío
suggest[58] : Tío,
...
suggest[112] : Týn
suggest[113] : Týn,
...
suggest[274] : Tabor
suggest[275] : Tabor,
...
suggest[944] : Tarnów
suggest[945] : Tarnów,
...
suggest[1023] : Tasquillo,

看末項，顯然 `Ta` 都沒列完，接著搜尋 `Tas` , 發現 `Tasquillo` 後面的確還有資料。又以`B`搜尋，得到同樣的結果，目前結論為此程式==最多一次列出 1024 筆資料==

+ 搜尋 `A` , 發現得到以下結果

find words matching prefix (at least 1 char): A
Segmentation fault (core dumped)

---
## 探討在 find words matching prefix, 輸入 A 發生 Segmentation fault 的原因
+ 用 gdb 找錯誤在哪發生

$ gdb ./test_cpy
...
(gdb) run 
...
choice: s
find words matching prefix (at least 1 char): A

Program received signal SIGSEGV, Segmentation fault.
0x0000555555555eea in tst_suggest (p=0x555556b1cb90, c=65 'A', nchr=1, a=0x7fffffffbdd0, n=0x7fffffffbd90, max=1024) at tst.c:330
330	        a[(*n)++] = (char *) p->eqkid;

發現在 tst.c:330 發生 Segmentation fault

void tst_suggest(const tst_node *p,
                 const char c,
                 const size_t nchr,
                 char **a,
                 int *n,
                 const int max)
{
    if (!p || *n == max)
        return;
    tst_suggest(p->lokid, c, nchr, a, n, max);
    if (p->key)
        tst_suggest(p->eqkid, c, nchr, a, n, max);
    else if (*(((char *) p->eqkid) + nchr - 1) == c)
        a[(*n)++] = (char *) p->eqkid;
    tst_suggest(p->hikid, c, nchr, a, n, max);
}