---
title: 2020q1 Homework1 (lab0)
tags: Linux
---

# 2020q1 Homework1 (lab0)
contributed by < `LJP-TW` >

- [Linux 核心設計課程 —— 第 1 次作業](https://hackmd.io/K0Ym8IkjR3iWaL6m8-DNZw)

# 實作
## queue_t

/* Queue structure */
typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t **tail;
    unsigned int size;
} queue_t;

- 為了使得 `q_insert_tail` 和 `q_size` 時間複雜度為 $O(1)$，於是增加了 tail 和 size 兩個欄位

## q_new

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

- `malloc` 執行失敗會回傳 NULL [1]

## q_free

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

- 將整個 linked list 釋放掉

## q_insert_head

bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    char *news;
    unsigned long len, tmp;
    if (q == NULL)
        goto ERROR;
    newh = malloc(sizeof(list_ele_t));
    if (newh == NULL)
        goto ERROR;
    len = 0;
    while (*(s + len))
        ++len;
    /* Plus 1 for NULL byte */
    news = malloc(sizeof(char) * (len + 1));
    if (news == NULL) {
        free(newh);
        goto ERROR;
    }
    /* Copy string, including the NULL byte */
    for (tmp = 0; tmp <= len; ++tmp) {
        news[tmp] = s[tmp];
    }
    newh->value = news;
    newh->next = q->head;
    q->head = newh;
    if (q->tail == NULL) {
        q->tail = &(newh->next);
    }           
    ++q->size;
    return true;
ERROR:
    return false;
}

- 在計算字串多長以及複製字串這兩方面，使用簡單的迴圈即可處理，不 call lib function
- 預想上是會比 call lib function 還要快，需再做實驗
- 將遇到錯誤的部分 goto 到一個區域
- 若日後要統一改變遇到錯誤後的行為，能直接在此區域變更，較為方便

## q_insert_tail

bool q_insert_tail(queue_t *q, char *s)
{
    list_ele_t *newh;
    char *news;
    unsigned long len, tmp;
    if (q == NULL)
        goto _ERROR;
    newh = malloc(sizeof(list_ele_t));
    if (newh == NULL)
        goto _ERROR;
    len = 0;
    while (*(s + len))
        ++len;
    news = malloc(sizeof(char) * (len + 1));
    if (news == NULL) {
        free(newh);
        goto _ERROR;
    }
    for (tmp = 0; tmp <= len; ++tmp) {
        news[tmp] = s[tmp];
    }
    newh->value = news;
    newh->next = NULL;
    if (q->head == NULL) {
        q->head = newh;
    } else {
        *(q->tail) = newh;
    }
    q->tail = &(newh->next);
    ++q->size;
    return true;
_ERROR:
    return false;
}

- 與 `q_insert_head` 只差在 linked list 鏈結的部分
- 反思 `q->tail` 的型態訂成什麼比較好
- 若為 `list_ele_t *`
則尾段的 code 要改成

        if (q->head == NULL) {
            q->head = newh;
        } else {
            q->tail->next = newh;
        }
        q->tail = newh;

似乎也沒有什麼不好
- 總之，有了 `q->tail` 後，此 function 就能在時間複雜度 $O(1)$ 以內處理完了

## q_remove_head

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    list_ele_t *tmp;
    if (q == NULL || q->head == NULL)
        return false;
    if (sp != NULL) {
        char *v;
        unsigned long i;
        v = q->head->value;
        for (i = 0; i < bufsize - 1; ++i) {
            sp[i] = v[i];
        }
        sp[i] = '\0';
    }
    free(q->head->value);
    if (q->size == 1) {
        /* There is only one element in list */
        free(q->head);
        q->head = NULL;
        q->tail = NULL;
    } else {
        tmp = q->head->next;
        free(q->head);
        q->head = tmp;
    }
    --q->size;
    return true;
}

- 若 `sp` 有值，表示使用者想將字串存取出來，先處理完這一部分後再執行釋放的部分

## q_size

int q_size(queue_t *q)
{
    if (q == NULL || q->head == NULL)
        return 0;
    return q->size;
}

- 判斷一些條件後回傳 size 即可，有了 `q->size` 後就能在時間複雜度 $O(1)$ 以內處理完

## q_reverse

void q_reverse(queue_t *q)
{
    list_ele_t *curr, *prev, *tmp;
    if (q == NULL || q->head == NULL)
        return;
    q->tail = &(q->head->next);
    prev = NULL;
    curr = q->head;
    while (curr != NULL) {
        tmp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = tmp;
    }
    q->head = prev;
}

- 透過 `prev` 和 `curr` 走完整張 linked list 並改變鏈結方向

## q_sort

void q_sort(queue_t *q)
{
    if (q == NULL || q->head == NULL || q->head->next == NULL)
        return;
    // bubble_sort(q, strnatcmp);
    merge_sort(q, strnatcmp);        
}

- 寫了 bubble sort 來驗證的確過不了 trace-16-perf.cmd
> sorting algorithms with O(n^2) time complexity are expected failed
> sorting algorithms with O(nlogn) time complexity are expected pass
>
- 原先擔心是否會用爆 stack，所以先寫了 iterative 版的 merge sort，但速度太慢，過不了 trace-15-perf.cmd，所以又寫了 recursive 版的
- Sorting algorithm 相關程式碼寫在 `sort.[ch]`，並也下載 [natural sort](https://github.com/sourcefrog/natsort) 的 `strnatcmp.[ch]`，最後修改 Makefile

## Makefile

OBJS := qtest.o report.o console.o harness.o queue.o strnatcmp.o sort.o\
        random.o dudect/constant.o dudect/fixture.o dudect/ttest.o

- `OBJS` 新增了 `strnatcmp.o` 和 `sort.o`

## merge_sort
### sort.h

#ifndef LAB0_SORT_H
#define LAB0_SORT_H

/*
 * This program implements kinds of sorting algorithm for singly linked list
 * You must make sure that queue_t *q, q->head, q->head->next isn't NULL
 */

#include "queue.h"

typedef int (*strcmpfp)(char const *, char const *); 

void merge_sort(queue_t *q, strcmpfp cmp);
void bubble_sort(queue_t *q, strcmpfp cmp);

#endif /* LAB0_SORT_H */

- 配合 `strnatcmp`，定義相對應的 function pointer type
- 可自訂比較方式

### sort.c

static strcmpfp cmp;

static list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
    list_ele_t buf;
    list_ele_t *tmp = &buf;

    while (l1 && l2) {
        if (cmp(l1->value, l2->value) <= 0) {
            tmp->next = l1; 
            tmp = tmp->next;
            l1 = l1->next;
        } else {
            tmp->next = l2; 
            tmp = tmp->next;
            l2 = l2->next;
        }   
    }   

    tmp->next = l1 ? l1 : l2; 

    return buf.next;
}

static list_ele_t *_merge_sort(list_ele_t *head)
{
    if (!head || !head->next)
        return head;

    list_ele_t *fast = head->next;
    list_ele_t *slow = head;

    // Split list
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }   
    fast = slow->next;
    slow->next = NULL;

    list_ele_t *l1 = _merge_sort(head);
    list_ele_t *l2 = _merge_sort(fast);

    return merge(l1, l2);
}

void merge_sort(queue_t *q, strcmpfp _cmp)
{
    list_ele_t *head, *curr;
    cmp = _cmp;

    // Sort
    head = _merge_sort(q->head);

    // Set queue_t
    q->head = head;
    curr = head;
    while (curr->next)
        curr = curr->next;
    q->tail = &(curr->next);
}

- 參考了 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 並實作出來
- `static strcmpfp cmp` 設為 global 目的是避免每次遞迴還要多傳這個變數一次

# Reference
[1]: man malloc
> The malloc() function allocates size bytes and returns a pointer to the allocated
memory. The memory is not initialized. If size is 0, then malloc() returns either
NULL, or a unique pointer value that can later be successfully passed to free().