Try   HackMD

2018q3 Homework2 (lab0)

contributed by < letticee >

課程助教

已改

作業說明：E01: lab0

  • 實驗環境
  • 學習 git 與 開發工具
  • 實作內容
  • 研究自動測試機制

實驗環境

$ uname -a
Darwin Cynthia-8.local 17.7.0 Darwin Kernel Version 17.7.0: Thu Jun 21 22:53:14 PDT 2018; root:xnu-4570.71.2~1/RELEASE_X86_64 x86_64

學習 git 與 開發工具

遇到的問題

  • 在 macOS 上跑 cppcheck 時，會出現一個錯誤，導致無法 commit

    [harness.c:147]: (error) Address of auto-variable 'new_block->payload' returned
    Fail to pass static analysis.

    猜測是因為他 return 了一個 local variable 的reference，出function就會消失了 (?

  • 目前處理方法：到 ./lab0-c/scripts/pre-commit.hook 加入一個 cppcheck 的 option –suppress 來擋住那個 error

    ​​​​CPPCHECK_OPTS="-I. -I./include --error-exitcode=1 . --suppress=*:./harness.c:147 ./"

實作內容

queue.h







/* Queue structure */
typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail;
    int size;
} queue_t;
  • 在 queue_t 中加入
    • list_ele_t *tail
      • 指向 queue 的尾端，使 q_insert_tail() 可以在常數時間內完成
    • int size
      • 紀錄 queue 的大小，使 q_size() 可以在常數時間內回傳 queue 的大小

q_new()

  1. 當 malloc 失敗時回傳 NULL
  2. 初始化 head = NULL, tail = NULL, size = 0

q_free()

  1. q 是 NULL 的話直接 return
  2. q 不是 empty 的話，先將 head 的指標複製一份到 ele，將 head 指標指到下一個元素。再 free 掉 ele 所指到的 value 跟 ele 指標
  3. free 掉 q
  • T(n)=O(n)

q_insert_head()

  1. q 是 NULL 的話回傳 false
  2. malloc 新的 head 的空間，如果失敗就回傳 false
  3. malloc 新的 head 的 value 空間，如果失敗 free 掉新的 head 、回傳 false
  4. 將傳入的字串複製到新的 head 的 value
  5. 將新的 head 的 next 指到原本 q 的 head，然後將 q 的 head 指到新的 head
  6. 如果 q 的 head 是 NULL (原本是 empty queue)，將 tail 也指到新的 head
  7. 將 q 的 size 加 1
  • T(n)=O(1)
  • 在配置空間和複製字串的部分，原本想要使用 strdup() 做到配置空間和複製字串的功能，但因為在 harness.h 裡有 define 使用自定義的 test_malloc() 取代 malloc()。實驗過後，發現 strdup() 在配置空間的時候不會呼叫到自定義的 test_malloc()，所以會造成 test 不過。
    • strdup() 版本
    




    ​​​​(newh->value) = strdup(s);
​​​​    if ((newh->value) == NULL) {
​​​​    free(newh);
​​​​    return false;
​​​​}
    • malloc() + strcpy() 版本
    





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

q_insert_tail()

  1. q 是 NULL 的話回傳 false
  2. malloc 新的 tail 的空間，如果失敗就回傳 false
  3. malloc 新的 tail 的 value 空間，如果失敗 free 掉新的 tail 、回傳 false
  4. 將傳入的字串複製到新的 tail 的 value
  5. 將原本 q 的 head 的 next 指到新的 tail，新的 tail 的 next 指到 NULL
  6. 將 q 的 tail 指到新的 tail
  7. 將 q 的 size 加 1
  • T(n)=O(1)

q_remove_head()

  1. q 是 NULL 或 empty ( head 是 NULL )的話回傳 false
  2. 如果 sp 不是 NULL，將 sp 空間內的 bufsize 大小範圍都設為 '\0'，然後將 head 的 value 中 bufsize - 1 大小的字串複製到 sp
  3. 先將原本的 head 的指標複製一份到 oldh，將 head 指到原本的 head 的下一個元素。再 free 掉 oldh 所指到的 value 跟 oldh 指標
  4. 將 q 的 size 減 1
  • T(n)=O(1)

q_size()

  1. q 是 NULL 或 empty ，回傳 0
  2. 回傳 q 的 size
  • T(n)=O(1)

q_reverse()

  1. q 是 NULL 或 empty 的話，直接 return
  2. 初始化 pre, itr, post 三個指標，分別指到 NULL, head, itr->next，然後將 tail 指到 head
  3. 迴圈內將 itr 的 next 指到 pre，pre 指到 itr ，itr 指到 post，post 指到 post 的 next ( 將所有元素的 next 指到前一個元素 )，直到 post 是 NULL，也就是 itr 指到的是 q 的最後一個元素
  4. 將 itr 的 next 指到 pre，將 head 指到 itr
  • T(n)=O(n)

研究自動測試機制

Makefile

  • 從 Makefile 可以得知 make 完後會產生一個 qtest 的可執行檔
  • make test 指令會去執行 driver.py
  • make clean 指令會清除 make 產生的檔案

自動評分系統運作的原理

  • 自動評分的主要程式是 driver.py
  • driver.py

    • 首先會呼叫 run()，run() 主要是處理參數（-h -p -t -v -a），接著呼叫Tracer.run()

      • -h：印出參數說明
      • -p：要測試的程式，預設是 ./qtest
      • -t：要測試的命令在 traceDict 裡的編號
      • -v：測試訊息的詳細程度（0 - 3），預設是 1
        • -v 0 參數：僅列出每個測驗的分數 
          ​​​​​​​​​​​​​​​​---	Trace		Points
​​​​​​​​​​​​​​​​---	trace-01-ops    6/6
​​​​​​​​​​​​​​​​---	trace-02-ops    6/6
​​​​​​​​​​​​​​​​---	trace-03-ops    6/6
​​​​​​​​​​​​​​​​---	trace-04-ops    6/6
​​​​​​​​​​​​​​​​---	trace-05-ops    6/6
​​​​​​​​​​​​​​​​---	trace-06-string 7/7
​​​​​​​​​​​​​​​​---	trace-07-robust 7/7
​​​​​​​​​​​​​​​​---	trace-08-robust 7/7
​​​​​​​​​​​​​​​​---	trace-09-robust 7/7
​​​​​​​​​​​​​​​​---	trace-10-malloc 7/7
​​​​​​​​​​​​​​​​---	trace-11-malloc 7/7
​​​​​​​​​​​​​​​​---	trace-12-malloc 7/7
​​​​​​​​​​​​​​​​---	trace-13-perf   7/7
​​​​​​​​​​​​​​​​---	trace-14-perf   7/7
​​​​​​​​​​​​​​​​---	trace-15-perf   7/7
​​​​​​​​​​​​​​​​---	TOTAL		100/100
          -v 1：多印出測驗內容 
          ​​​​​​​​​​​​​​​​---	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
          -v 2：多印出測驗的指令內容 
          ​​​​​​​​​​​​​​​​---	Trace		Points
​​​​​​​​​​​​​​​​+++ TESTING trace trace-01-ops:
​​​​​​​​​​​​​​​​cmd># Test of insert_head and remove_head
​​​​​​​​​​​​​​​​cmd>option fail 0
​​​​​​​​​​​​​​​​cmd>option malloc 0
​​​​​​​​​​​​​​​​cmd>new
​​​​​​​​​​​​​​​​cmd>ih gerbil
​​​​​​​​​​​​​​​​cmd>ih bear
​​​​​​​​​​​​​​​​cmd>ih dolphin
​​​​​​​​​​​​​​​​cmd>rh dolphin
​​​​​​​​​​​​​​​​Removed dolphin from queue
​​​​​​​​​​​​​​​​cmd>rh bear
​​​​​​​​​​​​​​​​Removed bear from queue
​​​​​​​​​​​​​​​​cmd>rh gerbil
​​​​​​​​​​​​​​​​Removed gerbil from queue
​​​​​​​​​​​​​​​​cmd>
​​​​​​​​​​​​​​​​---	trace-01-ops	6/6
          -v 3：多印出 queue 裡面儲存的內容 
          ​​​​​​​​​​​​​​​​---	Trace		Points
​​​​​​​​​​​​​​​​+++ TESTING trace trace-01-ops:
​​​​​​​​​​​​​​​​cmd># Test of insert_head and remove_head
​​​​​​​​​​​​​​​​cmd>option fail 0
​​​​​​​​​​​​​​​​cmd>option malloc 0
​​​​​​​​​​​​​​​​cmd>new
​​​​​​​​​​​​​​​​q = []
​​​​​​​​​​​​​​​​cmd>ih gerbil
​​​​​​​​​​​​​​​​q = [gerbil]
​​​​​​​​​​​​​​​​cmd>ih bear
​​​​​​​​​​​​​​​​q = [bear gerbil]
​​​​​​​​​​​​​​​​cmd>ih dolphin
​​​​​​​​​​​​​​​​q = [dolphin bear gerbil]
​​​​​​​​​​​​​​​​cmd>rh dolphin
​​​​​​​​​​​​​​​​Removed dolphin from queue
​​​​​​​​​​​​​​​​q = [bear gerbil]
​​​​​​​​​​​​​​​​cmd>rh bear
​​​​​​​​​​​​​​​​Removed bear from queue
​​​​​​​​​​​​​​​​q = [gerbil]
​​​​​​​​​​​​​​​​cmd>rh gerbil
​​​​​​​​​​​​​​​​Removed gerbil from queue
​​​​​​​​​​​​​​​​q = []
​​​​​​​​​​​​​​​​cmd>
​​​​​​​​​​​​​​​​Freeing queue
​​​​​​​​​​​​​​​​---	trace-01-ops	6/6
      • -A：在最後產生 JSON 格式的成績單

    • Tracer.run() 中會將 trace-01 – trace-15 依序執行一次 Tracer.runTrace()，根據回傳值判斷該測驗的分數、計算總分並印出成績

    • Tracer.runTrace() 呼叫 subprocess.call() 並傳入參數來執行 qtest

qtest 的行為和裡頭的技巧

  • qtest.c
    • 處理參數（-h -f -v -l）
      • -h：印出參數說明
      • -f：要讀入的 command 檔
      • -v：測試訊息的詳細程度
      • -l：將測試訊息輸出成檔
    • 在 console_init() 內呼叫 add_cmd() 來加入 cmd 指令
    • 處理每個指令的實作內容，包括檢查指令的參數、呼叫 queue 的 function 去操作 q、輸出警告和錯誤訊息（包括檢查 queue.c 的實作是否會發生 segmentation fault 和 timeout）
  • test_malloc() 和 test_free()
    • 在 harness.h 中可以看到有 define 使用自定義的 test_malloc() 取代 malloc()、 test_free() 取代 free()
    • 在 harness.c 的 test_malloc() 中會呼叫 fail_allocation() 根據現在的 fail_probability 機率回傳 NULL 。並將 malloc 的空間以 double linked list 儲存，以知道 malloc 了幾個 block (?，test_free() 也是從 linked list 去釋放空間
Last changed by 
 
Wei-Ting Lin
0
444
Published on HackMD