2018q3 Homework2(lab0)

contributed by <yichung279>

tags: sysprog2018

實驗環境

 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:                 60
Model name:            Intel(R) Core(TM) i7-4770 CPU @ 3.40GHz
Stepping:              3
CPU MHz:               3453.523
CPU max MHz:           3900.0000
CPU min MHz:           800.0000
BogoMIPS:              6784.64
Virtualization:        VT-x
L1d cache:             32K
L1i cache:             32K
L2 cache:              256K
L3 cache:              8192K
NUMA node0 CPU(s):     0-7

$ uname -a
Linux ******* 4.4.0-127-generic #153-Ubuntu SMP Sat May 19 10:58:46 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux

$ gcc --version
gcc (Ubuntu 5.5.0-12ubuntu1~16.04) 5.5.0 20171010
Copyright (C) 2015 Free Software Foundation, Inc.

Linked list 結構

由於 q_insert_tail 及 q_size 要求時間複雜度 \(O(1)\)，要求中也沒有 q_remove_tail此類需要往反方向迭代的操作，因此採用下列結構，單方向的 Linked list。






typedef struct {
    list_ele_t *head; 
    list_ele_t *tail;
    int size ;
} queue_t;

比起一般簡單 Linked list，多了q->tail ，但實際上還是 Linked list ，演算法上沒有太多問題，只需多注意q->tail的狀況，還有 malloc 失敗回傳 NULL 的狀況。
疑慮：strdup 非 ISO C，下次相關操作應自行分配記憶體後，使用 strcpy。

關於string

q_insert_head、q_insert_tail 傳入的值是 pointer to char， string 可能有生命週期的問題，難保證原本的記憶體位置一直能被 queue 存取，可藉由 strdup 分配記憶體位置，並注意分配記憶體失敗的問題。




char *str = strdup(s);
if (str == NULL)
    return false;

q_remove_head 要指將 string 存入 sp 中，一開始使用 strcpy 但測試時，遇到了沒有 terminator 的狀況，以及沒有對齊的狀況，改採用mempcy 只分配定量的記憶體並強迫最後一個 charactor 為 terminator 。





if (sp) {
    memcpy(sp, q->head->value, bufsize  - 1);
    sp[bufsize  - 1] = '\0';
}

被遺忘的細節

1.malloc有機會失敗，strdup 也包含記憶體配置。
2.q->head q->tail 甚至q都有可能是NULL容易在操作時 dereference a NULL

關於commit

凌晨三點鐘的哀號：

已經得到100分
但我無法git commit QQ

原因：clang-format後，沒有再 git add 一次，staging area ，一直是未修改的檔案，堅持 commit 只會重複觸發 clang-format 的警告。

關於if ( q == NULL)

自行code review時，思考了一下條件式的寫法。




if (q == NULL)
/* vs */
if (!q)

第一眼選用下面的方式，但後來認為條件式盡量以直述句為主，選用第一行的方式。

Git hook 原理

qtest 原理

Select a repo