2018q1 Homework2 (prefix-search)

contributed by < TingL7 >

系統環境

$ uname -r
4.14.0-041400-generic

$ lscpu
Architecture:          x86_64
CPU op-mode(s):        32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                8
On-line CPU(s) list:   0-7
Thread(s) per core:    2
Core(s) per socket:    4
Socket(s):             1
NUMA node(s):          1
Vendor ID:             GenuineIntel
CPU family:            6
Model:                 142
Model name:            Intel(R) Core(TM) i7-8550U CPU @ 1.80GHz
Stepping:              10
CPU MHz:               2000.000
CPU max MHz:           4000.0000
CPU min MHz:           400.0000
BogoMIPS:              3984.00
Virtualization:        VT-x
L1d cache:             32K
L1i cache:             32K
L2 cache:              256K
L3 cache:              8192K
NUMA node0 CPU(s):     0-7
Flags:                 fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc art arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf tsc_known_freq pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_fault epb intel_pt tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid mpx rdseed adx smap clflushopt xsaveopt xsavec xgetbv1 xsaves dtherm ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp

Ternary Search Tree

特性：每個節點有 3 個小孩，在搜尋時，比對每個字元與樹的節點字元的 ASCII code 大小或相等，以決定拜訪哪個小孩，並不斷比對字元直到字尾，觀察字尾所在的節點決定是否為要搜尋的字。
優點：
- 與 trie 相比，空間的使用率增加。 Trie 要作英文字母的搜尋時，每個節點會有 26 個孩子，但實際上並不是所有孩子都有用到。而 tst 只有 3 個孩子空間使用率會比較高。
  
  在只有四個字母的時後，trie 包含 {AB, ABBA, ABCD, BCD}
  
  同樣的資料，在 tst 儲存的空間使用率較高。
- 一節點的子孫都有同樣的前綴字，因此適合用在自動補齊單字。
引入 tst 到電話簿或戶政管理系統的適用性
- 電話簿或戶政管理系統的特性在於:資料庫有大量類似的字詞，如地址，有很多台南市…的，他們的前綴詞都相同，如果每筆資料都直接存放在記憶體，會有一堆重複的字出現，造成記憶體浪費，因此使用 tst 就很適合。

初始測試

$ make
$ ./test_cpy
ternary_tree, loaded 259112 words in 0.108185 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: f
find word in tree: Taiwan
  found Taiwan in 0.000002 sec.

choice: f
find word in tree: Chunghwa
  Chunghwa not found.

choice: s
find words matching prefix (at least 1 char): Chung
  Chung - searched prefix in 0.000008 sec

suggest[0] : Chunghwa,

choice: a
enter word to add: tii
  tii - inserted in 0.000006 sec. (259113 words in tree)

choice: f
find word in tree: tii
  found tii in 0.000002 sec.

choice: d
enter word to del: tii
  deleting tii
  deleted tii in 0.000010 sec

choice: q

奇妙的事情出現了，使用 f 找不到的東西，使用 s 居然找到了，多試了幾筆資料，推測 f 能夠查詢的只有國家，而無法查詢城市。
test_cpy 、 test_ref在功能測試上，結果相同。
a 功能為在數中新增節點， d 為刪除節點。

修改 test_ref.c

開啟 test_ref.c

enum 宣告內容為遞增的 int ，因此 INS 為 0 ， DEL 為 1 。
由 define 可以得知 REF 為 0 ， CPY 為 1 。



enum { INS, DEL, WRDMAX = 256, STKMAX = 512, LMAX = 1024 };
#define REF INS
#define CPY DEL

需要修改的地方有 3 處:


 /* FIXME: insert reference to each string */
if (!tst_ins_del(&root, &p, INS, CPY)) {


/* FIXME: insert reference to each string */
res = tst_ins_del(&root, &p, INS, CPY);


/* FIXME: remove reference to each string */
res = tst_ins_del(&root, &p, DEL, CPY);

開啟 tst.c 查看 tst_ins_del 的內容
函式功能為在三元樹中插入或刪除節點。
主要改變的參數 cpy ，決定要幫字串 allocate storage 或 save pointer 只出現在 for 迴圈中：



























void *tst_ins_del(tst_node **root, char *const *s, const int del, const int cpy)
{
    ...
    
    /* if not duplicate, insert remaining chars into tree rooted at curr */
    for (;;) {
        
        ...

        /* 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;
            }
        }
        pcurr = &(curr->eqkid);
    }
}

FIXME 1 建立 tst

將 CPY 改成 REF ，結果在 command s 、 q 會出錯：

choice: s
find words matching prefix (at least 1 char): Chung
  Chung - searched prefix in 0.000009 sec

suggest[0] : Chung
suggest[1] : Chung
suggest[2] : Chung
suggest[3] : Chung

choice: q
*** Error in `./test_ref': free(): invalid pointer: 0x00007ffd1303a630 ***
======= Backtrace: =========
...
======= Memory map: ========
...
Aborted (core dumped)

傳入 tst_ins_del() 的參數 s 為讀入的 word ，在 save pointer 的情況下，直接將 tst 指向 s，但 word 只是為了讀檔而暫存的地方，資料會不停的被洗掉，因此，有儲存指標，但指標的內容不停被更動。










 while ((rtn = fscanf(fp, "%s", word)) != EOF) {
    char *p = 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++;
}

command s

在使用 s 指令時，會呼叫 tst_search_prefix(const tst_node *root, const char *s, char **a, int *n, const int max) ，其中參數 a 是儲存 suggest 的變數，而在這個函數中，決定 a 的是一個遞迴函數

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

可以發現: a 直接取存放在 leaf 的值，也就是在建立 tst 時的 word 。但，很不幸的，之前在建立時，由於指向的內容是被修改過的，因此在使用 command s 時，建議值會出錯。

修改一

在不更動 tst.c 的前提下，要儲存指標，且內容不得更動，就要使每次進去 tst_ins_del() 中的 word 位址不同。
最直接，且考慮到記憶體連續避免 cache miss 過大，使用 array 使得每次讀進來的 word 存放到不同的位址。
array 大小：考慮到程式要可以增加資料 (command a) ，不適合直接寫死，而且直接寫死要考慮到有 259111 個城市 (word) ，宣告太大的陣列會 stack overflow ，因此以動態陣列的方式宣告比較適合。
離開時，要釋放 word_tst 的記憶體。
程式碼


















 char (*word_tst)[WRDMAX] = malloc(260000 * sizeof(*word_tst));
 while ((rtn = fscanf(fp, "%s", word_tst[idx])) != EOF) {
      char *p = word_tst[idx];
      /* 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++;
  }
...
        case 'q':
        tst_free_all(root);                                                 
        free(word_tst);
        return 0;
        break;

結果

choice: s
find words matching prefix (at least 1 char): Tain
  Tain - searched prefix in 0.000018 sec

suggest[0] : Tain,
suggest[1] : Tainan,
suggest[2] : Taino,
suggest[3] : Tainter
suggest[4] : Taintrux,

choice: q
*** Error in `./test_ref': free(): invalid pointer: 0x00007f4cc9d7ef10 ***
======= Backtrace: =========
...
======= Memory map: ========
...
Aborted (core dumped)

command s 沒問題，command q 還有錯誤。

command q

q 相關的程式碼很單純，主要就是在釋放記憶體。

case 'q':
    tst_free_all(root);
    free(word_tst);
    return 0;
    break;

在 tst.c 中，與釋放記憶體有關的函式有兩個：

























/** free the ternary search tree rooted at p, data storage internal. */
void tst_free_all(tst_node *p) 
{
    if (!p)
        return;
    tst_free_all(p->lokid);
    if (p->key)
        tst_free_all(p->eqkid);
    tst_free_all(p->hikid);
    if (!p->key)
        free(p->eqkid);
    free(p);
}

/** free the ternary search tree rooted at p, data storage external. */
void tst_free(tst_node *p) 
{
    if (!p)
        return;
    tst_free(p->lokid);
    if (p->key)
        tst_free(p->eqkid);
    tst_free(p->hikid);
    free(p);
}

差別在於是否有釋放 leaves 的記憶體。如註解所寫，資料現在儲存在 array 中，可以說儲存在 tst 外，因此不應該由 tst 這邊釋放。因此該使用 tst_free() 而非 tst_free_all()。

修改：

程式碼

case 'q':
    tst_free(root);                                                 
    free(word_tst);
    return 0;
    break;

結果
正常退出，沒有錯誤訊息。

FIXME 2 to add word to the tree

將 CPY 改成 REF

case 'a':
    printf("enter word to add: ");
    if (!fgets(word, sizeof word, stdin)) {                                    
        fprintf(stderr, "error: insufficient input.\n");
        break;
    }   
    rmcrlf(word);
    p = word;
    t1 = tvgetf();
    /* FIXME: insert reference to each string */
    res = tst_ins_del(&root, &p, INS, REF);
    t2 = tvgetf();
    if (res) {
        idx++;
        printf("  %s - inserted in %.6f sec. (%d words in tree)\n",
               (char *) res, t2 - t1, idx);
    } else
        printf("  %s - already exists in list.\n", (char *) res);
    break;

結果在 command s 、 d 會出錯：

choice: a    
enter word to add: Tiz
  Tiz - inserted in 0.000009 sec. (259113 words in tree)

choice: s    
find words matching prefix (at least 1 char): Tiz
  Tiz - searched prefix in 0.000021 sec

suggest[0] : Tiz
suggest[1] : Tiz
suggest[2] : Tiza,
suggest[3] : Tizapán
suggest[4] : Tizayuca,
suggest[5] : Tizi
suggest[6] : Tizi-n-Tleta,
suggest[7] : Tizimín,
suggest[8] : Tiznit,
suggest[9] : Tizzano

choice: d
enter word to del: Tiz
  deleting Tiz
*** Error in `./test_ref': free(): invalid pointer: 0x00007ffe8b614100 ***
======= Backtrace: =========
...
======= Memory map: ========
...
Aborted (core dumped)

command s 出錯的原因在於 insert 時失敗，與 FIXME 1 相同，有 word 指向同一塊位址的問題。因此，仿造上面的作法，以 array 的方式儲存字串。
command d 出錯的原因為沒有正確釋放記憶體。

修改

程式碼



















case 'a':
    printf("enter word to add: ");
    if (!fgets(word_tst[idx], sizeof word_tst[idx], stdin)) {
        fprintf(stderr, "error: insufficient input.\n");
        break;
    }   
    rmcrlf(word_tst[idx]);
    p = word_tst[idx];
    t1 = tvgetf();
    /* FIXME: insert reference to each string */
    res = tst_ins_del(&root, &p, INS, REF);
    t2 = tvgetf();
    if (res) {
        idx++;
        printf("  %s - inserted in %.6f sec. (%d words in tree)\n",
               (char *) res, t2 - t1, idx);
    } else
        printf("  %s - already exists in list.\n", (char *) res);
    break;

結果

choice: a
enter word to add: Tiz
  Tiz - inserted in 0.000010 sec. (259113 words in tree)
 choice: s
find words matching prefix (at least 1 char): Tiz
  Tiz - searched prefix in 0.000022 sec

suggest[0] : Tiz
suggest[1] : Tiza,
suggest[2] : Tizapán
suggest[3] : Tizayuca,
suggest[4] : Tizi
suggest[5] : Tizi-n-Tleta,
suggest[6] : Tizimín,
suggest[7] : Tiznit,
suggest[8] : Tizzano

FIXME 3 to delete a word from the tree

command d 出錯的地方在 tst_ins_del() 中所呼叫的 tst_del_word()


return tst_del_word(root, curr, &stk, 1);












static void *tst_del_word(tst_node **root,
                         tst_node *node,
                         tst_stack *stk,
                         const int freeword)
{
   tst_node *victim = node;          /* begin deletion w/victim */
   tst_node *parent = tst_stack_pop(stk); /* parent to victim */

   if (!victim->refcnt) {            /* if last occurrence */
       if (!victim->key && freeword) /* check key is nul   */
           free(victim->eqkid);      /* free string (data) */
       ...

line 64 的 free 是非法的，因為這裡的 string data 實際上是在建立資料庫時的 word array 中，不能直接 free 。
註解中提到 if 'freeword = 0', node->eqkid is stored elsewhere and not freed ，但從上面這兩段程式碼可以發現 freeword 永遠為 1 ，因次要將 line 238 的 tst_del_word（） 最後一個參數改為 cpy 。

修改

程式碼 (in tst.c)


return tst_del_word(root, curr, &stk, 238);

結果

choice: a
enter word to add: Tiz
  Tiz - inserted in 0.000009 sec. (259113 words in tree)

choice: d
enter word to del: Tiz
  deleting Tiz
  deleted Tiz in 0.000014 sec

idx 問題

因為 word_tst 是由 idx 在控制，但在刪除之後， word_tst 實際上是沒有減少的，但是會作 idx-- 因此在之後新增時，會覆蓋到原本 word_tst 中的資料。
解決：新增控制 word_tst 的變數。
程式碼


char (*word_tst)[WRDMAX] = malloc(260000 * sizeof(*word_tst));
int i = 0;











while ((rtn = fscanf(fp, "%s", word_tst[i])) != EOF) {
    char *p = word_tst[i];
    /* 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++;
    i++;
}















       case 'a':
            printf("enter word to add: ");
            if (!fgets(word_tst[i], sizeof word_tst[i], stdin)) {                 
            fprintf(stderr, "error: insufficient input.\n");
            break;
        }
        rmcrlf(word_tst[i]);
        p = word_tst[i];
        t1 = tvgetf();
        /* FIXME: insert reference to each string */
        res = tst_ins_del(&root, &p, INS, REF);
        t2 = tvgetf();
        if (res) {
            i++;
            idx++;

修改 `Makefile` 以做出效能評比

參考tina0405共筆

程式要可接受--bench ，作為 main 的參數。

意指執行如下指令，--bench 會存放在 argv[1]

./test_ref --bench s Tain

需要在 main function 中判斷，是否在執行 --bench ，可透過設立變數 (bench_flag) 來判斷。test_ref.c 及 test_cpy.c 都要設立。
執行 --bench 與一般 make ，不一樣的地方在於不用手動輸入資料，要自動的讀資料。先設定讀入的資料只有一筆 (s Tain) ，處理完之後，必須自動執行 command q 。
部份修改過的程式碼

int bench_flag = (agrc > 1 && !(strcmp(argv[1], "--bench"))?1:0;
...
for(;;)
    char *p; 
    if(bench_flag){
        if(bench_flag > 1)
            strcpy(word, "q");
        else{
            strcpy(word, argv[2]);
            bench_flag++;
        }   
    }else{
        printf(
            "\nCommands:\n"
            " a  add word to the tree\n"
            " f  find word in tree\n"
            " s  search words matching prefix\n"
            " d  delete word from the tree\n"
            " q  quit, freeing all data\n\n"
            "choice: ");
        fgets(word, sizeof word, stdin);
    }   
    p = NULL;
    switch (*word) {
    case 'a':
        if(bench_flag)
            strcpy(word_tst[i], argv[3]);
        else{
            printf("enter word to add: ");
            if (!fgets(word_tst[i], sizeof word_tst[i], stdin)) {
                fprintf(stderr, "error: insufficient input.\n");
                break;
            }
        }
        ...

參考上個作業 phonebook 的 Makefile ，讓程式進行 100 次，並作效能評比

程式碼(in Makefile)

DATA = s Tain
bench: $(TEST)
    perf stat --repeat 100 \
        -e cache-misses,cache-references,instructions,cycles \
        ./test_cpy --bench $(DATA)      
    perf stat --repeat 100 \
        -e cache-misses,cache-references,instructions,cycles \
        ./test_ref --bench $(DATA)

結果

ternary_tree, loaded 259112 words in 0.116547 sec
  Tain - searched prefix in 0.000003 sec, 5 suggests

 Performance counter stats for './test_cpy --bench s Tain' (100 runs):

 2,944,151      cache-misses:u            #   37.957 % of all cache refs      ( +-  0.21% )
 7,756,549      cache-references:u                                            ( +-  0.17% )
513,611,005      instructions:u            #    1.35  insn per cycle           ( +-  0.07% )
380,216,819      cycles:u                                                      ( +-  0.08% )

0.134732372 seconds time elapsed                                          ( +-  0.18% )

Ref 版本

ternary_tree, loaded 259112 words in 0.131607 sec
  Tain - searched prefix in 0.000005 sec,5 suggests

Performance counter stats for './test_ref --bench s Tain' (100 runs):

 3,644,486      cache-misses:u            #   42.456 % of all cache refs      ( +-  0.29% )
 8,584,217      cache-references:u                                            ( +-  0.12% )
483,558,386      instructions:u            #    1.23  insn per cycle           ( +-  0.00% )
394,352,557      cycles:u                                                      ( +-  0.12% )

0.168124774 seconds time elapsed                                          ( +-  0.28% )

建立 tst 和 prefix search 的時間比較圖
可以發現 cpy 版本 cache miss 較低，而且建立 tst 的時間也比較低。
雖然 cpy 版本中，使用 strdup 有 malloc 記憶體，在使用上並不連續，但是 ref 宣告了一個很大的陣列，但實際上並沒有全部用到，因此 cache miss 會比較高。

prefix search 缺陷

兩個字以上的城市，在 tst 中會被視為兩個地方。
- 如：Newcastle under Lyme, United States
- 不用 fscanf() 讀入，改用 fget(),並以 , 作為 token 且割字串。
find 找查城市時，需要在末端輸入 ,
無法分辨城市、州、國家
- ~~建立 3 棵樹，分別存放城市、州、國家。~~
  - 所需的空間比 1 棵樹大。
  - 搜尋時，會花費更多時間。
- ~~以 , 分辨~~
  - 無法分辨州、城市
  - 以其他符號分辨？
- 在 tst_node 新增 iscountry 欄位
城市與國家的關係，毫無聯繫

修正

程式碼




























    while ((fgets(str_ar, WRDMAX * 3, fp)) != NULL) {
    str = str_ar;                                                             
    strcpy(word, strsep(&str, ",\n"));
        
    while (strcmp(word, "") != 0) {
        if(word[0] == ' '){
            int j;
            for(j = 1;j < strlen(word);j++)
                    word_tst[i][j-1] = word[j];
            word_tst[i][j-1] = '\0';
        }else{
            int j;
            for(j = 0;j < strlen(word);j++)
                word_tst[i][j] = word[j];
            word_tst[i][j] = '\0';
        }   
        char *p = word_tst[i];
        /* 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++;
        i++;
        strcpy(word, strsep(&str, ",\n"));
    }   
}

結果

ternary_tree, loaded 206849 words in 0.106141 sec

choice: f
find word in tree: Tainan
  found Tainan in 0.000004 sec.

choice: f
find word in tree: Newcastle under Lyme
  found Newcastle under Lyme in 0.000004 sec.

實際上只有 206849 個城市、國家。

效能評比 part2 & 分析 `test_cpy` 和 `test_ref` 的效能，並提出改善機制

分析 prefix search

針對所有的資料，取前三個字元來搜尋。












char search_word[PREFIX] = "";
int count = 0;
fp = fopen(IN_FILE, "r");
while(fscanf(fp, "%s", word) != EOF){   
    if(strlen(word) < 3) continue;
    strncpy(search_word, word, PREFIX);
    t1 = tvgetf();
    tst_search_prefix(root, search_word, sgl, &sidx, LMAX);
    t2 = tvgetf();
    fprintf(fp_out2, "%d %.8f\n", count++, t2 - t1);
}   
fclose(fp_out2);

結果
- x 軸為資料編號， y 軸為執行 prefix search 的時間。
- 可以看出執行時間大部在 2*10^-6 sec 以內。觀察分佈發現，有幾個高峰的地方，如第 5000 比資料左右。總體來說，因為 ref 峰值較高，所以平均較高，而 cpy 的分佈則是相對平均。

信賴區間

參考 rex662624 共筆
gnuplot 的分析指令

$gnuplot
$stats "cpy.txt" using 2
$stats "ref.txt" using 2

* FILE:           cpy.txt                 ref.txt
Records:           254073                  254073
Out of range:           0                       0
Invalid:                0                       0
Blank:                  0                       0
Data Blocks:            1                       1

* COLUMN: 
Mean:          2.58959e-07            2.16105e-07
Std Dev:       2.15182e-07            2.57175e-07
Sample StdDev: 2.15183e-07            2.57176e-07
Skewness:          21.9973               139.0368
Kurtosis:        2635.6369             38465.3643
Avg Dev:       1.23026e-07            1.06763e-07
Sum:                0.0658                 0.0549
Sum Sq.:       2.88026e-08            2.86697e-08

Mean Err.:     4.26901e-10            5.10211e-10
Std Dev Err.:  3.01865e-10            3.60773e-10
Skewness Err.:      0.0049                 0.0049
Kurtosis Err.:      0.0097                 0.0097

Minimum:            0.0000 [     6]         0.000[    11]   
Maximum:            0.0000 [ 40470]         0.001[ 23637]     
Quartile:      2.40000e-07            2.40000e-07
Median:        2.40000e-07            2.40000e-07
Quartile:      2.40000e-07            2.40000e-07

The Confidence Interval formula is

x \pm z \cdot \frac{s}{\sqrt{n}}

X is the mean = 2.58959e-07 2.16105e-07
Z : 95% 時 z = 1.960
s is the standard deviation = 2.15182e-07 2.57175e-07
n is the number of samples = 254073

代入公式，得 :

CPY版本 prefix search 95% 信賴區間: 2.58959e-07 ± 8.3672502e-10 (sec)
REF版本 prefix search 95% 信賴區間: 2.16105e-07 ± 1.00001281e-9 (sec)

記憶體配置
- cpy 與 ref 都是使用動態記憶體，在 heap 中取用記憶體，然而，兩者的節點與葉節點的擺放位置不同，造成了效能差異。
- cpy
  在建立、搜尋時，由於 strdup 是由 heap 中抓取可用的記憶體，事實上也是順序的，不會差太遠，因此，在找到 leaf 時，也是很順的抓。因此， cache miss 效能較佳。
  
  node
  
  node
  
  node
  
  leaf
  
  node
  
  node
  
  leaf
- ref
  在建立之前，便先宣告 heap 中的一塊給 leaves 用，而每次建立到 leaf 時，都要再回去原本宣告的 leaves 的記憶體，造成記憶體在使用上很不連續， cache miss 就很高。
  
  leaves
  
  node
  
  node
  
  node
  
  node
  
  node
改善方法
- 根據記憶體配置差異的想法，可以模仿 cpy 的記憶體配置方式，因此在一開始就宣告一塊給所有 nodes 及 leaves 用，以達到如 cpy 的排列，也可以避免空間浪費，也就是 memory pool 的方式。

node
node
node
leaf
node
node
leaf

leaves
node
node
node
node
node

`tst_traverse_fn` 函式

callback function
- 根據維基百科定義：a callback is any executable code that is passed as an argument to other code, which is expected to call back (execute) the argument at a given time.
- 在 c 語言中， callback function 就是將 function pointer 當作參數傳入另一個 function 中執行。

tst_traverse_fn function

就是一個遞迴的 callback function ，它將 fn() 當作參數。

/** tst_traverse_fn(), traverse tree calling 'fn' on each word.
 *  prototype for 'fn' is void fn(const void *, void *). data can
 *  be NULL if unused.
 */
void tst_traverse_fn(const tst_node *p,
                     void(fn)(const void *, void *),
                     void *data)
{
    if (!p)
        return;
    tst_traverse_fn(p->lokid, fn, data);
    if (p->key)
        tst_traverse_fn(p->eqkid, fn, data);
    else    
        fn(p, data);
    tst_traverse_fn(p->hikid, fn, data);
}

這個函式的功能就是走訪整個樹的節點，並且在 leaves 執行使用者自訂函式 fn()。

應用：

計算 leaves 數量

void fn(const void *p, void *data)
{
    ++*(int *)data;
}
tst_traverse_fn(root, fn, &data);
printf("data: %d\n", data);

結果

data: 85500

效能評比
可以比較兩者的走訪速度。

t1 = tvgetf();
tst_traverse_fn(root, fn, &data);
t2 = tvgetf();                                                        
printf("cpy time: %.6f\n", t2-t1);

結果

cpy time: 0.015064
ref time: 0.015275

印出資料庫中所有的國家、城市

void fn(const void *p, void *data){
  printf("%s\n", tst_get_string(p));
}
tst_traverse_fn(root, fn, &data);

結果

...
Tufino,
Tuftonboro,
Tuganay,
Tugas,
Tugaya,
Tugbong,
Tugdan,
Tuggen,
Tuglie,
Tugolesskiy
Tugos,
Tuguegarao
Tugulym,
Tugun,
...