2023q1 Homework1 (quiz1)

contributed by < paul90317 >

題目連結

測驗 1

快速排序程式碼填空

static void list_sort(struct list_head *head)
{
    if (list_empty(head) || list_is_singular(head))
        return;
    
    /* 宣告左右兩 list */
    struct list_head list_less, list_greater;
    INIT_LIST_HEAD(&list_less);
    INIT_LIST_HEAD(&list_greater);
    
    /* 以第一個節點當 pivot */
    struct item *pivot = list_first_entry(head, AAA, BBB);
    list_del(&pivot->list);

    /* 大小分割 */
    struct item *itm = NULL, *is = NULL;
    CCC (itm, is, head, list) {
        if (cmpint(&itm->i, &pivot->i) < 0)
            DDD (&itm->list, &list_less);
        else
            EEE (&itm->list, &list_greater);
    }

    list_sort(&list_less);
    list_sort(&list_greater);

    list_add(&pivot->list, head);
    list_splice(&list_less, head);
    FFF(&list_greater, head);
}

list_first_entry 的輸入是節點 head，輸出是 entry 所以會用到 container_of，故 AAA 是 struct item，BBB 是 list。
CCC 是 list_for_each_entry_safe。
DDD 這個程式碼發生在 itm 比 pivot 小時發生。題目要求是該排序演算法要是 stable，所以應填入 list_add_tail。
EEE 同 DDD，也是 list_add_tail。
FFF 可以看出程式碼想要以 list_less, pivot, list_greater 建立新的 list 於 head，所以要填 list_splice_tail。

在 DDD FFF 的程式碼中，忘記把 itm 從原本的 list 中移除，正確答案應該要是 list_move_tail。
如果要填 list_add_tail，就要在分割結束串接之前加上 INIT_LIST_HEAD(head)。

參考：as200188

測驗 2

#define MAX_DEPTH 512
static void list_sort_nr(struct list_head *head)
{
    if (list_empty(head) || list_is_singular(head))
        return;

    struct list_head stack[MAX_DEPTH];
    for (int i = 0; i < MAX_DEPTH; i++)
        INIT_LIST_HEAD(&stack[i]);
    int top = -1; // top 代表最後一個 list，而非下一個
    list_splice_init(head, &stack[++top]);

    struct list_head partition;
    INIT_LIST_HEAD(&partition);
    
    /* 每次執行 statement 相當於遞迴呼叫 */
    while (top >= 0) {
        INIT_LIST_HEAD(&partition);
        
        /* 在 stack 頂部拿取一個 partition 進行排序 */
        list_splice_init(&stack[top--], &partition);
        
        /* 如果 partition 不為空 */
        if (!list_empty(&partition) && !list_is_singular(&partition)) {
            struct list_head list_less, list_greater;
            INIT_LIST_HEAD(&list_less);
            INIT_LIST_HEAD(&list_greater);
            
            /* 選取第一個節點當作 pivot */
            struct item *pivot =
                list_first_entry(&partition, struct item, list);
            list_del(&pivot->list);
            INIT_LIST_HEAD(&pivot->list);

            /* 分成大小兩邊 */
            struct item *itm = NULL, *is = NULL;
            GGGG (itm, is, &partition, list) {
                list_del(&itm->list);
                if (cmpint(&itm->i, &pivot->i) < 0)
                    list_move(&itm->list, &list_less);
                else
                    list_move(&itm->list, &list_greater);
                /* 這裡換成 list_stable 才能
                 * 達到 stable sort 的目的 */
            }
            
            /* 將 pivot 接在 list_less 後面 */
            HHHH (&pivot->list, &list_less);
            
            /* 將左右兩條 list (未經 partition) 推入 stack */
            if (!list_empty(&list_greater))
                list_splice_tail(&list_greater, IIII);
            if (!list_empty(&list_less))
                list_splice_tail(&list_less, JJJJ);
            /* 應先放入 greater 再放 less，因為下方程式碼
             * 會將 list 從頂部取出再推入 head 的尾巴 */
        
        /* 若 partition 為空或只有單一元素 */
        } else {
            /* 直接推入 stack */
            top++;
            list_splice_tail(&partition, &stack[top]);
            while (top >= 0 && list_is_singular(&stack[top])) {
                /* 當 list 只有單一節點，將 list 拿出並插入 head 尾端 */
                struct item *tmp =
                    list_first_entry(&stack[top], struct item, list);
                list_del(&tmp->list);
                INIT_LIST_HEAD(KKKK);
                list_add_tail(&tmp->list, head);
            }
        }
    }
}

GGGG 是 list_for_each_entry_safe
HHHH 是 list_add_tail
IIII 是 &stack[++top]
JJJJ 是 &stack[++top]
KKKK 是 &tmp->list

1. 解釋上方程式碼運作原理，指出設計和實作的缺失

• 在 40、42 行應該改成 list_add_tail 以達到 stable sort 的目的。
• 在 115 行應該改成 if (!list_empty(!list_empty(&partition))) 以防止將空的 list 推入並造成無窮迴圈。

測驗 3

typedef struct _xorlist_node {
    struct _xorlist_node *cmp;
} xor_node_t;

typedef struct _xor_list_struct {
    xor_node_t head, tail;
    uint32_t count;
} xor_list_t;

struct test_node {
    int value;
    xor_node_t xornode;
};

#define XOR_COMP(a, b) ((xor_node_t *) (LLLL))

根據題目說明，要把前一節點和後一節點的指標做相連，LLLL 是 a & b

#define xorlist_for_each(node, rp, rn, list)                        \
    for (rp = &(list)->head, node = rp->cmp; node != &(list)->tail; \
         rn = address_of(rp, node->cmp), rp = node, node = rn)

上方巨集迴圈初始化部分會將 node 直接指派成 list->head.cmp，這意味著第一個節點 (first entry) 不是 list->head，而是 list->head 的下一節點。
rp 是上一節點的指標，所以在迴圈迭代下一節點是 rn = address_of(rp, node->cmp)。
當 node 是 &list->tail 的時候，會跳出迴圈，因為它的容器是 xor_list_t 而非自訂義容器 struct test_node。

#define xorlist_for_each_prev(node, rp, rn, list)                   \
    for (rp = &(list)->tail, node = rp->cmp; node != &(list)->head; \
         rn = address_of(rp, node->cmp), rp = node, node = rn)

上方巨集的走訪方向與 xorlist_for_each 相反。

#define xorlist_for_each_from(node, pos1, pos2, rp, rn, list) \
    for (rp = pos2, node = pos1; node != &(list)->tail;       \
         rn = address_of(rp, node->cmp), rp = node, node = rn)

上方巨集定義了初始節點 pos2，需要再給它 pos1 以獲得下一節點。

#define xorlist_for_each_from_prev(node, pos1, pos2, rp, rn, list) \
    for (rp = pos1, node = pos2; node != &(list)->head;            \
         rn = address_of(rp, node->cmp), rp = node, node = rn)

上方巨集的走訪方向與 xorlist_for_each_from 相反。

int xorlist_add(xor_list_t *list, xor_node_t *n)
{
    /* n 的下一節點 */
    xor_node_t *real_next;

    if (!n)
        return ENOMEM;
    
    /* n 的前一節點，也就是 head */
    xor_node_t *real_prev = &list->head;
    
    /* node 是原本的第一個節點 */
    xor_node_t *node = real_prev->cmp;
    
    /* 對 n 的下一節點指派 */
    if (node == &list->tail)
        real_next = MMMM;
    else
        real_next = node;
    
    /* 將 head->cmp 直接指派為 n 因為 head 沒有前一節點 */
    real_prev->cmp = n;
    
    /* 根據定義指派 n->cmp */
    n->cmp = XOR_COMP(real_prev, real_next);
    
    /* real_next 是 node
     * node 的 cmp 是 n (node 的前一節點) 與 node 的下一節點的 xor
     * 故 XOR_COMP(real_prev, PPPP) 是 node 的下一節點
     * PPPP 是 node->cmp */
    real_next->cmp = XOR_COMP(n, XOR_COMP(real_prev, PPPP));
    list->count++;

    return 0;
}

real_next 是 n 的下一個節點，在一般的情況下它是原本的第一個節點 node，但在沒有節點時它是 tail，故 MMMM 是 &list->tail。
PPPP 是 node->cmp