2024q1 Homework2 (quiz1+2)

# 2024q1 Homework2 (quiz1+2) contributed by < `willyintw` > ## 開發環境 ```shell $ gcc --version gcc (Ubuntu 13.2.0-23ubuntu4) 13.2.0 Copyright (C) 2023 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Address sizes: 39 bits physical, 48 bits virtual Byte Order: Little Endian CPU(s): 8 On-line CPU(s) list: 0-7 Vendor ID: GenuineIntel Model name: Intel(R) Core(TM) i7-8550U CPU @ 1.80GHz CPU family: 6 Model: 142 Thread(s) per core: 2 Core(s) per socket: 4 Socket(s): 1 Stepping: 10 CPU(s) scaling MHz: 18% CPU max MHz: 4000.0000 CPU min MHz: 400.0000 BogoMIPS: 3999.93 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 cons tant_tsc art arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 sdbg fma cx 16 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 pti ssbd ibrs ibpb stibp tpr_shadow flexpriority ept vpid ept_ad fsgsbase tsc_adjust sgx bmi1 avx2 smep bmi2 erms invpcid mpx rdseed adx smap clflushopt intel_pt xsave opt xsavec xgetbv1 xsaves dtherm ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp vnmi md_clear flush_l1d arch_capabilities Virtualization features: Virtualization: VT-x Caches (sum of all): L1d: 128 KiB (4 instances) L1i: 128 KiB (4 instances) L2: 1 MiB (4 instances) L3: 8 MiB (1 instance) NUMA: NUMA node(s): 1 NUMA node0 CPU(s): 0-7 Vulnerabilities: Gather data sampling: Mitigation; Microcode Itlb multihit: KVM: Mitigation: VMX disabled L1tf: Mitigation; PTE Inversion; VMX conditional cache flushes, SMT vulnerable Mds: Mitigation; Clear CPU buffers; SMT vulnerable Meltdown: Mitigation; PTI Mmio stale data: Mitigation; Clear CPU buffers; SMT vulnerable Reg file data sampling: Not affected Retbleed: Mitigation; IBRS Spec rstack overflow: Not affected Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl Spectre v1: Mitigation; usercopy/swapgs barriers and __user pointer sanitization Spectre v2: Mitigation; IBRS; IBPB conditional; STIBP conditional; RSB filling; PBRSB-eIBRS Not affected; BHI Not affected Srbds: Mitigation; Microcode Tsx async abort: Not affected ``` ## 完善 queue.c ### `q_new()` 配置一塊heap空間並使用`INIT_LIST_HEAD`來初始化空的鏈結串列。 ```c /* Create an empty queue */ struct list_head *q_new() { struct list_head *head = calloc(1, sizeof(struct list_head)); if (!head) return NULL; INIT_LIST_HEAD(head); return head; } ``` ### `q_free()` 利用`list_for_each_safe()`來走訪 (traverse) 所有節點，並釋放節點內所占用的記憶體空間；最後釋放鏈結串列本身所占用的記憶體空間。註解說明提到：==list_for_each_safe - Iterate over list nodes and allow deletions== ```c /** * list_for_each_safe - Iterate over list nodes and allow deletions * @node: list_head pointer used as iterator * @safe: list_head pointer used to store info for next entry in list * @head: pointer to the head of the list * * The current node (iterator) is allowed to be removed from the list. Any * other modifications to the the list will cause undefined behavior. */ ``` 因此使用`list_for_each_safe()`可以放心地修改或刪除節點。 ```c /* Free all storage used by queue */ void q_free(struct list_head *head) { struct list_head *node, *safe; element_t *e; if (!head) return; list_for_each_safe(node, safe, head) { e = container_of(node, element_t, list); free(e->value); list_del(node); } free(head); } ``` 加入巨集 (macro) 檢查`free(NULL)`特例。 ```diff /* Free all storage used by queue */ +#define FREE(x) do{if(x)free;x=NULL;}while(0) void q_free(struct list_head *head) { struct list_head *node, *safe; @@ -33,11 +34,11 @@ void q_free(struct list_head *head) list_for_each_safe(node, safe, head) { e = container_of(node, element_t, list); - free(e->value); + FREE(e->value); list_del(node); } - free(head); + FREE(head); } ``` 但是編譯時遇到以下 warning 所以放棄使用巨集 (macro)。 ``` CC queue.o In file included from queue.h:13, from queue.c:5: queue.c: In function ‘q_free’: harness.h:58:14: warning: statement with no effect [-Wunused-value] 58 | #define free test_free | ^~~~~~~~~ queue.c:25:25: note: in expansion of macro ‘free’ 25 | #define FREE(x) do{if(x)free;x=NULL;}while(0) | ^~~~ queue.c:37:9: note: in expansion of macro ‘FREE’ 37 | FREE(e->value); | ^~~~ LD qtest ``` ### `q_insert_head()` ```c /* Insert an element at head of queue */ bool q_insert_head(struct list_head *head, char *s) { element_t *e = calloc(1, sizeof(element_t)); if(!e || !s) return false; e->value = strdup(s); list_add(&e->list, head); return true; } ``` ### `q_insert_tail()` ```c /* Insert an element at tail of queue */ bool q_insert_tail(struct list_head *head, char *s) { element_t *e = calloc(1, sizeof(element_t)); if(!e || !s) return false; e->value = strdup(s); list_add_tail(&e->list, head); return true; } ``` ### `q_remove_head()` ```c /* Remove an element from head of queue */ element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { element_t *e; if(!head || list_empty(head)) return NULL; e = list_first_entry(head, element_t, list); snprintf(sp, bufsize, "%s", e->value); list_del(head->next); return e; } ``` ### `q_remove_tail()` ```c /* Remove an element from tail of queue */ element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize) { element_t *e; if(!head || list_empty(head)) return NULL; e = list_last_entry(head, element_t, list); snprintf(sp, bufsize, "%s", e->value); list_del(head->prev); return e; } ``` ### `q_size()` ```c /* Return number of elements in queue */ int q_size(struct list_head *head) { int size = 0; struct list_head *node; if(!head) return 0; list_for_each(node, head) { size++; } return size; } ``` ### `q_delete_mid()` ### `q_delete_dup()` ### `q_swap()` ### `q_reverse()` ### `q_reverseK()` ### `q_sort()` ### `q_descend()` ### `q_merge()` ## 第一次使用GitHub提交第一次提交發現很多coding style不符合需要改進。 `if` 和`(condition)` 中間要一個空格 `if (condition)` 後面不可以加敘述 (statement) 需單獨一行。 ```diff diff --git a/queue.c b/queue.c index ee598f7..a2ce356 100644 --- a/queue.c +++ b/queue.c @@ -16,7 +16,8 @@ struct list_head *q_new() { struct list_head *head = calloc(1, sizeof(struct list_head)); - if (!head) return NULL; + if (!head) + return NULL; INIT_LIST_HEAD(head); @@ -29,9 +30,10 @@ void q_free(struct list_head *head) struct list_head *node, *safe; element_t *e; - if (!head) return; + if (!head) + return; - list_for_each_safe(node, safe, head) { + list_for_each_safe (node, safe, head) { e = container_of(node, element_t, list); free(e->value); list_del(node); ``` ### 盡可能縮小變數使用範圍 ``` Following files need to be cleaned up: queue.c queue.c:31:16: style: The scope of the variable 'e' can be reduced. [variableScope] element_t *e; ^ Fail to pass static analysis. ``` ### 錯別字提示當commit message有錯字時會提示 ``` Following files need to be cleaned up: queue.c Implement the queu basic function [line 1] - Possible misspelled word(s): queu How to Write a Git Commit Message: https://chris.beams.io/posts/git-commit/ Proceed with commit? [e/n/?] n ```

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.