2018q3 Homework2 (lab0)

# 2018q3 Homework2 (lab0) contributed by < [`allenchen8210`](https://github.com/allenchen8210/lab0-c) > >* 請補上實驗環境 >* 中英文字間請以空白隔開 >* git commit message 應具體提出哪些修改，而非指說明改了哪個 function，請修正 > >[name=課程助教][color=red] >Architecture: x86_64 >Operating Sysetem: ubuntu16.04LTS >[name=jn][color=blue] 2018.09.27進度總結 * 成功 push 本地端到原端，修改 <int q_size(queue_t *q)> * 在想要 commit 時，會顯示格式有錯不符合 Consistent Code Style ，常常只知道是哪一份 code 出問題，但不知道確切位置，以及修改方式。有找到參考資料<[`Consistent Code Style`](http://dept.stat.lsa.umich.edu/~jerrick/courses/stat701/notes/codestyle.html) >。 ## 2018.09.27遇到問題： >code block 可以加上程式語言名稱，會有 syntax highlight，增加可讀性 >[name= 課程助教][color=red] >謝謝助教 >[name= jn][color=blue] ### Insert head 1.0 遇到的問題 ```clike= bool q_insert_head(queue_t *q, char *s) { if(s==NULL) return false; list_ele_t *newh; /* What should you do if the q is NULL? */ if (malloc(sizeof(list_ele_t)) == NULL) return false; else newh = malloc(sizeof(list_ele_t)); /* Don't forget to allocate space for the string and copy it */ /* What if either call to malloc returns NULL? */ newh->next = q->head; char *list_value; list_value = malloc(sizeof(*s)); *list_value = *s; newh->value = list_value; q->head = newh; (q->qsize)++; return true; } ``` #### Terminal: ![](https://i.imgur.com/YHcjfXD.png) * 這邊一直顯示錯誤 list_value 有確定存我想要的值進去。 >請直接複製文字內容，避免截圖 >[name=課程助教][color=red] >最後發現是因為原來在在 Insert head 1.0 第15行 list_value = malloc(sizeof(*s)); 沒有正確取到 string 長度，應該是需要 list_value = malloc((strlen(s)+1); ，詳細可以看下面 Insert Head 2.0 第12行。 >[name=jn][color=blue] ### Insert Head 2.0 ```clike= bool q_insert_head(queue_t *q, char *s) { if (!q || !s) return false; list_ele_t *newh = malloc(sizeof(*newh)); if (!newh) return false; char *content = malloc(sizeof(strlen(s) + 1)); if (!content) { free(newh); return false; } strcpy(content, s); if (!q->qsize) { q->head = newh; q->tail = newh; newh->next = NULL; newh->value = content; } else { newh->next = q->head; newh->value = content; q->head = newh; } q->qsize++; return true; } ``` ## 2018q3 第 3 週測驗題筆記 ### 測驗4 ```C #include <stdlib.h> #include <string.h> typedef struct rec { char *value; struct rec *next; } record; void insert_sorted(record **r, const char *value) { record *newrec = NULL; while (*r && strcmp(value, (*r)->value) > 0) r = &((F1)->next); newrec = malloc(sizeof(record)); newrec->value = F2(value); newrec->next = F3; F4 = newrec; } ``` :::info 這邊 F2 答案是 strcpy ，有個問題是 strcpy 不是需要兩個參數？查詢 Linux Programmer's Manual 如右 http://man7.org/linux/man-pages/man3/strcpy.3.html ::: * 測試 ```C int main () { char *src = "hello world"; char *dest = (char*)(malloc((sizeof(strlen(src)+1)))); if(!dest) return 0; dest = strcpy(src); printf("Final copied string : %s\n", dest); return(0); } ``` * 編譯結果 ``` test.c: In function ‘main’: test.c:11:11: error: too few arguments to function ‘strcpy’ dest = strcpy(src); ``` --- ### 測驗2 考慮以下程式碼，在 little-endian 硬體上，會返回 `1`，反之，在 big-endian 硬體上會返回 `0`: ```C int main() { union { int a; char b; } c = { .a = K1 }; return c.b == K2; } ``` #### 在 little-endian 硬體上(最低記憶體位址結尾) ![](https://i.imgur.com/7cs2orP.png) * c.a 在記憶體的表現 * 00000001 低記憶體位置 * 00000000 * 00000000 * 00000000 高記憶體位置 * c.b 在記憶體的表現 * 00000001 #### 在 big-endian 硬體上(最高記憶體位址結尾) ![](https://i.imgur.com/4P15rWA.png) * c.a 在記憶體的表現 * 00000000 低記憶體位置 * 00000000 * 00000000 * 00000001 高記憶體位置 * c.b 在記憶體的表現 * 00000000 :::info 這邊有個問題是，當union 在配置記憶體時，配置的空間是可以容納最大的 data type ，但是如題目，這樣 char 怎麼知道配置到什麼位置記憶體？上面的假設是當 overlapping 都取最低位置 ::: * Reference: * [`little-endian & big-endian`](https://blog.gtwang.org/programming/difference-between-big-endian-and-little-endian-implementation-in-c/) * [`How do I print bits in C?`](https://jameshfisher.com/2017/02/23/printing-bits.html) * 作者描述: My machine puts most-significant bytes in lower memory addresses (可知道他的是 big-endian ) --- ## 2018.09.30 lab0 作業進度要加把勁，還有自動評分系統解析 ``` +++ 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 --- trace-09-robust 7/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 --- trace-12-malloc 7/7 +++ TESTING trace trace-13-perf: # Test performance of insert_tail --- trace-13-perf 7/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 --- trace-15-perf 7/7 --- TOTAL 87/100 ``` ---- ## linked list reverse * 參考的實做方法: [Reversing a linked list | GeeksforGeeks](https://www.youtube.com/watch?v=D7y_hoT_YZI) ---- ## 送code更新流程 * 1. clang-format -i <file> //確認自己寫的 code 符合格式 * 2. git add . //確認自己更動的檔案要並送到準備區 * 3. git commit //寫 commit message * 4. git push * 5. 順利完成更新 :::info 在碰到 coed 格式不符合時，其實一開始只知道自己的 code 沒有符合規範，看完同學的流程才知道必須下第一行(1.) command 才過得了。但我自己實際做完後下去比較跟我原本沒修改的長得一樣，不清楚差別在那，還是只要有修改過一定要下第一行(1.) command? ::: :::info 更新心得常常會出錯都在 free(), malloc() , 這兩個很容易出錯，我假設其中一個 malloc() 有分到記憶體，另一個 malloc() 沒分到，測試程式也會抓得到，什麼時候自己有配置記憶體時一定要清楚，不然沒 free() ，就可能會產生 memory leak 問題，學 C 的好處就是充分掌握硬體。 ::: ## 剩下的13分目標明天完成 ``` +++ TESTING trace trace-03-ops: # Test of insert_head, insert_tail, reverse, and remove_head ERROR: Corruption detected in block with address 0x848d20 when attempting to free it --- trace-03-ops 0/6 +++ TESTING trace trace-04-ops: # Test of insert_head, insert_tail, and size --- trace-04-ops 6/6 +++ TESTING trace trace-05-ops: # Test of insert_head, insert_tail, remove_head reverse, and size --- trace-05-ops 6/6 +++ TESTING trace trace-06-string: # Test of truncated strings ``` ## 20181001 進度 :::danger 在使用 ih it 使用很長的字串，常常會有錯誤，如下，目前乃然無法解決，假設單個字元，不會有這樣問題，讓我有點傷腦筋，停在87分，如果沒辦法解決，明天就會跳過往 qtest 先做。 p.s. 發現超過 queue 在 free 8個字元就會出問題，就算 queue 只有一個8個字元，在free時也會出問題，然而 queue 有20000個7個字元在 free 時也不會出問題。 ::: ``` cmd>new cmd>new q = [] cmd>ih 1234567 20000 cmd>ih 1234567 20000 q = [1234567 1234567 1234567 1234567 1234567 1234567 1234567 1234567 1234567 1234567 1234567 1234567 1234567 1234567 1234567 1234567 1234567 1234567 1234567 1234567 1234567 1234567 1234567 1234567 1234567 1234567 1234567 1234567 1234567 1234567 ... ] cmd>free cmd>free q = NULL cmd>new cmd>new q = [] cmd>ih 12345678 cmd>ih 12345678 q = [12345678] cmd>free cmd>free ERROR: Corruption detected in block with address 0x12779b0 when attempting to free it q = NULL cmd> ``` --- ## 20181003 進度 * 太感動了，終於拿到剩下的13分，原來又是自己在使用 malloc沒寫好自己想要的大小，先上結果。 ``` +++ TESTING trace trace-13-perf: # Test performance of insert_tail --- trace-13-perf 7/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 --- trace-15-perf 7/7 --- TOTAL 100/100 ``` ### Insert Head 2.0 * 很手殘的沒注意到自己在第12行打了什麼， sizeof(strlen(s)) 拿到的是資料格式 size_t 的大小，這邊輸出的大小是8 bytes ```clike= bool q_insert_head(queue_t *q, char *s) { if (!q || !s) return false; list_ele_t *newh = malloc(sizeof(*newh)); if (!newh) return false; char *content = malloc(sizeof(strlen(s) + 1)); if (!content) { free(newh); return false; } strcpy(content, s); if (!q->qsize) { q->head = newh; q->tail = newh; newh->next = NULL; newh->value = content; } else { newh->next = q->head; newh->value = content; q->head = newh; } q->qsize++; return true; } ``` ### Insert Head 3.0(newest) * 更改後，先確定大小，再給 malloc ```clike= bool q_insert_head(queue_t *q, char *s) { if (!q || !s) return false; list_ele_t *newh = malloc(sizeof(*newh)); if (!newh) return false; int s_len = strlen(s)+1; //printf("string length excluding the terminating null byte = %d bytes\n", s_len-1); char *content = (char*)malloc(s_len*sizeof(char)); if (!content) { free(newh); return false; } //printf("obtain %lu bytes from malloc\n", strlen(content)); strcpy(content, s); //printf("actually obtain %lu bytes after use strcpy\n", strlen(content)); if (!q->qsize) { q->head = newh; q->tail = newh; newh->next = NULL; newh->value = content; } else { newh->next = q->head; newh->value = content; q->head = newh; } q->qsize++; return true; } ``` ### 輸出 * 可以發現我們輸入的字串不包括'\0'是10 bytes，而 malloc 回傳的是 15 bytes，而最後經過 strcpy 的大小是 10 bytes ``` allen@Mac:~/lab0-c$ ./qtest cmd>new cmd>new q = [] cmd>ih 1234567890 cmd>ih 1234567890 string length excluding the terminating null byte = 10 bytes obtain 15 bytes from malloc actually obtain 10 bytes after use strcpy q = [1234567890] cmd>quit cmd>quit Freeing queue ``` ___ ## [What comes after Moore’s Law](https://enterprisersproject.com/article/2018/9/what-comes-after-moores-law) * 可以發現到各大廠商 INTEL, GLOBALFOUNDRIES 都相繼停止研發下一代先進製程，一方面設備成本攤提過高，另一方面物理限制，但是隨者時間，製程的成本會陸陸續續下降。 * 看完這篇文章，因為物理的限制，軟體有了一片新的天空，因應新的特殊功能需求，而有需要特殊的晶片，而不在是包山包海的x86架構，不同的需求不同的架構不同的作業系統，都是可以深耕的點。 --- ## PM2.5 [透過區塊鏈提升空氣污染監測的可信度，以大規模部署和創造經濟誘因](https://www.youtube.com/watch?v=7FGfmEiju4k ) * 今天早上才在想，要做甚麼東西?目的是甚麼?我本身很在意空氣品質，我來台南已經快四年了，可以很明顯感受到空氣品質的下降。科技的發展，也犧牲了台灣人民的健康，看似微乎其微，但深深影響了我們。會不會有那麼一天大家出去除了得看今天會不會下雨？還要看今天空氣好不好？天氣我們不能掌控，但空氣的品質是我們大家可以監督的，雖然目前政府不承認這種民間的空氣盒子，但我想我們還有很多努力的空間，這是是一個貧富差距不斷跨大的年代，但也因為網路而拉進你我的距離。我想我找到著力點了。 * 這邊有個 [FB粉專](https://www.facebook.com/nopm2.5/) 也是會討論關於中南部空氣品質，希望大家讓這個議題不斷擴大。 --- ## 解釋自動評分系統運作的原理，提及 qtest 的行為和裡頭的技巧 ### $make qtest * 當你在 terminal 下上面那道 command 時， Makefile 會去抓 test 標籤，test 冒號(:)後面是需要這些條件才能執行，接著就會去執行，等同 $python scripts/driver.py ```= 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 ``` :::danger driver.py 裡面這個不了解，不清楚第一行的 __name__ 哪裡來的？還需要再了解 ::: ```= if __name__ == "__main__": run(sys.argv[0], sys.argv[1:]) ``` :::info 自使用自動評分系統時，主要還是透過 driver.py 去執行 ./qtest，蠻有趣的。第9行 retcode = subprocess.call(clist), 可以用讓 python 來執行外部程式。 ::: ```python= def runTrace(self, tid): if not tid in self.traceDict: print "ERROR: No trace with id %d" % tid return False 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 return retcode == 0 ``` :::info 接著就是解析指令，透過 getopt() 來解，舉下面 "hv:f:l:" 這個例子，會去找有沒有 h hv v f l ，後面有冒號就是必須要有另外一個參數，然後傳給 optarg。 ::: ```= while ((c = getopt(argc, argv, "hv:f:l:")) != -1) { switch (c) { case 'h': usage(argv[0]); break; case 'f': strncpy(buf, optarg, BUFSIZE); buf[BUFSIZE - 1] = '\0'; infile_name = buf; break; case 'v': level = atoi(optarg); break; case 'l': strncpy(lbuf, optarg, BUFSIZE); buf[BUFSIZE - 1] = '\0'; logfile_name = lbuf; break; default: printf("Unknown option '%c'\n", c); usage(argv[0]); break; } } ``` >解析完指令，不知道怎麼丟進去 20181004 >[name=jn][color=blue] > [bitwise](http://puremonkey2010.blogspot.com/2011/05/c-bitwise-operation.html)

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.