Chapter 6 Kernel Data Structures

[jason--liu]

链表

struct list_head {
    struct list_head *next
    struct list_head *prev;
}

初始化

LIST_HEAD_INIT

链表头

static LIST_HEAD(fox_list)

设置链表头并初始化。

链表操作

1. 添加元素

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

从尾部添加

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

示例：

list_add(&f->list, &fox_list);
list_add_tail(struct list_head *new, struct list_head *head)

2. 删除元素

list_del(struct list_head *entry)

删除并重新初始化

list_del_init():
list_del_init(struct list_head *entry)

3. 移动和连接链表

list_move(struct list_head *list, struct list_head *head)
list_move_tail(struct list_head *list, struct list_head *head)

检查链表是否为空

list_empty(struct list_head *head)

将两个不相连的链表连接

list_splice(struct list_head *list, struct list_head *head)
list_splice_init(struct list_head *list, struct list_head *head)

4. 链表遍历

struct list_head *p;
list_for_each(p, fox_list) {
    /* p points to an entry in the list */
}
// 上面可以简化为
list_for_each_entry(pos, head, member)
// 如果在遍历过程中需要删除元素
list_for_each_entry_safe(pos, next, head, member)
// 反向遍历
list_for_each_entry_reverse(pos, head, member)

使用示例

struct list_head *p;
struct fox *f;
list_for_each(p, &fox_list) {
    /* f points to the structure in which the list is embedded */
    f = list_entry(p, struct fox, list);
}

队列

kfifo

Maps

Maps，也称为关联数组，是唯一键的集合，其中每个键都与特定值相关联。
Maps支持至少3种操作

Add (key, value)
Remove (key)
value = Lookup (key)

Linux中的Mpas设计有特殊用途：将指针映射为唯一值（UID），称为idr

初始化idr

struct idr id_huh; /* statically define idr structure */
idr_init(&id_huh); /* initialize provided idr structure */

分配新UID

1. 调整支持树大小

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

注意，idr_pre_get成功返回1错误返回0，这与内核中绝大多数函数不一样。
2. 获取新ID

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

成功返回0.
示例：

int id;
do {
    if (!idr_pre_get(&idr_huh, GFP_KERNEL))
        return -ENOSPC;
    ret = idr_get_new(&idr_huh, ptr, &id);
} while (ret == -EAGAIN);

查找UID

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

成功idp保存了返回的idr.
示例：

struct my_struct *ptr = idr_find(&idr_huh, id);
if (!ptr)
return -EINVAL; /* error */

移除UID

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

销毁idr

void idr_destroy(struct idr *idp);
void idr_remove_all(struct idr *idp); //强制移除所有UIDs

成功调用 idr_destroy() 只会释放与 idp 指向的 idr 关联的未使用内存，它不会释放分配的 UID 当前正在使用的任何内存。

二叉树

红黑树

1. All nodes are either red or black.
2. Leaf nodes are black.
3. Leaf nodes do not contain data.
4. All non-leaf nodes have two children.
5. If a node is red, both of its children are black.
6. The path from a node to one of its leaves contains the same number of black nodes as the shortest path to any of its other leaves.
   rb_link_node()在指定地方插入新节点，rb_insert_color()实现复杂的reblancing

如何选择数据结构

• If your primary access method is iterating over all your data, use a linked list.
• If your code follows the producer/consumer pattern, use a queue, particularly if you want (or can cope with) a fixed-size buffer
• If you need to map a UID to an object, use a map.
• If you need to store a large amount of data and look it up efficiently, consider a redblack tree.

算法复杂度

时间复杂度