# 2018q3 Homework2 (lab0)

contributed by < [flawless0714](https://github.com/flawless0714) >

###### tags: `sysprog2018`

## 實驗環境

OS: Lubuntu 18.04.1 LTS (Bionic Beaver)
Architecture:        x86_64
CPU op-mode(s):      32-bit, 64-bit
Byte Order:          Little Endian
CPU(s):              4
On-line CPU(s) list: 0-3
Thread(s) per core:  2
Core(s) per socket:  2
Socket(s):           1
NUMA node(s):        1
Vendor ID:           GenuineIntel
CPU family:          6
Model:               142
Model name:          Intel(R) Core(TM) i7-7500U CPU @ 2.70GHz
Stepping:            9
CPU MHz:             700.030
CPU max MHz:         3500.0000
CPU min MHz:         400.0000
BogoMIPS:            5808.00
Virtualization:      VT-x
L1d cache:           32K
L1i cache:           32K
L2 cache:            256K
L3 cache:            4096K
NUMA node0 CPU(s):   0-3
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 invpcid_single pti ssbd ibrs ibpb stibp tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid mpx rdseed adx smap clflushopt intel_pt xsaveopt xsavec xgetbv1 xsaves dtherm ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp flush_l1d

## queue.h 開發紀錄
- q->tail
為了讓 queue.c 中某些操作的時間複雜度為 $O(1)$，而新增此成員到結構體 queue_t 中以儲存 list 中最後一個節點。
- q->eleCount
為了讓 queue.c 中某些操作的時間複雜度為 $O(1)$，而新增此成員到結構體 queue_t 中以儲存 list 之節點數量。

## queue.c 開發紀錄
- queue_new
當 malloc 失敗而返回 NULL 時，我們可以在對 q 賦值前離開函數，以避免參照到 NULL 位置而導致 seg fault。

- queue_free
進入函數後先檢查 q 是否為 NULL，是則直接返回，否則繼續往下，接下來宣告並定義待會 free 會用到之變數，不把變數宣告放在開頭原因是為了省下 q 為 NULL 時浪費的些許時間，再來我們判斷 q 是否有連結下一個元素，假如沒有則在 free 完 q 後返回，假如有則往下開始 free 連結之元素與字串，在 free 完全部元素後再 free 結構體 q，然後返回。

- q\_insert\_head
進入函數後首先做的事跟其他函數都大同小異，先判斷傳入之 q 是否為空指標，接下來就是 malloc 一塊新節點需要的記憶體，當 malloc 失敗時就如 info 所說的回傳 false 並離開函數，再往下就是 malloc 一塊新字串需要的記憶體，失敗時同上所述，之後再將傳入的字串儲存到這塊新得到的記憶體上，最後在更新 q 中相關成員後離開函數。

- q\_insert\_tail
方法與 q_insert_head 雷同，差別在於最後，此函數主要是更新成員 q->tail 指向之位置。

- q\_remove\_head
此函數重點為在 \*sp 不為空指標的情況下將 q->head 中的字串複製到 \*sp 中，並且要在 q->head 中所儲存之字串的長度小於 bufsize 的條件下才能將字串完整複製到 \*sp 中，否則只複製 bufsize 長度之字串，也就是 truncated string，再來為釋放欲刪除之節點所占用之記憶體，最後在把 q->head 更新完後離開函數。
- q_size
假如 q 不為空指標，則在離開函數時回傳 q 的節點數量，反之直接回傳0。

- q_reverse
宣告三個節點型態(queue_t)的指標，previous, preceding, tmp,其中 previous 顧名思義為儲存前一個節點位置之指標，而 preceding 則儲存當前欲處理之節點之位置，tmp 則用在更新 previous 與 preceding 時暫存下個欲處理節點位置，此三個變數在 while loop 中持續執行直到 preceding 中之內容為 NULL，也就是已經處理到最後一個節點，最後在更新 q 中 head 與 tail 指標後離開函數。

## 心得
在開發過程中學到很多 singly linked list 的思維，或是常識(?，以前對 linked list 的了解只有個概念而沒有實做過其功能，這次實作過程中學到很多東西，像是 free() 只會釋放給定位置占用之記憶體，聽起來可能理所當然，可是我在開發時以為是會一直往裡面釋放指標中存放的記憶體，還有 free() 是一次釋放一整組記憶體，例如:結構體中有兩成員，free() 是一次釋放兩個成員占用的記憶體，了解之後再想一遍都覺得理所當然，之前不知道是怎麼想的...，而這些都是從無數次 seg fault 中學到的...。還有 list 的反轉，一開始誤以為是資料反轉(對 value 下手)...，後面實作完正確功能後還遇到個問題，我的 head 在每次`正反轉`完都會指向 NULL，會有正反轉這名詞出現是因為我沒考慮到反轉後 head 跟 tail 的善後，還搞出個正反反轉...，如此我的 list 在每次正反轉後都會只有 head 一個節點...，這問題我還想了許久，最後是 q_remove_head 這函數，我從一開始就誤解他意思，中間還想過為啥 `make test` 中有個檢驗叫做 truncated string，一直到最後才想通他是啥，也因為如此，我的 q_remove_head() 從一開始實作就有問題，對這次作業我想說...我真是菜雞一隻口合。

## 問題
百思不解 queue.h 中 list_ele_t 跟 struct ELE 的大小為什麼會不一樣，他們不是名稱跟別名的關西嗎?而且他們倆都同樣表示 node。