Try   HackMD

2025q1_Homework1(lab0)

contributed by dingsen-Greenhorn

作業書寫規範:

  • 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
  • 文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
  • 共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
  • 不要在筆記內加入 [TOC] : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
  • 不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，用於評分和接受同儕的檢閱
  • 當在筆記中貼入程式碼時，避免非必要的行號，也就是該手動將 c= 或 cpp= 變更為 c 或 cpp。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「你所不知道的 C 語言: linked list 和非連續記憶體」裡頭程式碼展現的方式
  • HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」
  • 留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」及「詞彙對照表」
  • 不要濫用 :::info, :::success, :::warning 等標示，儘量用清晰的文字書寫。:::danger 則僅限授課教師作為批注使用
  • 避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景
  • 在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","。注意書名號的使用，即 〈 和 〉，非「小於」和「大於」符號
  • 避免使用不必要的 emoji 字元

開發環境

dingsen@dingsen:~/linux/lab0-c$ ./qtest
cmd> help
Commands:
  #           ...          | Display comment
  ascend                   | Remove every node which has a node with a strictly less value anywhere to the right side of it
  dedup                    | Delete all nodes that have duplicate string
  descend                  | Remove every node which has a node with a strictly greater value anywhere to the right side of it
  dm                       | Delete middle node in queue
  free                     | Delete queue
  help                     | Show summary
  ih          str [n]      | Insert string str at head of queue n times. Generate random string(s) if str equals RAND. (default: n == 1)
  it          str [n]      | Insert string str at tail of queue n times. Generate random string(s) if str equals RAND. (default: n == 1)
  log         file         | Copy output to file
  merge                    | Merge all the queues into one sorted queue
  new                      | Create new queue
  next                     | Switch to next queue
  option      [name val]   | Display or set options. See 'Options' section for details
  prev                     | Switch to previous queue
  quit                     | Exit program
  reverse                  | Reverse queue
  reverseK    [K]          | Reverse the nodes of the queue 'K' at a time
  rh          [str]        | Remove from head of queue. Optionally compare to expected value str
  rt          [str]        | Remove from tail of queue. Optionally compare to expected value str
  show                     | Show queue contents
  size        [n]          | Compute queue size n times (default: n == 1)
  sort                     | Sort queue in ascending/descening order
  source                   | Read commands from source file
  swap                     | Swap every two adjacent nodes in queue
  time        cmd arg ...  | Time command execution
  web         [port]       | Read commands from builtin web server
Options:
  descend     0            | Sort and merge queue in ascending/descending order
  echo        1            | Do/don't echo commands
  entropy     0            | Show/Hide Shannon entropy
  error       5            | Number of errors until exit
  fail        30           | Number of times allow queue operations to return false
  length      1024         | Maximum length of displayed string
  malloc      0            | Malloc failure probability percent
  simulation  0            | Start/Stop simulation mode
  verbose     4            | Verbosity level
cmd>

Quene 操作功能實現

q_new

struct list_head *new_queue =
(struct list_head *) malloc(sizeof(struct list_head));

q_new 是其他功能的基礎功能，用動態分配記憶體 malloc分配空間給queue.

sizeof(struct list_head) 計算 struct list_head 結構的大小，確保分配足夠的記憶體空間來存儲這個結構。並且由於malloc 返回的是 void *，所以需要類型轉換成 struct list_head * 以符合變數 new_queue 的類型。

其中我一開始的寫法如下

        struct list_head *new_queue =
        malloc(sizeof(struct list_head));

後續再將自己的程式與同學討論發現，在 C 語言中，void * 因為可以自動轉換為任何指標類型，因此理論上

struct list_head *new_queue = malloc(sizeof(struct list_head));

也是可行的。
但是在 C++ 中，void * 不能隱式轉換為其他指標類型，所以如果這段程式碼將來可能會用 C++ 編譯，就需要顯式轉型 (struct list_head *) 來避免編譯錯誤。
因此，加入後可以同時兼容兩種語言，於是改進成以上方案。

q_free

q_free 的目標是釋放不需要的queue。由於刪除queue的過程中，需要正確釋放並確保不會有記憶體洩漏 (memory leak)。
假設如果若先釋放 element_t，則 value 仍然指向已釋放的記憶體 (dangling pointer)，對該指標進行 free() 可能會導致未定義行為 (undefined behavior)。

因此釋放順序應當是 先內部資料、再外部結構、最後頭部。

        list_for_each_safe (node, safe_front, head) {
        list_del(node);
        free(list_entry(node, element_t, list)->value);
        free(list_entry(node, element_t, list));
    }
    free(head);
}

q_insert_head & tail

基本上兩個設計幾乎一樣因此以q_insert_head為例：

分配 element_t 結構記憶體

    element_t *new_content = (struct list_head *)malloc(sizeof(element_t));

如同前面所說明的一樣malloc(sizeof(element_t))會分配一塊記憶體空間，大小為 element_t 結構的大小，並回傳一個指向這塊記憶體的指標。
element_t 的結構通常如下：

    typedef struct {
    struct list_head list;  
    char *value;            
} element_t;

INIT_LIST_HEAD()

INIT_LIST_HEAD() 來自 Linux Kernel 的 list.h，它的定義如下

static inline void INIT_LIST_HEAD(struct list_head *list)
{
    list->next = list;
    list->prev = list;
}

它的作用是初始化新節點，讓 new_content->list 的 prev 和 next 都指向自己，避免指標未初始化的問題。

分配字串記憶體

    new_content->value = strdup(s);

strdup(s) 會使用 malloc(strlen(s) + 1) 分配一塊新的字串記憶體。將 s 的內容複製到新記憶體中。回傳新字串的指標，讓 new_content->value 指向它。
這樣的設計可以確保：
new_content->value 擁有自己的獨立記憶體，不會與 s 共用。s 可能來自不同的作用域（例如函式參數），如果不複製就直接儲存 s 的指標，可能會導致記憶體存取錯誤。

插入鏈結串列


list_add(&new_content->list, head);

static inline void __list_add(struct list_head *new,
                              struct list_head *prev,
                              struct list_head *next)
{
    next->prev = new;
    new->next = next;
    new->prev = prev;
    prev->next = new;
}

list_add(&new_content->list, head);

讓 new_content 成為 head 之後的第一個節點。

相同的q_insert_tail,只差list_add_tail
在 Linux Kernel 的 list.h，list_add_tail 定義如下：

static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
    __list_add(new, head->prev, head);
}

與 list_add 相比，它呼叫 __list_add 時，參數改變：

    prev = head->prev（即原本的最後一個節點）
    next = head（因為 head 是循環鏈結串列的錨點）

q_remove_head & tail

q_remove_head and q_remove_tail基本上很類似，以q_remove_head為例：

取得鏈結串列的第一個節點

element_t *first = list_first_entry(head, element_t, list);

list_first_entry() 是 Linux Kernel 提供的 macro，定義如下：

     #define list_first_entry(ptr, type, member) \
        list_entry((ptr)->next, type, member)

(ptr)->next → 取 head->next，即第一個節點。
list_entry(head->next, element_t, list) 會將 head->next 轉換為 element_t * 型態的指標
根據 list 成員的偏移量，找到 element_t 結構的起始位址

從鏈結串列中移除該節點

list_del(&first->list);

list_del() 定義如下：

static inline void list_del(struct list_head *entry)
{
    __list_del(entry->prev, entry->next);
    entry->next = NULL;
    entry->prev = NULL;
}

運作方式：

修改前後節點的指標

entry->prev->next = entry->next;
entry->next->prev = entry->prev;

這樣，first 節點從鏈結串列中移除，但仍然佔有記憶體。
避免野指標（Dangling Pointer）

        entry->next = NULL;
        entry->prev = NULL;

這樣 first->list 的指標會變成 NULL，避免程式誤用它。

選擇性地複製字串

if (sp && bufsize > 0) {
    strncpy(sp, first->value, bufsize - 1);
    sp[bufsize - 1] = '\0';
}

為何要檢查 sp？
sp 是一個指標，若 sp == NULL，則表示不需要複製字串，直接跳過這段程式碼。

為何要檢查 bufsize > 0？
bufsize 是 sp 可用的記憶體大小，若 bufsize == 0，則不應該嘗試寫入，否則可能導致錯誤。

如何安全地複製字串？

strncpy(sp, first->value, bufsize - 1);
bufsize - 1 確保最多只複製 bufsize - 1 個字元，避免溢位（Buffer Overflow）。
sp[bufsize - 1] = '\0';
確保字串結尾是 \0，即使 first->value 的長度超過 bufsize - 1。

回傳移除的節點

return first;

為何不直接釋放 first？
q_remove_head() 只負責從鏈結串列中移除節點，但並不釋放它的記憶體。
這樣設計的好處是由呼叫者決定何時釋放記憶體，提高靈活性

Q_size

不知道大家對於head有沒有疑問？就是為什麼需要一個額外的東西來描述鍊結串列的referance point?
抱持這個疑問，我再網路上找到一個不錯的說例：

在 Linux list.h 的設計中，head 並不是一個真正的節點，而是作為鏈結串列的錨點（Sentinel Node），這樣能避免 NULL 指標錯誤，並且允許空的鏈結串列存在：

head → [A] → [B] → [C] → head

當鏈結串列為空時：

head → head
head->next == head，因此 list_for_each 直接結束，不會執行 len = len + 1;，這樣 len 保持 0。

q_delete_mid

這裡有很多不同的作法，我使用傳統的快慢指標來實作。

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

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

找出中間節點刪除

element_t *mid = list_entry(slow, element_t, list);
list_del(slow);
free(mid->value);
free(mid);
return true;

為什麼要從內層刪除到外面呢？為什麼刪除NODE需要宣告ELEMENT_T不能直接刪除SLOW並釋放SLOW記憶體就好？

這裡不能直接釋放 slow，而是需要透過 list_entry(slow, element_t, list) 來取得 element_t，再進行釋放。原因如下：

1. slow 是 list_head，而不是 element_t 本體

在 Linux kernel 的 list_head 佈局中，每個節點的 list_head 僅僅是鏈結串列指標部分，它嵌套在包含真實資料的結構體（如 element_t）內
舉個例子，假設 element_t 定義如下：

typedef struct {
    struct list_head list; // 用於鏈結串列的 list_head
    char *value;           // 真正存放的數據
} element_t;

記憶體佈局
假設 element_t 佔據的記憶體如下（簡化表示）：

地址偏移	內容
0x1000	list_head
0x1008	value 指標

slow 變數是 指向 list_head 的指標，即 slow == &element->list。
但 list_head 只是結構體的一部分，並不代表整個 element_t。

2. 直接釋放 slow 會導致「部分釋放」

如果你這樣做：

list_del(slow);
free(slow); // ❌ 這是錯的！
slow 只是 list_head 指標，而不是 element_t 的起始地址。
free(slow) 只會釋放 list_head（約 16 bytes），但 element_t 的其他部分仍未釋放，導致記憶體洩漏（memory leak）。

3. 正確的釋放方式

為了完整釋放 element_t，我們需要透過 list_entry() 取得 element_t 本體：

element_t *mid = list_entry(slow, element_t, list);
list_del(slow);
free(mid->value); // 釋放 value（假設是動態分配的記憶體）
free(mid); // 釋放 element_t 本身

這樣確保
正確刪除鏈結串列節點 list_del(slow)。
完整釋放 element_t 本體（free(mid)）。
避免記憶體洩漏,釋放 value。

q_delete_dup

if (safe != head && !strcmp(first->value, second->value)) {
            list_del(node); 
            free(first->value); 
            free(first); 
            dup = true; 
        } 
        else if (dup) {
            element_t *tmp = list_entry(node, element_t, list);
            list_del(node); 
            free(tmp->value); 
            free(tmp); 
            dup = false;

一開始我浮現一個疑問就是在前面已經刪除節點了，標記的意義是什麼？為什麼之後再發現dup的時候還需要刪除節點？

這段程式碼的處理想法是一個有重複字串的排序鏈表，並且在發現相鄰元素有相同的值時，會刪除這些元素。標記 dup 的目的是標示在遍歷過程中是否已經發現並刪除了重複元素。

關於 dup 標記的意義
當標記 dup 為 true 時，表示當前已經發現了一個重複的元素對。這時候，接下來遍歷到的所有具有相同字串的元素都應該被刪除。這是為了保證每一個重複元素都能被刪除，而不只是跳過已經處理過的元素。

q_swap,q_reverse,and q_reversek

多虧老師上課提到q_swap是一個q_reversek的k=2特例，因此啟發我進一步思考發現其實q_reverse也是q_reversek的一個k=Q_size的特例！
經過這個邏輯直覺的思考後，便開始實做.

q_swap

q_reverseK(head, 2);

q_reverse

根據上面的想法
q_reverseK(head,q_size);
應該可以順利做出，然而仔細查看Q_reversek

       list_cut_position(&tmp, head, tail->prev);
        q_reverse(&tmp);
        list_splice_tail_init(&tmp, &new_head);
    }
    list_splice_init(&new_head, head);

錯誤是因為在 q_reverseK 中調用了 q_reverse，而 q_reverse 本身也會調用 q_reverseK。這可能導致遞迴調用，尤其是當 q_reverse 的實作本身依賴於 q_reverseK 時，最終會造成不必要的遞迴調用。

q_reversek

list_for_each (tail, head)：遍歷 head 鏈結串列的節點，尋找 k 個節點的尾端。
當 j >= k 時，tail 會指向這組的 第 k+1 個節點。

list_cut_position(&tmp, head, tail->prev);
q_reverse(&tmp);
list_cut_position(&tmp, head, tail->prev)：將 head 前 k 個節點剪下，存放至 tmp。
q_reverse(&tmp)：反轉 tmp 內的 k 個節點。

以上為簡單講解實現方式。

小結

由於作業時間的因素，以及最後評估效能增加不顯著，因此留作為未來改善的方向。

未來改善的初步想法：
我們可以避免在 q_reverse 內部調用 q_reverseK，從而避免遞迴調用的錯誤。最簡單的做法是在 q_reverseK 中實作鏈結串列反轉邏輯，而不依賴於 q_reverse。

q_sort

Merge_two_lists

struct list_head *node = (descend ^ (strcmp(e1->value, e2->value) < 0))
                                 ? L1->next
                                 : L2->next;

​​​​strcmp(e1->value, e2->value) < 0：
​​​​    若 e1->value 小於 e2->value，則回傳 true（升冪順序）。
​​​​    若 e1->value 大於 e2->value，則回傳 false（降冪順序）。
​​​​descend ^ (條件判斷)：使用 XOR 運算來決定選擇哪個節點。
​​​​    當 descend == false（升冪排序）：選擇較小的節點。
​​​​    當 descend == true（降冪排序）：選擇較大的節點。

list_move_tail(node, &head);

將選擇的節點移動到 head（新的合併串列）。

list_splice_tail_init(list_empty(L1) ? L2 : L1, &head);

如果 L1 或 L2 還有剩餘的節點，直接將剩下的部分接到 head 的尾部。

list_splice(&head, L1);

最後將 head 的內容搬回 L1，完成合併。

struct list_head *slow = head;
const struct list_head *fast = NULL;

for (fast = head->next; fast != head && fast->next != head;
     fast = fast->next->next)
    slow = slow->next;

這段程式碼使用快慢指標與前面相同

struct list_head left;
list_cut_position(&left, head, slow);

    list_cut_position：將 head 切成兩個部分：
        head 變成前半部分。
        left 變成後半部分。

q_sort(&left, descend);
q_sort(head, descend);

遞迴地對兩個部分進行排序。

mergeTwoLists(head, &left, descend);

最後使用 mergeTwoLists 合併兩個排序好的部分，完成排序。

q_ascend and q_descend

由於兩者方法幾乎相同，以q_ascend為例。

list_for_each (curr, head) {

    list_for_each 是 Linux Kernel 提供的巨集，會遍歷 head 所指向的鏈結串列。

while (tail != head &&
       strcmp(list_entry(curr, element_t, list)->value,
              list_entry(tail, element_t, list)->value) < 0) {

strcmp(e1->value, e2->value) < 0：

如果當前節點 curr 的值小於 tail，表示 curr 需要被刪除，因為 右邊 tail 有更大的值。

tmp= tail->prev;
list_del(tail);
q_release_element(list_entry(tail, element_t, list));
tail = tmp;

刪除 tail，因為 tail 儲存的是右側的更大值，意味著 curr 需要移除。
list_del(tail)：從鏈結串列中刪除 tail。
q_release_element(list_entry(tail, element_t, list))：釋放 tail 所指向的記憶體。
tail = tmp：讓 tail 指向被刪除節點的前一個節點，以便繼續檢查。

q_merge

合併所有佇列

struct list_head *pos = head->next->next;
struct list_head *n;

​​​​pos：從 head->next->next 開始遍歷，因為 head->next 是 first_queue，不需要再合併自己。

while (pos != head) {

​​​​遍歷 head 的鏈結串列，依次處理每個 queue_contex_t。

n = pos->next;
queue_contex_t *current_queue = container_of(pos, queue_contex_t, chain);

儲存下一個節點：避免修改鏈結串列後影響遍歷。
取得 current_queue：從 pos 轉換為 queue_contex_t 結構。

list_splice_init(current_queue->q, first_queue->q);

將 current_queue->q 佇列的所有元素移到 first_queue->q。
list_splice_init：
將 current_queue->q 佇列插入 first_queue->q 的尾端。
清空 current_queue->q（INIT_LIST_HEAD(current_queue->q)）。

current_queue->size = 0;

清空 current_queue 的大小，因為它已經合併到 first_queue。

pos = n;

移動到下一個 queue_contex_t，繼續合併。

論文 <Dude,is my code contstant time>

1. 檢測流程概述

該方法的核心概念是 時間洩漏檢測（timing leakage detection），主要透過統計分析來確認執行時間是否會因輸入資料的不同而變化，從而推測程式是否可能受到時間攻擊（timing attack）。

整個檢測流程分為三個主要步驟：

​​​​測量執行時間
​​​​後處理測量數據
​​​​應用統計檢定

2. 詳細檢測流程

步驟 1：測量執行時間

該步驟的目的是收集執行時間數據，以判斷程式是否存在時間變異性。

定義測試類別：將輸入數據分為 固定值類別（fix class） 和 隨機值類別（random class） 來進行測試。
執行時間測量：
使用 CPU 週期計數器（cycle counter）（如 x86 TSC 或 ARM systick）。
在低階硬體上，可能需要高解析度計時器或外部設備來測量。
環境條件控制：
為了避免測量誤差，每次測試的輸入類別應隨機選擇，並確保外部影響最小化（如系統中斷等）。

步驟 2：後處理測量數據

收集的執行時間數據可能受到雜訊影響，因此需要進行後處理：

裁剪（Cropping）：
由於計時數據通常呈現 右偏分佈（positively skewed），可以移除過高的數據點（如設定閾值）。
高階預處理：
可以使用非線性變換（如 centered product 方法）來增強檢測效果。

步驟 3：應用統計檢定

最關鍵的一步是應用統計方法來判斷兩組執行時間分佈是否不同：

t-檢定（Welch’s t-test）：
測試兩組數據的均值是否相等。
若檢定結果顯示顯著差異，則表示執行時間依賴於輸入數據，可能存在時間洩漏。
非參數檢定（如 Kolmogorov-Smirnov test）：
適用於無法假設分佈形狀的情況，但可能需要更多數據來收斂結果。

3. 測試結果與案例分析

研究者使用該方法測試了不同類型的加密演算法，結果顯示該方法能夠有效偵測變異時間執行：

變數時間（variable-time）記憶體比較：
測試了 memcmp，結果顯示執行時間與輸入數據相關，存在時間洩漏。
AES 加密：
傳統 T-tables 實作被檢測出明顯的時間變異性。
Bitsliced AES 則被確認為常數時間執行（未發現統計顯著的洩漏）。
Curve25519 在 ARM7TDMI 上的實作：
發現其變異時間執行來自 ARM7TDMI 處理器的變數時間乘法指令。

dudect

亂數

實做shuffle命令

add_cmd 會在命令列表中添加新命令，要新增一條新命令 shuffle 則要實作 do_shuffle，並在qtest.c 的 console_init() 加上 ADD_COMMAND。

ADD_COMMAND(shuffle, "Do Fisher-Yates shuffle", "");

qtest 裡的 do_shuffle 加上shuffle的限制條件 :

static bool do_shuffle(int argc, char *argv[])
{
    if (!current || !current->q)
        report(3, "Warning: Calling shuffle on null queue");
    error_check();
    if (q_size(current->q) < 2)
        report(3, "Warning: Calling shuffle on single queue");
    error_check();
    if (exception_setup(true))
        q_shuffle(current->q);
    q_show(3);
    return !error_check();
}

依照 Fisher–Yates shuffle 提供的演算法:
將new指到 last->prev 也就是last 前一個
再用old （隨機的節點）與new交換，並逐漸減小大小

void q_shuffle(struct list_head *head) 
{
    if (!head || list_is_singular(head)) 
        return;
    struct list_head *last = head;
    int size = q_size(head);
    while (size > 0) {
        int index = rand() % size;
        struct list_head *new = last->prev;
        struct list_head *old = new;
        while (index--) 
            old = old->prev;
        swap(new, old);
        last = last->prev;
        size--;
    }
    return;
}

接下來用腳本測試結果

Expectation:  41666
Observation:  {'1234': 41889, '1243': 41786, '1324': 41679, '1342': 41628, '1423': 41565, '1432': 41527, '2134': 41724, '2143': 41962, '2314': 41514, '2341': 41524, '2413': 41735, '2431': 41478, '3124': 41788, '3142': 41491, '3214': 41716, '3241': 41830, '3412': 41962, '3421': 41807, '4123': 41662, '4132': 41598, '4213': 41375, '4231': 41420, '4312': 41400, '4321': 41940}
chi square sum:  17.94479911678587

histogram

Valgrind

運用 Valgrind 排除 qtest 實作的記憶體錯誤

執行 $ make valgrind 後，得到以下訊息：

scripts/driver.py -p /tmp/qtest.xabQT9 --valgrind 
---     Trace           Points
+++ TESTING trace trace-01-ops:
--56105:0:libcfile Valgrind: FATAL: Private file creation failed.
   The current file descriptor limit is 1073741804.
   If you are running in Docker please consider
   lowering this limit with the shell built-in limit command.
--56105:0:libcfile Exiting now.
---     trace-01-ops    0/5

Why Does This Cause an Issue?

Valgrind 使用檔案描述符來管理內部檔案

Valgrind 在執行時會建立私有的暫存檔案，並且依賴合理的檔案描述符（File Descriptor, FD）上限來運作。若 FD 限制過高，Valgrind 可能無法正確建立這些檔案，因為它無法配置必要的結構來管理這麼大量的描述符。

系統限制與核心約束

大多數 Linux 系統 預期的 FD 限制通常是 1024、4096 或 65536，但不會設定成數十億。若 FD 限制過高，可能會影響核心（Kernel）內部的檔案表分配，導致 Valgrind 無法正常建立私有檔案。

如何修正？

將 FD 限制調整為更合理的數值

ulimit -n 65536

最終，執行 make valgrind

dingsen@dingsen:~/linux/lab0-c$ make valgrind
# Explicitly disable sanitizer(s)
make clean SANITIZER=0 qtest
make[1]: Entering directory '/home/dingsen/linux/lab0-c'
rm -f qtest.o report.o console.o harness.o queue.o random.o dudect/constant.o dudect/fixture.o dudect/ttest.o shannon_entropy.o linenoise.o web.o .qtest.o.d .report.o.d .console.o.d .harness.o.d .queue.o.d .random.o.d .dudect/constant.o.d .dudect/fixture.o.d .dudect/ttest.o.d .shannon_entropy.o.d .linenoise.o.d .web.o.d *~ qtest /tmp/qtest.*
rm -rf .dudect
rm -rf *.dSYM
(cd traces; rm -f *~)
  CC    qtest.o
  CC    report.o
  CC    console.o
  CC    harness.o
  CC    queue.o
  CC    random.o
  CC    dudect/constant.o
  CC    dudect/fixture.o
  CC    dudect/ttest.o
  CC    shannon_entropy.o
  CC    linenoise.o
  CC    web.o
  LD    qtest
make[1]: Leaving directory '/home/dingsen/linux/lab0-c'
cp qtest /tmp/qtest.2MIX7V
chmod u+x /tmp/qtest.2MIX7V
sed -i "s/alarm/isnan/g" /tmp/qtest.2MIX7V
scripts/driver.py -p /tmp/qtest.2MIX7V --valgrind 
---     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, remove_head, reverse and merge
---     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, sort, descend and reverseK
---     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
Warning: Skip checking the stability of the sort because the number of elements 2000000 is too large, exceeds the limit 100000.
---     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

通過！

研讀 lib/list_sort.c 並嘗試改進

Last changed by 
 
DINGSEN
0
111

Read more

linux2025-homework2

contribute by &lt;dingsen-Greenhorn&gt;

Mar 16, 2025
2025q1_Homework1_ideas

Mar 4, 2025
Read more from DINGSEN
Published on HackMD