Try   HackMD

2025q1 Homework1 (lab0)

contributed by < Denny0097 >

作業書寫規範:

  • 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
  • 文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
  • 共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
  • 不要在筆記內加入 [TOC] : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
  • 不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，用於評分和接受同儕的檢閱
  • 當在筆記中貼入程式碼時，避免非必要的行號，也就是該手動將 c= 或 cpp= 變更為 c 或 cpp。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「你所不知道的 C 語言: linked list 和非連續記憶體」裡頭程式碼展現的方式
  • HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」
  • 留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」及「詞彙對照表」
  • 不要濫用 :::info, :::success, :::warning 等標示，儘量用清晰的文字書寫。:::danger 則僅限授課教師作為批注使用
  • 避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景
  • 在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","。注意書名號的使用，即 〈 和 〉，非「小於」和「大於」符號
  • 避免使用不必要的 emoji 字元

開發環境

$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
Copyright (C) 2023 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):                   16
  On-line CPU(s) list:    0-15
Vendor ID:                GenuineIntel
  Model name:             Intel(R) Core(TM) i7-10700 CPU @ 2.90GHz
    CPU family:           6
    Model:                165
    Thread(s) per core:   2
    Core(s) per socket:   8
    Socket(s):            1
    Stepping:             5
    BogoMIPS:             5808.02
    Flags:                fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clfl
                          ush mmx fxsr sse sse2 ss ht syscall nx pdpe1gb rdtscp lm constant_tsc arch_p
                          erfmon rep_good nopl xtopology cpuid pni pclmulqdq ssse3 fma cx16 pdcm pcid
                          sse4_1 sse4_2 movbe popcnt aes xsave avx f16c rdrand hypervisor lahf_lm abm
                          3dnowprefetch invpcid_single ssbd ibrs ibpb stibp ibrs_enhanced fsgsbase bmi
                          1 avx2 smep bmi2 erms invpcid rdseed adx smap clflushopt xsaveopt xsavec xge
                          tbv1 xsaves md_clear flush_l1d arch_capabilities
Virtualization features:
  Hypervisor vendor:      Microsoft
  Virtualization type:    full
Caches (sum of all):
  L1d:                    256 KiB (8 instances)
  L1i:                    256 KiB (8 instances)
  L2:                     2 MiB (8 instances)
  L3:                     16 MiB (1 instance)
Vulnerabilities:
  Gather data sampling:   Unknown: Dependent on hypervisor status
  Itlb multihit:          KVM: Mitigation: VMX unsupported
  L1tf:                   Not affected
  Mds:                    Not affected
  Meltdown:               Not affected
  Mmio stale data:        Vulnerable: Clear CPU buffers attempted, no microcode; SMT Host state unknow
                          n
  Reg file data sampling: Not affected
  Retbleed:               Mitigation; Enhanced IBRS
  Spec rstack overflow:   Not affected
  Spec store bypass:      Mitigation; Speculative Store Bypass disabled via prctl and seccomp
  Spectre v1:             Mitigation; usercopy/swapgs barriers and __user pointer sanitization
  Spectre v2:             Mitigation; Enhanced / Automatic IBRS; IBPB conditional; RSB filling; PBRSB-
                          eIBRS SW sequence; BHI SW loop, KVM SW loop
  Srbds:                  Unknown: Dependent on hypervisor status
  Tsx async abort:        Not affected

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

q_new

struct list_head *q_new()
{
    // struct list_head *head = malloc(sizeof(struct list_head));
    // if (head)
    //     INIT_LIST_HEAD(head);
    // return head;
    element_t *node = malloc(sizeof(element_t));
    if (node)
        INIT_LIST_HEAD(&(node->list));
    
    return &node->list;
}

->

    struct list_head *head = malloc(sizeof(struct list_head));
    if (head)
        INIT_LIST_HEAD(head);
    return head;

q_free

/* Free all storage used by queue */
void q_free(struct list_head *head)
{
    struct list_head *del = NULL;
    for(struct list_head *cur = head->next; cur!=head; cur=cur->next)
    {
        if(cur)
            del = cur;
        free(list_entry(del, element_t, list));
    }
    if (head)
        free(list_entry(head, element_t, list));
}

->

    if (!head)
        return;
    struct list_head *cur, *safe;
    list_for_each_safe(cur, safe, head) {
        list_del(cur);
        q_release_element(list_entry(cur, element_t, list));
    }
    free(head);

->

if(!head)
    return;
element_t *cur, *safe;
list_for_each_entry_safe (cur, safe, head, list) {
    list_del(&cur->list);
    q_release_element(cur);
}
free(head);

q_insert_head

/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
    if(head){
        struct list_head *new = q_new();
        char *newV = list_entry(new, element_t, value);
        newV = s;
        head->prev = new;
        new->next = head;
        return true;
    }
    return false;
}

q_insert

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *node = malloc(sizeof(element_t));

    node->value = malloc((strlen(s) + 1) * sizeof(char));
    strncpy(node->value, s, strlen(s) + 1);

    list_add(&node->list, head);

    return true;
}

​​​​# Test of malloc failure on insert_head
​​​​Segmentation fault occurred.  You dereferenced a NULL or invalid pointer---     trace-11-malloc 0/6
​​​​+++ TESTING trace trace-12-malloc:
​​​​# Test of malloc failure on insert_tail
​​​​Segmentation fault occurred.  You dereferenced a NULL or invalid pointer---     trace-12-malloc 0/6
​​​​+++ TESTING trace trace-13-malloc:

q_remove_head

/* Insert an element at head of queue */
if (!head || list_empty(head))
    return NULL;
element_t *pos = list_entry(head->next, element_t, list);
strncpy(sp, pos->value, bufsize);
list_del_init(&pos->list);
return NULL;

->

if (!head || list_empty(head))
    return NULL;
element_t *pos = list_entry(head->next, element_t, list);

if (sp && bufsize)
{
    strncpy(sp, pos->value, bufsize - 1);
    sp[bufsize - 1] = '\0';
}

list_del(&pos->list);
return pos;

​​​​# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
​​​​ERROR: Probably not constant time or wrong implementation
​​​​Testing insert_head...(7/10)
​​​​ERROR: Probably not constant time or wrong implementation
​​​​Probably constant time
​​​​ERROR: Probably not constant time or wrong implementation
​​​​---     trace-17-complexity     0/5
​​​​---     TOTAL           23/100

q_delete_mid

if (!head||list_empty(head))
    return false;
int size = q_size(head);

struct list_head *del = head->next;
int pos = 1;
while (pos < size/2)
{
    del = del->next;
    pos ++;
}
list_del(del);
q_release_element(list_entry(del, element_t, list));
return true;

->

if (!head || list_empty(head))
    return false;

struct list_head *forward = head->next, *backward = head->prev;
while (forward != backward && forward->next != backward) {
    forward = forward->next;
    backward = backward->prev;
}
list_del(forward);
q_release_element(list_entry(forward, element_t, list));
return true;

q_delete_dup

bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head)
        return false;

    bool del = false;
    struct list_head *cur, *next;

    list_for_each_safe (cur, next, head) {
        element_t *entry = list_entry(cur, element_t, list);
        if (next != head &&
            !strcmp(entry->value, list_entry(next, element_t, list)->value)) {
            list_del(cur);
            q_release_element(entry);
            del = true;
        } else if (del) {
            list_del(cur);
            q_release_element(entry);
            del = false;
        }
    }
    return true;
}

q_swap

Leetcode 24

if (!head||!head->next)
    return head;
struct ListNode *newHead = head->next;

struct ListNode *prev = NULL;
struct ListNode *cur = head;

while (cur&&cur->next)
{
    struct ListNode *pair = cur->next;
    cur->next = pair->next;
    pair->next = cur;
    if (prev)
        prev->next = pair;

    prev = cur;
    cur = cur->next;
}
return newHead;

->

if (!head || !head->next)
    return;

struct list_head *prev = head;
struct list_head *cur = head->next;

head->next = head->next->next;

do {
    struct list_head *pair = cur->next;
    cur->next = pair->next;
    pair->next->prev = cur;

    pair->next = cur;
    cur->prev = pair;

    prev->next = pair;
    pair->prev = prev;

    prev = cur;
    cur = cur->next;
} while (cur != head && cur != head->prev);

q_reverse

pointer ver:

head = head -> prev;
struct list_head *cur = NULL, *temp = NULL;

for (cur = head; cur != head -> prev ; cur = cur->next)
{
    temp = cur->next;
    cur->next  = cur->prev;
    cur->prev = temp;
}

temp = cur->next;
cur->next  = cur->prev;
cur->prev = temp;

error: head just a list but head->prev in a entry
->

 // X head = head -> prev;

Indirect pointer ver:

q_reverseK

void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if (!head || list_empty(head) || k < 2)
        return;
    struct list_head *cur = head ->next;

    while (cur != head)
    {   
        struct list_head *front = cur, *tail = NULL, *prev = NULL;
        int count = 0;
        while (count < k && cur != head)
        {
            cur = cur->next;
            count ++;
        }
        if (count < k)
            return;

        tail = cur->prev;
        prev = front->prev;
        front->prev = tail;
        tail->next = front;
        q_reverse(front);

        prev->next = tail;
        tail->prev = prev;
        front->next = cur;
        cur->prev = front;
    }
}

q_ascend

struct list_head *prevBig = head;
struct list_head *currBig = head->next;

for (struct list_head *cur = head->next; cur != head; cur = cur->next)
{
    if (list_entry(currBig, element_t, list)->value
        < list_entry(cur, element_t, list)->value)
    {
        currBig = cur;

        struct list_head *pos = currBig->prev;
        while (pos != prevBig)
        {
            struct list_head *del = pos;
            pos = pos->next;
            list_del(del);
        }
        prevBig = currBig;
    }
}

return 0;

error: 因為currBig在遇到更小的情況不會更新，導致ㄏcurrBig沒有達到預期作用

l = [2 3 1]
cmd> ascend
l = [ ... ]
ERROR:  Queue has more than 0 elements
cmd> ih 2
l = [2 ... ]
ERROR:  Queue has more than 1 elements

deal: 改成current Min，遇到更大的就更新改成current Min並del小的，遇到更小的就單純更新current Min
->

if (!head || list_empty(head))
    return 0;

struct list_head *currMin = head->next;
int elementNum = q_size(head);

for (struct list_head *cur = currMin->next; cur != head; cur = cur->next)
{
    if (list_entry(currMin, element_t, list)->value
        < list_entry(cur, element_t, list)->value)
    {
        list_del(currMin);
        q_release_element(list_entry(currMin, element_t, list));
        elementNum --;
    }
    currMin = cur;
}
return elementNum;

l = [c d b a]
cmd> ascend
ERROR: At least one node violated the ordering rule

->誤會題意，我以為是到比左邊小的數字時左邊的數字就不會再被刪除，結果是要保證右邊比左邊大，看錯的有點離譜
改成用prev去找，比較小就del，確保ascend

if (!head || list_empty(head))
    return 0;

int elementNum = q_size(head);

char *min = list_entry(head->prev, element_t, list)->value;
struct list_head *cur = head->prev;

while (cur != head) {
    if (strcmp(min, list_entry(cur, element_t, list)->value) > 0) {
        struct list_head *del = cur;
        cur = cur->prev;
        element_t *entry = list_entry(del, element_t, list);
        list_del(del);
        q_release_element(entry);
        elementNum--;
    }
    else {
        min = list_entry(cur, element_t, list)->value;
        cur = cur->prev;
    }
}
return elementNum;

infineted loop Error

l = [10 9 9 10]
cmd> ascend
ERROR: At least one node violated the ordering rule
l = [9 9 10]
cmd> ascend
ERROR: At least one node violated the ordering rule
l = [9 9 10]
Error limit exceeded.  Stopping command execution
cmd> ascend
cmd>
cmd> quit
cmd> free
cmd>
cmd>
cmd>
cmd> free
cmd> quit
cmd>
cmd>

strcmp使用錯誤
->

(strcmp(min, list_entry(cur, element_t, list)->value) < 0)

q_sort

一開始想要先把head切掉在去處理分開的queue，因為遇到malloc error，所以用多一個function merge_sort()，但不太直覺，遇到很多困難。

    // cut left and right as two independent qeueu

    // sort
    merge_sort(left, right, descend);

    // connect to head

merge_sort

if (q_size(left)>1) {

    // merge_sort(head, false);
    // merge_sort(right, false);
    // merge(head, right, descend);
}

merge

if(descend) {
    while(curOfLeft != right) {
        if(strcmp(list_entry(curOfLeft, element_t, list)->value,
                list_entry(curOfRight, element_t, list)->value) >= 0) {
            list_add_tail(left, curOfLeft);
            curOfLeft = curOfLeft->next;
        }else {
            list_add_tail(left, curOfRight);
            curOfRight = curOfRight->next;
        }
    }
}
else {
    while(curOfLeft != right) {
        if(strcmp(list_entry(curOfLeft, element_t, list)->value,
                list_entry(curOfRight, element_t, list)->value) <= 0) {
            list_add_tail(left, curOfLeft);
            curOfLeft = curOfLeft->next;
        }else {
            list_add_tail(left, curOfRight);
            curOfRight = curOfRight->next;
        }
    }
}

改成利用struct list_head left來分割queue，可以避開不能malloc的問題，有點太習慣使用pointer差點忘記原本的結構就是可以宣告的。

merge

    struct list_head *curOfLeft = left->next;
    struct list_head *curOfRight = head->next;
    struct list_head *nextOps = NULL;
    struct list_head result;

    INIT_LIST_HEAD(&result);

    while (curOfLeft != left && curOfRight != head && descend) {
        if (strcmp(list_entry(curOfLeft, element_t, list)->value,
                   list_entry(curOfRight, element_t, list)->value) < 0) {
            nextOps = curOfRight->next;
            list_move_tail(curOfRight, &result);
            curOfRight = nextOps;
        } else {
            nextOps = curOfLeft->next;
            list_move_tail(curOfLeft, &result);
            curOfLeft = nextOps;
        }
    }
    while (curOfLeft != left && curOfRight != head && !descend) {
        if (strcmp(list_entry(curOfLeft, element_t, list)->value,
                   list_entry(curOfRight, element_t, list)->value) > 0) {
            nextOps = curOfRight->next;
            list_move_tail(curOfRight, &result);
            curOfRight = nextOps;
        } else {
            nextOps = curOfLeft->next;
            list_move_tail(curOfLeft, &result);
            curOfLeft = nextOps;
        }
    }

    if (list_empty(left)) {
        // Append remaining nodes from left
        list_splice_tail_init(head, &result);
    } else {
        // Append remaining nodes from right
        list_splice_tail_init(left, &result);
    }
    list_splice_tail_init(&result, head);

sort

    if (!head || list_empty(head) || head->next->next == head)
        return;

    // find mid
    struct list_head *forward = head->next, *backward = head->prev;
    while (forward != backward && forward->next != backward) {
        forward = forward->next;
        backward = backward->prev;
    }
    struct list_head left;
    struct list_head *mid = forward;

    list_cut_position(&left, head, mid);
    q_sort(&left, descend);
    q_sort(head, descend);
    merge(head, &left, descend);

簡化merge的判斷，可以讓code更簡潔。

merge

    if (!head || list_empty(head))
        return 0;
    if (list_is_singular(head))
        return q_size(head);

    queue_contex_t *first = list_entry(head->next, queue_contex_t, chain);
    struct list_head *node = head->next->next;

    while (node != head) {
        queue_contex_t *cur = list_entry(node, queue_contex_t, chain);
        if (cur->q) {
            merge(first->q, cur->q, descend);
        }
        node = node->next;
    }
    return first->size;

研讀 lib/list_sort.c

Last changed by 
 
Denny0097
0
57

Read more

2025q1 Homework2 (quiz1+2)

contributed by &lt; Denny0097 &gt;

Mar 15, 2025
linux2025-ideas

2025q1 Homework1 (ideas)contributed by &lt; davidshiao55 &gt;{%hackmd NrmQUGbRQWemgwPfhzXj6g %}

Mar 8, 2025
Read more from Denny0097
Published on HackMD