Ò׽ؽØÍ¼Èí¼þ¡¢µ¥Îļþ¡¢Ãâ°²×°¡¢´¿ÂÌÉ«¡¢½ö160KB

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Ê÷ʵÏÖÓ봫ͳµÄʵÏÖ·½


Ïà¹ØÎĵµ£º

ʵսLinux Bluetooth±à³Ì(Áù) L2CAP±à³ÌʵÀý

ÀýÒ»£º·¢ËÍ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 ......

[תÌû]LinuxÇý¶¯¿ª·¢Ñ§Ï°µÄһЩ±ØÒª²½Öè

 1. ѧ»áд¼òµ¥µÄmakefile
2. ±àһЩӦÓÃ
³ÌÐò
£¬¿ÉÒÔÓÃmakefileÅÜÆðÀ´
3. ѧ»áдÇý¶¯
µÄmakefile
4. дһ¼òµ¥charÇý¶¯£¬makefile±àÒëͨ¹ý£¬¿ÉÒÔinsmod£¬ lsmod£¬ rmmod. ÔÚÇý¶¯µÄinitº¯ÊýÀï´òÓ¡hello world£¬insmodºóÓ¦¸ÃÄܹ»Í¨¹ýdmesg¿´µ½Êä³ö
¡£
5. дһÍêÕûÇý¶¯£¬ ¼ÓÉÏread£¬ write£¬ ioctl£¬ pollingµÈ¸ ......

º¯ÊýÖ¸Õë&»Øµ÷º¯Êý&linuxÖеÄsignalº¯Êý


1.
int (*func)();º¯ÊýÖ¸Õ룬ָÏòµÄº¯ÊýΪ¿Õ²ÎÊý£¬·µ»ØÕûÐÍ£»
2.
»Øµ÷º¯ÊýÊÇÒ»¸ö³ÌÐòÔ±²»ÄÜÏÔʽµ÷Óõĺ¯Êý£»Í¨¹ý½«»Øµ÷º¯ÊýµÄµØÖ·´«¸ø±»µ÷ÓÃÕß´Ó¶øÊµÏÖµ÷Óá£
»Øµ÷º¯ÊýÊÇÒ»¸öͨ¹ýº¯ÊýÖ¸Õëµ÷Óõĺ¯Êý¡£Èç¹ûÄã°Ñº¯ÊýµÄÖ¸Õ루µØÖ·£©×÷Ϊ²ÎÊý´«µÝ¸øÁíÒ»¸öº¯Êý£¬µ±Õâ¸öÖ¸Õë±»ÓÃΪµ÷ÓÃËüËùÖ¸ÏòµÄº¯Êýʱ£¬ÎÒÃǾÍ˵ÕâÊǻص÷º¯ ......

LinuxÉϵÄÐéÄ⻯¼¼Êõ


ÐéÄ⻯¼¼ÊõµÄ·½·¨, ¼Ü¹¹ºÍʵÏÖ¸ÅÀÀ
¼¶±ð: Öм¶
M. Tim Jones [mtj@mtjones.com], ¹ËÎʹ¤³Ìʦ, Emulex
Ô­ÎÄ: Virtual Linux
Òë: ÕÔçæ cn.zhaoke.com
http://blog.zhaoke.com/45.html
2006Äê12ÔÂ29ÈÕ
ÐéÄ⻯¼¼ÊõµÄÓ¦ÓÃÊ®·Ö¹ã·º. µ±Ç°ÐéÄ⻯¼¼ÊõÖ÷Òª¹Ø×¢ÓÚ·þÎñÆ÷µÄÐéÄ⻯, »òÔÚµ¥¸öÖ÷»úÉϼĴæ¶à¸ö¶ÀÁ¢µÄ²Ù×÷ϵͳ. ±¾Î ......

ÈçºÎ²é¿´linux°æ±¾


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 ......
© 2009 ej38.com All Rights Reserved. ¹ØÓÚE½¡ÍøÁªÏµÎÒÃÇ | Õ¾µãµØÍ¼ | ¸ÓICP±¸09004571ºÅ