changed 2 years ago  
Linked with GitHub

2023q1 homework1 (lab0)開發日誌

contributed by < Urbaner3 >

注意 GitHub 帳號名稱。我已經幫你修改了。

yanjiew1

感謝，其實我也很猶豫，那是我一開始設定的情形。

Urbaner

tags: linux2022,linux kernel

Reviewed by yanjiew1

  • commit message 語意表達不太清楚，開頭沒有大寫。例如： c7fe7ff ，implem_t del_mid 可改為 Implement q_delete_mid 。
  • Coding style 沒有符合規範，建議善用 clang-format -i 來協助調整 Coding style 。例如下方 q_delete_dup 的程式： 
    






    ​​  if(strcmp(val1->value, val2->value) == 0){
​​      list_del(val1);
​​      q_release_element(cur);
​​      break;
​​  }
​​  else
​​      printf("mulp is %c\n",mulp);
    5, 6 行 ： else 和 } 應為同一行； 第 1 行： ) 和 { 中間要有空格。可改為： 
    





    ​​​​if(strcmp(val1->value, val2->value) == 0) {
​​​​    list_del(val1);
​​​​    q_release_element(cur);
​​​​    break;
​​​​} else
​​​​    printf("mulp is %c\n", mulp);
  • 完成度不高，沒達到作業要求，但可以從共筆中看到你的努力。未來繼續努力，加油！

實驗環境

(base) urbaner@urbaner:~$ gcc --version
gcc (Ubuntu 12.2.0-3ubuntu1) 12.2.0

(base) urbaner@urbaner:~$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  4
  On-line CPU(s) list:   0-3
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i3-7100 CPU @ 3.90GHz
    CPU family:          6
    Model:               158
    Thread(s) per core:  2
    Core(s) per socket:  2
    Socket(s):           1
    Stepping:            9
    CPU(s) scaling MHz:  21%
    CPU max MHz:         3900.0000
    CPU min MHz:         800.0000
    BogoMIPS:            7799.87
Virtualization features: 
  Virtualization:        VT-x
Caches (sum of all):     
  L1d:                   64 KiB (2 instances)
  L1i:                   64 KiB (2 instances)
  L2:                    512 KiB (2 instances)
  L3:                    3 MiB (1 instance)
NUMA:                    
  NUMA node(s):          1
  NUMA node0 CPU(s):     0-3

作業要求

lab0

queue.c 介面

  • q_new: 建立新的「空」佇列;
  • q_free: 釋放佇列所佔用的記憶體;
  • q_insert_head: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則);
    ︙
    (後續…參閱[queue.c 介面])

開發過程

簡介：

完成作業要求，得到一個完整可控制排序的介面，包含自動偵錯、結果輸出、測試。熟悉專案開發環境，多人一起合作，認識程式從編碼，執行過程中控制，錯誤停止相關的觀念及技術等。這份作業可以輸入多個文字節點，利用 linux 內核鏈結序列結構，依照開頭順序，做需要的處理，包含排序、刪除重複、交換、翻轉順序等等。如例題：刪除重複。

你所不知道的 C 語言：編譯器和最佳化原理篇，背景知識回顧: The C++ Build Process Explained 此章節有
AST 產生之程序，以利於確認所有標頭檔，如下：

gcc -H -O0 -std=c99 -g -c -o queue.o queue.c

參考作業： laneser_2022q1 ，共筆示範

q_new

三步驟，配置空間、檢查開頭非空、控制指標。

建議寫清楚一點，這樣子太文言看不懂

yanjiew1

我放程式碼加上註解

Urbaner3

   struct list_head *q = malloc(sizeof(struct list_head))           // 配置空間      
    if (!list_empty(q))                                          // 檢查開頭非空          
        INIT_LIST_HEAD(q);                                           //控制指標           
    return q;       

@@ -16,7 +16,8 @@
 {
     struct list_head *q = malloc(sizeof(struct list_head));
     if (!list_empty(q))
-        INIT_LIST_HEAD(q);
+        return NULL;
+    INIT_LIST_HEAD(q);
     return q;
 }

改為 !q寫法 通過 make test 測試13，原理待釐清。

q_free

(1)element_t (2)q_release_element (3)list_for_each_entry_safe 經過兩次修改三處，閱讀並理解後，確認函數為如下：

void q_free(struct list_head *l) {
    if (l == NULL)
        return;
    element_t *n, *s;
    list_for_each_entry_safe (n, s, l, list)
        q_release_element(n);
    free(l);
}

老師舉 yanjiew 同學的例子，讓我另一個疑惑，free 到底作用在哪個結構更有興趣去探討了。

free 要作用在當初用 malloc 配置記憶體的結構上。故串列的頭是 struct list_head ，而串上去有存值的節點是 element_t 。

yanjiew1

q_insert_head & tail

因為對list結構，只知道細節，目前當作規格一樣遵守，日後維護時一併觀察。 越用越習慣了。
注意到需要用 strdup 函數，並將 insert 共用部份縮減為 part_ins 函式。

element_t *part_ins(char *s)
{
    element_t *new_ele = malloc(sizeof(element_t));
    if (new_ele == NULL)
        return NULL;
    new_ele->value = strdup(s);
    if (new_ele->value == NULL) {
        free(new_ele);
        return NULL;
    }
    return new_ele;
}

bool q_insert_head(struct list_head *head, char *s)
{
    if (head == NULL)
        return false;
    element_t *new_ele = part_ins(s);
    if (new_ele == NULL)
        return false;
    list_add(&new_ele->list, head);
    return true;
}

bool q_insert_tail(struct list_head *head, char *s)
{
    if (head == NULL)
        return false;
    element_t *new_ele = part_ins(s);
    if (new_ele == NULL)
        return false;
    list_add_tail(&new_ele->list, head);
    return true;
}

可以想想 q_insert_tail 可以怎麼利用 q_insert_head 來達成。可以參考我寫的。

yanjiew1

q_remove_head

很疑惑 q_remove_head 函數，其中的兩個參數，{ char *sp, size_t bufsize }，還有 q_remove_head 程式碼的 macro 巨集 container_of，發現 jserv 之前有做說明 container_of 附註於你所不知道的 C 語言: linked list 和非連續記憶體(含目錄) 另外 linked list 案例實作，這兩個連結是一樣的，但一個有包含你所不知道的 C 語言系列目錄。此處與 link 情形類似，可以注意它的插圖，幫助理解。注意有用到 strncpy 貼上 bufsize ，有些同學提到使用 memcpy 列於考慮中。好的說明，類似複製變數值的道理，將第三個變數稱作 buffer ，最後在結尾補上0，完成刪除的動作。

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    element_t *n = container_of(head->next, element_t, list);
    list_del(head->next);
    if (sp != NULL) {
        strncpy(sp, n->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return n;
}

共筆中英文和中文之間要有空格。
漢語表達不太清楚。例如：「有用到 strncpy 貼上 bufsize 」這句話， 應該可以改成「使用 strncpy 函式，將 n->value 中的字串複製到 sp 中，最多複製 bufsize - 1 個字元。」。可以善用 ChatGPT 來改進。

yanjiew1

q_remove_tail

修改一次兩處： (1)head 要做檢查。 (2)可以盡量使用 q_remove_head
因為對head的檢查，以及類似的指標是否為空，此一類檢查另我覺得很冗贅，所以思索原因並設計實驗確認，如以下，實驗方法與結果。

(base) urbaner@urbaner:~/linux2022/lab0-c$ make SANITIZER=1
  CC	queue.o
queue.c: In function ‘q_new’:
queue.c:20:8: error: ‘rr’ is used uninitialized [-Werror=uninitialized]
   20 |     if (!rr)
      |        ^
queue.c:19:23: note: ‘rr’ was declared here
   19 |     struct list_head *rr;
      |                       ^~
cc1: all warnings being treated as errors
make: *** [Makefile:50: queue.o] Error 1
(base) urbaner@urbaner:~/linux2022/lab0-c$ vim queue.c

只看文字無法了解你想表達的意思，建議在共筆貼出此段程式碼，文字描述寫完整一點。

yanjiew1

已修正並標示下方段落。

Urbaner3

實驗方法與結果

struct list_head *q_new()
{
    struct list_head *q = malloc(sizeof(struct list_head));    
    puts("check if sturct initial and malloc are null");
    if (q != NULL)
        printf("malloc is not null\n");
    else
        puts("sorry, malloc is null @@");
    if (list_empty(q))
        puts("list is empty");
    else if (list_empty(q)==0)
        puts("not empty!!");
    if (q != NULL)
        INIT_LIST_HEAD(q);
    if (q != NULL)
        printf("malloc is not null\n");
    else 
        puts("sorry, malloc is null @@");
    if (list_empty(q))
        puts("list is empty");
    else if (list_empty(q)==0)
        puts("not empty!!");
    return q;                                                                  
}  

void q_free(struct list_head *l)                                               
{        
    if (l == NULL)                   
        return; 
    element_t *n, *s;    
    int lp_l, lp_nl;
    list_for_each_entry_safe (n, s, l, list)
        q_release_element(n);
    raise(SIGINT);
    free(l);   
    lp_l=list_empty(l);        
    if (lp_l == 0){
        puts("l not empty in q_free");  
    }
    lp_nl=list_empty(&n->list);               
    raise(SIGINT);
    if (lp_nl == 0)  
        puts("n not empty in q_free");  
}            

(base) urbaner@urbaner:~/linux2022/lab0-c$ make SANITIZER=1
  CC	queue.o
  CC	random.o
  CC	dudect/constant.o
  CC	dudect/fixture.o
  CC	dudect/ttest.o
  CC	linenoise.o
  LD	qtest
(base) urbaner@urbaner:~/linux2022/lab0-c$ ./qtest
cmd> new
check if sturct initial and malloc are null
malloc is not null
not empty!!
malloc is not null
list is empty
l = []
cmd> 

(base) urbaner@urbaner:~/linux2022/lab0-c$ scripts/debug.py -d
Reading symbols from /home/urbaner/linux2022/lab0-c/qtest...

cmd> free

Program received signal SIGINT, Interrupt.
__pthread_kill_implementation (no_tid=0, signo=2, threadid=<optimized out>) at ./nptl/pthread_kill.c:44

malloc 函式初始化指標，其值為非 NULL ，這樣我們知道不需要測試，足以繼續開發。 list_empty 在 new 指令 q_new 函數前後能分別指令效果。所以應該把有關測試的檔案，其中 if(q!=NULL) 片段修改為 if(list_empty(q)) 才有意義。這告訴我們要習慣用 else if 來作測試，尤其是必須確認 if 條件式當中的變數值時。
於是將 q_new, q_free, q_insert_head, q_insert_tail, q_remove_head, q_remove_tail 都進行 if 條件式的修正。 CONTRIBUTING.md 檔案有說明，有比較好標準的 if 敘述參考。 至此完成初步操作，通過 make check 的要求。接下來的部份，會在發布前先暫時貼在這裡，通過測試後，再整理筆記。

無法理解你的意思。

當 malloc 回傳值不為 NULL 時，表示空間配置成功。然而，配置的記憶體空間是未初始化的，可能包含先前該記憶體位置上的舊資料。因此，在使用前應先進行初始化。

yanjiew1

q_delete_mid

bool q_delete_mid(struct list_head *head)       
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/   
    if (!head || list_empty(head)) {                                           
        return false;         
    }        
    struct list_head *h = head->next;     
    struct list_head *t = head->prev;    
    while (true) {    
        if (h == t || h->next == t) {  
            list_del(h);   
            q_release_element(list_entry(h, element_t, list));                 
            break;     
        } else {    
            puts("del tail case.");   
            break;    
        }   
        h = h->next;   
        t = t->prev;
    }
    return true;
}

按照 leetcode 的提示，刪去前方的節點。
失敗案例，沒定好結束條件，有最優化的程式提示錯誤：

cmd> it tig
l = [meer dolp bea ger bea ger tig]
cmd> rt tig
Removed tig from queue
l = [meer dolp bea ger bea ger]
cmd> dm
del tail case.
l = [meer dolp bea ger bea ... ]
ERROR:  Queue has more than 5 elements
cmd> show
Current queue ID: 0
l = [meer dolp bea ger bea ... ]
ERROR:  Queue has more than 5 elements

h 和 t 二個指標相遇時，應該要刪除 t 才對。

yanjiew1

已標注失敗案例，考慮今後省略，對開發無幫助，也無法交流，僅為我個人的疑慮。
下方補上程式碼。

補完程式碼：

        if (h->next == t) {
            list_del(t);
            q_release_element(list_entry(t, element_t, list));
            break;
        }
        h = h->next;       
        t = t->prev;

q_delete_dup

需要比對字串，因為 element_t 型別預設 value 為 char 型別，先指定strcmp做函數，找到三種作法，參考 for, while, cut_position, 可以學到不同的函式用法，能較快熟練 linked list 的細節。

縮減筆記篇幅，將疑惑與困難記錄收錄到另一份筆記。
link: dedup

digraph structs {
        rankdir=LR;
        node[shape=circle];
        struct0 [label= "head"];
        struct1 [label= "1"];
        struct2 [label= "1"];
        struct3 [label= "1"];   
        struct4 [label= "2"];
        struct5 [label= "3"];
        struct6 [shape=plaintext label="cut"];
        struct7 [shape=plaintext label="it"];
        struct8 [shape=plaintext label="safe"]
        
        struct0 -> struct1 -> struct2 -> struct3 -> struct4 -> struct5;
        struct7 struct6 struct8
        {rank = same; struct0; struct6};
        {rank = same; struct1; struct7};
        {rank = same; struct2; struct8};
}

digraph structs {
        rankdir=LR;
        node[shape=circle];
        struct0 [label= "head"];
        struct1 [label= "1"];
        struct2 [label= "1"];
        struct3 [label= "1"];   
        struct4 [label= "2"];
        struct5 [label= "3"];
        struct6 [shape=plaintext label="cut"];
        struct7 [shape=plaintext label="it"];
        struct8 [shape=plaintext label="safe"]
        
        struct0 -> struct1 -> struct2 -> struct3 -> struct4 -> struct5;
        struct7 struct6 struct8
        {rank = same; struct0; struct6};
        {rank = same; struct2; struct7};
        {rank = same; struct3; struct8};
}

digraph structs {
        rankdir=LR;
        node[shape=circle];
        struct0 [label= "head"];
        struct1 [label= "1"];
        struct2 [label= "1"];
        struct3 [label= "1"];   
        struct4 [label= "2"];
        struct5 [label= "3"];
        struct6 [shape=plaintext label="cut"];
        struct7 [shape=plaintext label="it"];
        struct8 [shape=plaintext label="safe"]
        
        struct0 -> struct1 -> struct2 -> struct3 -> struct4 -> struct5;
        struct7 struct6 struct8
        {rank = same; struct0; struct6};
        {rank = same; struct3; struct7};
        {rank = same; struct4; struct8};
}

如圖示，保持 cut 位置，移到比對相異時，safe 的節點，分開兩個 list。按照 list_cut_position 的定義，傳入參數。
code_page

swap and sort

merge_sort node ed., list ed., recursive

my work of merge sort 其中含有 merge_two 自訂函式

work of swap

void q_sort(struct list_head *head)                                            
{                                                                              
    /* Remove every node which has a node with a strictly greater value anywhere
     * to the right side of it */                                              
    /*https://npes87184.github.io/2015-09-12-linkedListSort/ */                
    if (!head || !head->next)           
        return head;                                                  
    struct list_head *fast = head->next;  
    struct list_head *slow = head;                                             
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    /*reset fast node, cut the list*/                  
    fast = slow->next;
    slow->next = NULL;                                                         
    q_sort(head); 
    q_sort(fast);                                                                   
    two_merge(head, fast);

trace 04, 05

reverse (and merge)

依序將節點從頭走訪，再將開頭視為另一表單入口，很像瓶口向瓶底送，先進後出，FILO。

merge

實作時使用 list 儲存排序後結果。把 iterative merge 排序後接上，結合 yanjiew, alan 的作法，寫出表單版本的合併。最後考慮若迴圈結束時， l1 或 l2 為空，將剩餘表單依序接在新做表單，再去做切割。

trace 03, 05

static void merge_two(struct list_head *l1, struct list_head *l2){             
    if (!l1 || !l2)
        return 0;
    element_t *nod1, *nod2;
    LIST_HEAD(newhd);
    nod1 = list_first_entry(l1,element_t,list);
    nod2 = list_first_entry(l2,element_t,list);
    while (l1 && l2){                                                          
        if (strcmp(nod1->value, nod2->value) < 0)                              
            /*add l1 node to tail of newhd list */                             
            list_move_tail(l1, &newhd);                                         
        else                                                                   
            list_move_tail(l2, &newhd);                                        
    }                                                                                                            
    list_splice(&newhd, l1);                                                   
    list_splice(                                                               
                                                                               
                                                                               
} 

  struct list_head *temp = LIST_HEAD(nh);
    struct list_head *q = temp;                                                
    element_t *ll1, *ll2;                                                             
    while (l1 && l2) {     
        ll1 = list_entry(l1, element_t, list);     
        ll2 = list_entry(l2, element_t, list);     
        if (*ll1->value < *ll2->value) {       
            temp->next = l1;       
            temp = temp->next;        
            l1 = l1->next;        
        } else {      
            temp->next = l2;        
            temp = temp->next;        
            l2 = l2->next;           
        }              
    }                                                                                         
    if (l1)              
        temp->next = l1;
    if (l2)             
        temp->next = l2;

    struct list_head *head = q->next;
    list_del(q);
    free(q);
    return head;

釐清 queue_context 這個結構之後，可以理解 alan 的程式碼，把 qc 命名之後，改正 size 的名字為 cnt_len，避免與 q_size 搞混。
先記錄第一列的資料，再引入迴圈，讀取第二列數列資料，合併和刪除空數列，即完成。

work of code

dedup reverseK, descend

trace 06

根據 yanjiew descend 為所有點右邊不可有更大的值或字串，從右邊開始，刪去小於尾端的值或字串，整理到開頭。 ascend 則相反。

work of code

Valgrind 與 自動程式設計

Web server

./qtest
cmd> web
listen on port 9999, fd is 3
cmd> Unknown command '.'
cmd> Unknown command 'favicon.ico'
cmd> l = []
cmd> Unknown command 'favicon.ico'
cmd> l = [1]
cmd> Unknown command 'favicon.ico'
cmd> l = [2 1]
cmd> Unknown command 'favicon.ico'
Error limit exceeded.  Stopping command execution

epoll_program

亂數 ＆ Dudect 論文

chi_square_test
t-test excel

檢查，yanjiew

/lab-0/dudect/ttest.c , only push, compute and init
3 functions.

/ob…/dudect/src/dudect.h, 4 structs ; public,init,main,free, randombits, randombytes

cmp, percentile, cpucycles(), measure, report_test, test percentile in dedect_ctx_t

Select a repo