2025q1 Homework1 (lab0)

$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
Copyright (C) 2023 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ lscpu
Architecture:             x86_64
  CPU op-mode(s):         32-bit, 64-bit
  Address sizes:          39 bits physical, 48 bits virtual
  Byte Order:             Little Endian
CPU(s):                   12
  On-line CPU(s) list:    0-11
Vendor ID:                GenuineIntel
  Model name:             Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
    CPU family:           6
    Model:                158
    Thread(s) per core:   2
    Core(s) per socket:   6
    Socket(s):            1
    Stepping:             10
    BogoMIPS:             5184.01

/* Create an empty queue */
struct list_head *q_new()
{
    struct queue_info *q = malloc(sizeof(struct queue_info));
    if (!q)
        return NULL;
    INIT_LIST_HEAD(&q->head);
    q->size = 0;
    return &q->head;
}

/* Free all storage used by queue */
void q_free(struct list_head *head)
{
    if (!head)
        return;

    struct queue_info *q = container_of(head, struct queue_info, head);
    struct list_head *pos, *tmp;
    list_for_each_safe (pos, tmp, head) {
        element_t *entry = list_entry(pos, element_t, list);
        free(entry->value);
        free(entry);
    }
    free(q);
}

/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
    if (!head || !s)
        return false;

    struct queue_info *q = container_of(head, struct queue_info, head);
    element_t *new = malloc(sizeof(element_t));
    if (!new)
        return false;

    new->value = strdup(s);
    if (!new->value) {
        free(new);
        return false;
    }

    list_add(&new->list, head);
    q->size++;
    return true;
}

/* Insert an element at tail of queue */
bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head || !s)
        return false;

    struct queue_info *q = container_of(head, struct queue_info, head);
    element_t *new = malloc(sizeof(element_t));
    if (!new)
        return false;

    new->value = strdup(s);
    if (!new->value) {
        free(new);
        return false;
    }

    list_add_tail(&new->list, head);
    q->size++;
    return true;
}

/* Remove an element from head of queue */
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    struct queue_info *q = container_of(head, struct queue_info, head);
    if (!head || list_empty(head))
        return NULL;

    element_t *item = list_first_entry(head, element_t, list);
    if (sp && bufsize > 0) {
        strncpy(sp, item->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    list_del(&item->list);
    q->size--;
    return item;
}

/* Remove an element from tail of queue */
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    struct queue_info *q = container_of(head, struct queue_info, head);
    if (!head || list_empty(head))
        return NULL;

    element_t *item = list_last_entry(head, element_t, list);
    if (sp && bufsize > 0) {
        strncpy(sp, item->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    list_del(&item->list);
    q->size--;
    return item;
}

/* Return number of elements in queue */
int q_size(struct list_head *head)
{
    if (!head)
        return 0;
    const struct queue_info *q = container_of(head, struct queue_info, head);
    return q->size;
}

/* Delete the middle node in queue */
bool q_delete_mid(struct list_head *head)
{
    struct queue_info *q = container_of(head, struct queue_info, head);
    if (!head || list_empty(head))
        return false;

    struct list_head *slow = head->next;
    struct list_head *fast = head->next;

    while (fast != head && fast->next != head) {
        slow = slow->next;
        fast = fast->next->next;
    }

    element_t *mid = list_entry(slow, element_t, list);
    list_del(slow);
    free(mid->value);
    free(mid);
    q->size--;
    return true;
}

/* Delete all nodes that have duplicate string */
bool q_delete_dup(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head)) {
        return false;
    }

    element_t *curr = NULL, *next = NULL;
    bool check = false;
    list_for_each_entry_safe (curr, next, head, list) {
        if (&next->list != head && !strcmp(curr->value, next->value)) {
            list_del_init(&curr->list);
            q_release_element(curr);
            check = true;
        } else if (check) {
            list_del_init(&curr->list);
            q_release_element(curr);
            check = false;
        }
    }
    return true;
}

/* Swap every two adjacent nodes */
void q_swap(struct list_head *head)
{
    if (!head || list_empty(head))
        return;

    struct list_head *node;
    list_for_each (node, head) {
        if (node->next == head)
            break;
        list_move(node, node->next);
    }
}

 /* Reverse elements in queue */
void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head))
        return;

    struct list_head *current = head, *prev = head->prev, *next = NULL;
    do {
        next = current->next;
        current->next = prev;
        current->prev = next;
        prev = current;
        current = next;
    } while (current != head);
}

 /* Reverse the nodes of the list k at a time */
void q_reverseK(struct list_head *head, int k)
{
    if (!head || list_empty(head) || k <= 1)
        return;

    struct list_head *current = head->next, *prev = head;

    while (current != head) {
        struct list_head *start = prev->next;
        int count = 0;  // Move count declaration inside the loop
        while (count < k && current != head) {
            current = current->next;
            count++;
        }
        if (count == k) {
            struct list_head *end = current->prev;
            struct list_head *p = start, *n, *tmp;
            while (p != current) {
                n = p->next;
                tmp = p->prev;
                p->prev = p->next;
                p->next = tmp;
                p = n;
            }
            prev->next = end;
            end->prev = prev;
            start->next = current;
            current->prev = start;
            prev = start;
        }
    }
}

/* Sort elements of queue in ascending/descending order */
struct list_head *merge(struct list_head *left,
                        struct list_head *right,
                        bool descend)
{
    struct list_head dummy;
    INIT_LIST_HEAD(&dummy);
    struct list_head *tail = &dummy;

    while (left && right) {
        const element_t *l = list_entry(left, element_t, list);
        const element_t *r = list_entry(right, element_t, list);
        if ((strcmp(l->value, r->value) <= 0) ^ descend) {
            tail->next = left;
            left->prev = tail;
            left = left->next;
        } else {
            tail->next = right;
            right->prev = tail;
            right = right->next;
        }
        tail = tail->next;
    }

    tail->next = left ? left : right;
    if (tail->next)
        tail->next->prev = tail;

    return dummy.next;
}

/* Sort elements of queue in ascending/descending order */
struct list_head *merge_sort(struct list_head *head, bool descend)
{
    if (!head || !head->next)
        return head;

    struct list_head *slow = head, *fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    struct list_head *mid = slow->next;
    slow->next = NULL;

    struct list_head *left = merge_sort(head, descend);
    struct list_head *right = merge_sort(mid, descend);

    return merge(left, right, descend);
}

void q_sort(struct list_head *head, bool descend)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    struct list_head *first = head->next;
    struct list_head *last = head->prev;

    last->next = NULL;
    first->prev = NULL;

    struct list_head *sorted = merge_sort(first, descend);

    head->next = sorted;
    sorted->prev = head;

    struct list_head *tail = sorted;
    while (tail->next)
        tail = tail->next;
    tail->next = head;
    head->prev = tail;
}

 /* Remove every node which has a node with a strictly less value anywhere to
 * the right side of it */
int q_ascend(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;

    struct list_head *cur = head->prev;
    const element_t *cur_e = list_entry(cur, element_t, list);
    while (cur != head) {
        struct list_head *prev = cur->prev;
        if (prev == head)
            break;
        element_t *prev_e = list_entry(prev, element_t, list);
        if (strcmp(prev_e->value, cur_e->value) > 0) {
            list_del(prev);
            free(prev_e->value);
            free(prev_e);
            struct queue_info *q = container_of(head, struct queue_info, head);
            q->size--;
        } else {
            cur = prev;
            cur_e = prev_e;
        }
    }

    return q_size(head);
}

 /* Remove every node which has a node with a strictly greater value anywhere to
 * the right side of it */
int q_descend(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;

    struct list_head *cur = head->prev;
    const element_t *cur_e = list_entry(cur, element_t, list);
    while (cur != head) {
        struct list_head *prev = cur->prev;
        if (prev == head)
            break;
        element_t *prev_e = list_entry(prev, element_t, list);
        if (strcmp(prev_e->value, cur_e->value) < 0) {
            list_del(prev);
            free(prev_e->value);
            free(prev_e);
            struct queue_info *q = container_of(head, struct queue_info, head);
            q->size--;
        } else {
            cur = prev;
            cur_e = prev_e;
        }
    }

    return q_size(head);
}

 /* Merge all the queues into one sorted queue, which is in ascending/descending
 * order */
int q_merge(struct list_head *head, bool descend)
{
    if (!head || list_empty(head))
        return 0;

    queue_contex_t *first = list_entry(head->next, queue_contex_t, chain);
    struct list_head *cur, *safe;
    list_for_each_safe (cur, safe, head) {
        if (cur == head->next)
            continue;
        queue_contex_t *ctx = list_entry(cur, queue_contex_t, chain);
        list_splice_init(ctx->q, first->q);
    }

    q_sort(first->q, descend);

    return q_size(first->q);
}

t = (x̄₁ - x̄₂) / sqrt(s₁²/n₁ + s₂²/n₂)

​​​// 對測量數據進行排序
​​​qsort(measurements, num_measurements, sizeof(double), compare_doubles);
​​​
​​​// 根據百分位數裁剪數據
​​​int cutoff_index = (int)(percentile * num_measurements / 100.0);
​​​int valid_measurements = num_measurements - cutoff_index;
​​​
​​​// 只使用未被裁剪的數據進行統計分析
​​​double *valid_data = measurements + cutoff_index;

tyler@tyler:~/lab0-c$ make valgrind
# Explicitly disable sanitizer(s)
make clean SANITIZER=0 qtest
make[1]: Entering directory '/home/tyler/lab0-c'
rm -f qtest.o report.o console.o harness.o queue.o random.o dudect/constant.o dudect/fixture.o dudect/ttest.o shannon_entropy.o linenoise.o web.o .qtest.o.d .report.o.d .console.o.d .harness.o.d .queue.o.d .random.o.d .dudect/constant.o.d .dudect/fixture.o.d .dudect/ttest.o.d .shannon_entropy.o.d .linenoise.o.d .web.o.d *~ qtest /tmp/qtest.*
rm -rf .dudect
rm -rf *.dSYM
(cd traces; rm -f *~)
  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    shannon_entropy.o
  CC    linenoise.o
  CC    web.o
  LD    qtest
make[1]: Leaving directory '/home/tyler/lab0-c'
cp qtest /tmp/qtest.UMIOyd
chmod u+x /tmp/qtest.UMIOyd
sed -i "s/alarm/isnan/g" /tmp/qtest.UMIOyd
scripts/driver.py -p /tmp/qtest.UMIOyd --valgrind 
---     Trace           Points
+++ TESTING trace trace-01-ops:
# Test of 'q_new', 'q_insert_head', and 'q_remove_head'
---     trace-01-ops    5/5
+++ TESTING trace trace-02-ops:
# Test of 'q_new', 'q_insert_head', 'q_insert_tail', 'q_remove_head', 'q_remove_tail', and 'q_delete_mid'
---     trace-02-ops    6/6
+++ TESTING trace trace-03-ops:
# Test of 'q_new', 'q_insert_head', 'q_remove_head', 'q_reverse', 'q_sort', and 'q_merge'
---     trace-03-ops    6/6
+++ TESTING trace trace-04-ops:
# Test of 'q_new', 'q_insert_tail', 'q_insert_head', 'q_remove_head', 'q_size', 'q_swap', and 'q_sort'
---     trace-04-ops    6/6
+++ TESTING trace trace-05-ops:
# Test of 'q_new', 'q_free', 'q_insert_head', 'q_insert_tail', 'q_remove_head', 'q_reverse', 'q_size', 'q_swap', and 'q_sort'
---     trace-05-ops    6/6
+++ TESTING trace trace-06-ops:
# Test of 'q_new', 'q_free', 'q_insert_head', 'q_insert_tail', 'q_remove_head', 'q_delete_dup', 'q_sort', 'q_descend', and 'q_reverseK'
---     trace-06-ops    6/6
+++ TESTING trace trace-07-string:
# Test of truncated strings: 'q_new', 'q_free', 'q_insert_head', 'q_insert_tail', 'q_remove_head', 'q_reverse', and 'q_sort'
---     trace-07-string 6/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue: 'q_new', 'q_remove_head', 'q_reverse', 'q_size', and 'q_sort'
---     trace-08-robust 6/6
+++ TESTING trace trace-09-robust:
# Test 'q_remove_head' with NULL argument: 'q_new', 'q_insert_head', and 'q_remove_head'
---     trace-09-robust 6/6
+++ TESTING trace trace-10-robust:
# Test operations on NULL queue: 'q_free', 'q_insert_head', 'q_insert_tail', 'q_remove_head', 'q_reverse', 'q_size', and 'q_sort'
---     trace-10-robust 6/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on 'q_insert_head': 'q_new', and 'q_insert_head'
---     trace-11-malloc 6/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on 'q_insert_tail': 'q_new', 'q_insert_head', and 'q_insert_tail'
---     trace-12-malloc 6/6
+++ TESTING trace trace-13-malloc:
# Test of malloc failure on 'q_new': 'q_new'
---     trace-13-malloc 6/6
+++ TESTING trace trace-14-perf:
# Test performance of 'q_new', 'q_insert_head', 'q_insert_tail', 'q_reverse', and 'q_sort'
Warning: Skip checking the stability of the sort because the number of elements 2000000 is too large, exceeds the limit 100000.
---     trace-14-perf   6/6
+++ TESTING trace trace-15-perf:
# Test performance of 'q_sort' with random and descending orders: 'q_new', 'q_free', 'q_insert_head', 'q_sort', and 'q_reverse'
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
---     trace-15-perf   6/6
+++ TESTING trace trace-16-perf:
# Test performance of 'q_new', 'q_insert_head', 'q_insert_tail', and 'q_reverse'
---     trace-16-perf   6/6
+++ 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
Testing insert_tail...(5/10)
Probably constant time
Probably constant time
Probably constant time
Probably constant time
---     trace-17-complexity     5/5
---     TOTAL           100/100

Test with specific case by running command:
scripts/driver.py -p /tmp/qtest.UMIOyd --valgrind -t <tid>

+++ TESTING trace trace-14-perf:
# Test performance of 'q_new', 'q_insert_head', 'q_insert_tail', 'q_reverse', and 'q_sort'
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
ERROR: Insertion of dolphin failed (1 failures total)
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
ERROR: Insertion of gerbil failed (2 failures total)
Warning: Skip checking the stability of the sort because the number of elements 1749161 is too large, exceeds the limit 100000.
---     trace-14-perf   0/6

+++ TESTING trace trace-16-perf:
# Test performance of 'q_new', 'q_insert_head', 'q_insert_tail', and 'q_reverse'
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
ERROR: Insertion of dolphin failed (1 failures total)
ERROR: Freed queue, but 1 blocks are still allocated
---     trace-16-perf   0/6