# 2021q1 Homework1 (quiz1)
contributed by < `Shanola` >

[第一周題目](https://hackmd.io/@sysprog/linux2021-quiz1)
[GitHub程式碼](https://github.com/Shanola/NCKU-Linux2021-Quiz1)
## 測驗 `1`
### 程式碼
考慮**單向** linked list 結構，已知**無 circular**，嘗試以**遞增**順序進行 Quick sort，以下為有進行新增或修改的程式碼片段

static inline void list_concat(node_t **left, node_t *right) {
    while (*left)
        left = &((*left)->next);// LLL
    *left = right;
}

void quicksort(node_t **list)
{
    if (!*list)
        return;

    node_t *pivot = *list;
    int value = pivot->value;
    node_t *p = pivot->next;
    pivot->next = NULL;

    node_t *left = NULL, *right = NULL;
    while (p) {
        node_t *n = p;
        p = p->next;
        list_add_node_t(n->value > value ? &right/*AAA*/ : &left/*BBB*/, n);
    }

    quicksort(&left);
    quicksort(&right);

    node_t *result = NULL;
    list_concat(&result, left);
    list_concat(&result, pivot);
    list_concat(&result, right); ///CCC
    *list = result;
}

node_t *list_make_node_t(node_t *list, int value)
{
    node_t *n = malloc(1 * sizeof(node_t));
    if (!n) {
        assert(n && "malloc error");
        return NULL;
    }
    n->value = value;
    n->next = NULL;
	n->prev = NULL;
    if (!list) {
        return n;
    } else {
        node_t *tmp = list;
        while (tmp->next) {
            tmp = (tmp->next);
        }
        tmp->next = n;
		n->prev = tmp;
        return list;
    }
}

void list_free(node_t **list)
{
    if (!(*list)->next) {
        free(*list);
    } else {
        list_free(&((*list)->next));
    }
}

### 程式碼解析
首先 `list_add_node_t` 是一個沒有回傳值 (void) 且在編譯時被展開到呼叫位置 (static inline) 的函式，具有一個指向 node_t 指標的指標 `list`，及指向 node_t 的指標 `node` 兩個參數，負責**將節點加到 list 前方**：

static inline void list_add_node_t(node_t **list, node_t *node) {
    node->next = *list;
    *list = node;
}

digraph G                                                           
{ 
    rankdir=LR;
    {
		listp [label="*list"];
		listpp [label="list"];
		n [label="node"];
        node_t [shape=record,label="{<data> *node| <ref> next}"];
		list [shape=record,label="{<data> **list| <ref> next}"];
		other [shape=record,label="..."];
		n->node_t;
		listpp->listp;
		listp->list [color=blue];
		list->other
    }
	
}

digraph G                                                           
{ 
    rankdir=LR;
    {
		listp [label="*list"];
		listpp [label="list"];
		n [label="node"];
        node_t [shape=record,label="{<data> *node| <ref> next}"];
		list [shape=record,label="{<data> **list| <ref> next}"];
		other [shape=record,label="..."];
		n->node_t->list->other;
		listpp->listp;
		listp->node_t [color=red];
    }
	
}

再來 `list_concat` **負責將兩個 list 連接起來**：

static inline void list_concat(node_t **left, node_t *right) {
    while (*left)
        left = &((*left))->next;// LLL
    *left = right;
}

在這個遞迴式的 `quicksort` 函式中，會先以 list 中的第一個節點當作 pivot，將所有比 pivot 小的值連接到 `left` list 上，而比較大的則會接到 `right` list 上，然後再對這兩個 list 遞迴做 quick sort，最後再將 left, pivot, right 連接起來。

### Random 問題
`long int random(void)` 是屬於 stdlib.h 標準函式庫中的函式，該函式根據 `seed` 去 table 找大小為 31 的 long int 的序列的其中一個值來回傳，但這個 seed 若沒有被指定時會自動餵入 1，也因此使得 random 每次回傳的亂數看似是固定的。

有一個常見的解決方法是使用 `void srandom(unsigned int seed)` 來填入 seed，填入的 seed 可以用一個**隨時**變化的值(譬如時間），如此一來 random 回傳的值所屬的序列便會隨時間變換，每次回傳的值的序列也不一樣。

### Optimized q-sort
將 `__node` 結構多一個指標以指向前一個節點：

typedef struct __node {
    int value;
	struct __node *next;
	struct __node *prev;
} node_t;

有改寫過後的函式變成：
`list_make_node_t`

node_t *list_make_node_t(node_t *list, int value)
{
    node_t *n = malloc(1 * sizeof(node_t));
    if (!n) {
        assert(n && "malloc error");
		return NULL;
    }
    n->value = value;
    n->next = NULL;
	n->prev = NULL;
    if (!list) {
        return n;
    } else {
        node_t *tmp = list;
        while (tmp->next) {
            tmp = (tmp->next);
        }
        tmp->next = n;
		n->prev = tmp;
        return list;
    }
}

###### tags: `linux2021`