Linux内核文档之rbtree.txt
Red-black Trees (rbtree) in Linux
January 18, 2007
Rob Landley <rob@landley.net>
=============================
red-black树是什么样的树，为什么需要red-black树？
------------------------------------------------
red-black tree（RB树）是一种平衡二叉树，它主要用于存储或者说索引可排序的键
值对数据。RB树（红黑树）与radix树和hash表都不同。radix树是一种比较适合用于
存储稀疏的数据集而且将用一个大整数进行插入，删除，查找的操作基础。而hash表
并不是以某种排序顺序进行存储，而且必须指定大小和hash函数。
RB树与AVL树很相似，但是比AVL树有更好的插入和删除最坏情况的时间复杂度，以及
O(log n)的最坏查找时间复杂度。
引用:
在Linux中有很多地方用到了RD树。anticipatory, deadline, 和CFQ I/O调度都使用
的是RB树进行请求跟踪，还有CD/DVD驱动的包管理也是如此。
高精度计时器（high-resolution timer）使用RB树组织定时请求。
EXT3文件系统也使用RB树来管理目录。
虚拟存储管理系统也是有RB树进行VMAs（Virtual Memory Areas）的管理。
当然还有文件描述符，密码钥匙，“等级令牌桶”调度的网络数据包都是用RB数据进
行组织和管理的。
相关资料：
Linux Weekly News article on red-black trees
http://lwn.net/Articles/184495/
Wikipedia entry on red-black trees
http://en.wikipedia.org/wiki/Red-black_tree
可见RB树（红黑树）在Linux内核中的重要性。
Linux内核的RB树实现
---------------------------------------
在Linux内核源代码中rb树的实现在lib/rbtree.c文件中，可以通过
#include "linux/rbtree.h"进行使用。
在Linux内核中的RB树实现与传统的实现方
相关文档：
一：前言
最近在研究android的sensor driver，主要是E-compass，其中用到了Linux input子系统.在网上也看了很多这方面的资料，感觉还是这篇分析的比较细致透彻，因此转载一下以便自己学习，同时和大家分享！
（这篇博客主要是以键盘驱动为例的，不过讲解的是Linux Input Subsystem，可以仔细的研究一下！）
键盘驱动将检 ......
出处:http://ericxiao.cublog.cn/
一：前言
在键盘驱动代码分析的笔记中，接触到了input子系统.键盘驱动，键盘驱动将检测到的所有按键都上报给了input子系统。Input子系统是所有I/O设备驱动的中间层，为上层提供了一个统一的界面。例如，在终端系统中，我们不需要去管有多少个键盘，多少个鼠标。它只要从input子系统中去� ......
环境介绍：Centos5.2+2.6.18-8.el5内核，编译器是GCC4.1.2。
要编译的内核2.6.18-8.el3
仅仅修改了部分内核的配置信息，没有大的变化。
然后：make ;make modules;make modules_install;
编译没有出问题，生成了内核，mkinitrd生成了initrd，加到lilo.conf中，重启选择新内核，出现一下问题：
hub 3-0:1.0: USB hub fo ......
牛津字典中对"kernel"一词的定义是："较软的、通常是一个坚果可食用的部分。"当然还有第二种定义："某个东西核心或者最重要的部分。"对Linux来说，它的Kernel无疑属于第二种解释。让我们来看看这个重要的东西是如何工作的，先从一点理论说起。
广义地来说kernel就是一个软件，它在硬件和运� ......
转自：http://hi.baidu.com/deep_pro/blog/item/b4253550bb5ab7561138c27a.html
这里转载的是Linux下移植jvm的过程，因为仅仅是CDC
J2ME CDC（Connected Device Configuration，连接式设备配置集）
使用CVM，面向那些具有更强计算能力的嵌入式设备，包含了Java类库的核心部分，是应用Java技术在嵌入式设备上进行开发所需 ......
