专栏首页orientluC 链表 - linux 如何实现

C 链表 - linux 如何实现

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

struct int_node_old {
    int val;
    struct int_node_old *next;
};

void old_list_insert(struct int_node_old *head, struct int_node_old *new)
{
    new->next = head->next;
    head->next = new;
}

void old_list_insert_tail(struct int_node_old *head, struct int_node_old *new)
{
    struct int_node_old *list = head;
    for (; list->next != NULL; list = list->next);
    list->next = new;
    new->next = NULL;
}

但是发现, 如果这么定义的话,每次实现一个list的结构, 都需要重新对应编写处理函数, 重复轮子。

想起前段时间, 看到FreeRTOS提供的链表处理方式(《 FreeRTOS 任务调度 List 组织 》), 将链表结构定义和实际使用时具体节点数据内容分开定义, 供系统各个模块使用。

查看linux的源码, 发现linux中也为我们提供了相似的实现(源码), 把一些共性统一起来。 类是 python 中for_each处理,有些意思。

linux 下的链表定义在文件 include/linux/types.h, 采用的是双向列表

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

在文件list.h, 提供了一常用的接口, 根据自己的需求, 定义节点node, 建立 list 并添加节点后, 看到的组织如图所示 :

list

利用这个定义, 我定义了一个自己的list数据结构, 并copy了一些接口实现,感受下,linux 是如何管理链表的。

// list 节点结构定义
struct int_node {
    int val;
    struct list_head list;
};

// 新建一个list head, 初始化其指针指向自身
#define LIST_HEAD(name) \
    struct list_head name = {&(name), &(name)};

// 将新节点插入到指定两个节点之间
static inline void __list_add(struct list_head *new,
        struct list_head *prev,
        struct list_head *next)
{
    next->prev = new;
    new->next = next;
    new->prev = prev;
    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);
}

// 正序遍历宏, 
#define list_for_each(pos, head) \
    for ((pos) = (head)->next; (pos) != (head); (pos) = (pos)->next)
// 逆序遍历宏
#define list_for_each_prev(pos, head) \
    for ((pos) = (head)->prev; (pos) != (head); (pos) = (pos)->prev)

// 已知一个结构的成员,获取该成员所属结构体地址
#define container_of(ptr, type, menber) \
    (type *)((char*)ptr - (char*) &(((type *)0)->menber))
#define list_entry(ptr, type, menber) container_of(ptr, type, menber)

通过 container_of, 可以取得我们当前正在操作链表所属结构体地址,进而对具体数据进行处理, 利用c语言的一个小技巧, 把结构体投影到地址为0的地方,那么成员的绝对地址就是偏移量, 得到偏移量后,根据成员的p指针反算出结构体的首地址。 另外一种做法是定义list_head中, 包含一个成员变量,指向其所属,FreeRTOS是如此做的。

int main(void)
{
    LIST_HEAD(my_list);
    struct int_node a, b, c;

    a.val = 1;
    b.val = 2;
    c.val = 3;

    list_add(&(a.list), &my_list);
    list_add(&(b.list), &my_list);
    list_add_tail(&(c.list), &my_list);

    struct list_head *plist;
    struct int_node *pnode;

    list_for_each(plist, &my_list) {
        pnode = list_entry(plist, struct int_node, list);
        printf("%d ", pnode->val);
    }
    printf("\n");

    list_for_each_prev(plist, &my_list) {
        pnode = list_entry(plist, struct int_node, list);
        printf("%d ", pnode->val);
    }
    printf("\n");

    return 0;
}

虽然比较简单,记录下,学习linux 代码, 程序员的自我修养。

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • linux 远程登录执行命令

    方便自动化运维部署,在多台机器上自动执行命令。 ssh 需要输入密码, 所以使用 expect 进行交互,从执行文本读取远程主机 IP, 登录名和密码后执行远...

    orientlu
  • linux ssh 登录管理

    功能类似 xshell 这类终端管理工具,将需要登录的机器ip信息统一记录在一个host文件中,登录直接选择对应序号就好,减少重复输入ip,账号。

    orientlu
  • FreeRTOS 消息队列

    上面这几中方式中, 除了消息通知, 其他几种实现都是基于消息队列。消息队列作为主要的通信方式, 支持在任务间, 任务和中断间传递消息内容。 这一章介绍 Fre...

    orientlu
  • linux通用链表

    链表的主要意义就是将分散地址的数据域通过指针排列成有序的队列。因此数据域是链表不可或缺的一部分,但是在实际使用中需要不同类型的数据域,因此也就限制了链表的通用。...

    开源519
  • linux内核源码 -- list链表

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

    扫帚的影子
  • Python-列表+-01-两个列表各元素合并

    系统:Windows 7 语言版本:Anaconda3-4.3.0.1-Windows-x86_64 编辑器:pycharm-community-2016.3....

    zishendianxia
  • Python list(列表)

    Python一共有6种序列的内置类型,list和tuple是其中最常见的。6种序列的都可以进行的操作包括索引、切片,加(实际上是连接),乘(实际上是复制)...

    Steve Wang
  • Python 列表 list 数组 ar

    Python中的列表(list)类似于C#中的可变数组(ArrayList),用于顺序存储结构。

    py3study
  • R语言数据清洗实战——高效list解析方案

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

    数据小磨坊
  • 基于python的文件操作

    类似于数据库的基本操作增删改查,工作中会经常出现使用python完成文件操作。 本文作者实现文件操作相关函数。

    潇洒坤

扫码关注云+社区

领取腾讯云代金券