Try   HackMD

2023q1 Homework1 (quiz1)

測驗一

給定 list.h 作為〈linked list 和非連續記憶體操作〉提及的 Linux 核心風格 circular doubly-linked list 實作，欲處理的節點採用以下結構體:

#include <stdint.h>
#include "list.h"

struct item {                         
    uint16_t i;
    struct list_head 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;
}

以下程式碼實作快速排序法，數值由小到大排列，並確保可達到 stable sorting 的目標。

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

請補完，使其行為符合預期。作答規範:

  • AAA, BBB, CCC, DDD, EEE, FFF 應以最簡潔的形式撰寫，且符合作業一排版規範 (近似 Linux 核心程式碼排版風格)，均不包含小括號 (即 ( 和 ))，且不可出現 , 和 ; 這樣的分隔符號 (separator)
  • BBB 為 identifier
  • CCC, DDD, EEE, FFF 均為以 list_ 開頭的巨集 (macro)

程式碼原理

  1. 首先先來看 list_first_entry 此巨集的參數，為 list_first_entry(head, type, member) ，可知 AAA 會是 type of the entry，即為 item ， BBB 則是 member variable ， item member variable 有兩種，為 uint16_t i 與 struct list_head list; ，而 pivot 要取得 list 的第一個位置，所以 BBB 即為 list。

  2. CCC (itm, is, head, list) 為含有 4 個參數的巨集，且排序法須對每個節點走訪，所以 CCC 即為 list_for_each_entry_safe 。

  3. 再迴圈中使用 cmpint 來比大小，比 pivot 小的節點接到 list_less 後面，比 pivot 大的節點接到 list_greater 後面，所以 DDD 與 EEE 皆為 list_move 。

  4. 最後將 pivot, list_less, list_greater 串起來，list_greater 要串接在 list 後面，所以 FFF 即為 list_splice_tail 。

答案

  • AAA = item
  • BBB = list
  • CCC = list_for_each_entry_safe
  • DDD = list_move
  • EEE = list_move
  • FFF = list_splice_tail

程式碼

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, item, list);
    list_del(&pivot->list);

    struct item *itm = NULL, *is = NULL;
    list_for_each_entry_safe (itm, is, head, list) {
        if (cmpint(&itm->i, &pivot->i) < 0)
            list_move (&itm->list, &list_less);
        else
            list_move (&itm->list, &list_greater);
    }

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

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

測驗二

延續上方測驗 1，參考 Optimized QuickSort — C Implementation (Non-Recursive)，將以下程式碼改寫為非遞迴 (non-recursive; iterative) 的實作:

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

程式碼原理

  1. GGGG (itm, is, head, list) 為含有 4 個參數的巨集，且排序法須對每個節點走訪，所以 GGGG 即為 list_for_each_entry_safe 。

  2. 再進入迴圈前，會先將 inpur list ，也就是 stack[0] 接在 partition 後，當 partition 不為空也不為單時，會初始化 list_less 與 list_greater ，並將比 pivot 小的節點接到 list_less 後面，比 pivot 大的節點接到 list_greater 後面，而 HHHH (&pivot->list, &list_less); ，因為 pivot 比 list_less 都還大，故應將 pivot 接在list_less 後，所以 HHHH 即為 list_add_tail 。

  3. 此時分類完的list_greater 與 list_less 應放入 stack 中，，此時 top = -1; ，所以應先將 top++; ，再將 list_greater 與 list_less 個別放入 stack 裡，所以綜合以上兩步驟， IIII 與 JJJJ 即為 stack[++top] 。

  4. 若 partition 為空或為單，則進入 else 裡面，若 partition 有一個值，那必定是最小值，將這個值放入最上層的 stack 裡，並將該值接到 head 後面，而 top 會指向下一層，所以須做 top--; ，綜合以上兩步驟，可知 KKKK 即為 stack[top--] 。

答案

  • GGGG = list_for_each_entry_safe
  • HHHH = list_add_tail
  • IIII = stack[++top]
  • JJJJ = stack[++top]
  • KKKK = stack[top--]

程式碼

#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;
            list_for_each_entry_safe (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_add_tail (&pivot->list, &list_less);
            if (!list_empty(&list_greater))
                list_splice_tail(&list_greater, stack[++top]);
            if (!list_empty(&list_less))
                list_splice_tail(&list_less, stack[++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(stack[top--]);
                list_add_tail(&tmp->list, head);
            }
        }
    }
}

測驗三

XOR 運算特性:

A⊕A=0
A⊕0=A
A⊕1=¬A
(A⊕B)⊕B=A

以下程式碼是個 XOR linked list 的實作，在這樣的資料結構可表示為:

       1    2    3    4
data  HAT  CAT  EAT  BAT
link   2    2    6    3

要往下一格移動時，我們需要前一格在哪和這一格的位置。例如我們現在在 HAT (1), 已知前一格是 (0)，那麼下一格就是 link(1) XOR 0 = 2 XOR 0 = 2，也就是 CAT。繼續，現在位於 CAT (2)，前一格在 (1)，於是下一格就是 link(2) XOR 1 = 2 XOR 1 = 3，亦即 EAT，依此類推。只要當找出來的下一格是 (0) 就結束。

XOR linked list 的優勢在於空間的佔用更精簡，與尋常作法相比，佔用的儲存空間比值會趨近 67%

。

以下是學習 Linux 核心 list.h 風格的 XOR linked list 實作，其中 ## 為 C 語言前置處理器，參見 你所不知道的 C 語言：前置處理器應用篇

參考執行輸出：

xorlist_for_each test
node [0] 999
node [1] 998
node [2] 997
...
node [996] 2
node [997] 1
node [998] 0

程式碼列表:

#include <assert.h>
#include <errno.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

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;

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

static inline xor_node_t *address_of(xor_node_t *n1, xor_node_t *n2)
{
    assert(n1 && n2);
    return XOR_COMP(n1, n2);
}

#define container_of(ptr, type, member)                            \
    __extension__({                                                \
        const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
        (type *) ((char *) __pmember - offsetof(type, member));    \
    })

#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)

#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)

#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)

#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)

/* Note that when the delete function success is must return 0. */
#define xorlist_delete_prototype(name, node) \
    int _xorlist_delete_##name(xor_node_t *node)

#define xorlist_delete_call(name) _xorlist_delete_##name

static inline xor_node_t *xornode_init(xor_node_t *n)
{
    assert(n);
    n->cmp = NULL;
    return n;
}

#define XORNODE_INIT(n) \
    do {                \
        (n).cmp = NULL; \
    } while (0)

#define XORLIST_INIT(h)           \
    do {                          \
        (h).head.cmp = &(h).tail; \
        (h).tail.cmp = &(h).head; \
        (h).count = 0;            \
    } while (0)

int xorlist_add(xor_list_t *list, xor_node_t *n)
{
    xor_node_t *real_next;

    if (!n)
        return ENOMEM;

    xor_node_t *real_prev = &list->head;
    xor_node_t *node = real_prev->cmp;
    if (node == &list->tail)
        real_next = MMMM;
    else
        real_next = node;
    real_prev->cmp = n;
    n->cmp = XOR_COMP(real_prev, real_next);
    real_next->cmp = XOR_COMP(n, XOR_COMP(real_prev, PPPP));
    list->count++;

    return 0;
}

int xorlist_del(xor_list_t *list,
                xor_node_t *n,
                xor_node_t *target,
                int (*delete_func)(xor_node_t *))
{
    assert(list && n && target && delete_func);
    assert(&list->head != target && &list->tail != target);
    xor_node_t *nn = address_of(target, n->cmp);
    xor_node_t *an = address_of(n, target->cmp);
    xor_node_t *ana = address_of(target, an->cmp);
    n->cmp = XOR_COMP(nn, an);
    an->cmp = XOR_COMP(n, ana);
    delete_func(target);
    list->count--;

    return 0;
}

int xorlist_destroy(xor_list_t *list, int (*delete_func)(xor_node_t *))
{
    assert(delete_func);

    xor_node_t *real_prev = &list->head;
    xor_node_t *node = real_prev->cmp;
    xor_node_t *real_next = address_of(real_prev, node->cmp);
    xor_node_t *tmp = real_prev;
    real_prev = node;
    node = real_next;

    while (node != &list->tail) {
        real_next = address_of(real_prev, node->cmp);
        tmp = real_prev;
        real_prev = node;
        node = real_next;

        if (delete_func(tmp) != 0)
            perror("delete function failed");
    }

    return 0;
}

struct test_node {
    int value;
    xor_node_t xornode;
};

xorlist_delete_prototype(test_delete, _node)
{
    struct test_node *node = container_of(_node, struct test_node, xornode);
    free(node);
    return 0;
}

int main(void)
{
    xor_list_t list;
    xor_node_t *p1, *p2;

    XORLIST_INIT(list);
    for (int i = 0; i < 1000; i++) {
        struct test_node *new = malloc(sizeof(struct test_node));
        xornode_init(&new->xornode);
        new->value = i;
        xorlist_add(&list, &new->xornode);
        if (i == 5)
            p1 = &new->xornode;
        if (i == 6)
            p2 = &new->xornode;
    }

    xor_node_t *real_prev, *real_next, *node;
    int i = 0;
    printf("xorlist_for_each test\n");
    xorlist_for_each(node, real_prev, real_next, &list)
    {
        printf("node [%d] %d\n", i++,
               container_of(node, struct test_node, xornode)->value);
    }

    i = 0;
    printf("xorlist_for_from test\n");
    xorlist_for_each_from(node, p1, p2, real_prev, real_next, &list)
    {
        printf("node %d\n",
               container_of(node, struct test_node, xornode)->value);
    }

    i = 0;
    printf("xorlist_for_each_from_prev test\n");
    xorlist_for_each_from_prev(node, p1, p2, real_prev, real_next, &list)
    {
        printf("node [%d] %d\n", i++,
               container_of(node, struct test_node, xornode)->value);
    }

    i = 0;
    printf("xorlist_for_each_prev test\n");
    xorlist_for_each_prev(node, real_prev, real_next, &list)
    {
        printf("node [%d] %d\n", i++,
               container_of(node, struct test_node, xornode)->value);
    }

    printf("xorlist_del test\n");
    xorlist_del(&list, p2, p1, xorlist_delete_call(test_delete));
    i = 0;
    xorlist_for_each(node, real_prev, real_next, &list)
    {
        printf("node [%d] %d\n", i++,
               container_of(node, struct test_node, xornode)->value);
    }

    xorlist_destroy(&list, xorlist_delete_call(test_delete));

    return 0;
}

請補完程式碼，使其運作符合預期。作答規範:

  • LLLL 為表示式，在運算子前後要一個空白字元區隔，應包含 uintptr_t，符合 lab0-c 預期的排版風格
  • MMMM 和 PPPP 為表示式

程式碼原理

       1    2    3    4
data  HAT  CAT  EAT  BAT
link   2    2    6    3

  1. 以上例為例，現在位於 CAT (2)，前一格在 (1)，於是下一格就是 link(2) XOR 1 = 2 XOR 1 = 3，亦即 EAT，也就是說：前一格 XOR link = 下一格，而 前一格 XOR 下一格 = link ，所以只要 link 存的是 前一格 XOR 下一格 的值，我們就能用前一格與 link 的值去找到下一格，所以也不難看出 struct _xorlist_node *cmp; 存的是 link 的值，在函式 xorlist_add 中的 n->cmp = XOR_COMP(real_prev, real_next); 就是要將 link 值放入 cmp 中，所以 #define XOR_COMP(a, b) ((xor_node_t *) (LLLL)) 中的 LLLL 為將兩個值做 XOR ，即為 (uintptr_t)(a) ^ (uintptr_t)(b) 。

  2. 在函式 xorlist_add 中，目的是將節點 n 加入到 list 中，當 n 為最後的節點時，它的下一個節點即為自己，因為自己 XOR 自己 = 0，也就是下一格，所以 MMMM 為 &list->tail 。

  3. real_next->cmp = XOR_COMP(n, XOR_COMP(real_prev, PPPP)); ，節點 n 的下一個節點的 link 值即為 前一格 XOR 下一格，也就是 n XOR real_next->next ，而下一格可以從 前一格 XOR 自己本身的 link 值取得，所以 PPPP 為自己本身的 link 值，也就是 real_next->cmp 。

答案

  • LLLL = (uintptr_t)(a) ^ (uintptr_t)(b)
  • MMMM = &list->tail
  • PPPP = real_next->cmp
Last changed by 
 
Tonr01
0
308

Read more

2023q1 Homework1 (lab0)

contributed by &lt; Tonr01 &gt;

May 11, 2025
2023q1 Linux核心設計-問題紀錄

__asm__ __volatile__(&quot;&quot;: : :&quot;memory&quot;); 的功用

Jun 23, 2023
2023q1 Homework6 (quiz5)

2023q1 Homework6 (quiz5) 測驗一 程式碼原理 Basic data structure typedef struct block { int size; /**&lt; Size of the data payload */ struct block *prev, *next; /**&lt; Pointer to the previous/next block */ } block_t; block 為每塊可使用區塊的 metadata ，其中紀錄每個區塊的大小及前一個與後一個區塊的 link。

May 14, 2023
2023q1 Homework5 (Assessment)

contributed by &lt; Tonr01 &gt;

May 9, 2023
Read more from Tonr01
Published on HackMD