###### tags: `sysprog2018` # 2018q3 Homework2(lab0) contributed by <`goho302jo03`> :::danger 請持續更新進度！！ --課程助教 ::: >請補上你的實驗環境 >[name=課程助教][color=red] ## 實驗環境 ``` $ cat /etc/lsb-release DISTRIB_ID=Ubuntu DISTRIB_RELEASE=16.04 DISTRIB_CODENAME=xenial DISTRIB_DESCRIPTION="Ubuntu 16.04.4 LTS" ``` ``` $ uname -a Linux merry03 4.4.0-134-generic #160-Ubuntu SMP Wed Aug 15 14:58:00 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux ``` ``` $ lscpu 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: 1 Core(s) per socket: 4 Socket(s): 1 NUMA node(s): 1 Vendor ID: GenuineIntel CPU family: 6 Model: 94 Model name: Intel(R) Core(TM) i5-6500 CPU @ 3.20GHz Stepping: 3 CPU MHz: 2399.875 CPU max MHz: 3600.0000 CPU min MHz: 800.0000 BogoMIPS: 6383.91 Virtualization: VT-x L1d cache: 32K L1i cache: 32K L2 cache: 256K L3 cache: 6144K 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 aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx smx 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 invpcid_single intel_pt ssbd ibrs ibpb stibp kaiser tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 hle avx2 smep bmi2 erms invpcid rtm mpx rdseed adx smap clflushopt xsaveopt xsavec xgetbv1 dtherm ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp flush_l1d ``` ## queue.h 實作 ### Linked List Element ``` typedef struct ELE { char *value; struct ELE *next; } list_ele_t; ``` 以上這段程式碼可以分成兩個區塊來看 1. 定義了一個 ELE 結構 ``` struct ELE { char *value; struct ELE *next; }; ``` 2. 幫這個 struct ELE 起了一個別名叫 list_ele_t ``` typedef struct ELE {...} list_ele_t; ``` ### Queue Structure ``` typedef struct { list_ele_t *head; list_ele_t *tail; int size; } queue_t; ``` - head 這個指標指向了queue最開始的位置，在實作 insert_head 以及 move_head 的時候可以有 O(1) 的時間複雜度。 - tail 在實作 insert_tail 的時候遇到一個限制是必須在時間複雜度為 O(1) 的情況下完成，因此在 queue struct 裡面新增了這個指標指向了 queue 的最尾端，而在 queue 是空的時， head 跟 tail 都會是NULL。 - size 在實作 q_size 時，也是有個限制是必須在時間複雜度 O(1) 下完成，因此加了一個 size 的變數，初始值為 0，會在每次插入節點時 +1，並在刪除節點時 -1，在呼叫 q_size() 時，若 queue 不是 NULL 的話就回傳 size 這個變數的值，因此能在常數時間內完成。 ## queue.c 實作 ### q_new 一開始先試著 alloc 大小為 queue_t 的記憶體，如果 alloc 失敗的話就直接回傳 NULL 表示無法成功創建 queue。如果 alloc 成功的話，因為這個 queue 還是空的，所以就將 queue 的 tail 以及 head 設為 NULL，並將 size 的值設為 0。 ### q_free 首先先檢查傳入的 q 是否為 NULL，如果是的話就不做任何事。必須依序將每個 node 所分配到的空間 free 掉，一直到每個 node 都成功 free 後，最後再 free(q)。 ### q_insert_head、q_insert_tail 首先檢查 q 是否為 NULL，是的話就直接 return false，接著宣告一個型態為 list_ele_t 的 node 並且嘗試 alloc 一段記憶體位址給它，如果失敗的話也是 return false，接著利用 strdup() 這個函式宣告一段記憶體位址給這個 node 的 value，strdup() 成功的話會回傳一個地址，失敗的話則回傳 NULL，若回傳值為 NULL 則先 free 先前 alloc 給 node 的記憶體，再 return false。 > strdup：會自動 alloc 記憶體給目的的指標，並且把要複製的內容複製到該指標中 > strcpy：目的指標必須是一個已經分配記憶體的位址 - q_insert_head 將新 node 的 next 指向原本 head 指向的位址，並將 head 指向新的 node，接著檢查這個 queue 本來是不是空的，是的話就將 tail 也指向這個新的 node。並且將 size + 1。 - q_insert_tail 將新 node 的 next 指向 NULL，並檢查這個 queue 本來是不是空的，是的話就將 head 也指向這個新的 node，不是的話就把本來 tail 的 next 指向的位址設為這個新 node。最後將 tail 指向新 node，並且將 size + 1。 ### q_size 一開始檢查 queue 是否為 NULL，是的話就回傳 0，不是的話就回傳 queue 的 size，如此一來可以達到 O(1) 的時間複雜度。 ### q_reverse 首先檢查 queue 是否為 NULL，是的話就不做任何事。接著參考 [linklist reverse](https://www.geeksforgeeks.org/reverse-a-linked-list/) 實作，唯一需要注意的就是 head 以及 tail 兩個指標必須對調。 queue 的實作到目前為止在 `make test` 下，拿到了 63 分，除了需要用到 q_remove_head 的 trace 外，其他的 trace 都可以順利通過。 ### q_remove_head 首先檢查 q 是否為 NULL，以及 q_size 是否為 0，這兩種情況下都沒辦法順利的 remove head，因此直接 return false。接著計算在有限的 bufsize 中可以存下多少個 char，宣告一個 tmp 來暫時存放要 remove 掉的那個 node，並且重新 assign head 的位址、size - 1。 接著因為 bufsize 的限制，因此這裡使用了 memcpy 來指定要分配的 memory 大小為何，並將 sp 的最後一個字元設為 null terminator。存取完 value 後就 free 掉 tmp，並且檢查剩餘的 queue size，是否為 0，是的話就把 tail 指向的位址也清空。 在完成了 remove head 的實作後，測試分數成功來到 100/100 ``` --- trace-15-perf 7/7 --- TOTAL 100/100 ```