Try   HackMD

2019q3 Homework2 (lab0)

contributed by < Benny1117Yen >

tags: sysprog2019

注意看作業要求，對於共筆格式有諸多規範。從細節小處做起！

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

作業目標

CMU Introduction to Computer Systems (ICS) 準備了 C Programming Lab 作為檢閱學生 C 語言程式設計的認知:

  • 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.

實驗目標為實作 queue

  • first in, first out (FIFO)
  • last in, first out (LIFO)

Resources

  1. C programming
  2. Linked lists
  1. Asympotic (big-Oh) notation
  2. afcidk 的開發紀錄
  3. posutsai 的開發紀錄
  4. 你所不知道的 C 語言: 指標篇

實驗總覽

queue.h 這檔案含有以下結構宣告:






/* 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_t 類型的結構。在開始代碼中，此結構僅包含單一個字段 head，之後需要變再添加其他字段。駐列內容表示為單鏈接列表，每個元素由類型為 list_ele_t 的結構表示，具有字段 value 和 next，分別存儲指向字符串的指針和指向下一個 list元素 的指針。最終列表元素的下一個指針設置為 NULL。您可以將其他字段添加到結構 list_ele 中，儘管不必這樣做。

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 →

  • 圖1：駐列的鍊錶實現。每個列表元素都有一個 value 字段，該字段指向一個字符矩陣（C的字符串表示形式），next 字段指向下一個列表元素。字符根據 ASCII 編碼（以十六進制顯示）進行編碼。

回想一下，C 語言裡面字符串表示是型態為 char 的有值陣列。在大多數機器中，數據類型 char 表示為 1 byte。為了存儲長度為 l 的字符串，該陣列包含 l + 1 個元素，前一個 l 存儲字符的代碼（通常為 ASCII1 格式），最後一個設置為 0。列表元素的 value 字段是一個指針指到字符的陣列。該圖表示列表 [“ cab”，“ bead”，“ cab”] 的表示形式，其中字符 a–e 以十六進製表示為 ASCII 碼 61–65。 觀察字符串 “cab” 的兩個實例是如何由分離的陣列們來表示 – 每個列表元素應具有其字符串的分離副本。
在我們的 C 代碼中，駐列是類型為 queue_t * 的指針。我們區分兩種特殊情況：NULL 駐列是指針值為 NULL。空駐列是指向有效結構，但是頭 (head) 字段的值為 NULL。所以代碼將需要正確處理這兩種情況，以及包含一個或多個元素的駐列。

Programming Task

Your task is to modify the code in queue.h and queue.c to fully implement the following functions.

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: 以反向次序重新排列列表。這函數不該分配或釋放任何列表元素 (不論是直接地或呼叫其他有分配或釋放列表元素功能的函數。) 也就是說，它只能重排已經存在的元素。
在這兩個文件的註釋中可以找到更多詳細信息，包括如何處理無效的操作（例如，從空駐列或 NULL 駐列中刪除），以及函數應具有的副作用和返回值。
對於以字符串作為參數的函數，必須通過調用 malloc 分配空間（記住要包含終止字符的空間），然後從原始空間複製到新分配的空間，來創建和存儲字符串的副本。當需要釋放列表元素時，還必須釋放字符串使用的空間。不能假設字符串的長度有任何固定的上限 – 必須根據字符串的長度為每個字符串分配空間。
其中兩個功能：q_insert_tail 和 q_size 將需要您付出一些努力才能達到所需的性能標準。原生執行將需要 O（n） 個步驟來處理具有 n 個元素的駐列。我們要求您的執行在時間 O（1） 內進行操作，即無論駐列大小如何，該操作僅需要固定數量的步驟。您可以藉由在 queue_t 數據結構中包括 (include) 其他字段並在插入，刪除和反轉列表元素時正確管理這些值來執行。
您的程序將在具有 1,000,000 個以上元素的駐列上進行測試。會發現無法使用遞歸函數在如此長的列表上進行操作，因為這將需要過多的堆棧 (stack) 空間。相反，需要使用循環 (loop) 遍歷 (traverse) 列表中的元素。

開發環境

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 →

文字訊息 不要 用圖片展現！

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

實作記錄

queue.h

依照內容中的註解需求，新增以下程式碼

typedef struct {
    list_ele_t *head; /* Linked list of elements */
    /*
    You will need to add more fields to this structure
    to efficiently implement q_size and q_insert_tail
    */
    list_ele_t *tail; /* Add tail pointer in the queue */
    int size; /* Queue size */
} queue_t;
  • 新增list_ele_t *tail 指向 tail 列表元素
  • 新增 int size 為 queue 的大小

queue.c

queue_t *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->size = 0;
    return q;
}
  • 創造一個頭、尾、大小都為 NULL 的駐列，若不能分配空間時，回傳 NULL。

void q_free(queue_t *q)

















void q_free(queue_t *q)
{
    /* How about freeing the list elements and the strings? */
    if (q == NULL)
        return;
    list_ele_t *ptr = q->head;
    list_ele_t *ptr = NULL;
    while (ptr) {
        prev = ptr;
        ptr = ptr->next;
        free(prev->value);
        free(prev);
    }
    /* Free queue structure */
    free(q);
}
  • if 條件是判斷駐列為 NULL 時，指針指到 head，指針的前一個位子為 NULL。
  • while 是當 ptr 有值 (指到頭)，那麼 prev 就等於 ptr ，ptr 去指向 next。
  • 如此，只用 ptr 指標就能指到要刪除的元素，要記得釋放指針指到的值記憶體大小跟指針本身記憶體大小。直到整個駐列清空。
  • free(q) 釋放駐列所占記憶體大小。

q_insert_head































bool q_insert_head(queue_t *q, char *s)
{
    /* What should you do if the q is NULL? */
    if (q == NULL)
        return false;

    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    /* Allocated failed */
    if (newh == NULL)
        return false;

    /* Don't forget to allocate space for the string and copy it */
    char *value = malloc((strlen(s) + 1) * sizeof(char));
    if (value == NULL) {
        free(newh);
        return false;
    }
    strcpy(value, s);
    newh->value = value;
    /* What if either call to malloc returns NULL? */
    newh->next = q->head;

    if (q->size == 1)
        q->tail = newh;

    q->head = newh;
    q->size++;
    return true;
}
  • 若駐列不為空，我們創造一新指針，並用 malloc 配置一個空間給它。
  • 再用 strcpy 把值 copy 給 value，也就是新的駐列的記憶體位址。
  • 而後新指針指向新的駐列頭，這裡有個判斷當 size 為 1 時，駐列尾指向新指針。
  • 最後駐列大小加一。

q_inset_tail
































bool q_insert_tail(queue_t *q, char *s)
{
    /* You need to write the complete code for this function */
    /* Remember: It should operate in O(1) time */
    if (q == NULL)
        return false;

    list_ele_t *newt;
    newt = malloc(sizeof(list_ele_t));
    
    /* Allocated failed */
    if (newt == NULL) {
        return false;
    }

    char *value = malloc((strlen(s) + 1) * sizeof(char));
    if (value == NULL) {
        free(newt);
        return false;
    }
    strcpy(value, s);
    newh->value = value;
    q->tail->next = newt;
    q->tail = newt;
    q->tail->next = NULL;
    if (q->size == 1)
        q->tail = newt;
        q->head = newt;
    q->size++;
    return true;
}
  • 跟 q_insert_head 概念相同，每次執行後 q->tail 要後移一個才會指向最後一個值。

q_remove_head



















bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* You need to fix up this code. */
    if (q == NULL || q->size == 0)
        return false;
    list_ele_t *tmp = q->head;
    q->head = q->head->next;
    int copy_len = bufsize / sizeof(char) - 1;
    if (sp != NULL) {
        memcpy(sp, tmp->value, copy_len);
        sp[copy_len] = '\0';
    }
    free(tmp);
    q->size--;
    if (q->size == 0)
        q->tail = NULL;
    return true;
}
  • 先用一個 tmp pointer 儲存原始 head 作為後來的 free 以及字串處理使用。
  • 更新 q->head 並調整 size。
  • 題目要求要複製 bufsize - 1 長度的字串到 sp ，並在字串最後補上節數字元 ‘\0’，我這裡使用的是 memcpy 而非 strdup，memcpy 的第三個參數，表示的是要拷貝的長度，所以我們必須先計算這樣的長度代表幾個 char 並在適當位置補上結束字元。
  • 最後在針對 tmp 做釋放。
  • 若是在移除 head 之後，list 內沒有任何節點，重複上述所有步驟，q->head = q->head->next 並不會受到影響因為會被更新為 NULL。由於現在 list 內沒有任一結點，所以我們也要把 tail 設為 NULL。

q_size

int q_size(queue_t *q)
{
    /* You need to write the code for this function */
    /* Remember: It should operate in O(1) time */
    if (q == NULL)
        return 0;
    return q->size;
}

q_reverse

void q_reverse(queue_t *q)
{
    /* You need to write the code for this function */
    if (q == NULL)
        return false;
    list_ele_t *tmp = NULL;

    prev = q->head;
    while (prev) {
        tmp = q->head;
        q->head = q->head->next;
        free(tmp->value);
        free(tmp);
    }
    free(q);
}

qtest 分數














































































---	Trace		Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
ERROR: Freed queue, but 3 blocks are still allocated
---	trace-01-ops	0/6
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, and remove_head
ERROR:  Removed value meerkat != expected value gerbil
ERROR:  Removed value bear != expected value meerkat
ERROR:  Removed value gerbil != expected value bear
ERROR: Segmentation fault occurred.  You dereferenced a NULL or invalid pointer
ERROR:  Removal from queue failed (1 failures total)
---	trace-02-ops	0/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, reverse, and remove_head
ERROR:  Removed value gerbil != expected value squirrel
ERROR:  Removed value vulture != expected value gerbil
ERROR:  Removed value bear != expected value gerbil
ERROR:  Removed value gerbil != expected value bear
ERROR:  Removed value squirrel != expected value dolphin
Error limit exceeded.  Stopping command execution
---	trace-03-ops	0/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, and size
ERROR: Freed queue, but 6 blocks are still allocated
---	trace-04-ops	0/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head reverse, and size
ERROR:  Removed value gerbil != expected value dolphin
ERROR:  Removed value bear != expected value gerbil
ERROR:  Removed value meerkat != expected value bear
ERROR:  Removed value bear != expected value meerkat
ERROR: Segmentation fault occurred.  You dereferenced a NULL or invalid pointer
ERROR:  Removal from queue failed (1 failures total)
Error limit exceeded.  Stopping command execution
---	trace-05-ops	0/6
+++ TESTING trace trace-06-string:
# Test of truncated strings
ERROR:  Removed value aardvark_bear_dolphin_gerbil_jaguar != expected value meerkat_panda_squirrel_vulture_wolf
ERROR:  Removed value aardvark_bear_dolphin_gerbil_j != expected value meerkat_panda_squirrel_vulture
ERROR:  Removed value meerkat_panda_squirre != expected value aardvark_bear_dolphin
ERROR:  Removed value meerkat_ != expected value aardvark
ERROR:  Removed value meerkat_panda_squirrel_vulture_wolf != expected value aardvark_bear_dolphin_gerbil_jaguar
Error limit exceeded.  Stopping command execution
---	trace-06-string	0/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
ERROR: Freed queue, but 1 blocks are still allocated
---	trace-09-robust	0/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
ERROR: Freed queue, but 2 blocks are still allocated
---	trace-12-malloc	0/7
+++ TESTING trace trace-13-perf:
# Test performance of insert_tail
ERROR: Freed queue, but 2 blocks are still allocated
---	trace-13-perf	0/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
ERROR: Freed queue, but 2 blocks are still allocated
---	trace-15-perf	0/7
---	TOTAL		35/100
  • 分數還有待提高，這部份我還需要在修正。做單元測試有助於檢查函數可不可行，通常會以預期報錯或回傳正確來設計，當中也長用到 Pseudo code。

qtest 技巧 – signal handler

待補

解析 Valgrind 的運作原理和針對本程式的使用

待補

Last changed by 
 
P86071244顏伯任
0
208
Published on HackMD