搬運工

Linux內核(源代碼的鏈接在github)。

1.鏈表、雙向鏈表、無鎖鏈表。

2.B+ 樹，這是一些你無法在教科書上找到的說明。

一個相對簡單的B+樹的實現。我把它作為一個學習練習來幫助理解B+樹是如何工作的。這同樣也被證明是有用的。 ...

一個在教科書中並不常見的技巧。最小的值在右側而不是在左側。所有在一個節點裏用到的槽都在左側，所有沒有用到的槽包含了空值(NUL)。大多數操作隻簡單地遍曆所有的槽一次並在第一個空值時(NUL)終止。

3.優先排序列表 用於 互斥量、驅動等等。

4.紅黑樹用於調度、虛擬內存管理、追蹤文件描述符和目錄項等。

5.區間樹

6.根樹用於內存管理，NFS相關查詢和網絡相關功能。

根樹的一個通用的用處是存儲指針到結構頁中。

7.優先級堆，如其名稱的教科書實現，用於cgroup。

《簡單的基於CLR的隻插入的，含有指針的定長優先級堆》第七章

8.哈希函數，參考了Knuth和一篇論文。

Knuth建議，用乘法哈希的機器字來表示接近黃金比例的素數的最大整數。Chuck Lever驗證了該技術的有效性：

https://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf

這些素數的選擇是位稀疏的，他們可以通過移位和加法操作，而不必使用乘法器，乘法器是很慢的。

9.有的代碼，比如這個驅動，實現了他們自己的哈希函數。 使用了一種旋轉哈希算法的哈希函數 Knuth, D. 《計算機程序設計藝術, 卷 3: 排序與搜索》, 第6、7章. Addison Wesley, 1973

10.哈希表用於實現inode、文件係統完整性檢測等等。

11.位數組用於處理標誌位、中斷等等。並在Knuth那本書的卷4中闡述。

12.信號量和自旋鎖

13.二分查找用於中斷處理,寄存器緩存查詢等等。

14.B樹的二分查找。

15.深度優先搜索被廣泛地用於目錄配置中。

執行一個修改過的命名空間樹的深度優先遍曆，以指定的start_handle節點開始（及結束）。回調函數會在任何一個參數匹配的節點被發現時被調用。如果回調函數返回了一個非0值，搜索將會立即終止並且將其返回給調用者。

16.廣度優先搜索用於檢測運行時鎖定的正確性。

17.鏈表中的歸並排序用於垃圾收集、文件係統管理等等。

18.冒泡排序在一個驅動庫中也有一個令人驚訝的實現。

19.Knuth-Morris-Pratt 字符串匹配,

根據Knuth、Morris和Pratt[1]實現了一個線性時間的字符串匹配算法。他們的算法避免了轉換函數的顯式地計算DELTA。對於長度為n的文本，其匹配時間是O(n)，對於長度為m的模式(pattern)，僅使用一個輔助函數PI[1 . .m]，預先計算模式的時間為O(m)。數組PI允許轉換函數DELTA被實時有效地計算。粗略地說，對於任何狀態"q"= 0,1,…、m和在SIGMA中的任何字符"a",PI["q"]的值包含的信息是獨立的"a"並需要計算DELTA("q","a") [2]。既然PI隻有m個記錄，而DELTA有O(m |SIGMA|)個記錄，在預處理時間計算PI而不是DELTA的時候，我們可以節省一個因數|SIGMA|

[1] Cormen, Leiserson, Rivest, Stein，算法介紹，第二版，MIT出版社

[2] 見有限自動機原理

20.Boyer-Moore 模式匹配是在找替代品時的參考和建議。

實現了Boyer-Moore字符串匹配算法:

[1] 《一個快速的字符串搜索算法》，R.S. Boyer and Moore.計算機通信協會，20(10), 1977, pp. 762-772.https://www.cs.utexas.edu/users/moore/publications/fstrpos.pdf

[2] 《準確的字符串匹配算法手冊》，Thierry Lecroq, 2004 https://www-igm.univ-mlv.fr/~lecroq/string/string.pdf

注:由於Boyer-Moore(BM)從右到左搜索匹配，仍然有可能匹配分布在多個塊，在這種情況下該算法並沒有優勢。

如果你希望確保這樣的事情永遠不會發生，那使用Knuth-Pratt-Morris(KMP)實現。總之，根據您的設置適當地選擇字符串搜索算法。

如果你正在用文本搜索器進行過濾，NIDS或任何類似的注重安全的目的，那麼使用KMP。否則，如果你真的關心性能，並且你對數據包進行分類以使用服務質量(QoS)政策，當你不介意匹配可能分布分散，那麼用BM。