Linux內(nèi)核實現(xiàn)了常用的通用數(shù)據(jù)結(jié)構(gòu)：

• 鏈表
• 隊列
• 映射
• 二叉樹
  內(nèi)核開發(fā)者應(yīng)盡可能使用這些數(shù)據(jù)結(jié)構(gòu)，不要造輪子重復(fù)開發(fā)。

一、鏈表

鏈表數(shù)據(jù)結(jié)構(gòu)：

//<linux/list.h>
struct list_head {
    struct list_head *next;
    struct list_head *prev;
};

因為C語言中，一個給定結(jié)構(gòu)的變量偏移在編譯時地址就被ABI固定下來了，所有使用宏container_of()可以從鏈表指針找到父結(jié)構(gòu)中包含的任何變量：

#define container_of(ptr, type, member) ({\
    const typeof( ( (type *)0)->member ) *__mptr = (ptr); \
    (type *)( (char *)__mptr - offsetof(type,member) ); })

返回包含list_head的父類型結(jié)構(gòu)體：

#define list_entry(ptr, type, member) container_of(ptr, type, member)

初始化鏈表：

INIT_LIST_HEAD(struct list_head*);

鏈表頭：

static LIST_HEAD(struct list_head*)

增加鏈表節(jié)點：

list_add(struct list_head *new, struct list_head *head)
list_add_tail(struct list_head *new, struct list_head *head)

刪除鏈表節(jié)點：

list_del(struct list_head *entry)
list_del_init(struct list_head *entry)

遍歷鏈表：

list_for_each(struct list_head *p, struct list_head *head) //p依次指向head為頭節(jié)點的鏈表中的節(jié)點

list_for_each_entry(typeof(member) *f, struct list_head *head, member) //f依次指向head為頭節(jié)點的鏈表中的節(jié)點的父結(jié)構(gòu)中member成員

二、隊列

Linux內(nèi)核通用隊列實現(xiàn)稱為kfifo。

初始化隊列：

int kfifo_alloc(struct kfifo *fifo, unsigned int size, gfp_t gfp_mask);
int kfifo_init(struct kfifo *fifo, void *bufffer, unsigned int size);

// size必須是2的冪

推入隊列數(shù)據(jù)：

unsigned int kfifo_in(struct kfifo *fifo, const void *from, unsigned int len);

摘取隊列數(shù)據(jù)：

unsigned int kfifo_out(struct kfifo *fifo, void *to, unsigned int len);
unsigned int kfifo_out_peek(struct kfifo *fifo, void *to, unsigned int len, unsigned offset);  //只讀取不從隊列中刪除數(shù)據(jù)

獲取隊列長度：

static inline unsigned int kfifo_size(struct kfifo *fifo); //隊列空間總體大小
static inline unsigned int kfifo_len(struct kfifo *fifo); //已推入數(shù)據(jù)大小
static inline unsigned int kfifo_avail(struct kfifo *fifo); //隊列中還有多少可用空間
static inline int kfifo_is_empty(struct kfifo *fifo); //隊列是否空
static inline int kfifo_is_full(struct kfifo *fifo); //隊列是否滿

重置隊列：

static inline void kfifo_reset(struct kfifo *fifo);

撤銷隊列：

void kfifo_free(struct kfifo *fifo);

三、映射

Linux內(nèi)核提供了簡單、有效的映射數(shù)據(jù)結(jié)構(gòu)，目標(biāo)是：映射一個唯一的標(biāo)識數(shù)（UID）到一個指針。idr數(shù)據(jù)結(jié)構(gòu)用于映射用戶空間的UID。

初始化idr：

void  idr_init(struct idr *idp);

分配新的UID，分為兩步：

• 1、告訴idr需要分配新的UID，允許其在必要時調(diào)整后備樹的大小

int idr_pre_get(struct idr *idp, gfp_t gfp_mask);

• 2、獲取新的UID，并且將其加到idr:

int idr_get_new(struct idr *idp, void *ptr, int *id);
int idr_get_new_above(struct idr *idp, void *ptr, int startint_id, int *id); //分配的UID必須大于或等于startint_id

查找UID:

void *idr_find(strcut idr *idp, int, id);

刪除UID：

void idr_remove(struct idr *idp, int id);

撤銷idr：

void idr_destroy(struct idr *idp); //只釋放idr中未使用的內(nèi)存，不釋放當(dāng)前分配給UID使用的任何內(nèi)存
void idr_remove_all(struct idr *idp); //刪除所有UID

四、二叉樹

Linux實現(xiàn)的紅黑樹稱為rbtree。