# 2025q1 Homework1 (lab0)
contributed by < `vestata` >

{%hackmd NrmQUGbRQWemgwPfhzXj6g %}

## 開發環境

$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0

$ 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-13700
    CPU family:           6
    Model:                183

## 針對佇列操作的程式碼實作

- [x] q_new
- [x] q_free
- [x] q_insert_head
- [x] q_insert_tail
- [x] q_remove_head
- [x] q_remove_tail
- [x] q_size
- [ ] q_delete_mid
- [ ] q_delete_dup
- [ ] q_swap
- [ ] q_reverse
- [ ] q_reverseK
- [ ] q_sort
- [ ] q_ascend
- [ ] q_descend
- [ ] q_merge

---

/* Free all storage used by queue */
void q_free(struct list_head *head) {
    if(!head)   return;

    element_t *tmp, *safe;
    list_for_each_entry_safe(tmp, safe, head, list) {
        q_release_element(tmp);
    }
    free(head);
    return;
}

要記得釋放 `head`，根據 `queue.h` 的敘述：

/**
 * q_free() - Free all storage used by queue, no effect if header is NULL
 * @head: header of queue
 */

若是 `head` 記憶體沒有被釋放會出現以下錯誤：

ERROR: There is no queue, but 1 blocks are still allocated

[commit](https://github.com/vestata/lab0-c/commit/f2f59763dc791b766d65304147f2c44c205db3f5)

### `q_insert_head()` and `q_insert_tail()`
原本的實做方法無法通過 `trace-11-malloc`、`trace-12-malloc`。 查看 `traces/trace-11-malloc.cmd` `malloc` 的失敗率設為 25%。

In [strdup](https://linux.die.net/man/3/strdup):
>The strdup() function returns a pointer to a new string which is a duplicate of the strings. Memory for the new string is obtained with malloc(3), and can be freed with free(3).
> [name=Linux man page]

在 `harness.h` 中，`malloc`、`calloc`、`free` 和 `strdup` 都透過對應的巨集 `test_` 來執行自定義操作。而在 `qtest` 中，可以使用 `malloc [probability]` 命令來設定 `fail_probability`，導致 `test_strdup` 中的 `test_malloc` 可能因為 `fail_probability` 的影響而失敗。因此，需要加入相應的檢查機制。

         return false;
 
     new->value = strdup(s);
+    if (!new->value) {
+        free(new);
+        return false;
+    }
 
     list_add(&new->list, head);
     return true;

[commit 58c0e8b](https://github.com/vestata/lab0-c/commit/58c0e8bbfe7abde3a2e822be87193c758e8e6c15)

## 研讀 lib/list_sort.c