2020q3 Homework1 (quiz1)

contributed by < grb72t3yde >

tags: sysprog2020

---

測驗題目

• 2020q3 第 1 週測驗題

程式運作原理解釋

add entry函式

• 在此函式中, 我想解釋 a pointer to a pointer 的引數如何直接對list進行操作; 因此, 我使用gdb追蹤兩個node的插入行為, 並搭配Graphviz圖像化呈現

1. 首先, 我們在 main function 中的第一個 add_entry(&head, 72); call (line 7), step into 進去看

int main(int argc, char const *argv[])
{
    node_t *head = NULL;

    print_list(head);

    add_entry(&head, 72);
    add_entry(&head, 101);
    ...

void add_entry(node_t **head, int new_value)
{
    node_t **indirect = head;

    node_t *new_node = malloc(sizeof(node_t));
    new_node->value = new_value;
    new_node->next = NULL;

    assert(new_node); //AA1
    while (*indirect)
        indirect = &(*indirect)->next;
    *indirect = new_node; //AA2
}

進到函式內node_t **indirect = head;這行時發現head以及其dereference如下:

此時狀況以圖形呈現如下, 其中add_entry中的head的位址位於0x7fffffffdc48

2. 接著觀察 new_node 在 malloc 並將 new_value copy 進去後 (line 5, 6, 7)的情況

新配置的間位址在 0x5555555596b0; value 已經被assigned為72, 且 next 指向 NULL, 如下圖:

3. 由上圖得知, 對 indirect 做 dereference 會得到 main:head 指標, 且其原先指向NULL; 因此第一次插入會直接從 while loop 跳出, 將* indirect指向new_node所指向的位址 (i.e. 0x5555555596b0) 以完成插入, 如下圖:

4. 繼續追蹤add_entry(&head, 101);, step into進去看

發現malloc為new_node指標配置了別的位址 0x5555555596d0, add_entry:head依然指向由引數傳入的reference
5. 此時indirect為TRUE, 進入while loop body, 來看一下 indirect = &(*indirect)->next; 有什麼作用:

注意此處將indirect dereference得到 0x5555555596b0, 再以->取得next屬性, 最後用reference of運算子, 變成如下圖:

6. 最後一樣用 indirect得到next來將其指向新空間, 完成插入

remove entry函式

問題

• assert(new_node)在 AA1 才做可能造成第六, 七行的 NULL pointer dereference?