# 2020q3 Homework1 (lab0)
contributed by < [stonelin](https://github.com/StoneLin0708) >

###### tags: `sysprog2020`

## Outline
* [Outline](https://hackmd.io/7C5DZ-VGSDGkMwlfp7XD8g#Outline)
* [Environment](https://hackmd.io/7C5DZ-VGSDGkMwlfp7XD8g#Environment)
* [Implement](https://hackmd.io/7C5DZ-VGSDGkMwlfp7XD8g#Implement)
* [X] queue_t
* [X] q_new
* [X] q_free
* [X] q_insert_head
* [X] q_insert_tail
* [X] q_remove_head
* [X] q_size
* [X] q_reverse
* [X] q_sort
* [The bug of qtest](https://hackmd.io/7C5DZ-VGSDGkMwlfp7XD8g?view#The-bug-of-qtest)
* [Valgrind](https://hackmd.io/7C5DZ-VGSDGkMwlfp7XD8g?both#Valgrind-amp-Massif)
## Environment

➜ uname -a
Linux stonelin-ncku 5.4.0-7642-generic #46~1598628707~20.04~040157c-Ubuntu SMP Fri Aug 28 18:02:16 UTC  x86_64 x86_64 x86_64 GNU/Linux

➜ gcc --version
gcc (Ubuntu 9.3.0-10ubuntu2) 9.3.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

## Implement

### queue_t

typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail;
    size_t size;
} queue_t;

Add a pointer to tail element and a size cache to provide
$O(1)$ q_insert_tail and $O(1)$ q_size.

### q_new

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    if (!q)
        return NULL;
    q->head = NULL;
    q->tail = NULL;
    q->size = 0;
    return q;
}

$O(1)$

### q_free

void q_free(queue_t *q)
{
    if (!q)
        return;
    while (q->head) {
        free(q->head->value);
        list_ele_t *next = q->head->next;
        free(q->head);
        q->head = next;
    }
    free(q);
}

$O(N)$
Free the value, element and finilly queue it self.

### q_insert_\[head, tail\]

bool q_insert_head(queue_t *q, char *s)
{
    if (!q)
        return false;
    list_ele_t *newh = malloc(sizeof(list_ele_t));
    if (newh) {
        const size_t l = strlen(s) + 1;
        newh->value = malloc(l);
        if (newh->value) {
            strncpy(newh->value, s, l);  // copy string

head:

            newh->next = q->head;
            q->head = newh;
            if (!q->tail)  // first element
                q->tail = newh;
            ++(q->size);

tail:

            newh->next = NULL;
            if (q->tail)
                q->tail->next = newh;
            q->tail = newh;
            if (!q->head)  // first element
                q->head = newh;

            return true;
        }
        free(newh);
    }
    return false;
}

$O(1)$
Create a new element and insert to head or tail, insert logic is a little bit different, both need to take care fore the first insert.

#### To do
* I use strlen combine with strncpy, but is should be same as only strcpy, need to find out if there is a safer way to do it. (the only solution I can figure out is not use null terminated string)
[stackoverflow](https://stackoverflow.com/questions/52207214/how-to-use-strncpy-correctly)

### q_remove_head

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (!q)
        return false;
    if (!q->head)
        return false;
    list_ele_t *node = q->head;
    q->head = node->next;
    if (q->tail == node)
        q->tail = NULL;
    size_t len = strlen(node->value);
    if (sp) {
        strncpy(sp, node->value, bufsize - 1);
        if (len > (bufsize - 1)) {
            sp[bufsize - 1] = 0;
        }
    }
    free(node->value);
    free(node);
    --(q->size);
    return true;
}

$O(1)$
Remove did provide buffer size, but the strcpy issue still unsolved at insert.

### q_size

int q_size(queue_t *q)
{
    return !q ? 0 : q->size;
}

$O(1)$
Cuz implelmention of insert and remove both keep track of queue size, so it could just return cached size.

### q_reverse

void q_reverse(queue_t *q)
{
    if (!q)
        return;
    list_ele_t *cur = NULL;
    q->tail = q->head;
    while (q->head) {
        list_ele_t *next = q->head->next;
        q->head->next = cur;
        cur = q->head;
        q->head = next;
    }
    q->head = cur;
}

$O(N)$

### q_sort

sort is more tricky one, before read anything online I have implement this

int cmp(const void *a, const void *b)
{
    const list_ele_t *aa = *(list_ele_t **) a;
    const list_ele_t *bb = *(list_ele_t **) b;
    return strcmp(aa->value, bb->value);
}

void q_sort(queue_t *q){
    const size_t s = q_size(q);
    if (!s)
        return;
    list_ele_t *l[s];
    {
        list_ele_t *h = q->head;
        for (int i = 0; i < s; ++i, h = h->next) {
            l[i] = h;
        }
    }
    qsort(l, s, sizeof(list_ele_t *), cmp);
    q->head = l[0];
    for (int i = 0; i < (s - 1); ++i) {
        l[i]->next = l[i + 1];
    }
    q->tail = l[s - 1];
    q->tail->next = NULL;

}

Speed: $O(NlogN)$
Space: $O(N)$

By using qsort at stdlib, extract all element from queue to a array, and re-link elements after sorting.
Queue to array and re-link should both take $O(N)$, qsort is [most likely](https://en.cppreference.com/w/c/algorithm/qsort) $O(NlogN)$. The array take $O(N)$ extra space.

**It overload the stack by creating large array in test.**
And head allocate is not allowed.

I find out on internet I should do merge sort instead using qsort, but I still didn't figure out how to doing it efficiently (since it take mulitiple split and neither do I want to cache all midpoint *which I can't without overloading stak* nor do I feel like to implement recursive version).

So I combine merge and qsort in this way

list_ele_t *merge(list_ele_t *l, list_ele_t *r)
{
    list_ele_t *h;
    if (strcmp(l->value, r->value) < 0) {
        h = l;
        l = l->next;
    } else {
        h = r;
        r = r->next;
    }
    list_ele_t *c = h;
    while (l && r) {
        if (strcmp(l->value, r->value) < 0) {
            c->next = l;
            l = l->next;
        } else {
            c->next = r;
            r = r->next;
        }
        c = c->next;
    }
    c->next = l ? l : r;
    return h;
}

int comp(const void *a, const void *b)
{
    return strcmp((*(list_ele_t **) a)->value, (*(list_ele_t **) b)->value);
}

list_ele_t *quick_sort_sub(list_ele_t **l)
{
    list_ele_t *arr[512];          // create array of elements
    list_ele_t **end = &arr[512];  // set maximum
    list_ele_t **begin;
    // put list of elements into array, also find last element
    for (begin = arr; (begin != end) && *l; *l = (*l)->next, ++begin)
        *begin = *l;
    end = begin;
    qsort(arr, end - arr, sizeof(list_ele_t *), comp);  // sort
    for (begin = arr; (begin != end - 1);
         ++begin)  // put array of elements back to list
        (*begin)->next = *(begin + 1);
    (*begin)->next = NULL;  // cut last
    return *arr;
}

void q_sort(queue_t *q)
{
    const size_t s = q_size(q);
    if (!s)
        return;
    list_ele_t *head = q->head;
    list_ele_t *sorted = NULL;
    while (head) {  // terminate when no element left
        // quick sort sub-list and modify head to next element after sorted list
        list_ele_t *newh = quick_sort_sub(&head);
        // merge two list if exist
        sorted = sorted ? merge(sorted, newh) : newh;
    }
    q->head = sorted;
}

Speed: $O(NlogN)$
Space: $O(K)$ which K is number of element to be sort at once, 512 in my case.

Sort only $K$ element at once, and merge it after. it is not a clean solution, and I don't really know if it is faster than plain merge sort, to address that I sould do some perormance and memory test.

#### To do
* do performance test on each sorting algorithm

# The bug of qtest

After run

make SANITIZER=1
make test

I got this.

0x55838d6059a1 is located 0 bytes to the right of global variable 'simulation' defined in 'console.c:20:6' (0x55838d6059a0) of size 1
  'simulation' is ascii string ''
SUMMARY: AddressSanitizer: global-buffer-overflow /home/stonelin/project/sysprog/lab0-c/console.c:368 in do_option_cmd

The error message cleary point out the line couse the buffer overflow, but I didn't read it carefully and just want to find what does 'simulation' do.

And I accidentally found another bug cause by 'echo' when running qtest and run help command.

==992535==ERROR: AddressSanitizer: global-buffer-overflow on address 0x55e4ece2c780 at pc 0x55e4ece1c4b5 bp 0x7ffd6672b230 sp 0x7ffd6672b220
READ of size 4 at 0x55e4ece2c780 thread T0
    #0 0x55e4ece1c4b4 in do_help_cmd /home/stonelin/project/sysprog/lab0-c/console.c:306
    #1 0x55e4ece1c5c8 in interpret_cmda /home/stonelin/project/sysprog/lab0-c/console.c:220
    #2 0x55e4ece1d00f in interpret_cmd /home/stonelin/project/sysprog/lab0-c/console.c:243
    #3 0x55e4ece1dee5 in cmd_select /home/stonelin/project/sysprog/lab0-c/console.c:607
    #4 0x55e4ece1e088 in run_console /home/stonelin/project/sysprog/lab0-c/console.c:628
    #5 0x55e4ece1b103 in main /home/stonelin/project/sysprog/lab0-c/qtest.c:772
    #6 0x7f84ee6700b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
    #7 0x55e4ece188ed in _start (/home/stonelin/project/sysprog/lab0-c/qtest+0x78ed)

0x55e4ece2c781 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:58:13' (0x55e4ece2c780) of size 1
SUMMARY: AddressSanitizer: global-buffer-overflow /home/stonelin/project/sysprog/lab0-c/console.c:306 in do_help_cmd
Shadow bytes around the buggy address

I notice those two variable are both type bool, and both reference once at console.c:init_cmd(), and cast to type (int*). after some trace and varification, I fix bug by change type of those two global variable from bool to int.

# Valgrind & Massif

make valgrind
valgrind --tool=massif /tmp/qtest.wj8opq -f traces/trace-12-malloc.cmd
massif-visualizer massif.out.994298

### Test result of trace-12-malloc.cmd

It allocate memory and end up zero, which means the program doesn't has memory leak.

# Review : Dude, is my code constant time?