2024q1 Homework1 (lab0)

contributed by < zack-404 >

開發環境

❯ gcc --version
gcc (Debian 10.2.1-6) 10.2.1 20210110
Copyright (C) 2020 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.

❯ cppcheck --version
Cppcheck 2.3

❯ lscpu
Architecture:                    aarch64
CPU op-mode(s):                  32-bit, 64-bit
Byte Order:                      Little Endian
CPU(s):                          4
On-line CPU(s) list:             0-3
Thread(s) per core:              1
Core(s) per socket:              4
Socket(s):                       1
Vendor ID:                       ARM
Model:                           3
Model name:                      Cortex-A72
Stepping:                        r0p3
CPU max MHz:                     1800.0000
CPU min MHz:                     600.0000
BogoMIPS:                        108.00
L1d cache:                       128 KiB
L1i cache:                       192 KiB
L2 cache:                        1 MiB

以樹莓派藉由遠端控制進行此項作業唯一一個問題就是無法直接以提交所寫的程式碼至 Github ，目前尚未有 raspian 版本的 git-credential-manager 。目前以使用樹莓派進行測試，再藉由 Macbook Air 進行提交的動作。

工欲善其事，必先…

背景知識

佇列（唸作：ㄓㄨˋ）

佇列為一種先進先出的資料結構，此次實作注重其與鏈結串列的關係。

inline 對函式效能的影響

在參閱 25077757 與 nosba0957 的程式碼時，發現 25077757 在諸多函式加入了 static 與 inline 兩個關鍵字。

static 關鍵字在 C 語言

If the declaration of a file scope identifier for an object or a function contains the storageclass specifier static, the identifier has internal linkage.(22) (C99 6.2.2)

(22) A function declaration can contain the storage-class specifier static only if it is at file scope; see 6.7.1. (C99 6.2.2)

In addition to optional type qualifiers and the keyword static, the [ and ] may delimit an expression or *. If they delimit an expression (which specifies the size of an array), the expression shall have an integer type. If the expression is a constant expression, it shall have a value greater than zero. The element type shall not be an incomplete or function
type. The optional type qualifiers and the keyword static shall appear only in a declaration of a function parameter with an array type, and then only in the outermost array type derivation (C99 6.7.5.2)

查閱 C 語言規格書，不要把自己的專業前途交給你沒有注入資本的大語言模型。

[工程師應知道的0x10個問題(6): Static的用法 MuLong PuYang](https://medium.com/@racktar7743/%E5%B7%A5%E7%A8%8B%E5%B8%AB%E6%87%89%E7%9F%A5%E9%81%93%E7%9A%840x10%E5%80%8B%E5%95%8F%E9%A1%8C-6-static%E7%9A%84%E7%94%A8%E6%B3%95-d391dacb28a3)

優先閱讀權威材料！

inline

A function declared with an inline function specifier is an inline function. The
function specifier may appear more than once; the behavior is the same as if it appeared
only once. Making a function an inline function suggests that calls to the function be as
fast as possible.(118) The extent to which such suggestions are effective is
implementation-defined.(119) (C99 6.7.4.5)

Any function with internal linkage can be an inline function. For a function with external
linkage, the following restrictions apply: If a function is declared with an inline function specifier, then it shall also be defined in the same translation unit. If all of the
file scope declarations for a function in a translation unit include the inline function
specifier without extern, then the definition in that translation unit is an inline
definition. An inline definition does not provide an external definition for the function,
and does not forbid an external definition in another translation unit. An inline definition
provides an alternative to an external definition, which a translator may use to implement
any call to the function in the same translation unit. It is unspecified whether a call to the
function uses the inline definition or the external definition.120) (C99 6.7.4.5)

了解 elememt_t 與 queue_contest_t

/**
 * struct list_head - Head and node of a doubly-linked list
 * @prev: pointer to the previous node in the list
 * @next: pointer to the next node in the list
 *
 * The simple doubly-linked list consists of a head and nodes attached to
 * this head. Both node and head share the same struct type. The list_*
 * functions and macros can be used to access and modify this data structure.
 *
 * The @prev pointer of the list head points to the last list node of the
 * list and @next points to the first list node of the list. For an empty list,
 * both member variables point to the head.
 *
 * The list nodes are usually embedded in a container structure which holds the
 * actual data. Such container structure is called entry. The helper list_entry
 * can be used to calculate the structure address from the address of the node.
 */
struct list_head {
    struct list_head *prev;
    struct list_head *next;
};

由上述程式碼與註解可知， list_head 提供一個雙向鏈結串列的單元結構。

/**
 * element_t - Linked list element
 * @value: pointer to array holding string
 * @list: node of a doubly-linked list
 *
 * @value needs to be explicitly allocated and freed
 */
typedef struct {
    char *value;
    struct list_head list;
} element_t;

/**
 * queue_contex_t - The context managing a chain of queues
 * @q: pointer to the head of the queue
 * @chain: used by chaining the heads of queues
 * @size: the length of this queue
 * @id: the unique identification number
 */
typedef struct {
    struct list_head *q;
    struct list_head chain;
    int size;
    int id;
} queue_contex_t;

element_t 中的 *value 則是在記錄該結點的值，而 list 則是記錄串列中相鄰的兩個節點。

而queue_context_t 與 element_t 不同的地方在於它可以記錄的不單單是一個節點，而可以是串列中的一個子串列。 size 與 id 則分別紀錄此子串列的大小與 id。

針對佇列的操作

q_new

q_free

此函式目標為清除佇列上所有的節點。

 * list_for_each_safe - Iterate over list nodes and allow deletions
 * @node: list_head pointer used as iterator
 * @safe: list_head pointer used to store info for next entry in list
 * @head: pointer to the head of the list
 *
 * The current node (iterator) is allowed to be removed from the list. Any
 * other modifications to the the list will cause undefined behavior.
 */
#define list_for_each_safe(node, safe, head)                     \
    for (node = (head)->next, safe = node->next; node != (head); \
         node = safe, safe = node->next)

以上為 list.h 所提供的 API ，用途為持續進行 node->next 直到 node 與 (head) 相同。若 node 與 (head) 相同，則代表 head 與 tail 相同，意即為空的佇列。

/* Free all storage used by queue */
void q_free(struct list_head *head) 
{
    if (!head) 
        return;
    struct list_head *entry = NULL, *safe = NULL;
    list_for_each_safe (entry, safe, head)
        q_release_element(container_of(entry, element_t, list));
    free(head);
}

首先，要先確認 head 是否為空指標。若為空指標，則此佇列以為空佇列，不用繼續執行後續程式。若非空指標，則藉由 list.h 提供的 list_for_each_safe 與 queue.h 提供的 q_release_element 走訪與刪除節點，最後就可以完成清空佇列的動作。

q_insert_head 與 q_insert_tail

q_insert_head 目標為在佇列的前端插入一個節點並回傳布林值確認是否成功插入，而 q_insert_tail 則目標插入節點於最末端。不過兩者的實作皆須注意是否為 head 與tail 。此外，此兩項實作亦可與通用的 q_insert 結合，進而精簡程式碼。以下實作將注重於實作通用的 q_insert 。

static inline bool q_insert(struct list_head *head, char *s)
{
    if (!head || !s)
        return false;
    element_t *new_element = malloc(sizeof(element_t));
    if (!new_element)
        return false;
    new_element->value = strdup(s);
    if (!(new_element->value)) {
        free(new_element);
        return false;
    }
    list_add(&new_element->list, head);
    return true;
}

q_remove_head 與 q_remove_tail

/**
 * container_of() - Calculate address of structure that contains address ptr
 * @ptr: pointer to member variable
 * @type: type of the structure containing ptr
 * @member: name of the member variable in struct @type
 *
 * Return: @type pointer of structure containing ptr
 */
#ifndef container_of
#ifdef __LIST_HAVE_TYPEOF
#define container_of(ptr, type, member)                            \
    __extension__({                                                \
        const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
        (type *) ((char *) __pmember - offsetof(type, member));    \
    })
#else
#define container_of(ptr, type, member) \
    ((type *) ((char *) (ptr) -offsetof(type, member)))
#endif
#endif

container_of 巨集用於計算共有幾個結構的指標有包含指標 ptr。

strncpy 函式用於複製字串，特別之處在於能夠使用空值字元 '\0' 填補省略空缺，其取決於字串長度。

要刪除整個佇列的 head 或 tail ，此行為即為刪除此佇列開頭的

q_size

此函式的目的在於回傳目前佇列的長度。

/**
 * list_for_each - Iterate over list nodes
 * @node: list_head pointer used as iterator
 * @head: pointer to the head of the list
 *
 * The nodes and the head of the list must be kept unmodified while
 * iterating through it. Any modifications to the the list will cause undefined
 * behavior.
 */
#define list_for_each(node, head) \
    for (node = (head)->next; node != (head); node = node->next)

上述 list.h 所提供的 list_for_each API 使用與 list_for_each_safe 相同的技巧走訪佇列中的每個節點，直到 head 與 tail 相同，即走訪完成。

註：在 linux 中，鏈結串列為雙向且環狀

/* Return number of elements in queue */
int q_size(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;
    size_t len = 0;
    struct list_head *iter;
    list_for_each (iter, head)
        len++;
    return len;
}

實作以 list_for_each API 為基底，以 len 紀錄共走訪了幾步。

q_delete_mid q_delete_dup

首先， del 與 remove 最大的差別在於被刪除的節點是否會繼續存在於記憶體。在串列中 del 就是將該節點與前後節點斷開，但該節點仍存在於記憶體；而remove 則是將該節點於記憶體中抹除，釋放記憶體空間。

list_splice

join or connect (a rope or ropes) by interweaving the strands at the ends.

/**
 * list_splice() - Add list nodes from a list to beginning of another list
 * @list: pointer to the head of the list with the node entries
 * @head: pointer to the head of the list
 *
 * All nodes from @list are added to the beginning of the list of @head.
 * It is similar to list_add but for multiple nodes. The @list head is not
 * modified and has to be initialized to be used as a valid list head/node
 * again.
 */
static inline void list_splice(struct list_head *list, struct list_head *head)
{
    struct list_head *head_first = head->next;
    struct list_head *list_first = list->next;
    struct list_head *list_last = list->prev;

    if (list_empty(list))
        return;

    head->next = list_first;
    list_first->prev = head;

    list_last->next = head_first;
    head_first->prev = list_last;
}

swap

1. 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
2. 避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。
3. 改進你的漢語描述

鏈結串列是一個環狀的結構，所以只要拆開其中一個，並把他的 next 與 prev 接上 first 與 last ；因其是雙向的，所以最後還要再用一次。 delete 會用到。

q_reverse

reverse 最直觀的觀點就是走訪每個節點，並把節點中的 prev 與 next 對調，不過實作中必須注意是否能夠走訪每個節點。

/**
 * list_move() - Move a list node to the beginning of the list
 * @node: pointer to the node
 * @head: pointer to the head of the list
 *
 * The @node is removed from its old position/node and add to the beginning of
 * @head
 */
static inline void list_move(struct list_head *node, struct list_head *head)
{
    list_del(node);
    list_add(node, head);
}

/* Reverse elements in queue */
void q_reverse(struct list_head *head) 
{
    if (!head || list_empty(head))
        return;
    struct list_head *cur = NULL, *safe = NULL;
    list_for_each_safe (cur, safe, head)
        list_move(cur, head);  // Move to the beginning
}

實作中，藉由 list_move 的 API 完成更新節點的步驟；而 list_add API 則包含了交換 prev 與 next 的步驟。

q_reverseK

此項函式與 q_reverse 不同的地方在於 q_reverseK 轉置的不是一個節點，而是連續 K 個節點。

/* Reverse the nodes of the list k at a time */
void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if (!head || list_empty(head))
        return;
    size_t count = 0;
    struct list_head *safe, *end, *start = head;
    list_for_each_safe (end, safe, head) {
        count++;
        if(count == k){
            LIST_HEAD(tmp);
            list_cut_position(&tmp, start, end);
            q_reverse(&tmp);
            list_splice_init(&tmp, start);
            start = safe->prev;
            count = 0;
        }
    }
}

delete()

mergeSort()

poat 才有順序

?

並行與平行

$\to$ 參見並行和多執行緒程式設計