2018q3 Homework2 (lab0)

contributed by < Jyun-Neng >

請補上實驗環境
課程助教

• 修改 Makefile
  • 刪除以下兩行則執行 make 指令後便不會產生 handin.tar
  ​​​​-tar -cf handin.tar queue.c queue.h
  ​​​​tar cf handin.tar queue.c queue.h
  

  handin.tar 的存在是為了 CMU Autolab 使用，以我們的使用情境來說，的確多餘，歡迎送 pull request 過來
  

  jserv

Implementation of Queue

Queue Structure

• 新增記錄 queue 內 element 總數的 size
• 新增 pointer to tail node in queue。

typedef struct {
    list_ele_t *head; // pointer to head element
    list_ele_t *tail; // pointer to tail element
    int size; // queue size
}    

Create empty queue

• 需要判斷若 malloc 回傳 NULL 的情況。

if (q) {
    q->head = NULL;
    q->tail = NULL;
    q->size = 0;
}

Free all storage used by queue

• 釋放 queue 的空間
• 釋放 queue 內 element 的空間

雖說若 q 是 NULL 則 free(q) 不會運作，
但 pos = q->head 在 q 是 NULL 的情況下會導致 segmantation fault。因此，仍需要判斷 q 是否為 NULL。

if (!q) // prevent to execute line 4
    return;
        
list_ele_t *pos = q->head;
while (pos) {
    list_ele_t *tmp = pos;
    pos = pos->next_node;    
    free(tmp);
}
free(q);

Insert element at head of queue

• 判斷 queue 是否為 NULL。
• 判斷 malloc 新的 element 是否回傳 NULL。
• queue size 要增加。
• 要考慮 tail pointer，當加入第一個 element 時 tail pointer 也須指向此 element。

if (!q)
    return false;
    
list_ele_t *newh;
newh = (list_ele_t *) malloc(sizeof(list_ele_t));
    
if (newh) {
    newh->value = strdup(s);
    newh->next = q->head;
    q->head = newh;
    if (++(q->size) == 1)
        q->tail = q->head; // tail node should be asigned at first insertion
    return true;
}
return false;

Insert element at tail of queue

• 判斷 queue 是否為 NULL。
• 判斷 malloc 新的 element 是否回傳 NULL。
• queue size 要增加。
• 要考慮 head pointer，當加入第一個 element 時 head pointer 也須指向此 element。

if (!q)
    return false;

list_ele_t *newt;
newt = (list_ele_t *) malloc(sizeof(list_ele_t));

if (newt) {
    newt->next = NULL;
    newt->value = strdup(s);
    if (++(q->size) == 1)
        q->head = newt; // head node should be assigned at first insertion
    else
        q->tail->next = newt;
    q->tail = newt;
    return true;
}
return false;

Remove element from head of queue

• 當 q 或者 q->head 是 NULL 時，回傳 false。
• queue size 要減少。
• 要釋放移除的 element 的記憶體空間。
• 要顯示移除的 element 內記錄的字串。
• 複製移除字串。

若 sp 不是 NULL，被移除的 element 內儲存的字串需複製到 sp 且要比較字串長度及bufsize，若字串長度大於 bufsize-1 ，僅複製 bufsize-1 的字串。反之，則複製整個字串大小，且最後都需加入 null character。

if (!q || !(q->head))
    return false;
        
list_ele_t *tmp = q->head;
unsigned long size;

if (sp) { // copy the removed string
    size = strlen(tmp->value);
    size = (size > bufsize - 1) ? bufsize - 1 : size;
    strncpy(sp, tmp->value, size);
    sp[size] = '\0';
}
q->size--;
q->head = q->head->next;
free(tmp);
return true;

free 字串會出現 double free error 是 strdup 惹的禍，因為 harness.h 有段 macro 會把 free 換成一個自己開發的函式，導致你用不到真正的 free ，變成在用 malloc 與 test_free ，因此直接用 malloc 讓 preprocessor 把它也轉成 test_malloc 就好了。
pjchiou2018 Sep 27 Thu 05:58

Return number of elements in queue

• 由於我們已經在 queue structure 新增記錄 size 的變數，因此只需回傳當前紀錄queue大小的 size 變數即可，運算時間及為
  $O(1)$。
• 若queue已經被釋放記憶體空間或根本沒有queue存在，直接回傳 0。

return (q) ? q->size : 0;

Reverse elements in queue

• 當不存在 queue、queue 內是空的、只有一個 element，不需動作。
• 需要三個 pointers 來記錄當前、下一個、前一個的 element。
• Time complexity:
  $O(n)$

next = q->head->next;
prev = q->head;
while (next) {
    pos = next;
    next = next->next;
    pos->next = prev;
    prev = pos;
}

Test Results

$make test
.
.
.
TOTAL 100/100

分析測試的結果，剩餘的錯誤是因為尚未完成 reverse 所導致，其餘的部分皆已完成且通過測試。

未完成 reverse 的測試結果: 81/100
LawrenceSat, Sep 22, 2018 11:35 PM

Reverse 完成後發現 remove 是有問題的，string copy 沒有分辨好要複製的長度及沒有加 null character。

LawrenceSun, Sep 23, 2018 3:34 PM

修改完 copy string 的問題後測試完成: 100/100
LawrenceSun, Sep 23, 2018 3:36 PM

請繼續更新！
– 課程助教

自動評分系統

driver.py

getopt

optlist, args = getopt.getopt(args, 'hp:t:v:A')

這段程式碼將所需的參數存到 optlist

Python documentation – getopt

• Parses command line options and parameter list. args is the argument list to be parsed, without the leading reference to the running program. Typically, this means sys.argv[1:]. options is the string of option letters that the script wants to recognize, with options that require an argument followed by a colon (: ; i.e., the same format that Unix getopt() uses).

>> import getopt
>> args = ['-h', '-p', 'xx', '-t', 'xxx', '-v', 'xxxx', '-A']
>> optlist, args = getopt.getopt(args, 'hp:t:v:A')
>> optlist
[('-h', ''), ('-p', 'xx'), ('-t', 'xxx'), ('-v', 'xxxx'), ('-A'. '')]
>> args
[]

runTrace

runTrace 為執行測試指令的函式

fname = "%s/%s.cmd" % (self.traceDirectory, self.traceDict[tid])
vname = "%d" % self.verbLevel
clist = [self.qtest, "-v", vname, "-f", fname]
try:
    retcode = subprocess.call(clist)
except Exception as e:
    print "Call of '%s' failed: %s" % (" ".join(clist), e)
    return False

retcode = subprocess.call(clist)
等同於執行 command line ./qtest -v -f ./traces/file.cmd，qtest 便會執行 file.cmd 的指令來測試。

qtest.c

測試程式的指令是由 console.[ch] 來管理，且是用 linked list 來儲存新增的指令。

/* Information about each command */
/* Organized as linked list in alphabetical order */
typedef struct CELE cmd_ele, *cmd_ptr;
struct CELE {
    char *name;
    cmd_function operation;
    char *documentation;
    cmd_ptr next;
};