# 2019q1 Homework1 (lab0)
###### tags: `System-Software-2019`
contributed by < `ultype` >

:::warning
注意看 [作業要求](https://hackmd.io/s/SJ4kPZYS4)，共筆的網址應該以 “publish” (點選「發布」按鈕可得) 的網址，也就是如 https://hackmd.io/s/XXXX 的形式，請留意!
:notes: jserv
:::

* Data structure
* queue.h
* list_ele_t 為單向 linkedlist單元
* queue_t 有兩個list_ele_t成員分別指向 linklist 頭和尾的list_ele_t單元 和size大小

/* */
typedef struct ELE {
    char *value;
    struct ELE *next;
} list_ele_t;

/* Queue structure */
typedef struct {
    list_ele_t *head;
    list_ele_t *tail;
    int size;
} queue_t;

* 第一題
* 新增一個queue
* 檢查malloc回傳值是否為null來判斷malloc有無成功
* 初始化queue

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

* 第二題
* 注意傳近來的queue是否為null
* 新增兩個function listEleNew和char counter 方便新增新單元
* 檢查listEleNew 回傳值 是否為null
* 插入元素會遇到兩個狀況
* cond1 Queue size == 0
* 頭尾同時指向新元素
* cond2 Queue size != 0
* 頭指向新元素
* 在頭處插入新元素

bool q_insert_head(queue_t *q, char *s) {
/*  What should you do if the q is NULL? */
    if (q == NULL)
        return false;
    /* Don't forget to allocate space for the string and copy it */
    newh = listEleNew(s);
    if (newh == NUL)
        return false;
    /* What if either call to malloc returns NULL? */
    if (q->head == NULL) {
        q->head = newh;
        q->tail = newh;
    } else {
        newh->next = q->head;
        q->head = newh;
    }
    q->size++;
    return true;
}

list_ele_t *listEleNew(char *s) {
    list_ele_t *newh = NULL;
    if (!s)
        return NULL;  // input string NULL
    newh = (list_ele_t *) malloc(sizeof(list_ele_t));
    if (!newh)
        return NULL;  // list element malloc fail
    newh->value = (char *) malloc(charCounter(s) * sizeof(char));
    if (newh->value == NULL) {  // malloc new char success
        free(newh);
        newh = NULL;
        // printf("new name success size%d
        // %s\n",charCounter(newh->value),newh->value);
    } else {  // malloc new char array fail
        strcpy(newh->value, s);
        newh->next = NULL;
    }
    return newh;
}

int charCounter(char *s) {
    int count = 0;
    if (s == NULL)
        return 0;
    while (s[count] != '\0') {
        count++;
    }
    return count + 1;
}

* 第三題
* 同第二題
* cond1 Queue size == 0
* 頭尾同時指向新元素
* cond2 Queue size != 0
* 尾指向新元素
* 在尾處插入新元素

bool q_insert_tail(queue_t *q, char *s) {
    /* You need to write the complete code for this function */
    list_ele_t *newh;
    /* What should you do if the q is NULL? */
    if (q == NULL)
        return false;
    newh = listEleNew(s);
    if (newh == NULL)
        return false;
    /* Don't forget to allocate space for the string and copy it */
    /* Remember: It should operate in O(1) time */
    if (q->tail == NULL) {  // from zero to one
        q->head = newh;
        q->tail = newh;
    } else {
        q->tail->next = newh;
        q->tail = newh;
    }
    q->size++;
    return true;
}

* 第四題
* 注意傳近來的queue是否為null
* 刪除元素會遇到兩個狀況
* queue 剩下一個單元
* queue 剩下多於一個的單元
* 字串的最後要補上"\0" 不然會出錯

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    list_ele_t *temp;
    int stringsize;

    if (q == NULL || q->size == 0)
        return false;

    /* You need to fix up this code. */
    temp = q->head;
    if (q->head == q->tail) {  // from one to zero
        q->head = NULL;
        q->tail = NULL;
    } else {
        q->head = q->head->next;
    }
    stringsize = charCounter(temp->value);
    if (bufsize > 0) {
        if (bufsize < stringsize) {
            strncpy(sp, temp->value, bufsize);
            sp[bufsize - 1] = '\0';
        } else {
            strcpy(sp, temp->value);
        }
    }
    free(temp->value);
    free(temp);

    q->size--;
    return true;
}

* 第五題
* 注意傳近來的queue是否為null
* 發現可重複利用第四題完成第五題

void q_free(queue_t *q) {
    /* How about freeing the list elements and the strings? */
    /* Free queue structure */
    if (q == NULL)
        return;
    while (q->head != NULL) {
        q_remove_head(q, NULL, 0);
    }
    free(q);
    return;
}

* 第六題
* 注意傳近來的queue是否為null
* 回傳queue內size 即可

int q_size(queue_t *q) {
    /* You need to write the code for this function */
    /* Remember: It should operate in O(1) time */
    if (q) {
        return q->size;
    }
    return 0;
}

* 第七題
* 注意傳近來的queue是否為null
* 觀察反轉後與原本linkedlist是對稱的
* 先將前面的單元往後搬
* 被搬動的單元搬到原本tail的後面
* 被搬動的單元的next指向tail->next
* a->b->c->d
* b->c->d->"a"
* c->d->"b"->a
* d->"c"->b->a
* 資料來源 leetcode 大神 （來源遺失）

    void q_reverse(queue_t *q) {
    /* You need to write the code for this function */
    list_ele_t *temp, *curr;
    if (q == NULL)
        return;
    curr = q->head;
    while (curr != q->tail) {
        temp = curr;
        curr = temp->next;
        temp->next = (q->tail)->next;
        (q->tail)->next = temp;
    }

    q->tail = q->head;  // swap head and tail
    q->head = curr;
}

# githook 腳本研究
* [reference1](http://wadmiraal.net/lore/2014/07/14/how-git-hooks-made-me-a-better-and-more-lovable-developer/)

* Makefile
* 執行git hook 腳本

GIT_HOOKS := .git/hooks/applied
$(GIT_HOOKS):
      @scripts/install-git-hooks
      @echo

* script資料夾內
* install-git-hooks
* pre-commit.hook
* 第23行(檢查所有 .c .cpp .h檔)

FILES=`git diff --cached --name-only --diff-filter=ACMR | grep -E "\.(c|cpp|h)$"`

* commit-msg.hook