tags: `homework` `sysprog2017`

2017q3 Homework2(prefix-search)

contributed by <Jetudie>

您是不是沒有填寫課程表單?
課程助教

當初錯填帳號名稱，已找老師修改
若有需要，可再重填一份表單給您
Jetudie

Reviewed by `jackyhobingo`

實驗上發現會有 search 'A' 時會發生 segfault，解決了嗎？若沒有解決可以參考我的解決方法
查看原始資料會發現輸入是 "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 的分析之後，也試試以單一字母開頭搜尋

搜尋 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);
}

tags: homework sysprog2017