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Ê÷ʵÏÖÓ봫ͳµÄʵÏÖ·½
Ïà¹ØÎĵµ£º
1. HCI²ãÐÒé¸ÅÊö£º
HCIÌṩһÌ×ͳһµÄ·½·¨À´·ÃÎÊBluetoothµ×²ã¡£ÈçͼËùʾ£º
´ÓͼÉÏ¿ÉÒÔ¿´³ö£¬Host Controller Interface(HCI) ¾ÍÊÇÓÃÀ´¹µÍ¨HostºÍModule¡£Hostͨ³£¾ÍÊÇPC£¬ ModuleÔòÊÇÒÔ¸÷ÖÖÎïÀíÁ¬½ÓÐÎʽ£¨USB,serial,pc-cardµÈ£©Á¬½Óµ½PCÉϵÄbluetooth Dongle¡£
ÔÚHostÕâÒ»¶Ë£ºapplication,SDP,L2capµÈÐÒé ......
Ò»£ºÇ°ÑÔ
×î½üÔÚÑо¿androidµÄsensor driver£¬Ö÷ÒªÊÇE-compass£¬ÆäÖÐÓõ½ÁËLinux input×Óϵͳ.ÔÚÍøÉÏÒ²¿´Á˺ܶàÕâ·½ÃæµÄ×ÊÁÏ£¬¸Ð¾õ»¹ÊÇÕâÆª·ÖÎöµÄ±È½ÏϸÖÂ͸³¹£¬Òò´Ë×ªÔØÒ»ÏÂÒÔ±ã×Ô¼ºÑ§Ï°£¬Í¬Ê±ºÍ´ó¼Ò·ÖÏí£¡
£¨ÕâÆª²©¿ÍÖ÷ÒªÊÇÒÔ¼üÅÌÇý¶¯ÎªÀýµÄ£¬²»¹ý½²½âµÄÊÇLinux Input Subsystem£¬¿ÉÒÔ×ÐϸµÄÑо¿Ò»Ï£¡£©
¼üÅÌÇý¶¯½«¼ì ......
mountÊÇÓÃÀ´¹ÒÔØÎļþϵͳµÄ£¬¿ÉÒÔÔÚÆô¶¯µÄʱºò¹ÒÔØÒ²¿ÉÒÔÔÚÆô¶¯ºó¹ÒÔØ¡£ÔÚÆô¶¯ºó¹ÒÔØ¿ÉÒÔʹÓÃmountÃüÁîʵÏÖ£¬ÒªÊµÏÖÆô¶¯Ê±×Ô¶¯¹ÒÔØÉ豸ÔòÐèÆô¶¯autofs·þÎñ¾ÍÌṩÕâÖÖ¹¦ÄÜ¡£¸Ã¹¦ÄܾÍÏñwindowsÖеĹâÇý×Ô¶¯´ò¿ª¹¦ÄÜ£¬Äܹ»¼°Ê±¹ÒÔØ¶¯Ì¬¼ÓÔØµÄÎļþϵͳ¡£ÃâÈ¥ÎÒÃÇÊÖ¶¯¹ÒÔÚÂé·³¡£ÒªÊµÏÖ¹âÇý£¬ÈíÅ̵ȵĶ¯Ì¬×Ô¶¯¹ÒÔØ£¬ÐèÒª½øÐÐÏà¹Øµ ......
´ÓUbuntu 8.04µ½9.10£¬ÎÒµÄAcer Aspire 4920±¾×ÓµÄýÌå´¥Ãþ¿ØÖƼüʼÖÕ²»ÄÜÕý³£¹¤×÷¡£×î½üÕÒµ½ÁË´ËÎÊÌâµÄ½â¾ö·½·¨£¬¹©Ê¹ÓÃLinux²Ù×÷ϵͳ¼°ÓµÓÐAcer±Ê¼Ç±¾µÄÓû§²Î¿¼¡£ ÔÚUbuntu 9.10Ï£¬ÎÒµÄýÌå¿ØÖÆ¼ü±»Ê¶±ðΪÁíÒ»¿éSynaptics´¥Ãþ°å£¬²¢ÇÒËĸö¼ü·Ö±ð±»Ê¶±ðΪÉÏ¡¢Ï¡¢×ó¡¢ÓÒ·Ò³¼ü£¬µ¼ÖÂÎÞ·¨Õý³£¹¤×÷¡£ÐèҪͨ¹ýÐ޸İ´¼üÓ³Éä ......
ת×Ô£ºhttp://hi.baidu.com/deep_pro/blog/item/b4253550bb5ab7561138c27a.html
ÕâÀï×ªÔØµÄÊÇLinuxÏÂÒÆÖ²jvmµÄ¹ý³Ì£¬ÒòΪ½ö½öÊÇCDC
J2ME CDC£¨Connected Device Configuration£¬Á¬½ÓʽÉ豸ÅäÖü¯£©
ʹÓÃCVM£¬ÃæÏòÄÇЩ¾ßÓиüÇ¿¼ÆËãÄÜÁ¦µÄǶÈëʽÉ豸£¬°üº¬ÁËJavaÀà¿âµÄºËÐIJ¿·Ö£¬ÊÇÓ¦ÓÃJava¼¼ÊõÔÚǶÈëʽÉ豸ÉϽøÐпª·¢ËùÐè ......