---
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
Sign in with Wallet
Connect another wallet