[What]linux -> list

罗列内核已经提供的双向链表数据结构的使用方式。

linux 在 linux/list.h 中提供了 双向环形链表双向链表 的操作函数, 此代码可以移植到其他应用环境中,方便使用.

需要注意的是:

  1. linux是通过 将此链表嵌入在其他数据结构中, 从而将很多不同的数据结构链接起来!. (而不是链表中包含数据).
  2. 函数中的参数 head 代表的即为链表头!
  3. typeof 是GCC扩展的关键字, 所以不能在编译选项中添加 -std=c99!
    • 为了兼容所有编译器,我在github中移植了通用版本。

使用

双向环形链表

内核提供了以下宏供操作:

  • LIST_HEAD(name) : 定义一个名称为 name 的双向环形链表.
  • list_entry(ptr, type, member) : 通过链表节点地址 ptr , 来反推处包含它的 type 类型数据的起始地址, member 就是该链表节点在 type 中定义的名称
  • list_first_entry(ptr, type, member): 反推节点 ptr 的下一个节点被包含的 type 类型数据的起始地址, 当 ptr为头指针时, 返回的就是第一个对象.
  • list_last_entry(ptr, type, member): 反推节点 ptr 的上一个节点被包含的 type 类型数据的起始地址, 当 ptr 为头指针时, 返回的就是最后一个对象.
  • list_first_entry_or_null(ptr, type, member): 反推节点 ptr 的上一个节点被包含的 type 类型数据的起始地址, 如果没有则返回 NULL
  • list_next_entry(pos, member): 得到与 pos 相连的下一个数据结构的地址
  • list_next_entry(pos, member): 得到与 pos 相连的下一个数据结构的地址
  • list_for_each(pos, head) : 向下遍历 poshead 节点, 此宏为一个for语句
  • list_for_each_prev(pos, head) : 向上遍历 poshead 节点, 此宏为一个for语句
  • list_for_each_safe(pos, head) : 向下遍历 poshead 节点, 此宏为一个for语句
  • list_for_each_prev_safe(pos, head) : 向上遍历 poshead 节点, 此宏为一个for语句
  • list_for_each_entry(pos, head, member): 通过节点, 向下数据结构遍历
  • list_for_each_entry_reverse(pos, head, member): 通过节点,向上数据结构遍历
  • list_for_each_entry_continue(pos, head, member): 通过数据结构,向下数据结构遍历
  • list_for_each_entry_continue_reverse(pos, head, member): 通过数据结构,向下数据结构遍历
  • list_for_each_entry_from(pos, head, member): 寻找与head匹配的数据结构 pos
  • list_safe_reset_next(pos, n, member): 得到与 pos 相连的下一个数据结构地址, 并将地址复制给 n.

内核提供了以下函数供操作:

/**
* @brief 初始化链表
*/

static inline void INIT_LIST_HEAD(struct list_head *list);
/**
* @brief 在节点 prev,next 之间插入新节点 new
*/

static inline void __list_add(struct list_head *new,
struct list_head *prev,
struct list_head *next);

/**
* @brief 在节点 head 前插入节点 new (以head 为参考)
*/

static inline void list_add(struct list_head *new, struct list_head *head);

/**
* @brief 在节点 head 后插入节点 new (以head 为参考)
*/

static inline void list_add_tail(struct list_head *new, struct list_head *head);

/**
* @brief 删除 prev 和 next 之间的节点
*/

static inline void __list_del(struct list_head *prev, struct list_head *next);
/**
* @brief 删除 entry 节点
*/

static inline void __list_del_entry(struct list_head *entry);
/// 在上面的基础上还要初始化 entry
static inline void list_del_init(struct list_head *entry);
/**
* @brief 节点 new 替换节点 old
*/

static inline void list_replace(struct list_head *old, struct list_head *new);
/// 在上面基础上还要初始化 old
static inline void list_replace_init(struct list_head *old, struct list_head *new);
/**
* @brief 将节点 list 移出当前链表, 并插入到另一个链表的 head 节点前
*/

static inline void list_move(struct list_head *list, struct list_head *head);
/// 与上函数相比, 插入到 head 后
static inline void list_move_tail(struct list_head *list, struct list_head *head);
/**
* @brief 判断节点 head 是否是 list 节点的下一个节点
*/

static inline int list_is_last(struct list_head *list, struct list_head *head);
/**
* @brief 判断当前链表是否是空链表
*/

static inline int list_empty(struct list_head *head);
/**
* @brief 以安全的方式判断当前链表是否是空链表
*/

static inline int list_empty_careful(const struct list_head *head);
/**
* @brief 移动head节点到左边
*/

static inline int list_rotate_left(struct list_head *head);
/**
* @brief 判断一个链表是否只有一个元素
*/

static inline int list_is_singular(struct list_head *head);
/**
* @brief 将链表从 head 节点处切断(不包括 head), 一直到 entry(包括), 并拼接到 list节点处
*/

static inline int list_cut_position(struct list_head *list,
struct list_head *head,
struct list_head *entry)
;


/**
* @brief 在链表的 head 前拼接一段链表 list
*/

static inline int list_splice(struct list_head *list, struct list_head *head);
/// 拼接并初始化 list
static inline int list_splice_init(struct list_head *list, struct list_head *head);
/// 在链表后拼接
static inline int list_splice_tail(struct list_head *list, struct list_head *head);
static inline int list_splice_tail_init(struct list_head *list, struct list_head *head);

双向链表(待分析)

内核提供了以下宏供操作:

  • HLIST_HEAD(name) : 定义一个名称为 name 的双向链表

内核提供了如下函数供操作:

/**
* @brief 初始化一个链表
*/

static inline void INIT_HLIST_NODE(struct hlist_node *h);
Last Updated 2018-11-05 Mon 07:36.
Render by hexo-renderer-org with Emacs 26.1 (Org mode 9.1.14)