2021q1 Homework1 (lab0)

contributed by < howardjchen >

Goal of Homework

Impelment following functions in queue.[ch]:

• q_new: Create a new, empty queue.
• q_free: Free all storage used by a queue.
• q_insert_head: Attempt to insert a new element at the head of the queue (LIFO discipline).
• q_insert_tail: Attempt to insert a new element at the tail of the queue (FIFO discipline).
• q_remove_head: Attempt to remove the element at the head of the queue.
• q_size: Compute the number of elements in the queue.
• 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

• 先完成 make check 可以 pass 的 version
• 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_教學
• C Programming Lab: Assessing Your C Programming Skills
• ASCII_Table

tags lab Linux-internals