2017q1 Homework1 (phonebook)
===
contributed by < `leocorter` >

新手上路請多多指教

### Reviewed by `king1224`

* 我在你的 github 上沒有看到你的 BST 版本的程式碼
* 你在 stackoverflow 上看到的程式碼是以 double 做為鍵值來比較判斷要放左子樹 or 右子樹，本次 phonebook 是以 lastname 做為鍵值，請問你是如何判斷該往左子樹 or 右子樹走
* 關於 main.c 中的 append() 使用，原始版本可以傳入整串資料的任意節點，畢竟原始版本的儲存方式沒有分支，但對於 BST 結構來說，每次都需要傳入 root，因此 main.c 中的使用方式需修改

### Reviewed by `tina0405`
*關於BINARYTREE我本身是嘗試用字數長短判斷左右，想了解是以和者為判斷標準。

*還有你將STRUCTURE只分為左子樹和右子樹那其他的資料要如何去呼叫，之後在使用這份電話簿時，還是會運用到其他資訊。

*其他方面也可測試不同的hashfunctin嘗試。

## 開發環境

Architecture:          x86_64
CPU op-mode(s):        32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                8
Vendor ID:             GenuineIntel
Model name:            Intel(R) Core(TM) i7-3632QM CPU @ 2.20GHz
CPU MHz:               1243.343
CPU max MHz:           3200.0000
CPU min MHz:           1200.0000
BogoMIPS:              4389.95
Virtualization:        VT-x
L1d cache:             32K
L1i cache:             32K
L2 cache:              256K
L3 cache:              6144K

---

## 未優化版本

/* original version */
entry *findName(char lastName[], entry *pHead)
{
    while (pHead != NULL) {
        if (strcasecmp(lastName, pHead->lastName) == 0)
            return pHead;
        pHead = pHead->pNext;
    }
    return NULL;
}

很單純的找不到就換下一個

* 執行: `$ ./phonebook_orig`

* append() 及 findName() 時間如下

size of entry : 136 bytes
execution time of append() : 0.189302 sec
execution time of findName() : 0.005467 sec

 Performance counter stats for './phonebook_orig' (100 runs):

          212,2953      cache-misses              #   95.108 % of all cache refs      ( +-  0.12% )
          223,2152      cache-references                                              ( +-  0.14% )
       2,6081,7801      instructions              #    1.43  insns per cycle          ( +-  0.02% )
       1,8211,8763      cycles                                                        ( +-  0.49% )

       0.088154008 seconds time elapsed                                          ( +-  1.88% )

>進度請加快[name=亮谷][color=#f64]

---
## phonebook

### 改進方向
* binary search tree
* hashing function 加入查詢
* 降低資料表示的成本 S

---

## Binary search tree

### 想法：
* 如果我們只要找 lastName 這個字串那麼 entry 裡面的其他資料就是多餘的，所以我就把其他資料刪除。
* 原本的資料是用 linked list 一個一個串起來，現在我想要建造一個 binary tree 所以加上了左右的連結。

typedef struct __PHONE_BOOK_ENTRY {
    char lastName[MAX_LAST_NAME_SIZE];
    struct __PHONE_BOOK_ENTRY *pNext_left;
    struct __PHONE_BOOK_ENTRY *pNext_right;
} entry;

可是再我實作的過程中遇到了 segmentation fault 後來檢查是執行到 findName() 產生錯誤，之後我上網搜尋 binary tree segmentation fault 找到了 [stackoverflow](
https://stackoverflow.com/questions/23767937/c-segmentation-fault-in-insert-to-binary-tree) 發現裏面有<s>雙重指標</s>指標的指標
>> 中文的「雙」表示對等的兩者，比方說「雙人」，但 `node **tree` 本質上是「指標的指標」，貿然稱為「雙指標」的話，你會發現對價關係錯誤了，請務必留意。 [name="jserv"]

void addNode(double value, node **tree)
{
    // search first
    while (*tree)
    {
        if (value < (*tree)->key) 
            tree = &(*tree)->left;
        else if((*tree)->key < value) 
            tree = &(*tree)->right;
        else return;
    }

    // no match, so add
    *tree = malloc(sizeof(**tree));
    (*tree)->key = value;
    (*tree)->left = (*tree)->right = NULL; // note: set to null
}

>>我想請問關於指標，網路上查詢之後還是不太懂，為何這邊要這樣用？？
>>感謝 許友綸學長的教學已了解
>> 不要貿然讀網路上資料，為何不回頭讀 [K&R C](https://en.wikipedia.org/wiki/The_C_Programming_Language) 呢？ [name="jserv"]
>> 謝謝老師的建議 [name=鄭安邦]

## 實驗結果

 Performance counter stats for './phonebook_opt' (100 runs):

           39,2941      cache-misses              #   64.873 % of all cache refs      ( +-  0.71% )
           60,5712      cache-references                                              ( +-  1.02% )
       2,4814,4349      instructions              #    1.69  insns per cycle          ( +-  0.08% )
       1,4716,5776      cycles                                                        ( +-  0.36% )

       0.075049025 seconds time elapsed                                          ( +-  2.39% )

* cache miss 下降到 64.873%


### 討論
* append() findName() 下降
* 如果 binary tree 有實作成功 append()應該會上升，且 findName() 應該會下降更多，代表只有 struct 資料的減少影響到實驗結果

# 還要再努力

---
* [petermouse 同學的共筆](https://hackmd.io/s/B161G0qFx#)
* [twzjwang 同學的共筆](https://hackmd.io/s/HJsOjpYKl)
* [vic85821 同學的共筆](https://hackmd.io/s/r1B6WwQT#)
* [Binary search tree](http://www.thegeekstuff.com/2013/02/c-binary-tree/)
* [Binary search tree](http://www.cprogramming.com/tutorial/c/lesson18.html)

---

昨天嘗試用 binary tree 完成實驗，可是結果沒有達到所要的要求，今天發現了錯誤的地方，是因為原本的邏輯不對，造成的不是 binary tree 而是變成 pNext_left 和 pNext_right 兩個選一個串下去，想要修改缺發生了 segmentation fault

>> 請問要從何資料或書籍了解 segmentation fault 的相關知識和解決方法，我查了維基百科了解了可能發生原因，和 The C program language 卻還是無法解決