# 2022q1 Homework1 (lab0)
contributed by < `tseng0201` >
:::danger
在「作業區」以「[固定網址](https://hackmd.io/s/how-to-share-note-tw)」填寫 HackMD 超連結，請注意細節！
:notes: jserv
:::
## 前置作業:
- [x] 閱讀 [你所不知道的C語言：指標篇](https://hackmd.io/@sysprog/c-pointer)
- [X] 閱讀 [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)
- [X] 詳閱 [lab0](https://hackmd.io/@sysprog/linux2022-lab0) 作業需求
## queue.c實現進度:
- [X] q_new: 建立新的「空」佇列;
- [X] q_free: 釋放佇列所佔用的記憶體;
- [X] q_insert_head: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則);
- [x] q_insert_tail 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則);
- [x] q_remove_head: 在佇列開頭 (head) 移去 (remove) 給定的節點;
- [x] q_remove_tail: 在佇列尾端 (tail) 移去 (remove) 給定的節點;
- [x] q_release_element: 釋放特定節點的記憶體空間;
- [x] q_size: 計算目前佇列的節點總量;
- [x] q_delete_mid: 移走佇列中間的節點，詳見 LeetCode 2095. Delete the Middle Node of a Linked List
- [x] q_delete_dup: 在已經排序的狀況，移走佇列中具備重複內容的節點，詳見 LeetCode 82. Remove Duplicates from Sorted List II
- [x] q_swap: 交換佇列中鄰近的節點，詳見 LeetCode 24. Swap Nodes in Pairs
- [X] q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點;
- [x] q_sort: 以遞增順序來排序鏈結串列的節;
## 更多
- [ ] 了解lab0中提到的分析工具 Cppcheck Valgrind Perf
- [x] 在 qtest 提供新的命令 shuffle
- [ ] 在 qtest 提供新的命令 web
- [ ] 解釋 select 系統呼叫在本程式的使用方式，並分析 console.c 的實作，說明其中運用 CS:APP RIO 套件 的原理和考量點。
- [ ] 研讀論文〈Dude, is my code constant time?〉，解釋本程式的 “simulation” 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student’s t-distribution 及程式實作的原理。注意：現有實作存在若干致命缺陷，請討論並提出解決方案;
- [ ] 指出現有程式的缺陷 (提示: 和 RIO 套件 有關) 或者可改進之處 (例如更全面地使用 Linux 核心風格的鏈結串列 API)，嘗試實作並提交 pull request
## 實驗環境:
```shell
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 39 bits physical, 48 bits virtual
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: 94
Model name: Intel(R) Core(TM) i7-6700 CPU @ 3.40GHz
Stepping: 3
CPU MHz: 816.656
CPU max MHz: 4000.0000
CPU min MHz: 800.0000
BogoMIPS: 6799.81
Virtualization: VT-x
L1d cache: 128 KiB
L1i cache: 128 KiB
L2 cache: 1 MiB
L3 cache: 8 MiB
NUMA node0 CPU(s): 0-7
```
## queue.c實現:
想法 ：利用 linux 已經實現的 `struct list_head` 與其相關巨集/函式進行 queue 節點間的移動,再透過 container_of / list_entry 取得其他該節點的成員進行操作
### 自定義struct
#### q_head
在原有的head定義下新增 count 用於計算queue的長度,
count 為0時代表一個空的 queue
```c
typedef struct {
int count;
struct list_head group;
} q_head;
```
### 定義queue節點
#### queue_member
已定義於queuq.h
藉由定義好的 struct list_head 進行節點間的移動, 以成員 value(pointer to char）紀錄該節點的資料
```c
* Linked list element */
typedef struct {
/* Pointer to array holding string.
* This array needs to be explicitly allocated and freed
*/
char *value;
struct list_head list;
} element_t;
```
### 自定義函式
q_delete_element()
delete 一個 queue member 先移出 queue 再釋放其記憶體位置
```c
void q_delete_element(struct list_head *node)
{
if (!node) {
return;
}
list_del(node);
free(list_entry(node, element_t, list)->value);
free(list_entry(node, element_t, list));
}
```
#### void list_swap()
交換兩個 list_head* 所指向的位置
```c
void list_swap(struct list_head **list_addr1 ,struct list_head **list_addr2 )
{
struct list_head *temp = *list_addr2;
*list_addr2 = *list_addr1;
*list_addr1 = temp;
}
```
### 實現的函式
#### q_new()
建立一個空的queue head，並將 count 設為0
並透過 INIT_LIST_HEAD() 將 prev, next指標都指向自己
當 memory allocate 失敗將會返回 NULL
新增
當 allocate 失敗時回傳 NULL 不再進行後續操作
```c
struct list_head *q_new()
{
q_head *temp = malloc(sizeof(q_head));
if (!temp) {
return NULL;
}
temp->count = 0;
INIT_LIST_HEAD(&temp->list);
return &temp->list;
}
```
#### q_free()
將整個 queue 包含 queue head 所佔用的記憶體釋放,由於 queue 的資料是由 pointer 紀錄,所以要先釋放掉其指向的記憶體,再釋放掉節點本身
函式透過 temp 紀錄要消除的節點, 並修改 queue head 的 next 紀錄下一個要消去的節點, 最後才將queue head 釋放
```c
void q_free(struct list_head *l)
{
if (!l) {
return;
}
struct list_head *temp = l->next;
while (l != temp) {
l->next = temp->next;
free(list_entry(temp, element_t, list)->value);
free(list_entry(temp, element_t, list));
temp = l->next;
}
free(list_entry(l, q_head, list));
return;
}
```
#### q_insert_head
建立一個新的節點插入在 head next, 由於字串是由 pointer傳入 無法使用 sizeof 取得字串長度所以直接使用 for loop 計算長度後再分配適當的空間
建立新的節點後使用 list_add 自動將其指標指向正確位置
使用strlcpy 而非 strncpy 兩者都可以防止輸入大於分配的空間,但strlcpy還會將最後一個改為 '\0' 用起來更安全
新增
當 data malloc 失敗時函式回傳 false,且要將剛建立的 element_t 物件釋放 (free)
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head) {
return false;
}
element_t *temp_member = malloc(sizeof(element_t));
if (!temp_member) {
return false;
}
int count = 0;
for (; s[count]; count++) {
};
temp_member->value = malloc(count + 1 * sizeof(char));
//check successful malloc
if (!temp_member->value ) {
free(temp_member);
return false;
}
strlcpy(temp_member->value, s, count + 1);
list_add(&temp_member->list, head);
list_entry(head, q_head, list)->count += 1;
return true;
}
```
#### q_insert_tail
同 q_insert_head ,但指標操作改為list_add_tail
新增
當 data malloc 失敗時函式回傳 false,且要將剛建立的 element_t 物件釋放 (free)
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head) {
return false;
}
element_t *temp_member = malloc(sizeof(element_t));
if (!temp_member) {
return false;
}
int count = 0;
for (; s[count]; count++) {
};
temp_member->value = malloc(count + 1 * sizeof(char));
if (!temp_member->value ) {
free(temp_member);
return false;
}
strlcpy(temp_member->value, s, count + 1);
list_add_tail(&temp_member->list, head);
list_entry(head, q_head, list)->count += 1;
return true;
}
```
#### q_size
回傳 queue 的長度, 直接回傳 q_head 的 count 即可
```c
int q_size(struct list_head *head)
{
if (!head) {
return 0;
}
return list_entry(head, q_head, group)->count;
}
```
#### q_remove_head
將第一個 queue 節點從 queue 中斷開, 並將其 value 轉移至
sp
當 head 為 NULL 或 empty 時回傳 NULL
使用strlcpy 進行字串複製這樣會自動在最後加上 '\0'
並使用list_del進行 queue之間的修改
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head)){
return NULL;
}
element_t *temp = list_entry(head->next, element_t, list);
list_del(head->next);
if (sp) {
strlcpy(sp, temp->value, bufsize);
}
list_entry(head, q_head, list)->count -= 1;
return temp;
}
```
#### q_remove_tail
刪除queue中最後的節點 ,概念q_remove_head
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head)){
return NULL;
}
element_t *temp = list_entry(head->prev, element_t, list);
list_del(head->prev);
if (sp) {
strlcpy(sp, temp->value, bufsize);
}
list_entry(head, q_head, list)->count -= 1;
return temp;
}
```
#### q_size
回傳 queue 的長度, 直接回傳 q_head 的 count 即可
```c
int q_size(struct list_head *head)
{
if (!head) {
return 0;
}
return list_entry(head, q_head, group)->count;
}
```
#### q_delete_mid
移除queue中間的節點, 透過 queue head 的 count 即可快速求出該中間節點,透過ptr移動至該節點後先移出(remove) queue 再進行刪除(delete)
count 要減1
待改進的點 :
head 其實算完 count 後不需要了可以直接拿來當ptr
```c
bool q_delete_mid(struct list_head *head)
{
if (!head || list_empty(head)) {
return false;
}
int n = list_entry(head, q_head, list)->count-- / 2;
// list_entry(head, q_head, list)->count -= 1;
struct list_head *ptr = head->next;
while (n--) {
ptr = ptr->next;
}
q_delete_element(ptr);
return true;
}
```
#### q_delete_dup
把重複的節點都刪除 e.g. old: 1->2->2->3 改為 1->3
注意 ：此程式必須為排序過的 list 才適用
設定 ptr 為當前節點的節點並與 ptr->next 比較,如果相同則刪除ptr->next 否則該節點保留
kill_self 用來紀錄當前 ptr 是否為duplicate的一部分 如果kill_self 為 true 則節點也應該刪除
```c
bool q_delete_dup(struct list_head *head)
{
if (!head) {
return false;
}
if (list_empty(head) || list_is_singular(head)) {
return true;
}
int count = list_entry(head, q_head, list)->count;
struct list_head * ptr = head->next;
bool kill_self = false;
while (ptr != head && ptr->next != head) {
while (ptr->next != head && !strcmp(list_entry(ptr, element_t, list)->value, list_entry(ptr->next, element_t, list)->value)) {
q_delete_element(ptr->next);
count--;
kill_self = true;
}
ptr = ptr->next;
if (kill_self) {
q_delete_element(ptr->prev);
kill_self = false;
count--;
}
}
list_entry(head, q_head, list)->count = count;
return true;
}
```
#### q_swap()
將 queue 中的節點每兩個兩個相反,且不能改變node value
e.g. a->b->c->d 改為b->a->d->c
此程式以單向 link_list 方向思考,最後再以 while 迴圈將prev 指向正確的節點
ptr 紀錄當前節點 first second 紀錄當前節點的下個與下下個
代表要交換的兩個節點
```c
void q_swap(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head)) {
return;
}
struct list_head * ptr = head;
while (ptr->next != head && ptr->next->next != head) {
struct list_head * first = ptr->next;
struct list_head * second = ptr->next->next;
first->next = second->next;
ptr->next = second;
ptr->next->next = first;
ptr = ptr->next->next;
}
ptr = head;
while (ptr->next != head) {
ptr->next->prev = ptr;
ptr = ptr->next;
}
head->prev = ptr;
return ;
}
```
#### q_reverse
由於 queue是雙向的環 所以只要將每個節點(包含 head)的 prev 與 next 指向的位置換就好
```c
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head)) {
return;
}
struct list_head *temp = head;
do {
struct list_head *t = temp->next;
temp->next = temp->prev;
temp->prev = t;
temp = temp->prev;
} while (temp != head);
}
```
#### q_sort
以三個函式實現
1.q_sort : 呼叫界面
2.list_mergesort() : 執行mergesort
3.merge_two_list : 執行merge
##### merge_two_list()
引用：[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-LeetCode-21-Merge-Two-Sorted-Lists)中的實做
進行
概念是讓一個指標 ptr 每次都走向 q_1 或 q_2 value 比較小的節點,然後移動被選中的節點至其下一個,當ptr走完兩個 list 便可得到一個依 value 由小到大串在一起的list
程式碼解析
在引用的實做中, 使用** 進行對指標的紀錄與移動
1.ptrㄧ開始指向節點本身而之後都是指向節點的 next
2.node 為紀錄目前比較小的那個節點並進行操作
```c
*node = (*node)->next
```
上列函式可看做
```c
if(l1 < l2)
l1 = l1->next;
else
l1 = l1->next;
```
3.透過 node 紀錄當前較小的節點並透過 ptr 串起走訪的節點
```c
struct list_head** ptr ;
*ptr = *node;
可以看作
struct list_head* ptr;
ptr->next = (q_1 < q_2) ? q_1 : q_2
```
4.地址的 bitwise操作
c 不允對指標指向的地址做 or 所以將地址強制轉形成 unsigned int 進行操作後再轉回本的型態
C99規格書上面寫道
>6.5.12 BitwiseinclusiveORoperator
>Constraints:
>Each of the operands shall have integer type.
```c
(struct list_head *) ((__UINTPTR_TYPE__) q_1 | (__UINTPTR_TYPE__) q_2);
```
以下為完整程式碼
```c
struct list_head* merge_two_list(struct list_head *q_1,struct list_head *q_2)
{
if (!q_1 || !q_2) return (struct list_head *) ((__UINTPTR_TYPE__) q_1 | (__UINTPTR_TYPE__) q_2);
struct list_head *head = NULL, **ptr = &head, **node;
for (node = NULL; q_1 && q_2; *node = (*node)->next) {
node = (strcmp(list_entry(q_1, element_t, list)->value, list_entry(q_2, element_t, list)->value) <= 0 ) ? &q_1: &q_2;
*ptr = *node;
ptr = &(*ptr)->next;
}
*ptr = (struct list_head *)( (__UINTPTR_TYPE__) q_1 | (__UINTPTR_TYPE__) q_2 );
return head;
}
```
##### merge_two_list()
利用 divine and counquer 的概念進行分割與合併,將原本 queue
分隔為多個長度為1的 queue 後再進行合併,分割使 用slow、fast 指標取的中間的節點、並分為left 與 right 處理
最後回傳merge後的queue
```c
struct list_head* list_mergesort(struct list_head * head)
{
if (!head || !head->next) {
return head;
}
struct list_head *slow = head;
struct list_head *fast = head->next;
for (; fast && fast->next; fast = fast->next->next) {
slow = slow->next;
}
fast = slow->next;
slow->next = NULL;
struct list_head * left = list_mergesort(head);
struct list_head * right = list_mergesort(fast);
return merge_two_list(left, right);
}
```
##### q_sort()
首先先將環狀的queue 斷開成直線的queue
```c
head->prev->next = NULL;
```
再將queue進行sort
```c
head->next = list_mergesort(head->next);
```
最後透過迴圈將 prev 修正並修復回環狀的queue
```c
struct list_head *ptr = head;
while (ptr->next) {
ptr->next->prev = ptr;
ptr = ptr->next;
}
ptr->next = head;
head->prev = ptr;
ptr = head;
```
以下為完整程式碼
```c
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head)) {
return;
}
head->prev->next = NULL;
head->next = list_mergesort(head->next);
struct list_head *ptr = head;
while (ptr->next) {
ptr->next->prev = ptr;
ptr = ptr->next;
}
ptr->next = head;
head->prev = ptr;
ptr = head;
return;
}
```
### 更多
#### 在 qtest 提供新的命令 shuffle
##### shuffle實現
使用 Fisher–Yates shuffle 演算法,每次隨機選擇一個節點與最後一個尚未交換過的節點交換其 value (不改變節點順序)
```c
void q_shuffle(struct list_head *head)
{
//檢查head 是否需要進行shuffle
if (!head || list_empty(head) || list_is_singular(head)) {
return;
}
//取的目前的節點數
int count = list_entry(head, q_head, list)->count;
//紀錄最後一個尚未交換過的節點
struct list_head *last = head->prev;
//不斷的進行隨機的交換
for (; count >1; count--) {
int need_change = rand()%count;
struct list_head *ptr = head->next;
//移動指標至被選到的節點
for(; need_change > 0; need_change--) {
ptr = ptr->next;
}
//交換被選到的節點與最後的節點
char *temp = list_entry(last, element_t, list)->value;
list_entry(last, element_t, list)->value = list_entry(ptr, element_t, list)->value;
list_entry(ptr, element_t, list)->value = temp;
last = last->prev;
}
return;
}
```
##### 修改qtest
根據 lab0 的引導在 console_init()新增指令shuffle, 並實現 do_shuffle 函式進行 q_shuffle
此函式參考 do_swap() 實現
```c
static bool do_shuffle(int argc, char *argv[])
{
//檢查時否有輸入其他參數
if (argc != 1) {
report(1, "%s takes no arguments", argv[0]);
return false;
}
//檢查queue是否已建立
if (!l_meta.l)
report(3, "Warning: Try to access null queue");
error_check();
set_noallocate_mode(true);
if (exception_setup(true))
q_shuffle(l_meta.l);
exception_cancel();
set_noallocate_mode(false);
show_queue(3);
return !error_check();
}
```
Sign in with Wallet
Connect another wallet