2023q1 Homework1 (quiz1)

contributed by < PlusThousand0107 >

實驗環境

$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  12
  On-line CPU(s) list:   0-11
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz
    CPU family:          6
    Model:               158
    Thread(s) per core:  2
    Core(s) per socket:  6
    Socket(s):           1
    Stepping:            10
    CPU max MHz:         4100.0000
    CPU min MHz:         800.0000
    BogoMIPS:            4399.99

測驗 1

解釋程式碼原理

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_tail (&itm->list, &list_less);
        else
            list_move_tail (&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);
}

目的 :

實作出快速排序法，將數字由小排到大，並使其達到 stable sorting 的效果

作法 :

if (list_empty(head) || list_is_singular(head))
    return;

• list_empty 會判斷傳入的串列是否為空，而 list_is_singular 則會判斷整個串列是否只有一個元素，遇到這兩種狀況的話都會直接 return

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

• 這裡宣告了 list_less 和 list_greater ，並將它們傳給了 INIT_LIST_HEAD 做初始化

struct item *pivot = list_first_entry(head, item, list);
list_del(&pivot->list);

• 為了實作出快速排序法，需要宣告 pivot 將串列做切割，其中 list_first_entry 根據定義需傳入的三個參數分別是 head 、 item 、 list ，並回傳串列的第一個項目位址給 pivot

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

• list_for_each_entry_safe 相較於 list_for_each_entry 多了一個參數，這個參數會提供一個臨時的儲存空間，讓之後走訪需要做刪除的時後，可以安全的刪除，不對之後的走訪造成影響
• 在迴圈中會用 cmpint 對目前走訪的元素 itm 比大小，如果比 pivot 小的話就用 list_move_tail 接到 list_less 的末尾，比 pivot 大的話則會接到 list_great 的末尾

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

• 分好後則會遞迴呼叫 list_sort 來對 list_less 和 list_greater 做排序

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

• 最後再把 pivot 、 list_less 、 list_greater 接回 head
• 先用 list_add 把 pivot 加回 head ，再用 list_splice 把 list_less 接到 pivot 前面，再用 list_splice_tail 把 list_greater 從串列的末尾插入，至此，排序才算完成

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

目的 :

以非遞迴的方法實作快速排序法

作法 :

if (list_empty(head) || list_is_singular(head))
    return;

• list_empty 會判斷傳入的串列是否為空，而 list_is_singular 則會判斷整個串列是否只有一個元素，遇到這兩種狀況的話都會直接 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]);

• 宣告 stack ，大小為 512 ，用迴圈以及 INIT_LIST_HEAD 做初始化
• 設 top 為 -1 ，並用 list_splice_init 把 head 接到 stack 前

struct list_head partition;
INIT_LIST_HEAD(&partition);

測驗 3

解釋程式碼原理

#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 *) ((uintptr_t)(a) ^ (uintptr_t)(b)))

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 = node;
    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, real_next->cmp));
    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;
}

目的 :

實作出 XOR linked list

作法 :