Try   HackMD

2023q1 Homework1 (lab0)

contributed by < as200188 >

開發環境

作業系統: ubuntu 22.04
硬體配置

$ 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-7700 CPU @ 3.60GHz
    CPU family:          6
    Model:               158
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            9
    CPU max MHz:         4200.0000
    CPU min MHz:         800.0000
    BogoMIPS:            7200.00
    Flags:               fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mc
                         a cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss 
                         ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc art
                          arch_perfmon pebs bts rep_good nopl xtopology nonstop_
                         tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cp
                         l vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid ss
                         e4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes 
                         xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_f
                         ault epb invpcid_single pti ssbd ibrs ibpb stibp tpr_sh
                         adow vnmi flexpriority ept vpid ept_ad fsgsbase tsc_adj
                         ust bmi1 avx2 smep bmi2 erms invpcid mpx rdseed adx sma
                         p clflushopt intel_pt xsaveopt xsavec xgetbv1 xsaves dt
                         herm ida arat pln pts hwp hwp_notify hwp_act_window hwp
                         _epp md_clear flush_l1d arch_capabilities
Virtualization features: 
  Virtualization:        VT-x
Caches (sum of all):     
  L1d:                   128 KiB (4 instances)
  L1i:                   128 KiB (4 instances)
  L2:                    1 MiB (4 instances)
  L3:                    8 MiB (1 instance)
NUMA:                    
  NUMA node(s):          1
  NUMA node0 CPU(s):     0-7
Vulnerabilities:         
  Itlb multihit:         KVM: Mitigation: VMX disabled
  L1tf:                  Mitigation; PTE Inversion; VMX conditional cache flushe
                         s, SMT vulnerable
  Mds:                   Mitigation; Clear CPU buffers; SMT vulnerable
  Meltdown:              Mitigation; PTI
  Mmio stale data:       Mitigation; Clear CPU buffers; SMT vulnerable
  Retbleed:              Mitigation; IBRS
  Spec store bypass:     Mitigation; Speculative Store Bypass disabled via prctl
  Spectre v1:            Mitigation; usercopy/swapgs barriers and __user pointer
                          sanitization
  Spectre v2:            Mitigation; IBRS, IBPB conditional, RSB filling, PBRSB-
                         eIBRS Not affected
  Srbds:                 Mitigation; Microcode
  Tsx async abort:       Mitigation; TSX disabled

開發過程

設定開發環境

安裝及設定 git

參考 Git 教學和 GitHub 設定指引

複製 lab0-c 專案

  1. Fork lab0-c 參考官方文檔 Fork 的方式
  2. 將專案複製到本地端
$ git clone https://github.com/as200188/lab0-c.git
  1. 設定成SSH連線 參考 git push without password
$ git remote set-url origin git@github.com:as200188/lab0-c.git
  1. 確認輸出
$ git remote -v
origin	git@github.com:as200188/lab0-c.git (fetch)
origin	git@github.com:as200188/lab0-c.git (push)

安裝 make 套件

  1. 安裝
$ sudo apt-get install make
  1. 確認安裝版本
$ make -version
GNU Make 4.3
Built for x86_64-pc-linux-gnu
Copyright (C) 1988-2020 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.

安裝 curl 套件

  1. 安裝
$ sudo apt-get install curl
  1. 測試
$ curl -I https://www.gnu.org/
HTTP/1.1 200 OK
Date: Tue, 21 Feb 2023 09:29:21 GMT
Server: Apache/2.4.29
Content-Location: home.html
Vary: negotiate,accept-language,Accept-Encoding
TCN: choice
Strict-Transport-Security: max-age=63072000
X-Frame-Options: sameorigin
X-Content-Type-Options: nosniff
Access-Control-Allow-Origin: (null)
Accept-Ranges: bytes
Cache-Control: max-age=0
Expires: Tue, 21 Feb 2023 09:29:21 GMT
Content-Type: text/html
Content-Language: en

安裝 gcc 套件

  1. 安裝
$ sudo apt-get install gcc
  1. 確認版本
$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.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.

測試 lab0-c 專案

編譯

~/linux2023/lab0-c$ make
  CC	qtest.o
  CC	report.o
  CC	console.o
  CC	harness.o
  CC	queue.o
  CC	random.o
  CC	dudect/constant.o
  CC	dudect/fixture.o
  CC	dudect/ttest.o
  CC	shannon_entropy.o
  CC	linenoise.o
  CC	web.o
  LD	qtest

清除編譯產生的檔案

~/linux2023/lab0-c$ make clean 
rm -f qtest.o report.o console.o harness.o queue.o random.o dudect/constant.o dudect/fixture.o dudect/ttest.o shannon_entropy.o linenoise.o web.o .qtest.o.d .report.o.d .console.o.d .harness.o.d .queue.o.d .random.o.d .dudect/constant.o.d .dudect/fixture.o.d .dudect/ttest.o.d .shannon_entropy.o.d .linenoise.o.d .web.o.d *~ qtest /tmp/qtest.*
rm -rf .dudect
rm -rf *.dSYM
(cd traces; rm -f *~)

實做 queue 相關函式

實做所使用的資料結構

參考 linked list
利用 list.h 建立雙向 linked list

Linked list element

想法: 節點嵌入結構體 list_head，若要取得節點，則利用 container_of 來取得節點。

typedef struct {
    char *value;
    struct list_head list;
} element_t;

Queue 結構

typedef struct {
    int size;
    struct list_head head;
} queue_t;

建立 element 並初始化

想法: 用 malloc() 取得節點空間，並且初始化，回傳該節點位址。

/* Initial element */
static inline void INIT_ELEMENT(element_t *e)
{
    e->value = NULL;
    INIT_LIST_HEAD(&e->list);
}

/* Create element and initial it */
struct element_t *element_new()
{
    element_t *e = malloc(sizeof(element_t));
    INIT_ELEMENT(e);
    return e;
}

未考慮到 malloc() 可能會回傳 NULL，因此將程式碼修正成:

static inline void INIT_ELEMENT(element_t *e)
{
    if (e == NULL)
        return;

    e->value = NULL;
    INIT_LIST_HEAD(&e->list);
}

q_new

想法: 建 empty queue，並且做初始化。

struct list_head *q_new()
{
    /* Create queue and initial it */
    queue_t *q = malloc(sizeof(queue_t));

    q->size = 0;
    INIT_LIST_HEAD(&q->head);
    
    return &q->head;
}

未考慮到 malloc() 可能會回傳 NULL，因此將程式碼修正成:

/* Initial queue */
static inline void INIT_QUEUE(queue_t *q)
{
    if (q == NULL)
        return;

    q->size = 0;
    INIT_LIST_HEAD(&q->head);
}

/* Create an empty queue and initial it */
struct list_head *q_new()
{
    /* Create queue and initial it */
    queue_t *q = malloc(sizeof(queue_t));
    INIT_QUEUE(q);

    return (q != NULL) ? &q->head : NULL;
}

q_insert_head

想法: 建立新節點，利用 list_add 加到第一個節點。
考慮到傳入空指標和極長字串會導致程式出錯，利用計算字串長度再加一(放空字元)，作為放字串的空間，從靜態改成動態，避免極長字串導致程式出錯，將程式碼修改成:

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

    char *str = malloc(strlen(s)+1);
    element_t *e = element_new();
    queue_t *q = container_of(head, queue_t, head);

    strcpy(str, s);
    e->s = str;
    list_add(&e->list, head);
    q->size += 1;

    return true;
}

發現字串動態配置空間和複製字串可由 strdup 一次做完(參考 willwillhi)，可將程式碼經簡化，將程式碼改成:

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

    char *str = strdup(s);
    element_t *e = element_new();
    queue_t *q = container_of(head, queue_t, head);

    e->value = str;
    list_add(&e->list, head);
    q->size += 1;

    return true;
}

未考慮到 malloc 失敗後，未將已配置空間釋放，導致 memory leak。修正成:

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

    char *str = strdup(s);
    if (str == NULL)
        goto malloc_failed;
    element_t *e = element_new();
    if (e == NULL)
        goto malloc_failed;

    queue_t *q = container_of(head, queue_t, head);

    e->value = str;
    list_add(&e->list, head);
    q->size += 1;

    return true;

malloc_failed:
    if (str)
        free(str);
    if (e)
        free(e);
    return false;
}

q_insert_tail

bool q_insert_tail(struct list_head *head, char *s)
{
    if (head == NULL || s == NULL)
        return false;

    char *str = strdup(s);
    if (str == NULL)
        goto malloc_failed;
    element_t *e = element_new();
    if (e == NULL)
        goto malloc_failed;

    queue_t *q = container_of(head, queue_t, head);

    e->value = str;
    list_add_tail(&e->list, head);
    q->size += 1;

    return true;

malloc_failed:
    if (str)
        free(str);
    if (e)
        free(e);
    return false;
}

q_size

想法: 有一種做法是計算節點數量，然後回傳答案，但該方式的時間複雜度為

O(N)，我希望讓時間複雜度為
O(1)，所以我會有一個 queue 結構，裡面會有 size 和 head 成員，並且利用 container_of 來取得該 queue 結構。

int q_size(struct list_head *head)
{
    if (head == NULL)
        return -1;

    queue_t *q = container_of(head, queue_t, head);
    return q->size;
}

q_remove_head

想法: 若能移去節點，需要將字串複製到 sp, 並將 q->size 減一。

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (head == NULL || sp == NULL || q_size() == 0)
        return NULL;

    element_t *e = list_first_entry(head, element_t, list);
    queue_t *q = container_of(head, queue_t, head);

    strncpy(sp, e->value, bufsize-1);
    sp[bufsize-1] = '\0';
    list_del(&e->list);
    q->size -= 1;

    return e;
}

q_remove_head

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (head == NULL || sp == NULL || q_size() == 0)
        return NULL;

    element_t *e = list_last_entry(head, element_t, list);
    queue_t *q = container_of(head, queue_t, head);

    strncpy(sp, e->value, bufsize-1);
    sp[bufsize-1] = '\0';
    list_del(&e->list);
    q->size -= 1;

    return e;
}

q_free

想法: 利用 list_for_each_safe 逐一走訪 list 上的節點，利用 container_of 取得 element 並釋放該 element 所使用的空間，走訪完後，將 queue 所使用的空間釋放。

void q_free(struct list_head *head)
{
    if (head == NULL)
        return;

    queue_t *q = container_of(head, queue_t, head);
    struct list_head *iter = NULL, *next = NULL;
    element_t *e = NULL;

    list_for_each_safe(iter, next, head){
        e = container_of(iter, element_t, list);
        free(e->value);
        e->value = NULL;
        list_del_init(iter);
        free(e);
    }

    free(q);
}

由於刪除 element 這段程式經常重複，所以將該段程式寫成 function，修改成:

/* Delete element and update list and queue */
static void element_del(element_t *e, struct list_head *head)
{
    if (e == NULL || head == NULL)
        return;

    queue_t *q = container_of(head, queue_t, head);

    free(e->value);
    e->value = NULL;
    list_del_init(&e->list);
    free(e);
    q->size -= 1;
}


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

    queue_t *q = container_of(head, queue_t, head);
    struct list_head *iter = NULL, *next = NULL;
    element_t *e = NULL;

    list_for_each_safe (iter, next, head) {
        e = container_of(iter, element_t, list);
        element_del(e, head);
    }

    free(q);
}

q_delete_mid

想法: 有想到三種做法，第一種是逐一走訪，計算節點數，再去刪中間。第二種是用快慢指標來去找中間。第三種做法是從頭尾逐一走訪來找中間，採用第三種做法，當節點數是奇數的時候，front 等於 end時，front 和 end 都是中間節點，節點數為偶數的時候，front->next 等於 end時，end 為中間節點，找到中間節點後，將其刪除。

/* Delete the middle node in queue */
bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    if (head == NULL || q_size(head) == 0)
        return false;

    struct list_head *front = head->next, *end = head->prev;
    element_t *e = NULL;

    while(front != end && front->next != end){
        front = front->next;
        end = end->prev;
    }

    e = container_of(end, element_t, list);
    element_del(e, head);

    return true;
}

q_reverse

想法: 有想到兩種做法，一種是不改變節點 list 指向的位址，藉由改變 value 來做到 reverse，好處是 element 只有 value 要改變時，需要交換的值很少，效率佳，可從頭尾指標做 swap，得到結果。此處使用第二種做法，改變 list 指向的位址，逐一走訪節點，將節點放到尾巴，得到結果。

void q_reverse(struct list_head *head)
{
    if (head == NULL || list_empty(head) || list_is_singular(head))
        return;

    struct list_head *old_front = head->next, *old_end = head->prev;
    struct list_head *iter = NULL, *next = NULL, *tmp = NULL;

    list_for_each_safe (iter, next, head) {
        tmp = iter->prev;
        iter->prev = iter->next;
        iter->next = tmp;
    }

    head->next = old_end;
    head->prev = old_front;
}

q_swap

想法: 兩個節點以上才需要 swap，在做 swap 時，要將前一個和下一個和下兩個的節點，指標關係需要做更新，而當 swap 時，是和最後一個節點交換，需要更新 head 的前一個節點。

void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (head == NULL || list_empty(head) || list_is_singular(head))
        return;

    struct list_head *iter = NULL, *next = NULL, *next_next = NULL,
                     *prev = NULL;

    for (iter = head->next, next_next = iter->next->next;
         iter != head && iter != head->prev;
         iter = next_next, next_next = iter->next->next) {
        prev = iter->prev;
        next = iter->next;

        iter->next = next_next;
        next_next->prev = iter;
        prev->next = next;
        next->prev = prev;
        next->next = iter;
        iter->prev = next;

        if (head->prev == next)
            head->prev = iter;
    }
}

compare

int compare(const void *a, const void *b)
{
    const struct list_head *a_list = a;
    const struct list_head *b_list = b;
    element_t *a_e = container_of(a_list, element_t, list);
    element_t *b_e = container_of(b_list, element_t, list);
    return strcmp(a_e->value, b_e->value);
}

q_sort

想法: 有想到兩種有效率的排序方式，quick sort 和 merge sort，怕會有 worst case 造成 quick sort 時間複雜度為

O(N2)，所以最後採用 merge sort 讓時間複雜度為
O(N∗log(N))。

void merge(struct list_head *head,
           struct list_head *left_head,
           struct list_head *right_head)
{   
    struct list_head *left_iter = left_head->next,
                     *right_iter = right_head->next;
    struct list_head *left_next = left_iter->next,
                     *right_next = right_iter->next;

    while (left_iter != left_head || right_iter != right_head) {
        if (left_iter == left_head) {
            list_move_tail(right_iter, head);
            right_iter = right_next;
            right_next = right_iter->next;
            continue;
        }

        if (right_iter == right_head) {
            list_move_tail(left_iter, head);
            left_iter = left_next;
            left_next = left_iter->next;
            continue;
        }


        
        if (compare(left_iter, right_iter) < 0) {
            list_move_tail(left_iter, head);
            left_iter = left_next;
            left_next = left_iter->next;
        } else {
            list_move_tail(right_iter, head);
            right_iter = right_next;
            right_next = right_iter->next;
        }
    }
}
void merge_sort(struct list_head *head)
{
    if (head == NULL || list_empty(head) || list_is_singular(head))
        return;

    LIST_HEAD(left_head);
    LIST_HEAD(right_head);
    struct list_head *front = head->next, *end = head->prev, *mid = NULL;
    struct list_head *iter = NULL, *next = NULL;

    while (front != end && front->next != end) {
        front = front->next;
        end = end->prev;
    }                                                                                                

    mid = end;

    for (iter = head->next, next = iter->next; iter != mid;
         iter = next, next = iter->next) {
        list_move_tail(iter, &left_head);
    }

    for (iter = mid, next = iter->next; iter != head;
         iter = next, next = iter->next) {
        list_move_tail(iter, &right_head);
    }

    merge_sort(&left_head);
    merge_sort(&right_head);
    merge(head, &left_head, &right_head);
}

/* Sort elements of queue in ascending order */
void q_sort(struct list_head *head)
{
    if (head == NULL || list_empty(head) || list_is_singular(head))
        return;

    merge_sort(head);
}

q_reverseK

想法: 將 list 切成多個 group，每個 group 大小為 k，切好後利用 q_reverse() 來得到結果，最後將多個 group 拼接起來。

/* Reverse the nodes of the list k at a time */
void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if (head == NULL || list_empty(head) || list_is_singular(head))
        return;

    int num_of_groups = q_size(head) / k;                                                                                           
    int i = 0, j = 0;
    struct list_head *iter = head->next, *next = iter->next;
    LIST_HEAD(res_head);

    for (; i < num_of_groups; i++) {
        LIST_HEAD(tmp_head);

        for (j = 0; j < k; j++) {
            list_move_tail(iter, &tmp_head);
            iter = next;
            next = iter->next;
        }

        q_reverse(&tmp_head);
        list_splice_tail(&tmp_head, &res_head);
    }

    list_splice(&res_head, head);
}

q_delete_dup

想法: first 指標指向第一個節點，second 指標指向第二個節點，若兩個節點的字串相同，則 second 往下一個節點走，直到兩個節點的字串不相同，便能得到 first 和 second 的前一個為相同字串的節點。若兩個節點的字串不相同，first 和 second 皆往下一個節點走。

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

    struct list_head *first = head->next, *second = first->next,
                     *second_next = second->next, *first_prev = NULL;
    element_t *e = NULL;

    while (first != head && second != head) {
        if (compare(first, second) == 0) {
            first_prev = first->prev;
            while (second != head && compare(first, second) == 0) {
                e = container_of(second, element_t, list);
                element_del(e, head);
                second = second_next;
                second_next = second->next;
            }

            e = container_of(first, element_t, list);
            element_del(e, head);
            first_prev->next = second;
            second->prev = first_prev;
        }

        first = second;
        second = second_next;
        second_next = second->next;
    }
    
    return true;
}

q_descend

想法: 由後往前逐一走訪，紀錄當前最大值，只要比最大值小，將該節點移除即可。

int q_descend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    if (head == NULL || list_empty(head) || list_is_singular(head))
        return 0;

    struct list_head *iter = head->prev, *prev = iter->prev, *max = iter;
    element_t *e = NULL;

    while (iter != head) {
        if (compare(iter, max) > 0)
            max = iter;
        else if (compare(iter, max) < 0) {
            e = container_of(iter, element_t, list);
            element_del(e, head);
        }

        iter = prev;
        prev = iter->prev;
    }

    return q_size(head);
}
Last changed by 
 
Shino 吳宗諺
Hi
0
504

Read more

Golang 多版本 Windows

Golang 多版本 Windows

Nov 14, 2023
2023q1 Homework1 (quiz1)

contributed by < as200188 > 第一題 參考 list.h static void list_sort(struct list_head *head)運作原理 若 head 為空或只有一個節點，則不需處理，直接 return。 宣告 list_less 和 list_greater 用來指向小於 pivot 的多個節點和大於 pivot 的多個節點。 取 list 第一個節點作為 pivot。然後將該 pivot 從 list 中移除。

Feb 20, 2023
Read more from Shino 吳宗諺
Published on HackMD