# 2020q1 Homework1 (lab0)
contributed by < `markhuang3310` >

## 說明

- [作業說明](https://hackmd.io/@sysprog/linux2020-lab0#-%E4%BD%9C%E6%A5%AD%E8%A6%81%E6%B1%82)
- [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)

## 開發環境部屬

### Container
* 在安裝 snap 卡關 snapd 沒辦法用 systemd 叫起來

$ sudo systemctl status snapd.service
System has not been booted with systemd as init system (PID 1). Can't operate.

### VM
* 照著作業流程建立
* 想在 host (Windows)上編輯檔案

* 於 make 時會發生沒辦法建立 soft-link 的問題
    * 手動複製 hook 到 .git/hook 並註解掉 hook install script 中 ln -s 的部分
    * make test 時候會發生找不到檔案
        * ```Call of './qtest -v 1 -f ./traces/trace-01-ops.cmd' failed: [Errno 13] Permission denied: './qtest'```
    * 睡個 10 秒就正常了
        * ```make clean;make;sleep 10; scripts/driver.py -c```

:::warning
TODO: 探討為何 symbolic links 在你的開發環境 (需要描述) 中無法運作
:notes: jserv
:::

## 實作規格

### q_new
> Create a new, empty queue.

* 處理 malloc fail
* 增加 tail 與 size

queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (!q)
return NULL;
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
}

:::danger
下方共筆內容的縮排深度 (depth) 不利於編輯，可比照 `q_new` 這節的方式重新排版
:notes: jserv
:::


### q_free
> Free all storage used by a queue.

* 處理 q 為 NULL
* 用 free_ptr 存當前要被 free 的 element
* 用 next_ptr 存下一個要被 free 的 element
* 當 free_ptr 指向的 element 被 free 完，處理下一個(next_ptr)
* 當 free_ptr 為空則代表已經到 tail 出迴圈

void q_free(queue_t *q)
{
if (!q)
return;
list_ele_t *free_ptr = q->head;
list_ele_t *next_ptr = NULL;
while (NULL != free_ptr) {
next_ptr = free_ptr->next;
free(free_ptr->value);
free(free_ptr);
free_ptr = next_ptr;
next_ptr = NULL;
}
/* Free queue structure */
free(q);
}

### q_insert_head
> Attempt to insert a new element at the head of the queue (LIFO discipline).
* 分為四個步驟
    * 新的 element
    * 處理字串複製
    * 處理結點的 link
    * 處理 size

{
if (!q)
return false;
list_ele_t *newh;
newh = malloc(sizeof(list_ele_t));
if (!newh)
return false;

/* Process string */
size_t length = strlen(s) + 1;
newh->value = (char *) malloc(length * sizeof(char));
if (!newh->value) {
free(newh);
return false;
}
memcpy(newh->value, s, length);

/* Process link */
newh->next = q->head;
q->head = newh;
/* First insert element is both tail and head */
if (0 == q->size)
q->tail = newh;

/* Update size*/
q->size += 1;

return true;
}

### q_insert_tail
> Attempt to insert a new element at the tail of the queue (FIFO discipline).
* 邏輯同 [q_insert_head](#q_insert_head)
* 必須判斷 empty queue ，否則直接取 q->tail->next 時就會噴 NULL pointer dereference

bool q_insert_tail(queue_t *q, char *s)
{
if (!q)
return false;
list_ele_t *newt;
newt = malloc(sizeof(list_ele_t));
if (!newt)
return false;

/* Process string */
size_t length = strlen(s) + 1;
newt->value = (char *) malloc(length * sizeof(char));
if (!newt->value) {
free(newt);
return false;
}
memcpy(newt->value, s, length);

/* Process link */
newt->next = NULL;
/* Handle empty queue */
if (0 != q->size)
q->tail->next = newt;
else
q->head = newt;
q->tail = newt;

/* Update size */
q->size += 1;

return true;
}

### q_remove_head
> Attempt to remove the element at the head of the queue.
* 分為四步
    * 處理 q 為 NULL 或 empty
    * 處理字串複製到 sp, 若 sp 為 NULL 則跳過該步驟
    * 處理 link
    * 更新 size

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q)
return false;
if (0 == q->size)
return false;

if (sp) {
/* Process string */
size_t length = strlen(q->head->value) 1;
if (bufsize < length) {
memcpy(sp, q->head->value, bufsize - 1);
sp[bufsize - 1] = '\0';
} else {
memcpy(sp, q->head->value, length);
}
}
free(q->head->value);

/* Process link */
list_ele_t *free_ptr = q->head;
q->head = q->head->next;
/* Latest remove element is both tail and head */
if (1 == q->size)
q->tail = NULL;
free(free_ptr);

/* Update size */
q->size -= 1;
return true;
}

### q_size
> Compute the number of elements in the queue.

只需處理 q 為 NULL

int q_size(queue_t *q)
{
if (!q)
return 0;
return q->size;
}

### q_reverse
> Reorder the list so that the queue elements are reversed in order. This function should not allocate or free any list elements (either directly or via calls to other functions that allocate or free list elements.) Instead, it should rearrange the existing elements.

解讀:
- 仿照 [q_free](#q_free)
- tmp_ptr 存當前要反轉的 element
- pre_ptr 存前一個 element (for tmp_ptr-> next)
- 直到 tmp_ptr 為 null (也就是 pre_ptr 為反轉前的 tail)
- 更新 q->tail 和 q->head

void q_reverse(queue_t *q)
{
if (!q)
return;
if (0 == q->size)
return;
list_ele_t *tmp_ptr = q->head;
list_ele_t *pre_ptr = NULL;
while (tmp_ptr) {
q->tail = tmp_ptr->next;
tmp_ptr->next = pre_ptr;
pre_ptr = tmp_ptr;
tmp_ptr = q->tail;
}
q->tail = q->head;
q->head = pre_ptr;
return;
}

:::warning
考慮以下變更:

@@ -1,18 +1,14 @@
void q_reverse(queue_t *q)
{
- if (!q)
+ if (!q || !q->size)
return;
- if (0 == q->size)
- return;
- list_ele_t *tmp_ptr = q->head;
- list_ele_t *pre_ptr = NULL;
- while (tmp_ptr) {
- q->tail = tmp_ptr->next;
- tmp_ptr->next = pre_ptr;
- pre_ptr = tmp_ptr;
- tmp_ptr = q->tail;
+
+ list_ele_t *tmp, *prev = NULL;
+ for (tmp = q->head; tmp; tmp = q->tail) {
+ q->tail = tmp->next;
+ tmp->next = prev;
+ prev = tmp;
}
q->tail = q->head;
- q->head = pre_ptr;
- return;
+ q->head = prev;
}

要點:
1. 精簡又可辨識的變數名稱;
2. 用 `for` 迴圈改寫後，程式碼精簡且易讀;
3. 移除多餘的 `return` 敘述;
4. 合併 `if` 敘述;

:notes: jserv
:::

### q_sort
 * Sort elements of queue in ascending order
     * 根據測試時間複雜度要求預計 heap sort 符合
     * 仿照 [Program for Heap Sort in C](https://www.thecrazyprogrammer.com/2013/12/c-program-for-sorting-array-using-heap-sort.html) 實作進行修改
     * 用 heap sort 排序後再重建 queue

void create(list_ele_t *heap[], int size);
void down_adjust(list_ele_t *heap[], int i, int size);

/*
* Sort elements of queue in ascending order
* No effect if q is NULL or empty. In addition, if q has only one
* element, do nothing.
*/
void q_sort(queue_t *q)
{
if (!q)
return;
if (0 == q->size)
return;
int step_count = q->size;
list_ele_t *heap[q->size + 1];
list_ele_t *tmp_ptr = q->head;
for (int i = 1; i <= q->size; i++) {
heap[i] = tmp_ptr;
tmp_ptr = tmp_ptr->next;
}

create(heap, q->size);

// sorting
while (step_count > 1) {
// swap heap[1] and heap[last]
int last = step_count;
tmp_ptr = heap[1];
heap[1] = heap[last];
heap[last] = tmp_ptr;
step_count--;
down_adjust(heap, 1, step_count);
}

// reconnect link of q
q->head = heap[1];
tmp_ptr = q->head;
for (int i = 2; i <= q->size; i++) {
tmp_ptr->next = heap[i];
tmp_ptr = tmp_ptr->next;
}
tmp_ptr->next = NULL;
q->tail = tmp_ptr;
return;
}
void create(list_ele_t *heap[], int size)
{
for (int i = size / 2; i >= 1; i--)
down_adjust(heap, i, size);
}

void down_adjust(list_ele_t *heap[], int i, int size)
{
int flag = 1;
list_ele_t *temp;
while (2 * i <= size && flag == 1) {
int j = 2 * i; // j points to left child
if (j + 1 <= size && strcmp(heap[j + 1]->value, heap[j]->value) > 0)
j = j + 1;
if (strcmp(heap[i]->value, heap[j]->value) > 0)
flag = 0;
else {
temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
i = j;
}
}
}