quene.c開發紀錄

開發環境

$ lscpu
Architecture:             x86_64
  CPU op-mode(s):         32-bit, 64-bit
  Address sizes:          46 bits physical, 48 bits virtual
  Byte Order:             Little Endian
CPU(s):                   24
  On-line CPU(s) list:    0-23
Vendor ID:                GenuineIntel
  Model name:             13th Gen Intel(R) Core(TM) i7-13700
    CPU family:           6
    Model:                183
    Thread(s) per core:   2
    Core(s) per socket:   16
    Socket(s):            1
    Stepping:             1
    CPU(s) scaling MHz:   18%
    CPU max MHz:          5200.0000
    CPU min MHz:          800.0000
    BogoMIPS:             4224.00
Virtualization features:  
  Virtualization:         VT-x
Caches (sum of all):      
  L1d:                    640 KiB (16 instances)
  L1i:                    768 KiB (16 instances)
  L2:                     24 MiB (10 instances)
  L3:                     30 MiB (1 instance)
NUMA:                     
  NUMA node(s):           1
  NUMA node0 CPU(s):      0-23

補全queue.c

q_new

一開始想先了解linux kernel的寫法（因為看不懂）
先研讀queue.h和list.h相關程式碼發現INIT_LIST_HEAD()這個函式可以使程式碼更簡潔

/* Create an empty queue */
struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(*head));
    if (!head)
        return NULL;
    INIT_LIST_HEAD(head);
    return head;
}

INIT_LIST_HEAD(head)會初始化head指向其自身
內部程式碼為

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

如此我們即創建一個新的queue而目前為空佇列

q_free

在研究list.h時發現有list_for_each_safe(pos, next, head)這個迴圈的控制結構，它的作用是讓 pos 依序指向每個節點，而 next 則確保當 pos 被刪除時，仍然能繼續遍歷下一個節點。
這個宏不會自動刪除節點或釋放記憶體，所以還是需要手動處理刪除與釋放記憶體的步驟

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

    struct list_head *pos, *next;
    list_for_each_safe(pos, next, head) {
        element_t *elem = list_entry(pos, element_t, list);
        list_del(pos);
        free(elem->value);
        free(elem);
    }
    free(head);
}

pos：當前正在處理的節點
next：下一個節點，確保當前節點刪除後不影響迴圈繼續運行

為什麼要用 _safe？
Ans : 直接刪除 pos 後，它的 next 可能會無法訪問，因此 list_for_each_safe 事先儲存 next 以確保迴圈不會因為 pos 被刪除而出錯。

element_t *elem = list_entry(pos, element_t, list);
list_entry 是 Linux Kernel 提供的宏：把 pos 轉換回實際的 element_t 結構（因為 list_head 只是鏈結串列的一部分，而 element_t 是整個節點）。
element_t 內部應該包含：

struct element {
    char *value;
    struct list_head list;
};

這樣我們就可以存取 value 和 list。

list_del(pos);
從鏈結串列中刪除該節點，但還沒有釋放記憶體。
free(elem->value);
釋放該節點的 value，這是動態配置的字串。
free(elem);
釋放該節點的記憶體，避免記憶體洩漏。
free(head);
在遍歷並釋放所有節點後，最後釋放 head 所佔用的記憶體。
這適用於 head 本身是動態配置的情況（如 malloc() 分配的鏈結串列）。
但如果 head 是 stack 上的變數，不應該 free(head)，否則會導致錯誤（double free）。

q_insert_head

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

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

    struct list_head *next = head->next;
    head->next = &new_node->list;
    new_node->list.next = next;
    new_node->list.prev = head;
    next->prev = &new_node->list;
    return true;
}

q_insert_tail

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

    new_node->value = strdup(s);
    if (!new_node->value) {
        free(new_node);
        return false;
    }
    struct list_head *prev = head->prev;
    head->prev = &new_node->list;
    new_node->list.next = head;
    new_node->list.prev = prev;
    prev->next = &new_node->list;
    return true;
}

q_remove_head

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

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

    element_t *elem = list_entry(first, element_t, list);

    if (bufsize > 0) {
        strncpy(sp, elem->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    return elem;
}

q_remove_tail

/* Remove an element from tail of queue */
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head)
        return NULL;
    struct list_head *tail = head->prev;
    struct list_head *prev = tail->prev;
    prev->next = head;
    head->prev = prev;

    element_t *elem = list_entry(prev, element_t, list);

    if (bufsize > 0) {
        strncpy(sp, elem->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    return elem;
}