2024q1 Homework1 (lab0)

contributed by < hugo0406 >

開發環境

$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  8
  On-line CPU(s) list:   0-7
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i7-8565U CPU @ 1.80GHz
    CPU family:          6
    Model:               142
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            12
    CPU max MHz:         4600.0000
    CPU min MHz:         400.0000
    BogoMIPS:            3999.93

說好的進度呢？

佇列實作與改進

q_new

宣告一個結構指標 head ，並且使用 list.h 中的 INIT_LIST_HEAD 進行初始化 ，讓 next 和 prev 都指向 head本身。 在依 queue.h 裡 q_new() 的註解 ， 當記憶體配置失敗，返回 NULL

留意詞彙的使用：

• 資訊科技詞彙翻譯
• 詞彙對照表

避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。
在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","

q_free

直覺的想法是去走訪佇列的每個節點並釋放，使用 list.h 中的 list_for_each_entry_safe 去走訪每個節點，並釋放記憶體空間， 依 queue.h 裡 q_free() 的註解要去釋放佇列使用的所有儲存空間，所以連同 head 及 element_t 裡成員所指向字串的記憶體區塊也要進行釋放。

改進你的漢語表達。

q_insert_head

依 queue.h 裡 q_insert_head() 的註解，把給定的新節點插入在佇列開頭 (LIFO)，並把給定的字串複製並插入在節點裡面。成功返回 true，分配失敗或佇列為 NULL 時返回 false，也就是說有用到 malloc() 這個函式都要進行判斷。

對照 Dictionary.com 對 implement 一詞的解釋:

• to fulfill; perform; carry out:
• to put into effect according to or by means of a definite plan or procedure.
• Computers. to realize or instantiate (an element in a program), often under certain conditions as specified by the software involved.
• to fill out or supplement

「實作」會是符合上述 "implement" 語意的譯詞，取「起」以「創作」的意思，而「製造」本質上是固定輸入並通常產生固定輸出的行為。

$\to$ 資訊科技詞彙翻譯

一開始實作是先配置要被複製字串長度的記憶體空間，在使用 strcpy() ，進行複製。在使用 list.h 中的 list_add()將節點加入在串列的開頭。但根據老師 lab0 教材裡的 (依據 CERN Common vulnerabilities guide for C programmers 建議而移除 gets / sprintf / strcpy 等不安全的函式)，改用 strncpy() 進行複製。

The strcpy built-in function does not check buffer lengths and may very well overwrite memory zone contiguous to the intended destination. In fact, the whole family of functions is similarly vulnerable: strcpy, strcat and strcmp.

在 make test 的時候第十一項測試沒有通過，錯誤訊息如下:

+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
ERROR: Freed queue, but 4 blocks are still allocated
---     trace-11-malloc 0/6

經過除錯之後是在判斷配置字串是否成功時，若失敗時需要連同節點一起釋放掉，而不是直接返回 false。

q_insert_tail

與 q_insert_head 實做的想法類似，把給定的新節點插入在佇列結尾 (FIFO)，只須把 list.h 中的 list_add() 改成 list_add_tail()。

q_remove_head

依 queue.h 裡 q_remove_head() 的註解，把佇列開頭的節點移除，其中 "移除" 與 "刪除" 不同，element 與字串所使用的空間不應被釋放。

想法是利用list.h 中的 list_entry 找出第一個節點的位址，若 sp 不為 NULL ， 複製字串到 sp ，再使用 list_del_init 移除並且初始化。這邊不能使用 list_del 的原因是未初始化，若存取該節點的next 或 prev 指標是不安全的。一開始對 LIST_POISONING 的用途不是很了解，但參考 2024-02-{20,27} 問答簡記 解開心中的疑惑。

q_remove_tail

與 q_remove_tail 實做想法相當類似，只須把 list_entry 中的第一個參數 head->next (佇列第一個節點) 改成 head->prev (佇列最後一個節點)。

q_size

使用 list.h 中的 list_for_each 去走訪每個節點，並計算節點個數。

q_delete_mid

考慮到環狀佇列，使用 fnt 及 end 兩個指標，前者從佇列的開頭往後走訪，後者從佇列的尾端往前走訪。有兩種情況，第一種為佇列上的節點是奇數個，當 fnt == end，則此節點為中間點;第二種為佇列上的節點是偶數個，當fnt 與 end 鄰近，也就是fnt->next == end ，則 end 為中間點。

改進你的漢語表達。

q_delete_dup

q_swap

q_reverse

使用 list_for_each_safe() 去走訪每個節點，並把當前 *curr 所指到的節點透過 list_move() 移動到 head 的開頭

q_reverse_k

q_sort

q_ascend

q_descend

q_merge