Linux內核之數據結構

前言

Linux內核實現了一下常用的內建數據結構，主要有： 鏈表

隊列

映射

二叉樹

映射也稱為關聯數組，就是每個唯一的id對應一個自定義的數據結構指針。感覺關於映射的知識比較復雜，沒有深入理解，這裡就記錄一下一些常用的操作API。idr數據結構用於映射用戶空間的UID。

初始化一個idr

建立一個idr的過程分兩步，先靜態定義或者動態創建一個idr數據結構，然後調用idr_init()：

[code]struct idr id;    //靜態定義idr結構體
idr_init(&id);    //初始化idr結構體

分配一個UID

分配一個新的UID也分為兩步： 第一步，告訴idr需要分配新的UID，調整後備樹的大小

[code]int idr_pre_get(struct idr *idp, gfp_t gfp_mask); 
//注意該函數成功時返回1，失敗時返回0。

第二步，獲取新的UID

[code]int idr_get_new(struct idr *idp, void *ptr, int *id);

該方法使用idp指向的idr分配新的UID，將其關聯到指針ptr上。成功時返回0，並將分配的UID存在id上。錯誤時返回非0的錯誤碼，-EAGAIN表示需要再次調用idr_pre_get()，-ENOSPC表示idr已滿。

例：

[code]do {
    if (!idr_pre_get(&idp, GFP_KERNEL))
        return -ENOSPC;
    ret = idr_get_new(&idp, ptr, &id);
    printk(KERN_ALERT "id=%d\n", id);
} while(ret == -EAGAIN);

函數idr_get_new_above()作用與idr_get_new()作用相同，只不過指定了最小的UID限制，就是確保獲取的新的UID大於等於傳入的參數starting_id。

int idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id);

查找UID

在idr中查找UID，idr返回對應的指針。

[code]void *idr_find(struct idr *idp, int id);    //查找id對應的指針

如果成功返回id對應的指針，失敗則返回空指針。

移除UID

從idr中移除UID

[code]void idr_remove(struct idr *idp, int id);   //移除id  
void idr_remove_all(struct idr *idp);   //移除所有id

若成功，則將id關聯的指針和一起從映射中刪除，若失敗了也不會提示、、、

撤銷idr

[code]void idr_destroy(struct idr *idp);  //銷毀idr_layer空閒鏈表

該函數會釋放idr中未使用的內存。並不會釋放已分配給UID使用的內存。