linux内核中的数据结构
http://vinllen.com/linuxnei-he-zhong-de-shu-ju-jie-gou/
https://zhuanlan.zhihu.com/p/58087261
https://blog.csdn.net/wenqian1991/article/details/44515713
https://blog.csdn.net/ace_an/article/details/53813242
?
?
Linux中最重要最常用如下四種：
LIST：鏈表 <linux/list.h>
Linux內(nèi)核的標(biāo)準(zhǔn)鏈表就是采用“環(huán)形、雙向”鏈表形式實(shí)現(xiàn)
沿著鏈表移動(dòng)智能是線性移動(dòng)
需要隨機(jī)訪問(wèn)的數(shù)據(jù)，一般不使用鏈表
鏈表存放數(shù)據(jù)的理想情況是：需要遍歷所有數(shù)據(jù)、或者需要?jiǎng)討B(tài)加入/刪除數(shù)據(jù)
有時(shí)首元素會(huì)用一個(gè)特殊的指針表示，稱為“頭指針”，可以方便的找到鏈表的“起始端”
Linux內(nèi)核實(shí)現(xiàn)特殊性：不是將數(shù)據(jù)結(jié)構(gòu)塞入鏈表，而是將鏈表結(jié)點(diǎn)塞入數(shù)據(jù)結(jié)構(gòu)
Linux內(nèi)核鏈表操作函數(shù)的復(fù)雜度都是O（1），而不管鏈表中元素?cái)?shù)目的多少
list_add\__list_add
list_add_tail\__list_add_tail
list_del\__list_del
list_del_init\__list_del_init
list_move\__list_move
list_move_tail\__list_move_tail
list_empty\__list_empty
list_entry\__list_entry
list_splice\__list_splice
list_splice_init\__list_splice_init
Linux內(nèi)核遍歷鏈表的復(fù)雜度是O（n），n是鏈表元素?cái)?shù)目
list_for_each
list_for_each_entry
list_for_each_entry_reverse 反向遍歷鏈表，有二原因：①當(dāng)反向遍歷性能好時(shí)；②當(dāng)遍歷順序很重要時(shí)；
list_for_each_entry_safe 該函數(shù)允許在遍歷鏈表循環(huán)體中刪除元素，普通遍歷函數(shù)不允許這樣做
list_for_each_entry_safe_reverse
鏈表操作函數(shù)分為外部函數(shù)、內(nèi)部函數(shù)，函數(shù)同名，只差雙下劃線__，內(nèi)部函數(shù)用prev、next參數(shù)
FIFO：隊(duì)列 <linux/kfifo.h>
Linux內(nèi)核通用隊(duì)列實(shí)現(xiàn)稱為kfifo，實(shí)現(xiàn)在文件kernel/kfifo.c中
維護(hù)兩個(gè)偏移量：
入口偏移（下一次入隊(duì)時(shí)位置）>=出口偏移（下一次出隊(duì)時(shí)位置）；
入口偏移==出口偏移，說(shuō)明隊(duì)列空了；
入口偏移==隊(duì)列長(zhǎng)度，說(shuō)明隊(duì)列重置前不能再有入隊(duì)操作；
提供兩個(gè)主要操作：
入隊(duì)enqueue（copy數(shù)據(jù)到隊(duì)列入口偏移位置）
出隊(duì)dequeue（從隊(duì)列出口偏移copy數(shù)據(jù)）
隊(duì)列操作：
kfifo_alloc 動(dòng)態(tài)創(chuàng)建、初始化 （size需是2的n次冪）
kfifo_init 動(dòng)態(tài)創(chuàng)建、初始化，但使用已分配內(nèi)存 （size同上）
DECLARE_KFIFO/INIT_KFIFO 靜態(tài)聲明，不常用（size同上）
kfifo_in ? 入隊(duì)
kfifo_out ? 出隊(duì)
kfifo_out_peek ? 不出隊(duì)，只返回?cái)?shù)據(jù)
kfifo_size ? 隊(duì)列總體空間（長(zhǎng)度）
kfifo_len ? 隊(duì)列已用空間
kfifo_avail ? 隊(duì)列剩余空間
kfifo_is_empty ? 判定隊(duì)列空
kfifo_is_full ? 判定隊(duì)列滿
kfifo_reset ? 重置隊(duì)列（拋棄所有元素）
kfifo_free ? 釋放kfifo_alloc創(chuàng)建的隊(duì)列
映射：
稱為關(guān)聯(lián)數(shù)組，由“鍵<==>值”對(duì)兒組成的集合；?
“鍵”是唯一的，“值”關(guān)聯(lián)到鍵；
映射操作：
Add (key, value) ? 增加
Remove (key) ? 刪除
Value = Lookup (key) ? 查找
Allocate ? 插入鍵值對(duì)，產(chǎn)生UID
Linux內(nèi)核提供了簡(jiǎn)單、有效的映射數(shù)據(jù)結(jié)構(gòu)。但是它并非一個(gè)通用的映射；
Linux內(nèi)核提供它的目標(biāo)是：映射一個(gè)唯一的標(biāo)識(shí)數(shù)（UID）到一個(gè)指針； （因此并不適合其它場(chǎng)景）
idr數(shù)據(jù)結(jié)構(gòu)：用于映射用戶空間的UID
idr_init ? 初始化靜態(tài)/動(dòng)態(tài)分配的idr
...
二叉樹(shù)：
樹(shù)，是一個(gè)能提供分層的“樹(shù)”型數(shù)據(jù)結(jié)構(gòu)的特定數(shù)據(jù)結(jié)構(gòu)；
樹(shù)，是一個(gè)無(wú)環(huán)、連接的有向圖；
樹(shù)，任何一個(gè)節(jié)點(diǎn)具有0~n個(gè)出邊，1個(gè)入邊；
節(jié)點(diǎn)深度，是從根節(jié)點(diǎn)起到達(dá)該節(jié)點(diǎn)止一共需要經(jīng)過(guò)的父節(jié)點(diǎn)數(shù)目；
樹(shù)的高度，是葉子節(jié)點(diǎn)的深度；
二叉樹(shù)，任何一個(gè)節(jié)點(diǎn)最多有2個(gè)出邊的樹(shù)，即只能有0、1、2個(gè)出邊；
BST：二叉搜索樹(shù)
規(guī)則1：根左分支節(jié)點(diǎn)值 < 根節(jié)點(diǎn)值
規(guī)則2：根右分支節(jié)點(diǎn)值 > 根節(jié)點(diǎn)值
規(guī)則3：所有子樹(shù)都是二叉搜索樹(shù)
前序遍歷：根節(jié)點(diǎn)->左子樹(shù)->右子樹(shù)
中序遍歷：左子樹(shù)->根節(jié)點(diǎn)->右子樹(shù)
后序遍歷：左子樹(shù)->右子樹(shù)->根節(jié)點(diǎn)
在樹(shù)中搜索給定值、按序遍歷都相當(dāng)快捷；中序遍歷二叉搜索樹(shù)時(shí)會(huì)按照節(jié)點(diǎn)值從小到大的順序排序；
自平衡二叉搜索樹(shù)
平衡二叉搜索樹(shù)：所有葉子節(jié)點(diǎn)深度差值都不超過(guò)1的二叉搜索樹(shù)
自平衡二叉搜索樹(shù)：操作都試圖維持平衡（半平衡）的二叉搜索樹(shù)
紅黑樹(shù)
是一種“自平衡二叉搜索樹(shù)”
是Linux主要的平衡二叉搜索樹(shù)
具有特殊的著色屬性（或紅色、或黑色）
能維持半平衡結(jié)構(gòu)，其6屬性：
屬性1：所有節(jié)點(diǎn)要么著紅色、要么著黑色
屬性2：葉子節(jié)點(diǎn)都是黑色
屬性3：葉子節(jié)點(diǎn)不包含數(shù)據(jù)
屬性4：非葉子節(jié)點(diǎn)都有2個(gè)子節(jié)點(diǎn)
屬性5：如果節(jié)點(diǎn)是紅色，則它子節(jié)點(diǎn)都是黑色
屬性6：一個(gè)節(jié)點(diǎn)到該節(jié)點(diǎn)的葉子節(jié)點(diǎn)的所有路徑中，總是包含相同數(shù)目的黑色節(jié)點(diǎn)；
上述屬性確保：
一個(gè)紅色節(jié)點(diǎn)不能是其它紅色節(jié)點(diǎn)的子節(jié)點(diǎn)（或者父節(jié)點(diǎn)），即兩個(gè)紅色節(jié)點(diǎn)不能相連；
從樹(shù)的任何一個(gè)節(jié)點(diǎn)到其葉子節(jié)點(diǎn)的路徑都具有相同數(shù)目的黑色節(jié)點(diǎn)；即最長(zhǎng)路徑是紅黑交替路徑，最短路徑是全黑路徑；
所以，最深葉子節(jié)點(diǎn)深度，不會(huì)大于2倍最淺葉子節(jié)點(diǎn)深度； 紅黑樹(shù)總是半平衡的；
rbtree： <linux/rbtree.h>
Linux實(shí)現(xiàn)的紅黑樹(shù)
實(shí)現(xiàn)在lib/rbtree.c中
插入效率和樹(shù)中節(jié)點(diǎn)數(shù)目呈現(xiàn)對(duì)數(shù)關(guān)系；（即：時(shí)間復(fù)雜度與節(jié)點(diǎn)數(shù)目是對(duì)數(shù)關(guān)系）
根節(jié)點(diǎn)由數(shù)據(jù)結(jié)構(gòu)rb_root描述，創(chuàng)建新紅黑樹(shù)，需要分配新的rb_root結(jié)構(gòu)并初始化為RB_ROOT
其它節(jié)點(diǎn)由數(shù)據(jù)結(jié)構(gòu)rb_node描述
未提供搜索和插入操作函數(shù)，需要由用戶自己實(shí)現(xiàn)（可以使用rbtree提供的輔助函數(shù)，但要實(shí)現(xiàn)比較操作算子）
其它較少用的：
radixtree：基數(shù)樹(shù)
數(shù)據(jù)結(jié)構(gòu)的選擇：
原則一：遍歷操作為主時(shí)，優(yōu)先考慮鏈表；（沒(méi)有數(shù)據(jù)結(jié)構(gòu)能提供比線性算法復(fù)雜度更好的算法去遍歷元素）
原則二：排除性能因素，當(dāng)需要相對(duì)較少數(shù)據(jù)項(xiàng)時(shí)，優(yōu)先考慮鏈表；
原則三：當(dāng)需要與其它選擇鏈表的代碼交互時(shí)，優(yōu)先考慮鏈表；
原則四：需要大小不明的數(shù)據(jù)集合，優(yōu)先選擇鏈表；
原則五：代碼架構(gòu)復(fù)合"生產(chǎn)者/消費(fèi)者"模式，優(yōu)先選擇隊(duì)列；
原則六：當(dāng)需要一個(gè)定長(zhǎng)的緩沖，選擇隊(duì)列；
原則七：如果需要映射一個(gè)UID到一個(gè)對(duì)象，選擇映射；
原則八：如果需要存儲(chǔ)大量數(shù)據(jù)，并且快速檢索，選擇紅黑樹(shù)；
轉(zhuǎn)載于:https://www.cnblogs.com/clemente/p/10887589.html
總結(jié)
以上是生活随笔為你收集整理的linux内核中的数据结构的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
