2025q1 Homework5 (assessment)

contributed by < JimmyChongz >

閱讀〈因為自動飲料機而延畢的那一年〉的啟發

看完作者製作自動飲料機的心路歷程後，我深刻體會到「不輕易放棄」有多難。當困難接踵而至時，選擇放棄很簡單，但我會因為放棄而失去解決問題與累積經驗的機會，若未來有人問我：「在你的求學或工作經驗中，遇過最大的挑戰是什麼？你是如何克服的？」我可能會因為當初的退縮而無話可說。

我覺得這堂課的作業內容對我來說難度頗高 ，目前完成度最高的作業是作業一，在寫作業的過程中，我意識到我還有太多東西要補，搞不清楚自己到底要先補哪一個，且我使用 LLM 的機率很高，當我遇到問題時，都習慣先問 LLM，因為它能夠馬上給我「符合邏輯」的解釋，讓我能夠免強跟上作業繳交進度，但這就是為了交作業而交作業，並沒有真的學到東西，這部分我需要改變心態，應先把一件事做好再做另一件事。

學期初受指導教授指派擔任物聯網課程 Network Programming 的助教，需說明 socket interface 概念以及帶領學生透過樹莓派做 client & server 相關的實驗，有花費一些時間在看 Socket Interface 相關的內容，且 server 要能夠服務多個 client，需要對 server 做多執行緒（I/O）的設計，因此內容就應涉及 pthread, select 或 epoll 的概念。所以，針對期末專題我希望是完成第六次作業 khttpd 或參與類似 以 eBPF 建構 TCP 伺服器 的專案。

對 socket() 回傳的 File Descriptor 有些疑惑，已知 Everything in Unix is a file 的概念，且 File Descriptor 是一個非負整數，代表 File Descriptor Table 中的一個 entry 的索引。File Descriptor Table 是儲存在 PCB （即 Linux 中的 task_struct）中的一個資料結構，用來記錄程序所開啟檔案的相關資訊。每個 entry 會指向一個 Open File Table 的 entry，該表中包含與檔案操作有關的詳細資料，例如檔案的偏移量、開啟模式等。Open File Table 中的每個項目則會對應到一個 i-node（Linux 檔案系統中的資料結構），而 i-node 中則紀錄了檔案的路徑、大小、權限等。不過，這是針對像是 open() 這種 system call，即 open() 回傳的 fd 最終會指向硬碟中的某個檔案，但像是 socket() 回傳的 fd 最終會指向什麼？有查過是 Linux 實作 TCP/IP 的網路協議協定堆疊，但有點抽象難以理解，還是不太懂不懂。

就是困難才要特別教，其他教授對你沒期待，但我不是！
在此紀錄你的問題，隨後討論。

謝謝老師

會議紀錄

• Homework5
• bitwise operations
• Q2: Assume x is a single-precision floating point (IEEE 754) and always >= 1, calculate square root. No FPU is allowed.

https://hackmd.io/@sysprog/linux2025-kxo ⇒ Q1: 何以 Linux 核心不傾向使用 FPU
float my_sqrtf(float x)
{
}

Q3: 為何有 accpet 系統呼叫？為何不能直接 read socket fd？
Tell me why?

紀錄問題！

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

Q4: 比照 remove_list_node 撰寫 find_node / reverse_nodes，利用 indirect pointer (no external allocated memory. i.e., constant space complexity)

bool find_node(List *list, Node *target) 
{
    Node **indirect = &list->head;
    while (*indirect != NULL) {
        if (*indirect == target) {
            return true;
        }
        indirect = &(*indirect)->next;
    }
    return false;
}

// in-place: In-place_algorithm

void reverse_nodes(List *head) {
	if (!head || !head->next) { // singular
		return;
	}
	Node **cur = &head->next; // current 
	Node *tmp = NULL;
	Node *next = head->next;
	while (cur) {
		*cur = tmp;
		tmp = next;
		next = next->next;
		cur = &(*cur)->next;
	}
}

如何測試？
head -> 1 -> 2 -> 3 ->
          ^
shorter and faster
3 -> 2 -> 1

Q5:複雜度 大 O、小 o 的定義

return type?
重視細節！

https://hackmd.io/@sysprog/it-vocabulary

誠實面對自己
待辦事項

• TODO: 回答上述 Q1 到 Q5

回覆會議問答記錄 - 完整版

Q4: 比照 remove_list_node 撰寫 find_node / reverse_nodes，利用 indirect pointer (no external allocated memory. i.e., constant space complexity)，如何驗證？

bool find_node(List *list, Node *target) 
{
    Node **indirect = &list->head;
    while (*indirect != NULL) {
        if (*indirect == target) {
            return true;
        }
        indirect = &(*indirect)->next;
    }
    return false;
}

以下程式碼的缺陷:

1. 參數 List *list 指定單向鏈結串列的開頭，當完成反轉所有節點後，鏈結串列的開頭會發生改變，但呼叫該函式的人卻無從知悉新的開頭是什麼

   是，當完成反轉所有節點後 list->head 所指向的節點會不一樣，不過呼叫該函式的人是傳入 list 的位址，也就是說這函式是更改的 list->head 與原先（於 main() 中的） list->head 是同一塊記憶體空間，所以照理講呼叫該函式的人應該能夠取得更新後的 list->head (開頭)？

   ​​​​typedef struct Node {
   ​​​​    int data;
   ​​​​    struct Node* next;
   ​​​​} Node;
   
   ​​​​typedef struct {
   ​​​​    struct Node* head;
   ​​​​} List;
   

2. 當鏈結串列僅有一個節點時 (即 singular)，不用繼續操作

   新增 !list->head->next 的判斷。

3. 未依循指定的程式碼縮排風格 (類似 Linux 核心)

   已更正

void reverse_node(List *list) 
{
    if (!list || !list->head || !list->head->next)
        return;
    
    Node **cur = &list->head;
    Node *prev = NULL;
    Node *next = NULL;

    while (*cur) {
        next = (*cur)->next;
        (*cur)->next = prev;
        prev = *cur;
        *cur = next;
    }

    *cur = prev;
}

驗證方法一：畫圖追蹤程式碼

將必要指標初始化：

使用 while 迴圈將每個 Node 之 next 指標往前一個 Node 指：

最後，將 head 指到最末端的節點：

驗證方法二：寫出完整程式碼來跑，並印出結果

完整測試程式碼

#include <stdio.h>
#include <stdbool.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

typedef struct {
    struct Node* head;
} List;

bool find_node(List *list, Node *target) {
    Node **indirect = &list->head;
    while (*indirect != NULL) {
        if (*indirect == target) {
            return true;
        }
        indirect = &(*indirect)->next;
    }
    return false;
}

void reverse_node(List *list) {
    if (!list || !list->head) {
        return;
    }
    
    Node **cur = &list->head;
    Node *prev = NULL;
    Node *next = NULL;

    while (*cur) {
        next = (*cur)->next;
        (*cur)->next = prev;
        prev = *cur;
        *cur = next;
    }

    *cur = prev;
}

void print_list(List *list) {
    Node *cur = list->head;
    while (cur != NULL) {
        printf("%d -> ", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}

int main() {
    Node node4 = {4, NULL};
    Node node3 = {3, NULL};
    Node node2 = {2, &node3};
    Node node1 = {1, &node2};

    List list = {.head = &node1};
    printf("list: ");
    print_list(&list);
    printf("Find 2: %s\n", find_node(&list, &node2) ? "Found" : "Not Found");
    printf("Find 4: %s\n", find_node(&list, &node4) ? "Found" : "Not Found");
    
    reverse_node(&list);
    printf("Reverse list: ");
    print_list(&list);

    return 0;
}

預期輸出結果：

jimmy@NEAT:~/linux2025$ ./test_list 
list: 1 -> 2 -> 3 -> NULL
Find 2: Found
Find 4: Not Found
Reverse list: 3 -> 2 -> 1 -> NULL