2022q1 Homework1 (lab0)

contributed by < oucs638 >

Test Environment

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

$ lscpu
Architecture:                    x86_64
CPU op-mode(s):                  32-bit, 64-bit
Byte Order:                      Little Endian
Address sizes:                   39 bits physical, 48 bits virtual
CPU(s):                          12
On-line CPU(s) list:             0-11
Thread(s) per core:              2
Core(s) per socket:              6
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           158
Model name:                      Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
Stepping:                        13
CPU MHz:                         3594.185
CPU max MHz:                     4500.0000
CPU min MHz:                     800.0000
BogoMIPS:                        5199.98
Virtualization:                  VT-x
L1d cache:                       192 KiB
L1i cache:                       192 KiB
L2 cache:                        1.5 MiB
L3 cache:                        12 MiB
NUMA node0 CPU(s):               0-11

Implement Progress Records

Homework Requirement

There is the Linux-like doubly-linked list implementation in lab0-c/list.h.
- Reference: Linux Kernel API
- Simplify the code with these APIs.

q_new

Create empty queue.
Return NULL if failed to allocate enough memory space.
Initialize queue before returning it.

struct list_head *q_new()
{
    // allocate memory space for list head
    struct list_head *head = malloc(sizeof(struct list_head));

    // failed to allocate space
    if (!head)
        return NULL;

    // allocate space success, init it
    INIT_LIST_HEAD(head);

    return head;
}

q_free

Iterate over list entries and release every element.
Use list_for_each_entry_safe(entry, safe, head, member) to iterate since it will save the next node in temporary storage, so it allows removing the current node.
Invoke q_release_element(element_t *e) to free the node.

void q_free(struct list_head *l)
{
    if (!l)
        return;

    // iterate over list entries and release every element
    element_t *cur = NULL, *nxt = NULL;
    list_for_each_entry_safe (cur, nxt, l, list)
        q_release_element(cur);

    // release list head
    free(l);
}

q_insert_head

Allocate memory space for new element.
Allocate memory space for value in new element before copying the string into it.
Invoke memcpy() to copy the string into value in new element.
Invoke list_add() to add the new node to the beginning of the list.

bool q_insert_head(struct list_head *head, char *s)
{
    // return flase if queue if NULL
    if (!head)
        return false;

    // allocate memory space for new queue element
    // return false if allocate space failed
    // initialize "list" in new element
    element_t *new = malloc(sizeof(element_t));
    if (!new)
        return false;
    INIT_LIST_HEAD(&new->list);

    // allocate memory space for "value" in new element
    // allocate one addtional character of memory space for '\0'
    // return false if allocate space failed
    size_t len = strlen(s) + 1;
    new->value = malloc(len * sizeof(char));
    if (!new->value) {
        free(new);
        return false;
    }

    // copy the string into value in new element
    memcpy(new->value, s, len);

    // add the new node to the beginning of the list
    list_add(&new->list, head);

    return true;
}

q_insert_tail

Similar to q_insert_head but list_add() is replaced by list_add_tail() to add the new node to the end of the list.

bool q_insert_tail(struct list_head *head, char *s)
{
    // return flase if queue if NULL
    if (!head)
        return false;

    // allocate memory space for new queue element
    // return false if allocate space failed
    // initialize "list" in new element
    element_t *new = malloc(sizeof(element_t));
    if (!new)
        return false;
    INIT_LIST_HEAD(&new->list);

    // allocate memory space for "value" in new element
    // allocate one addtional character of memory space for '\0'
    // return false if allocate space failed
    size_t len = strlen(s) + 1;
    new->value = malloc(len * sizeof(char));
    if (!new->value) {
        free(new);
        return false;
    }

    // copy the string into value in new element
    memcpy(new->value, s, len);

    // add the new node to the end of the list
    list_add_tail(&new->list, head);

    return true;
}

q_remove_head

Find the target entry from the list and remove it from the list.
Invoke list_first_entry() to get the first entry of the list.
Invoke list_del_init() to remove the node from the list.
Invoke memcpy() to copy the removed string into sp.

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    // return NULL if queue is NULL or empty
    if (!head || list_empty(head))
        return NULL;

    // get the first entry of the list
    // and remove it from the list
    element_t *target = list_first_entry(head, element_t, list);
    list_del_init(&target->list);

    // copy the removed string if sp is non-NULL
    if (sp) {
        // copy the removed string and plus a null terminator
        memcpy(sp, target->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    
    return target;
}

q_remove_tail

Similat to q_insert_head but list_first_entry() is replaced by list_last_entry() to get the last entry of the list.

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    // return NULL if queue if NULL or empty
    if (!head || list_empty(head))
        return NULL;

    // get the last entry of the list
    // and remove it from the list
    element_t *target = list_last_entry(head, element_t, list);
    list_del(head->prev);

    // copy the removed string if sp is non-NULL
    if (sp) {
        // copy the removed string and plus a null terminator
        memcpy(sp, target->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    return target;
}

q_size

Invoke list_for_each() to iterate over list nodes.

int q_size(struct list_head *head)
{
    // return 0 if queue is NULL or empty
    if (!head || list_empty(head))
        return 0;

    int size = 0;

    // iterate over list nodes and count the number of nodes
    struct list_head *tmp;
    list_for_each (tmp, head)
        size++;

    return size;
}

q_delete_mid

Iterate from both directions with two iterater to find the middle node.
Invoke list_entry() to get the entry of the middle node.
Invoke list_del_init() to remove the middle from list.
Invoke q_release_element() to free the node.

bool q_delete_mid(struct list_head *head)
{
    // return false if queue is NULL or empty
    if (!head || list_empty(head))
        return false;

    // find the middle node
    struct list_head *l = head->next, *r = head->prev;
    while (l != r && l->next != r) {
        l = l->next;
        r = r->prev;
    }

    // delete the middle node in list
    element_t *mid = list_entry(r, element_t, list);
    list_del_init(&mid->list);
    q_release_element(mid);

    return true;
}

q_delete_dup

Invoke list_for_each_entry_safe() to iterate over list entries because it allow deletes.
Use flg to represent whether the current node needs to be deleted or not.
If the value of current node is same as the value of next node, delete current node and set the flg to true.

bool q_delete_dup(struct list_head *head)
{
    // return false if queue is NULL
    if (!head)
        return false;

    // return true without checking if queue is empty or singular
    // if (list_empty(head) || list_is_singular(head))
    //     return true;

    bool flg = false;
    element_t *cur = NULL, *nxt = NULL;
    list_for_each_entry_safe (cur, nxt, head, list) {
        if ((cur->list.next != head) &&
            (strcmp(cur->value,
                    list_entry(cur->list.next, element_t, list)->value) == 0)) {
            list_del(&cur->list);
            q_release_element(cur);
            flg = true;
        } else if (flg) {
            list_del(&cur->list);
            q_release_element(cur);
            flg = false;
        }
    }

    return true;
}

q_swap

Do nothing if queue if NULL or empty or singular.
Use two list_head * a and b to implement swap(a, b).





















void q_swap(struct list_head *head)
{
    // do nothing if queue is NULL or empty or singular
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    struct list_head *a = head->next;
    // check if there are still unprocessed nodes
    // and more than one node has not been processed
    while (a != head && a->next != head) {
        // implement swap (a, b) to swap (a, b) to (b, a)
        struct list_head *b = a->next;
        a->next = b->next;
        b->prev = a->prev;
        a->prev->next = b;
        b->next->prev = a;
        a->prev = b;
        b->next = a;
        a = a->next;
    }
}

Explain with diagram

The original state.

Step 0 : line 12

Step 1 : line 13

Step 2 : line 14

Step 3 : line 15

Step 4 : line 16

Step 5 : line 17

Step 6 : line 18

Step 7 : line 19

q_reverse



















void q_reverse(struct list_head *head)
{
    // do nothing if queue is NULL or empty
    if (!head || list_empty(head))
        return;

    struct list_head *cur = head;

    // save the original next node of current node first
    // then make the original prev node into the new next node
    // and make the origin next node into the new prev node
    // iterate after done, process all node the same
    do {
        struct list_head *nxt = cur->next;
        cur->next = cur->prev;
        cur->prev = nxt;
        cur = nxt;
    } while (cur != head);
}

Explain with diagrams

The original state.

Step 0 : line 14

Step 1 : 15

Step 2 : line 16

Step 3 : line 17

Repeat the step 1 to step 3

The complete state.

Equal to:

q_sort

Sort the list with merge sort.
The merge function refer to Leetcode NO.23 Merge k Sorted Lists.
Merge the sorted lists in an iterative way to prevent excessive function call in a recursive way lead to stack overflow.
Refer to linux: lib/list_sort.c to improve the merge function.

struct list_head *merge(struct list_head *l1, struct list_head *l2)
{
    if (!l1)
        return l2;
    if (!l2)
        return l1;

    struct list_head *res = NULL, **cur = &res;

    while (l1 && l2) {
        if (strcmp(list_entry(l1, element_t, list)->value,
                   list_entry(l2, element_t, list)->value) > 0) {
            *cur = l2;
            cur = &l2->next;
            l2 = l2->next;
        } else {
            *cur = l1;
            cur = &l1->next;
            l1 = l1->next;
        }
    }

    if (l1)
        *cur = l1;
    if (l2)
        *cur = l2;

    return res;
}

The mergeSort function refer to Linked List Sort.

struct list_head *mergeSort(struct list_head *l)
{
    if (!l || !l->next)
        return l;

    // split the list
    struct list_head *fst = l->next, *slw = l;
    while (fst && fst->next) {
        slw = slw->next;
        fst = fst->next->next;
    }
    fst = slw->next;
    slw->next = NULL;

    return merge(mergeSort(l), mergeSort(fst));
}

Refer to linux: lib/list_sort.c to treat the list as singly linked list.

void q_sort(struct list_head *head)
{
    // do nothing if queue is NULL or empty or singular
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    // treat the list as a singly linked list
    head->prev->next = NULL;

    // sort the list with merge sort
    head->next = mergeSort(head->next);

    // recover the list as doubly linked list
    struct list_head *cur = head;
    while (cur->next != NULL) {
        cur->next->prev = cur;
        cur = cur->next;
    }
    head->prev = cur;
    cur->next = head;
}

q_shuffle

Refer to Fisher–Yates shuffle to implement do_shuffle in q_test.c.
Pseudo code.

-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 downto 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

C code

// https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
static bool do_shuffle()
{
    if (!l_meta.l)
        report(3, "Warning: Calling shuffle on null queue");
    error_check();

    int i = l_meta.size;
    // for i from n - 1 downto 1
    for(struct list_head *ptr1 = l_meta.l->prev; i > 0; i--, ptr1 = ptr1->prev) {
        struct list_head *ptr2 = l_meta.l->next;
        // j random integer such that 0 <= j <= i
        for (int j = rand() % i; j > 0; j--, ptr2 = ptr2->next);
        // exchange a[i] and a[j]
        element_t *ele1 = list_entry(ptr1, element_t, list), 
                  *ele2 = list_entry(ptr2, element_t, list);
        char *tmp = ele1->value;
        ele1->value = ele2->value;
        ele2->value = tmp;
    }
    show_queue(3);
    return !error_check();
}

Add the command in console_init().

ADD_COMMAND(
        shuffle, "                | Shuffle all nodes in queue");

Improve the Code Progress Records

Problems to be solved

Failed the last test.

+++ TESTING trace trace-17-complexity:
---	trace-17-complexity	0/5
---	TOTAL		95/100

But the code works on the local side, so it means q_insert_head, q_insert_tail, q_remove_head, or q_remove_tail are not stable.
Profile the q_test with valgrind.

make && valgrind ./qtest < traces/trace-17-complexity.cmd

Result

make: Nothing to be done for 'all'.
Probably constant time
ERROR: Probably not constant time
Probably constant time
Probably constant time
==4162== 32 bytes in 1 blocks are still reachable in loss record 1 of 32
==4162==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162==    by 0x10CD55: malloc_or_fail (report.c:189)
==4162==    by 0x10D7DF: add_cmd (console.c:89)
==4162==    by 0x10DB69: init_cmd (console.c:408)
==4162==    by 0x10C4C5: main (qtest.c:944)
==4162== 
==4162== 32 bytes in 1 blocks are still reachable in loss record 2 of 32
==4162==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162==    by 0x10CD55: malloc_or_fail (report.c:189)
==4162==    by 0x10D7DF: add_cmd (console.c:89)
==4162==    by 0x10DB83: init_cmd (console.c:409)
==4162==    by 0x10C4C5: main (qtest.c:944)
==4162== 
==4162== 32 bytes in 1 blocks are still reachable in loss record 3 of 32
==4162==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162==    by 0x10CD55: malloc_or_fail (report.c:189)
==4162==    by 0x10D7DF: add_cmd (console.c:89)
==4162==    by 0x10DB9D: init_cmd (console.c:410)
==4162==    by 0x10C4C5: main (qtest.c:944)
==4162== 
==4162== 32 bytes in 1 blocks are still reachable in loss record 4 of 32
==4162==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162==    by 0x10CD55: malloc_or_fail (report.c:189)
==4162==    by 0x10D7DF: add_cmd (console.c:89)
==4162==    by 0x10DBB7: init_cmd (console.c:411)
==4162==    by 0x10C4C5: main (qtest.c:944)
==4162== 
==4162== 32 bytes in 1 blocks are still reachable in loss record 5 of 32
==4162==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162==    by 0x10CD55: malloc_or_fail (report.c:189)
==4162==    by 0x10D7DF: add_cmd (console.c:89)
==4162==    by 0x10DBD1: init_cmd (console.c:412)
==4162==    by 0x10C4C5: main (qtest.c:944)
==4162== 
==4162== 32 bytes in 1 blocks are still reachable in loss record 6 of 32
==4162==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162==    by 0x10CD55: malloc_or_fail (report.c:189)
==4162==    by 0x10D7DF: add_cmd (console.c:89)
==4162==    by 0x10DBEB: init_cmd (console.c:413)
==4162==    by 0x10C4C5: main (qtest.c:944)
==4162== 
==4162== 32 bytes in 1 blocks are still reachable in loss record 7 of 32
==4162==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162==    by 0x10CD55: malloc_or_fail (report.c:189)
==4162==    by 0x10D7DF: add_cmd (console.c:89)
==4162==    by 0x10DC05: init_cmd (console.c:414)
==4162==    by 0x10C4C5: main (qtest.c:944)
==4162== 
==4162== 32 bytes in 1 blocks are still reachable in loss record 8 of 32
==4162==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162==    by 0x10CD55: malloc_or_fail (report.c:189)
==4162==    by 0x10D7DF: add_cmd (console.c:89)
==4162==    by 0x10C4DF: console_init (qtest.c:767)
==4162==    by 0x10C4DF: main (qtest.c:945)
==4162== 
==4162== 32 bytes in 1 blocks are still reachable in loss record 9 of 32
==4162==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162==    by 0x10CD55: malloc_or_fail (report.c:189)
==4162==    by 0x10D7DF: add_cmd (console.c:89)
==4162==    by 0x10C4F9: console_init (qtest.c:768)
==4162==    by 0x10C4F9: main (qtest.c:945)
==4162== 
==4162== 32 bytes in 1 blocks are still reachable in loss record 10 of 32
==4162==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162==    by 0x10CD55: malloc_or_fail (report.c:189)
==4162==    by 0x10D7DF: add_cmd (console.c:89)
==4162==    by 0x10C513: console_init (qtest.c:769)
==4162==    by 0x10C513: main (qtest.c:945)
==4162== 
==4162== 32 bytes in 1 blocks are still reachable in loss record 11 of 32
==4162==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162==    by 0x10CD55: malloc_or_fail (report.c:189)
==4162==    by 0x10D7DF: add_cmd (console.c:89)
==4162==    by 0x10C52D: console_init (qtest.c:773)
==4162==    by 0x10C52D: main (qtest.c:945)
==4162== 
==4162== 32 bytes in 1 blocks are still reachable in loss record 12 of 32
==4162==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162==    by 0x10CD55: malloc_or_fail (report.c:189)
==4162==    by 0x10D7DF: add_cmd (console.c:89)
==4162==    by 0x10C547: console_init (qtest.c:777)
==4162==    by 0x10C547: main (qtest.c:945)
==4162== 
==4162== 32 bytes in 1 blocks are still reachable in loss record 13 of 32
==4162==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162==    by 0x10CD55: malloc_or_fail (report.c:189)
==4162==    by 0x10D7DF: add_cmd (console.c:89)
==4162==    by 0x10C561: console_init (qtest.c:781)
==4162==    by 0x10C561: main (qtest.c:945)
==4162== 
==4162== 32 bytes in 1 blocks are still reachable in loss record 14 of 32
==4162==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162==    by 0x10CD55: malloc_or_fail (report.c:189)
==4162==    by 0x10D7DF: add_cmd (console.c:89)
==4162==    by 0x10C57B: console_init (qtest.c:785)
==4162==    by 0x10C57B: main (qtest.c:945)
==4162== 
==4162== 32 bytes in 1 blocks are still reachable in loss record 15 of 32
==4162==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162==    by 0x10CD55: malloc_or_fail (report.c:189)
==4162==    by 0x10D7DF: add_cmd (console.c:89)
==4162==    by 0x10C595: console_init (qtest.c:788)
==4162==    by 0x10C595: main (qtest.c:945)
==4162== 
==4162== 32 bytes in 1 blocks are still reachable in loss record 16 of 32
==4162==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162==    by 0x10CD55: malloc_or_fail (report.c:189)
==4162==    by 0x10D7DF: add_cmd (console.c:89)
==4162==    by 0x10C5AF: console_init (qtest.c:789)
==4162==    by 0x10C5AF: main (qtest.c:945)
==4162== 
==4162== 32 bytes in 1 blocks are still reachable in loss record 17 of 32
==4162==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162==    by 0x10CD55: malloc_or_fail (report.c:189)
==4162==    by 0x10D7DF: add_cmd (console.c:89)
==4162==    by 0x10C5C9: console_init (qtest.c:790)
==4162==    by 0x10C5C9: main (qtest.c:945)
==4162== 
==4162== 32 bytes in 1 blocks are still reachable in loss record 18 of 32
==4162==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162==    by 0x10CD55: malloc_or_fail (report.c:189)
==4162==    by 0x10D7DF: add_cmd (console.c:89)
==4162==    by 0x10C5E3: console_init (qtest.c:792)
==4162==    by 0x10C5E3: main (qtest.c:945)
==4162== 
==4162== 32 bytes in 1 blocks are still reachable in loss record 19 of 32
==4162==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162==    by 0x10CD55: malloc_or_fail (report.c:189)
==4162==    by 0x10D7DF: add_cmd (console.c:89)
==4162==    by 0x10C5FD: console_init (qtest.c:793)
==4162==    by 0x10C5FD: main (qtest.c:945)
==4162== 
==4162== 32 bytes in 1 blocks are still reachable in loss record 20 of 32
==4162==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162==    by 0x10CD55: malloc_or_fail (report.c:189)
==4162==    by 0x10D7DF: add_cmd (console.c:89)
==4162==    by 0x10C617: console_init (qtest.c:794)
==4162==    by 0x10C617: main (qtest.c:945)
==4162== 
==4162== 32 bytes in 1 blocks are still reachable in loss record 21 of 32
==4162==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162==    by 0x10CD55: malloc_or_fail (report.c:189)
==4162==    by 0x10D7DF: add_cmd (console.c:89)
==4162==    by 0x10C631: console_init (qtest.c:796)
==4162==    by 0x10C631: main (qtest.c:945)
==4162== 
==4162== 40 bytes in 1 blocks are still reachable in loss record 22 of 32
==4162==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162==    by 0x10CD55: malloc_or_fail (report.c:189)
==4162==    by 0x10D859: add_param (console.c:110)
==4162==    by 0x10DC24: init_cmd (console.c:415)
==4162==    by 0x10C4C5: main (qtest.c:944)
==4162== 
==4162== 40 bytes in 1 blocks are still reachable in loss record 23 of 32
==4162==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162==    by 0x10CD55: malloc_or_fail (report.c:189)
==4162==    by 0x10D859: add_param (console.c:110)
==4162==    by 0x10DC43: init_cmd (console.c:416)
==4162==    by 0x10C4C5: main (qtest.c:944)
==4162== 
==4162== 40 bytes in 1 blocks are still reachable in loss record 24 of 32
==4162==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162==    by 0x10CD55: malloc_or_fail (report.c:189)
==4162==    by 0x10D859: add_param (console.c:110)
==4162==    by 0x10DC62: init_cmd (console.c:417)
==4162==    by 0x10C4C5: main (qtest.c:944)
==4162== 
==4162== 40 bytes in 1 blocks are still reachable in loss record 25 of 32
==4162==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162==    by 0x10CD55: malloc_or_fail (report.c:189)
==4162==    by 0x10D859: add_param (console.c:110)
==4162==    by 0x10DC81: init_cmd (console.c:418)
==4162==    by 0x10C4C5: main (qtest.c:944)
==4162== 
==4162== 40 bytes in 1 blocks are still reachable in loss record 26 of 32
==4162==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162==    by 0x10CD55: malloc_or_fail (report.c:189)
==4162==    by 0x10D859: add_param (console.c:110)
==4162==    by 0x10C650: console_init (qtest.c:798)
==4162==    by 0x10C650: main (qtest.c:945)
==4162== 
==4162== 40 bytes in 1 blocks are still reachable in loss record 27 of 32
==4162==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162==    by 0x10CD55: malloc_or_fail (report.c:189)
==4162==    by 0x10D859: add_param (console.c:110)
==4162==    by 0x10C66F: console_init (qtest.c:800)
==4162==    by 0x10C66F: main (qtest.c:945)
==4162== 
==4162== 40 bytes in 1 blocks are still reachable in loss record 28 of 32
==4162==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162==    by 0x10CD55: malloc_or_fail (report.c:189)
==4162==    by 0x10D859: add_param (console.c:110)
==4162==    by 0x10C68E: console_init (qtest.c:802)
==4162==    by 0x10C68E: main (qtest.c:945)
==4162== 
==4162== 52 bytes in 6 blocks are still reachable in loss record 29 of 32
==4162==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162==    by 0x4A4B50E: strdup (strdup.c:42)
==4162==    by 0x110875: linenoiseHistoryAdd (linenoise.c:1236)
==4162==    by 0x10E1CF: run_console (console.c:650)
==4162==    by 0x10C6E0: main (qtest.c:962)
==4162== 
==4162== 104 bytes in 1 blocks are still reachable in loss record 30 of 32
==4162==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162==    by 0x4A4B50E: strdup (strdup.c:42)
==4162==    by 0x110901: linenoiseHistoryAdd (linenoise.c:1236)
==4162==    by 0x10E1CF: run_console (console.c:650)
==4162==    by 0x10C6E0: main (qtest.c:962)
==4162== 
==4162== 160 bytes in 1 blocks are still reachable in loss record 31 of 32
==4162==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162==    by 0x1108C1: linenoiseHistoryAdd (linenoise.c:1224)
==4162==    by 0x10E1CF: run_console (console.c:650)
==4162==    by 0x10C6E0: main (qtest.c:962)
==4162== 
==4162== 8,216 bytes in 1 blocks are still reachable in loss record 32 of 32
==4162==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4162==    by 0x10CD55: malloc_or_fail (report.c:189)
==4162==    by 0x10D3D8: push_file (console.c:439)
==4162==    by 0x10E19B: run_console (console.c:641)
==4162==    by 0x10C6E0: main (qtest.c:962)
==4162==

It is found that q_insert_head() has a problem after reading the test data.
After a few days of trying, it still get the same error. It is found that the test script may also call q_sort a lot, so try to improve the efficiency of q_sort.
Replace memcpy() with strncpy() in q_remove_head() and q_remove_tail().
Finally, the code pass the automatic test. link

+++ TESTING trace trace-17-complexity:
---	trace-17-complexity	5/5
---	TOTAL		100/100
    ▍▃                                  
    ▍▃▅                                 
    ▊╷▘▝             ▂▀▆▍╌▘             
     ╹╷▔▖         ▃▅╷╷▁▗▘            ▁▁ 
     ▝▖│▝▀▅▆▆▅▅▆▆▅╷▁▂▀       ▁▂▃▀▅▀▔▃▔▗ 
      ▍▝▆╷╷╷╷╷╷╷╷╷▝▍    ▂▃▅▆▅╷╷╷╷╷╷╷╷▗  
     ▕┢╷╷╷╷╷╷╷╷▂▂▁▋▝  ▋▔▃▃▃▃▃▃▃▃▃▃▂▂▁▘  
      ▏▗▖▃▅╷╸╷┫┗▘▋▁╷▃▀▆▔╋▍╷╷╷╷╷╷╷╷╷╷▗   
  ▆▅▀▃▎▝▃▘╷▁▂▂▂▖╷▗▔▃▋╷╷╷▗▘╷▂▂▃▀▀▅▅▆▆    
 ▝▖╷╷╷▌▗▖▝▝▗▅▃▃▎╷▝▀▀▘╷╷▗▖╷╷▎            
   ▅▂╷▝▅▘╷╷▝▂▂▗┋╷▀┏▅╷▗▘▁▋╷╷▎            
     ▆▀▂▖▔╷▝╷━▅━╷╷╷▗▃▌▔╊▂▂▃▘            
     ▅▖▁▏╷╷╷╷╷╷╷╷╷╷▝▅▝▀▀▖               
    ▊▆╿▔╷▆╷╷╷╷╷╷╷╷╷╷╷▌▘╷▊               
     ▖╷╷╷╷╷╷╷╷╷╷╷╷╷╷╷▝╺▔                
     ▝▃╷▀▀▃▃▂▁─╷╷╷╷╷╷▋▋                 
        ▆▅▀▀▃▂▁▅▃▁╷╷▁▂▘                 
                ▆▅▀▖━▌                  
                    ▃▊

However, when I profiled the code with Valgrind, the last test still had some problems.

Result

 make && valgrind ./qtest < traces/trace-17-complexity.cmd
  CC	qtest.o
  CC	report.o
  CC	console.o
  CC	harness.o
  CC	queue.o
  CC	random.o
  CC	dudect/constant.o
  CC	dudect/fixture.o
  CC	dudect/ttest.o
  CC	linenoise.o
  LD	qtest
Probably constant time
Probably constant time
Probably constant time
Probably constant time
Freeing queue
==17905== 156 bytes in 7 blocks are still reachable in loss record 1 of 3
==17905==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==17905==    by 0x4A4B50E: strdup (strdup.c:42)
==17905==    by 0x110850: linenoiseHistoryAdd (linenoise.c:1236)
==17905==    by 0x10E1CF: run_console (console.c:650)
==17905==    by 0x10C6E0: main (qtest.c:962)
==17905== 
==17905== 160 bytes in 1 blocks are still reachable in loss record 2 of 3
==17905==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==17905==    by 0x11089C: linenoiseHistoryAdd (linenoise.c:1224)
==17905==    by 0x11146F: linenoiseHistoryLoad (linenoise.c:1325)
==17905==    by 0x10C6B0: main (qtest.c:951)
==17905== 
==17905== 528 bytes in 13 blocks are still reachable in loss record 3 of 3
==17905==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==17905==    by 0x4A4B50E: strdup (strdup.c:42)
==17905==    by 0x110850: linenoiseHistoryAdd (linenoise.c:1236)
==17905==    by 0x11146F: linenoiseHistoryLoad (linenoise.c:1325)
==17905==    by 0x10C6B0: main (qtest.c:951)
==17905==

Fixed the memory error generated during the excution of `q_test()`

After q_test() is excuted, the memory allocated by linenoiseHistoryAdd() or linenoiseHistoryLoad() is not properly released.

$ make && valgrind ./qtest < traces/trace-01-ops.cmd 
make: Nothing to be done for 'all'.
l = []
l = [gerbil]
l = [bear gerbil]
l = [dolphin bear gerbil]
Removed dolphin from queue
l = [bear gerbil]
Removed bear from queue
l = [gerbil]
Removed gerbil from queue
l = []
Freeing queue
==7332== 131 bytes in 11 blocks are still reachable in loss record 1 of 3
==7332==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==7332==    by 0x4A4B50E: strdup (strdup.c:42)
==7332==    by 0x110913: linenoiseHistoryAdd (linenoise.c:1236)
==7332==    by 0x10E292: run_console (console.c:650)
==7332==    by 0x10C7A3: main (qtest.c:987)
==7332== 
==7332== 160 bytes in 1 blocks are still reachable in loss record 2 of 3
==7332==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==7332==    by 0x11095F: linenoiseHistoryAdd (linenoise.c:1224)
==7332==    by 0x111532: linenoiseHistoryLoad (linenoise.c:1325)
==7332==    by 0x10C773: main (qtest.c:976)
==7332== 
==7332== 179 bytes in 9 blocks are still reachable in loss record 3 of 3
==7332==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==7332==    by 0x4A4B50E: strdup (strdup.c:42)
==7332==    by 0x110913: linenoiseHistoryAdd (linenoise.c:1236)
==7332==    by 0x111532: linenoiseHistoryLoad (linenoise.c:1325)
==7332==    by 0x10C773: main (qtest.c:976)
==7332==

The function linenoiseHistoryAdd() will called by run_console() and linenoiseHistoryLoad().
In linenoiseHistoryAdd(), the program will allocate memory for a global variable static char **history = NULL.

int linenoiseHistoryAdd(const char *line)
{
    char *linecopy;

    if (history_max_len == 0)
        return 0;

    /* Initialization on first call. */
    if (history == NULL) {
        history = malloc(sizeof(char *) * history_max_len);
    ...
}

And there is a funtion named freeHistory() will called by linenoiseAtExit().
The function linenoiseAtExit() may be registered by enableRawMode().
The function enableRawMode() may be called by linenoiseRaw().
The function linenoiseRaw() may be called by linenoise().
The only place where it is possible to call linenoise() is run_console().

bool run_console(char *infile_name)
{
    if (!push_file(infile_name)) {
        report(1, "ERROR: Could not open source file '%s'", infile_name);
        return false;
    }


    if (!has_infile) {
        char *cmdline;
        while ((cmdline = linenoise(prompt)) != NULL) {
    ...
}

If has_infile is true, run_console() will not call linenoise(), so linenoiseAtExit() will not be registered.
Try to add function to register linenoiseAtExit() if has_infile is true. Since the global variable atexit_registered can not be used out of linenoise.c, so it need to create a new function.

void addHistoryFree()
{
    if (!atexit_registered) {
        atexit(linenoiseAtExit);
        atexit_registered = 1;
    }
}

Try to add the new function.

bool run_console(char *infile_name)
{
    ...
    if (!has_infile) {
        ...
    } else {
        addHistoreyFree();
        while (!cmd_done())
            cmd_select(0, NULL, NULL, NULL, NULL);
    }
    ...
}

But it failed. Then I found there may also be cases in linenoise() with out registering linenoiseAtExit().
So I try to call addHistoryFree() whether has_infile is true or not.

bool run_console(char *infile_name)
{
    ...
    addHistoryFree();

    if (!has_infile) {
        ...
    } else {
        while (!cmd_done())
            cmd_select(0, NULL, NULL, NULL, NULL);
    }
    ...
}

And it work, after q_test is excuted, there has no error message.

$ make && valgrind ./qtest < traces/trace-01-ops.cmd
  CC	console.o
  CC	linenoise.o
  LD	qtest
l = []
l = [gerbil]
l = [bear gerbil]
l = [dolphin bear gerbil]
Removed dolphin from queue
l = [bear gerbil]
Removed bear from queue
l = [gerbil]
Removed gerbil from queue
l = []
Freeing queue

But there will still be an error at the end of the last test.

Last Test

 make && valgrind ./qtest < traces/trace-17-complexity.cmd 
make: Nothing to be done for 'all'.
Probably constant time
Probably constant time
Probably constant time
Probably constant time
==11358== 32 bytes in 1 blocks are still reachable in loss record 1 of 30
==11358==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358==    by 0x10CE18: malloc_or_fail (report.c:189)
==11358==    by 0x10D8A2: add_cmd (console.c:89)
==11358==    by 0x10DC2C: init_cmd (console.c:408)
==11358==    by 0x10C56E: main (qtest.c:969)
==11358== 
==11358== 32 bytes in 1 blocks are still reachable in loss record 2 of 30
==11358==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358==    by 0x10CE18: malloc_or_fail (report.c:189)
==11358==    by 0x10D8A2: add_cmd (console.c:89)
==11358==    by 0x10DC46: init_cmd (console.c:409)
==11358==    by 0x10C56E: main (qtest.c:969)
==11358== 
==11358== 32 bytes in 1 blocks are still reachable in loss record 3 of 30
==11358==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358==    by 0x10CE18: malloc_or_fail (report.c:189)
==11358==    by 0x10D8A2: add_cmd (console.c:89)
==11358==    by 0x10DC60: init_cmd (console.c:410)
==11358==    by 0x10C56E: main (qtest.c:969)
==11358== 
==11358== 32 bytes in 1 blocks are still reachable in loss record 4 of 30
==11358==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358==    by 0x10CE18: malloc_or_fail (report.c:189)
==11358==    by 0x10D8A2: add_cmd (console.c:89)
==11358==    by 0x10DC7A: init_cmd (console.c:411)
==11358==    by 0x10C56E: main (qtest.c:969)
==11358== 
==11358== 32 bytes in 1 blocks are still reachable in loss record 5 of 30
==11358==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358==    by 0x10CE18: malloc_or_fail (report.c:189)
==11358==    by 0x10D8A2: add_cmd (console.c:89)
==11358==    by 0x10DC94: init_cmd (console.c:412)
==11358==    by 0x10C56E: main (qtest.c:969)
==11358== 
==11358== 32 bytes in 1 blocks are still reachable in loss record 6 of 30
==11358==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358==    by 0x10CE18: malloc_or_fail (report.c:189)
==11358==    by 0x10D8A2: add_cmd (console.c:89)
==11358==    by 0x10DCAE: init_cmd (console.c:413)
==11358==    by 0x10C56E: main (qtest.c:969)
==11358== 
==11358== 32 bytes in 1 blocks are still reachable in loss record 7 of 30
==11358==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358==    by 0x10CE18: malloc_or_fail (report.c:189)
==11358==    by 0x10D8A2: add_cmd (console.c:89)
==11358==    by 0x10DCC8: init_cmd (console.c:414)
==11358==    by 0x10C56E: main (qtest.c:969)
==11358== 
==11358== 32 bytes in 1 blocks are still reachable in loss record 8 of 30
==11358==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358==    by 0x10CE18: malloc_or_fail (report.c:189)
==11358==    by 0x10D8A2: add_cmd (console.c:89)
==11358==    by 0x10C588: console_init (qtest.c:791)
==11358==    by 0x10C588: main (qtest.c:970)
==11358== 
==11358== 32 bytes in 1 blocks are still reachable in loss record 9 of 30
==11358==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358==    by 0x10CE18: malloc_or_fail (report.c:189)
==11358==    by 0x10D8A2: add_cmd (console.c:89)
==11358==    by 0x10C5A2: console_init (qtest.c:792)
==11358==    by 0x10C5A2: main (qtest.c:970)
==11358== 
==11358== 32 bytes in 1 blocks are still reachable in loss record 10 of 30
==11358==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358==    by 0x10CE18: malloc_or_fail (report.c:189)
==11358==    by 0x10D8A2: add_cmd (console.c:89)
==11358==    by 0x10C5BC: console_init (qtest.c:793)
==11358==    by 0x10C5BC: main (qtest.c:970)
==11358== 
==11358== 32 bytes in 1 blocks are still reachable in loss record 11 of 30
==11358==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358==    by 0x10CE18: malloc_or_fail (report.c:189)
==11358==    by 0x10D8A2: add_cmd (console.c:89)
==11358==    by 0x10C5D6: console_init (qtest.c:797)
==11358==    by 0x10C5D6: main (qtest.c:970)
==11358== 
==11358== 32 bytes in 1 blocks are still reachable in loss record 12 of 30
==11358==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358==    by 0x10CE18: malloc_or_fail (report.c:189)
==11358==    by 0x10D8A2: add_cmd (console.c:89)
==11358==    by 0x10C5F0: console_init (qtest.c:801)
==11358==    by 0x10C5F0: main (qtest.c:970)
==11358== 
==11358== 32 bytes in 1 blocks are still reachable in loss record 13 of 30
==11358==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358==    by 0x10CE18: malloc_or_fail (report.c:189)
==11358==    by 0x10D8A2: add_cmd (console.c:89)
==11358==    by 0x10C60A: console_init (qtest.c:805)
==11358==    by 0x10C60A: main (qtest.c:970)
==11358== 
==11358== 32 bytes in 1 blocks are still reachable in loss record 14 of 30
==11358==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358==    by 0x10CE18: malloc_or_fail (report.c:189)
==11358==    by 0x10D8A2: add_cmd (console.c:89)
==11358==    by 0x10C624: console_init (qtest.c:809)
==11358==    by 0x10C624: main (qtest.c:970)
==11358== 
==11358== 32 bytes in 1 blocks are still reachable in loss record 15 of 30
==11358==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358==    by 0x10CE18: malloc_or_fail (report.c:189)
==11358==    by 0x10D8A2: add_cmd (console.c:89)
==11358==    by 0x10C63E: console_init (qtest.c:812)
==11358==    by 0x10C63E: main (qtest.c:970)
==11358== 
==11358== 32 bytes in 1 blocks are still reachable in loss record 16 of 30
==11358==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358==    by 0x10CE18: malloc_or_fail (report.c:189)
==11358==    by 0x10D8A2: add_cmd (console.c:89)
==11358==    by 0x10C658: console_init (qtest.c:813)
==11358==    by 0x10C658: main (qtest.c:970)
==11358== 
==11358== 32 bytes in 1 blocks are still reachable in loss record 17 of 30
==11358==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358==    by 0x10CE18: malloc_or_fail (report.c:189)
==11358==    by 0x10D8A2: add_cmd (console.c:89)
==11358==    by 0x10C672: console_init (qtest.c:814)
==11358==    by 0x10C672: main (qtest.c:970)
==11358== 
==11358== 32 bytes in 1 blocks are still reachable in loss record 18 of 30
==11358==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358==    by 0x10CE18: malloc_or_fail (report.c:189)
==11358==    by 0x10D8A2: add_cmd (console.c:89)
==11358==    by 0x10C68C: console_init (qtest.c:816)
==11358==    by 0x10C68C: main (qtest.c:970)
==11358== 
==11358== 32 bytes in 1 blocks are still reachable in loss record 19 of 30
==11358==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358==    by 0x10CE18: malloc_or_fail (report.c:189)
==11358==    by 0x10D8A2: add_cmd (console.c:89)
==11358==    by 0x10C6A6: console_init (qtest.c:817)
==11358==    by 0x10C6A6: main (qtest.c:970)
==11358== 
==11358== 32 bytes in 1 blocks are still reachable in loss record 20 of 30
==11358==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358==    by 0x10CE18: malloc_or_fail (report.c:189)
==11358==    by 0x10D8A2: add_cmd (console.c:89)
==11358==    by 0x10C6C0: console_init (qtest.c:818)
==11358==    by 0x10C6C0: main (qtest.c:970)
==11358== 
==11358== 32 bytes in 1 blocks are still reachable in loss record 21 of 30
==11358==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358==    by 0x10CE18: malloc_or_fail (report.c:189)
==11358==    by 0x10D8A2: add_cmd (console.c:89)
==11358==    by 0x10C6DA: console_init (qtest.c:820)
==11358==    by 0x10C6DA: main (qtest.c:970)
==11358== 
==11358== 32 bytes in 1 blocks are still reachable in loss record 22 of 30
==11358==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358==    by 0x10CE18: malloc_or_fail (report.c:189)
==11358==    by 0x10D8A2: add_cmd (console.c:89)
==11358==    by 0x10C6F4: console_init (qtest.c:822)
==11358==    by 0x10C6F4: main (qtest.c:970)
==11358== 
==11358== 40 bytes in 1 blocks are still reachable in loss record 23 of 30
==11358==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358==    by 0x10CE18: malloc_or_fail (report.c:189)
==11358==    by 0x10D91C: add_param (console.c:110)
==11358==    by 0x10DCE7: init_cmd (console.c:415)
==11358==    by 0x10C56E: main (qtest.c:969)
==11358== 
==11358== 40 bytes in 1 blocks are still reachable in loss record 24 of 30
==11358==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358==    by 0x10CE18: malloc_or_fail (report.c:189)
==11358==    by 0x10D91C: add_param (console.c:110)
==11358==    by 0x10DD06: init_cmd (console.c:416)
==11358==    by 0x10C56E: main (qtest.c:969)
==11358== 
==11358== 40 bytes in 1 blocks are still reachable in loss record 25 of 30
==11358==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358==    by 0x10CE18: malloc_or_fail (report.c:189)
==11358==    by 0x10D91C: add_param (console.c:110)
==11358==    by 0x10DD25: init_cmd (console.c:417)
==11358==    by 0x10C56E: main (qtest.c:969)
==11358== 
==11358== 40 bytes in 1 blocks are still reachable in loss record 26 of 30
==11358==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358==    by 0x10CE18: malloc_or_fail (report.c:189)
==11358==    by 0x10D91C: add_param (console.c:110)
==11358==    by 0x10DD44: init_cmd (console.c:418)
==11358==    by 0x10C56E: main (qtest.c:969)
==11358== 
==11358== 40 bytes in 1 blocks are still reachable in loss record 27 of 30
==11358==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358==    by 0x10CE18: malloc_or_fail (report.c:189)
==11358==    by 0x10D91C: add_param (console.c:110)
==11358==    by 0x10C713: console_init (qtest.c:824)
==11358==    by 0x10C713: main (qtest.c:970)
==11358== 
==11358== 40 bytes in 1 blocks are still reachable in loss record 28 of 30
==11358==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358==    by 0x10CE18: malloc_or_fail (report.c:189)
==11358==    by 0x10D91C: add_param (console.c:110)
==11358==    by 0x10C732: console_init (qtest.c:826)
==11358==    by 0x10C732: main (qtest.c:970)
==11358== 
==11358== 40 bytes in 1 blocks are still reachable in loss record 29 of 30
==11358==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358==    by 0x10CE18: malloc_or_fail (report.c:189)
==11358==    by 0x10D91C: add_param (console.c:110)
==11358==    by 0x10C751: console_init (qtest.c:828)
==11358==    by 0x10C751: main (qtest.c:970)
==11358== 
==11358== 8,216 bytes in 1 blocks are still reachable in loss record 30 of 30
==11358==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11358==    by 0x10CE18: malloc_or_fail (report.c:189)
==11358==    by 0x10D49B: push_file (console.c:439)
==11358==    by 0x10E25E: run_console (console.c:641)
==11358==    by 0x10C7A3: main (qtest.c:987)
==11358==

After tracing the code, it found that in init_cmd() will allocate memory space for cmd_list.
There is a function named finish_cmd() that will call do_quit() to free the momory of cmd_list().
Refer to AmyLin's note, the main function of q_test may not call the finish_cmd() if the ok is false.
So modify a line in main of q_test.

# replace this line
ok = ok && finish_cmd();

# with
ok = finish_cmd() && ok;

2022q1 Homework1 (lab0)

Test Environment

Implement Progress Records

q_new

q_free

q_insert_head

q_insert_tail

q_remove_head

q_remove_tail

q_size

q_delete_mid

q_delete_dup

q_swap

q_reverse

q_sort

q_shuffle

Improve the Code Progress Records

Problems to be solved

Fixed the memory error generated during the excution of q_test()

Fixed the memory error generated during the excution of `q_test()`