# 2024q1 Homework1 (lab0) contributed by < [`hugo0406`](https://github.com/hugo0406) > ## 開發環境 ```shell $ 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 ``` :::danger 說好的進度呢? ::: ## 佇列實作與改進 ### `q_new` 宣告一個結構指標 head ,並且使用 [list.h ](https://github.com/sysprog21/lab0-c/blob/master/list.h) 中的 `INIT_LIST_HEAD` 進行初始化 ,讓 next 和 prev 都指向 head本身。 在依 [queue.h](https://github.com/sysprog21/lab0-c/blob/master/queue.h) 裡 q_new() 的註解 , 當記憶體配置失敗,返回 NULL :::danger :warning: 留意詞彙的使用: * [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary) * [詞彙對照表](https://hackmd.io/@l10n-tw/glossaries) 避免過多的中英文混用,已有明確翻譯詞彙者,例如「鏈結串列」(linked list) 和「佇列」(queue),就使用該中文詞彙,英文則留給變數名稱、人名,或者缺乏通用翻譯詞彙的場景。 在中文敘述中,使用全形標點符號,例如該用「,」,而非 "," ::: ### `q_free` 直覺的想法是去走訪佇列的每個節點並釋放,使用 [list.h ](https://github.com/sysprog21/lab0-c/blob/master/list.h) 中的 `list_for_each_entry_safe` 去走訪每個節點,並釋放記憶體空間, 依 [queue.h](https://github.com/sysprog21/lab0-c/blob/master/queue.h) 裡 q_free() 的註解要去釋放佇列使用的所有儲存空間,所以連同 head 及 element_t 裡成員所指向字串的記憶體區塊也要進行釋放。 :::danger 改進你的漢語表達。 ::: ### `q_insert_head` 依 [queue.h](https://github.com/sysprog21/lab0-c/blob/master/queue.h) 裡 q_insert_head() 的註解,把給定的新節點插入在佇列開頭 (LIFO),並把給定的字串複製並插入在節點裡面。成功返回 true,分配失敗或佇列為 NULL 時返回 false,也就是說有用到 malloc() 這個函式都要進行判斷。 :::danger 對照 Dictionary.com 對 [implement](https://www.dictionary.com/browse/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$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary) ::: 一開始實作是先配置要被複製字串長度的記憶體空間,在使用 strcpy() ,進行複製。在使用 [list.h ](https://github.com/sysprog21/lab0-c/blob/master/list.h) 中的 `list_add()`將節點加入在串列的開頭。但根據老師 lab0 教材裡的 (依據 CERN [Common vulnerabilities guide for C programmers](https://security.web.cern.ch/security/recommendations/en/codetools/c.shtml) 建議而移除 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` 的時候第十一項測試沒有通過,錯誤訊息如下: ```terminal +++ 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 ](https://github.com/sysprog21/lab0-c/blob/master/list.h) 中的 `list_add()` 改成 `list_add_tail()`。 ### `q_remove_head` 依 [queue.h](https://github.com/sysprog21/lab0-c/blob/master/queue.h) 裡 q_remove_head() 的註解,把佇列開頭的節點移除,其中 "移除" 與 "刪除" 不同,element 與字串所使用的空間不應被釋放。 想法是利用[list.h ](https://github.com/sysprog21/lab0-c/blob/master/list.h) 中的 `list_entry` 找出第一個節點的位址,若 sp 不為 NULL , 複製字串到 sp ,再使用 `list_del_init` 移除並且初始化。這邊不能使用 `list_del ` 的原因是未初始化,若存取該節點的`next` 或 `prev` 指標是不安全的。一開始對 `LIST_POISONING` 的用途不是很了解,但參考 [2024-02-{20,27} 問答簡記](https://hackmd.io/YCnIwo_0R-GaYjISEZwG1A?view#%E7%82%BA%E4%BD%95-listh-%E9%81%B8%E5%AE%9A-0x00100100-%E8%88%87-0x00200200-%E4%BD%9C%E7%82%BA%E7%84%A1%E6%95%88%E7%9A%84%E5%9C%B0%E5%9D%80%EF%BC%9F) 解開心中的疑惑。 ### `q_remove_tail` 與 `q_remove_tail` 實做想法相當類似,只須把 list_entry 中的第一個參數 `head->next` (佇列第一個節點) 改成 `head->prev` (佇列最後一個節點)。 ### `q_size` 使用 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h) 中的 `list_for_each` 去走訪每個節點,並計算節點個數。 ### `q_delete_mid` 考慮到環狀佇列,使用 `fnt` 及 `end` 兩個指標,前者從佇列的開頭往後走訪,後者從佇列的尾端往前走訪。有兩種情況,第一種為佇列上的節點是奇數個,當 `fnt == end`,則此節點為中間點;第二種為佇列上的節點是偶數個,當`fnt` 與 `end` 鄰近,也就是`fnt->next == end` ,則 `end` 為中間點。 :::danger 改進你的漢語表達。 ::: ### `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`
×
Sign in
Email
Password
Forgot password
or
By clicking below, you agree to our
terms of service
.
Sign in via Facebook
Sign in via Twitter
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
Wallet (
)
Connect another wallet
New to HackMD?
Sign up