Linux内核数据结构

链表

       链表是Linux内核中最简单、最普通的数据结构。链表是一种存放和操作可变数量元素（常称为节点）的数据结构。链表和静态数据的不同之处在于，它所包含的元素都是动态创建并插入链表的，在编译时不知道具体需要创建多少个元素。另外链表中每个元素的创建时间各不相同，所以他们在内存中无须占用连续内存区。正是因为元素不连续地存放，所以各元素需要通过某种方式被连接在一起。于是每个元素都包含一个指向下一个元素的指针，当有元素加入链表或从链表中删除时，简单调整指向下一个节点的指针就可以了。

 

环形链表

      通常情况下，因为链表中最后一个元素不再有下一个元素，所以将链表尾元素中的向后指针设置为NULL，以此表明它是链表中的最后一个元素。但是在有些链表中，末尾元素并不指向特殊值，相反，它指回链表的首元素。这种链表因为首尾相连，所以被称为是环形链表。环形链表也存在双向链表和单向链表两种形式。在环形链表中，首节点的向前指针指向尾节点。下图分别为单向和环形双向链表。

        因为环形双向链表提供了强大的灵活性，所以Linux内核的标准链表就是采用环形双向链表形式实现的。

 

沿链表移动

       沿链表移动只能是线性移动。先访问某个元素，然后沿该元素的向后指针访问下一个元素，不断重复这个过程，就可以沿链表向后移动了。这是一种最简单的沿链表移动方法，也是最适合访问链表的方法。如果需要随机访问数据，一般不使用链表。使用链表存放数据的理想情况是，需要遍历所有数据或需要动态加入和删除数据时。

        有时，首元素会用一个特殊指针表示--该指针称为头指针，利用头指针可方便、快速地找到链表的起始端。在非环形链表里，向后指针指向NULL的元素是尾元素，而在环形链表里向后指针指向头元素的元素是尾元素。遍历一个链表需要线性地访问从第一个元素到最后一个元素之间的所有元素。对于双向链表来说，也可以反向遍历链表，可以从最后一个元素线性访问到第一元素。当然还可以从链表中的指定元素开始向前和向后访问数个元素，并不一定要访问整个链表。

 

 

队列

         任何操作系统内核都少不了一种编程模型：生产者和消费者。在该模式中，生产者创造数据，而消费者则反过来，读取消息和处理包或者以其他的方式消费这些数据。实现该模型的最简单的方式无非是使用队列。生产者将数据推进队列，然后消费者从队列中摘取数据。消费者获取数据的顺序和推入顺序一致。也就是说，第一个进入队列的数据一定是第一个离开队列的。也正是这个原因，队列也称为FIFO。Linux内核通用队列实现称为kfifo。

       kfifo和多数其他队列实现类似，提供了两个主要操作：enqueue(入队列)和dequeue(出队列)。kfifo对象维护了两个偏移量：入口偏移量和出口偏移量。入口偏移量是指下一次入队列的位置，出口偏移量是指下一次出队列时的位置。出口偏移量总是小于等于入口偏移，否则无意义，因为那样说明要出队列的元素根本还没有入队列。enqueue操作拷贝数据到队列中的入口偏移位置。当上述动作完成后，入口偏移随之加上推入的元素数目。dequeue操作从队列中出口偏移处拷贝数据，当上述动作完成后，出口偏移量随之减去摘取的元素数据。当出口偏移量等于入口偏移是，说明队列空了：在新数据被推入前，不可再摘取任何数据了。当入口偏移等于队列长度时，说明队列重置前，不可再有新数据推入队列。

 

映射

       一个映射，也常称为关联数组，其实是一个由唯一键组成的集合，而每个键必然关联一个特定的值。这种键到值的关联关系称为映射。

 

二叉树

        树结构是一个能够提供分层的树型结构的特定数据结构。在数学意义上，树是一个无环的，连续的有向图，其中任何一个顶点（在树里叫作节点）具有0个或多个出边以及0个或1个入边。一个二叉树是每个节点最多只有两个出边的树。

 

二叉搜索树

        一个二叉搜索树（BST）是一个节点有序二叉树，其顺序通常遵循下列法则：

• 根的左分支节点值都小于根节点值
• 右分支节点值都大于根节点值
• 所有的子树都是二叉搜索树

       因此，一个二叉搜索树所有节点必然都有顺序，而且左节点小于其父亲节点值，而右子节点大于其父节点值的二叉树。所以，在树中搜索一个给定值或者按序遍历树都箱单快捷（算法分别是对数和线性的），二叉搜索树见下图。

 

自平衡二叉搜索树

        一个节点的深度是指从其根节点起，到达它一共需要经过的父节点数目。处于树底层的节点（再也没有子节点）称为叶子节点。一个树的高度是指树中的处于最底层节点的深度。一个平衡二叉搜索树是一个所有叶子节点深度不超过1的二叉搜索树，一个自平衡二叉搜索树是指其操作都试图维持（半）平衡的二叉搜索树。

 

      红黑树是一种自平衡二叉搜索树。Linux主要的平衡二叉树数据结构就是红黑树。红黑树具有特殊的着色属性，或红色或黑色。红黑树因遵循下面六个属性，所以能够维持半平衡结构：

• 所有的节点要么红色，要么黑色
• 叶子节点都是黑色
• 叶子节点不包含数据
• 所有非叶子节点都有两个子节点
• 如果一个节点是红色，则它的子节点都是黑色
• 在一个节点到叶子节点的路径中，如果总是包含同样数据的黑色节点，则该路径相比其他路径最短的。

       上述条件，保证了最深叶子节点的深度不会大于两倍的最浅叶子节点的深度。所以红黑树总是平衡的。为什么它具有如此神奇特点呢？首先第五个属性，一个红色几点不能使其他红色节点的子节点或父节点。而第六个属性保证了，从树的任何节点到叶子节点的路径都具有相同数据的黑色节点，树里的最长路径则是红黑交替节点路径，所以最短路径必然是具有相同数量黑色节点的---只包含黑色节点的路径。于是从根节点到叶子节点的最长路径不会超过最短路径的两倍。

 

算法复杂度

       在计算机科学和相关的学科中，很有必要将算法的复杂度（或伸缩度）量化地表示出来。虽然存在各种各样的表示伸缩度的方法，但最常用的技术还是研究算法的渐近行为（asymptoic behavior）。渐近行为是指当算法的输入变得非常大或接近于无限大时算法的行为。渐近行为充分显示了当一个算法的输入逐渐变大时，该算法的伸缩度如何。研究算法的伸缩度可以帮助我们以特定基准抽象出算法模型，从而更好的理解算法的行为。

      算法就是一系列的指令，它可能有一个或多个输入，最后产生一个结果或输出。

大O符号

     一种很有用的渐近表示法就是上限--它是一个函数，其值自从一个起点之后总是超过我们研究的函数的值，也就是说上限增长等于或快于我们的函数。一个特殊符号，大O符号用来描述这种增长率。函数f(x)可以写作O(g(x))，读为“f是g的大O”。数学定义形式为：如果f(x)是O(g(x))，那么Ec，x’满足f(x)<=C.g(x),Vx>x' ,换成自然语言是，完成f(x)的时间总是短于或等于完成g(x)的时间和任意敞亮(至少要输入的x值大于等于某个初始化值x')的乘积。

 

大θ[卡帕]符号

      当大多数人谈论大O符号时，更准确地讲他们谈论的更接近Donald Knuth所描述的大θ符号。算法分析领域之父，Kunth教授，将其描述为大θ符号，并给出了下面的定义：如果f(x)是g(x)的大θ，那么g(x)既是f(x)的上限也是f(x)的下限。

       那么，我们可以说f(x)是g(x)级(order).级或大θ，是理解内核中算法的最重要的数据工具之一。