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;
}

q_remove_head

q_remove_tail

q_delete_mid

q_delete_dup

q_swap

q_reverse

q_sort