HackMD
2022q1 Homework1 (lab0)
contributed by < 25077667 >
實驗環境
➜ ~ neofetch; gcc -v
-` scc@scc-lab
.o+` -----------
`ooo/ OS: Arch Linux x86_64
`+oooo: Host: WS E500 G5_WS690T Rev 1.xx
`+oooooo: Kernel: 5.16.10-arch1-1
-+oooooo+: Uptime: 25 mins
`/:-:++oooo+: Packages: 1123 (pacman)
`/++++/+++++++: Shell: zsh 5.8.1
`/++++++++++++++: Resolution: 1920x1080
`/+++ooooooooooooo/` Terminal: /dev/pts/0
./ooosssso++osssssso+` CPU: Intel i7-8700 (12) @ 4.600GHz
.oossssso-````/ossssss+` GPU: Intel CoffeeLake-S GT2 [UHD Graphics 630]
-osssssso. :ssssssso. Memory: 639MiB / 31902MiB
:osssssss/ osssso+++.
/ossssssss/ +ssssooo/-
`/ossssso+/:- -:/+osssso+-
`+sso+:-` `.-/+oso:
`++:. `-/+/
.` `/
Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-pc-linux-gnu/11.2.0/lto-wrapper
Target: x86_64-pc-linux-gnu
Chread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 11.2.0 (GCC)
- 過去 2020 年之開發紀錄
開發過程
使用 Linux API list.h，第一手資料於 The Linux Kernel API
q_new
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
if (head)
INIT_LIST_HEAD(head);
return head;
}
q_free
使用 Linux API list_for_each_safe，並且重用相同函式 q_release_element
void q_free(struct list_head *l)
{
if (!l)
return;
if (list_empty(l)) {
free(l);
return;
}
struct list_head *cur = NULL, *safe = NULL;
list_for_each_safe (cur, safe, l)
q_release_element(container_of(cur, element_t, list));
free(l);
}
q_insert_head
由於 insert node 都是相同的程式碼，
因此定義 static 函式 create_node 及 q_insert:
static inline element_t *create_node(const char *s)
{
element_t *const new_node = (element_t *const) malloc(sizeof(element_t));
if (!new_node)
return NULL;
const size_t len = strlen(s);
new_node->value = malloc(len + 1);
if (!new_node->value) {
free(new_node);
return NULL;
}
strncpy(new_node->value, s, len);
new_node->value[len] = 0;
/*
* NOTE: I think that use strndup is better, but the test_malloc hook
* would make you failed in test_free here.
*
* new_node->value = strndup(s, len);
*/
return new_node;
}
但是這邊原先設計上，遇到一個問題： strndup 不會經過 Jserv 老師所 hook 的 test_malloc 所以在後續 q_free 做釋放時會出現對不上 block_ele_t 的不預期錯誤。
改良方法，修改 harness.c 新增 strndup 函式，以支援 strndup 標準函式庫之簡潔粗曠操作。
q_insert 函式使用 function pointer 方法，將函數抽象化為一操作方法之物件 (an object of operating method)
static inline bool q_insert(struct list_head *head,
char *s,
void (*op)(struct list_head *, struct list_head *))
{
if (!head)
return false;
element_t *new_node = create_node(s);
if (!new_node)
return false;
op(&new_node->list, head);
return true;
}
因此，前後這兩個 insert 操作，即可不論頭尾，變成一行。
bool q_insert_head(struct list_head *head, char *s)
{
return q_insert(head, s, list_add);
}
q_insert_tail
bool q_insert_tail(struct list_head *head, char *s)
{
return q_insert(head, s, list_add_tail);
}
q_remove_head
同上，建立 q_remove 函式，將 remove node 操作合併。
static inline element_t *q_remove(struct list_head *head,
char *sp,
size_t bufsize,
struct list_head *rm_node)
{
element_t *ele = list_entry(rm_node, element_t, list);
if (sp && ele->value) {
strncpy(sp, ele->value, bufsize);
sp[bufsize - 1] = 0;
}
list_del(rm_node);
return ele;
}
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
return q_remove(head, sp, bufsize, head->next);
}
q_remove_tail
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
return q_remove(head, sp, bufsize, head->prev);
}
q_size
遍歷所有節點（我記得我上次寫這作業時是 2020 年，這題要 element_t 結構體，新增紀錄元素數量之變數）
int q_size(struct list_head *head)
{
if (!head || list_empty(head))
return 0;
size_t size = 0;
struct list_head *p = NULL;
list_for_each (p, head)
++size;
return size;
}
q_delete_mid
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 *fast = head->next, *slow = head->next;
while (fast != head && fast->next != head)
slow = slow->next, fast = fast->next->next;
list_del(slow);
q_release_element(list_entry(slow, element_t, list));
return true;
}
採用之前(2020)寫作經驗， fast/slow 模式，找出中點。
q_delete_dup
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;
struct list_head *node = NULL, *safe = NULL;
bool last_dup = false;
list_for_each_safe (node, safe, head) {
element_t *cur = list_entry(node, element_t, list);
const bool match =
node->next != head &&
!strcmp(cur->value, list_entry(node->next, element_t, list)->value);
if (match || last_dup) {
list_del(node);
q_release_element(cur);
}
last_dup = match;
}
return true;
}
q_swap
採用兩兩成一對的子問題，將整個 circular linked-list 分割分治。
而後觀摩 tinyynoob 的實做，驚為天人。
q_reverse
list 反轉是常見考題，聽過很多次，但是沒寫過。
第一次直覺想法是，遍歷並交換 prev, next 指標。不料測試發現在「頭尾相接」的 circular linked-list 上會造成無窮迴圈。
所以改變思路，走訪時將期節點放到「頭」。
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *cur = NULL, *safe = NULL;
list_for_each_safe (cur, safe, head)
list_move(cur, head); // put to beginning
}
