---
# System prepended metadata

title: 2023q1 Homework1 (lab0)

---

# 2023q1 Homework1 (lab0)
contributed by < `yeiogy123` >

## 開發環境
```shell
$ 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):                          4
On-line CPU(s) list:             0-3
Thread(s) per core:              1
Core(s) per socket:              4
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           165
Model name:                      Intel(R) Core(TM) i7-10870H CPU @ 2.20GHz
Stepping:                        2
CPU MHz:                         2208.000
BogoMIPS:                        4416.00
Hypervisor vendor:               KVM
Virtualization type:             full
L1d cache:                       128 KiB
L1i cache:                       128 KiB
L2 cache:                        1 MiB
L3 cache:                        64 MiB

$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0
```

## 開發紀錄
### q_new()
使用 list.h 中 list_head 的指標來儲存記憶體配置空間所回傳的位址，
並且確認是否配置成功與否，成功則回傳所指向的位址，而失敗則回傳 NULL。
```c
//allocate a new queue, return new queue if success, otw, return NULL.
struct list_head *q_new(){
    struct list_head *queue = malloc(sizeof(sturct list_head));
    if(!queue) return NULL;
    INIT_LIST_HEAD(queue);
    return queue;
}
```

### q_free()
當預期釋放的位置位於 head 時，只能使用 `list_for_each_entry_safe` 來進行釋放。
而我們又不能保證刪除的位置不位於 head ，因此我們使用`list_for_each_entry_safe` 。
而為了符合 API  `list_for_each_entry_safe` 又需要兩個額外的 elemnet_t 的資料結構參數。
```c
//free all of the element in the queue
void q_free(struct list_head *l){
    if(!l) return;
    element_t *entry, *safe;
    list_for_each_entry_safe(entry, safe, l, list)
        q_release_element(entry);
    free(l);
}
```

### q_insert_head()
這邊特別需要判斷如果加入進 queue 中的 character 為空白字元，需要額外判斷不加入 queue 中 ，並且使用 `list_add` 加入進 queue 中
```c
bool q_insert_head(struct list_head *head, char *s){
    if (!head)    return false;
    element_t *temp = malloc(sizeof(element_t));
    if (!temp)    return temp;
    temp->value = strdup(s);
    if(!temp->value){
        free(temp);
        return false;
    }
    list_add(&temp->list, head);
    return true;
}
```

### q_insert_tail()

這邊特別需要判斷如果加入進 queue 中的 character 為空白字元，需要額外判斷不加入 queue 中 ，並且使用 `list_add_tail` 加入進 queue 中
```c
bool q_insert_tail(struct list_head *head, char *s){
    if (!head)    return false;
    element_t *temp = malloc(sizeof(element_t));
    if (!temp)    return false;
    temp->value = strdup(s);
    if (!temp->value) {
        free(tmp);
        return false;
    }
    list_add_tail(&temp->list, head);
    return true;
}
```

### q_remove_head()
因為在 Linux 中的 linked list 為 `doubled circular linked list` ，
因此我們可以使用他的特性，保留頭的結構體中所含指向下一位結構體的指標，
並且刪除頭的結構體。

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

### q_remove_tail()
因為在 Linux 中的 linked list 為 `doubled circular linked list` ，
因此我們可以使用他的特性，刪除頭的結構體中所含指向前一位結構體的指標，
也就是尾端，並且刪除頭的結構體。
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize){
    if (!head || list_empty(head))      return NULL;
    element_t *temp = list_entry(head->prev, element_t, list);
    list_del(head->prev);
    if (sp) {
        strncpy(sp, temp->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return temp;
}
```

### q_size()
首先判別其是否為 NULL queue ，再來計算歷經幾次回圈，則為 queue 的長度。
```c
int q_size(struct list_head *head){
    if (!head)  return 0;
    int length = 0;
    struct list_head *li;
    list_for_each (li, head)
        length++;
    return length;
}
```

### q_delete_mid()
首先先判斷是否為空，接下來我們利用 double circular linked list 的特性，
判斷從頭端開始往後算，同時間從尾端往前算，而恰好會再同一個位置中停下。
該位置則為中點。
```c
bool q_delete_mid(struct list_head *head){
    if (!head)    return false;
    struct list_head *behind = head->next, *back = head->prev;
    while (behind != back && behind->next != back) {
        behind = behind->next;
        back = back->prev;
    }
    list_del(behind);
    q_release_element(list_entry(behind, element_t, list));
    return true;
}
```

### q_delete_dup()
刪除重複的節點，歷經串列的遞迴中，將逐步判斷一點 A 與其後一點是否相同，若相同則將其刪除，並且串接上原本後面的點後，再逐步判斷後面其他點是否與 A 相同後，再重先串接 previous pointer 與 next pointer 。

```c
bool q_delete_dup(struct list_head *head){
    if (!head)  return false;
    element_t *entry, *next, *temp;
    list_for_each_entry_safe (entry, next, head, list) {
        if(&next->list != head && !strcmp(entry->value, next->value)){
            while (&next->list != head && !strcmp(entry->value, next->value)){
                    temp = next;
                    next = list_entry(next->list.next, element_t, list);
                    q_release_element(temp);
            }
            entry->list.prev->next = &next->list;
            next->list.prev = entry->list.prev;
            q_release_element(entry);
        }
    }
    return true;
}
```

### q_swap()
先判斷是否存在 queue ，再進行交換。
交換的方法為將 previous 的節點加入原點的 next 點。
```c
void q_swap(struct list_head *head){
    if (!head)  return;
    struct list_head *first = head->next;
    for (struct list_head *next = first->next;
                    first != head && next != head;
                    first = first->next, next = first->next) {
        list_del(first);
        list_add(first, next);
        }
}
```

### q_reverse()
先判斷是否存在，而後則將中心點 position 的位置之前後 pointer 指向的位址互相交換。
```c
void q_reverse(struct list_head *head) {
    if (head == NULL)   return;
    struct list_head *position, *n, *temp;
    list_for_each_safe (position, n, head) {
        temp = position->next;
        position->next = position->prev;
        position->prev = temp;
    }
    temp = head->next;
    head->next = head->prev;
    head->prev = temp;
}
```

### q_reverseK()
reverseK 為以 K 個單位進行 reverse 的功能，
首先先判斷是否存在，
再來使用 `list_for_each_safe` 來歷經串列，其中計算是否歷經了 K 個單位。
若達成則切掉串列且倒轉串列後再串接原本的串列。
```c
void q_reverseK(struct list_head *head, int k){
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if (!head） return;
    struct list_head *entry, *safe, start, *target;
    INIT_LIST_HEAD(&start);
    target = head;
    int count = 0;
    list_for_each_safe(entry, safe, head){
        count++;
        if(clount == k){
            list_cut_position(&start, target, entry);
            q_reverse(&start);
            list_splice_init(&start, target);
            target = safe->prev;
            count = 0;
        }
    }
}
```

### q_sort()
這裡我參考了 `@itscaleb` 的實作方式。
merge 將兩兩 list 合併，
其中 while 迴圈將會判斷兩 list 是否為空， 若不為空則比較大小，
將小的放入 result list 的尾端，再依序比較。
直到結束後，再比較是否還有剩餘的 list ，將其加入 result list 。
```c
void merge(struct list_head *left,
                struct list_head *right,
                struct list_head *result){
    while (!list_empty(left) && !list_empty(right)) {
        element_t *list1 = list_entry(left->next, element_t, list);
        element_t *list2 = list_entry(right->next, element_t, list);
        if (strcmp(list1->value, list2->value) <= 0)
            list_move_tail(&list1->list, result);
        else
            list_move_tail(&list2->list, result);
    }
    if (!list_empty(left))
        list_splice_tail(left, result);
    else
        list_splice_tail(right, result);
}
```

q_sort 使用了兩指標，一指標較快，一次移動兩步，另一指標較慢，一次移動一步。
並藉由此步驟找到了中間點 `slow`。
而此法可以分成左右兩 list ，
`list_cut_position` 則將 `slow` 放入 left list 中。

```c
void q_sort(struct list_head *head){
    if (list_empty(head) || list_is_singular(head))    return;
    struct list_head *slow = head, *fast = head;
    do {
        fast = fast->next->next;
        slow = slow->next;
    } while (fast != head && fast->next != head);
    LIST_HEAD(left);
    LIST_HEAD(right);
    list_splice_tail_init(head, &right);
    list_cut_position(&left, &right, slow);
    q_sort(&left);
    q_sort(&right);
    merge(&left, &right, head);               
```

### q_descend()
每個 list 中若有節點會被刪除，則是因為該節點比後節點小。
我們使用由 list 最後端往前遞迴所找尋到的最大值作為基準進行比較，
較大則更新最大值，較小則刪除該點。
```c
int q_descend(struct list_head *head){
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    if (!head || list_empty(head))      return 0;
    element_t *entry = list_entry(head->prev, element_t, list),
              *ori = list_entry(entry->list.prev, element_t, list);
    char *largest = entry->value;
    while (&entry->list != head) {
        if (strcmp(entry->value, largest) < 0) {
            list_del(&entry->list);
            q_release_element(entry);
        } else { 
            largest = entry->value;
        }

        entry = ori;
        ori = list_entry(entry->list.prev, element_t, list);
    }
    return q_size(head);
}   
```

### q_merge()
合併後再進行 q_sort 。
```c
int q_merge(struct list_head *head){
    if (!head || list_empty(head))      return 0;
    queue_contex_t *first = list_first_entry(head, queue_contex_t, chain), *otw = NULL;
    int len = first->size;
    list_for_each_entry (otw, head, chain) {
        if (otw == first)
            continue;
        len += otw->size;
        list_splice_tail_init(otw->q, first->q);
    }
    q_sort(first->q);
    return len;
}
```

---

### 請提出改善目前無法使用 web 命令的 linenoise 套件
### 實作shuffle指令
根據 Fisher–Yates shuffle 演算法實作如下:
```c
void swap_value(element_t *a, element_t *b)
{
    char *tmp = a->value;
    a->value = b->value;
    b->value = tmp;
}
```
```c
/* Get the nth node from list */
struct list_head *list_idx(struct list_head *head, int idx)
{
    while (idx-- >= 0) {
        head = head->next;
    }
    return head;
}
```
```c
static void q_shuffle(struct list_head *head)
{
    int len = q_size(head);
    if (len <= 1) {
        return;
    }

    srand(time(NULL));
    struct list_head *tail = head->prev;
    for (int i = len; i > 1; i--) {
        int rand_idx = rand() % i;
        swap_value(list_entry(list_idx(head, rand_idx), element_t, list),
                   list_entry(tail, element_t, list));
        tail = tail->prev;
    }
}
```

配合 ADD_COMMAND 的巨集來新增函式 do_shuffle
```c
static bool do_shuffle(int argc, char *argv[])
{
    if (argc != 1) {
        report(1, "%s takes no arguments", argv[0]);
        return false;
    }

    if (!current || !current->q)
        report(3, "Warning: Try to access null queue");
    error_check();

    set_noallocate_mode(true);
    if (exception_setup(true)){
        
        q_shuffle(current->q);
        
        }
    exception_cancel();

    set_noallocate_mode(false);

    q_show(3);
    return !error_check();
}
```
並且於 console_init() 中新增
```c 
ADD_COMMAND(
        shuffle,
        " | Shuffle the queue using Fisher–Yates shuffle",
        "");
```
即可完成命令
```shell
./qtest 
cmd> new
l = []
cmd> ih RAND 5
l = [rxbfygpvb dkkpo paimlqfnt tdtnzmth ypcceqku]
cmd> shuffle
l = [rxbfygpvb ypcceqku tdtnzmth dkkpo paimlqfnt]
cmd> quit
Freeing queue
```

## 參考資訊
- 共筆格式參考：[共筆示範](https://hackmd.io/@jim12312321/linux2022-lab0)
- 踩坑/解惑參考：
    - [lab0-c](https://hackmd.io/@sysprog/linux2023-lab0)
    - [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)
   - [C99 standard p.257](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf)
