2022q1 Homework1 (lab0)

contributed by <curlyw819 >

tags: linux2022

實驗環境

$ gcc --version
gcc (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0

$ lscpu
Architecture:        x86_64
CPU op-mode(s):      32-bit, 64-bit
Byte Order:          Little Endian
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:               158
Model name:          Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz
Stepping:            9
CPU MHz:             2635.475
CPU max MHz:         3800.0000
CPU min MHz:         800.0000
BogoMIPS:            5599.85
Virtualization:      VT-x
L1d cache:           32K
L1i cache:           32K
L2 cache:            256K
L3 cache:            6144K
NUMA node0 CPU(s):   0-7

作業要求

lab0

詳細閱讀 C Programming Lab ，依據指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改，記得也該實作 q_sort 函式。

• q_new: 創一個空的 queue
• q_free: 釋放掉一個 queue
• q_insert_head: 在 head 插入一個 element (LIFO)
• q_insert_tail: 在 tail 插入一個 element (FIFO), O(1)
• q_remove_head: 把 head 的 element 移除
• q_size: return queue 的大小
• q_reverse: 將 queue 反轉，不配置或釋放任何的 element
• q_sort: 將 queue 由小排到大, sort by nature sort

開發過程

q_new

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

配置一塊記憶體空間給head，再使用container of的INIT_LIST_HEAD

q_free

void q_free(struct list_head *l)
{
    if (!l)
        return;
    struct list_head *current = l->next;
    while (current != l) {
        struct list_head *temp_pointer = current;
        element_t *temp_node = list_entry(temp_pointer, element_t, list);
        current = current->next;
        list_del(temp_pointer);
        free(temp_node->value);
        free(temp_node);
    }
    free(l);
}

使用 list_entry 來得到 list 的內部節點，其中 list_entry 等價 container of

q_insert_head

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    size_t slen = strlen(s) + 1;
    element_t *new_node;
    if (!(new_node = (element_t *) malloc(sizeof(element_t))))
        return false;


    if (!(new_node->value = (char *) malloc(sizeof(char) * slen))) {
        free(new_node);
        return false;
    }

    memcpy(new_node->value, s, slen);
    list_add(&new_node->list, head);

    return true;
}

若配置記憶體不成功則 return false ，若成功則使用 list head 將結點插入至 head 後

q_insert_tail

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;
    size_t slen = strlen(s) + 1;
    element_t *new_node;
    if (!(new_node = (element_t *) malloc(sizeof(element_t))))
        return false;


    if (!(new_node->value = (char *) malloc(sizeof(char) * slen))) {
        free(new_node);
        return false;
    }

    memcpy(new_node->value, s, slen);
    list_add_tail(&new_node->list, head);

    return true;
}

q_remove_head

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || head->next == head || head->prev == head)
        return NULL;
    element_t *temp_node = list_first_entry(head, element_t, list);
    if (sp)
        memcpy(sp, temp_node->value, bufsize);
    list_del(head->next);
    return temp_node;
}

q_remove_tail

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || head->next == head || head->prev == head)
        return NULL;
    element_t *temp_node = list_last_entry(head, element_t, list);
    if (sp)
        memcpy(sp, temp_node->value, bufsize);
    list_del(head->prev);
    return temp_node;
}

q_size

int q_size(struct list_head *head)
{
    if (!head)
        return 0;

    int len = 0;
    struct list_head *li;
    list_for_each (li, head)
        len++;
    return len;
}

q_delete_mid

bool q_delete_mid(struct list_head *head)
{
    if (!head || head->next == head)
        return false;

    struct list_head *slow_pointer = head;
    struct list_head *fast_pointer = head;
    do {
        fast_pointer = fast_pointer->next->next;
        slow_pointer = slow_pointer->next;
    } while (fast_pointer != head && fast_pointer->next != head);
    element_t *temp = list_entry(slow_pointer, element_t, list);
    list_del(slow_pointer);
    free(temp->value);
    free(temp);
    return true;
}

q_delete_dup

原本的寫法只有前半段，但因為功能不正確導致後面幾個數字輸出錯誤，所以將程式複製一遍從後面再跑回來來使結果正確

bool q_delete_dup(struct list_head *head)
{
    if (!head)
        return false;
    int count = 0;
    struct list_head *current_pointer = head->next;
    struct list_head *ref_pointer = current_pointer;
    struct list_head *temp_pointer;
    struct list_head *temp_temp_pointer;
    element_t *current_node = list_entry(current_pointer, element_t, list);
    element_t *temp;
    element_t *temp_node;
    char *sp, *ref;
    ref = current_node->value;

    while (current_pointer != head) {
        current_node = list_entry(current_pointer, element_t, list);
        sp = current_node->value;
        if (count == 0) {
            ref = current_node->value;
            ref_pointer = current_pointer;
            if (current_pointer->prev != head) {
                temp = list_entry(current_pointer->prev, element_t, list);
                if (strcmp(temp->value, ref) == 0) {
                    printf("HI\n");
                    current_pointer = current_pointer->prev;
                    ref_pointer = current_pointer;
                }
            }
        }

        if (strcmp(sp, ref) == 0 && current_pointer->next != head) {
            count++;

        } else {
            if (count > 1) {
                temp_pointer = ref_pointer;
                for (int i = 0; i < count; i++) {
                    temp_temp_pointer = temp_pointer;
                    temp_pointer = temp_pointer->next;
                    temp_node = list_entry(temp_temp_pointer, element_t, list);
                    list_del(temp_temp_pointer);
                    free(temp_node->value);
                    free(temp_node);
                }
                count = 0;
                current_pointer = temp_pointer;
            } else {
                count = 0;
            }
        }
        current_pointer = current_pointer->next;
    }

    count = 0;
    current_pointer = head->prev;
    ref_pointer = current_pointer;
    current_node = list_entry(current_pointer, element_t, list);
    ref = current_node->value;
    while (current_pointer != head) {
        current_node = list_entry(current_pointer, element_t, list);
        sp = current_node->value;
        if (count == 0) {
            ref = current_node->value;
            ref_pointer = current_pointer;
            if (current_pointer->next != head) {
                temp = list_entry(current_pointer->next, element_t, list);
                if (strcmp(temp->value, ref) == 0) {
                    printf("HI\n");
                    current_pointer = current_pointer->next;
                    ref_pointer = current_pointer;
                }
            }
        }

        if (strcmp(sp, ref) == 0 && current_pointer->prev != head) {
            count++;

        } else {
            if (count > 1) {
                temp_pointer = ref_pointer;
                for (int i = 0; i < count; i++) {
                    temp_temp_pointer = temp_pointer;
                    temp_pointer = temp_pointer->prev;
                    temp_node = list_entry(temp_temp_pointer, element_t, list);
                    list_del(temp_temp_pointer);
                    free(temp_node->value);
                    free(temp_node);
                }
                count = 0;
                current_pointer = temp_pointer;
            } else {
                count = 0;
            }
        }
        current_pointer = current_pointer->prev;
    }
    return true;
}

q_swap

void q_swap(struct list_head *head)
{
    struct list_head *current = head;
    int count = 0;
    while (current->next != head && current->next->next != head) {
        count++;
        struct list_head *first = current->next;
        struct list_head *second = current->next->next;
        first->next = second->next;
        current->next = second;
        second->next = first;

        first->next->prev = first;
        first->prev = second;
        second->prev = current;
        current = current->next->next;
    }
    printf("%d", count);
}

q_reverse

void q_reverse(struct list_head *head)
{
    if (head == NULL || head->next == head)
        return;
    struct list_head *temp;
    struct list_head *current = head->next;
    while (current != head) {
        temp = current->next;
        current->next = current->prev;
        current->prev = temp;
        current = temp;
    }
    temp = head->next;
    head->next = head->prev;
    head->prev = temp;
}

q_sort

參考程式碼 : Chao-Shun-Cheng 同學之 q_sort 程式碼

mergetwolist

void mergetwolist(struct list_head *head1,
                  struct list_head *head2,
                  struct list_head *head)
{
    if (!head || !head1 || !head2 || (list_empty(head1) && list_empty(head2)))
        return;
    if (list_empty(head1)) {
        list_splice_tail_init(head2, head);
        return;
    }
    if (list_empty(head2)) {
        list_splice_tail_init(head1, head);
        return;
    }
    struct list_head *temp = NULL;
    struct list_head *p_1 = head1->next;
    struct list_head *p_2 = head2->next;
    while (p_1 != head1 && p_2 != head2) {
        if (strcmp(list_entry(p_1, element_t, list)->value,
                   list_entry(p_2, element_t, list)->value) > 0) {
            temp = p_2;
            p_2 = p_2->next;
            list_move_tail(temp, head);
        } else {
            temp = p_1;
            p_1 = p_1->next;
            list_move_tail(temp, head);
        }
    }
    list_splice_tail_init(head1, head);
    list_splice_tail_init(head2, head);
}

mergesort

void mergesort(struct list_head *head, int size)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    LIST_HEAD(head1);
    LIST_HEAD(head2);
    int mid = size / 2, count = 0;
    struct list_head *node = NULL, *safe = NULL;
    list_for_each_safe (node, safe, head) {
        count++;
        if (count == mid) {
            list_cut_position(&head1, head, node);
            list_splice_tail_init(head, &head2);
            break;
        }
    }
    mergesort(&head1, mid);
    mergesort(&head2, size - mid);
    mergetwolist(&head1, &head2, head);
}

qsort

void q_sort(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    mergesort(head, q_size(head));
}