# 2024q1 Homework1 (lab0)
contributed by < [`Ken-LuWeiRu`](https://github.com/Ken-LuWeiRu) >
<s># linux2024-homework1</s>

:::danger
標題格式固定為 2024q1 Homework1 (lab0)，其中 "lab0" 是小寫，2024q1 表示「2024 年第 1 季」。
共筆內容的第二行則為 `contributed by < 你的GitHub帳號名稱 >`

留意各式細節，唯有重視小處並步步為營，方可挑戰原始程式碼規模超越三千七百萬行的 Linux 核心
:::

## 開發環境

$ gcc -v
gcc version 11.4.0 (Ubuntu 11.4.0-1ubuntu1~22.04) 

$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         46 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  24
  On-line CPU(s) list:   0-23
Vendor ID:               GenuineIntel
  Model name:            13th Gen Intel(R) Core(TM) i7-13700K
    CPU family:          6
    Model:               183
    Thread(s) per core:  2
    Core(s) per socket:  16
    Socket(s):           1
    Stepping:            1
    CPU max MHz:         5400.0000
    CPU min MHz:         800.0000
    BogoMIPS:            6835.20

## 專案底下個檔案用途

:::danger
詳閱[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::

這禮拜才開始學 C 與指標 <s>指針</s>，原本是直接以queue.c來實作，後續才意識到queue.h與list.h早已實作好許多功能，以下是簡單敘述

* `Makefile` : 包含編譯和構建項目的指令。
* `console.c 和 console.h` : 實現qtest的命令行解釋器。
* `harness.c 和 harness.h` : 提供嚴格測試框架的自定義malloc/free/strdup實現。
* `linenoise.c 和 linenoise.h` : 為qtest提供命令行的函數庫。
* `list.h` : 列表頭文件。
* `log2_lshift16.h` : 提供顯示/隱藏Shannon熵的選項。
* `qtest.c` : 測試queue.c，可以生成測試queue
* `queue.c 和 queue.h` : 實現隊列的代碼和聲明。
* `random.c 和 random.h` : 生成隨機數的實現和聲明。
* `report.c 和 report.h` : 實現在不同詳細等級打印信息的功能。
* `shannon_entropy.c` : 提供顯示/隱藏Shannon熵的功能。
* `web.c 和 web.h` : 為qtest集成一個小型的Web服務器。

:::danger
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
:::

## 實作指定佇列操作

### q_new

:::danger
改進你的漢語表達，什麼是「建立list的頭」？
:::

由於list.h已經提供INIT_LIST_HEAD()來建立list的頭，不該重複撰寫類似的程式碼，因此直接使用。
在測試記憶體空間時，若不足需要返回NULL。

struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(struct list_head));
+    if (!head)
+        return NULL;
-    head->next = head;
-    head->prev = head;
+    INIT_LIST_HEAD(head);
    return head;
}

### q_free

free首先也需要注意確認是否head是否存在，並且在list.h有提供list_for_each_safe()可以遍歷所有節點，list_first_entry()可以得到第一個元素，改使用後還可以通過效能測驗。

void q_free(struct list_head *head)
{
    if (!head)
        return;
    struct list_head *current, *temp;
+    list_for_each_safe(current, temp, head) {
+        element_t *entry = list_entry(current, element_t, list);
+        list_del(current);
+        free(entry->value);
+        free(entry);
+    }
-    struct list_head *current = head->next;
-    while (current != head) {
-        struct list_head *temp = current;
-        current = current->next;
-        element_t *entry = (element_t *)((char *)temp - offsetof(element_t, list));
-        list_del(temp);
-        free(entry->value);
-        free(entry);
-    }
    free(head);
}

之前也沒注意到有q_release_element()。

-        free(entry->value);
-        free(entry);
+        q_release_element(entry);

### q_insert_head // q_insert_tail
檢查節點是否存在會使得一定無法通過效能測驗，所以先刪除。

bool q_insert_head(struct list_head *head, char *s)
{
-    if (!head || !s) { // Check if either head or s is NULL.
-        return false;
-    }

    element_t *new_element = malloc(sizeof(element_t));
    if (!new_element) {
        return false;  // Memory allocation failed for new_element.
    }

    new_element->value = strdup(s);  // Duplicate the string.
    if (!new_element->value) {
+        free(new_element);  // Free the allocated memory for new_element since
-        q_release_element
                            // strdup failed.
        return false;
    }

    list_add(&new_element->list,
             head);  // Insert the new element at the head of the list.
    return true;
}

q_insert_tail 也移除檢測

bool q_insert_tail(struct list_head *head, char *s)
{
-    if (!head || !s) { // Check if either head or s is NULL.
-        return false;
-    }

### q_delete_mid
此題[2095. Delete the Middle Node of a Linked List](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/description/)我採用[快慢指針](https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.md)的方式

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return false;

    struct list_head *slow = head->next, *fast = head->next;
    struct list_head *prev = NULL;

    while (fast != head && fast->next != head) {
        prev = slow;
        slow = slow->next;
        fast = fast->next->next;
    }

    if (prev != NULL) {
        element_t *middle_element = list_entry(slow, element_t, list);
        list_del(slow);
        free(middle_element->value);
        free(middle_element);
        return true;
    }
    return false;
}

### q_delete_dup
[82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/description/)

bool q_delete_dup(struct list_head *head)
{
    if (!head || list_empty(head)) {
        return false;  // Return false if the list is empty or head is NULL.
    }

    struct list_head *current = head->next, *next_node;
    bool global_deleted = false;
    bool duplicate_flag = false;

    while (current != head && current->next != head) {
        element_t *current_element = list_entry(current, element_t, list);
        next_node = current->next;  // Move to the next node early because
                                    // current might get deleted.
        element_t *next_element = list_entry(next_node, element_t, list);

        // Check if current and next nodes have the same value.
        if (strcmp(current_element->value, next_element->value) == 0) {
            duplicate_flag = true;
            global_deleted = true;
        }

        // Move ahead to find the end of duplicates if there are any.
        while (duplicate_flag && next_node != head &&
               strcmp(current_element->value, next_element->value) == 0) {
            struct list_head *temp = next_node->next;
            list_del(next_node);
            free(next_element->value);
            free(next_element);
            next_node = temp;  // Proceed to next node.
            next_element = next_node != head
                               ? list_entry(next_node, element_t, list)
                               : NULL;
        }

        // If duplicates were found, delete the current node as well.
        if (duplicate_flag) {
            list_del(current);
            free(current_element->value);
            free(current_element);
            duplicate_flag = false;  // Reset the flag for the next iteration.
        }

        current =
            next_node;  // Proceed to next node for the next loop iteration.
    }

    return global_deleted;  // Return true if any element was deleted.
}

:::danger
針對環狀且雙向鏈結串列的特性，搭配 List API，撰寫出更精簡有效的程式碼。
:::

### q_swap

### q_reverse

### q_reverseK

### q_sort
一開始採用插入排序法(Insertion sort)，因為平均時間複雜度是$O(n^2)$，無法通過效能測驗。改用快速排序法(Quick Sort)，平均複雜度是$O(n\log n)$但是沒注意到會測試最糟糕案例，因其最壞時間複雜度是$O(n^2)$無法通過。最後還是只能用最壞時間複雜度是$O(n\log{n})$的合併排序法 (Merge sort)處理。

:::danger
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。
:::

在測驗時出現我的queue不是doubly linked list，後續才發現我的```*sortedMerge```沒有正確的連接好

:::danger
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
:::

### q_descend

### q_merge

## 研讀論文〈Dude, is my code constant time?〉
目前程式碼會有時95有時100，主因看來是這部份。目前是 q_insert_tail 與 q_insert_head 會出現 Probably not constant time or wrong implementation

:::danger
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
:::

## Valgrind + 自動測試程式

## 整合網頁伺服器

:::danger
段落中的程式碼標注，使用 1 個 [backtick](https://en.wikipedia.org/wiki/Backtick)，而非 3 個。
:::

## 實作```shuffle```命令

## M03: ttt

###