《Linux内核设计与实现》读书笔记——内核数据结构

链表

简单链表：

双向链表：

环形链表：

如果对数据集合的主要操作是遍历数据，就使用链表。

 

双向链表

Linux不是将数据结构塞入链表，而是将链表节点塞入数据结构。

链表节点（include\linux\list.h）：

/*
 * Simple doubly linked list implementation.
 *
 * Some of the internal functions ("__xxx") are useful when
 * manipulating whole lists rather than single entries, as
 * sometimes we already know the next/prev entries and we can
 * generate better code by using them directly rather than
 * using the generic single-entry routines.
 */
struct list_head {
    struct list_head *next, *prev;
};

list_head本身没有意义，它需要嵌入到数据结构中才能生效：

struct clk {
    struct list_head node;
    const char *name;
    int id;
    struct module *owner;
    struct clk *parent;
    struct clk_ops *ops;
    struct kref kref;
    unsigned long rate;
    unsigned long flags;
};

使用宏container_of()可以方便地从链表节点找到父结构中的成员。

/**
 * container_of - cast a member of a structure out to the containing structure
 * @ptr:    the pointer to the member.
 * @type:   the type of the container struct this is embedded in.
 * @member: the name of the member within the struct.
 *
 */
#define container_of(ptr, type, member) ({          \
    const typeof(((type *)0)->member) * __mptr = (ptr); \
    (type *)((char *)__mptr - offsetof(type, member)); })

对应的有一个链表的宏：

/**
 * list_entry - get the struct for this entry
 * @ptr:    the &struct list_head pointer.
 * @type:   the type of the struct this is embedded in.
 * @member: the name of the list_struct within the struct.
 */
#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

用于返回包含list_head的父类型结构体相关成员。

依靠list_entry()，内核提供了创建、操作以及其它链表管理的各种例程。

 

链表操作

链表节点初始化：

#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
    struct list_head name = LIST_HEAD_INIT(name)
static inline void INIT_LIST_HEAD(struct list_head *list)
{
    list->next = list;
    list->prev = list;
}

数据结构静态初始化中的链表节点初始化：

static struct ts_ops bm_ops = {
    .name         = "bm",
    .find         = bm_find,
    .init         = bm_init,
    .get_pattern      = bm_get_pattern,
    .get_pattern_len  = bm_get_pattern_len,
    .owner        = THIS_MODULE,
    .list         = LIST_HEAD_INIT(bm_ops.list)
};

双向链表通常没有所谓的头部，但是很多时候会需要指定：

static LIST_HEAD(cpufreq_governor_list);

然后使用：

    list_for_each_entry(t, &cpufreq_governor_list, governor_list)
        if (!strnicmp(str_governor, t->name, CPUFREQ_NAME_LEN))
            return t;

链表相关的操作都在include\linux\list.h中，注意操作函数都是内联函数，所以在头文件中。

这里不一一介绍。

 

队列

队列先进后出：

如果代码符合生产者/消费者模式，则使用队列。

 

队列操作

Linux内核通用队列实现称为kfifo，位于kernel\kfifo.c，声明在include\linux\kfifo.h。

队列：

struct kfifo {
    unsigned char *buffer;  /* the buffer holding the data */
    unsigned int size;  /* the size of the allocated buffer */
    unsigned int in;    /* data is added at offset (in % size) */
    unsigned int out;   /* data is extracted from off. (out % size) */
};

队列动态分配：

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

队列静态分配：

#define DECLARE_KFIFO(name, size) \
union { \
    struct kfifo name; \
    unsigned char name##kfifo_buffer[size + sizeof(struct kfifo)]; \
}
#define INIT_KFIFO(name) \
    name = __kfifo_initializer(sizeof(name##kfifo_buffer) - \
                sizeof(struct kfifo), \
                name##kfifo_buffer + sizeof(struct kfifo))

推入：

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

送出：

extern __must_check unsigned int kfifo_out(struct kfifo *fifo,
                void *to, unsigned int len);

 

映射

映射也称关联数组。

映射指的是键值的对应关系。

键是唯一的。

Linux中实现的映射是一个唯一的标识数（UID，其实是一个int类型的数值）到指针的映射。

Linux提供了idr数据结构用于映射UID（include\linux\idr.h）。

struct idr {
    struct idr_layer *top;
    struct idr_layer *id_free;
    int       layers; /* only valid without concurrent changes */
    int       id_free_cnt;
    spinlock_t    lock;
};

如果需要映射一个UID到一个对象，就使用映射。

 

映射操作

初始化一个idr：

void idr_init(struct idr *idp);

获取UID，这里分为两步：

int idr_pre_get(struct idr *idp, gfp_t gfp_mask);
int idr_get_new(struct idr *idp, void *ptr, int *id);

UID存放在id中，与ptr指针关联。

查找UID：

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

删除UID：

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

销毁idr：

void idr_destroy(struct idr *idp);

但是不会清除已分配给UID使用的内存，除非使用：

void idr_remove_all(struct idr *idp);

 

树

树结构是一个能够提供分层的树形数据结构。

二叉树每个节点最多只有两个出边的树。

二叉搜索树是一个节点有序的二叉树：

• 根的左分支节点值都小于根节点值；
• 右分支节点值都大于根节点值；
• 所有子树也都是二叉搜索树；

自平衡二叉搜索树所有叶子节点深度差不超过1。

红黑树是一种自平衡二叉搜索树，有如下特定：

• 所有节点要么着红色，要么着黑色；
• 叶子节点都是黑色的；
• 叶子节点不包含数据；
• 所有非叶子节点都有两个子节点；
• 如果一个节点是红色，则它的子节点都是黑色；
• 在一个节点到其叶子节点的路径中，如果总是包含相同数目的黑色节点，则该路径相比其它路径是最短的；

如果需要存储大量的数据，并且检索迅速，就使用红黑树。

 

红黑树实现

Linux主要的平衡二叉树数据结构就是红黑树。

Linux实现的红黑树称为rbtree。

根节点用rb_root表示（include\linux\rbtree.h）：

struct rb_root
{
    struct rb_node *rb_node;
};

其它节点用rb_node表示：

struct rb_node
{
    unsigned long  rb_parent_color;
#define RB_RED      0
#define RB_BLACK    1
    struct rb_node *rb_right;
    struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));

rbtree的实现并没有提供搜索和插入例程。