--- tags: lab0-c, linux2023 --- # 2023q1 Homework1 (lab0) contributed by < `EdwardCKC` > ## 開發環境 ```shell gcc --version gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0 $ 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): 12 On-line CPU(s) list: 0-11 Vendor ID: GenuineIntel Model name: 12th Gen Intel(R) Core(TM) i5-12400 CPU family: 6 Model: 151 Thread(s) per core: 2 Core(s) per socket: 6 Socket(s): 1 Stepping: 2 CPU max MHz: 5600.0000 CPU min MHz: 800.0000 BogoMIPS: 4992.00 Virtualization: VT-x L1d: 288 KiB (6 instances) L1i: 192 KiB (6 instances) L2: 7.5 MiB (6 instances) L3: 18 MiB (1 instance) NUMA node0 CPU(s): 0-11 ``` ## 開發過程 :::danger 說好的進度呢？ :notes: jserv ::: ### `q_insert_head` & `q_insert_tail` 一開始如下: `malloc` 的 + 1 是要補 `\0` 在 string 的尾端 ，不然會有 overflow 的問題 ```cpp { if (!head || !s) return false; element_t *new_node = malloc(sizeof(element_t)); if (!new_node) return false; new_node->value = (char *) malloc(sizeof(char) * strlen(s) + 1); if (!new_node->value) { free(new_node); return false; } strncpy(new_node->value, s, strlen(s) + 1); list_add(&new_node->list, head); free(s); return true; } ``` 之後發現 `free()` 不能釋放不是`malloc()` / `calloc()` 的記憶體空間 :::warning 改進漢語表達。 :notes: jserv ::: ``` cmd> ih 1 ERROR: Attempted to free unallocated block. Address = 0x55e0a6498020 ERROR: Attempted to free unallocated or corrupted block. Address = 0x55e0a6498020 ERROR: Corruption detected in block with address 0x55e0a6498020 when attempting to free it l = [1] ``` 為了加強自己對指標的了解，把 `element_t *value` 和 `*s` 印了出來 ``` cmd> ih 1 -------- ptr value &new_node->value: 0x563781585000 new_node->value: 0x563781585050 *new_node->value: 85 -------- ptr s &s: 0x7ffda928e478 s: 0x563781585ba0 *s: 49 -------- after strncpy -------- ptr value &new_node->value: 0x563781585000 new_node->value: 0x563781585050 *new_node->value: 49 -------- ptr s &s: 0x7ffda928e478 s: 0x563781585ba0 *s: 49 l = [1] ----------------------------- cmd> ih 1 -------- ptr value &new_node->value: 0x5637815850b0 new_node->value: 0x563781585100 *new_node->value: 85 -------- ptr s &s: 0x7ffda928e478 s: 0x563781584f30 *s: 49 -------- after strncpy -------- ptr value &new_node->value: 0x5637815850b0 new_node->value: 0x563781585100 *new_node->value: 49 -------- ptr s &s: 0x7ffda928e478 s: 0x563781584f30 *s: 49 l = [1 1] ``` 結果發現: 我錯誤以為 `strncopy()` 是在複製 pointer s 指向數值的地址去 pointer value，所以根本不用 ```free(s)``` / ```s=NULL``` 去節省記憶體空間或防止更改 s 會改到 value 的值 ```! C99 7.21.2.4 The strncpy function Description The strncpy function copies not more than n characters (characters that follow a null character are not copied) from the array pointed to by s2 to the array pointed to by s1. If copying takes place between objects that overlap, the behavior is undefined. If the array pointed to by s2 is a string that is shorter than n characters, null characters are appended to the copy in the array pointed to by s1, until n characters in all have been written. ``` ```cpp NAME strcpy, strncpy - copy a string SYNOPSIS #include <string.h> char *strcpy(char *dest, const char *src); char *strncpy(char *dest, const char *src, size_t n); DESCRIPTION The strcpy() function copies the string pointed to by src, including the terminating null byte ('\0'), to the buffer pointed to by dest. The strings may not overlap, and the destination string dest must be large enough to receive the copy. Beware of buffer overruns! (See BUGS.) The strncpy() function is similar, except that at most n bytes of src are copied. Warning: If there is no null byte among the first n bytes of src, the string placed in dest will not be null-terminated. If the length of src is less than n, strncpy() writes additional null bytes to dest to ensure that a total of n bytes are written. A simple implementation of strncpy() might be: char * strncpy(char *dest, const char *src, size_t n) { size_t i; for (i = 0; i < n && src[i] != '\0'; i++) dest[i] = src[i]; for ( ; i < n; i++) dest[i] = '\0'; return dest; } ``` 從 **C99 7.21.2.4 The strncpy function** 和 man page 可以得知 `strncpy` 最後要 +1 的原因 :::warning 列出 C 語言規格書和 man page 相關描述，向第一手材料學習。 :notes: jserv ::: ### `q_remove` & `q_remove_tail` remove 只是去掉 node 跟 list 的連結，所以需要 `char *sp` 去暫存 寫的時侯在`list_del` 跟 `list_del_init` 之間在選擇，最後選了 `list_del` 因為在 if 已經有考慮到 list is empty 的問題，但還是會想會不會像 sql injection 一樣使一個 empty list 可以 by pass 這個條件式，也可能只是因為我還是沒有很懂 C 跟記憶體之間的關係，所以之後還是會去找找看`list_del_init` 的應用情景 ```cpp if (!head || list_empty(head)) return NULL; element_t *f_node = list_first_entry(head, element_t, list); list_del(&f_node->list); ``` ### q_delete_mid 因為這次是 delete 也就是說需要釋放記憶體空間，所以最後會用 `q_release_element` 原本這樣寫想要節省記憶體空間 ```cpp q_release_element(list_entry(trv_backward, element_t, list); ``` 最後改成下面，因為這樣可讀性比較高 ```cpp element_t *middle = list_entry(trv_backward, element_t, list); q_release_element(middle); ``` ### q_reverse 一開始我是用 `list_for_each_safe` 作為 loop ，然後把每個 node 移到 head ```cpp list_for_each_safe(node, tmp, head) { list_move(node, head); } ``` 然後發現第一個node的移動是多餘的 所以改成 ```cpp list_for_each_safe(node, tmp, head) { list_move_tail(node, head); } ``` 但出現以下error ``` cmd> reverse ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient ``` 看了 `list_move_tail` 的 code，發現會 `infinite loop` ```cpp static inline void list_move_tail(struct list_head *list, struct list_head *head) { __list_del_entry(list); list_add_tail(list, head); } ``` 再改成逆序，原本也預期跟上面一樣是 `infinite loop` ```cpp list_for_each_prev_safe(node, tmp, head) { list_move(node, head); } ``` 但在編譯時出現以下 error ```gcc CC queue.o queue.c: In function ‘q_reverse’: queue.c:179:5: error: implicit declaration of function ‘list_for_each_prev_safe’ did you mean ‘list_for_each_safe’? [-Werror=implicit-function-declaration] 179 | list_for_each_prev_safe(node, tmp, head); { | ^~~~~~~~~~~~~~~~~~~~~~~ | list_for_each_safe queue.c:179:45: error: expected ‘;’ before ‘{’ token 179 | list_for_each_prev_safe(node, tmp, head) { | ^~ | ; queue.c:179:5: error: ‘node’ may be used uninitialized [-Werror=maybe-uninitialized] 179 | list_for_each_prev_safe(node, tmp, head); { | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ queue.c:179:5: error: ‘tmp’ may be used uninitialized [-Werror=maybe-uninitialized] cc1: all warnings being treated as errors make: *** [Makefile:54: queue.o] Error 1 ``` ### q_sort ### q_delete_dup