2023q1 Homework1 (lab0)

contributed by < Lomomo >

前言

寫這段主要是來提醒和勉勵自己。

大學畢業到現在已經工作兩年，雖然拿到看似還過得去的薪水，但是因為自己的專業不足，對於每天自己產出爛程式碼的生活感到反感，於是來參加課程。

第一周的上課老師說很多所謂的得過且過、能動就好的那種半吊子工程師根本就是在說我，在 Maslow’s pyramid of code review 中，我的確連邊都摸不到。

誠實面對自己，面對自己的不足。

Vic LuoFeb 17, 2023

開發環境

$ 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.

$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         43 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  16
  On-line CPU(s) list:   0-15
Vendor ID:               AuthenticAMD
  Model name:            AMD Ryzen 7 3700X 8-Core Processor
    CPU family:          23
    Model:               113
    Thread(s) per core:  2
    Core(s) per socket:  8
    Socket(s):           1
    Stepping:            0
    Frequency boost:     disabled
    CPU max MHz:         5040.9170
    CPU min MHz:         2200.0000
    BogoMIPS:            8200.08
Virtualization features: 
  Virtualization:        AMD-V
Caches (sum of all):     
  L1d:                   256 KiB (8 instances)
  L1i:                   256 KiB (8 instances)
  L2:                    4 MiB (8 instances)
  L3:                    32 MiB (2 instances)
NUMA:                    
  NUMA node(s):          1
  NUMA node0 CPU(s):     0-15

開發過程

開發環境設定

cppcheck install from gitgub.

git clone https://github.com/danmar/cppcheck
sudo apt install libpcre3-dev
make install -j24 MATCHCOMPILER=yes FILESDIR=/usr/share/cppcheck HAVE_RULES=yes CXXFLAGS="-O2 -DNDEBUG -Wall -Wno-sign-compare -Wno-unused-function"
$ cppcheck --version 
Cppcheck 2.11 dev

q_insert_head

head 若為 Null 回傳 false.
要為 element_t 和 element_t->value 配置記憶體.

strlen() 回傳字串長度不包含 \0.
strncpy() 不會幫字串加入結尾字元, 必須另外處裡.

q_remove_head

若 head->next 指向自己,表示 queue 為空.

list_del 在 list.h 中說明

the node has to be handled like an uninitialized node.

使用 list_del_init 移除並初始化節點, 確保移除後節點內指標是安全的.

做到這邊發現我不知道怎麼取得 element_t->value.到 qtest.c 中觀察到 q_show() 有使用到 list_entry ,在這裡面還有 container_of 在教材中有搜尋到回去詳讀.

#define container_of(ptr, type, member) \
    ((type *) ((char *) (ptr) -offsetof(type, member)))

參考 Linux 核心原始程式碼巨集: container_of
offsetof 會回傳成員的位址減去 struct 的起始位址

offsetof 會處理 struct 記憶體對齊的部份

offsetof example code

#include <stddef.h>
#include <stdio.h>

struct data {
    short a;
    char b;
    double c;
};
int main() {
    struct data x = {.a = 25, .b = 'A', .c = 12.45};
    char *p = (char *) &x;
    printf("a=%d\n", *((short *) p));
    p += sizeof(short);
    printf("b=%c\n", *((char *) p));
    p = (char *) &x + offsetof(struct data, c);
    // p += sizeof(char);
    printf("c=%lf\n", *((double *) p));
    printf("p=%p, &x.c=%p\n", p, &(x.c));

    printf("offsetof(struct data, c): %ld\n", offsetof(struct data, c));
}

$ ./main 
a=25
b=A
c=12.450000
p=0x7ffe438c9c88, &x.c=0x7ffe438c9c88
offsetof(struct data, c): 8

下面是結果是直接對 struct member type 計算偏移的結果, 會有 padding 導致 c 得出的結果有誤.

./main 
a=25
b=A
c=190346578428946467411813376969926036231236201599375216348857262157744255007426608362121915988857235308148337053537869186724122510073570901116281414778212356702476212757602596560790618112.000000
p=0x7ffc47e4ae73, &x.c=0x7ffc47e4ae78

了解 offsetof 後, 回到作業中觀察, 就可以知道麼去獲取 element_t 的位置了.

展開 Macro 後如下

// #define container_of(ptr, type, member)
container_of(head->next, element_t, list);
((element_t *) ((char *) (head->next) - offsetof(element_t, list)))

• (char *) (head->next) 在 element_t 中 list_head 的位址
• offsetof(element_t, list) element_t->list 的位址減去 struct 的起始位址
• 上述兩個位址相減就得到最外層 element_t 的位址
• 最後 (element_t *) 回傳

q_reverse

利用 list_for_each_safe 的特性就可以順利的走訪 queue 及 node->next 和 node->prev 交換操作.
最後 node 會指回 head 即可完成 head->next 和 head->prev 交換的操作.

q_delete_mid

剛開始就很直觀的直接去實做出來, 先計算 queue size 的一半的是多少, 然後走訪 queue 得到 middle 的位置.

在教材中有看到可以利用快慢指標的方式去取得之後再來改寫.

另外在 qtest 測試 dm 的過程中，有發現計算 queue 大小的變數 current->size 除了程式報錯的情況都會去執行 current->size-- 的運算, 導致有負數的出現. 已經提交 Pull request 等待 code reivew.

下面為 gdb 除錯的紀錄

0x0000555555557dd8 in do_dm (argc=<optimized out>, argv=<optimized out>) at qtest.c:689
689         current->size--;
(gdb) c
Continuing.

Hardware access (read/write) watchpoint 1: current->size

Old value = 0
New value = -1

Hardware access (read/write) watchpoint 1: current->size

Value = -1
do_dm (argc=<optimized out>, argv=<optimized out>) at qtest.c:690
690         q_show(3);

使用快慢指針改進原本用計數取得中間節點的時間複雜度, 少了計算 queue 的大小, 使得時間複雜度從

$O(n^2)$ 變成

$O(n)$.

q_swap()

初步思考如下圖，A 節點透過 list_del移出後, B 節點對於 C 節點後面的 list 即為 head node. 在透過 list_add(A, B) 把 A 節點加到 C list 的開頭, 這樣對於 A, B 兩節點即完成交換的動作. list_del 和 list_add 也已經在 list.h 封裝成 list_move.

在 list_for_each node 在 swap 完成後, 也就剛好指向下一對節點.
最後走訪所有節點, 執行上述步驟即完成 q_swap().

q_sort()

嘗試去實做時, 因為 merge sort 需要取得中間節點, 就使用快慢指針回去改寫 get_middle_node 的方法.

閱讀教材的過程, 真的覺得自己理解指標變數的速度很慢, 特別要去理解間接指標的時候更覺得有挫折感, 下面是大概描述我看到這段程式腦海理解他的聲音，雖然感覺描述這段很沒有意義，但是就是有個結在卡在那的感覺，如果有更好的理解在麻煩多指教，不過追根究底我覺得還是指標的使用太少了，還得多多練習.

// head 是指向結構體的變數, 存有結構體的位址
struct ListNode *head = malloc(stuct ListNode);

// ptr 是 pointer to pointer to struct ListNode 知道他是這樣但是感覺有點迷糊
struct ListNode **ptr = &head;
// ptr equal &head
// *ptr equal head
// **ptr equal *head equal struct Listnode
ptr = &(*ptr)->next
// ptr = &(head)->next
// ptr = &(*head).next