2022q1 Homework1 (lab0)

--- tags: linux2022 --- # 2022q1 Homework1 (lab0) > contributed by <[Linchi1997yeh](https://github.com/Linchi1997yeh)> > [Link to homework1](https://hackmd.io/@sysprog/linux2022-lab0) ### Reviewed by `kevinshieh0225` - To detect whether the list is empty, use `list_empty` in linux kernel api. - If you found bug, you should find it and send patch to the origin repositary. - `q_delete_dup` to many additional condition in the function, it can still be more concise. - The implementation of `q_delete_dup` seems wrong, although you past the `make test`, try to fix the function to meet the expectation. - To swap node in `shuffle`, use `list_move_tail` instead of swapping the char value. ## Environment ```shell $ gcc --version gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0 $ lscpu 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: 1 Core(s) per socket: 8 Socket(s): 1 NUMA node(s): 1 Vendor ID: GenuineIntel CPU family: 6 Model: 158 Model name: Intel(R) Core(TM) i7-9700 CPU @ 3.00GHz Stepping: 13 CPU MHz: 1058.944 CPU max MHz: 4700.0000 CPU min MHz: 800.0000 BogoMIPS: 6000.00 Virtualization: VT-x L1d cache: 256 KiB L1i cache: 256 KiB L2 cache: 2 MiB L3 cache: 12 MiB NUMA node0 CPU(s): 0-7 ``` ## Requirements The task is implement a queue (using linked list) with the following functions: * `q_new`: 建立新的「空」佇列; * `q_free`: 釋放佇列所佔用的記憶體; * `q_insert_head`: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則); * `q_insert_tail`: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則); * `q_remove_head`: 在佇列開頭 (head) 移去 (remove) 給定的節點; * `q_release_element`: Release the memory used by a node in the queue. * `q_size`: Return the number of nodes contained by the queue. * `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/) * `q_delete_dup`: 在已經排序的狀況，移走佇列中具備重複內容的節點，詳見 [LeetCode 82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/) * `q_swap`: 交換佇列中鄰近的節點，詳見 [LeetCode 24. Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/) * `q_reverse`: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點; * `q_sort`: 以==遞增順序==來排序鏈結串列的節點，可參閱 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 得知實作手法; ## Development Journal ### q_new Initialize a empty queue using list_head * Wasn't too sure of the structure of ircular doubly linked list, So I made the mistake of creating a node and used the node as list head ```c= struct list_head *q_new() { struct list_head *head = malloc(sizeof(struct list_head)); // if space cannot be allocated malloc will return NULL　resulting into a // NULL pointer if (head) { INIT_LIST_HEAD(head); } return head; } ``` We can omit the case when memory cannot be allocated, because malloc returns Null if fail to allocate. ### q_free Free all storage used by queue by using macros defined in lish.h Here we need to use list_for_each_safe, to allow deletes. Here we pass in an extra pointer, so it can point to the next node to be iterated before it gets removed. ```c= void q_free(struct list_head *l) { if (!l) { return; } struct list_head *entry, *safe; list_for_each_safe (entry, safe, l) { element_t *node = container_of(entry, element_t, list); q_release_element(node); } free(l); } ``` ### q_insert_head / q_insert_tail Here we should be careful to free element_t node if the string memory space cannot be allocated to prevent memory leak problem. :::warning Here I encounter with a problem when pushing to git: When calling line 18 list_add(&(node->list), head); // This would lead to memory leak problem list_add(&node->list, head); by just memoving the parenthesis the memory leak problem is not detected ::: :::spoiler q_insert_head (code) ```c= bool q_insert_head(struct list_head *head, char *s) { if (!head) { return false; } element_t *node = malloc(sizeof(element_t)); if (!node) { return false; } int strsize = strlen(s); node->value = malloc(strsize + 1); if (!(node->value)) { free(node); return false; } memcpy(node->value, s, strsize); node->value[strsize] = '\0'; list_add(&node->list, head); // list_add(&(node->list), head); why does this results into a memleak??? return true; } ``` ::: :::spoiler q_insert_tail(code) ```c= bool q_insert_tail(struct list_head *head, char *s) { if (!head) { return false; } element_t *node = malloc(sizeof(element_t)); if (!node) { return false; } int strsize = strlen(s); node->value = malloc(strsize + 1); if (!(node->value)) { free(node); return false; } memcpy(node->value, s, strsize); node->value[strsize] = '\0'; list_add_tail(&node->list, head); return true; } ``` ::: ### q_remove_head/q_remove_tail Here the challenge was to return the value of the removed node. First implementation I got the instructions wrong, if the buffsize is smaller than the value string I would not return anything. ::: spoiler q_remove_head ```c= element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { if (!head || head->next == head) { return NULL; } struct list_head *rm = head->next; element_t *node = container_of(rm, element_t, list); list_del(rm); if (node->value != NULL) { if (sp) { memcpy(sp, node->value, bufsize - 1); sp[bufsize - 1] = '\0'; } } return node; } ``` ::: ::: spoiler q_remove_tail ```c= element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize) { if (!head || head->next == head) { return NULL; } struct list_head *rm = head->prev; element_t *node = container_of(rm, element_t, list); list_del(rm); if (node->value != NULL) { if (sp) { memcpy(sp, node->value, bufsize - 1); sp[bufsize - 1] = '\0'; } } return node; } ``` ::: ### q_size Use list_for_each to iterate and count the number of nodes ```c= int q_size(struct list_head *head) { if (!head) { return 0; } int size = 0; struct list_head *node; list_for_each (node, head) { size++; } return size; } ``` ### q_delete_mid Here I implemented the turtle and hare concept. Where there is two pointers hopping one-node and two-node per iteration respectively. When the faster pointer reaches head it means that the slow pointer is in the round down middle. ```c= bool q_delete_mid(struct list_head *head) { // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/ if (!head || head->next == head) { return false; } struct list_head *iter1 = head->next, *iter2 = head->next->next; while (iter2 != head && iter2->next != head) { iter1 = iter1->next; iter2 = iter2->next->next; } element_t *delnode = container_of(iter1, element_t, list); list_del(iter1); q_release_element(delnode); return true; } ``` ### q_delete_dup This can be further improved. The idea is to delete nodes if the values of the previous nodes already appeared once. -> Just found out that I got the function wrong when documenting but the test cases didn't contain this exception. ```c= bool q_delete_dup(struct list_head *head) { // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/ if (!head) { return false; } element_t *entry, *safe; char *laststring = ""; list_for_each_entry_safe (entry, safe, head, list) { // compare if previous values appeared atleast once already if (strcmp(entry->value, laststring) == 0) { list_del(&entry->list); q_release_element(entry); } else { // here the values are seen for the first time if (entry->list.prev != head) { element_t *first = container_of(entry->list.prev, element_t, list); list_del(entry->list.prev); q_release_element(first); } laststring = entry->value; } } entry = list_last_entry(head, element_t, list); if (strcmp(entry->value, laststring) == 0) { list_del(&entry->list); q_release_element(entry); } return true; } ``` :::danger Here is an example of wrong execution, but still got 100 on make test~. ::: ``` cmd> new l = [] cmd> ih k 2 l = [k k] cmd> ih j l = [j k k] cmd> ih c 2 l = [c c j k k] cmd> dedup l = [] cmd> Freeing queue darren@darren-Altos-P30-F6:~/linux2022/lab0-c$ make test scripts/driver.py -c --- Trace Points +++ TESTING trace trace-01-ops: # Test of insert_head and remove_head --- trace-01-ops 5/5 +++ TESTING trace trace-02-ops: # Test of insert_head, insert_tail, remove_head, remove_tail, and delete_mid --- trace-02-ops 6/6 +++ TESTING trace trace-03-ops: # Test of insert_head, insert_tail, reverse, and remove_head --- trace-03-ops 6/6 +++ TESTING trace trace-04-ops: # Test of insert_head, insert_tail, size, swap, and sort --- trace-04-ops 6/6 +++ TESTING trace trace-05-ops: # Test of insert_head, insert_tail, remove_head, reverse, size, swap, and sort --- trace-05-ops 6/6 +++ TESTING trace trace-06-ops: # Test of insert_head, insert_tail, delete duplicate, and sort --- trace-06-ops 6/6 +++ TESTING trace trace-07-string: # Test of truncated strings --- trace-07-string 6/6 +++ TESTING trace trace-08-robust: # Test operations on empty queue --- trace-08-robust 6/6 +++ TESTING trace trace-09-robust: # Test remove_head with NULL argument --- trace-09-robust 6/6 +++ TESTING trace trace-10-robust: # Test operations on NULL queue --- trace-10-robust 6/6 +++ TESTING trace trace-11-malloc: # Test of malloc failure on insert_head --- trace-11-malloc 6/6 +++ TESTING trace trace-12-malloc: # Test of malloc failure on insert_tail --- trace-12-malloc 6/6 +++ TESTING trace trace-13-malloc: # Test of malloc failure on new --- trace-13-malloc 6/6 +++ TESTING trace trace-14-perf: # Test performance of insert_tail, reverse, and sort --- trace-14-perf 6/6 +++ TESTING trace trace-15-perf: # Test performance of sort with random and descending orders # 10000: all correct sorting algorithms are expected pass # 50000: sorting algorithms with O(n^2) time complexity are expected failed # 100000: sorting algorithms with O(nlogn) time complexity are expected pass --- trace-15-perf 6/6 +++ TESTING trace trace-16-perf: # Test performance of insert_tail --- trace-16-perf 6/6 +++ TESTING trace trace-17-complexity: # Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant Probably constant time Probably constant time Probably constant time Probably constant time --- trace-17-complexity 5/5 --- TOTAL 100/100 ``` ### q_swap Didn't open the leetcode link at first instance so implemented the first version swapping the values and not the nodes. ```c= void q_swap(struct list_head *head) { if (!head) { return; } struct list_head *curr, *after; curr = head->next; while (curr != head && curr->next != head) { after = curr->next; curr->next = after->next; curr->next->prev = curr; after->prev = curr->prev; after->prev->next = after; after->next = curr; curr->prev = after; curr = curr->next; } } ``` Here I will try to explain how this code works. We should consider carefully the relationship between the nodes in play. ```graphviz digraph g{ 1 -> 2; 2 -> 1; 2 -> 3; 3 -> 2; 3 -> 4; 4 -> 3; } ``` The logic is to first work with either the links of 1 and 3 or 2 and 4 and last with the links of 2 and 3 (Because we don't want to mess up with the links that are the most obvious to us in the first instance) ### q_reverse Use list_for_each_safe to iterate over the nodes and reversing its link. ( Should use _safe version because during the process we will be modifiying the node's link) After reversing all the node's link we shouldn't forget to reverse the head's link also. ```c= void q_reverse(struct list_head *head) { if (!head || head == head->next) { return; } // reverse the queue excluding head struct list_head *node, *safe, *temp; list_for_each_safe (node, safe, head) { temp = node->next; node->next = node->prev; node->prev = temp; } // reverse head temp = head->next; head->next = head->prev; head->prev = temp; } ``` ### q_sort Recursive version of mergesort. For easier implementation we break the circular linked list, so we can just implement a linked list merge sort. After the list is sorted we have to adjust the prev pointer and reconnect the last node back to the head. ```c= struct list_head *mergeTwoLists(struct list_head *L1, struct list_head *L2) { struct list_head *head = NULL, **ptr = &head, **node; for (node = NULL; L1 && L2; *node = (*node)->next) { element_t *L1_node = container_of(L1, element_t, list); element_t *L2_node = container_of(L2, element_t, list); node = (strcmp(L1_node->value, L2_node->value) <= 0) ? &L1 : &L2; *ptr = *node; ptr = &(*ptr)->next; } *ptr = (struct list_head *) ((uintptr_t) L1 | (uintptr_t) L2); return head; } struct list_head *mergesort_list(struct list_head *head) { if (!head->next) return head; // break the list node in the middle struct list_head *slow = head; for (struct list_head *fast = head->next; fast && fast->next; fast = fast->next->next) slow = slow->next; struct list_head *mid = slow->next; slow->next = NULL; // recursive call struct list_head *left = mergesort_list(head), *right = mergesort_list(mid); // merge list return mergeTwoLists(left, right); } void q_sort(struct list_head *head) { if (!head || list_empty(head)) return; // break the circular link list into a regular link list head->prev->next = NULL; //sort head->next = mergesort_list(head->next); // Adjust the previous pointer to the correct node struct list_head *ptr = head; for (; ptr->next; ptr = ptr->next) ptr->next->prev = ptr; ptr->next = head; head->prev = ptr; } ``` ### shuffle Implement Fisher-Yates Shuffle ```c= void q_shuffle(struct list_head *head) { if (!head || list_empty(head)) { return; } int q_length = q_size(head); if (q_length == 1) { return; } struct list_head *node, *target_node; for (node = head->next; node->next != head; node = node->next) { int target = 0; while (target == 0) { target = rand() % q_length; } target_node = node; for (int i = 0; i < target; i++) { target_node = target_node->next; } element_t *node_el = container_of(node, element_t, list); element_t *target_node_el = container_of(target_node, element_t, list); // swap values char *temp = node_el->value; node_el->value = target_node_el->value; target_node_el->value = temp; q_length--; } } ``` ```c= static bool do_shuffle(int argc, char *argv[]) { if (argc != 1) { report(1, "%s takes no arguments", argv[0]); return false; } if (!l_meta.l) report(3, "Warning: Calling shuffle on 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(); } ``` ### References: Lecture notes: > [你所不知道的C語言：指標篇](https://hackmd.io/@sysprog/c-pointer) > [你所不知道的C語言：linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list) Classmate's work : > [kevinshieh0225](https://hackmd.io/@Masamaloka/2022q1-hw1) > [happyjack91630](https://hackmd.io/@Z80E9t1oQmejDKgmGy_dBQ/BkTGEADgq) > [jimmy-liu1021](https://hackmd.io/WuvH2ILMSaat53sYeXmivA?both)

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.