---
tags: linux2022
---

# 2022q1 Homework1 (lab0)
contributed by < [`qwe661234`](https://github.com/qwe661234) >

## Implement queue.c
### queue structure
Doubly-linked list and its value is string.

struct list_head {
    struct list_head *prev;
    struct list_head *next;
};

typedef struct {
    char *value;
    struct list_head list;
} element_t;

### queue_new

struct list_head *q_new()
{
    struct list_head *newh =
        (struct list_head *) malloc(sizeof(struct list_head));
    if (!newh)
        return NULL;

    INIT_LIST_HEAD(newh);
    return newh;
}

### q_insert_head
Add new queue node to the end of the list by `list_add`.

If `malloc` fails to allocate space for string that store in new node, you should free the memory of new node. Otherwise, it would cause memory leak.

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *ele = (element_t *) malloc(sizeof(element_t));
    if (!ele)
        return false;
    size_t slen = strlen(s);
    char *str = (char *) malloc((slen + 1) * sizeof(char));
    if (!str) {
        free(ele);
        return false;
    }
    strncpy(str, s, slen);
    str[slen] = '\0';
    ele->value = str;
    list_add(&ele->list, head);
    return true;
}

:::warning
Instead of `char *str = (char *) malloc((slen + 1) * sizeof(char))`, you can simply write as `char *str = malloc((slen + 1) * sizeof(char))` which is a valid C statement.
:notes: jserv
:::

### q_insert_tail
Expect for adding new queue node to the end of the list by `list_add_tail`, other operations are the same as `q_insert_head`.

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *ele = (element_t *) malloc(sizeof(element_t));
    if (!ele)
        return false;
    size_t slen = strlen(s);
    char *str = (char *) malloc((slen + 1) * sizeof(char));
    if (!str) {
        free(ele);
        return false;
    }
    strncpy(str, s, slen);
    str[slen] = '\0';
    ele->value = str;
    list_add_tail(&ele->list, head);
    return true;
}

### q_remove_head
Get first node of queue by `list_first_entry`.

Check if the buffer size - 1 is larger than the length of copy string. Otherwise, it would overflow destination buffer.

Undefined behavior for `strncpy`
1. memory dest and memory src overlap
2. one of dest and src does not point to char
3. size of dest is less than `bufsize`
4. size of src is less than size of dest, but src is not terminate with `'\0'`

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *target = list_first_entry(head, element_t, list);
    if (sp) {
        size_t slen = strlen(target->value);
        if (slen <= bufsize - 1) {
            strncpy(sp, target->value, slen);
            sp[slen] = '\0';
        } else {
            strncpy(sp, target->value, bufsize - 1);
            sp[bufsize - 1] = '\0';
        }
    }
    list_del(&target->list);
    return target;
}

### q_remove_tail
Except for getting first node of queue by `list_last_entry`, other operations are the same as `q_remove_head`.

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *target = list_last_entry(head, element_t, list);
    if (sp) {
        size_t slen = strlen(target->value);
        if (slen <= bufsize - 1) {
            strncpy(sp, target->value, slen);
            sp[slen] = '\0';
        } else {
            strncpy(sp, target->value, bufsize - 1);
            sp[bufsize - 1] = '\0';
        }
    }
    list_del(&target->list);
    return target;
}

### q_size

int q_size(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;
    int len = 0;
    struct list_head *li;
    list_for_each (li, head)
        len++;
    return len;
}

### q_delete_mid
If queue is singular, delete the only node in queue.

If queue is non-singular, use two pointer to get middle node. The first pointer is point to the first node and the second pointer is point to the last node. The first pointer iterate from the first to the the last node and the last pointer iterate oppositely. When these two pointers point to the same node or the firat pointer cross the second pointer, the node pointed by the second pointer would be the middle node.

Becasue these two pointers meet the terminal condition in the beginning, we use `do while`.

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *target;

    if (!list_is_singular(head)) {
        // More than one node in the queue
        struct list_head *front = head->next, *back = head->prev;
        do {
            front = front->next;
            back = back->prev;
        } while (front != back && front->prev != back);
        target = list_entry(front, element_t, list);
        list_del(front);
    } else {
        // Only one node in the queue
        target = list_entry(head->next, element_t, list);
        list_del(head->next);
    }
    free(target->value);
    free(target);
    return true;
}

### q_delete_dup
A queue node would be delete in two condition:
1. node value is equal to next node value
2. node value is not equal to next node value, but it is equal to previous node value.

bool q_delete_dup(struct list_head *head)
{
    if (!head)
        return false;
    bool flag = false;
    element_t *entry, *safe;
    list_for_each_entry_safe (entry, safe, head, list) {
        if (&safe->list != head && !strcmp(entry->value, safe->value)) {
            flag = true;
            list_del(&entry->list);
            free(entry->value);
            free(entry);
        } else if (flag) {
            flag = false;
            list_del(&entry->list);
            free(entry->value);
            free(entry);
        }
    }
    return true;
}

### q_swap
Iterate the queue and record the number of iterated node. If the number is even, move current node to the position which is previos to previous node.

void q_swap(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    int count = 0;
    struct list_head *node, *prev = head;
    list_for_each (node, head) {
        count++;
        if (count % 2 == 0) {
            list_move(node, prev);
            node = node->next;
            prev = node;
        }
    }
}

### q_reverse
#### Modified version:
Except for the last node, move node to the queue tail from node is previous to the last node to the first node.

This version is more concise.

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    struct list_head *cur = head->prev->prev, *next;
    while(cur != head) {
        next = cur->prev;
        list_move_tail(cur, head);
        cur = next;
    }
}

#### original version:
Change the value of pointer `*prev` and `*next` of all queue nodes and head

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    element_t *entry, *safe;
    struct list_head *tmp;
    list_for_each_entry_safe (entry, safe, head, list) {
        tmp = entry->list.prev;
        entry->list.prev = entry->list.next;
        entry->list.next = tmp;
    }
    tmp = head->next;
    head->next = head->prev;
    head->prev = tmp;
}

:::warning
By means of Linux APIs, you can shorten the above code snip.
:notes: jserv
:::

### q_sort
Sort the queue by merge sort.

I want to create another head to maintain when I divide the queue, but `malloc` is disallowed in `q_sort`. Therefore, I remove queue head and pass the first node and the last node as parameters.

Because the `mergeSort` only return the first node of sorted queue, we should iterate sorted queue to find out the last node. Then, connect removed queue head to the first node and the last node of sorted queue.

struct list_head *merge(struct list_head *l1, struct list_head *l2)
{
    struct list_head *return_head, *cur;
    if (strcmp(list_entry(l1, element_t, list)->value,
               list_entry(l2, element_t, list)->value) < 0) {
        return_head = l1;
        l1 = l1->next;
    } else {
        return_head = l2;
        l2 = l2->next;
    }
    cur = return_head;
    while (l1 && l2) {
        if (strcmp(list_entry(l1, element_t, list)->value,
                   list_entry(l2, element_t, list)->value) < 0) {
            cur->next = l1;
            l1->prev = cur;
            l1 = l1->next;
        } else {
            cur->next = l2;
            l2->prev = cur;
            l2 = l2->next;
        }
        cur = cur->next;
    }
    if (l1) {
        cur->next = l1;
        l1->prev = cur;
    } else if (l2) {
        cur->next = l2;
        l2->prev = cur;
    }
    return return_head;
}

struct list_head *mergeSort(struct list_head *head, struct list_head *tail)
{
    if (head == tail)
        return head;
    struct list_head *front = head, *back = tail;
    do {
        front = front->next;
        back = back->prev;
    } while (front != back && front->prev != back);
    if (front != back) {
        back->next = NULL;
        front->prev = NULL;
    } else {
        front = front->next;
        back->next = NULL;
        front->prev = NULL;
    }
    struct list_head *l1 = mergeSort(head, back);
    struct list_head *l2 = mergeSort(front, tail);
    return merge(l1, l2);
}

void q_sort(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    struct list_head *front = head->next, *back = head->prev;
    front->prev = NULL;
    back->next = NULL;
    front = mergeSort(front, back);
    back = front;
    while (back->next)
        back = back->next;
    head->next = front;
    front->prev = head;
    head->prev = back;
    back->next = head;
}

## Command list
All commands store in a command list, and it is a singly-linked list
### Data Structure of command list
* name: command name
* operation: do_command function
* documentation: command information show in command help

typedef struct CELE cmd_ele, *cmd_ptr;
struct CELE {
    char *name;
    cmd_function operation;
    char *documentation;
    cmd_ptr next;
};

### ADD_COMMAND Macro
`ADD_COMMAD` automatically link command `xxx` to its operation function `do_xxx`

#define ADD_COMMAND(cmd, msg) add_cmd(#cmd, do_##cmd, msg)

:::warning
You should explain why it works.
:notes: jserv
:::

### add_cmd
`cmd_list` is the head of command list

what `while` loop in funciton `add_cmd` does is sorting commands in alphabetical order. The operaion like insertion sort, find out the suit position from the head of list and insert new command element into command list.

void add_cmd(char *name, cmd_function operation, char *documentation)
{
    cmd_ptr next_cmd = cmd_list;
    cmd_ptr *last_loc = &cmd_list;
    while (next_cmd && strcmp(name, next_cmd->name) > 0) {
        last_loc = &next_cmd->next;
        next_cmd = next_cmd->next;
    }

    cmd_ptr ele = (cmd_ptr) malloc_or_fail(sizeof(cmd_ele), "add_cmd");
    ele->name = name;
    ele->operation = operation;
    ele->documentation = documentation;
    ele->next = next_cmd;
    *last_loc = ele;
}

## Add new command shuffle for qtest
### q_shuffle
Follow [the modern shuffle algorithm](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) to shuffle queue.

* Each round:
1. choose tail node and record node previous to it.
2. remove tail node.
3. generate random number, this number represent node number from `0` ~ `n - 1`
* node number of the first node of queue is `0`.
* `n` means node number of tail node.
4. find out the node that its number is equal to the random number and swap the node for tail node.
5. set tail node to recorded node.
* Terminal:
tail node is equal to the frist node

void q_shuffle(struct list_head *head)
{
    if (!head || list_empty(head))
        return;

    srand(time(NULL));
    int size = q_size(head);
    struct list_head *cur, *tail = head, *target = head->prev;
    for (int i = size - 1; i > 0; i--) {
        long random_num = rand() % i;
        cur = head->next;
        list_del(target);
        while (random_num) {
            cur = cur->next;
            random_num--;
        }
        list_move_tail(target, cur);
        list_move_tail(cur, tail);
        tail = tail->prev;
        target = tail->prev;
    }
}

### do_shuffle
When user call command shuffle, funciton `do_shuffle` would be called.

static bool do_shuffle(int argc, char *argv[])
{
    if (!l_meta.l)
        report(3, "Warning: Calling sort on null queue");
    error_check();

    int cnt = q_size(l_meta.l);
    if (cnt < 2)
        report(3, "Warning: Calling sort on single node");
    error_check();

    set_noallocate_mode(true);
    if (exception_setup(true))
        q_shuffle(l_meta.l);
    exception_cancel();
    set_noallocate_mode(false);

    bool ok = true;

    show_queue(3);
    return ok && !error_check();
}

### Add command shuffle
Function `ADD_COMAND` connect command `parameter1` to `do_parameter1` automatically, so when user call command `shuffle`, then function `do_shuffle` would be called.

`parameter2` is the information of command. When user call command `help`, the `"| shuffle queue"` will show in the information of the command `shuffle`.

ADD_COMMAND(shuffle, "                | shuffle queue");

:::info
TODO List
- [x] read continer_of
https://hackmd.io/@sysprog/linux-macro-containerof
- [x] qtest 提供新的命令 shuffle
- [ ] read qtest
- [ ] 在 qtest 提供新的命令 web，提供 web 伺服器功能，注意: web 伺服器運作過程中，qtest 仍可接受其他命令
- [ ] 以 Valgrind 分析記憶體問題
- [ ] 研讀論文〈Dude, is my code constant time?〉，解釋本程式的 “simulation” 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student’s t-distribution 及程式實作的原理。注意：現有實作存在若干致命缺陷，請討論並提出解決方案;
- [ ] 解釋 select 系統呼叫在本程式的使用方式，並分析 console.c 的實作，說明其中運用 CS:APP RIO 套件 的原理和考量點。可對照參考 CS:APP 第 10 章重點提示
:::