专栏首页分布式系统进阶linux内核源码 -- list链表

linux内核源码 -- list链表

  • linux kernel中的list估计已经被各位前辈们写烂了,但是我还是想在这里记录一下;
  • linux kernel里的很多数据结构都很经典, list链表就是其中之一
  • 本篇要介绍的内容:
    1. list的定义
    2. list提供的操作方法
    3. 注意事项
    4. 使用实例

List 所在文件:
  • List的所有操作可以在 include/linux/list.h找到;
  • List head的定义可以在 include/linux/types.h找到;
定义
  • 实际上这就是一个双向循环链表, 且有一个头指针
  • list head的定义:
struct list_head {
    struct list_head *next, *prev;
};
  • 这个定义中只有前向和后向指针,没任何的数据部分, 那我们基本上就知道了, 它不是被单独使用的,而是把它嵌入到用户定义的struct中, 将用户定义的数据结构串起来,作成list;
  • 思想很巧妙, 对用户定义的数据结构侵入性很小, 实现了c++中std::List模板的功能;
  • 虽然这个定义是叫head, 但其实嵌入到用户定义的数据结构中的也是这个.
初始化
// 静态初始化
#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) \
    struct list_head name = LIST_HEAD_INIT(name)

// 调用INIT_LIST_HEAD来初始化, **WRITE_ONCE**这个后面我们专门介绍
static inline void INIT_LIST_HEAD(struct list_head *list)
{
    WRITE_ONCE(list->next, list);
    list->prev = list;
}
插入操作
  • 将一个元素插入到两个元素之间, 即将 new插入到prevnext中, 这个函数是下面在头部和尾部插入的实现基础
static inline void __list_add(struct list_head *new,
                  struct list_head *prev,
                  struct list_head *next)
{
    if (!__list_add_valid(new, prev, next))
        return;

       // 前后向指针的改写赋值
    next->prev = new;
    new->next = next;
    new->prev = prev;
    WRITE_ONCE(prev->next, new);
}
  • 在头部插入, 在头指针和第一个元素间插入
static inline void list_add(struct list_head *new, struct list_head *head)
{
    __list_add(new, head, head->next);
}
  • 在尾部插入,在最后一个元素间和头指针间插入, 因为是循环链表嘛~
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
    __list_add(new, head->prev, head);
}
删除操作
  • 删除两个元素之间的元素
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
    next->prev = prev;
    WRITE_ONCE(prev->next, next);
}
  • 删除一个已知元素entry
static inline void __list_del_entry(struct list_head *entry)
{
    if (!__list_del_entry_valid(entry))
        return;

    __list_del(entry->prev, entry->next);
}
替换操作

都是指针的变换

static inline void list_replace(struct list_head *old,
                struct list_head *new)
{
    new->next = old->next;
    new->next->prev = new;
    new->prev = old->prev;
    new->prev->next = new;
}
移动操作
  • 将一个元素移动到另一个list的头部
static inline void list_move(struct list_head *list, struct list_head *head)
{
       // 从原处的list后摘掉
    __list_del_entry(list);
       // 添加到新链表的头部
    list_add(list, head);
}
  • 将一个元素移动到另一个list的队尾
static inline void list_move_tail(struct list_head *list,
                  struct list_head *head)
{
       // 从原处的list后摘掉
    __list_del_entry(list);
       // 添加到新链表的队尾
    list_add_tail(list, head);
}
拆分操作, 将一个队列由指定的位置拆成两个队列

list是新队列的head指针, 包括的元素从原head队列的第一个元素到entry, head队列仅包括余下的元素

static inline void __list_cut_position(struct list_head *list,
        struct list_head *head, struct list_head *entry)
{
    struct list_head *new_first = entry->next;
    list->next = head->next;
    list->next->prev = list;
    list->prev = entry;
    entry->next = list;
    head->next = new_first;
    new_first->prev = head;
}
合并操作:
  • 将list列表中除了list本身插入到prev和next之间
static inline void __list_splice(const struct list_head *list,
                 struct list_head *prev,
                 struct list_head *next)
{
    struct list_head *first = list->next;
    struct list_head *last = list->prev;

    first->prev = prev;
    prev->next = first;

    last->next = next;
    next->prev = last;
}
  • 将一个列表插入到另一个列表的头部
static inline void list_splice(const struct list_head *list,
                struct list_head *head)
{
    if (!list_empty(list))
        __list_splice(list, head, head->next);
}
  • 将一个列表插入到另一个列表的尾部
static inline void list_splice_tail(struct list_head *list,
                struct list_head *head)
{
    if (!list_empty(list))
        __list_splice(list, head->prev, head);
}
list_entry

按之前说的, 这个list_head都有要嵌入到用户定义的struct中,这个宏就是由这个list_head ptr来获取当前所处的struct对象的指针, 用了linux的经典宏定义 container_of

#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)
一堆宏定义, 用来各种遍历, 获取entry
注意事项
  • 只说一个,就是多线程操作同一个list, 还是需要加锁
使用实例
typedef struct _Foo {                              
    int data_;                                     
    struct list_head link;                         
} Foo;                                             
                                                   
int main(int argn, char* argv[]) {                 
    LIST_HEAD(test_link);                          
                                                   
    Foo f1;                                        
    f1.data_ = 1;                                  
    LIST_HEAD_INIT(f1.link);                       
                                                   
    Foo f2;                                        
    f1.data_ = 2;                                  
    LIST_HEAD_INIT(f2.link);                       
                                                   
    list_add(&f1.link, &test_link)                 
    list_add(&f2.link, &test_link)                 
                                                   
    struct Foo* pos;                               
    list_for_each_entry(pos, &test_link, link) {   
        printf("%d\n", pos->data_);                
    }                                              
                                                   
    return 0;                                      
}                                                  

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Influxdb 编译

    扫帚的影子
  • KafkaController分析3-ControllerChannelManager

    使用NetworkClient连接到broker node, 使用selector处理网络IO;

    扫帚的影子
  • Kafka中Message存储相关类大揭密Kafka源码分析-汇总

    扫帚的影子
  • C 链表 - linux 如何实现

    链表是基本数据结构, 一开始学习数据结构时, 我一般这么定义, 对应实现从头或尾插入的处理函数,

    orientlu
  • Python中赋值、浅拷贝与深拷贝

       python中关于对象复制有三种类型的使用方式,赋值、浅拷贝与深拷贝。他们既有区别又有联系,刚好最近碰到这一类的问题,研究下。 一、赋值         ...

    用户1214487
  • Python数据分析之锁具装箱问题问题重述问题分析建模与求解

    罗罗攀
  • <算法入门>快速理解7种排序算法 | python3实现(附源码)学习难度:桶排序(简化版)冒泡排序选择排序插入排序快速排序(面试常用算法)归并排序(先分后和, 分而治之)希尔排序

    算法是程序的灵魂,而排序算法 是算法的入门经典,作者在此用python亲自实现了7种主流的排序算法,并做简短的说明. ? 排序算法 学习难度: 桶排序 < 冒泡...

    zhaoolee
  • python将字符串类型list转换成list

    python读取了一个list是字符串形式的'[11.23,23.34]',想转换成list类型:

    机器学习和大数据挖掘
  • R语言数据清洗实战——高效list解析方案

    list是R语言中包容性最强的数据对象,几乎可以容乃所有的其他数据类型。 但是包容性最强也也意味着他对于内部子对象的类型限制最少,甚至内部可以存在递归结构,这样...

    数据小磨坊
  • python 集合

    说明: 拿list_1每一个元素去list_2中查找,如果有,直接忽略,否则就直接输出。

    py3study

扫码关注云+社区

领取腾讯云代金券