第一週: 誠實面對自己

# 第一週: 誠實面對自己 ## 我的背景 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. 之後會逼自己都使用繁體中文翻譯，可以參考[資訊科技詞彙翻譯](/i4pWFe0fQHS7WTi10KVdEA) :::spoiler 思考過程心得與思考過程會放在`:::spoiler`當中 ::: ## 以下是課程閱讀筆記 ### [Linux 核心設計 (2025): 課程介紹](https://www.youtube.com/watch?v=HiT19cs_Ys0) * 工程師素養 * 課程與作業批改方式介紹 * Wiki 當中有* 號的要先看 * 課程講解的錄影一定要看 * 請使用安裝 Linux 作業系統與使用Linux :::spoiler murmur 大家應該都是回到家打開Chrome 看Youtube 或玩遊戲，Steam Deck 也是用 Linux ::: * 數學要會用 :::spoiler murmur 數學不懂沒關係，會用就好。有時候不懂只是背不起來。先不用害怕的去嘗試用用看，用多了就會背，會背了就懂了 (忘了就問AI) 寫數學不用怕寫錯，數學又不是恐怖遊戲 ::: ### GNU/Linux 開發工具共筆(https://hackmd.io/@sysprog/gnu-linux-dev/) - [x] 安裝 Ubuntu 24.04 LTS - [x] 熟悉 Linux 操作 - [x] 熟悉 Git - [x] 熟悉 HackMD - [x] 熟悉 LaTex (https://hackmd.io/@eastWillow/rJ-DKHiKK) - [x] 安裝 perf - [x] 安裝 gnuplot * http://www.gnuplot.info/screenshots/ :::spoiler 推測示範當中的B 可以轉置並不是有什麼數學意義只是為了示範效能主要原因是B 的For 迴圈可以快速利用 j k 變數來利用Cache ::: ### [你所不知道的 C 語言：指標篇](/hqJBzualRcOrb2wMhheKCQ) 使用Whisper 產生逐字稿環境是使用[colab](https://colab.research.google.com/github/ArthurFDLR/whisper-youtube/blob/main/whisper_youtube.ipynb) 可以快速複習概念與學習新的觀點打算把youtube 影片轉成mp3 匯入到 Google NotebookLM 幫忙作筆記目前自己需要加強練習的部份,暫時不會讓作業寫不出來先記著後面再看。 - [ ] cdecl 可解釋 C 程式宣告的意義這是一個好工具 - [ ] typedef 我沒有真正理解，這裡我需要加強 - [ ] function pointer 理解練習 #### [你所不知道的 C 語言：指標篇 (上) (2018-02-05)](https://youtu.be/G7vERppua9o?si=BkNa0COuQSfQy1BY) https://notebooklm.google.com/notebook/b69a4118-26b7-4099-9872-fd46a69095a2 可以mail 給我再share 給你, 但還是這種學習型筆記建議自己寫比較有吸收的效果 :::spoiler 推薦補充書籍 https://refactoring.guru/design-patterns ::: #### [你所不知道的 C 語言：指標篇 (下) (2018-02-12)](https://www.youtube.com/watch?v=Owxols1RTAg) 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"` 是一種明確寫法 > 今天終於知道明確背後真正的原因了 :::spoiler 實驗`char *p = "abc" 和 char s[] = "ijk"`的底層差異是什麼 ```cpp= #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) ```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) ```mipsasm= _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" ``` ::: :::spoiler 把常數的概念套用到文字上但遇到一些小瓶頸 ```cpp= const int a = 1; /*declare a as const int*/ const int *p = &a /*declare p as pointer to const int*/ ``` a 初始化為一個不可更改的常數1 p 指標指向變數a 但是常數沒有字串一樣的語法糖，所以在撰寫的時候不會攪混。如果把字串宣告的語法糖拆開的話 ```cpp= #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#%E6%B8%AC%E9%A9%97-2 > 題目1 的分析 : https://hackmd.io/@sysprog/linked-list-quiz * 理解 linked list 的基本概念和不同類型 (單向、雙向、環狀) * 掌握 linked list 的基本操作 (新增、刪除、搜尋、反轉) * 參考題目1 的分析方式繪圖與逐行分析 * 先詢問 NotebookLM 需要作答需要哪些基本知識，先確認自己有沒有足夠的知識作答，不夠的話先補習 * 接下來作答方式必須要自己使用已知的基本知識作答並背起來，思考過才可以記得久 :::spoiler 學習結果 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 迴圈的執行順序，太久沒碰忘了 ```cpp for(int i = 0 /*1*/, i < 1 /*2*/, i++ /*4*/) printf("%d\n",i); /*3*/ ``` 做題技巧是可以偶而化簡可以幫助思考 ```cpp 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 0. 準備工作把影片轉成MP3 並上傳，第一個上傳的東西會特別影響AI 的方向，所以要先上傳語音轉成逐字稿 1. 先放老師的Hackmd 就夠多了，為了避免AI 失去焦點，可以讓AI做一次總結，等後續跟AI 討論想法前再補連結進去 2. 先詢問 NotebookLM 需要作答需要哪些基本知識，可以直接把NoteBookLM 右邊的預設記事都按過一次 3. 根據 NoteBookLM 出的題目考自己 4. 補上傳[C99 Spec](https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf) 5. 補上課程Hackmd 內的連結與影片 6. 只要有一點不懂就要讀到懂並理解到可以換句話說給NotebookLM 聽（Attention + 強化學習法） 7. 再把自己不會的地方複習多次一點（AI 的蒸餾學習法） 8. 可以練習英文聽力因為有兩位主持人會根據上傳的內容討論題目給你聽一次 * 單向 linked list 節點的常見結構需要先知道，這是基本知識 * 理解 remove_list_node 是如何變成有「品味」的版本 :::spoiler 用自己的話說一次有「品味」的版本 0. 前提：以下的討論不涵蓋 list is empty 和 node is not in the list 的狀況這個前提很只重要，因為node is not in the list 這個寫法就不存在了 1. 先理解特例如何產生原本的解法都是從target 的角度去看事情，所以希望的是把prev 的next 取代掉，但是會遇到prev == NULL 的時候因為head 本身就是target 2. 嘗試理解如何解決特例特例：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 所以教材裡面才會說這句話 >更新的是同一類型的資料，不用特別操作，自然省下額外的處理 ::: * 來猜測如何從基礎的一般解法找到有「品味」的版本，試著從直觀解法如何發現 :::spoiler 因為我是一般人，所以想要試著推敲當初是如何發現找到這種解法，試著回推思考路經，並從中學習思考的方式。這一次學習到的結論是：如何利用指標就是代表的能力，去想辦法找到同時代表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->head` 與 `candidate = &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#%E6%B8%AC%E9%A9%97-1 https://notebooklm.google.com/notebook/10554a4d-a375-4c01-a5b9-8225923ebeee?_gl=1*yr9j42*_ga*Nzc2MDg1ODc4LjE3MzgxMzY5Nzk.*_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順序中的前一個，也就是左子樹中的最大者，會在左子樹最偏右的位置 :::spoiler 定義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) ```graphviz digraph g { graph [ rankdir = "LR" ]; "head" [ label = "<prev> prev | <address> (head) | <next> next" shape = "record" ]; "head":next -> "head":address "head":prev -> "head":address } ``` 2. list_add(node1, head) next direction : head -> node1 ```graphviz 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] } ``` 3. list_add(node2, head) next direction : head -> node2 -> node1 ```graphviz 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] } ``` 4. 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

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.