---
title: '2020q3 Homework1 (lab0)'
tags: linux2020
---
# 2020q3 Homework1 (lab0)
contributed by < `ChongMingWei` >

## Outline
[TOC]

## 環境

$ uname -a
Linux cmw-System-Product-Name 5.4.0-47-generic #51~18.04.1-Ubuntu SMP Sat Sep 5 14:35:50 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux


$ gcc --version
gcc (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0
Copyright (C) 2017 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.

## 作業要求
在 ``queue.[c/h]`` 中完成以下實作

* `q_new`: 建立新的「空」佇列;
* `q_free`: 釋放佇列所佔用的記憶體;
* `q_insert_head`: 在佇列開頭 (head) 加入 (insert) 給定的新元素 (以 LIFO 準則);
* `q_insert_tail`: 在佇列尾端 (tail) 加入 (insert) 給定的新元素 (以 FIFO 準則);
* `q_remove_head`: 在佇列開頭 (head) 移除 (remove) 給定的元素。
* `q_size`: 計算佇列中的元素數量。
* `q_reverse`: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列元素，換言之，它只能重排已經存在的元素;
* `q_sort`: 以==遞增順序==來排序鏈結串列的元素

## 實作流程

### q_size
Add new member int size into struct queue_t.
Simutaneously, add new member list_ele_t \*tail because of the hint:eyes:

/*queue.h*/
typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail; /* Efficiently implement q_insert_tail*/
    int size;         /* Efficiently implement q_size*/
} queue_t;

Get size of current queue.

/*queue.c*/
int q_size(queue_t *q)
{
    if (!q)
        return 0;
    else if (!q->head)
        return 0;
    else
        return q->size;
}

### q_new

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

### q_free
:::info
20200915
1.Comment line 12 (Undefined behavior: repeatedly free memory. No error occured last time because insert tail function hadn't been implemented.
2.Add line 14-16 to remove dangling pointer (**Remember to do this!!**).
:::

void q_free(queue_t *q)
{
    /* Free queue structure */
    if (q) {
        while (q->head) {
            list_ele_t *tmp;
            tmp = q->head;
            q->head = q->head->next;
            free(tmp->value);
            free(tmp);
        }
        //free(q->tail); //20200915 No need to free again.
        free(q);
        q->head = NULL;
        q->tail = NULL;
        q = NULL;   
    }
}

Commit error
:::info
Declare the variable in the scope which accesses it
:::

### q_insert_head
Check if it is sucessful for each malloc. Copy string by using memset first to avoid different lenghs between src and dst buffer.
[C99 standard-7.21.6.1 7.21.6.3 ](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf)
[C 語言的字串複製](https://medium.com/@cashbooktw/c-%E8%AA%9E%E8%A8%80%E7%9A%84%E5%AD%97%E4%B8%B2%E8%A4%87%E8%A3%BD-94da3884dc6e)
[C語言中sizeof與strlen區別](https://www.itread01.com/content/1531321469.html)
:::info
20200915
1.Deal with empty condition (line 28-29)
20200916
1.Use strlcpy from [CERN](https://security.web.cern.ch/recommendations/en/codetools/c.shtml) (line 24)
2.Wrong usage of malloc (line 14)
:::

bool q_insert_head(queue_t *q, char *s)
{
    if (!q)
        return false;
    else {
        list_ele_t *newh;
        newh = malloc(sizeof(list_ele_t));
        if (!newh){
            free(newh);
            return false;
        }
        else {
            char *news;
            //news = malloc(strlen(s) + 1);
            news = malloc(sizeof(char) * (strlen(s) + 1));
            if (!news){
                free(news);
                free(newh);
                return false;
            }
            else {
                //memset(news, '\0', strlen(s) + 1);
                //strncpy(news, s, strlen(s));
                strlcpy(news, s, strlen(s) + 1);//Using strlcpy from CERN.
                newh->next = q->head;
                newh->value = news;
                /*Deal with queue empty condition*/
                if (q->size == 0)
                    q->tail = newh;
                q->head = newh;
                q->size += 1;
                return true;
            }
        }
    }
}

Commit error
:::info
Remember to free memory!!
:::
### q_insert_tail
:::info
20200916
1.**Oops! In line 16, the size of malloc is wrong. Simply remove sizeof can resolve the problem. (However 3 hours passed...:weary:)**
2.Use strlcpy from [CERN](https://security.web.cern.ch/recommendations/en/codetools/c.shtml) (line 21)
3.Wrong usage of malloc (line 14)
:::

bool q_insert_tail(queue_t *q, char *s)
{
    if (!q)
        return false;
    else {
        list_ele_t *newt;
        newt = malloc(sizeof(list_ele_t));
        if (!newt){
            free(newt);
            return false;
        } else{
            char *news;
            //news = malloc(sizeof(strlen(s) + 1));
            //news = malloc(strlen(s) + 1);
            news = malloc(sizeof(char) * (strlen(s) + 1));
            if (!news){
                free(newt);
                free(news);
                return false;
            } else{
                //memset(news, '\0', strlen(s) + 1);
                //strncpy(news, s, strlen(s));
                strlcpy(news, s, strlen(s) + 1);
                newt->next = NULL;
                newt->value = news;
                if (!q->size){
                    q->head = newt;
                    q->tail = newt;
                } else{
                    q->tail->next = newt;
                    q->tail = newt;
                }
                q->size += 1;
                return true;
            }
        }
    }
}

### q_remove_head
:::info
20200916
1.Use strlcpy from [CERN](https://security.web.cern.ch/recommendations/en/codetools/c.shtml) (line 24)
:::

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (!q)
        return false;
    else if (!q->head){
        return false;
    } else{
        list_ele_t *tmp;
        tmp = q->head;
        q->head = q->head->next;
        if (sp){
            //memset(sp, '\0', bufsize);
            //memcpy(sp, tmp->value, bufsize - 1);
            int strLen = strlen(tmp->value) + 1;
            size_t realBufSize = bufsize > strLen ? strLen : bufsize;
            strlcpy(sp, tmp->value, realBufSize);
        }
        free(tmp->value);
        free(tmp);
        if (!q->head) 
            q->tail = NULL;
        q->size -= 1;
        return true;
    }
}

### q_reverse
:::info
20200916
1. Error occurs when testing trace-03-ops.cmd
It is about to remove string "squirrel" from head of the queue.
The size of "squirrel" is 9 bytes. If I mannually change it to "squirre", everything is going fine.
However, I repeatedly check the functions used in this trace and still have no idea. :cry:
So, I determine to reference other student's work. Thanks to [**Wei Cheng's work**](https://hackmd.io/@YR6cO28kScKZO4-yjkuAqw/HyAa0RTVP).
By reviewing his code, I find that some parts need to be modified:
+ The strlcpy macro must be used to replace strcpy. Although I originally had tried other method to replace strcpy, I determined to follow this fashion. (I don't read the whole [**CERN article**](https://security.web.cern.ch/recommendations/en/codetools/c.shtml)). It's my bad.:sweat:
+ Modification of functions are mentioned in blocks above.
+ **The error found FINALLY is mentioned in *q_insert_tail* block.**

2020xxxx
:::

void q_reverse(queue_t *q)
{

    if(q){
        list_ele_t *cursor = NULL;
        q->tail = q->head;
        while (q->head){
            list_ele_t *next = q->head->next;
            q->head->next = cursor;
            cursor = q->head;
            q->head = next;
        }
        q->head = cursor;
    }

/* Try using pointer to pointer
    if(q){
        list_ele_t **now = &q->head;
        list_ele_t *cursor = NULL;
        q->tail = q->head;
        while(*now){
            list_ele_t *tmp = (*now)->next;
            (*now)->next = cursor;
            cursor = *now;
            *now = tmp;
        }
        *now = cursor;  
    }
*/
}

### q_sort
Add 2 functions in *queue.c* and *queue.h* to do mergesort (In test, the time complexity must be less than O(n^2^). So mergesort and heapsort can be used here. I choose former because it's mentioned in the reference :sweat_smile:)
[**Linked List Sort**](https://npes87184.github.io/2015-09-12-linkedListSort/)
:::info
20200916
First, I follow the code in the above blog but get error. It is because of the prohibited use of malloc.
Then I try to modify but get wrong result. (Use trace-04-ops.cmd)
20200917
1. Actually, it is such a stupid mistake.
For strcmp:
***The strcmp function returns an integer greater than, equal to, or less than zero,
accordingly as the string pointed to by s1 is greater than, equal to, or less than the string pointed to by s2. (from C99 standard)***
And the number it returns is the difference between the ascii code of first different char in unsigned char format.
e.g. strcmp("dolphin", "dp") returns -1.
[**strcmp src code**](https://code.woboq.org/userspace/glibc/string/strcmp.c.html)
Also, the original code (line5, line14)directly takes return number of strcmp to compare. It is also wrong.:sweat:
2. Error occurs when git commit:
Line 9-10 are old codes for checking if malloc in funciton *merge* is successful in the version of the reference blog mentioned above. Here, it must be removed. Nothing wrong.:ok_hand:

:::

void q_sort(queue_t *q)
{
    if (!q || !q->head)
        return;
    if (q->size == 1)
        return;
    //mergeSortList
    q->head = mergeSortList(q->head);
    /*if (!q->head)
        printf("Failed to malloc in function merge...\n");*/
    list_ele_t *tmp = q->head;
    while(tmp->next) {
        tmp = tmp->next;
    }
    q->tail = tmp;
}

list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
    list_ele_t *tmp;
    list_ele_t *head;
    //if (strcmp(l1->value, l2->value)) {// l1 > l2
    if (strcmp(l1->value, l2->value)>0) {// l1 > l2
        tmp = l2;
        l2 = l2->next;
    } else {// l1 <= l2
        tmp = l1;
        l1 = l1->next;
    }
    head = tmp;
    while(l1 && l2) {
        //if (strcmp(l1->value, l2->value)) {// l1 > l2
        if (strcmp(l1->value, l2->value)>0) {// l1 > l2
            tmp->next = l2;
            tmp = tmp->next;
            l2 = l2->next;
        } else{// l1 <= l2
            tmp->next = l1;
            tmp = tmp->next;
            l1 = l1->next;
        }
    }
    if (l1)
        tmp->next = l1;
    if (l2)
        tmp->next = l2;

    return head;
}

list_ele_t *mergeSortList(list_ele_t *head)
{
    if(!head || !head->next)
        return head;

    list_ele_t *fast = head->next;
    list_ele_t *slow = head;
    
    //split list
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    fast = slow->next;
    slow->next = NULL;
    list_ele_t *l1 = mergeSortList(head);
    list_ele_t *l2 = mergeSortList(fast);
    
    return merge(l1, l2);
}

## Valgrind
>20200916 Added
- To current code(q_sort hasn't been implemented), use valgrind to test.
1. Choose trace-03-ops.cmd

    valgrind -q --leak-check=full ./qtest -f traces/trace-03-ops.cmd

Result:
Code:

    void q_free(queue_t *q)
    {
        /* Free queue structure */
        if (q) {
            while (q->head) {
                list_ele_t *tmp;
                tmp = q->head;
                q->head = q->head->next;
                free(tmp->value);
                free(tmp);
            }
            free(q);
            //Originally use to avoid dangling pointer, but it seems to be an invalid write operation. So remove it.
            //q->head = NULL;
            //q->tail = NULL;
            //q = NULL;
        }
    }