# 2021q1 Homework1 (lab0)
contributed by < `ilkclord` >

## Schedule

* [x] struct of queue
* [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
* [x] console.h
* [x] qtest_debugging
* [ ] qtest-completing
## Development Detail

### queue.h
* **q_struct**
* ***head** the start of the linked list
* ***tail** use to make $O(1)$ time in insert_tail

typedef struct {
    list_ele_t *head;
    list_ele_t *tail;
    int size;
} queue_t;

### queue.c

* **q_new**
* create a new queue
* initialize the queue

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

* **q_free**
* ***tmp** use for rember the address of next node
* free the string first then free the node

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

* **q_insert_head**
* Three checking gate to prevent acting on NULL ,empty and lack of memory
* Contents a special case for the inserting when th queue is empty

bool q_insert_head(queue_t *q, char *s)
{
    if (q == NULL)
        return false;
    list_ele_t *newh = malloc(sizeof(list_ele_t));
    if (newh == NULL) {
        free(newh);
        return false;
    }
    char *tmp = malloc(strlen(s) + 1);
    if (tmp == NULL) {
        free(tmp);
        free(newh);
        return false;
    }
    strncpy(tmp, s, strlen(s));
    tmp[strlen(s)] = '\0';
    if (q->head == NULL) // special case
        q->tail = newh;
    newh->value = tmp;
    newh->next = q->head;
    q->head = newh;
    q->size = q->size + 1;
    return true;
}

* **q_insert_tail**
* Three checking gate to prevent acting on NULL ,empty and lack of memory
* Contents a special case for the inserting when queue is empty

bool q_insert_tail(queue_t *q, char *s)
{
    if (q == NULL)
        return false;
    list_ele_t *newt = malloc(sizeof(list_ele_t));
    if (newt == NULL) {
        free(newt);
        return false;
    }
    char *tmp = malloc(strlen(s) + 1);
    if (tmp == NULL) {
        free(tmp);
        free(newt);
        return false;
    }
    strncpy(tmp, s, strlen(s));
    tmp[strlen(s)] = '\0';
    newt->next = NULL;
    newt->value = tmp;
    if (q->tail == NULL) { // special case
        q->tail = newt;
        q->head = newt;
        return true;
    }
    q->tail->next = newt;
    q->tail = newt;
    q->size = q->size + 1;
    return true;
}

* **q_remove_head**
* A checking gate for NULL and empty queue
* A checking gate for NULL sp
* free the string first then the node

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

* **q_size**
* Operate in $O(1)$ time
* A checking gate for NULL and empty queue

int q_size(queue_t *q)
{
    if (q == NULL || q->head == NULL)
        return 0;
    return q->size;
}

* **q_reverse**
* First check if the queue has at least 2 elements
* Change the direction between each elements
* Break the loop if reach the end (NULL)

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

* **q_sort**
* Add three function to complete the Task

void q_sort(queue_t *q)
{
    if (q == NULL || q->head == NULL || q->head->next == NULL)
        return;
    q->head = merge_split(q->head, q->size);
    q->tail = merge_find(q->size, q->head);
}

* **merge**
* The merging process
* **q1** and **q2** represents two linked list
* Can merge two linked list with diffrent size
* Return a **merged** linked list
* First if_else determine the head of **merged** linked list

list_ele_t *merge(list_ele_t *q1, list_ele_t *q2)
{
    list_ele_t *leads = NULL, *root;
    if (strcmp(q1->value, q2->value) < 0) {
        leads = q1;
        q1 = q1->next;
    } else {
        leads = q2;
        q2 = q2->next;
    }
    root = leads;
    while (q1 != NULL && q2 != NULL) {
        if (strcmp(q1->value, q2->value) < 0) {
            leads->next = q1;
            q1 = q1->next;
        } else {
            leads->next = q2;
            q2 = q2->next;
        }
        leads = leads->next;
    }
    if (q1 == NULL)
        leads->next = q2;
    else
        leads->next = q1;
    return root;
}

* **merge_find**
* Find the node in specific position

list_ele_t *merge_find(int a, list_ele_t *root)
{
    while (a > 1) {
        root = root->next;
        a = a - 1;
    }
    return root;
}

* **merge_split**
* First split the linked list to two linkend list
* The tail points to the NULL
* Do the merge-sort to the two linked list
* Recursively , return root if it has only ine elements
* Finally merge the two linked list to one
* Return the **merged-sorted** linked list

list_ele_t *merge_split(list_ele_t *root, int size)
{
    if (size / 2 > 0) {
        list_ele_t *tmp = merge_find(size / 2, root);
        list_ele_t *q2 = tmp->next;
        tmp->next = NULL;
        root = merge_split(root, size / 2);
        q2 = merge_split(q2, size - size / 2);
        return merge(root, q2);
    } else {
        root->next = NULL;
        return root;
    }
}

## Some Error

When making the test score 100/100 , there are some condition that i didn't notice

* **NULL States**
In the function below , I called the data in the nodes but the nodes are NULL actually.
* **q_insert_head**
The first insertion needs to initialize the tail too , so a gate is added

        if (q->head == NULL) // special case
            q->tail = newh;

* **q_insert_tail**
The first insertion will failed because the tail is NULL ,and can't be called , so the gate below is added.

    if (q->tail == NULL) { // special case
        q->tail = newt;
        q->head = newt;
        return true;
    }

* **q_sort**
When finished sorting ,because the return linked list were copy to head, but tail has to modified too.

    q->tail = merge_find(q->size, q->head);

## Error in qtest
### Variable echo
By the command

$ make clean
$ make SANITIZER=1 
$ ./qtest
$ cmd>help

We get the error message below

==11584==ERROR: AddressSanitizer: global-buffer-overflow on address 0x555e3e8143c0 at pc 0x555e3e7fd7bd bp 0x7ffce26b18b0 sp 0x7ffce26b18a0
READ of size 4 at 0x555e3e8143c0 thread T0
    #0 0x555e3e7fd7bc in do_help_cmd /home/ilkclord/linux2020/lab0-c/console.c:307
    #1 0x555e3e7fd8d0 in interpret_cmda /home/ilkclord/linux2020/lab0-c/console.c:221
    #2 0x555e3e7fe0b5 in interpret_cmd /home/ilkclord/linux2020/lab0-c/console.c:244
    #3 0x555e3e7ff7f8 in run_console /home/ilkclord/linux2020/lab0-c/console.c:660
    #4 0x555e3e7fc3e5 in main /home/ilkclord/linux2020/lab0-c/qtest.c:780
    #5 0x7fc192aea0b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
    #6 0x555e3e7f9b8d in _start (/home/ilkclord/linux2020/lab0-c/qtest+0x8b8d)

0x555e3e8143c1 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:59:13' (0x555e3e8143c0) of size 1
SUMMARY: AddressSanitizer: global-buffer-overflow /home/ilkclord/linux2020/lab0-c/console.c:307 in do_help_cmd

From the error message below we can figure out that
* The error occur in global variable **echo**
* It happend because reading size 4 in a size 1 memory
* The **echo** is a 1 byte variable

==11584==ERROR: AddressSanitizer: global-buffer-overflow on address 0x555e3e8143c0 at pc 0x555e3e7fd7bd bp 0x7ffce26b18b0 sp 0x7ffce26b18a0
READ of size 4 at 0x555e3e8143c0 thread T0

0x555e3e8143c1 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:59:13' (0x555e3e8143c0) of size 1

Find the definition of **echo** in console.c

static bool echo = 0;

Find out the line first error occured

report(1, "\t%s\t%d\t%s", plist->name, *plist->valp,
               plist->documentation);

We can know there are somthing wrong in 3 parameters , and they all belongs to **plist** which the type is **param_ptr**

param_ptr plist = param_list;

And the sturct of **param_ptr** can be find in console.h

typedef struct PELE param_ele, *param_ptr;
struct PELE {
    char *name;
    int *valp;
    char *documentation;
    /* Function that gets called whenever parameter changes */
    setter_function setter;
    param_ptr next;
};

Because the size of type **char** is 1 , the only possibe parameters which cause error is **int** ***valp**
TSo we find out that the **echo** is used to initialize **valp**

add_param("echo", (int *) &echo, "Do/don't echo commands", NULL);

And **add_param()** add a new node with type **param_ptr**

    // part of the function
    param_ptr ele = (param_ptr) malloc_or_fail(sizeof(param_ele), "add_param");
    ele->name = name;
    ele->valp = valp;
    ele->documentation = documentation;
    ele->setter = setter;
    ele->next = next_param;
    *last_loc = ele;

Apparently **(int\*)&echo** is a invalid use ,because the size doesn't match (1 -> 4) .
To fix it ,we can just let the type of **echo** be **int** ,because there aren't any assinging true or false to **echo** action.
After applying the change , we fix it !
### Variable simulation
By the command

$ make clean
$ make SANITIZER=1 
$ make test

We get the error message

==13139==ERROR: AddressSanitizer: global-buffer-overflow on address 0x564b115bb5e0 at pc 0x564b115a3ae8 bp 0x7ffe28ebd340 sp 0x7ffe28ebd330
READ of size 4 at 0x564b115bb5e0 thread T0
    #0 0x564b115a3ae7 in do_option_cmd /home/ilkclord/linux2020/lab0-c/console.c:369
    #1 0x564b115a28d0 in interpret_cmda /home/ilkclord/linux2020/lab0-c/console.c:221
    #2 0x564b115a30b5 in interpret_cmd /home/ilkclord/linux2020/lab0-c/console.c:244
    #3 0x564b115a42e1 in cmd_select /home/ilkclord/linux2020/lab0-c/console.c:594
    #4 0x564b115a485b in run_console /home/ilkclord/linux2020/lab0-c/console.c:667
    #5 0x564b115a13e5 in main /home/ilkclord/linux2020/lab0-c/qtest.c:780
    #6 0x7f1b857f80b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
    #7 0x564b1159eb8d in _start (/home/ilkclord/linux2020/lab0-c/qtest+0x8b8d)

0x564b115bb5e1 is located 0 bytes to the right of global variable 'simulation' defined in 'console.c:21:6' (0x564b115bb5e0) of size 1
  'simulation' is ascii string ''
SUMMARY: AddressSanitizer: global-buffer-overflow /home/ilkclord/linux2020/lab0-c/console.c:369 in do_option_cmd

From the error message we find the similar information of **simulation** as **echo**
* The error occur in global variable **simulation**
* It happend because reading size 4 in a size 1 memory
* The **simulation** is a 1 byte variable

==13139==ERROR: AddressSanitizer: global-buffer-overflow on address 0x564b115bb5e0 at pc 0x564b115a3ae8 bp 0x7ffe28ebd340 sp 0x7ffe28ebd330
READ of size 4 at 0x564b115bb5e0 thread T0

0x564b115bb5e1 is located 0 bytes to the right of global variable 'simulation' defined in 'console.c:21:6' (0x564b115bb5e0) of size 1
  'simulation' is ascii string ''

We cna find out where **simulation** is used

add_param("simulation",(int*)&simulation, "Start/Stop simulation mode",                      NULL);

And since the definition shows that **simulation** is **bool** type , it is a inavalid tranfer .

bool simulation = false;

We fixed it by changing the declared type to int, but then the error occured

ilkclord~01:36:38>~/linux2020/lab0-c>$ make SANTILIZER=1
  CC	qtest.o
  CC	report.o
  CC	console.o
console.c:21:5: error: conflicting types for ‘simulation’
   21 | int simulation = false;
      |     ^~~~~~~~~~
In file included from console.c:3:
console.h:11:13: note: previous declaration of ‘simulation’ was here
   11 | extern bool simulation;
      |             ^~~~~~~~~~
make: *** [Makefile:50: console.o] Error 1

So we go to console.h ,and change the type **bool** to **int** , then we fixed it !

extern int simulation;