---
tags: linux2022
---
# 2022q1 Homework1 (lab0)
contributed by < `ioksengtan` >
## 實驗環境
```shell
$ gcc --version
Configured with: --prefix=/Library/Developer/CommandLineTools/usr --with-gxx-include-dir=/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/4.2.1
Apple clang version 12.0.5 (clang-1205.0.22.11)
Target: arm64-apple-darwin20.5.0
Thread model: posix
```
## [作業要求](https://hackmd.io/@sysprog/linux2022-lab0)
### Queue operation implementation
- [x] `q_new`: 建立新的「空」佇列
- [ ] error handling: old blocks are still allocated
- [x] `q_size`: 計算目前佇列的節點總量
- [x] `q_insert_head`: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則)
- [x] `q_insert_tail`: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則)
- [x] issue: corruption when attempting to free queue after insert node to tail.
- [ ] what's the difference between &(ele->list) and &ele->list
- [ ] what’s the difference between strdup and malloc+memset+strncpy ?
- [x] `q_remove_head`: 在佇列開頭 (head) 移去 (remove) 給定的節點
- [x] ERROR: Corruption detected in block with address 0x123f04140 when attempting to free it
- [x] `q_remove_tail`: 在佇列尾端 (tail) 移去 (remove) 給定的節點
- [x] `q_free`: 釋放佇列所佔用的記憶體
- [x] `q_reverse`: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點
- [x] `q_delete_mid`: 移走佇列中間的節點
- [x] LeetCode 2095. Delete the Middle Node of a Linked List
- [x] pseudo diagram
- [x] `q_delete_dup`: 在已經排序的狀況，移走佇列中具備重複內容的節點
- [x] LeetCode 82. Remove Duplicates from Sorted List II
- [x] pseudo diagram
- [ ] what if the list is not sorted
- [ ] `q_swap`: 交換佇列中鄰近的節點
- [ ] LeetCode 24. Swap Nodes in Pairs
- [ ] `q_sort`: 以==遞增順序==來排序鏈結串列的節點
### new command implementation
- [ ] shuffle
提供新的命令 shuffle，允許藉由 Fisher–Yates shuffle 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作
- [ ] web
提供新的命令 web，提供 web 伺服器功能，注意: web 伺服器運作過程中，qtest 仍可接受其他命令
### Documentation in Devlog
- [ ] 開啟 Address Sanitizer，修正 qtest 執行過程中的錯誤
先執行 qtest 再於命令提示列輸入 help 命令，會使 開啟 Address Sanitizer 觸發錯誤，應予以排除
- [ ] 運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 “simulation” 過程中的記憶體使用量，需要設計對應的實驗
- [ ] 解釋 select 系統呼叫在本程式的使用方式，並分析 console.c 的實作，說明其中運用 CS:APP RIO 套件 的原理和考量點。可對照參考 CS:APP 第 10 章重點提示
- [ ] 研讀論文〈Dude, is my code constant time?〉，解釋本程式的 “simulation” 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student’s t-distribution 及程式實作的原理。注意：現有實作存在若干致命缺陷，請討論並提出解決方案;
:::danger
Improve your writing! It is supposed to be an official document.
:notes: jserv
:::
:::info
Thanks a lot jserv for feedback.
I will continue refining my documentation.
:notes: ioksengtan
:::
## Queue operation implementation
### q_size
list_for_each
```c
int q_size(struct list_head *head)
{
if (!head)
return 0;
int len = 0;
struct list_head *li;
list_for_each (li, head)
len++;
return len;
}
```
### q_new
1. create a new element
2. return the pointer to the next list
```c
struct list_head *q_new()
{
element_t *q = malloc(sizeof(element_t));
if (q == NULL) {
return NULL;
}
INIT_LIST_HEAD(&q->list);
return &q->list;
}
```
```
cmd> new
Freeing old queue
l = NULL
ERROR: Freed queue, but 2 blocks are still allocated
l = []
```
reference: https://myao0730.blogspot.com/2016/12/linux.html
### q_insert_head
1. new an element
2. new_ele->next = head->next
3. head->next = new_ele
using provided list_add() in list.h
```c
/**
* list_add() - Add a list node to the beginning of the list
* @node: pointer to the new node
* @head: pointer to the head of the list
*/
static inline void list_add(struct list_head *node, struct list_head *head)
{
struct list_head *next = head->next;
next->prev = node;
node->next = next;
node->prev = head;
head->next = node;
}
```
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *ele = malloc(sizeof(element_t));
if (!ele)
return false;
ele->value = malloc(sizeof(s));
memset(ele->value, '\0', strlen(ele->value));
strncpy(ele->value, s, strlen(s));
list_add(&ele->list, head);
return true;
}
```
#### testing
```
cmd> new
l = []
cmd> ih test
l = [test]
cmd> ih test2
l = [test2 test]
```
### q_insert_tail
reuse list_add_tail in list.h
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *ele = malloc(sizeof(element_t));
if (!ele)
return false;
ele->value = malloc(sizeof(s));
memset(ele->value, '\0', strlen(ele->value));
strncpy(ele->value, s, strlen(s));
list_add_tail(&ele->list, head);
return true;
}
```
#### issue:
```
cmd> new
l = []
cmd> it test
l = [test]
cmd> free
ERROR: Corruption detected in block with address 0x12ef04130 when attempting to free it
l = NULL
```
##### Observation on solution
Corruption detected:
```c=
ele->value = malloc(sizeof(s));
memset(ele->value, '\0', strlen(ele->value));
strncpy(ele->value, s, strlen(s));
```
No Corruption detection:
```c=
ele->value = strdup(s);
```
Revised implementation of q_insert_tail
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *ele = malloc(sizeof(element_t));
if (!ele)
return false;
ele->value = strdup(s);
list_add_tail(&ele->list, head);
return true;
}
```
:::danger
You must explain your observations and reactions.
:notes: jserv
:::
:::info
Thanks alot jserv for feedback,
I am cooking those information then document it later.
:notes: ioksengtan
:::
Then there is no corruption
```
cmd> new
l = []
cmd> it test
l = [test]
cmd> rt
Removed test from queue
l = []
cmd> it test
l = [test]
cmd> free
l = NULL
```
#### discussion: what's the difference between strdup and malloc+memset+strncpy ?
#### discussion: what's the difference between following two lines?
(1) ```list_add_tail(&(ele->list), head);```
(2) ```list_add_tail(&ele->list, head);```
using (1), will fail the static analysis when git commit.
```
lab0-c git:(master) ✗ git commit -a
Following files need to be cleaned up:
queue.c
queue.c:118:5: error: Memory leak: ele [memleak]
return true;
^
```
#### testing
```
cmd> new
l = []
cmd> it test
l = [test]
cmd> it test2
l = [test test2]
cmd> it test3
l = [test test2 test3]
```
### q_remove_head
```c=
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
if (sp) {
element_t *e = list_first_entry(head, element_t, list);
size_t len = strlen(e->value);
len = (bufsize-1)>len?len:(bufsize-1);
memcpy(sp, e->value, len);
sp[len] = '\0';
list_del(&e->list);
return e;
}
return NULL;
}
```
#### testing
```
cmd> new
l = []
cmd> ih test
l = [test]
cmd> ih test2
l = [test2 test]
cmd> rh
Removed test2 from queue
l = [test]
```
### q_free
1. given the pointer of queue head
2. using provided q_release_element(element_t *e)
3. release all elements until end of queue
```c=
void q_free(struct list_head *l)
{
if (l == NULL) {
return;
}
struct list_head *node = l->next;
while (node != l) {
element_t *e = container_of(node, element_t, list);
node = node->next;
q_release_element(e);
}
// cppcheck-suppress nullPointer
element_t *head = container_of(l, element_t, list);
free(head);
}
```
Following implementation is wrongful, causing segmentation fault.
```c
if (!l)
return;
// iterate over the list entries and remove it
element_t *entry, *safe;
list_for_each_entry_safe (entry, safe, l, list)
q_release_element(entry);
free(l);
```
```
cmd> new
l = []
cmd> ih test
l = [test]
cmd> ih test2
l = [test2 test]
cmd> free
ERROR: Attempted to free unallocated block. Address = 0x15bf042b8
ERROR: Attempted to free unallocated or corrupted block. Address = 0x15bf042b8
Segmentation fault occurred. You dereferenced a NULL or invalid pointer
```
### q_delete_mid
when number is even (N=4)
```graphviz
digraph {
rankdir=LR;
size="8,5"
node [shape = circle];
"head"->"node"
"node"->"node2"
"node2"->"node3"
"node3"->"node_tail"
"*front"->"node"[color=Red]
"*end"->node_tail[color=Red]
}
```
```graphviz
digraph {
rankdir=LR;
size="8,5"
node [shape = circle];
"head"->"node"
"node"->"node2"
"node2"->"node3"
"node3"->"node_tail"
"*front"->"node2"[color=Red]
"*end"->node3[color=Red]
}
```
if front->next = end, remove node3
```graphviz
digraph {
rankdir=LR;
size="8,5"
node [shape = circle];
"head"->"node"
"node"->"node2"
"node2"->"node_tail"
"*front"->"node2"[color=Red]
"*end"->node3[color=Red]
}
```
when number is odd (N=3)
```graphviz
digraph {
rankdir=LR;
size="8,5"
node [shape = circle];
"head"->"node"
"node"->"node2"
"node2"->"node_tail"
"*front"->"node"[color=Red]
"*end"->node_tail[color=Red]
}
```
```graphviz
digraph {
rankdir=LR;
size="8,5"
node [shape = circle];
"head"->"node"
"node"->"node2"
"node2"->"node_tail"
"*front"->"node2"[color=Red]
"*end"->node2[color=Red]
}
```
if front = end, remove node2
```graphviz
digraph {
rankdir=LR;
size="8,5"
node [shape = circle];
"head"->"node"
"node"->"node_tail"
"*front"->"node2"[color=Red]
"*end"->node2[color=Red]
}
```
```c=
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
if (!head || list_empty(head)) {
return false;
}
struct list_head *front = head->next;
struct list_head *end = head->prev;
while (true) {
if (front == end || front->next == end){
list_del(front);
q_release_element(list_entry(front, element_t, list));
break;
}
front = front->next;
end = end->prev;
}
return true;
}
```
### q_delete_dup
### q_swap
### q_sort
worst case:
1. quick sort: time: O(N^2), spce: O(N)
2. merge sort: time: O(nlogn), spce: O(N)
看到一些同學實作quick sort有遇到效能的問題。
複習了sort 的時空複雜度，的確quick sort 的最差情境會是N^2。
merge sort原理：
1. 將原始的list 以二分法切成最小單位(N=2 or 1)的sorted list
2. 再兩兩一組合併回來 ([Leetcode 24 Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/))
### web
Sign in with Wallet
Connect another wallet