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Ê÷ÊÇÒ»ÖֱȽÏÊʺÏÓÃÓÚ
´æ´¢Ï¡ÊèµÄÊý¾Ý¼¯¶øÇÒ½«ÓÃÒ»¸ö´óÕûÊý½øÐвåÈ룬ɾ³ý£¬²éÕҵIJÙ×÷»ù´¡¡£¶øhash±í
²¢²»ÊÇÒÔijÖÖÅÅÐò˳Ðò½øÐд洢£¬¶øÇÒ±ØÐëÖ¸¶¨´óСºÍhashº¯Êý¡£
RBÊ÷ÓëAVLÊ÷ºÜÏàËÆ£¬µ«ÊDZÈ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Ê÷ʵÏÖÓ봫ͳµÄʵÏÖ·½
Ïà¹ØÎĵµ£º
ÀýÒ»£º·¢ËÍSignaling Packet£º
Signaling CommandÊÇ2¸öBluetoothʵÌåÖ®¼äµÄL2CAP²ãÃüÁî´«Êä¡£ËùÒÔµÃSignaling CommandʹÓÃCID 0x0001.
¶à¸öCommand¿ÉÒÔÔÚÒ»¸öC-frame£¨control frame£©Öз¢ËÍ¡£
Èç¹ûÒªÖ±½Ó·¢ËÍSignaling Command.ÐèÒª½¨Á¢SOCK_RAWÀàÐ͵ÄL2CAPÁ¬½ÓSocket¡£ÕâÑù²ÅÓлú»á×Ô¼ºÌî³äCommand Code£¬Identi ......
1. ѧ»áд¼òµ¥µÄmakefile
2. ±àһЩӦÓÃ
³ÌÐò
£¬¿ÉÒÔÓÃmakefileÅÜÆðÀ´
3. ѧ»áдÇý¶¯
µÄmakefile
4. дһ¼òµ¥charÇý¶¯£¬makefile±àÒëͨ¹ý£¬¿ÉÒÔinsmod£¬ lsmod£¬ rmmod. ÔÚÇý¶¯µÄinitº¯ÊýÀï´òÓ¡hello world£¬insmodºóÓ¦¸ÃÄܹ»Í¨¹ýdmesg¿´µ½Êä³ö
¡£
5. дһÍêÕûÇý¶¯£¬ ¼ÓÉÏread£¬ write£¬ ioctl£¬ pollingµÈ¸ ......
1.
int (*func)();º¯ÊýÖ¸Õ룬ָÏòµÄº¯ÊýΪ¿Õ²ÎÊý£¬·µ»ØÕûÐÍ£»
2.
»Øµ÷º¯ÊýÊÇÒ»¸ö³ÌÐòÔ±²»ÄÜÏÔʽµ÷Óõĺ¯Êý£»Í¨¹ý½«»Øµ÷º¯ÊýµÄµØÖ·´«¸ø±»µ÷ÓÃÕß´Ó¶øÊµÏÖµ÷Óá£
»Øµ÷º¯ÊýÊÇÒ»¸öͨ¹ýº¯ÊýÖ¸Õëµ÷Óõĺ¯Êý¡£Èç¹ûÄã°Ñº¯ÊýµÄÖ¸Õ루µØÖ·£©×÷Ϊ²ÎÊý´«µÝ¸øÁíÒ»¸öº¯Êý£¬µ±Õâ¸öÖ¸Õë±»ÓÃΪµ÷ÓÃËüËùÖ¸ÏòµÄº¯Êýʱ£¬ÎÒÃǾÍ˵ÕâÊǻص÷º¯ ......
ÐéÄ⻯¼¼ÊõµÄ·½·¨, ¼Ü¹¹ºÍʵÏÖ¸ÅÀÀ
¼¶±ð: Öм¶
M. Tim Jones [mtj@mtjones.com], ¹ËÎʹ¤³Ìʦ, Emulex
ÔÎÄ: Virtual Linux
Òë: ÕÔçæ cn.zhaoke.com
http://blog.zhaoke.com/45.html
2006Äê12ÔÂ29ÈÕ
ÐéÄ⻯¼¼ÊõµÄÓ¦ÓÃÊ®·Ö¹ã·º. µ±Ç°ÐéÄ⻯¼¼ÊõÖ÷Òª¹Ø×¢ÓÚ·þÎñÆ÷µÄÐéÄ⻯, »òÔÚµ¥¸öÖ÷»úÉϼĴæ¶à¸ö¶ÀÁ¢µÄ²Ù×÷ϵͳ. ±¾Î ......
1. ²é¿´Äں˰汾ÃüÁ
¡¡¡¡1) [root@q1test01 ~]# cat /proc/version
¡¡¡¡ Linux version 2.6.9-22.ELsmp (bhcompile@crowe.devel.redhat.com) (gcc version 3.4.4 20050721 (Red Hat 3.4.4-2)) #1 SMP Mon Sep 19 18:00:54 EDT 2005
¡¡¡¡2) [root@q1test01 ~]# uname -a
¡¡¡¡Linux q1test0 ......