# 2024q1 Homework1 (lab0)
[github](https://github.com/backink/lab0-c)
## 實作 queue.c 中未完成的函式
本次作業第一個目標是通過 `make test` 中所有測試資料，觀察 Makefile 內容可以發現測試是由 `script/driver.py` 執行，而 `script/driver.py` 的工作是將 `trace/` 內的檔案當作輸入資料傳入主程式 `qtest`中。
實作`queue.c`過程中需要盡可能使用 Linux 鏈結串列 API (即 `list.h`中所提供之 API)完成函式指定之操作。
### q_new()
```c
/* Create an empty queue */
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
if (!head)
return NULL;
INIT_LIST_HEAD(head);
return head;
}
```
### q_free()
```c
/* Free all storage used by queue */
void q_free(struct list_head *head)
{
if (!head)
return;
element_t *entry, *safe;
list_for_each_entry_safe (entry, safe, head, list) {
q_release_element(entry);
}
free(head);
}
```
### q_insert_head()
```c
/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
if (!head || !s)
return false;
element_t *ele = malloc(sizeof(element_t));
if (!ele)
return false;
ele->value = strdup(s);
if (!ele->value) {
free(ele);
return false;
}
list_add(&ele->list, head);
return true;
}
```
### q_insert_tail()
```c
/* Insert an element at tail of queue */
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head || !s)
return false;
element_t *ele = malloc(sizeof(element_t));
if (!ele)
return false;
ele->value = strdup(s);
if (!ele->value) {
free(ele);
return false;
}
list_add_tail(&ele->list, head);
return true;
}
```
### q_remove_head()
```c
/* Remove an element from head of queue */
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *ele = list_first_entry(head, element_t, list);
if (sp && ele->value) {
strncpy(sp, ele->value, bufsize);
sp[bufsize - 1] = '\0';
}
list_del(head->next);
return ele;
}
```
### q_remove_tail()
```c
/* Remove an element from tail of queue */
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *ele = list_last_entry(head, element_t, list);
if (sp && ele->value) {
strncpy(sp, ele->value, bufsize);
sp[bufsize - 1] = '\0';
}
list_del(head->prev);
return ele;
}
```
### q_size()
```c
/* Return number of elements in queue */
int q_size(struct list_head *head)
{
if (!head || list_empty(head))
return 0;
int ret = 0;
struct list_head *node;
list_for_each (node, head) {
ret++;
}
return ret;
}
```
### q_delete_mid()
```c
/* Delete the middle node in queue */
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 *first = head->next, *last = head->prev;
while ((first != last) && (first->next != last)) {
last = last->prev;
first = first->next;
}
element_t *ele = list_entry(first, element_t, list);
list_del(first);
q_release_element(ele);
return true;
}
```
在寫 leetcode 時因為題目限制都是單向鏈結串列，通常會用快慢指標來找到中間節點。
這裡的實作是雙向鏈結串列，因此使用兩個指標分別從頭尾往中間移動，一旦交會就可以得知中間節點的位置。
### q_delete_dup()
```c
/* Delete all nodes that have duplicate string */
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;
element_t *entry, *safe;
bool dup = false;
list_for_each_entry_safe (entry, safe, head, list) {
if (&safe->list != head && !strcmp(entry->value, safe->value)) {
dup = true;
list_del(&entry->list);
q_release_element(entry);
} else if (dup) {
dup = false;
list_del(&entry->list);
q_release_element(entry);
}
}
return true;
}
```
### q_swap()
```c
/* 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))
return;
struct list_head *node = head->next;
for (; node->next != head && node != head; node = node->next) {
list_move(node, node->next);
}
}
```
### q_reverse()
```c
/* Reverse elements in queue */
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *last = head->next;
struct list_head *node = head;
for (; head->prev != last; node = node->next) {
list_move(head->prev, node);
}
}
```
### q_reverseK()
```c
/* Reverse the nodes of the list k at a time */
void q_reverseK(struct list_head *head, int k)
{
// https://leetcode.com/problems/reverse-nodes-in-k-group/
if (!head || list_empty(head) || list_is_singular(head) || k <= 1)
return;
struct list_head *start = head->next;
struct list_head *node;
while (start != head) {
int n = k - 1;
for (node = start; n > 0 && node->next != head; node = node->next) {
n--;
}
if (n == 0) {
reverse_between(start, node);
start = start->next;
} else {
break;
}
}
}
void reverse_between(struct list_head *start, struct list_head *node)
{
struct list_head *head = start->prev;
struct list_head *tmp;
while (node != start) {
tmp = node->prev;
list_move(node, head);
head = head->next;
node = tmp;
}
}
```
新增一個函式`reverse_between` 給定兩個節點，將包含兩個節點之間的所有節點反向，以滿足`reverseK` 中反向K個節點的需求。
### q_sort()
```c
/* Sort elements of queue in ascending/descending order */
void q_sort(struct list_head *head, bool descend)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *first = head->next, *last = head->prev;
while (first != last) {
last = last->prev;
if (first == last)
break;
first = first->next;
}
LIST_HEAD(head_to);
list_cut_position(&head_to, head, first);
q_sort(head, descend);
q_sort(&head_to, descend);
merge(head, &head_to, descend);
}
void merge(struct list_head *head_main, struct list_head *head, bool descend)
{
struct list_head *node_main = head_main->next, *node = head->next;
struct list_head *tmp;
int flag = descend ? 1 : -1;
while (node_main != head_main && node != head) {
element_t *entry_main = list_entry(node_main, element_t, list);
element_t *entry = list_entry(node, element_t, list);
while (node_main != head_main &&
(flag * strcmp(entry_main->value, entry->value) > 0)) {
node_main = node_main->next;
entry_main = list_entry(node_main, element_t, list);
}
tmp = node->next;
list_move(node, node_main->prev);
node = tmp;
}
if (node != head)
list_splice_tail(head, head_main);
}
```
實作遞迴版本的 Merge Sort。
:::info
TODO
1. 比較不同排序方法的執行效能
:::
### q_ascend()
```c
/* Remove every node which has a node with a strictly less value anywhere to
* the right side of it */
int q_ascend(struct list_head *head)
{
// https://leetcode.com/problems/remove-nodes-from-linked-list/
if (!head || list_empty(head))
return 0;
struct list_head *min = head->prev;
int ret = 1;
while (min->prev != head) {
element_t *ele_min = list_entry(min, element_t, list);
element_t *ele_pre = list_entry(min->prev, element_t, list);
if (strcmp(ele_min->value, ele_pre->value) < 0) {
list_del(min->prev);
q_release_element(ele_pre);
} else {
min = min->prev;
ret++;
}
}
return ret;
}
```
函式說明使用`Remove`而非`Delete` ，所以我一開始沒有將移除節點的記憶體釋放，即使使用 Valgrind 也沒有找到錯誤位置，最後觀摩同學實作才發現需要釋放目標節點的記憶體。
```
Valgrind結果
```
:::success
送出PR，新增函式說明 [Link](https://github.com/sysprog21/lab0-c/pull/170)
TODO
1. 使用 sha1sum 更新 queue.h 的 checksum值
2. 追蹤 git hook 的流程，了解 git hook 如何運作及實作
:::
### q_descend()
```c
/* Remove every node which has a node with a strictly greater value anywhere to
* the right side of it */
int q_descend(struct list_head *head)
{
// https://leetcode.com/problems/remove-nodes-from-linked-list/
if (!head || list_empty(head))
return 0;
struct list_head *max = head->prev;
int ret = 1;
while (max->prev != head) {
element_t *ele_max = list_entry(max, element_t, list);
element_t *ele_pre = list_entry(max->prev, element_t, list);
if (strcmp(ele_max->value, ele_pre->value) > 0) {
list_del(max->prev);
q_release_element(ele_pre);
} else {
max = max->prev;
ret++;
}
}
return ret;
}
```
### q_merge()
```c
/* Merge all the queues into one sorted queue, which is in ascending/descending
* order */
int q_merge(struct list_head *head, bool descend)
{
// https://leetcode.com/problems/merge-k-sorted-lists/
if (!head || list_empty(head))
return 0;
struct list_head *first = head->next, *last = head->prev;
int ret = 0;
bool count_size = true;
while (last != head->next) {
while (first != last && first->prev != last) {
queue_contex_t *q_first = list_entry(first, queue_contex_t, chain);
queue_contex_t *q_last = list_entry(last, queue_contex_t, chain);
if (count_size) {
ret += q_first->size + q_last->size;
}
merge(q_first->q, q_last->q, descend);
first = first->next;
last = last->prev;
}
if (count_size && first == last) {
queue_contex_t *q = list_entry(first, queue_contex_t, chain);
ret += q->size;
}
count_size = false;
first = head->next;
}
return ret;
}
```
:::success
閱讀說明中有發現錯字，發送PR修正 [Link](https://github.com/sysprog21/lab0-c/pull/171)
:::
## 整合網頁伺服器
流程
select、fdf_set的說明及使用
## 論文〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉
本次作業有導入部分論文內容實作的程式碼 [dudect](https://github.com/oreparaz/dudect)，用意是檢測函式實作是否屬於常數時間。
簡介、摘要：
雖然知道作業內原始程式碼和dudect的差異是後者有使用percetile對資料做篩選，藉由將離群值移除得到較佳的統計結果，但是我還沒有完全理解 percentile 實作的原理。
:::success
閱讀 dudect 程式碼的時候發現問題，原本的程式碼將64位元轉換成32位元數值，有可能造成非預期結果
發送 PR 修正 [Link](https://github.com/oreparaz/dudect/commit/dc269651fb2567e46755cfb2a13d3875592968b5)
```diff
- static int cmp(const int64_t *a, const int64_t *b) { return (int)(*a - *b); }
+ static int cmp(const int64_t *a, const int64_t *b) {
+ if (*a == *b)
+ return 0;
+ return (*a > *b) ? 1 : -1;
+}
```
:::
percentile 的計算方式？
## 研讀 Linux 核心原始程式碼的 lib/list_sort.c
Sign in with Wallet
Connect another wallet