2019q1 Homework1 (lab0)

Contributed by < krimson8 >

既然是第二次進行此作業，請考慮下述改進:

引入 AddressSanitizer 來檢驗記憶體操作，較新版本的 gcc 已包含相關的 sanitizer，搭配 Useful GCC address sanitizer checks not enabled by default;
嘗試保有原本的自動評分系統，將給定的 linked list 程式碼換為 F02: list 給定的 Linux-like 實作，並確保能夠通過完整的檢驗流程;
重新整理下方共筆 (刪去過時資訊)，學習技術文件的撰寫，可參照基於 C 語言標準研究與系統程式安全議題的風格;
Image Not Showing Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
jserv

實驗環境資訊

$ uname -a
Linux pc 4.15.0-34-generic #37-Ubuntu SMP Mon Aug 27 15:21:48 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux

100/100

C-programming lab 作業重點節錄

1.Logistics
- 只要linked list 的邏輯正確便不難
2.Overview
- 所測試的技能
  - Explicit memory management, as required in C.
  - Creating and manipulating pointer-based data structures.
  - Working with strings.
  - Enhancing the performance of key operations by storing redundant information in data structures.
  - Implementing robust code that operates correctly with invalid arguments, including NULL pointers.
- 需要 implement LIFO 和 FIFO 的 queue 資料結構
3.Resources
- C programming
  - K&R C
  - https://en.wikibooks.org/wiki/C_Programming.
- Linked lists
  - http://www.cs.cmu.edu/~iliano/courses/18S-CMU-CS122/handouts/10-linkedlist.pdf
- Asympotic notation
  - http://www.cs.cmu.edu/~iliano/courses/18S-CMU-CS122/handouts/05-sort.pdf
- Linux Man Pages
4, 5 爲 autolab 相關，忽略
6.Overview
- queue.h
  - list_ele_t 爲 linked list 的節點 struct
  - queue_t 爲 queue 的 struct
```
/* Linked list element */
typedef struct ELE {
    char *value;
    struct ELE *next;
} list_ele_t;
  /* Queue structure */
typedef struct {
    list_ele_t *head; /* Linked list of elements */
} queue_t;
```
  詳細 queue 結構如下圖：
  Image Not Showing Possible Reasons
  The image file may be corrupted
  The server hosting the image is unavailable
  The image path is incorrect
  The image format is not supported
  Learn More →
- 一個長度爲 L 的 string，在 C語言裏面的表達方式爲 L+1 長度的 char 陣列
- list_ele_t 內的 value 應該存有指向一個char array 的 pointer
- queue_t 裏的每一個節點都應該有自己的 string （就算和別的節點是一樣的 string）
  - 每一個節點都使用 strdup 或自行 malloc
  - 因爲 strdup 有使用到 malloc 所以猜想刪除節點的時候也要一併free掉
  - 網絡上找到一個很好的解釋 strcpy和 strdup 之間的差別
```
// strcpy
while(*ptr2++ = *ptr1++)

// strdup
ptr2 = malloc(strlen(ptr1)+1);
strcpy(ptr2,ptr1);
```
  - 用法
```
char *p1 = "LOL";
char *p2;
p2 = strdup(p1);

printf("Duplicated string is : %s", p2);
```
- queue_t* 內的 head 指向一個 queue 的開頭，queue 可分爲兩種 case
  - queue_t* X = NULL; 即爲Null queue
  - queue_t* X = ...;
    X->head = NULL; 則是 Empty queue
7.Programming Task
- q_new: Create a new, empty queue.
- q_free: Free all storage used by a queue.
- q_insert_head: Attempt to insert a new element at the head of the queue (LIFO discipline).
- q_insert_tail: Attempt to insert a new element at the tail of the queue (FIFO * discipline).
- q_remove_head: Attempt to remove the element at the head of the queue.
- q_size: Compute the number of elements in the queue.
- q_reverse: Reorder the list so that the queue elements are reversed in order. This function should not allocate or free any list elements (either directly or via calls to other functions that allocate or free list elements.) Instead, it should rearrange the existing elements.
這段有說使用到 string 的時候，必須 create and store a copy of the string by calling malloc to allocate space, 還有 allocate space for each string based on its length.
q_insert_tail 和 q_size 要達到
$O (1)$

實作

這裏是實作的過程，一個 function 接上一個 function 做解釋，並且優先解釋先完成的 function。

queue.h

首先更改原本 queue 的 struct 結構，增加一個只想 tail 的 pointer 和節點數計算





typedef struct {
    list_ele_t *head; 
    list_ele_t *tail;
    long long int list_count;
} queue_t;

這樣的話q_size 和 q_insert_tail 就都能夠有辦法實現

O (1)

的演算法

q_new












queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    /* What if malloc returned NULL? */
    if (q == NULL) {
        return NULL;
    }
    q->head = NULL;
    q->tail = NULL;
    q->list_count = 0;
    return q;
}

起始化 queue 結構，根據作業定義 q->head = NULL; 即表示這是一個空 queue

q_insert_head
```
bool q_insert_head(queue_t *q, char *s)
{
    if (q == NULL) {
        return false;
    }

    list_ele_t *newh;
    newh = (list_ele_t *) malloc(sizeof(list_ele_t));
    
    if (newh == NULL) {
        return false;
    }

    newh->value = malloc(strlen(s) + 1);
    if (newh->value == NULL) {
        free(newh);
        return false;
    }
    
    strcpy(newh->value, s);
    
    if (q->list_count == 0) {
        q->tail = newh;
    }

    newh->next = q->head;
    q->head = newh;
    q->list_count++;
    return true;
}
```
- 根據作業要求進行一下判定和宣告流程
  - 判斷argument 的 q 是否爲NULL，若是則回傳 false
  - 嘗試建立新節點 list_ele_t *newh;，若malloc過程失敗則回傳 false
  - 接下來進行字串copy 的動作
    這裏有一個疑問，本來的寫法是 newh->value = strdup(s);，但是這樣的話執行 qtest 會回傳 attempted to free unallocated space error，因此參考了 strdup 的實作
```
newh->value = malloc(strlen(s) + 1);
strcpy(newh->value, s);
```
    問：爲什麼strdup 不行？
    已解決
    
    因爲這支程式裏面呼叫的 malloc 不是系統的 malloc 而是 qtest的，因此如果用 strdup （qtest 沒有提供）雖然可以過掉測資，但是因爲我的程式碼裏面有顧慮到 free 每一個節點的時候先 free 掉 value，但是若使用strdup 所 malloc 出來的空間 qtest 是不知情的！這就造成了 qtest 顯示 attempted to free unallocated space error。
    
    qtest的程式碼有自行模擬malloc
    
    然後一樣嘗試在malloc 的過後判斷 value 是 NULL 的話回傳false
    
    因爲qtest 內有一個選項是可以開啓 malloc 成功率，當不爲0 的時候，就會有很多情況回傳NULL
    因此若newh->value == NULL 則必須同時兼顧newh 的free 的動作，不然會有memory leak 的錯誤
  - 判斷list_count 是否爲0，若爲0 則先讓 tail 指向 newh
  - 讓newh->next = q->head （head 可能爲 NULL，即創立第一個節點）
  - 讓q->head = newh （更新 head pointer 指向新節點）
  - list_count++ 增加節點數量

q_insert_tail






























bool q_insert_tail(queue_t *q, char *s)
{
    if (q == NULL) {
        return false;
    }

    list_ele_t *newh;

    newh = (list_ele_t *) malloc(sizeof(list_ele_t));
    if (newh == NULL) {
        return false;
    }

    newh->value = malloc(strlen(s) + 1);
    if (newh->value == NULL) {
        free(newh);
        return false;
    }
    strcpy(newh->value, s);

    if (q->list_count == 0) {
        q->head = newh;
    } else {
        q->tail->next = newh;
    }
    newh->next = NULL;
    q->tail = newh;
    q->list_count++;
    return true;
}

基本上與q_insert_head的實作方式一樣
- list_count 爲0 的時候，讓head指向新的節點，若不是0 則 tail->next = newh
- 新節點的next 指向 NULL
- tail 指向新節點
- list_count++ 增加節點數量

q_remove_head


















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 *temp = q->head;
    q->head = q->head->next;
    free(temp->value);
    free(temp);
    q->list_count--;
    return true;
}

根據作業要求
- 若q 與 q->head 爲 NULL 則回傳 false
- 若 sp 非 NULL，則把移除的節點的字串複製進去，sp 可以接受的最大size 爲 bufsize - 1 因此要寫好條件判定式，而且 array 最後需要以 NULL terminator 結束（s[bufsize - 1]）
- 使用 strncpy 複製給定大小的字串長度
- 建立一個名爲 temp 的pointer 指向 head 節點
- 把 head 指向 head->next
- 把 temp 所佔的空間 free 掉
- list_count++ 節點數量減一
- - 10/01 更新，減少不必要的程式碼

q_size







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

若 q 是 NULL 或者 empty 的話回傳0，否則回傳queue 長度

q_reverse
















void q_reverse(queue_t *q)
{
    if (q != NULL && q->head != NULL && q->head->next != NULL) {
        list_ele_t *itr = q->head->next;
        list_ele_t *temp;

        q->tail = q->head;
        while (itr != NULL) {
            temp = itr->next;
            itr->next = q->head;
            q->head = itr;
            itr = temp;
        }
        q->tail->next = NULL;
    }
}

根據作業要求
- 若q 與 q->head 爲 NULL 則 NO EFFECT
- 不能呼叫其他函式
- 把q->tail 指向 q->head ，從第二個節點開始每一個節點指向上一個節點，結束後讓 q->head 指向最後一個節點
- 實作方式可看程式碼
- 10/01 更新，減少使用的迴圈變數

q_free















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

根據作業要求進行撰寫
- 留意作業要求並沒有註明這個 function 需要在 q == NULL 的時候回傳什麼值，但是有一筆測資內含指令 free ，而 qtest 結束的時候也會進行 free 指令的動作，因此進行了兩次free，若不檢查q 的狀態的話會出錯(double free error)
- 先 free 字串的空間，再 free 掉節點所佔的空間

程式執行結果

$ make test

截圖

scripts/driver.py
---	Trace		Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
---	trace-01-ops	6/6
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, and remove_head
---	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, and size
---	trace-04-ops	6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head reverse, and size
---	trace-05-ops	6/6
+++ TESTING trace trace-06-string:
# Test of truncated strings
---	trace-06-string	7/7
+++ TESTING trace trace-07-robust:
# Test operations on NULL queue
---	trace-07-robust	7/7
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
---	trace-08-robust	7/7
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
---	trace-09-robust	7/7
+++ TESTING trace trace-10-malloc:
# Test of malloc failure on new
---	trace-10-malloc	7/7
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
---	trace-11-malloc	7/7
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
---	trace-12-malloc	7/7
+++ TESTING trace trace-13-perf:
# Test performance of insert_tail
---	trace-13-perf	7/7
+++ TESTING trace trace-14-perf:
# Test performance of size
---	trace-14-perf	7/7
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, and reverse
---	trace-15-perf	7/7
---	TOTAL		100/100