# 2021q1 Homework1 (lab0)
contributed by < `howardjchen` >

## Goal of Homework
Impelment following functions in `queue.[ch]`:
- [x] `q_new`: Create a new, empty queue.
- [x] `q_free`: Free all storage used by a queue.
- [x] `q_insert_head`: Attempt to insert a new element at the head of the queue (LIFO discipline).
- [x] `q_insert_tail`: Attempt to insert a new element at the tail of the queue (FIFO discipline).
- [x] `q_remove_head`: Attempt to remove the element at the head of the queue.
- [x] `q_size`: Compute the number of elements in the queue.
- [x] `q_reverse`: Reorder the list so that the queue elements are reversed in order. This function should notallocate or free any list elements.
- [ ] `q_sort`: Sort the elements of the given queue in ascending order.

## Goal
* [x] 先完成 ```make check``` 可以 pass 的 version
* [x] q_insert_tail & q_size 時間複雜度改為 $O(1)$ (常數時間)
* [ ] 改進效能

## Learning target in lab0

* 學習使用 Valgrind
* 學習使用 Address Sanitizer
* 學習 Git
* 學習 Git pre-commit hook
* 學習 Git pre-push hook
* 時間複雜度改進
* 閱讀論文: Dude, is my code constant time?
* 學習 Makefile

# Envirnment setup

## Ubuntu 環境

Static hostname   : IntelH270
         Icon name: computer-desktop
           Chassis: desktop
  Operating System: Ubuntu 20.04 LTS
            Kernel: Linux 5.8.0-43-generic
      Architecture: x86-64

## 安裝必要工具

$ sudo apt install build-essential git-core valgrind
$ sudo apt install cppcheck clang-format aspell colordiff

| 名稱 | 作用 |
| --------------- | ----------------- |
| build-essential | GNU Toolchain and necessary headers/libraries |
| git-core | distributed revision control system |
| valgrind | dynamic binary instrumentation (DBI) framework |
| cppcheck | static C/C++ code analysis |
| clang-format | format C/C++/Obj-C code |
| aspell | spell-checker |
| colordiff | colorize 'diff' output |

# 開發紀錄

## q_new

* Allocate and initialize a queue.
* Assign head and tail to be ```NULL```
* queue size is initialized to be 0.

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));

    /* Return NULL is malloc fail */
    if (!q)
        return NULL;

    q->head = NULL;
    q->tail = NULL;
    q->size = 0;
    return q;
}

## q_insert_head

* Description: TBD

bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    char *news;

    /* Return false is q is NULL */
    if (!q)
        return false;

    /* Allocate space for new node */
    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;

    /* Allocate space for string */
    news = malloc(sizeof(news));
    if(!news)
        return false;

    /* Copy string */
    memcpy(news, s, strlen(s) + 1);

    /* Attach new head */
    newh->next = q->head;
    q->head = newh;
    newh->value = news;
    q->size += 1;

    return true;
}

## q_free

* Description: TBD

/* Free all storage used by queue */
/* Free all storage used by queue */
void q_free(queue_t *q)
{
    list_ele_t *node, *pre_node;

    if(!q)
        return;

    /* Free each element and node */
    pre_node = q->head;
    while(pre_node != NULL) {
        node = pre_node->next;
        free(pre_node->value);
        free(pre_node);
        pre_node = node;
    }
    /* Free queue structure */
    free(q);
}

## q_insert_tail

bool q_insert_tail(queue_t *q, char *s)
{
    list_ele_t *newt;
    char *news;

    /* Return false is q is NULL */
    if (!q)
        return false;

    /* Allocate space for new node */
    newt = malloc(sizeof(list_ele_t));
    if (!newt)
        return false;

    /* Allocate space for string */
    news = malloc(strlen(s) + 1);
    if (!news) {
        free(newt);
        return false;
    }

    /* Copy string */
    memcpy(news, s, strlen(s) + 1);
    newt->value = news;
    newt->next = NULL;

    if (q->size > 0)
        q->tail->next = newt;
    else
        q->head = newt;

    q->tail = newt;
    q->size += 1;

    return true;
}

# 參考連結

* [HackMD_教學](https://hackmd.io/c/tutorials-tw/)
* [C Programming Lab: Assessing Your C Programming Skills](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)
* [ASCII_Table](http://www.asciitable.com/)

###### tags `lab` `Linux-internals`