2023q1 Homework1 (lab0)

ontributed by < OWaitsInTime >

開發環境

$ 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):                  8
  On-line CPU(s) list:   0-7
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i7-7700 CPU @ 3.60GHz
    CPU family:          6
    Model:               158
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            9
    CPU max MHz:         4200.0000
    CPU min MHz:         800.0000
    BogoMIPS:            7200.00

開發過程

說好的進度呢？

jserv

q_new

/* Create an empty queue */
struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(struct list_head));
    if (!head)
        return NULL;
    INIT_LIST_HEAD(head);
    return head;
}

q_free

最開始的想法是用指標記錄上一個節點
queue.h 中 q_release_element 可以用來釋放指標的記憶體

/* Free all storage used by queue */
void q_free(struct list_head *l) {
    if (!l)
        return;

    struct list_head *led = l->prev;
    struct list_head *folo = led->prev;
    while (tmp != l){
        tmp = tmp->prev;
        q_release_element(l->prev);
        l->prev = tmp;
    }
    free(tmp);
}

q_release_element 只能釋放 element_t 結構，重看架構圖
head的部分是 list_head 沒有儲存value，而其他部分是 element_t

因為 q_release_element 會失去 next 的資料，所以額外使用一個指標在 release 後連結資料

void q_free(struct list_head *l)
{
    if (!l)
        return;

    struct list_head *fnode = l->next;
    struct list_head *lnode = l->next->next;
    while (lnode != l) {
        lnode = lnode->next;
        q_release_element(list_entry(fnode, element_t, list));
        fnode = lnode->prev;
    }

    q_release_element(list_entry(fnode, element_t, list));
    free(l);
}

q_insert_head

要求 Return: true for success, false for allocation failed or queue is NULL

首先判斷要插入的 insert 以及要被插入的 head 是否存在，而 list_add 可以把節點插入到 list 的開頭

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *insert = malloc(sizeof(element_t));
    if (!insert)
        return false;
    
    insert->value = strdup(s);
    list_add(&new->list, head);
    return true;
}

ERROR: Failed to save copy of string in queue

沒有考慮到 insert->value == NULL 的狀況

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *insert = malloc(sizeof(element_t));
    if (!insert)
        return false;
    
    insert->value = strdup(s);
    if (!insert->value){
        free(insert);
        return false;
    }
    list_add(&new->list, head);
    return true;
}

q_insert_tail

把 q_insert_head 中的 list_add 改成 list_add_tail

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *insert = malloc(sizeof(element_t));
    if (!insert)
        return false;

    insert->value = strdup(s);
    if (!insert->value) {
        free(insert);
        return false;
    }
    list_add_tail(&insert->list, head);
    return true;
}

q_remove_head

要求 Return: the pointer to element, %NULL if queue is NULL or empty.

C 字串需要尾端的 '\0' 字元來判斷字串結束

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *node = list_entry(head->next, element_t, list);
    if (sp) {
        strncpy(sp, node->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    list_del(&node->list);
    return node;
}

q_remove_tail

把 q_remove_head 中 head->next 改成 head_prev

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *node = list_entry(head->prev, element_t, list);
    strncpy(sp, node->value, bufsize - 1);
    sp[bufsize - 1] = '\0';
    list_del(&node->list);
    return node;

}

q_size

要求 Return: the number of elements in queue, zero if queue is NULL or empty

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

q_delete_mid

使用 q_size 得到 queue 的節點數並利用 (x/2)+1 找到中間節點是第幾個

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;
    int mid = (q_size(head) / 2) + 1;
    struct list_head *current = head;
    while (mid != 0) {
        current = current->next;
        mid--;
    }

    q_release_element(list_entry(current, element_t, list));
    return true;
}

q_delete_dup

q_swap

list.h 中 list_swap 可以交換兩個節點，當 leader 指標指向 head 或 head->next 時就不做交換

void q_swap(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    struct list_head *l = head->next->next;
    struct list_head *f = head->next;
    while (l != head && l != head->next) {
        list_swap(l, f);
        l = f->next->next;
        f = f->next;
    }
}

// 發生錯誤
ueue.c:154:9: error: implicit declaration of function ‘list_swap’ [-Werror=implicit-function-declaration]
  154 |         list_swap(n, t->next);
      |         ^~~~~~~~~
cc1: all warnings being treated as errors
make: *** [Makefile:54：queue.o] 錯誤 1

把 list_swap 用 list_move 替代

void q_swap(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    struct list_head *l = head->next->next;
    struct list_head *f = head->next;
    while (l != head && l != head->next) {
        list_move(l, f);
        l = f->next->next;
        f = f->next;
    }
}

q_reverse

q_reverseK

q_sort

q_descend

q_merge

q_shuffle