2024q1 Homework1 (lab0)

contributed by < Randy-Chuang >

詳閱作業規範。留意各式細節，唯有重視小處並步步為營，方可挑戰原始程式碼規模超越三千七百萬行的 Linux 核心

開發環境

$ gcc --version 
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
Copyright (C) 2021 Free Software Foundation, Inc. 

$ 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):                  16
  On-line CPU(s) list:   0-15
Vendor ID:               GenuineIntel
  Model name:            13th Gen Intel(R) Core(TM) i7-1360P
    CPU family:          6
    Model:               186
    Thread(s) per core:  2
    Core(s) per socket:  12
    Socket(s):           1
    Stepping:            2
    CPU max MHz:         5000.0000
    CPU min MHz:         400.0000
    BogoMIPS:            3225.60

指定的佇列操作

執行結果

不該列出完整的執行結果，只要摘錄你認為值得討論的部分即可。

說好的進度呢？

Temp

$ gitk  include/linux/list.h
0ad42352c01788e41a33336577fdd270d8de55bb 

在做 q_descend, q_ascend 因為功能要求是與右邊節點相比，因此以反向順序檢查處理，從 Linux kernel 專案搜尋，發現在 2006 年就有上反向走訪的 patch，但是作業專案中的 list.h 並未提供。

遇到問題

CppCheck 有檢查提示 is always true/false 、uninitialized 的警告訊息，我覺得很有可能分析的是未經過前處理展開 Macro 後的程式碼。這部份還需要確認相關文件或是簡報。

看還能不能刪減

int q_merge(struct list_head *head, bool descend)
{
    // https://leetcode.com/problems/merge-k-sorted-lists/
    int cnt = 0, remain;
    queue_contex_t *ptr;
    struct list_head sorted;
    INIT_LIST_HEAD(&sorted);
    do {
        remain = 0;
        queue_contex_t *q_target = NULL;
        element_t *e_target = NULL;

        list_for_each_entry (ptr, head, chain) {
            if (list_empty(ptr->q))
                continue;

            remain += ptr->size;
            element_t *element = list_first_entry(ptr->q, element_t, list);

            if (e_target == NULL ||
                (descend ? (strcmp(element->value, e_target->value) > 0)
                         : (strcmp(element->value, e_target->value) < 0))) {
                e_target = element;
                q_target = ptr;
            }
        }

        /// doing merge
        if (e_target != NULL) {
            list_del(&e_target->list);
            list_add_tail(&e_target->list, &sorted);
            --q_target->size;
            ++cnt;
        }
    } while (remain != 0);

    if (!list_empty(&sorted)) {
        ptr = list_first_entry(head, queue_contex_t, chain);
        list_splice(&sorted, ptr->q);
        ptr->size = cnt;
    }

    return cnt;
}

Following files need to be cleaned up:
queue.c
queue.c:353:26: style: Condition 'e_target==NULL' is always true [knownConditionTrueFalse]
            if (e_target == NULL ||
                         ^
queue.c:344:31: note: Assignment 'e_target=NULL', assigned value is 0
        element_t *e_target = NULL;
                              ^
queue.c:347:27: note: Assuming condition is false
            if (list_empty(ptr->q))
                          ^
queue.c:353:26: note: Condition 'e_target==NULL' is always true
            if (e_target == NULL ||
                         ^
queue.c:347:33: error: Uninitialized variable: ptr->q [uninitvar]
            if (list_empty(ptr->q))
                                ^

Fail to pass static analysis.