2022q1 Homework1 (lab0)

contributed by < MicahDoo >

實驗環境

Linux on Macbook Air

$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0

Architecture:                    x86_64
CPU op-mode(s):                  32-bit, 64-bit
Byte Order:                      Little Endian
Address sizes:                   36 bits physical, 48 bits virtual
CPU(s):                          2
On-line CPU(s) list:             0,1
Thread(s) per core:              1
Core(s) per socket:              2
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           23
Model name:                      Intel(R) Core(TM)2 Duo CPU     L9600  @ 2.13G
                                 Hz
Stepping:                        10
CPU MHz:                         1578.988
CPU max MHz:                     2128.0000
CPU min MHz:                     798.0000
BogoMIPS:                        4247.28
Virtualization:                  VT-x
L1d cache:                       64 KiB
L1i cache:                       64 KiB
L2 cache:                        6 MiB
NUMA node0 CPU(s):               0,1

作業要求

詳細閱讀 C Programming Lab ，依據指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改，記得也該實作 q_sort 函式。

• q_new: 創一個空的 queue
• q_free: 釋放掉一個 queue
• q_insert_head: 在 head 插入一個 element (LIFO)
• q_insert_tail: 在 tail 插入一個 element (FIFO), O(1)
• q_remove_head: 把 head 的 element 移除
• q_size: return queue 的大小
• q_reverse: 將 queue 反轉，不配置或釋放任何的 element
• q_sort: 將 queue 由小排到大, sort by nature sort

Linux 上安裝注音

$ sudo apt-get install ibus-chewing

Settings -> Region & Language -> +(Under Input Sources) -> Other -> Chinese(Chewing)

原始作業文件詳讀

1. Logistics 細節事項

There are no late days, grace days, or extensions for this assignment.
Late days/period: 可以接受遲交的日子。(通常會扣分)
Grace days/period: 可以遲交並且不扣分的日子。
Extensions: 延長繳交。
All handins are electronic.

2. Overview 概覽

Ther material covered should all be review for you.

Explicit memory management, as required in C.
用C實際人工手打程式碼做記憶體管理，而非讓編譯器自動完成。
Creating and manipulating pointer-based data structures.
學會使用創建及操縱指針類的結構。
Ehancing the performance of key operations by storing redundant information in data structures.
利用在資料結構中儲存多餘的資訊以強化關鍵操作的效能。
Implementing robust code that operates correctly with invalid arguments in data structures.
實做出能處理無效輸入的穩健程式碼。

The lab involves implementing a queue, suppporting both LIFO and FIFO queuing disciplines. The underlying data structure is a singly-linked list, enhanced to make some of the operations more efficient.

3. Resources 有用的資源

6. Starter Code Overview 初始程式碼概覽

One queue is one queue_t variable whose ->head points to the head of the list.
One node is one ELE/list_ele_t variable storing the string ->value and the next node ->next.

本次作業不同於CMU的作業，因此有多處已不甚相同！

開發過程

Playing Around With make test

Tested make test before putting in any code and found two successful traces:

1. malloc failure on new

+++ TESTING trace trace-13-malloc:
# Test of malloc failure on new
---	trace-13-malloc	6/6

Tracing Test

In MakeFile:

test: qtest scripts/driver.py
	scripts/driver.py -c

In scripts/driver.py:

if __name__ == "__main__":
    run(sys.argv[0], sys.argv[1:])

If the file is run directly, call run(sys.arg[0]), sys.argv[1:]), which is a method in the file. Here, sys.arg[0] == 'scripts/driver.py' and sys.argv[1:] is a list that contains only one string -c.

In def run(name, args)::

t = Tracer(qtest=prog,
   verbLevel=vlevel,
   autograde=autograde,
   useValgrind=useValgrind,
   colored=colored)
t.run(tid)

In run(self, tid) under the class Tracer:

ok = self.runTrace(t)

In runTrace(t):

fname = "%s/%s.cmd" % (self.traceDirectory, self.traceDict[tid])
vname = "%d" % self.verbLevel
clist = self.command + ["-v", vname, "-f", fname]

try:
    retcode = subprocess.call(clist)
except Exception as e:
    self.printInColor("Call of '%s' failed: %s" % (" ".join(clist), e), self.RED)
    return False

With self.traceDirectiory == "./traces" and self.traceDict == "trace-13-malloc".
…
clist == "./qtest -v 0 -f ./traces/trace-13-malloc"

In trace-13-malloc.cmd:

# Test of malloc failure on new
option fail 10
option malloc 50
new
new
new
new
new
new

Only the commands option and new are used.

In qtest.c:

ADD_COMMAND(new, "                | Create new queue");
...
add_param("malloc", &fail_probability, "Malloc failure probability percent",
              NULL);
add_param("fail", &fail_limit,
              "Number of times allow queue operations to return false", NULL);

These are the command and parameters used in trace-13.

In static bool do_new(int argc, char *argv[]):

if (exception_setup(true)) {
    l_meta.l = q_new();
    l_meta.size = 0;
}
exception_cancel();
lcnt = 0;
show_queue(3);

return ok && !error_check();

In show_queue():

if (!l_meta.l) {
    report(vlevel, "l = NULL");
    return true;
}

Seems like nothing else is being checked after q_new() is called, as show_queue() returns true right after a NULL queue is being detected, which is why the test passed.

TODO: revise the above code to include ./qtest -f traces/trace-13-malloc.cmd which will tell us that the reason it passes is because it only returns a WARNING when the intialized list is NULL.

2. complexity

+++ TESTING trace trace-17-complexity:
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
Probably constant time
Probably constant time
Probably constant time
Probably constant time
---     trace-17-complexity     5/5

Why?
Nothing has been put into the code yet so naturally the complexity is expected to be O(0).

element_t

Upon inspection of the given queue.h file, the difference in struct declaration between the CMU version and the NCKU version is clear:

CMU

TODO

NCKU

TODO

q_new

First try (incorrect):

struct list_head *q_new()
{
    element_t *q = (element_t*)malloc(sizeof(element_t));
    if(!q) {
        return NULL;
    }
    INIT_LIST_HEAD(&q->list);
    return &q->list;
}

Second try:

The first node doesn't have to be wrapped in element_t.

struct list_head *q_new()
{
    struct list_head *q = (struct list_head*)malloc(sizeof(struct list_head));
    if(!q) 
    {
        INIT_LIST_HEAD(q);
    }
    return q; // If could not allocate space, q is automatically NULL
}

Test q_new (trace=13)

$ ./qtest -f traces/trace-13-malloc.cmd 
cmd> # Test of malloc failure on new
cmd> option fail 10
cmd> option malloc 50
cmd> new
WARNING: Malloc returning NULL
l = NULL
cmd> new
l = []
cmd> new
Freeing old queue
l = NULL
ERROR: Freed queue, but 1 blocks are still allocated
WARNING: Malloc returning NULL
l = NULL
cmd> new
WARNING: Malloc returning NULL
l = NULL
cmd> new
l = []
cmd> new
Freeing old queue
l = NULL
ERROR: Freed queue, but 2 blocks are still allocated
WARNING: Malloc returning NULL
l = NULL
cmd> 
cmd> 

1. option malloc 50: malloc will return NULL on average half of the times.
2. Warning: malloc returning NULL: the creation of a new queue failed, giving l = NULL, it should be l = [].
3. When trying to execute new when l != NULL, the old queue will be freed. This is where errors happen. We need to finish q_free() before we can complete q_new().

q_free

Remember to free value first before freeing the whole element.

void q_free(queue_t *q)
{
    // NULL queue
    if (q == NULL)
        return;

    for (list_ele_t *tmp = q->head; q->head; tmp = q->head) {
        q->head = q->head->next;
        free(tmp->value);
        free(tmp);
    }
    free(q);
}

Reminder: Fetch Upstream

Remember to click fetch upstream in your repository to keep up with updates.

q_insert_head

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *e = (element_t *) malloc(sizeof(element_t));
    if (!e)
        return false;
    e->value = strdup(s);  // strdup already does the malloc, WHICH MIGHT FAIL
    if (!e->value)  // if string memory alloc failed
    {
        free(e);
        return false;
    }
    list_add(&e->list, head);
    return true;
}

q_insert_tail

bool q_insert_tail(struct list_head *head, char *s)
{
    if (head == NULL)
        return false;
    element_t *e = (element_t *) malloc(sizeof(element_t));
    if (e == NULL)
        return false;
    e->value = strdup(s);  // strdup already does the malloc, WHICH MIGHT FAIL
    if (e->value == NULL)  // if string memory alloc failed
    {
        free(e);
        return false;
    }
    list_add_tail(&e->list, head);
    return true;
}

q_remove_head

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *e = list_first_entry(head, element_t, list);
    if (sp) {
        // incorrect: strndup does a new malloc, storing the value to a new
        // address other than where sp is originally pointing to sp =
        // strndup(e->value, bufsize-1);
        strncpy(sp, e->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    list_del(&e->list);
    return e;
}

q_remove_tail

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *e = list_last_entry(head, element_t, list);
    if (sp) {
        strncpy(sp, e->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    list_del(&e->list);
    return e;
}

q_release_element

void q_release_element(element_t *e)
{
    free(e->value);
    free(e);
}

q_size

int q_size(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;
    int i = 0;
    struct list_head *it = head->next;
    list_for_each(it, head) {
        ++i;
    }
    return i;
}

q_delete_mid

Two pointers going from the opposite sides inward at the same pace.
When both pointers meet(l == r, odd length) or when they are one node apart (l->next == r, even length), the left pointer should be deleted.

bool q_delete_mid(struct list_head *head)
{
    if (head == NULL || list_empty(head))
        return false;

    struct list_head *l = head->next;
    struct list_head *r = head->prev;

    while (l != r && l->next != r) {
        l = l->next;
        r = r->prev;
    }

    list_del(l); 
    q_release_element(list_entry(l, element_t, list));

    return true;
}

q_delete_dup

I use a pointer to pointer to make removing the current node easy.
In each iteration, if the current string in the node is the same as the next, I delete the current string, then continue deleting nodes until a different string is found or the end is reached.

bool q_delete_dup(struct list_head *head)
{
    if (!head)
        return false;

    struct list_head **curr = &head->next;
    struct list_head *tmp;
    while ((*curr) != head) {
        /* If the next string is different or if reach the end, advance the traversal */
        if ((*curr)->next == head ||
            strcmp(
                list_entry((*curr), element_t, list)->value,
                list_entry((*curr)->next, element_t, list)->value)) {  // diff
            curr = &(*curr)->next;
        } else {
        /* If not, we have a couple of  duplicate nodes. Delete all of them. */
            do {
                /* Remember to update the next node to point to the previous \
                 * node before moving the next node into the address of the current node \
                 * because if we do the latter first, (*curr)->prev won't be the previous node \
                 * and we can't access the previous node \
                 * anymore */
                tmp = *curr;
                (*curr)->next->prev = (*curr)->prev;  // !!!IMPORTANT!!!
                *curr = (*curr)->next; /* Same as (*curr)->prev->next = (*curr)->next */
                q_release_element(list_entry(tmp, element_t, list));
            } while ((*curr)->next != head &&
                     !strcmp(list_entry((*curr), element_t, list)->value,
                             list_entry((*curr)->next, element_t, list)
                                 ->value));  // same
            tmp = *curr;
            (*curr)->next->prev = (*curr)->prev;  // !!!IMPORTANT!!!
            *curr = (*curr)->next;
            (*curr)->next->prev = *curr;
            q_release_element(list_entry(tmp, element_t, list));
        }
    }

    return true;
}

q_swap

Special attention required on the order in which we assign pointers:

• Always start with inward pointers, that is, pointers that point to nodes you can already have variables for. In this case, they are left and right.
  • right->next->prev is originally left, but since we can already reference that node with left, we can change it as early as possible.
• Outward pointers usually comes last because changing one results in losing reference to a node you might potentially need later.
  • In this case, if I change left->prev, I can no longer access the left neighbor of the pair anymore.

void q_swap(struct list_head *head)
{
    if (!head || list_empty(head))
        return;

    struct list_head *left = head->next;
    struct list_head *right = left->next;

    while (left != head && right != head) {
        /* Don't modify the "outwards" pointers first, e.g. left->prev or
         * right->next \
         * because they are the only variable giving us reference to the left
         * neightbor \ and the right neighbor. */

        /* Make the neighbors point to the correct new nodes */
        right->next->prev = left;
        left->prev->next = right;

        /* Make the two nodes point to the new neighbors */
        right->prev = left->prev;
        left->next = right->next;

        /* Change outward pointers */
        right->next = left;
        left->prev = right;

        /* Next two pairs */
        left = left->next;
        right = left->next;
    }
}

q_reverse

Because this operation involves swapping two values (it->next & it->prev), so a tmp node is inevitable.

void q_reverse(struct list_head *head)
{
    if (head == NULL || list_empty(head))
        return;
    struct list_head *it = head;
    struct list_head *tmp;

    do {
        tmp = it->next;
        it->next = it->prev;
        it->prev = tmp;
        it = it->prev; /* it = it->next works too */
    } while (it != head);
}

MEMO: 觀摩@LGP-TW的實作，看到教授留下一行：針對上方的若干操作，提取出可共用的 inline function。
不甚解其意，待問。

q_sort

void merge_sort(struct list_head **head)
{
    /* Base cases */
    if (!*head || !(*head)->next)
        return;

    /* Split: fast will reach the end when slow reaches the middle */
    struct list_head *fast = (*head)->next;
    struct list_head *slow = *head;

    while (fast != NULL) {
        fast = fast->next;
        if (fast != NULL) {
            fast = fast->next;
            slow = slow->next;
        }
    }

    struct list_head *left = *head;
    struct list_head *right = slow->next;
    slow->next = NULL; /* End of the left list */
    merge_sort(&left);
    merge_sort(&right);

    struct list_head dummy;
    struct list_head *curr = &dummy;
    while (left && right) {
        if (strcmp(list_entry(left, element_t, list)->value, list_entry(right, element_t, list)->value) > 0) {
            curr->next = right;
            right = right->next;
        } else {
            curr->next = left;
            left = left->next;
        }
        curr = curr->next;
    }
    curr->next = !left ? right : left;
    *head = dummy.next;
}

void q_sort(struct list_head *head)
{
    if (head == NULL || list_empty(head) || list_is_singular(head))
        return;

    /* Turn it into a singly linked list where the end is NULL */
    head->prev->next = NULL;

    /* The first node should have a value */
    merge_sort(&(head->next));

    /* Revert it back to a circular doubly linked list */
    struct list_head *prev = head;
    struct list_head *curr = head->next;
    while (curr != NULL) {
        curr->prev = prev;
        prev = curr;
        curr = curr->next;
    }
    prev->next = head;
    head->prev = prev;
}

q_sort performance fail

The 14th trace failed. Time limit exceeded.

$ ./qtest -f traces/trace-14-perf.cmd 
cmd> # Test performance of insert_tail, reverse, and sort
cmd> option fail 0
cmd> option malloc 0
cmd> new
l = []
cmd> ih dolphin 1000000
l = [dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin ... ]
cmd> it gerbil 1000000
l = [dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin ... ]
cmd> reverse
l = [gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil gerbil ... ]
cmd> sort
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer
Aborted (core dumped)

Since my computer is from 2011 I think this error might be due to my computer being too old. It could be my algorithm as well. I shall ask a classmate to test my code for me on a different computer.
Update:
Works fine on Github Workflow.