# 2021q1 Homework2 (quiz2)
contributed by < [bobhsiao0306](https://github.com/bobhsiao0306) >
> [GitHub repository](https://github.com/bobhsiao0306/linux2021_quiz2)

###### tags: `linux2021` `quiz2`

## 測驗 1
在 main() 函式中，首先先將 `cities.txt` 中讀到的每一行利用 ==q_insert_head== 新增至 queue 的頂端

### q_insert_head

bool q_insert_head(queue_t *q, char *s)
{
    if (!q) return false;

    list_ele_t *newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;

    char *new_value = strdup(s);
    if (!new_value) {
        free(newh);
        return false;
    }

    newh->value = new_value;
    newh->next = q->head;
    q->head = newh;
    if (q->size == 0)
        q->tail = newh;
    q->size++;
    list_add_tail(&newh->list, &q->list);

    return true;
}

而 ==q_insert_head== 則是利用 ==list_add_tail== 新增的節點加入 doubly linked list 的尾端

### list_add_tail

    digraph {
        rankdir=LR
        node [shape="box"]
        edge [dir="both"]        
        left [label="..." shape="none"]
        pnode [label="head->prev"]
        nnode [label="new node", color="red"]
        head [label="head"]
        right [label="..." shape="none"]
        
        left -> pnode 
        pnode -> head [color=gray, style=dashed]
        head -> right
        pnode -> nnode -> head [color=red]
    }

> 紅色實線為新增的連結及節點，灰色虛線則為刪除的連結

### Merge Sort
接下來對先前的 doubly linked list 做 merge sort，分為三個部份
* ==list_cut_position== 函式中利用 ==get_middle== 將 doubly linked list 切成左右兩半
* 遞迴呼叫 ==list_merge_sort==
* ==list_merge== 將左右兩半排序好的 linked list 合併起來

#### get_middle

static list_ele_t *get_middle(struct list_head *list)
{
    struct list_head *fast = list->next, *slow;
    list_for_each (slow, list) {
        if (fast->next == list || fast->next->next == list)
            break;
        fast = fast->next->next;
    }
    return list_entry(slow, list_ele_t, list);
}

slow 一次前進一個節點，fast 一次前進兩個節點，而當 fast 前進至倒數第一個或倒數第二個節點時，slow 剛好會在 linked list 的中間節點

:::warning
TODO: 討論切分 list 的適當位置及比例
:notes: jserv
:::

#### `list_cut_position`
輸入為一個 doubly linked list

    digraph {
        rankdir=LR
        node [shape="box"]
        edge [dir="both"]
        head_from[label="q->list", color="red"]
        head_from_first[label="q->list->next", color="blue"]
        left [label="..." shape="none"]
        node_prev [label="slow->prev", color="blue"]
        nnode [label="slow", color="blue"]
        node_next [label="slow->next", color="red"]
        tail [label="tail", color="red"]
        right [label="..." shape="none"]
        
        head_from -> head_from_first -> left -> node_prev -> nnode -> node_next -> right -> tail -> head_from
              
    }

經過 ==list_cut_position== 後切成兩個 doubly linked list

    digraph {
        rankdir=LR
        node [shape="box"]
        edge [dir="both"]
        head_to[label="left.list", color="blue"]
        head_from[label="q->list", color="red"]
        head_from_first[label="q->list->next", color="blue"]
        left [label="..." shape="none"]
        node_prev [label="slow->prev", color="blue"]
        nnode [label="slow", color="blue"]
        node_next [label="slow->next", color="red"]
        tail [label="tail", color="red"]
        right [label="..." shape="none"]
        
        
        head_from -> node_next
        nnode -> head_to -> head_from_first
        head_from_first -> left -> node_prev -> nnode 
        node_next -> right -> tail -> head_from
              
    }

## 測驗 2
函式 func 接受一個 16 位元無號整數 N，並回傳小於或等於 N 的 power-of-2

uint16_t func(uint16_t N) {
    /* change all right side bits to 1 */
    N |= N >> 1;
    N |= N >> 2;
    N |= N >> 4;
    N |= N >> 8;

    return (N + 1) >> 1;
}

### 作法
1. 無號數N的二進位表示法中(e.g. 00101000)，使最左邊的1其右側的 bits 都變成1(e.g. 00111111)，而將N與自己右移1 bit、2 bit、4 bit、8 bit 做 or 運算即可達到此效果。
2. 加1之後再右移1 bit 即可得到小於或等於 N 的 power-of-2。