---
# System prepended metadata

title: 2021q1 Homework1 (lab0)

---

# 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
```clike=
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
``` clike=
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
```clike=
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
```clike=
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
```clike=
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
```clike=

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
```clike=
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)
```clike=
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
```clike=

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
```clike=
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
```clike=
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
```clike=
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
    ```clike=
        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.
    ```clike=
    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.
    ```clike=
    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
```clike
==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
```clike
==11584==ERROR: AddressSanitizer: global-buffer-overflow on address 0x555e3e8143c0 at pc 0x555e3e7fd7bd bp 0x7ffce26b18b0 sp 0x7ffce26b18a0
READ of size 4 at 0x555e3e8143c0 thread T0
```

```clike
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 
```clike
static bool echo = 0;
```
Find out the line first error occured
```clike
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**
```clike
param_ptr plist = param_list;
```
And the sturct of **param_ptr** can be find in console.h
```clike
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**
```clike
add_param("echo", (int *) &echo, "Do/don't echo commands", NULL);
```
And **add_param()** add a new node with type **param_ptr**
```clike
    // 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
```clike
$ make clean
$ make SANITIZER=1 
$ make test
```
We get the error message
```clike
==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
```clike
==13139==ERROR: AddressSanitizer: global-buffer-overflow on address 0x564b115bb5e0 at pc 0x564b115a3ae8 bp 0x7ffe28ebd340 sp 0x7ffe28ebd330
READ of size 4 at 0x564b115bb5e0 thread T0
```
```clike
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
```clike
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 .
```clike=
bool simulation = false;
```
We fixed it by changing the declared type to int, but then the error occured
```clike
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 !
```clike
extern int simulation;
```