第一週: 誠實面對自己

我的背景

  1. 出社會工作只有六日可以學習
  2. 因為都是寫embedded 所以活在C99 的世界裡面
  3. 使用C 語言十年,關於C 語言的部份有精讀過這些書,但是有時候細節與不常用的特性其實忘了差不多,只記得在哪裡也許可以找到答案
    • ​​​​​​​​​​The C Programming Language, 2/e
      
    • ​​​​​​​​​​C in a Nutshell: The Definitive Reference, 2/e
      
    • ​​​​​​​​​​Test Driven Development for Embedded C
      
  4. 有一些用到才會查的工具書籍
  5. 自己的學習方法是先看一次簡中版快速吸收再看一次英文版確認細節
  6. 之後會逼自己都使用繁體中文翻譯,可以參考資訊科技詞彙翻譯
思考過程

心得與思考過程會放在:::spoiler當中

以下是課程閱讀筆記

Linux 核心設計 (2025): 課程介紹

  • 工程師素養
  • 課程與作業批改方式介紹
  • Wiki 當中有* 號的要先看
  • 課程講解的錄影一定要看
  • 請使用安裝 Linux 作業系統與使用Linux
murmur

大家應該都是回到家打開Chrome 看Youtube 或玩遊戲,Steam Deck 也是用 Linux

  • 數學要會用
murmur

數學不懂沒關係,會用就好。有時候不懂只是背不起來。
先不用害怕的去嘗試用用看,用多了就會背,會背了就懂了 (忘了就問AI)
寫數學不用怕寫錯,數學又不是恐怖遊戲

GNU/Linux 開發工具共筆(https://hackmd.io/@sysprog/gnu-linux-dev/)

推測

示範當中的B 可以轉置並不是有什麼數學意義只是為了示範效能
主要原因是B 的For 迴圈可以快速利用 j k 變數來利用Cache

你所不知道的 C 語言:指標篇

使用Whisper 產生逐字稿 環境是使用colab
可以快速複習概念與學習新的觀點
打算把youtube 影片轉成mp3 匯入到 Google NotebookLM 幫忙作筆記

目前自己需要加強練習的部份,暫時不會讓作業寫不出來先記著後面再看。

  • cdecl 可解釋 C 程式宣告的意義這是一個好工具
  • typedef 我沒有真正理解,這裡我需要加強
  • function pointer 理解練習

你所不知道的 C 語言:指標篇 (上) (2018-02-05)

https://notebooklm.google.com/notebook/b69a4118-26b7-4099-9872-fd46a69095a2
可以mail 給我再share 給你, 但還是這種學習型筆記建議自己寫比較有吸收的效果

推薦補充書籍

https://refactoring.guru/design-patterns

你所不知道的 C 語言:指標篇 (下) (2018-02-12)

https://notebooklm.google.com/notebook/efd91a9c-0d12-4c51-918a-ab7e5c60eb6e

底下是這一次更新我的腦袋的知識

  • Array subscripting 在 C 語言中實際上是一種語法糖(syntactic sugar)
  • https://hackmd.io/@sysprog/c-pointer#Pointers-vs-Arrays (要背起來什麼時候可以互相轉換什麼時候不行)
  • A pointer to void shall have the same representation and alignment requirements as a pointer to a character type.
  • char *p = "hello world" 和 char p[] = "hello world" 寫法相似,但底層的行為卻大相逕庭
  • C 語言規格中定義 string literals 會被分配於 "static storage" 當中 (C99 [6.4.5]),並說明如果程式嘗試修改 string literals 的內容,將會造成未定義行為
  • C99 [6.2.4] Storage durations of objects
    An object has a storage duration that determines its lifetime.
    There are three storage durations: static, automatic, and allocated.
  • C 語言中,static literal通常在唯讀的data section裡。C 語言規範說明若程式修改string literal,會導致未定義的行為
  • 使用 https://godbolt.org/ 實驗實際行為
  • 觀察出來跟課程相同的結論
    • char *p = "hello world"
      • p is a pointer to char.
      • "hello world" is a string literal, which is stored in a read-only section of memory.
      • p is initialized to point to the first character of this string, 'h'.
      • Since the string is a constant, modifying its contents through p leads to undefined behavior.
    • char p[] = "hello world"
      • p is a character array (char array).
      • "hello world" is a string literal, which is copied into the p array at compile time.
      • The size of p is automatically determined and includes the null terminator (\0),
        making the total size 12 (11 characters + 1 null terminator).

只知道寫8051 的時候都編譯器都會提醒要加上const ,原來是這個C99 Spec的原因,今天(2025/02/22)終於知道了
自己過去都是先背起來,避免使用錯誤與不清楚的語法,直接記憶const char* p = "abc" 是一種明確寫法
今天終於知道明確背後真正的原因了

實驗char *p = "abc" 和 char s[] = "ijk"的底層差異是什麼
#include <stdio.h> #include <string.h> void foo(void) { const char *p = "abc"; char s[] = "efg"; const char cS[] = "ijk"; puts(p); }

x86_64_gcc (x86asm)

.LC0: .string "abc" foo: pushq %rbp movq %rsp, %rbp subq $16, %rsp movq $.LC0, -8(%rbp) movl $6776421, -12(%rbp) movl $7039593, -16(%rbp) movq -8(%rbp), %rax movq %rax, %rdi call puts nop leave ret

sdcc (8051)

_foo_s_10000_41: .ds 4 _foo_cS_10000_41: .ds 4 _foo: ar7 = 0x07 ar6 = 0x06 ar5 = 0x05 ar4 = 0x04 ar3 = 0x03 ar2 = 0x02 ar1 = 0x01 ar0 = 0x00 mov _foo_s_10000_41,#0x65 mov (_foo_s_10000_41 + 0x0001),#0x66 mov (_foo_s_10000_41 + 0x0002),#0x67 mov (_foo_s_10000_41 + 0x0003),#0x00 mov _foo_cS_10000_41,#0x69 mov (_foo_cS_10000_41 + 0x0001),#0x6a mov (_foo_cS_10000_41 + 0x0002),#0x6b mov (_foo_cS_10000_41 + 0x0003),#0x00 mov dptr,#___str_0 mov b, #0x80 ljmp _puts ___str_0: .ascii "abc"
把常數的概念套用到文字上但遇到一些小瓶頸
const int a = 1; /*declare a as const int*/ const int *p = &a /*declare p as pointer to const int*/

a 初始化為一個不可更改的常數1
p 指針指向變數a

但是常數沒有字串一樣的語法糖,所以在撰寫的時候不會攪混。
如果把字串宣告的語法糖拆開的話

#include <stdio.h> #include <string.h> const char a[] = "abc"; /*這個要宣告在所有function 的外面才會等效語法糖*/ void foo(void) { const char *p = &a[0]; } void bar(void) { const char *p = "abc"; puts(p); } void uwu(void) { const char b[] = "abc"; /*declare b as array of const char, and "abc" is copied into the a array at compile time*/ const char *p = &b[0]; }

題目 1 (雙向 + 環狀) + 分析(https://www.youtube.com/watch?v=zaA9jzWvMlg)

題目1 原本長這樣子 : https://hackmd.io/@jserv/SyK-WApKM?type=view#測驗-2
題目1 的分析 : https://hackmd.io/@sysprog/linked-list-quiz

  • 理解 linked list 的基本概念和不同類型 (單向、雙向、環狀)
  • 掌握 linked list 的基本操作 (新增、刪除、搜尋、反轉)
  • 參考題目1 的分析方式繪圖與逐行分析
  • 先詢問 NotebookLM 需要作答需要哪些基本知識,先確認自己有沒有足夠的知識作答,不夠的話先補習
  • 接下來作答方式必須要自己使用已知的基本知識作答並背起來,思考過才可以記得久
學習結果

Q1
func C 都沒有找到就先malloc 並且最後沒有找到的話也沒有free 並且根據圖片是環狀,那一直找不到就會一直while 死迴圈吧
題目void main(void)有考慮到這件事情,所以不會無窮迴圈

Q2
https://en.cppreference.com/w/c/language/operator_precedence
這裡有答案告訴你運算的先後順序

https://learn.microsoft.com/zh-tw/cpp/cpp/for-statement-cpp?view=msvc-170
這裡有答案告訴你for 迴圈的執行順序,太久沒碰忘了

    for(int i = 0 /*1*/, i < 1 /*2*/, i++ /*4*/)
        printf("%d\n",i); /*3*/

做題技巧是可以偶而化簡可以幫助思考

int FuncX(struct node *head, int *data) {
    struct node *node;
    for (node = head->next;     /*1. initialize node is head->next*/
         node && node != head;  /*(Verify that the node is not the head) and (Verify node is not null)*/
                                /*2. (Verify that the head->next is not the head) and (Verify head->next is not null)*/
        node = node->next)      /*4. head->next = head->next->next */
        data++;                 /*3. memory address plus one and throw away*/
    return node - head;         /*5. calcualte the memory address distance between the head->next and head*/
}

Linux: 作業系統術語及概念 (目標是先寫作業,先跳過詳細閱讀, 先吃8051有深度理解的老本)

https://hackmd.io/@sysprog/linux-concepts

我的目標事先寫作業,先大概聽過影片就好
8051 是極度簡化的CPU 架構

你所不知道的 C 語言: linked list 和非連續記憶體(https://www.youtube.com/watch?v=pTcRq__iKzI)

https://hackmd.io/@sysprog/c-linked-list

https://notebooklm.google.com/notebook/1122fc69-c759-4397-819e-2e02f5fc21be

  1. 準備工作把影片轉成MP3 並上傳,第一個上傳的東西會特別影響AI 的方向,所以要先上傳語音轉成逐字稿
  2. 先放老師的Hackmd 就夠多了,為了避免AI 失去焦點,可以讓AI做一次總結,等後續跟AI 討論想法前再補連結進去
  3. 先詢問 NotebookLM 需要作答需要哪些基本知識,可以直接把NoteBookLM 右邊的預設記事都按過一次
  4. 根據 NoteBookLM 出的題目考自己
  5. 補上傳C99 Spec
  6. 補上課程Hackmd 內的連結與影片
  7. 只要有一點不懂就要讀到懂並理解到可以換句話說給NotebookLM 聽 (Attention + 強化學習法)
  8. 再把自己不會的地方複習多次一點 (AI 的蒸餾學習法)
  9. 可以練習英文聽力因為有兩位主持人會根據上傳的內容討論題目給你聽一次
  • 單向 linked list 節點的常見結構需要先知道,這是基本知識
  • 理解 remove_list_node 是如何變成有「品味」的版本
用自己的話說一次有「品味」的版本
  1. 前提:以下的討論不涵蓋 list is empty 和 node is not in the list 的狀況
    這個前提很只重要,因為node is not in the list 這個寫法就不存在了
  2. 先理解特例如何產生
    原本的解法都是從target 的角度去看事情,所以希望的是把prev 的next 取代掉,但是會遇到prev == NULL 的時候
    因為head 本身就是target
  3. 嘗試理解如何解決特例
    特例:head 需要有辦法變成target->next ,那只能寫一個東西來代表head 的位址,就說是候選人好了
    因為是代表head,所以能夠代表記憶體空間的只有指標了,所以才會稱作「指標的指標」

候選人一開始一定是代表list->head。 Node **candidate = &list->head;
當候選人不是目標就換候選人下一位,當作候選人

while (*candidate != target)
   candidate = &(*candidate)->next

直到候選人就是目標,這個時候候選人本身被目標的下一位給覆蓋,覆蓋這件事情也是一種刪除
*candidate = target->next
3. 重新用自己的話說一次當list->head == target 的時候發生的事情
例如有一個list 是 A->B->C->D , list->head = &A
3.1 當A 這位候選人是目標的時候,候選人一開始會是list->head,馬上檢查到A 是目標,候選人(list->head) 會被目標的下一位給取代
最後就是list->head = target->next (A = target->next)
3.2 當B 這位候選人事目標的時候,一開始會檢查A 不是目標,所以候選人換成下一位,變成B,結果檢查B 是目標,B 這位候選人會被目標的下一位給取代
這個時候B = target->next
所以教材裡面才會說這句話

更新的是同一類型的資料,不用特別操作,自然省下額外的處理

  • 來猜測如何從基礎的一般解法找到有「品味」的版本,試著從直觀解法如何發現

因為我是一般人,所以想要試著推敲當初是如何發現找到這種解法,試著回推思考路經,並從中學習思考的方式。
這一次學習到的結論是:如何利用指標就是代表的能力,去想辦法找到同時代表list->head 與 prev->next 。

直觀的解法當中有這個判斷

if (!prev)
    list->head = target->next;
else
    prev->next = target->next;

找到能夠同時代表 list->head 與 prev->next 的類型只有 Node ** ,從這裡開始改寫的話

void remove_list_node(List *list, Node *target)
{
    Node **candidate;
    Node *prev = NULL;
    Node *current = list->head;
    // Walk the list
    while (current != target) {
        prev = current;
        current = current->next;
    }
    // Remove the target by updating the head or the previous node.
    if (!prev)
        candidate = &list->head;
        candidate = target->next;
    else
        candidate = &prev->next;
        candidate = target->next;
}

再進行嘗試直觀可以取代的事物Node *current = list->headcandidate = &list->head ,因為同時存在list->head

void remove_list_node(List *list, Node *target)
{
    Node **candidate = &list->head;
    Node *prev = NULL;
    Node *current = *candidate;
    // Walk the list
    while (current != target) {
        prev = current;
        current = current->next;
    }
    // Remove the target by updating the head or the previous node.
    if (!prev)
        /* candidate = &list->head; */ /*因為重複所以可以刪除*/
        candidate = target->next;
    else
        candidate = &prev->next;
        candidate = target->next;
}

繼續取代掉Node *current ,因為作用跟*candidate 重複了

void remove_list_node(List *list, Node *target)
{
    Node **candidate = &list->head;
    Node *prev = NULL;
    // Walk the list
    while (*candidate != target) {
        prev = *candidate;
        candidate = &(*candidate)->next;
    }
    // Remove the target by updating the head or the previous node.
    if (!prev)
        candidate = target->next;
    else
        candidate = &prev->next;
        candidate = target->next;
}

因為看到if 當中有相同的邏輯,所以可以把它取出來,並保持執行順序

void remove_list_node(List *list, Node *target)
{
    Node **candidate = &list->head;
    Node *prev = NULL;
    // Walk the list
    while (*candidate != target) {
        prev = *candidate;
        candidate = &(*candidate)->next;
    }
    // Remove the target by updating the head or the previous node.
    if (prev)
        candidate = &prev->next;
    candidate = target->next;
}

通常上面這裡已經很接近結果,這個時候思考一下prev 重要嘛?

  1. list->head 是 target 會發生什麼?
void remove_list_node(List *list, Node *target)
{
    Node **candidate = &list->head;
    Node *prev = NULL;
    while (*candidate != target) {
        prev = *candidate;
        candidate = &(*candidate)->next;
    }
    candidate = target->next;
}

prev is NULL ,所以最後的if 也可以刪掉,但是這只是一個特例,思考下面的原本直觀的步驟
2. list->head 不是target 會發生什麼?
假設這樣: A->B->C , list->head = A

void remove_list_node(List *list, Node *target)
{
    Node **candidate = &list->head;
    Node *prev = NULL;
    while (*candidate != target) {
        prev = *candidate; /*prev會變成前一位候選人=>A*/
        *candidate = &(*candidate)->next; /*候選人變成下一位候選人=>(B)*/
    }
    if (prev) /*prev 是(A)*/
        candidate = &prev->next; /*候選人會變成前一位候選人(A)的下一位(B),就是現在這位,等於沒變*/
    candidate = target->next;
}

所以prev 的判斷最後就可以拿掉了

void remove_list_node(List *list, Node *target)
{
    Node **candidate = &list->head;
    while (*candidate != target) {
        *candidate = &(*candidate)->next; /*候選人變成下一位候選人*/
    }
    candidate = target->next;
}

這就是我猜測的思考流程

隨堂測驗

https://hackmd.io/@sysprog/linux2025-quiz1#測驗-1

https://notebooklm.google.com/notebook/10554a4d-a375-4c01-a5b9-8225923ebeee?_gl=1yr9j42_gaNzc2MDg1ODc4LjE3MzgxMzY5Nzk._ga_W0LDH41ZCB*MTc0MDQ3NjA3MS41LjEuMTc0MDQ3NjA3MS42MC4wLjA.

重新複習心得,根據上述的思考過後,加速記憶indirect pointer 還有一種解釋方式,記憶成:找Address、代表Address 的代表

Q1 是單純的考概念
Q2 自己需要補Binary Tree 當中的名詞

https://hackmd.io/@QKMHK3OyTUSmk9BqwHaggQ/SyqXuBRE5
直接學習引用的文章的刪除的部份,不能直接看NoteBoolLM 提供的答案

  • In-order traversal(依序遍歷):以「左 -> 中 -> 右」的順序走訪二元樹
  • successor 繼任 predecessor 前任
  • In-order predecessor 代表,Inorder Predecessor: N在inorder順序中的前一個,也就是左子樹中的最大者,會在左子樹最偏右的位置

定義successor 跟 predecessor 因為當左右都有子樹的時候,必須挑一個來替代自己,左右都有子樹的意思就是自己為中間的根。
所以 In-order predecessor 就是跟的左邊的數,並且數字接近自己
左 < 中 < 右

In-order predecessor 就是左子樹的最偏右的位置,因為數字才會最接近中間,如果大於中間就會是右子樹的範圍。

所以要往左數的最右邊的子節點,從某一個子節點來看,就帶表示右邊不是空的時候就要往右走,一直往右走。

Q3

  • 需要先看懂實作非遞迴 (non-recursive; iterative) 的快速排序法程式碼,才有辦法改寫成 list.h 的格式
    當中就有 cccc / dddd / eeee 的題目包含在裡面 XDDDDD

  • 需要先看懂圖片 操作鏈結串列的圖解,實做出來 CCCC/DDDD/EEEE 再轉換?
    先試試看不用,找到送分題試試看

  • HHHH/IIII 本身就是送分題 可以參考 list_is_ordered
    p = p->next; 看起來放在最後面會更像圖片的思考流程,放在前面給人一種不會再用到所以先放在前面 (或是誤導要用p) ?

  • JJJJ/KKKK 參考前面的結果描述撰寫的 應該是只存入的list_head

  • 突然發現自己不懂 circular doubly-linked list ,沒辦作答 GGGG

  1. 一開始指向自己的head 很重要,初始化過後的 head,第一次執行list_add 當中的 *next 其實是head 自己。
  • list_add 的圖解步驟
  1. INIT_LIST_HEAD
    next direction : head -> (head)
digraph g {
graph [
rankdir = "LR"
];
"head" [
label = "<prev> prev | <address> (head) | <next> next"
shape = "record"
];
"head":next -> "head":address
"head":prev -> "head":address
}
  1. list_add(node1, head)
    next direction : head -> node1
digraph g {
graph [
rankdir = "LR"
];
"head" [
label = "<prev> prev | <address> (head) | <next> next"
shape = "record"
];
"node1" [
label = "<prev> prev | <address> (node1) | <next> next"
shape = "record"
];
"head":next -> "node1":address [color=orange]
"head":prev -> "node1":address [color=orange]
"node1":next -> "head":address [color=orange]
"node1":prev -> "head":address [color=orange]
}
  1. list_add(node2, head)
    next direction : head -> node2 -> node1
digraph g {
graph [
rankdir = "LR"
];
"head" [
label = "<prev> prev | <address> (head) | <next> next"
shape = "record"
];
"node1" [
label = "<prev> prev | <address> (node1) | <next> next"
shape = "record"
];
"node2" [
label = "<prev> prev | <address> (node2) | <next> next"
shape = "record"
];
"head":prev -> "node1":address
"node1":next -> "head":address
"node1":prev -> "node2":address [color=orange]
"node2":next -> "node1":address [color=orange]
"node2":prev -> "head":address [color=orange]
"head":next -> "node2":address [color=orange]
}
  1. list_add(node3, head)
    next direction : head -> node3 -> node2 -> node1
  • 又發現自己不會list_construct,沒辦作答 GGGG ?

每一個node 的記憶體位置的旁邊都有 long,所以才可以用container_of

https://hackmd.io/@sysprog/c-trick

是一種轉態,原本是list_head 的記憶體轉態,原本只有專住在list_head 的記憶體空間,轉態之後擴充到可以看到list_head 記憶體位置上面所包含的資料,利用struct 是緊湊記憶體空間的特性,就可以看到剩下的value,所以只要改變list_head 的排列順序就可以改變整體的資料結構,不用把value 跟著複製。

  • GGGG 難怪放在第一個,其實就是很單純的 circular doubly-linked list 重建
    可以參考 list.h 把 list_add變數換掉就可以看出來答案的樣子

  • 如果要用debug 的方式還原的value,可以手動轉態
    (node_t*)((char*)pivot - (sizeof(node_t) - sizeof(struct list_head)))
    (node_t*)((char*)p - (sizeof(node_t) - sizeof(struct list_head)))
    (node_t*)((char*)L - (sizeof(node_t) - sizeof(struct list_head)))
    (node_t*)((char*)R - (sizeof(node_t) - sizeof(struct list_head)))
    (node_t*)((char*)n - (sizeof(node_t) - sizeof(struct list_head)))
    (node_t*)((char*)left - (sizeof(node_t) - sizeof(struct list_head)))
    用char* 單純因為計算的時候會是1 個address 1個address 移動

只要跟著走一次就可以理解所謂的begin 模擬stack 行為的意思

list 是 list_head 沒辦法算出value
第一個變數
(node_t*)((char*)list->next - (sizeof(node_t) - sizeof(struct list_head)))

可以確認最後行為都正確,代表答案也都正確了

  • 終於都考100 分了

2025/2/27 都寫完了,Ya

Select a repo