---
# System prepended metadata

title: lab0c

---

# 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