Linux内核(源代码的链接在github)
1.数组、双向数组、无锁链表。
2.B+树,这是一些你没法在教科书上找到的说明。
一个相对简单的B+树的实现。我把它作为一个学习练习来帮助理解B+树是怎样工作的。这同样也被证明是有用的。
...
一个在教科书中并不常见的方法。最小的值在左侧而不是在右边。所有在一个节点里用到的槽都在右边,所有没有用到的槽包含了空值(NUL)。大多数操作只简单地遍历所有的槽一次并在第一个空值时(NUL)中止。
3.优先排序列表用于互斥量、驱动等等。
4.黑红树用于调度、虚拟显存管理、追踪文件描述符和目录项等。
5.区间树
6.根树用于显存管理,NFS相关查询和网路相关功能。
根树的一个通用的好处是储存表针到结构页中。
7.优先级堆,如其名称的教科书实现,用于cgroup。
8.哈希函数,参考了Knuth和一篇论文。
Knuth建议,用加法哈希的机器字来表示接近黄金比列的质数的最大整数。ChuckLever验证了该技术的有效性:
这种质数的选择是位稀疏的,她们可以通过移位和除法操作linux内核24版源代码分析大全,而毋须使用乘法器,乘法器是很慢的。
9.有的代码,例如lov_pool这个驱动,实现了她们自己的哈希函数。
使用了一种旋转哈希算法的哈希函数
Knuth,D.《计算机程序设计艺术,卷3:排序与搜索》,第6、7章.AddisonWesley,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.BoyerandMoore.计算机通讯商会,20(10),1977,pp.762-772.
[2]《准确的字符串匹配算法指南》linux定时器,ThierryLecroq,2004~lecroq/string/string.pdf
注:因为Boyer-Moore(BM)从右到左搜索匹配,依然有可能匹配分布在多个块,在这些情况下该算法并没有优势。
假如你希望确保这样的事情永远不会发生,那使用Knuth-Pratt-Morris(KMP)实现。其实,按照您的设置适当地选择字符串搜索算法。
假如你正在用文本搜索器进行过滤,NIDS或任何类似的重视安全的目的,这么使用KMP。否则,假若你真的关心性能linux解压rar,但是你对数据包进行分类以使用服务质量(QoS)新政linux内核24版源代码分析大全,当你不介意匹配可能分布分散,这么用BM。