# 2024q1 Homework1 (lab0)
contributed by < `otteryc` >
## 開發環境
```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-7700K CPU @ 4.20GHz
CPU family: 6
Model: 158
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
Stepping: 9
CPU max MHz: 4500.0000
CPU min MHz: 800.0000
BogoMIPS: 8400.00
```
## 針對佇列操作的程式碼實作
### `q_insert_head`
依 `queue.h` 檔案中之指示，本函式當明確地<s>分配</s> 配置空間，並將傳入字串 `s` 存入所新增於佇列的物件中。
:::warning
allocate 翻譯為「配置」，而非「分配」，這樣才可跟 dispatch 的翻譯區隔，二者都頻繁在作業系統領域出現。
:::
惟查，關於 `s` 字串之大小，作業說明以及程式碼中，並無明確說明。為妥適配置記憶體，減少程式開銷，吾人查詢呼叫 `q_insert_head` 以及 `q_insert_tail` 之程式碼區段：
:::warning
改進你的漢語表達，文言文擬古不能掩蓋行文不流暢的現象，以清晰且無語病的白話文書寫。
:::
巨集 `dut_insert_head` ，所插入的字串係由 `get_random_string` 產生，而 random_string 則是由 `prepare_inputs`產生，揆諸前開函式，可知 random_string 長度固定為 8 個字元，而且是 well null-terminated。
```c
static char random_string[N_MEASURES][8];
static char *get_random_string(void)
{
random_string_iter = (random_string_iter + 1) % N_MEASURES;
return random_string[random_string_iter];
}
void prepare_inputs(uint8_t *input_data, uint8_t *classes)
{
randombytes(input_data, N_MEASURES * CHUNK_SIZE);
for (size_t i = 0; i < N_MEASURES; i++) {
classes[i] = randombit();
if (classes[i] == 0)
memset(input_data + (size_t) i * CHUNK_SIZE, 0, CHUNK_SIZE);
}
for (size_t i = 0; i < N_MEASURES; ++i) {
/* Generate random string */
randombytes((uint8_t *) random_string[i], 7);
random_string[i][7] = 0;
}
}
```
次查，在 `linenoice.c` 中，規定 console 中每行指令之上限為 4096
```c
#define LINENOISE_MAX_LINE 4096
```
:::danger
減少非必要的項目縮排 (即 `* `)，使用清晰、明確，且流暢的漢語書寫。
:::
本於上述觀察，吾人獲悉佇列中單一元素（即 `element_t`）中所指向的字串，大小最多為 4096 個位元。嘗試將之作為單一元素所指向的字串的長度上限，惟此舉會導致 `make test` 時，超過記憶體限制，只能以實作上需要兩次<s>遍歷</s> 走訪的 `strdup(3)` 替代之。
:::warning
留意[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::
```diff
bool q_insert_head(struct list_head *head, char *s)
{
if (!head || !s)
return false;
element_t *n = malloc(sizeof(element_t));
if (!n)
return false;
- n->value = malloc(MAX_STRING_LEN);
+ n->value = strdup(s);
if (!n->value) {
free(n);
return false;
}
- strncpy(n->value, s, MAX_STRING_LEN);
list_add(&n->list, head);
return true;
}
```
### `q_insert_tail`
本函式與 `q_insert_head` 的實作幾近相同，差異者係在插入新物件時，所使用之函式應改為 `list_add_tail` ，僅此而已。
TODO: 兩函式的實作或許可改以 macro 實作 ，俾降低程式碼維護成本。
:::warning
「或許」不該簡稱為「或」，否則會造成歧義。
:::
### `q_reverse`
<s>依題旨，本題</s> 本函式不得涉及記憶體管理的操作，本函式的想法是用兩個指標，`fast` 指標儲存被操作的物件的下一個物件的記憶體位置，`slow` 指標則負責將 `list_head` 結構體中分別指往前後的指標反向。並且，當 `slow` 指向 `head` 時，就代表反向完成。
```c
void q_reverse(struct list_head *head)
{
if (!head)
return;
struct list_head *fast = head->next, *slow = head, *tmp;
do {
tmp = slow->next;
slow->next = slow->prev;
slow->prev = tmp;
} while (slow = fast, fast = fast->next, slow != head);
}
```
### `q_delete_mid`
:::danger
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。
:::
<s>本題</s>由於這份作業的 queue 是由 doubly circular linked-list 實作，除了針對 singly linked-list 的快慢指標來尋找在佇列正中央的節點以外，還可以透過兩個指標分別從 head 跟 tail 開始互為反向地走訪，當兩個指標相遇時，就是佇列中點，並刪除之。
```c
struct list_head *right = head->next, *left = head->prev;
while (true) {
if (right == left)
break;
right = right->next;
if (right == left)
break;
left = left->prev;
}
```
上述程式碼，值得注意的是，讓 right 提早 left 移動一步，如此就可以解決當佇列中元素個數為偶數的情形，像是下圖情形，應被從佇列中刪除的是標示為 2 號的元素。
```graphviz
digraph delete_mid {
rankdir=LR
Head [label=H,shape=circle]
0 [shape=circle]
1 [shape=circle]
2 [color=Red, shape=circle]
3 [shape=circle]
Head->0
0->1
1->2
2->3
3->Head
}
```
:::warning
不該言及「本題」，個別函式之間存在關聯，應看待為整體的創作，只是依據工程開發的角度，逐項分析和探討。
:::
### `q_sort`
這一個函式依照指示用 merge sort 完成，在進行 conquer 的時候所用的函式可以獨立出來，供 `q_merge` 函式呼叫。
```c
void q_sort(struct list_head *head, bool descend)
{
if (!head || list_is_singular(head) || list_empty(head))
return;
struct list_head *right = head->next, *left = head->prev;
while (true) {
if (right == left)
break;
left = left->prev;
if (right == left)
break;
right = right->next;
}
LIST_HEAD(mid);
list_cut_position(&mid, head, right);
q_sort(head, descend);
q_sort(&mid, descend);
merge_sort_conquer(head, &mid, descend);
}
```
這裡一樣要尋找佇列中點，不過應該注意的是，當佇列內的節點個數是偶數時，應該要取的節點與上一個函式不同。
```graphviz
digraph delete_mid {
rankdir=LR
Head [label=H,shape=circle]
0 [shape=circle, color=red]
1 [shape=circle]
Head->0
0->1
1->Head
}
```
在這個情況下，應該要取編號為 0 的節點作為中點進行分出兩個子佇列，否則將無法有效的分治。
```diff
static void merge_sort_conquer(struct list_head *dest,
struct list_head *victim,
bool descend)
{
int mask = descend ? 0 : INT_MIN;
LIST_HEAD(result);
struct list_head *insert;
while (!list_empty(dest) && !list_empty(victim)) {
element_t *e_victim = list_first_entry(victim, element_t, list),
*e_dest = list_first_entry(dest, element_t, list);
insert = strcmp(e_victim->value, e_dest->value) & mask ? victim->next
: dest->next;
list_move_tail(insert, &result);
}
insert = list_empty(dest) ? victim : dest;
- list_splice_tail(insert, &result);
+ list_splice_tail_init(insert, &result)
list_splice(&result, dest);
return;
}
```
另外，在 conquer 的部分，透過 `strcmp` 函式回傳的值來判斷兩個節點之間的大小，根據 man strcmp(3)：
```
strcmp() returns an integer indicating the result of the comparison, as follows:
• 0, if the s1 and s2 are equal;
• a negative value if s1 is less than s2;
• a positive value if s1 is greater than s2.
```
此外，在排序時，兩個節點的內容相等時，孰先孰後並不重要。所以，在判斷要依升冪還是降冪排列時，只要觀查 strcmp 回傳值的 sign bit 就好，可以有效降低進行分支的次數。
另外， `list_splice_tail` 在搬離所有節點之後，不會妥善的處理來源佇列的 head ，如果這時候再去存取來源佇列的 head ，會造成未定義的結果，所以應該改用 `list_splice_tail`
### `q_merge`
這個函式所要處理的是把多個以排序佇列合而為一，僅需一一走訪，並使用前述 merge sort 的 conquer 函式把每個佇列連接在一起即可。
```c=
int q_merge(struct list_head *head, bool descend)
{
if (!head || list_empty(head))
return 0;
LIST_HEAD(result);
queue_contex_t *iter;
list_for_each_entry (iter, head, chain) {
// cppcheck-suppress uninitvar
merge_sort_conquer(&result, iter->q, descend);
INIT_LIST_HEAD(iter->q);
}
list_splice(&result, list_first_entry(head, queue_contex_t, chain)->q);
return q_size(list_first_entry(head, queue_contex_t, chain)->q);
}
```
另外，在第 9 行處， cppcheck 似乎會將 `iter->q` 認為未初始化的變數，由於在 `list_for_each_entry` 巨集的定義中，有確實的初始化 iter 變數，所以透過 suppress 選項 <s>指令</s> 使 cppcheck 暫不檢查此類潛在錯誤。
Sign in with Wallet
Connect another wallet