# 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

## 開發過程

:::danger
說好的進度呢？
:notes: 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;
}

:::warning
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

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