本頁由 Uduru0522, qwe661234, SmallHanley, hankluo6, jserv 貢獻 概況 Linux 核心如同其他複雜的資訊系統,也提供 hash table 的實作,但其原始程式碼中卻藏有間接指標 (可參見你所不知道的 C 語言: linked list 和非連續記憶體) 的巧妙和數學奧秘。 間接指標的應用 Linux 核心的 hash table 實作中,用以處理 hash 數值碰撞的 hlist_node: struct hlist_node { struct hlist_node *next, **pprev;
3/26/2023本頁由 steven1lung, linD026, jserv 貢獻 red-black tree (以下簡稱 rbtree 或紅黑樹) 是一種特別的自平衡樹,不僅其新增、移除、搜尋的時間複雜度均維持在 $O(\log n)$,而樹高 (tree height) 的定義與尋常平衡樹不同 (紅黑樹用的是 black height),後者使其重新平衡所需的時間成本較其他平衡樹小。 black height 的定義是,對於 bh(x),從 x 到任何一個它後代到末端 (即 leaf) 節點的路徑上,遇到的標註為「黑」的節點個數 (不含自身)。 Linux 核心原始程式碼中,許多地方出現紅黑樹的蹤影,例如:hr_timer 使用紅黑樹來記錄計時器 (timer) 端發出的要求、ext3 檔案系統使用紅黑樹來追蹤目錄內容變更,以及 CFS 這個 Linux 預設 CPU 排程器,由於需要頻繁地插入跟移除節點 (任務),因此開發者選擇用紅黑樹 (搭配一些效能調整)。VMA(Virtual Memory Area)也用紅黑樹來紀錄追蹤頁面 (page) 變更,因為後者不免存在頻繁的讀取 VMA 結構,如 page fault 和 mmap 等操作,且當大量的已映射 (mapped) 區域時存在時,若要尋找某個特定的虛擬記憶體地址,鏈結串列 (linked list) 的走訪成本過高,因此需要一種資料結構以提供更有效率的尋找,於是黑紅樹就可勝任。 延伸閱讀: Red-black Trees (rbtree) in Linux
3/25/2023virtme 是 Linux 核心開發者利用 QEMU 所建立一個輕量級的 Linux 核心測試環境,和 Linux 核心原始程式碼有很好的整合。 預先安裝套件 以 Ubuntu Linux 22.04 來說,需要安裝以下套件: $ sudo apt -y -q install \ bc \ flex \ bison \ build-essential \
3/24/2023contributed by <LinYunWen, raygoah> ==Linked List 練習題== 參考解題錄影 Q1. 分析以下程式碼,推敲 FuncA, FuncB, FuncC 的作用,並且推測程式執行結果。 首先看到 struct node 為節點的結構,有一個 int 儲存資料,及一個 next pointer, prev pointer,因此可以推測其為一個雙向的 linked list struct node {
3/24/2023