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 的 headNULL (原本是 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 的 headnext 指到新的 tail,新的 tail 的 next 指到 NULL
  6. 將 q 的 tail 指到新的 tail
  7. 將 q 的 size 加 1
  • T(n)=O(1)

q_remove_head()

  1. q 是 NULL 或 empty ( headNULL )的話回傳 false
  2. 如果 sp 不是 NULL,將 sp 空間內的 bufsize 大小範圍都設為 '\0',然後將 headvaluebufsize - 1 大小的字串複製到 sp
  3. 先將原本的 head 的指標複製一份到 oldh,將 head 指到原本的 head 的下一個元素。再 free 掉 oldh 所指到的 valueoldh 指標
  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. 迴圈內將 itrnext 指到 prepre 指到 itritr 指到 postpost 指到 postnext ( 將所有元素的 next 指到前一個元素 ),直到 postNULL,也就是 itr 指到的是 q 的最後一個元素
  4. itrnext 指到 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.ctest_malloc() 中會呼叫 fail_allocation() 根據現在的 fail_probability 機率回傳 NULL 。並將 malloc 的空間以 double linked list 儲存,以知道 malloc 了幾個 block (?,test_free() 也是從 linked list 去釋放空間