2018q3 Homework2(lab0)

contributed by < type59ty >

tags:sysprog2018,hw2,lab0

---

開發環境

Distributor ID: Ubuntu
Description:    Ubuntu 16.04 LTS
Release:        16.04
Codename:       xenial

預期目標

• 英文閱讀
• C 語言程式設計基礎
• 準備 GNU/Linux 開發工具
• 學習使用 Git 與 GitHub
• 學習效能分析
• 研究自動測試機制

英文閱讀

閱讀以下文件

• C programming lab
• Overview
• Linked lists : Principles of Imperative Computation
  • 探討使用 linked list 使用實作 stack, queue
• How to Write a Git Commit Message

程式架構

從 github clone lab0-c
先查看裡面有哪些檔案

forest@ideal121:~/lab0-c$ ls
console.c  handin.tar  harness.h  Makefile  queue.c  README.md  report.h  traces
console.h  harness.c   LICENSE    qtest.c   queue.h  report.c   scripts

看一下README.md

需要修改這兩個檔案

• queue.h : Modified version of declarations including new fields you want to introduce
• queue.c : Modified version of queue code to fix deficiencies of original code

在 queue.c 中有這幾個 function:

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

queue.h

• 新增 tail pointer
• 新增 size

/* Queue structure */
typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail;
    size_t size;         /*
                         You will need to add more fields to this structure
                        to efficiently implement q_size and q_insert_tail
                      */
} queue_t;

queue.c

q_new()

• 初始化一個 queue

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

forest@ideal121:~/lab0-c$ make test
---	TOTAL		7/100

q_free()

• 功能：清空 queue 的內容
• 作法：先宣告一個 pinter x 指向 head，將x所指到的節點清除，並讓 q 不斷指向下一個節點，直到所有節點都清空，最後清除 q

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

q_insert_head()

• 功能：從 queue 的前端插入一個節點
• 作法：先分配一個空間給新節點 newh， s 指向這個節點的值，所以使用 strdup() 做一個 s 的副本，然後將 newh 指向原本的 head ，最後修改 q ，讓 q 指向新的 head newh
• 如果 queue 原本是空的，那麼這個節點同時是 head 也是 tail

bool q_insert_head(queue_t *q, char *s)
{
    if (q == NULL)
        return false;
    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (newh != NULL) {
        newh->value = strdup(s);
        if (newh->value == NULL) {
            return false;
        }
        if (q->size == 0) {
            q->tail = newh;
            newh->next = NULL;
        } else {
            newh->next = q->head;
        }
        q->head = newh;
        q->size++;
        return true;
    } else
        return false;
}

• strdup：The strdup() function returns a pointer to a new string which is a duplicate of the string s.
  strdup 函式可以回傳指向一個 string s 的副本的 pointer，它會根據 s 的大小 locate 一個空間，並且不會影響 s

char * __strdup (const char *s){
    size_t len =strlen (s) + 1;
    void *new =malloc (len);
    if (new == NULL)
        return NULL;
    return (char *)memcpy (new, s, len);}

q_insert_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));
    if (newt != NULL) {
        newt->value = strdup(s);
        if (newt->value == NULL) {
            free(newt);
            return false;
        }
        if (q->size == 0) {
            q->head = newt;
            newt->next = NULL;
        } else {
            q->tail->next = newt;
            newt->next = NULL;
        }
        q->tail = newt;
        q->size++;
        return true;
    } else
        return false;
}

forest@ideal121:~/lab0-c$ make test
---	TOTAL		42/100

• 測試 new, insert head, insert tail, free 功能是否正常

foest@forest-ubuntu:~/lab0-c$ ./qtest
cmd>new
cmd>new
q = []
cmd>ih 1
cmd>ih 1
q = [1]
cmd>it 2
cmd>it 2
q = [1 2]
cmd>free
cmd>free
q = NULL

• 雖然功能正常，但在 commit 時卻出現錯誤訊息：

[queue.c:69]: (error) Memory leak: newh
[queue.c:101]: (error) Memory leak: newt

• 原因是因為當判定新節點的值為 NULL 後， return false 前應該先把這個空間給清除，否則就產生了 memory leak 的問題，因此作以下修改：

if (newh->value == NULL) {
    free(newh);
    return false;
}

q_remove_head()

• 功能：移除 queue 的 head 節點並回傳它的值
• 作法：跟 free 概念差不多，只是只做第一步並且要考慮如何回傳節點值
  這邊使用 strncpy 是因為這個 function 可以設定要 copy 的大小，
  題目要求 copy size 為 bufsize-1，並且在字串最後加上 null terminator

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (q == NULL)
        return false;
    if (q->size == 0)
        return false;
    if (sp != NULL) {
        strncpy(sp, q->head->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    list_ele_t *x;
    x = q->head;
    if (q->head != NULL)
        q->head = q->head->next;
    q->size--;
    free(x);
    return true;
}

q_size()

• 功能：回傳 queue 的 size
• 作法：設定一個變數 size，在作其他操作時都會記錄 queue size的變化，因此可以達到
  $O(1)$ 時間複雜度

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

q_reverse()

• 功能：反轉 linked list 方向

• 作法：設定三個 pointer ： prev, current, prec 分別代表上個、目前、下個節點
  因為在單向的 linked list 當中，一個節點的位址只會被它上一個節點記錄，如果直接改變方向，下個節點就無法找到它的位址了，所以需要 pointer 來記錄原來的位址

  • 先設定 prev 為 q -> head，然後讓 prev 指向 NULL 當作 queue 的 tail
  • 讓 current 指向 prev，並持續循環下去
  • 當 prec 為 NULL 代表已經到 queue 的尾端，所以將 current 設為 head
  

void q_reverse(queue_t *q)
{
    if ((q == NULL) || (q->size == 0))
        return;
    list_ele_t *prev;
    list_ele_t *prec;
    list_ele_t *current;

    prev = q->head;
    current = prev->next;
    prec = current->next;
    prev->next = NULL;
    q->tail = prev;
    while (prec != NULL) {
        current->next = prev;
        prev = current;
        current = prec;
        prec = prec->next;
    }
    current->next = prev;
    q->head = current;
}

• 發現忘了考慮只有一個節點的情況，產生了錯誤

cmd>ih 2
q = [2]
cmd>reverse
cmd>reverse
ERROR: Segmentation fault occurred.  You dereferenced a NULL or invalid pointer
q = [2 ... ]

• 判斷式稍微改一下即可

if ((q == NULL) || (q->size <= 1))

make test

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

qtest

foest@forest-ubuntu:~/lab0-c$ ./qtest
cmd>new
cmd>new
q = []
cmd>ih 1
cmd>ih 1
q = [1]
cmd>it 2
cmd>it 2
q = [1 2]
cmd>ih 3
cmd>ih 3
q = [3 1 2]
cmd>reverse
cmd>reverse
q = [2 1 3]
cmd>rh
cmd>rh
Removed 2 from queue
q = [1 3]
cmd>rh
cmd>rh
Removed 1 from queue
q = [3]
cmd>reverse
cmd>reverse
q = [3]
cmd>free
cmd>free
q = NULL
cmd>quit
cmd>quit
Freeing queue

更新 repository

看了一下其他人的開發紀錄才發現， lab0-c 原始專案有做一點更動，需要 git rebase 更新 fork 出來的專案

foest@forest-ubuntu:~/lab0-c$ git remote add upstream https://github.com/sysprog21/lab0-c
foest@forest-ubuntu:~/lab0-c$ git pull upstream master
remote: Enumerating objects: 29, done.
remote: Counting objects: 100% (29/29), done.
remote: Compressing objects: 100% (7/7), done.
remote: Total 18 (delta 12), reused 17 (delta 11), pack-reused 0
Unpacking objects: 100% (18/18), done.
From https://github.com/sysprog21/lab0-c
 * branch            master     -> FETCH_HEAD
 * [new branch]      master     -> upstream/master
of https://github.com/sysprog21/lab0-c       
 - Separate subject from body with a blank line
Proceed with commit? [e/n/?] e
Merge made by the 'recursive' strategy.
 Makefile          |  2 --
 console.c         | 18 +++++++++---------
 harness.c         |  6 +++---
 harness.h         |  4 ++--
 qtest.c           |  8 ++++----
 report.c          | 17 ++++++++---------
 report.h          |  2 +-
 scripts/driver.py | 28 ++++++++++++++--------------
 8 files changed, 41 insertions(+), 44 deletions(-)

學習效能分析

• 後來想了一下發現在 q_insert_head 和 q_insert_tail 中的 strdup function 會使用到 malloc，但使用完卻沒有 free ，因此會造成 memory leak 的問題，這部份還需要做一下調整

研究自動測試機制

• 研究 Makefile
• Makefile：

CC = gcc
CFLAGS = -O0 -g -Wall -Werror

GIT_HOOKS := .git/hooks/applied
all: $(GIT_HOOKS) qtest

$(GIT_HOOKS):
	@scripts/install-git-hooks
	@echo

queue.o: queue.c queue.h harness.h
	$(CC) $(CFLAGS) -c queue.c 

qtest: qtest.c report.c console.c harness.c queue.o
	$(CC) $(CFLAGS) -o qtest qtest.c report.c console.c harness.c queue.o

test: qtest scripts/driver.py
	scripts/driver.py

clean:
	rm -f *.o *~ qtest 
	rm -rf *.dSYM
	(cd traces; rm -f *~)

• 在 C programming lab 中提到：

Evaluation
Your program will be evaluated using the fifteen traces described above. You will given credit (either 6 or 7 points, depending on the trace) for each one that executes correctly, summing to a maximum score of 100. This will be your score for the assignment—the grading is completely automated.
The driver program driver.py runs qtest on the traces and computes the score. This is the same program that will be used to compute your score with Autolab. You can invoke the driver directly with the command:
linux> ./driver.py
or with the command:
linux> make test

輸入 make test 指令後會執行 driver.py
裡面會執行15個測試，通過測試後即可得到對應的分數

1 : "trace-01-ops",
2 : "trace-02-ops",
3 : "trace-03-ops",
4 : "trace-04-ops",
5 : "trace-05-ops",
6 : "trace-06-string",
7 : "trace-07-robust",
8 : "trace-08-robust",
9 : "trace-09-robust",
10 : "trace-10-malloc",
11 : "trace-11-malloc",
12 : "trace-12-malloc",
13 : "trace-13-perf",
14 : "trace-14-perf",
15 : "trace-15-perf"

...

maxScores = [0, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7]

而最後一行，查了一下為什麼他要這樣寫： What does if __name__ == “__main__”: do?

if __name__ == "__main__":
    run(sys.argv[0], sys.argv[1:])

簡單來說，有些 python 程式需要 import 其他 python 程式當作 module，但沒有妥善處理會連同要 import 的那個程式的其他 function 也一併執行
因此 python 有個機制，當我們要編譯一個 python 程式，e.g example.py 時，編譯器會先定義一個特殊變數： __name__ 並賦予它值為 __main__，所以當我們加上if __name__ == "__main__"這個判斷，編譯器就會知道現在是在執行原來的程式，
而當其他程式 import example.py時， example.py 的 __name__ 會被設為 module 的名稱，而不再是__main__，因此就不會執行不該執行的區塊