# 2025q1 Homework1 (lab0)
contributed by < Cactex >

{%hackmd NrmQUGbRQWemgwPfhzXj6g %}

# 開發環境

 $ hostnamectl
Operating System: Ubuntu 24.04.1 LTS              
Kernel: Linux 6.11.0-19-generic
              
 $ 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:            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) i5-10200H CPU @ 2.40GHz
CPU family:               6
Model:                    165
Thread(s) per core:       2
Core(s) per socket:       4
Socket(s):                1
Stepping:                 2
CPU(s) scaling MHz:       93%
CPU max MHz:              4100.0000
CPU min MHz:              800.0000
BogoMIPS:                 4800.00   
L1d:                      128 KiB (4 instances)
L1i:                      128 KiB (4 instances)
L2:                       1 MiB (4 instances)
L3:                       8 MiB (1 instance)             
NUMA node(s):             1
NUMA node0 CPU(s):        0-7

# 實作指定的佇列操作

在實作 ```queue.c``` 的函式之前，應閱讀 ```queue.h```中對應之函式說明。

並且在執行 `git commit` 前，使用 clang-format 工具

 $ clang-format -i *.[ch] 

來調整程式碼以符合作業要求的風格

## q_new
> commit [0e4d305
](https://github.com/Cactex/lab0-c/commit/0e4d305c199a7140d3afdef48aa6425bfcea9bee)

建立空佇列並且將 `next` 和 `prev` 都指向自己

struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(struct list_head));
    if (!head)
        return NULL;
    INIT_LIST_HEAD(head);
    return head;
}

## q_free
> commit [e37136f
](https://github.com/Cactex/lab0-c/commit/e37136fd93b69ab0fcb3b5c158979b2d9935296c)

釋放佇列`element_t` 使用的所有記憶體空間，若傳入值 `head` 是 `NULL`則不需要做任何操作

void q_free(struct list_head *head)
{
    if (!head)
        return;
    if (list_empty(head)) {
        free(head);
        return;
    }
    struct list_head *node, *safe;
    list_for_each_safe (node, safe, head) {
        element_t *target_ele = list_entry(node, element_t, list);
        q_release_element(target_ele);
    }
    free(head);
}

## q_insert_head
> commit [0e4d305
](https://github.com/Cactex/lab0-c/commit/0e4d305c199a7140d3afdef48aa6425bfcea9bee)

建立新的佇列元素並且將其插入到 `head` 和 `head->next` 中間
需要注意的是如果 `head` 為 `NULL` 或呼叫 `malloc()` 分配記憶體失敗則須回傳 `false`

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *new_element = malloc(sizeof(element_t));
    if (!new_element)
        return false;
    new_element->value = malloc(strlen(s) + 1);
    if (!new_element->value) {
        q_release_element(new_element);
        return false;
    }
    strlcpy(new_element->value, s, strlen(s) + 1);
    list_add(&new_element->list, head);
    return true;
}

## q_insert_tail
> commit [0e4d305
](https://github.com/Cactex/lab0-c/commit/0e4d305c199a7140d3afdef48aa6425bfcea9bee)

基本上和 `q_insert_head` 一樣，只是將元素加到佇列尾端

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *new_element = malloc(sizeof(element_t));
    if (!new_element)
        return false;
    new_element->value = malloc(strlen(s) + 1);
    if (!new_element->value) {
        q_release_element(new_element);
        return false;
    }
    strlcpy(new_element->value, s, strlen(s) + 1);
    list_add_tail(&new_element->list, head);
    return true;
}

## q_remove_head
> commit [0e4d305
](https://github.com/Cactex/lab0-c/commit/0e4d305c199a7140d3afdef48aa6425bfcea9bee)

"移出"佇列中第一個元素，並且回傳該地址
並將元素的值複製到 `sp` ，大小由 `bufsize` 決定，須注意 `bufsize` 中包含 `\0`

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    struct list_head *target_node = head->next;
    element_t *target_ele = list_entry(target_node, element_t, list);
    strlcpy(sp, target_ele->value, bufsize);
    list_del(target_node);
    return target_ele;
}

## q_remove_tail
> commit [0e4d305
](https://github.com/Cactex/lab0-c/commit/0e4d305c199a7140d3afdef48aa6425bfcea9bee)

"移出"佇列中最後一個元素，並且回傳該地址
並將元素的值複製到 `sp` ，大小由 `bufsize` 決定，須注意 `bufsize` 中包含 `\0`

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    struct list_head *target_node = head->prev;
    element_t *target_ele = list_entry(target_node, element_t, list);
    strlcpy(sp, target_ele->value, bufsize);
    list_del(target_node);
    return target_ele;
}

## q_delete_mid
> commit [1691d92
](https://github.com/Cactex/lab0-c/commit/1691d925d8ea9ab32170fe98bf364caa2a33e610)

若 `head` 為 `NULL` 或 佇列為空則回傳 `false`
實做方法為兩個節點，一個向前 traverse，另外一個向後，直到兩個節點相遇

**討論**
另一種作法為兩節點同方向 traverse ，其中一個節點速度為另一個兩倍，直到節點相遇

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;
    struct list_head *nprev = head->prev;
    struct list_head *nnext = head->next;
    while ((nprev != nnext) && (nnext->next != nprev)) {
        nprev = nprev->prev;
        nnext = nnext->next;
    }
    list_del(nprev);
    q_release_element(list_entry(nprev, element_t, list));
    return true;
}

## q_delete_dup
> commit [9ae6e83
](https://github.com/Cactex/lab0-c/commit/9ae6e83a58e5669e90faf7eb2b6e8dce2be1018a)

前提預設為 sorted list

bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head || list_empty(head))
        return false;
    struct list_head *node, *safe;
    bool isdup = 0;
    list_for_each_safe (node, safe, head) {
        element_t *curr = list_entry(node, element_t, list);
        element_t *next = list_entry(safe, element_t, list);
        if(strcmp(curr->value, next->value) == 0){
            list_del(&curr->list);
            q_release_element(curr);
            isdup = true;
            continue;
        }
        if(isdup){
            list_del(&tmp->list);
            q_release_element(curr);
            isdup = false;
        }
    }
    return true;
}

實做以上程式碼遇到 `0xdeadbeef`
使用Valgrind工具發現問題在 `strcmp` ，以上程式碼會比較現在節點和下個節點的value，導致訪問到 `head` 節點的 value

 $ valgrind -q --leak-check=full ./qtest
...
cmd> ih 4
l = [4 3 2 2]
cmd> dedup
==104311== Invalid read of size 1
==104311==    at 0x4850367: strcmp (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==104311==    by 0x110141: q_delete_dup (queue.c:142)
==104311==    by 0x10C3B6: do_dedup (qtest.c:467)
==104311==    by 0x10E76D: interpret_cmda (console.c:181)
==104311==    by 0x10ED32: interpret_cmd (console.c:201)
==104311==    by 0x10F81C: run_console (console.c:659)
==104311==    by 0x10DB5C: main (qtest.c:1444)
==104311==  Address 0xdeadbeef is not stack'd, malloc'd or (recently) free'd
==104311== 
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer==104311== 2 bytes in 1 blocks are still reachable in loss record 1 of 52

補上就沒問題了

+if(safe != head){
            element_t *next = list_entry(safe, element_t, list);
            if(strcmp(curr->value, next->value) == 0){
                list_del(&curr->list);
                q_release_element(curr);
                isdup = true;
                continue;
            }
+        }
 }

## q_swap
> commit [b29d3c2
](https://github.com/Cactex/lab0-c/commit/b29d3c26bdfee783714c774b522ee84f3c38a680)

目標是將佇列中每對相鄰的節點交換，可以想像成把第一個節點放到第二個節點後面

**討論**
另一種作法為兩節點同方向 traverse ，其中一個節點速度為另一個兩倍，直到節點相遇

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;
    struct list_head *nprev = head->prev;
    struct list_head *nnext = head->next;
    while ((nprev != nnext) && (nnext->next != nprev)) {
        nprev = nprev->prev;
        nnext = nnext->next;
    }
    list_del(nprev);
    q_release_element(list_entry(nprev, element_t, list));
    return true;
}

## q_reverse
> commit [1683868
](https://github.com/Cactex/lab0-c/commit/168386826d282417bf7bdc24ce87f627bd7ff913)

目標是將佇列每個元素的順序翻轉，如果佇列為空或 `NULL` 不需要調整。
並且不能 allocate 或 free 任何佇列元素，僅調整原有元素之順序。

想法為將最後面的元素一直向前放

void q_reverse(struct list_head *head)
{
    for (struct list_head *last = head->prev, *front = head->next,
                          *current = head;
         last != front; last = head->prev, current = current->next) {
        head->prev = last->prev;
        last->prev->next = head;

        current->next->prev = last;
        last->next = current->next;
        last->prev = current;
        current->next = last;
    }
}

## q_reverseK
> commit [1683868
](https://github.com/Cactex/lab0-c/commit/168386826d282417bf7bdc24ce87f627bd7ff913)

和q_reverse接近，但翻轉的大小為 k ，若佇列大小不足 k 則不須翻轉。
佇列為空或長度為1或 k 的大小為則不需要作任何動作。

若佇列長度和 k 大小一致，則和 `q_reverse` 相同。
一般 case 的實做則可以透過 `list_cut_position` 去切分佇列，將其翻轉後再接回原本佇列。

void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if (!head || list_empty(head) || k == 1 || list_is_singular(head))
        return;
    int length = q_size(head);
    if (length == k)
        q_reverse(head);
    int counter = 0;
    LIST_HEAD(tmp);
    LIST_HEAD(reverse);
    struct list_head *node, *safe;
    list_for_each_safe (node, safe, head) {
        if (++counter == k) {
            list_cut_position(&tmp, head, node);
            q_reverse(&tmp);
            list_splice_tail_init(&tmp, &reverse);
            counter = 0;
        }
    }
    list_splice_init(&reverse, head);
}

## q_sort
> commit [14be610
](https://github.com/Cactex/lab0-c/commit/14be610687ae1b6e50847ae583255bb1745b7a94)

用 top down 的方法去實做 q_sort

struct list_head *merge_sort(struct list_head *head)
{
    if (!head || !head->next)
        return head;
    struct list_head *slow = head;
    for (const struct list_head *fast = head->next; fast && fast->next;
         fast = fast->next->next)
        slow = slow->next;
    struct list_head *mid = slow->next;
    // remove mid and its prev link
    slow->next = NULL;
    struct list_head *left = merge_sort(head), *right = merge_sort(mid);
    return mergeTwoLists(left, right);
}

/* Sort elements of queue in ascending/descending order */
void q_sort(struct list_head *head, bool descend)
{
    if (!head || list_empty(head))
        return;

    if (list_is_singular(head))
        return;

    head->prev->next = NULL;
    head->next = merge_sort(head->next);

    // reconnect list
    struct list_head *c = head, *n = head->next;
    while (n) {
        n->prev = c;
        c = n;
        n = n->next;
    }
    c->next = head;
    head->prev = c;


    if (descend)
        q_reverse(head);
    return;
}

## q_ascend
> commit [1f5fb10
](https://github.com/Cactex/lab0-c/commit/1f5fb100afd20766ee9c7c03a8a0c76cea8cbac7)

透過移除佇列元素讓佇列達到升冪排列(可以有相同值)，空佇列和佇列長度為1不需要更改

將 `list.h` 中的 `list_for_each_entry_safe` 改寫，以達到逆向走訪的效果。

int q_ascend(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;
    if (list_is_singular(head))
        return 1;
    element_t *safe, *node;
    char const *tmpch = (list_entry(head->prev, element_t, list))->value;
    for (node = list_entry((head)->prev, typeof(*node), list),
        safe = list_entry(node->list.prev, typeof(*node), list);
         &node->list != (head);
         node = safe, safe = list_entry(safe->list.prev, typeof(*node), list)) {
        if (strcmp(node->value, tmpch) > 0) {
            list_del(&node->list);
            continue;
        }
        tmpch = node->value;
    }
    return q_size(head);
}

## q_descend
> commit [1f5fb10
](https://github.com/Cactex/lab0-c/commit/1f5fb100afd20766ee9c7c03a8a0c76cea8cbac7)

透過移除佇列元素讓佇列達到降冪排列(可以有相同值)，空佇列和佇列長度為1不需要更改

內容和q_ascend差不多，只是變成降冪排列

int q_descend(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;
    if (list_is_singular(head))
        return 1;
    element_t *safe, *node;
    char const *tmpch = (list_entry(head->prev, element_t, list))->value;
    for (node = list_entry((head)->prev, typeof(*node), list),
        safe = list_entry(node->list.prev, typeof(*node), list);
         &node->list != (head);
         node = safe, safe = list_entry(safe->list.prev, typeof(*node), list)) {
        if (strcmp(node->value, tmpch) < 0) {
            list_del(&node->list);
            continue;
        }
        tmpch = node->value;
    }
    return q_size(head);
}

## q_merge
> commit [b2aabc4](https://github.com/Cactex/lab0-c/commit/b2aabc4e19c23602158245d9a6c627e117aa678f)

> commit [d76a488](https://github.com/Cactex/lab0-c/commit/d76a488c70bbfa64402ae80cfab83f23af401072)

將 queue 中多個 sorted lists 合併

需要注意的是一開始給的佇列中每個元素都包含一個 queue ，需要用 `list_entry` 以找到整個結構體中的 sorted list。

另外有寫 `merge_2_queue` 去完成

int q_merge(struct list_head *head, bool descend)
{
    // https://leetcode.com/problems/merge-k-sorted-lists/
    if (!head || list_empty(head))
        return 0;
    queue_contex_t *list1 = list_entry(head->next, queue_contex_t, chain);
    struct list_head *chain_queue = head->next->next;
    if (chain_queue == head)
        return list1->size;
    int count = list1->size;
    for (; chain_queue != head; chain_queue = chain_queue->next) {
        queue_contex_t *merge_list =
            list_entry(chain_queue, queue_contex_t, chain);
        if (!merge_list->q || list_empty(merge_list->q)) {
            continue;
        }
        count = count + merge_list->size;
        merge_2_queue(list1->q, merge_list->q, descend);
    }
    return count;
}

# git rebase

$ git rebase upstream/master
自動合併 queue.c11)
衝突（內容）：合併衝突於 queue.c
error: 不能套用 b2aabc4... Implement q_merge and fixed bugs
提示：Resolve all conflicts manually, mark them as resolved with
提示："git add/rm <conflicted_files>", then run "git rebase --continue".
提示：You can instead skip this commit: run "git rebase --skip".
提示：To abort and get back to the state before "git rebase", run "git rebase --abort".
不能套用 b2aabc4... Implement q_merge and fixed bugs

在手動解決衝突後

$ git add queue.c
$