# 2022q1 Homework1 (lab0)
contributed by < `Shawn5141` >
# Homework Requirement
- [x] fork [lab-c](https://github.com/sysprog21/lab0-c)
- [ ] 依據上述指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改，要能滿足 $ make test 自動評分系統的所有項目。
- [x] 詳閱 [如何寫好 Git Commit Message](https://blog.louie.lu/2017/03/21/%E5%A6%82%E4%BD%95%E5%AF%AB%E4%B8%80%E5%80%8B-git-commit-message/)
- [x] 詳閱[「你所不知道的 C 語言: linked list 和非連續記憶體」](https://hackmd.io/@sysprog/c-linked-list)
- [ ] 研讀 Linux 核心原始程式碼的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差
- [x] 完成Function requirement (詳見下面)
- [x] 在 qtest 提供新的命令 shuffle，允許藉由 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作
- [ ] 在 qtest 提供新的命令 web，提供 web 伺服器功能，注意: web 伺服器運作過程中，qtest 仍可接受其他命令。
- [ ] 嘗試整合 [tiny-web-server](https://github.com/7890/tiny-web-server)
- [ ] 編輯「[作業區](https://hackmd.io/@sysprog/linux2022-homework1)」
- [x] 增添開發紀錄和 GitHub 連結
- [x] 提及你如何逐步達到自動評分程式的要求
- [x] 開啟 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer)，修正 qtest 執行過程中的錯誤
- [x] 運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 “simulation” 過程中的記憶體使用量，需要設計對應的實驗
- [ ] 解釋 select 系統呼叫在本程式的使用方式，並分析 console.c 的實作，說明其中運用 CS:APP RIO 套件 的原理和考量點
- [ ] 研讀論文〈Dude, is my code constant time?〉，解釋本程式的 “simulation” 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student’s t-distribution 及程式實作的原理。注意：現有實作存在若干致命缺陷，請討論並提出解決方案
- [ ] 指出現有程式的缺陷 (提示: 和 RIO 套件 有關) 或者可改進之處
# Quiz1 Answer and Discussion
- [x] [2022q1-quiz1](https://hackmd.io/@kDjnp2cDTDSkoyWftnjw5A/2022q1-quiz1/edit)
# Function Requirement
- [x] q_new: create new "empty" queue.
- [x] q_free: release memory of queue.
- [x] q_insert_head: insert new node after head.
- [x] q_insert_tail: insert new node after tail.
- [x] q_remove_head: 在佇列開頭 (head) 移去 (remove) 給定的節點;
- [x] q_remove_tail: 在佇列最後 (head-prev) 移去 (remove) 給定的節點;
- [x] q_release_element: 釋放特定節點的記憶體空間;
- [x] q_size: 計算目前佇列的節點總量;
- [x] q_delete_mid: 移走佇列中間的節點，詳見 [LeetCode 2095. Delete the Middle Node of a Linked List](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/)
- [x] q_delete_dup: 在已經排序的狀況，移走佇列中具備重複內容的節點，詳見 [LeetCode 82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)
- [x] q_swap: 交換佇列中鄰近的節點，詳見 [LeetCode 24. Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/)
- [x] q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點;
- [x] q_sort: 以遞增順序來排序鏈結串列的節點，可參閱 Linked List Sort 得知實作手法;
- [x] helper functions:
- [x] __q_ele_new: 產生新的element，並把list_head放進去。
- [x] __q_ele_remove: 把element 從指定位置移除
- [x] __q_ele_mid: 找出中間的element
- [x] __mergesort:
- [x] __merge_two_lists:
## queue_new:
Create a new, empty queue. Because it's empty queue, initilize empty list will suffice the requirement here.
```cpp
struct list_head *q_new()
{
struct list_head *l = malloc(sizeof(struct list_head));
if (l == NULL)
return NULL;
INIT_LIST_HEAD(l);
return &l;
}
```
After allocating queue memory (element_t), use [linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) macro [INIT_LIST_HEAD](https://github.com/torvalds/linux/blob/9195e5e0adbb8a9a5ee9ef0f9dedf6340d827405/include/linux/list.h#L35) to initialize list_head member element.
- Time complexity:
- Space complexity:
## queue_free:
Free all storage used by a queue.
1. Use list_for_each_safe to iterate through queue and call list_del to remove list entry. [Comparison for list_for_each vs list_for_each_safe](https://biscuitos.github.io/blog/LIST_ADV_safe/). If there is char array in element_t, those memory also need bo be freed. After char array is cleaned, element would be freed entirely.
```cpp=
/* Free all storage used by queue */
void q_free(struct list_head *l) {
if (!l)
return;
if (list_empty(l)){
free(l);
return;
}
element_t* element, *n;
list_for_each_entry_safe(element, n, l, list) {
if (element->value)
free(element->value);
free(element);
}
free(l);
}
```
- Time complexity:
- Space complexity:
## queue_insert_head
Attempt to insert a new element at the head of the queue (LIFO discipline).
1. Allocate memory for element_t and char array through self-defined function q_ele_new (described latter).
2. Use linux list_add macr to add newly allocated element's list_head to head of list.
```cpp
/*
* Attempt to insert element at head of queue.
* Return true if successful.
* Return false if q is NULL or could not allocate space.
* Argument s points to the string to be stored.
* The function must explicitly allocate space and copy the string into it.
*/
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *ele = NULL;
if (!q_ele_new(&ele, s)) {
return false;
}
list_add(&(ele->list), head);
return true;
}
```
- Time complexity:
- Space complexity:
## queue_insert_tail
Attempt to insert a new element at the tail of the queue (FIFO discipline).
1. Allocate memory for element_t and char array through self-defined function q_ele_new (described latter).
2. Use linux list_add_tail macr to add newly allocated element's list_head to end of list.
```cpp
/*
* Attempt to insert element at tail of queue.
* Return true if successful.
* Return false if q is NULL or could not allocate space.
* Argument s points to the string to be stored.
* The function must explicitly allocate space and copy the string into it.
*/
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *ele = NULL;
if (!q_ele_new(&ele, s)) {
return false;
}
list_add_tail(&(ele->list), head);
return true;
}
```
- Time complexity:
- Space complexity:
## q_remove_head
Refering to self-defined function `__q_remove`. By providing pointer to first list_head element. It would
- Retrieve first element using list_entry.
- Utilize list_del to remove first element's list_head without delete it.
```cpp
/*
* Attempt to remove element from head of queue.
* Return target element.
* Return NULL if queue is NULL or empty.
* If sp is non-NULL and an element is removed, copy the removed string to *sp
* (up to a maximum of bufsize-1 characters, plus a null terminator.)
*
* NOTE: "remove" is different from "delete"
* The space used by the list element and the string should not be freed.
* The only thing "remove" need to do is unlink it.
*
* REF:
* https://english.stackexchange.com/questions/52508/difference-between-delete-and-remove
*/
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head)
return NULL;
return __q_remove(head->next, sp, bufsize);
}
```
## q_remove_tail
Refering to self-defined function `__q_remove`. By providing pointer to last list_head element. It would
- Retrieve last element using list_entry.
- Utilize list_del to remove first element's list_head without deleting it.
```cpp
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head)
return NULL;
return __q_remove(head->prev, sp, bufsize);
}
```
## q_delete_mid
Use slow-fast pointer technique to find out middle point (Refers to helper function `__q_ele_mid`)
```cpp
/*
* Delete the middle node in list.
* The middle node of a linked list of size n is the
* ⌊n / 2⌋th node from the start using 0-based indexing.
* If there're six element, the third member should be return.
* Return NULL if list is NULL or empty.
*/
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
element_t *element = __q_ele_mid(head);
if (element == NULL)
return NULL;
list_del_init(&element->list);
q_release_element(element);
return true;
}
```
## q_delete_dup
- Initilize left and right pointer.
```graphviz
digraph ele_list {
rankdir=LR;
node[shape=record];
e1 [label="head node|{<left>prev|<right>next}", style="bold", color=grey];
h [label="left", style=dashed, color=grey];
h -> e2:up:w [style=dashed, color=grey];
e2 [label="4|{<left>prev|<right>next}", style="bold"];
h1 [label="right", style=dashed, color=grey];
h1 -> e4:up:w [style=dashed, color=grey];
e4 [label="4|{<left>prev|<right>next}", style="bold"];
e5 [label="1|{<left>prev|<right>next}", style="bold"];
e1:right:e -> e2:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e2:right:e -> e4:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e4:right:e -> e5:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e5:right:e -> e1:left:w[arrowhead=normal, arrowtail=normal, dir=both];
}
```
- Proceed to while loop when both left and right value are same
- Assign right pointer to tmp pointer
- Move right pointer to it's next
- Delete right pointer
```graphviz
digraph ele_list {
rankdir=LR;
node[shape=record];
e1 [label="head node|{<left>prev|<right>next}", style="bold", color=grey];
h [label="left", style=dashed, color=grey];
h -> e2:up:w [style=dashed, color=grey];
e2 [label="4|{<left>prev|<right>next}", style="bold"];
h1 [label="tmp(delete)", style=dashed, color=grey];
h1 -> e4:up:w [style=dashed, color=grey];
e4 [label="4|{<left>prev|<right>next}", style="bold"];
h2 [label="right", style=dashed, color=grey];
h2 -> e5:up:w [style=dashed, color=grey];
e5 [label="1|{<left>prev|<right>next}", style="bold"];
e1:right:e -> e2:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e2:right:e -> e4:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e4:right:e -> e5:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e5:right:e -> e1:left:w[arrowhead=normal, arrowtail=normal, dir=both];
}
```
```graphviz
digraph ele_list {
rankdir=LR;
node[shape=record];
e1 [label="head node|{<left>prev|<right>next}", style="bold", color=grey];
h [label="left", style=dashed, color=grey];
h -> e2:up:w [style=dashed, color=grey];
e2 [label="4|{<left>prev|<right>next}", style="bold"];
h2 [label="right", style=dashed, color=grey];
h2 -> e5:up:w [style=dashed, color=grey];
e5 [label="1|{<left>prev|<right>next}", style="bold"];
e1:right:e -> e2:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e2:right:e -> e5:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e5:right:e -> e1:left:w[arrowhead=normal, arrowtail=normal, dir=both];
}
```
- If dup_flag is on, delete left pointer
```graphviz
digraph ele_list {
rankdir=LR;
node[shape=record];
e1 [label="head node|{<left>prev|<right>next}", style="bold", color=grey];
h2 [label="right", style=dashed, color=grey];
h2 -> e5:up:w [style=dashed, color=grey];
e5 [label="1|{<left>prev|<right>next}", style="bold"];
e1:right:e -> e5:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e5:right:e -> e1:left:w[arrowhead=normal, arrowtail=normal, dir=both];
}
```
- Move right pointer to it's next and terminate while loop when right pointer is point to head
```graphviz
digraph ele_list {
rankdir=LR;
node[shape=record];
h2 [label="right", style=dashed, color=grey];
h2 -> e1:up:w [style=dashed, color=grey];
e1 [label="head node|{<left>prev|<right>next}", style="bold", color=grey];
e5 [label="1|{<left>prev|<right>next}", style="bold"];
e1:right:e -> e5:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e5:right:e -> e1:left:w[arrowhead=normal, arrowtail=normal, dir=both];
}
```
- On the other hand, if there is no duplicate element in sorted list, the left pointer and right pointer will just continue proceed to next til right pointer point to head.
```cpp
/*
* Version 2
* Delete all nodes that have duplicate string,
* leaving only distinct strings from the original list.
* Return true if successful.
* Return false if list is NULL.
*
* Note: this function always be called after sorting, in other words,
* list is guaranteed to be sorted in ascending order.
*/
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head || list_empty(head))
return false;
if (list_is_singular(head))
return true;
// Use two pointer to iterate through list
struct list_head *left = head->next;
struct list_head *right = head->next->next;
bool dup_flag = false;
while (1) {
// If left value is equal to right value, entering inner while loop
while (right != head &&
!strcmp(
// cppcheck-suppress nullPointer
list_entry(left, element_t, list)->value,
// cppcheck-suppress nullPointer
list_entry(right, element_t, list)->value)) {
list_del(left);
// cppcheck-suppress nullPointer
q_release_element(list_entry(left, element_t, list));
left = right;
right = right->next;
dup_flag = true;
}
if (dup_flag) {
dup_flag = false;
list_del(left);
// cppcheck-suppress nullPointer
q_release_element(list_entry(left, element_t, list));
}
if (right == head)
break;
left = right;
right = right->next;
}
return true;
}
```
:::warning
Shorten the above code snip by effective techniques.
:notes: jserv
:::
:::info
Verson2:
Still require dup_flag. But release left pointer instead of right one. Need to come up with more effective techniques latter.
:::
## q_swap
Move node in front of fack node and proceed node two step further
```cpp
/*
* Attempt to swap every two adjacent nodes.
*/
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (!head || list_empty(head) || list_is_singular(head))
return;
for (struct list_head *node = head->next->next;
node != head && node != head->next; node = node->next->next->next) {
// Move node in front of fack node and proceed node two step further
struct list_head *fake_head = node->prev->prev;
list_move(node, fake_head);
}
}
```
## q_reverse
1. Create prev_node and next_node pointer pointing to head.
2. Create curr_node pointer pointing to next list_head in list.
```graphviz
digraph ele_list {
rankdir=LR;
node[shape=record];
prevNode [label="prev_node", style=dashed, color=grey];
prevNode -> e1:up:w [style=dashed, color=grey];
nextNode [label="next_node", style=dashed, color=grey];
nextNode -> e1:up:w [style=dashed, color=grey];
e1 [label="head node|{<left>prev|<right>next}", style="bold", color=grey];
currNode [label="curr_node", style=dashed, color=grey];
currNode -> e2:up:w [style=dashed, color=grey];
e2 [label="1|{<left>prev|<right>next}", style="bold"];
e4 [label="2|{<left>prev|<right>next}", style="bold"];
e5 [label="3|{<left>prev|<right>next}", style="bold"];
e1:right:e -> e2:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e2:right:e -> e4:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e4:right:e -> e5:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e5:right:e -> e1:left:w[arrowhead=normal, arrowtail=normal, dir=both];
}
```
3. Iterate through list while curr_node is not equal to head
- Assign next_node as next list_head of curr_node.
```graphviz
digraph ele_list {
rankdir=LR;
node[shape=record];
prevNode [label="prev_node", style=dashed, color=grey];
prevNode -> e1:up:w [style=dashed, color=grey];
e1 [label="head node|{<left>prev|<right>next}", style="bold", color=grey];
currNode [label="curr_node", style=dashed, color=grey];
currNode -> e2:up:w [style=dashed, color=grey];
e2 [label="1|{<left>prev|<right>next}", style="bold"];
nextNode [label="next_node", style=dashed, color=grey];
nextNode -> e4:up:w [style=dashed, color=grey];
e4 [label="2|{<left>prev|<right>next}", style="bold"];
e5 [label="3|{<left>prev|<right>next}", style="bold"];
e1:right:e -> e2:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e2:right:e -> e4:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e4:right:e -> e5:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e5:right:e -> e1:left:w[arrowhead=normal, arrowtail=normal, dir=both];
}
```
- Make curr_node pointing it's next pointer to prev_node.
```graphviz
digraph ele_list {
rankdir=LR;
node[shape=record];
prevNode [label="prev_node", style=dashed, color=grey];
prevNode ->first:up:w [style=dashed, color=grey];
first [label="head node|{<left>prev|<right>next}", style="bold", color=grey];
currNode [label="curr_node", style=dashed, color=grey];
currNode -> second:up:w [style=dashed, color=grey];
second [label="1|{<left>prev|<right>next}", style="bold", ];
nextNode [label="next_node", style=dashed, color=grey];
nextNode -> thrid:up:w [style=dashed, color=grey];
thrid [label="2|{<left>prev|<right>next}", style="bold"];
fourth [label="3|{<left>prev|<right>next}", style="bold"];
first:right:e -> second:up:w[arrowhead=normal, arrowtail=normal, dir=single];
thrid:left:e -> second:up:w[arrowhead=normal, arrowtail=normal, dir=single];
second:right:e -> first:up:w[arrowhead=normal, arrowtail=normal, dir=single, color="red"];
thrid:right:e -> fourth:left:w[arrowhead=normal, arrowtail=normal, dir=both];
fourth:right:e -> first:left:w[arrowhead=normal, arrowtail=normal, dir=both];
}
```
- Make prev_node point it's prev pointer to curr_node.
- Let head point it's next to curr_node while point curr_node's prev to head. So that the cycle is closed.
4. Make head eqaul to prev_node.
```cpp
/*
* Reverse elements in queue
* No effect if q is NULL or empty
* This function should not allocate or free any list elements
* (e.g., by calling q_insert_head, q_insert_tail, or q_remove_head).
* It should rearrange the existing ones.
*/
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return ;
struct list_head *prev_node = head;
struct list_head *next_node = head;
struct list_head *curr_node = prev_node->next;
prev_node->prev = prev_node;
prev_node->next = prev_node;
while (curr_node != head) {
next_node = curr_node->next;
curr_node->next = prev_node;
prev_node->prev = curr_node;
head->next = curr_node;
curr_node->prev = head;
prev_node = curr_node;
curr_node = next_node;
}
head = prev_node;
}
```
## q_sort
Developing about iterative merge sort:
Problem:
1. How to intialize pointer to list_head array with default value of empty head.
2. Unable to figure out how to do merge circular sorted list. So decide to turn circular list into normal linked list and convert it back after sorting.
```cpp=
/*
* Sort elements of queue in ascending order
* No effect if q is NULL or empty. In addition, if q has only one
* element, do nothing.
*/
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *node = head->next, *ptr;
// Make it not cicular
head->prev->next = NULL;
head->next = NULL;
node = __mergesort(node);
// Make sure every list's prev and next is pointing to right place
ptr = head;
ptr->next = node;
while (ptr->next) {
ptr->next->prev = ptr;
ptr = ptr->next;
}
// Connect last node'next to head and head's prev to ndoe
ptr->next = head;
head->prev = ptr;
}
```
```cpp=
struct list_head *__mergesort(struct list_head *head)
{
if (!head->next)
return head;
struct list_head *fast = head, *slow = head, *mid;
while (true) {
if (!fast->next || !fast->next->next)
break;
fast = fast->next->next;
slow = slow->next;
}
mid = slow->next;
slow->next = NULL;
struct list_head *left = __mergesort(head), *right = __mergesort(mid);
return __merge_two_lists(left, right);
}
```
```cpp=
/*
* Merge to sorted linked list
* Inspired by https://hackmd.io/@sysprog/c-linked-list
*/
struct list_head *__merge_two_lists(struct list_head *left,
struct list_head *right)
{
struct list_head *head = NULL, **ptr = &head, **node;
for (node = NULL; left && right; *node = (*node)->next) {
// cppcheck-suppress nullPointer
char *val1 = list_entry(left, element_t, list)->value;
// cppcheck-suppress nullPointer
char *val2 = list_entry(right, element_t, list)->value;
node = (strcmp(val1, val2) < 0) ? &left : &right;
*ptr = *node;
ptr = &(*ptr)->next;
}
*ptr = (struct list_head *) ((uintptr_t) left | (uintptr_t) right);
return head;
}
```
- Performance comparsion with [linux/lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)
## q_shuffle
### [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle)
Pusedo code
```
-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 downto 1 do
j ← random integer such that 0 ≤ j ≤ i
exchange a[j] and a[i]
```
This algorithm create true randomness given to the fact that the probablity of chosen number place to each position are same.
:::info
For example, if we randomly pick one position (let's say 3rd position) in array [0,1,2,3,4] to swap with the last position. The probablity is 1/5. And the array became [0,1,2,4,3]. Then in next round, as we choose from 1 to 3 (n-1), the probablity are still (4/5)*(1/4)=1/5 no matter which position we choose to swap the last element with.
:::
### Add command to qtest
I found this macro ADD_COMMAND added 3 weeks ago and this is align with this article [Preprocessor operators](https://gcc.gnu.org/onlinedocs/cpp/Stringizing.html).
```
#define ADD_COMMAND(cmd, msg) add_cmd(#cmd, do_##cmd, msg)
```
- Stringizing operator (#): 用來將引數變成一個字串
- Charizing operator (#@): 用來將引數變成一個字元
- Token-pasting operator (##): 用來拼接引數
```cpp=
#define MAKESTR(s) #s
#define MAKECHAR(x) #@x
#define CONS(a,b) int(a##e##b)
int main()
{
a = MAKECHAR(b); // a = 'b';
b = MAKESTR(hello) // b = "hello";
c = CONS(2,3); // c = 2e3;
return 0;
}
```
- Add shuffle using ADD_COMMAND
```cpp=
ADD_COMMAND(shuffle,
" | Shuffle list randomly");
```
:::danger
I need to think about a way to declare q_shuffle function since I can't modify queue.h.
:::
### Swap function for any given two node.
#### __q_swap
1. Get l2 previous node (l2_prev) and remove l2 from list.
2. Replace l1 by l2.
3. Check if l1 used to be l2->prev. We can place l1 in next node of l2, so assign l2_prev as l2.
4. Use list_add to add l1 as next node of l2_prev.
```cpp=
/*
* swap any given two list_head. Inspired by linux/list.h
*/
void __q_swap(struct list_head *l1, struct list_head *l2)
{
struct list_head *l2_prev= l2->prev;
list_del(l2);
//replace
l2->next = l1->next;
l2->next->prev = l2;
l2->prev = l1->prev;
l2->prev->next = l2;
if (l2_prev == l1)
l2_prev = l2;
list_add(l1, l2_prev);
}
```
### Create random in range
- Since void srand( unsigned seed ) is called in qtest line 967, we don't need to repeatedly called it.
:::info
Seeds the pseudo-random number generator used by rand() with the value seed. Note: The pseudo-random number generator should only be seeded once, before any calls to rand(), and the start of the program. It should not be repeatedly seeded, or reseeded every time you wish to generate a new batch of pseudo-random numbers.
:::
- Call rand() function. Need to convert it into integer.
```cpp=
int num = (int)(rand()% i);
```
### Use list_head pointer array to store pointer
- Using array to store pointer can greatly reduce time for traversing.
```cpp=
list_for_each(node, head) {
node_array[cnt++] = node;
}
```
### Final solution
1. Create array pointer and store each pionter into it (line 11)
2. Apply Fisher–Yates algorithm and call __q_swap to swap two pointer's position in list.
3. swap chosen pointer in array with pointer in last array position.
```cpp=
void q_shuffle(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
int size = q_size(head);
struct list_head *node_array[size];
struct list_head *node;
int cnt = 0;
list_for_each(node, head) {
node_array[cnt++] = node;
}
struct list_head *tmp;
for (int i = size - 1; i > 0; i--) {
int num = (int)(rand()% i);
__q_swap(node_array[num], node_array[size-1]);
tmp = node_array[size-1];
node_array[size-1] = node_array[num];
node_array[num] = tmp;
}
}
```
## __q_ele_new
- Allocate new node and let pointer to pointer to element_t point to newly allocated address of element_t with char array initilized.
```cpp
/*
* Self-defined function: Allocate new node and let pointer to pointer to element_t point to newly allocated address
* of element_t with char array initilized.
*/
bool __q_ele_new(element_t **pptr_element, char*s) {
*pptr_element = malloc(sizeof(element_t));
if (*pptr_element == NULL) {
free(*pptr_element);
return false;
}
(*pptr_element)->value = malloc(sizeof(char) * (strlen(s) + 1));
if ((*pptr_element)->value == NULL) {
free(*pptr_element);
return false;
}
// Initilize list_head
INIT_LIST_HEAD(&(*pptr_element)->list);
return true;
}
```
- Time complexity:
- Space complexity:
## __q_ele_remove
- Created generic `__q_remove` function called by q_remove_head and q_remove_tail. It would remove the element from list and copy out element char array to specifed buffer (sp) with given length (bufsize).
```cpp
/*
* Self-defined function to generailize q_remove_tail and q_remove_head
*/
element_t *__q_ele_remove(struct list_head *head, char *sp, size_t bufsize)
{
if (head == NULL || list_empty(head))
return NULL;
list_del_init(head);
// cppcheck-suppress nullPointer
element_t *element = list_entry(head, element_t, list);
if (sp != NULL) {
strncpy(sp, element->value, (bufsize - 1));
sp[bufsize - 1] = '\0';
}
return element;
}
```
# Tool
## AddressSanitizer
1. Feature
- 對堆、棧和全域性記憶體的訪問越界(堆緩衝區溢位，棧緩衝區溢位，和全域性緩衝區溢位)
- UAP(Use-after-free，懸掛指標的解引用，或者說野指標)
- Use-after-return(無效的棧上記憶體，執行時標記 ASAN_OPTIONS=detect_stack_use_after_return=1)
- Use-After-Scope (作用域外訪問，clang標記-fsanitize-address-use-after-scope)
- 記憶體的重複釋放 (double-free)
- 初始化順序的BUG
- 記憶體洩漏 (memory leak)
2. How to use:
- Attach below command in CFLAGS
```
-fsanitize=address -fno-omit-frame-pointer -g
```
- Example
```cpp=
#include <iostream>
int main(int argc, char** argv)
{
int a[5];
int index=6;
int retval=a[index];
std::cout << "Ret :" << retval << std::endl;
return retval;
}
```
- result:
```
==2696==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7ffd6eb424c8 at pc 0x56176dbc6fa8 bp 0x7ffd6eb42460 sp 0x7ffd6eb42450
READ of size 4 at 0x7ffd6eb424c8 thread T0
#0 0x56176dbc6fa7 in main /home/shawn/tmp/test.cpp:6
#1 0x7fe1fb98dbf6 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21bf6)
#2 0x56176dbc6e09 in _start (/home/shawn/tmp/test+0xe09)
Address 0x7ffd6eb424c8 is located in stack of thread T0 at offset 56 in frame
#0 0x56176dbc6ed4 in main /home/shawn/tmp/test.cpp:3
This frame has 1 object(s):
[32, 52) 'a' <== Memory access at offset 56 overflows this variable
HINT: this may be a false positive if your program uses some custom stack unwind mechanism or swapcontext
(longjmp and C++ exceptions *are* supported)
SUMMARY: AddressSanitizer: stack-buffer-overflow /home/shawn/tmp/test.cpp:6 in main
Shadow bytes around the buggy address:
0x10002dd60440: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x10002dd60450: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x10002dd60460: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x10002dd60470: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x10002dd60480: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x10002dd60490: 00 00 f1 f1 f1 f1 00 00 04[f2]00 00 00 00 00 00
0x10002dd604a0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x10002dd604b0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x10002dd604c0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x10002dd604d0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x10002dd604e0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
Addressable: 00
Partially addressable: 01 02 03 04 05 06 07
Heap left redzone: fa
Freed heap region: fd
Stack left redzone: f1
Stack mid redzone: f2
Stack right redzone: f3
Stack after return: f5
Stack use after scope: f8
Global redzone: f9
Global init order: f6
Poisoned by user: f7
Container overflow: fc
Array cookie: ac
Intra object redzone: bb
ASan internal: fe
Left alloca redzone: ca
Right alloca redzone: cb
==2696==ABORTING
```
Sign in with Wallet
Connect another wallet