---
# System prepended metadata

title: 2025q1 Homework2 (quiz1+2)
tags: [linux2025]

---

# 2025q1 Homework2 (quiz1+2)

contributed by < PigeonSir >

## w1 測驗 1
運用  "a pointer to a pointer" 技巧操作單向的鏈結串列，其中基本的結構體如下

```graphviz
digraph queue_context {
    rankdir=TB;
    node [shape=plaintext];

    queue1 [label=<
        <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
            <TR><TD COLSPAN="1" BGCOLOR="lightgray"><B>    list_t    </B></TD></TR>
            <TR><TD PORT="n">next</TD></TR>
        </TABLE>
    >];

    queue2 [label=<
        <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
            <TR><TD PORT="p" COLSPAN="2" BGCOLOR="lightgray"><B>   list_item_t    </B></TD></TR>
            <TR><TD>value</TD><TD PORT="n">next</TD></TR>
        </TABLE>
    >];

    nullNode [label="NULL", shape=none];
    queue1:n -> queue2:p [constraint=false];
    queue2:n -> nullNode [weight=0, minlen=2, constraint=false];
}
```
### insert before
```c
static inline void list_insert_before(list_t *h, list_item_t *before, list_item_t *item)
{
    list_item_t **p;
    for (p = &h->head; *p != before; p = &(*p)->next)
        ;
    *p = item;
    item->next = before;
}
```
利用 p 做為指標的指標，指向當前節點的 next 的地址，對 p 執行 deference 可得到下一個節點的地址
與沒有使用指標的指標技巧的作法比較 :
```c
static inline void list_insert_before(list_t *h, list_item_t *before, list_item_t *item)
{
    lsit_item_t *cur, *prev;
    for (cur = h->head; cur != before; prev = cur, cur = cur->next)
        ;
    prev->next = item;
    item->next = cur;
}
```
使用 "a pointer to a pointer" 技巧後就不需要使用額外的指標紀錄拜訪過的節點 (prev)
### 測試程式
#### my_assert
```c
#define my_assert(test, message) \
    do {                         \
        if (!(test))             \
            return message;      \
    } while (0)
```
定義 my_assert 宏用於觀察執行時遭遇的錯誤，這裡有一個疑問是為何要使用到 do while ，
### 圖例
要插入 node2 於 node3 以前
```graphviz
digraph g{
    rankdir=LR;
    node [shape=record];
    l [label = "{<data>h |<ref>}"];
    1 [label = "{<head>node 1} | {<data>1 |<ref>}"];    
    2 [label = "{<head>node 3} |{<data>3 |<ref>}"];
    3 [label = "{<head>node 2} | {<data>2 |<ref>}"];
    node [shape=none]
    p;
    before;
    edge[weight=2];
    l:ref:c -> 1:head [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    1:ref:c -> 2:head [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    2:ref:c -> NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    edge[weight=1];
    p -> l:ref:s;
    edge[weight=1]
    before -> 2:head:n;
    { rank=max; 3;}
}
```
走訪鏈結串列直到 `*p == before` 時跳出迴圈，此時 p 紀錄的為 node1 中 next 的地址
```graphviz
digraph g{
    rankdir=LR;
    node [shape=record];
    l [label = "{<data>h |<ref>}"];
    1 [label = "{<head>node 1} | {<data>1 |<ref>}"];    
    2 [label = "{<head>node 3} |{<data>3 |<ref>}"];
    3 [label = "{<head>node 2} | {<data>2 |<ref>}"];
    node [shape=none]
    p;
    before;
    edge[weight=2];
    l:ref:c -> 1:head [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    1:ref:c -> 2:head [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    2:ref:c -> NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    edge[weight=1];
    p -> 1:ref:s;
    edge[weight=1]
    before -> 2:head:n;
    { rank=max; 3;}
}
```
更新 *p (即 node1 的 next) 為 node2 ，最後再將 node3 接上於 node2 後便完成
```graphviz
digraph g{
    rankdir=LR;
    node [shape=record];
    l [label = "{<data>h |<ref>}"];
    1 [label = "{<head>node 1} | {<data>1 |<ref>}"];    
    3 [label = "{<head>node 3} |{<data>3 |<ref>}"];
    2 [label = "{<head>node 2} | {<data>2 |<ref>}"];
    node [shape=none]
    p;
    before;
    null; // NULL 仍然保留作為節點名稱

    edge[weight=2];
    l:ref:c -> 1:head [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    1:ref:c -> 2:head [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    2:ref:c -> 3:head [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    3:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];

    edge[weight=1];
    p -> 1:ref:s;
    edge[weight=1]
    before -> 3:head:n;

    { rank=max; null; } // 這行將 null 設為最右側
}

```
## W1 測驗 2