# 2025q1 Homework5 (assessment)
contributed by < `JimmyChongz` >

## 閱讀〈[因為自動飲料機而延畢的那一年](https://blog.opasschang.com/the-story-of-auto-beverage-machine-1)〉的啟發

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

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

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

:::info
對 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 的網路<s>協議</s>協定堆疊，但有點<s>抽象</s>難以理解，還是<s>不太懂</s>不懂。
:::

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

:::spoiler 會議紀錄
- [Homework5](https://hackmd.io/@Jimmy-Xu/linux2025-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](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](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](https://en.wikipedia.org/wiki/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](https://hackmd.io/@sysprog/it-vocabulary)

誠實面對自己
待辦事項
- TODO: 回答上述 Q1 到 Q5
:::
## [回覆會議問答記錄 - 完整版](https://hackmd.io/@Jimmy-Xu/0514qa)
### 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;
}

:::danger
以下程式碼的缺陷:
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 指到最末端的節點：

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

#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