---
# System prepended metadata

title: 2021q1 Homework1 (lab0)
tags: [linux2022]

---

# 2021q1 Homework1 (lab0)
contributed by < `hankluo6` >
> 延續 [2020q3 Homework1(lab0)](https://hackmd.io/@hankluo6/2020q3-lab0),  [2021q1 Homework1(lab0)](https://hackmd.io/@hankluo6/2021q1-lab0) 的開發
>
> [GitHub](https://github.com/hankluo6/lab0-c)

## 環境

```shell
$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0

$ lscpu
Architecture:        x86_64
CPU op-mode(s):      32-bit, 64-bit
Byte Order:          Little Endian
CPU(s):              1
On-line CPU(s) list: 0
Thread(s) per core:  1
Core(s) per socket:  1
Socket(s):           1
NUMA node(s):        1
Vendor ID:           GenuineIntel
CPU family:          6
Model:               158
Model name:          Intel(R) Core(TM) i5-8300H CPU @ 2.30GHz
Stepping:            10
CPU MHz:             2304.002
BogoMIPS:            4608.00
Hypervisor vendor:   KVM
Virtualization type: full
L1d cache:           32K
L1i cache:           32K
L2 cache:            256K
L3 cache:            8192K
NUMA node0 CPU(s):   0
```

    
### Queue implementation

#### `q_new`
```c
struct list_head *q_new()
{
    struct list_head *q = malloc(sizeof(struct list_head));
    if (!q)
        return NULL;
    INIT_LIST_HEAD(q);
    return q;
}
```
利用  `INIT_LIST_HEAD` 初始化 list_head 當作 queue 的 head。

#### `q_insert_head`
```c
bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *e = malloc(sizeof(element_t));
    if (!e)
        return false;
    e->value = strdup(s);
    if (!e->value) {
        free(e);
        return false;
    }
    list_add(&e->list, head);

    return true;
}
```
分配 `element_t` 的空間並將字串存入，再與 queue 連接。

#### `q_insert_tail`
```c
bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *e = malloc(sizeof(element_t));
    if (!e)
        return false;
    e->value = strdup(s);
    if (!e->value) {
        free(e);
        return false;
    }
    list_add_tail(&e->list, head);

    return true;
}
```
同 `q_insert_head`。

#### `q_remove_head`
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *e = list_entry(head->next, element_t, list);
    list_del(head->next);
    if (sp) {
        strncpy(sp, e->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return e;
}
```
利用 `list_entry` 取得第一個 element，並把資料放入 `sp`。

#### `q_remove_tail`
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    return q_remove_head(head->prev->prev, sp, bufsize);
}
```
取得 tail 的前一個元素，便能利用 `q_remove_head` 來移除。

#### `q_size`
```c
int q_size(struct list_head *head)
{
    if (!head)
        return 0;

    int len = 0;
    struct list_head *li;

    list_for_each (li, head)
        len++;
    return len;
}
```

#### `q_delete_mid`
```c
bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    if (!head || list_empty(head))
        return false;
    struct list_head *fast = head->next;
    struct list_head *slow = head->next;
    while (fast != head && fast->next != head) {
        fast = fast->next->next;
        slow = slow->next;
    }
    list_del(slow);
    q_release_element(list_entry(slow, element_t, list));
    return true;
}
```
運用 [Floyd's Algorithm](https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_tortoise_and_hare) 的 fast and slow pointer 的方法找出中間元素，再移除即可。

#### `q_delete_dup`
```c
bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head || list_empty(head))
        return false;
    struct list_head *e;
    list_for_each (e, head) {
        struct list_head *next = e->next;
        bool dup = false;
        while (next != head &&
               !strcmp(list_entry(e, element_t, list)->value,
                       list_entry(next, element_t, list)->value)) {
            list_del(e);
            q_release_element(list_entry(e, element_t, list));
            e = next;
            next = e->next;
            dup = true;
        }
        if (dup) {
            list_del(e);
            q_release_element(list_entry(e, element_t, list));
            e = next;
        }
    }
    return true;
}
```
遍歷整個 queue，並再迴圈中檢查當前元素與下一個元素是否相同，並持續移除下個元素，最後把當前元素也移除便能刪除所有相同的元素。

#### `q_swap`
```c
void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (!head || list_empty(head))
        return;
    struct list_head *e;
    list_for_each (e, head) {
        if (e->next == head)
            break;
        struct list_head *next = e->next;
        list_del(e);
        list_add(e, next);
    }
}
```
遍歷 queue 時兩兩交換即可。

#### `q_reverse`
```c
void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    struct list_head *prev, *iter, *rear;
    for (prev = head, iter = head->next, rear = iter->next; iter != head;) {
        iter->prev = rear;
        iter->next = prev;
        prev = iter;
        iter = rear;
        rear = rear->next;
    }
    head->next = prev;
    head->prev = rear;
}
```
利用三個 pointer 分別指向 prev, current, next 元素，在遍歷時持續更改指標指向。

#### `q_sort`
```c
void merge_sort(struct list_head **head)
{
    if (!(*head) || !(*head)->next)
        return;
    struct list_head *fast = (*head)->next;
    struct list_head *slow = *head;
    while (fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
    }
    fast = slow->next;
    slow->next = NULL;

    struct list_head **front = head;
    struct list_head **back = &fast;

    merge_sort(front);
    merge_sort(back);

    struct list_head *newh = NULL;
    struct list_head **tmp = &newh;
    while (*front && *back) {
        element_t *f = list_entry(*front, element_t, list);
        element_t *b = list_entry(*back, element_t, list);
        if (strcmp(f->value, b->value) < 0) {
            *tmp = *front;
            *front = (*front)->next;
        } else {
            *tmp = *back;
            *back = (*back)->next;
        }
        tmp = &((*tmp)->next);
    }
    if (*front)
        *tmp = *front;
    else if (*back)
        *tmp = *back;
    *head = newh;
}

void q_sort(struct list_head *head)
{
    if (q_size(head) < 2)
        return;
    head->next->prev = NULL;
    head->prev->next = NULL;
    merge_sort(&head->next);
    struct list_head *e, *prev;
    for (e = head->next, prev = head;; prev = e, e = e->next) {
        if (!e) {
            head->prev = prev;
            prev->next = head;
            break;
        }
        e->prev = prev;
    }
}
```
使用 merge sort 作為排序，使用 pointer to pointer 可以避免 merge 完需要回傳 node，在 merge 過程只有建立 `next` 連接，故在 `q_sort` 內需重新設定 `prev` 指標。

    
### Queue Shuffle
```c
void q_shuffle(struct list_head *head)
{
    int len = q_size(head);
    
    if (len <= 1)
        return;

    struct list_head *node, *tmp, *last = head->prev;
    while (--len) {
        int r = rand() % (len + 1);

        list_for_each(node, head) {
            if (!r)
                break;
            r--;
        }
        tmp = node->prev;
        list_del(node);
        list_add(node, last);
        list_del(last);
        list_add(last, tmp);
        last = node->prev;
    }
}
```

### Web Implementatiton

[先前方法](https://hackmd.io/@hankluo6/2021q1-lab0#%E6%95%B4%E5%90%88-tiny-web-server-%E8%87%B3-lab0)使用 `cmd_select` 接收資料，需要將 linenoise 關閉，且 `cmd_select` 似乎專門用於 source 讀檔專用，故改採用更改 linenoise 讀取的方式來接收 web 傳來的訊息。

```diff
static int linenoiseEdit(...)
{
     ...
     linenoiseHistoryAdd("");

     if (write(l.ofd, prompt, l.plen) == -1)
         return -1;
     while (1) {
         signed char c;
         int nread;
         char seq[3];

+        if (listenfd != -1) {
+            fd_set set;
+            FD_ZERO(&set);
+            FD_SET(listenfd, &set);
+            FD_SET(stdin_fd, &set);
+            int rv = select(listenfd + 1, &set, NULL, NULL, NULL);
+            struct sockaddr_in clientaddr;
+            socklen_t clientlen = sizeof clientaddr;
+            int connfd;
+
+            switch (rv) {
+            case -1:
+                perror("select"); /* an error occurred */
+                continue;
+            case 0:
+                printf("timeout occurred\n"); /* a timeout occurred */
+                continue;
+            default: 
+                if (FD_ISSET(listenfd, &set)) {
+                    connfd = accept(listenfd,(SA *) &clientaddr, &clientlen);
+                    char *p = process(connfd, &clientaddr);
+                    strncpy(buf, p, strlen(p) + 1);
+                    close(connfd);
+                    free(p);
+                    return strlen(p);
+                } else if (FD_ISSET(stdin_fd, &set)) {
+                    nread = read(l.ifd, &c, 1);
+                    if (nread <= 0)
+                        return l.len;
+                }
+                break;
+            }
+        } else {
            nread = read(l.ifd, &c, 1);
            if (nread <= 0)
                return l.len;
+       }
    ...
    }
}
```

將 web 使用的 filedescription 以及 stdin 使用的 file desciption 都加到 `set` 當中，便能使用 [`select`](https://man7.org/linux/man-pages/man2/select.2.html) 判斷目前接收到的資料來源，`FD_ISSET` 判斷哪個 fd 被設置，如果為 `listenfd` 表示收到 web 端傳來的資料，如果為 `stdin_fd` 則表示為使用者輸入端傳來的資料。

TODO Coroutine

### termios

TODO



###### tags: `linux2022`