2023q1 Homework1 (quiz1)

tags: 2023-linux_kernel

contributed by < JoshuaLee0321 >

第一週測驗題

測驗一

2023q1 第 1 週測驗題

題目敘述如下：

• 給定一個結構體如下

struct item {
    uint16_t i;
    struct list_head list;
};

• 是一個以 doubly linked list 串在一起的串列
• 除此之外給定了一個比較內部值的函式

static inline int cmpint(const void *p1, const void *p2)
{
    const uint16_t *i1 = (const uint16_t *) p1;
    const uint16_t *i2 = (const uint16_t *) p2;
    return *i1 - *i2;
}

而目標為利用 linux/list.h 中的 API 對快速排序法實作

• 基本上快速演算法為一種 divide and conquer 演算法，而很明顯的這個演算法就會把給定的 linked list 分為兩半來處理，除此之外還要保證 stable
• 題目code 如下：

static void list_sort(struct list_head *head)
{
    if (list_empty(head) || list_is_singular(head))
        return;

    struct list_head list_less, list_greater;
    INIT_LIST_HEAD(&list_less);
    INIT_LIST_HEAD(&list_greater);

    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);
}

• 由於知道是 quick sort，我們就可以直接填入以上AAA 到 FFF 了

• struct item *pivot = list_first_entry(head, AAA, BBB);

  • 以這行為例
  • pivot 不外乎就是快速排序法中取出pivot，而這邊直接使用 list_first_entry來取出
  • 所以 AAA 很明顯就是 item
  • BBB 就是 list

• CCC 吃四個參數，主要是為了把最前面的itm 移除掉後給list_less 或 list_greater，所以

  • CCC 為 list_for_each_entry_safe
  • DDD 為 list_move_tail
  • EEE 為 list_move_tail

• 最後的 FFF，由於是已經把 list_greater 排序好了，而很明顯這個已經排序好的 linked list 為比較大的鏈結串列，那只需要把他接在最後面，這個排序就完成了。

  • FFF 為 list_splice_tail

延伸問題

一、

二、

三、

四、

測驗二

• 給定程式碼如下：
• 找出 GGGG HHHH IIII JJJJ KKKK
• 這個程式碼，根據題目敘述，為iterative 版本的 quick sort

#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;
    list_splice_init(head, &stack[++top]);

    struct list_head partition;
    INIT_LIST_HEAD(&partition);

    while (top >= 0) {
        INIT_LIST_HEAD(&partition);
        list_splice_init(&stack[top--], &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);
            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);
            }

            HHHH (&pivot->list, &list_less);
            if (!list_empty(&list_greater))
                list_splice_tail(&list_greater, IIII);
            if (!list_empty(&list_less))
                list_splice_tail(&list_less, JJJJ);
        } else {
            top++;
            list_splice_tail(&partition, &stack[top]);
            while (top >= 0 && list_is_singular(&stack[top])) {
                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);
            }
        }
    }
}

• 我們一一來分解以上code到底在做甚麼

    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;
    list_splice_init(head, &stack[++top]);

    struct list_head partition;
    INIT_LIST_HEAD(&partition);

• 一開始這幾行都在把 stack 設定好，並且把 head 放入 &stack[0]的位置

2023/2/28 老師我想要請問為甚麼要寫

int top = -1;
list_splice_init(head, &stack[++top]);

而不是

int top = 0;
list_splice_init(head, &stack[top]);

這樣意義何在？多做一件事情不是會多消耗資源嗎?

• 後面的while 大致上可以分成
  1. 從stack 中取出需要的 partition
  2. 對partition 進行排序並且放回stack中
  3. 若從stack 中取出的partition沒有東西，則把排序好的list 放回head 中
• 知道這個基本結構之後，我們就可以來看看填空的區域了

            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);
            }

• GGGG 很明顯就是 list_for_each_entry_safe

            HHHH (&pivot->list, &list_less);
            if (!list_empty(&list_greater))
                list_splice_tail(&list_greater, IIII);
            if (!list_empty(&list_less))
                list_splice_tail(&list_less, JJJJ);

• HHHH 看起來就是要把 pivot 放入 list_less 中，而由於在 quicksort 中 pivot 會是 list_less 中最大的元素，故把他擺到 list_less 中的最後一位，也就是list_move_tail
  • 其實也可以改成 list_move(&pivot->list, &list_greater)
• IIII 跟 JJJJ 的意思為，當 list_greater 或是 list_less 中有東西的話，我就把他們擺入stack中，所以這邊應該要寫 &stack[++top] 如此一來可以保證 top往上移動並且不會撞到原本的元素

else {
            top++;
            list_splice_tail(&partition, &stack[top]);
            while (top >= 0 && list_is_singular(&stack[top])) {
                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);
            }
        }

• 最後一個部分為把 stack 中的元素放入 原本的 head 中，一一把排序好的元素放回head中。
• 很明顯的就是要把 stack[top] 的元素拿出來之後並且初始化
• 所以 KKKK 很明顯的就是 &stack[top–]

其實這四行程式碼可以省略成一行，變成以下:
list_move_tail(&stack[top--], head)

測驗三