HackMD
2022q1 Homework1 (lab0)
contributed by < chrisliu430 >
實驗環境
$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 39 bits physical, 48 bits virtual
CPU(s): 16
On-line CPU(s) list: 0-15
Thread(s) per core: 2
Core(s) per socket: 8
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 165
Model name: Intel(R) Core(TM) i7-10700 CPU @ 2.90GHz
Stepping: 5
CPU MHz: 2900.000
CPU max MHz: 4800.0000
CPU min MHz: 800.0000
BogoMIPS: 5799.77
Virtualization: VT-x
L1d cache: 256 KiB
L1i cache: 256 KiB
L2 cache: 2 MiB
L3 cache: 16 MiB
NUMA node0 CPU(s): 0-15
針對佇列的操作
q_new
4846696
struct list_head *q_new()
{
struct list_head *q = malloc(sizeof(struct list_head));
if (!q) {
return NULL;
}
q->prev = q->next = q;
return q;
}
先使用 malloc 對 list_head 做記憶體分配的動作，接下來檢測是否有分配，若沒有分配就回傳 NULL ；若有分配則對 struct list_head 做初始化，將 prev 及 next 指回自身位址。
參考 laneser 得知
list.h中有提供INIT_LIST_HEAD可以使用
- 改進程式碼
b3d85fe
struct list_head *q_new()
{
struct list_head *q = malloc(sizeof(struct list_head));
if (!q) {
return NULL;
}
INIT_LIST_HEAD(q);
return q;
}
q_free
q_size
4846696
int q_size(struct list_head *head)
{
if (!head) {
return 0;
}
int cnt = 0;
struct list_head *n;
for (n = head->next; n != head; n = n->next) {
cnt++;
}
return cnt;
}
先判斷 head 是否為不存在，若不存在則 Queue Size 為0；存在時在利用 list_head
環形結構計算 Queue 中內存有多少元素，結束條件為節點被指派的位址與 list_head 的開頭相同。
宣告
struct list_head的指標時，並沒有給予初始值，於是往內移至for loop內
- 改進程式碼
b3d85fe
int q_size(struct list_head *head)
{
if (!head) {
return 0;
}
int cnt = 0;
for (struct list_head *n = head->next; n != head; n = n->next) {
cnt++;
}
return cnt;
}
q_insert_head
4846696
bool q_insert_head(struct list_head *head, char *s)
{
element_t *ele = malloc(sizeof(element_t));
if (!head || !ele) {
free(ele);
return false;
}
ele->value = strdup(s);
list_add(&ele->list, head);
return true;
}
先分配記憶體空間給 element_t 作為要被儲存的元素的節點，接下來才判斷串接資料的節點 head 是否不存在或分配 element_t 空間時是否有分配，若沒有就將剛剛分配給予 element_t 的空間給釋；若 head 存在及 element_t 有分配到記憶體的情況下，則將使用 strdup 對要儲存的字串分配記憶體空間，並採用在 list.h 中現有的 list_add 對新增節點加入在開頭的部份。
參考 laneser 的開發筆記，對於
insert的處理是先判斷head是否存在。
我的寫法是先創建element_t再判斷可否正常插入node，這個寫法雖然可以正常用作，但根據所查詢的資料 Is it good practice to free a NULL pointer in C? 中提到不要對NULL指標坐存取，原因是因為會多存取不必要的程式碼，即使free函式傳入NULL不會發生任何問題。
- 改進程式碼
b3d85fe
bool q_insert_head(struct list_head *head, char *s)
{
if (!head) {
return false;
}
element_t *ele = malloc(sizeof(element_t));
if (!ele) {
return false;
}
ele->value = strdup(s);
list_add(&ele->list, head);
return true;
}
q_insert_tail
4846696
bool q_insert_tail(struct list_head *head, char *s)
{
element_t *ele = malloc(sizeof(element_t));
if (!head || !ele) {
free(ele);
return false;
}
ele->value = strdup(s);
list_add_tail(&ele->list, head);
return true;
}
先分配記憶體空間給 element_t 作為要被儲存的元素的節點，接下來才判斷串接資料的節點 head 是否不存在或分配 element_t 空間時是否有分配，若沒有就將剛剛分配給予 element_t 的空間給釋；若 head 存在及 element_t 有分配到記憶體的情況下，則將使用 strdup 對要儲存的字串分配記憶體空間，並採用在 list.h 中現有的 list_add_tail 對新增節點加入在結尾的部份。
- 改進程式碼
b3d85fe
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head) {
return false;
}
element_t *ele = malloc(sizeof(element_t));
if (!ele) {
return false;
}
ele->value = strdup(s);
list_add_tail(&ele->list, head);
return true;
}
