# 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)
Sign in with Wallet
Connect another wallet