# 2025q1 Homework1 (lab0)
contributed by <markarz>
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## 開發環境
```
jorge@jorge-MS-7E56:~/linux2025/lab0-c$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 48 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: AuthenticAMD
Model name: AMD Ryzen 7 9700X 8-Core Processor
CPU family: 26
Model: 68
Thread(s) per core: 2
Core(s) per socket: 8
Socket(s): 1
Stepping: 0
Frequency boost: enabled
CPU(s) scaling MHz: 53%
CPU max MHz: 5581.0000
CPU min MHz: 600.0000
BogoMIPS: 7599.99
jorge@jorge-MS-7E56:~/linux2025/lab0-c$ gcc -v
Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/libexec/gcc/x86_64-linux-gnu/13/lto-wrapper
OFFLOAD_TARGET_NAMES=nvptx-none:amdgcn-amdhsa
OFFLOAD_TARGET_DEFAULT=1
Target: x86_64-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Ubuntu 13.3.0-6ubuntu2~24.04' --with-bugurl=file:///usr/share/doc/gcc-13/README.Bugs --enable-languages=c,ada,c++,go,d,fortran,objc,obj-c++,m2 --prefix=/usr --with-gcc-major-version-only --program-suffix=-13 --program-prefix=x86_64-linux-gnu- --enable-shared --enable-linker-build-id --libexecdir=/usr/libexec --without-included-gettext --enable-threads=posix --libdir=/usr/lib --enable-nls --enable-bootstrap --enable-clocale=gnu --enable-libstdcxx-debug --enable-libstdcxx-time=yes --with-default-libstdcxx-abi=new --enable-libstdcxx-backtrace --enable-gnu-unique-object --disable-vtable-verify --enable-plugin --enable-default-pie --with-system-zlib --enable-libphobos-checking=release --with-target-system-zlib=auto --enable-objc-gc=auto --enable-multiarch --disable-werror --enable-cet --with-arch-32=i686 --with-abi=m64 --with-multilib-list=m32,m64,mx32 --enable-multilib --with-tune=generic --enable-offload-targets=nvptx-none=/build/gcc-13-fG75Ri/gcc-13-13.3.0/debian/tmp-nvptx/usr,amdgcn-amdhsa=/build/gcc-13-fG75Ri/gcc-13-13.3.0/debian/tmp-gcn/usr --enable-offload-defaulted --without-cuda-driver --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu --with-build-config=bootstrap-lto-lean --enable-link-serialization=2
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 13.3.0 (Ubuntu 13.3.0-6ubuntu2~24.04)
```
## 實做queue.c
### q_new
使用malloc配置給head一個struct list_head的記憶體空間大小，如果空見配置成功就會用list.h裡的INIT_LIST_HEAD()初始化head。
```
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
if (head)
INIT_LIST_HEAD(head);
return head;
}
```
---
### q_free
如果l指向null，就不做任何事，如果指向非空會用list.h裡面的list_for_each_entry_safe找尋每個節點，並用 q_release_element釋放空間，最後在釋放l的記憶體空間。
```
void q_free(struct list_head *l)
{
if (!l)
return;
element_t *entry, *safe = NULL;
list_for_each_entry_safe (entry, safe, l, list)
q_release_element(entry);
free(l);
}
```
### q_insert_head
先驗證 head 和 s 是否為空指標，嘗試使用 malloc 動態分配 element_t 結構所需的記憶體空間給 new_element；若記憶體分配失敗，則立即返回 false。若成功分配，則進一步利用 strdup() 函式對字串 s 進行深度複製，將內容安全地賦值給 new_element->value。若字串複製失敗，則需釋放已分配的 new_element 記憶體並返回 false。最後，在所有前置條件和記憶體操作皆成功的情況下，透過 list_add 將新建立的節點插入至鏈結串列的頭部。
```
bool q_insert_head(struct list_head *head, char *s)
{
if (!head || !s) // 確保 head 和 s 不是 NULL
return false;
element_t *new_element = malloc(sizeof(element_t));
if (!new_element) // 檢查 malloc 是否成功
return false;
new_element->value = strdup(s); // 分配記憶體並複製字串
if (!new_element->value) {
free(new_element);
return false;
}
list_add(&new_element->list, head); // 插入節點
return true;
}
```
### q_insert_tail
先驗證 head 和 s 是否為空指標，嘗試使用 malloc 動態分配 element_t 結構所需的記憶體空間給 new_element；若記憶體分配失敗，則立即返回 false。若成功分配，則進一步利用 strdup() 函式對字串 s 進行深度複製，將內容安全地賦值給 new_element->value。若字串複製失敗，則需釋放已分配的 new_element 記憶體並返回 false。最後，在所有前置條件和記憶體操作皆成功的情況下，透過 list_add_tail 將新建立的節點插入至鏈結串列的尾巴。
```
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head || !s) // 確保 head 和 s 不是 NULL
return false;
element_t *new_element = malloc(sizeof(element_t));
if (!new_element) // 檢查 malloc 是否成功
return false;
new_element->value = strdup(s); // 分配記憶體並複製字串
if (!new_element->value) {
free(new_element);
return false;
}
list_add_tail(&new_element->list, head); // 插入節點
return true;
}
```
### q_remove_head
先驗證head 和 s 是否為空指標，接下來用list_first_entry()將elem指向queue的第一個節點，用list_del()將elem變成一個獨立的節點，用strncpy()將elem->value的字串複製到sp也就是緩衝區位置，最後回傳elem的指標。
```
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *elem = list_first_entry(head, element_t, list);
list_del(&elem->list);
if (sp && bufsize > 0) {
sp[0] = '\0';
if (elem->value) {
strncpy(sp, elem->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
}
return elem;
}
```
### q_remove_tail
先驗證head 和 s 是否為空指標，接下來用list_last_entry()將elem指向queue最後一個節點，用list_del()將elem變成一個獨立的節點，用strncpy()將elem->value的字串複製到sp也就是緩衝區位置，最後回傳elem的指標。
```
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *elem = list_last_entry(head, element_t, list);
list_del(&elem->list);
if (sp && bufsize > 0) {
// 先將緩衝區置空，避免後面狀況導致舊資料殘留
sp[0] = '\0';
// 若 elem->value 不為 NULL，就做字串拷貝
if (elem->value) {
strncpy(sp, elem->value, bufsize - 1);
sp[bufsize - 1] = '\0'; // 確保結尾有 '\0'
}
}
return elem;
}
```
### q_delete_mid
```
bool q_delete_mid(struct list_head *head)
{
if (!head)
return NULL;
if (list_is_singular(head)) {
list_del(head);
return true;
}
struct list_head *cur = NULL;
struct list_head *tmp = NULL;
int mid = 0, current = -1;
cur = head;
mid = q_size(head) / 2;
while (cur != NULL && current != mid) {
tmp = cur;
cur = cur->next;
current++;
}
element_t *del_element = list_entry(cur, element_t, list);
tmp->next = cur->next;
q_release_element(del_element);
return true;
}
```
### q_delete_dup
```
bool q_delete_dup(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return false;
struct list_head *cur = head->next;
while (cur != head) {
element_t *elem1 = list_entry(cur, element_t, list);
struct list_head *next = cur->next;
bool has_duplicate = false;
// 檢查後面是否有相同的數據
while (next != head) {
element_t *elem2 = list_entry(next, element_t, list);
if (strcmp(elem1->value, elem2->value) == 0) {
struct list_head *dup = next;
next = next->next;
list_del(dup);
q_release_element(elem2);
has_duplicate = true;
} else
break;
}
struct list_head *temp = cur;
cur = next;
// 如果 `has_duplicate == true`，代表 `temp` 也應該刪除
if (has_duplicate) {
list_del(temp);
q_release_element(elem1);
}
}
return true;
}
```
### q_swap
```
void q_swap(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *cur = head->next;
while (cur != head && cur->next != head) {
struct list_head *next = cur->next;
// 取得 element_t 結構體
element_t *elem1 = list_entry(cur, element_t, list);
element_t *elem2 = list_entry(next, element_t, list);
// 交換 `value`（這裡只交換指標，因為 `value` 是字串）
char *temp = elem1->value;
elem1->value = elem2->value;
elem2->value = temp;
// 移動 cur 到下一對
cur = next->next;
}
}
```
### q_reverse
```
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *cur = head->next, *last = head->prev;
while (cur != last && last->next != cur) {
element_t *elem1 = list_entry(cur, element_t, list);
element_t *elem2 = list_entry(last, element_t, list);
// 交換 `value`
char *temp = elem1->value;
elem1->value = elem2->value;
elem2->value = temp;
cur = cur->next;
last = last->prev;
}
}
```
### q_reverseK
```
void q_reverseK(struct list_head *head, int k)
{
if (!head || list_empty(head) || list_is_singular(head) || k == 1)
return;
struct list_head *cur = head->next;
while (cur != head) {
struct list_head *start = cur, *end = cur;
int count = 1;
// 找到 k 個節點
while (count < k && end->next != head) {
end = end->next;
count++;
}
if (count < k) // 剩餘節點不足 k 個，停止
break;
struct list_head *left = start, *right = end;
while (left != right && right->next != left) {
element_t *elem1 = list_entry(left, element_t, list);
element_t *elem2 = list_entry(right, element_t, list);
// 交換 `value`
char *temp = elem1->value;
elem1->value = elem2->value;
elem2->value = temp;
left = left->next;
right = right->prev;
}
cur = end->next; // 移動到下一組
}
}
```
我一開始用 快速排序（Quick Sort） 的方式寫，結果測資過不了。測資會過不了的原因，可能是因為其中含有已排列過的資料，所以我後來改用 合併排序（Merge Sort）。改用之後，時間複雜度基本上都可以維持在 O(nlogn)。
[merge sort參考連結](https://hackmd.io/@lambert-wu/list-merge-sort)
### q_sort
```
static inline void split_in_half(struct list_head *src,struct list_head *left_out)
{
struct list_head *slow_ptr =
src->next; // `slow_ptr` will be the tail of the left part.
// Starts at the first actual element.
struct list_head *fast_ptr =
src->next->next;
while (fast_ptr != src && fast_ptr->next != src) {
slow_ptr = slow_ptr->next;
fast_ptr = fast_ptr->next->next;
}
list_cut_position(left_out, src, slow_ptr);
}
static inline void merge_two_sorted(struct list_head *dest,
struct list_head *left,
struct list_head *right,
bool descend)
{
while (!list_empty(left) && !list_empty(right)) {
element_t *a = list_first_entry(left, element_t, list);
element_t *b = list_first_entry(right, element_t, list);
int cmp = strcmp(a->value, b->value);
if (descend) { // If descending, reverse comparison logic
cmp = -cmp;
}
if (cmp <= 0) {
list_move_tail(&a->list, dest);
} else {
list_move_tail(&b->list, dest);
}
}
if (!list_empty(left)) {
list_splice_tail_init(left, dest);
}
if (!list_empty(right)) {
list_splice_tail_init(right, dest);
}
}
void q_sort(struct list_head *head, bool descend)
{
if (!head || list_empty(head) || list_is_singular(head)) {
return;
}
split_in_half(head, &left_half);
q_sort(&left_half, descend); // Sort the left part.
q_sort(head, descend); // Sort the right part (which is now in `head`).
struct list_head merged;
INIT_LIST_HEAD(&merged);
merge_two_sorted(&merged, &left_half, head, descend);
list_splice_tail_init(&merged, head);
}
```
**自己寫的quick sort與參考別人寫的merge sort測資比較**
Sign in with Wallet
Connect another wallet