---
tags: linux kernel
---

# 2022q1 Homework1 (lab0)
contributed by < `huang-me` >

:::danger
注意作業書寫規範！
:notes: jserv
:::

# Prerequisites

$ sudo apt install build-essential git clang-format aspell colordiff valgrind

### Build cppcheck
Download cppcheck source code from [GitHub](https://github.com/danmar/cppcheck/releases).

# unzip file
tar -xf <cppcheck-version.tar.gz>
cd cppcheck-<version>
# build file and install
sudo make CFGDIR=/usr/share/cppcheck/ FILESDIR=/usr/bin/ -j4
sudo make install CFGDIR=/usr/share/cppcheck/ FILESDIR=/usr/bin -j4

# Environment
:::danger
Your gcc was too old. Upgrade your Linux distribution as soon as possible, otherwise you will encounter some unexpected issues later.

:notes: jserv
:::

$ gcc --version
gcc (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0

$ lscpu
Architecture:        x86_64
CPU op-mode(s):      32-bit, 64-bit
Byte Order:          Little Endian
CPU(s):              8
On-line CPU(s) list: 0-7
Thread(s) per core:  2
Core(s) per socket:  4
Socket(s):           1
NUMA node(s):        1
Vendor ID:           GenuineIntel
CPU family:          6
Model:               142
Model name:          Intel(R) Core(TM) i7-8550U CPU @ 1.80GHz
Stepping:            10
CPU MHz:             899.969
CPU max MHz:         4000.0000
CPU min MHz:         400.0000
BogoMIPS:            3999.93
Virtualization:      VT-x
L1d cache:           32K
L1i cache:           32K
L2 cache:            256K
L3 cache:            8192K
NUMA node0 CPU(s):   0-7

# Development
## queue_new
- Use `malloc` to acquire memory space, return NULL if no space available.
Initialize list_head with `INTI_LIST_HEAD` defined in `list.h`

struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(*head));
    if (!head)
        return NULL;
    INIT_LIST_HEAD(head);
    return head;
}

## queue_free
- Delete first node until list have no element, and delete list_head.

void q_free(struct list_head *l)
{
    if (!l)
        return;
    while (!list_empty(l)) {
        element_t *node = list_first_entry(l, element_t, list);
        q_remove_head(l, NULL, 0);
        free(node->value);
        free(node);
    }
    free(l);
}

- Use `list_for_each_entry_safe` defined in `list.h` to iterate through all nodes in list, remove them from list and release the memory.

void q_free(struct list_head *l)
{
    if (!l)
        return;
    element_t *e, *s;
    list_for_each_entry_safe (e, s, l, list) {
        list_del(&(e->list));
        q_release_element(e);
    }
    free(l);
}

## q_insert_head
- Use `malloc` allocate memory, `return false` if no memory can be allocated.
Use `memset` initialize the value of `newNode` and copy input to `newNode->value`

bool q_insert_head(struct list_head *head, char *s)
{
    element_t *newNode = malloc(sizeof(element_t));
    if (!newNode)
        return false;
    newNode->value = malloc(sizeof(char) * (strlen(s) + 1));
    if(!newNode->value) {
        q_release_element(newNode);
        return false;
    }
    memset(newNode->value, '\0', strlen(s) + 1);
    strncpy(newNode->value, s, strlen(s));
    list_add(&newNode->list, head);
    return true;
}

## q_insert_tail
- Most operations are same as `q_insert_head`, the only difference is replace `list_add` with `list_add_tail`.

bool q_insert_tail(struct list_head *head, char *s)
{
    element_t *newNode = malloc(sizeof(element_t));
    if (!newNode)
        return false;
    newNode->value = malloc(sizeof(char) * (strlen(s) + 1));
    if (!newNode->value) {
        q_release_element(newNode);
        return false;
    }
    memset(newNode->value, '\0', strlen(s) + 1);
    strncpy(newNode->value, s, strlen(s));
    list_add_tail(&newNode->list, head);
    return true;
}

## q_remove_head
- Use `list_entry` to get the address of the entry.
Copy the entry value to sp if sp is given.

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *node = list_entry(head->next, element_t, list);
    if (sp && node->value) {
        strncpy(sp, node->value, bufsize - 1);
        *(sp + bufsize - 1) = '\0';
    }
    list_del(head->next);
    return node;
}

## q_remove_tail
- Most operations are same as `q_remove_head`, the only difference is the node position is changed from `head->next` to `head->prev`.

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *node = list_entry(head->prev, element_t, list);
    if (sp && node->value) {
        strncpy(sp, node->value, bufsize - 1);
        *(sp + bufsize - 1) = '\0';
    }
    list_del(head->prev);
    return node;
}

## q_release_element
- Release the memory of `e->value` and `e` if they were defined.

void q_release_element(element_t *e)
{
    if (!e)
        return;
    if (e->value)
        free(e->value);
    free(e);
}

## q_size
- Iterate through the queue with `list_for_each` and count the number of elements.

int q_size(struct list_head *head)
{
    if (!head)
        return -1;
    int cnt = 0;
    struct list_head *e;
    list_for_each (e, head)
        cnt++;
    return cnt;
}

## q_delete_mid
- Use `fast/slow` pointer find middle element of linked list and delete it.

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, *slow;
    fast = slow = head->next;
    while (slow->next != head && slow->next->next != head) {
        slow = slow->next->next;
        fast = fast->next;
    }
    element_t *e = list_entry(fast, element_t, list);
    list_del(fast);
    q_release_element(e);
    return true;
}

## q_delete_dup
- Iterate through all list nodes, delete the node if value is same as last node.

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;
    element_t *e, *s;
    char *last = NULL;
    list_for_each_entry_safe (e, s, head, list) {
        if (last && strcmp(last, e->value) == 0) {
            list_del(&e->list);
            q_release_element(e);
        } else {
            last = strdup(e->value);
        }
    }
    return true;
}

:::success
`strdup` may lead to memory leak since the space is never released.
Rewrite `q_delete_dup` as following code to prevent copying data.

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;
    element_t *e, *s;
    char *last = NULL;
    list_for_each_entry_safe (e, s, head, list) {
        if (last && strcmp(last, e->value) == 0) {
            list_del(&e->list);
            q_release_element(e);
        } else {
            last = e->value;
        }
    }
    return true;
}

:::

## q_swap
- Reassign all pointers between list nodes.

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 = head->next;
    while (e != head && e->next != head) {
        struct list_head *n;
        n = e->next;
        n->next->prev = e;
        e->next = n->next;
        n->next = e;
        n->prev = e->prev;
        e->prev->next = n;
        e->prev = n;
        e = e->next;
    }
}

:::success
Shorten code with use of list.h functions.

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 = head->next;
    while (e != head && e->next != head) {
        struct list_head *n = e->next;
        list_del(n);
        list_add(n, e->prev);
        e = e->next;
    }
}

:::

## q_reverse
- Exchange all node's `next` and `prev` pointer to achieve reverse.

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    struct list_head *e, *s;
    list_for_each_safe (e, s, head) {
        e->next = e->prev;
        e->prev = s;
    }
    struct list_head *tmp = head->next;
    head->next = head->prev;
    head->prev = tmp;
}

## q_sort
- Split list into two subqueues, sort them separately and Merge into one queue.
Time complexity: `O(nlogn)`

void q_sort(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    struct list_head *fast, *slow;
    fast = slow = head->next;
    while (fast != head && fast->next != head) {
        fast = fast->next->next;
        slow = slow->next;
    }
    if (fast == head)
        fast = fast->prev;

    struct list_head *mid;
    mid = slow->prev;
    head->prev = mid;
    mid->next = head;
    q_sort(head);
    struct list_head *front, *last;  // ptr for 1st subqueue
    front = head->next;
    last = head->prev;
    head->next = slow;
    slow->prev = head;
    head->prev = fast;
    q_sort(head);
    struct list_head *fr;  // ptr for 2nd subqueue
    fr = head->next;
    last->next = fr;
    fr->prev = last;
    head->next = front;
    front->prev = head;

    // merge two subqueue
    struct list_head *p1 = front, *p2 = last->next;
    while (p1 != last->next && p2 != head) {
        char *v1 = list_entry(p1, element_t, list)->value,
             *v2 = list_entry(p2, element_t, list)->value;
        if (strcmp(v1, v2) <= 0) {
            p1 = p1->next;
        } else {
            struct list_head *tmp = p2->next;
            list_del(p2);
            p2->next = p1;
            p2->prev = p1->prev;
            p1->prev = p2;
            p2->prev->next = p2;
            p2 = tmp;
        }
    }
}

:::success
Shorten merge code with use of list.h function.

    struct list_head *p1 = front, *p2 = last->next;
    while (p1 != last->next && p2 != head) {
        char *v1 = list_entry(p1, element_t, list)->value,
             *v2 = list_entry(p2, element_t, list)->value;
        if (strcmp(v1, v2) <= 0) {
            p1 = p1->next;
        } else {
            struct list_head *tmp = p2->next;
            list_del(p2);
            list_add(p2, p1->prev);
            p2 = tmp;
        }
    }

:::

# Result

make test
scripts/driver.py -c
---	Trace		Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
---	trace-01-ops	5/5
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, remove_head, remove_tail, and delete_mid
---	trace-02-ops	6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, reverse, and remove_head
---	trace-03-ops	6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, swap, and sort
---	trace-04-ops	6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, swap, and sort
---	trace-05-ops	6/6
+++ TESTING trace trace-06-ops:
# Test of insert_head, insert_tail, delete duplicate, and sort
---	trace-06-ops	6/6
+++ TESTING trace trace-07-string:
# Test of truncated strings
---	trace-07-string	6/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
---	trace-08-robust	6/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
---	trace-09-robust	6/6
+++ TESTING trace trace-10-robust:
# Test operations on NULL queue
---	trace-10-robust	6/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
---	trace-11-malloc	6/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
---	trace-12-malloc	6/6
+++ TESTING trace trace-13-malloc:
# Test of malloc failure on new
---	trace-13-malloc	6/6
+++ TESTING trace trace-14-perf:
# Test performance of insert_tail, reverse, and sort
---	trace-14-perf	6/6
+++ TESTING trace trace-15-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
---	trace-15-perf	6/6
+++ TESTING trace trace-16-perf:
# Test performance of insert_tail
---	trace-16-perf	6/6
+++ TESTING trace trace-17-complexity:
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
Probably constant time
Probably constant time
Probably constant time
Probably constant time
---     trace-17-complexity     5/5
---	TOTAL		100/100

:::danger
Insert/Remove time complexity test doesn't always pass in GitHub CI.
> You should read the paper and recognize the root cause.
> :notes: jserv
:::

# Fisher-Yates shuffle
- Add `q_shuffle` into `queue.c`
- Fisher-Yates shuffle steps
1. Randomly choose a node and move it to tail of the queue.
2. Repeat step 1 for `q_size` times

void q_shuffle(struct list_head *head) {
    if(!head || list_empty(head))
        return;
    struct list_head *node;
    for(int cnt=q_size(head); cnt>0; cnt--) {
        int x = rand() % cnt;
        node = head->next;
        for(int i=0; i<x; i++)
            node = node->next;
        list_del(node);
        list_add_tail(node, head);
    }
    return;
}

- Add `q_shuffle` definition into queue.h header file.

void q_shuffle(struct list_head *head);

- Add `do_shuffle` in `qtest.c`.

static bool do_shuffle(int argc, char *argv[])
{
    if (argc != 1) {
        report(1, "%s takes no arguments", argv[0]);
        return false;
    }
    q_shuffle(l_meta.l);
    show_queue(3);
    return !error_check();
}

- Add command shuffle to console

ADD_COMMAND(shuffle, "                | Shuffle the queue");