2023q1 Homework1 (lab0)

contributed by < joshyue >

實驗環境

$ 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
Byte Order:                      Little Endian
Address sizes:                   39 bits physical, 48 bits virtual
CPU(s):                          8
On-line CPU(s) list:             0-7
Thread(s) per core:              2
Core(s) per socket:              4
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           60
Model name:                      Intel(R) Xeon(R) CPU E3-1231 v3 @ 3.40GHz
Stepping:                        3
CPU MHz:                         1200.000
CPU max MHz:                     3800.0000
CPU min MHz:                     800.0000
BogoMIPS:                        6800.57
Virtualization:                  VT-x
L1d cache:                       128 KiB
L1i cache:                       128 KiB
L2 cache:                        1 MiB
L3 cache:                        8 MiB
NUMA node0 CPU(s):               0-7

開發過程

q_new

struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(struct list_head));
    if (!head)
        return NULL;     
    INIT_LIST_HEAD(head);
    return head;
}

參照list.h中的 INIT_LIST_HEAD , 將next和prev皆指向head本身。

q_free

void q_free(struct list_head *l) 
{
    if (!l)
        return;
    element_t *pos, *temp;
    list_for_each_entry_safe (pos, temp, l, list)
        q_release_element(pos);
    free(l);
}

參照list.h中的 list_for_each_entry_safe走訪queue中每個元素，利用temp保存下個節點的位置後，透過queue.h的q_release_element將當前節點之value刪除並釋放，最後才將head釋放。

q_insert_head

bool q_insert_head(struct list_head *head, char *s)
{
    if(!head)
    	return false;
    	
    element_t *node_insert = malloc(sizeof(element_t));
    
    if (!node_insert)
        return false;
    
    node_insert->value = strdup(s);
    if (!node_insert->value) {
        free(node_insert);
        return false;
    }
    list_add(&node_insert->list, head);
    return true;
}

宣告node_insert物件並配置記憶體，配置失敗回傳false，若成功則利用strdup根據字串長度配置相對應之記憶體空間後，才將字串複製到物件內的value，同前述若配置失敗則釋放node_insert，回傳false，成功則參照list.h中的list_add，將node_insert插入至queue最前方。

q_insert_tail

bool q_insert_tail(struct list_head *head, char *s)
{
    if(!head)
        return false;
    	
    element_t *node_insert = malloc(sizeof(element_t));
    
    if (!node_insert)
        return false;
    
    node_insert->value = strdup(s);
    if (!node_insert->value) {
        free(node_insert);
        return false;
    }
    list_add_tail(&node_insert->list, head);
    return true;
}

同q_insert_head的概念，差別在於list_add是將node_insert插入到queue最前方，此處改用list_add_tail，將node_insert插入到queue尾端。

q_remove_head

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *removed_element = list_entry(head->next, element_t, list);
    list_del(head->next);

    if (sp) {
        strncpy(sp, removed_element->value, bufsize-1);
        sp[bufsize - 1] = '\0';
    }

    return removed_element;
}

首先先判斷head若為NULL或empty的話，則回傳NULL，再來參照list.h中的list_entry，取得第一個節點之位址,並透過list_del刪除第一個節點的連結，並保持斷開位置之前後節點仍相連，再來若sp不為NULL，則將刪除節點之value複製給sp，因strncpy不會回傳字串結束符'\0'，因此最後要在sp的最後補上'\0'。

q_remove_tail

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    }

    element_t *removed_element = list_entry(head->prev, element_t, list);
    list_del(head->prev);

    if (sp) {
        strncpy(sp, removed_element->value, bufsize-1);
        sp[bufsize - 1] = '\0';
    }

    return removed_element;
}

同q_remove_head的概念，差別在於將head->next改為head->prev。

q_size

int q_size(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;
        
    int len = 0;
    struct list_head *li;
    
    list_for_each (li, head)
        len++;
    return len;
}

若head為NULL或empty，則回傳0；反之則參照list.h中的list_for_each來遍歷queue的每個節點，並在跳到下個節點時，長度+1，如此走訪完便能得到queue的size。

q_delete_mid

q_delete_dup

q_swap

q_reverse

q_reverseK

q_sort

q_descend

q_merge

q_shuffle