概要 本文对双向链表进行探讨，介绍的内容是Linux内核中双向链表的经典实现和用法。其中，也会涉及到Linux内核中非常常用的两个经典宏定义offsetof和container_of。...内容包括： 1.Linux中的两个经典宏定义 2.Linux中双向链表的经典实现 Linux中的两个经典宏定义 倘若你查看过Linux Kernel的源码，那么你对 offsetof 和 container_of...这两个宏最初是极客写出的，后来在Linux内核中被推广使用。...内核的include/linux/kernel.h中定义。...Linux中双向链表的经典实现 1.Linux中双向链表介绍 Linux双向链表的定义主要涉及到两个文件： include/linux/types.h include/linux/list.h Linux
/******************** * 内核中链表的应用 ********************/ (1)介绍 在Linux内核中使用了大量的链表结构来组织数据，包括设备列表以及各种功能模块中的数据组织...这些链表大多采用在include/linux/list.h实现的一个相当精彩的链表数据结构。...和next，内核的数据结构通常组织成双循环链表。...和以前介绍的双链表结构模型不同，这里的list_head没有数据域。在Linux内核链表中，不是在链表结构中包含数据，而是在数据结构中包含链表节点。...内核提供了一组函数来操作链表。
linux kernel中的list估计已经被各位前辈们写烂了,但是我还是想在这里记录一下; linux kernel里的很多数据结构都很经典, list链表就是其中之一 本篇要介绍的内容: list...的定义 list提供的操作方法 注意事项 使用实例 ---- List 所在文件: List的所有操作可以在 include/linux/list.h找到; List head的定义可以在 include.../linux/types.h找到; 定义 实际上这就是一个双向循环链表, 且有一个头指针 list head的定义: struct list_head { struct list_head *next...,没任何的数据部分, 那我们基本上就知道了, 它不是被单独使用的,而是把它嵌入到用户定义的struct中, 将用户定义的数据结构串起来,作成list; 思想很巧妙, 对用户定义的数据结构侵入性很小, 实现了...list->next, list); list->prev = list; } 插入操作 将一个元素插入到两个元素之间, 即将 new插入到prev和next中, 这个函数是下面在头部和尾部插入的实现基础
printf("num = %d, math = %d\n", temp->num, temp->math); } printf("\n"); return 0; } 运行效果： 内核双链表效果图...其实关于内核中链表的操作还有很多的函数，目前就分析这几个。其余留给自己尝试。
描述 在linux内核中封装了一个通用的双向链表库，这个通用的链表库有很好的扩展性和封装性，它给我们提供了一个固定的指针域结构体，我们在使用的时候，只需要在我们定义的数据域结构体中包含这个指针域结构体就可以了...传统的链表结构 struct node{ int key; int val; node* prev; node* next; } linux 内核通用链表库结构 提供给我们的指针域结构体...方式一 list_add(&a->list,&head); list_add(&b->list,&head); //插入链表 方式二 list_add_tail(&a->list,&head); list_add_tail...就是student结构定义里的属性list //list_entry的原理有点复杂，也是linux内核的一个经典实现，这个在上面那篇链接文章里也有讲解 tmp_student = list_entry...内核提供的这个通用链表库里面还有很多其他的接口，这里没有详细的一一举例，有兴趣的可以自己去看看，在源码包 include/linux/list.h 文件里面，不过通过阅读一些源代码确实对我们也有很大的提高
应要求分享一下内核链表结构，故写了本blog。本文对内核链表做一个简单介绍，以及引出内核中大量使用的分离思想和数据结构的定义。...传统链表的困境 内核中数据结构千变万化，采用传统的链表结构形式，需要为各种数据都定义出一个链表。...内核链表 内核链表正是采用了如上的思想进行设计的，内核链表位于内核代码的include/linux/list.h中，该链表定义为双向循环链表，所有的相关操作都定义在该头文件中，该文件中每个函数极为简洁。...void list_add(struct list_head *new, struct list_head *head) { __list_add(new, head, head->next); } 使用内核链表的方式...= (head); \ pos = list_next_entry(pos, member)) 总结 内核中大量使用了该思想，凡是在物理内存中离散分布的结构，均采用此思想将结构嵌入到具体数据中实现数据的结构组织
接口定义 首先我们定义链表的基本接口,为了显示出 B 格，我们模仿我们 Java 中的 List 接口定义。...看起来是不是很像骚包，接着我们再抽象一个抽象类，后续我们还会继续写双向链表，循环链表。...双向循环链表。把他们的共性放在抽象类中，将不同点延迟到子类实现。...所以我们在单向链表定义一个静态内部类表示 Node 节点。 构造方法分别将数据构建成 Node 节点，默认 next 指针是 null。...在找到被删除的 cur 指针以及 cur 上一个节点指针 prev 后我们做删除操作，这里有三种情况：当链表只有一个节点的时候，当一个以上节点情况下分为删除头结点、尾节点、其他节点。
在 Linux 内核中使用最多的数据结构就是链表了，其中就包含了许多高级思想。 比如面向对象、类似C++模板的实现、堆和栈的实现。 1....链表简介 链表是一种常用的组织有序数据的数据结构，它通过指针将一系列数据节点连接成一条数据链，是线性表的一种重要实现方式。...如果去掉前驱指针，就是单循环链表。 ? 2. 内核链表 在Linux内核中使用了大量的链表结构来组织数据，包括设备列表以及各种功能模块中的数据组织。...这些链表大多采用在[include/linux/list.h]实现的一个相当精彩的链表数据结构。事实上，内核链表就是采用双循环链表机制。 内核链表有别于传统链表就在节点本身不包含数据域，只包含指针域。...总结 本文详细分析了 linux 内核 中的双链表结构，以图文的方式旨在帮助大家理解。
前言： 在上期文章中，已经给大家分享过offsetof()和container_of两个宏函数，这两个宏函数在Linux内核链表里面有大量的应用，对于我们平时工作写代码有很大的帮助。...下面是Linux内核链表的内容分享。...做内核驱动开发经常会使用linux内核最经典的双向链表 list_head， 以及它的拓展接口(或者宏定义)： list_add , list_add_tail, list_del , list_entry...; }; 然后就开始围绕这个结构开始构建链表，然后插入、删除节点 ，遍历整个链表等等，其实内核已经提供好了现成的接口，接下来就让我们进入 kernel/include/linux/list.h中： 一...那接下来让我们揭开她的面纱：此宏在内核代码 kernel/include/linux/kernel.h中定义（此处kernel版本为3.10；新版本4.13之后此宏定义改变，但实现思想保持一致） /**
EPOLL_CTL_DEL EPOLL_CTL_DEL 的实现调用的是 ep_remove 函数，函数只是清除ADD时， 添加的各种结构，EPOLL_CTL_MOD 的实现调用的是ep_modify...，在ep_modify中用新的事件掩码调用f_ops->poll，检测事件是否已可用，如果可用就直接唤醒epoll，这两个的实现与EPOLL_CTL_ADD 类似，代码上比较清晰，这里就不具体分析了。...wait_queue_t wait; ktime_t expires, *to = NULL; if (timeout > 0) { // 转换为内核时间...unsigned int revents; struct epitem *epi; struct epoll_event __user *uevent; // 遍历已就绪链表...mutex_lock_nested(&ep->mtx, depth); spin_lock_irqsave(&ep->lock, flags); // 移动rdllist 到新的链表
目前Linux内核主线不支持软实时，而是使用下面2个仓库存放和Linux内核主线的版本对应的实时内核的源代码。...(3)如果使用内核线程执行中断处理函数，那么原来禁止硬中断的临界区不需要禁止硬中断，为了兼顾非实时内核和实时内核，引入本地锁，非实时内核把本地锁映射到禁止内核抢占和禁止硬中断，实时内核把本地锁映射到基于实时互斥锁实现的自旋锁...(3)在实时内核中大多数禁止内核抢占的临界区可以变成可抢占的，为了兼顾非实时内核和实时内核，引入本地锁，非实时内核把本地锁映射到禁止内核抢占和禁止硬中断，实时内核把本地锁映射到使用实时互斥锁实现的自旋锁...(2)“Voluntary Kernel Preemption (Desktop)”，自愿内核抢占，配置宏是CONFIG_PREEMPT_VOLUNTARY。这种模型通过增加抢占点的方式减小延迟。...14.参考文档 (1)A realtime preemption overview，https://lwn.net/Articles/146861/，（说明：Linux内核没有完全按照这篇文档实现） (
copy on write）技术提高效率 COW并不会复制整个地址空间，而是让父子进程以只读方式共享内存，数据的复制只有在写入时才进行 3.3 fork函数 linux通过clone()系统调用实现fork...线程在linux中的实现 4.1 liunx线程概述 一组线程共享进程内的内存地址空间，打开的文件和其他资源 线程机制支持并发程序设计技术，多处理器上保证真正的并行处理 linux实现线程的机制非常独特...概述 调度程序是内核组成部分，它负责选择下一个要运行的进程 调度程序负责给可运行进程分配处理器时间资源 多任务系统可分为：抢占式任务（linux等现代操作系统的方式）和非抢占式任务 分配给每个进程的执行时间叫做时间片...调度算法 3.1 概述 linux调度程序定义与kernel/sched.c 2.5版本内核重写调度算法，和以前版本区别很大，实现以下目标 充分实现O（1）调度，不管多少进程或什么输入，每个算法能在恒定时间内完成...内核同步方法 2.1 原子操作 原子操作保证指令以原子方式执行 原子操作通常是内联函数，通过内嵌汇编指令完成 原子操作比其他同步方法给系统的开销小 linux内核提供对整数和单独对位进行的原子操作 整数原子操作相关函数为
链表是基本数据结构， 一开始学习数据结构时， 我一般这么定义， 对应实现从头或尾插入的处理函数， struct int_node_old { int val; struct int_node_old...想起前段时间， 看到FreeRTOS提供的链表处理方式（《 FreeRTOS 任务调度 List 组织 》）， 将链表结构定义和实际使用时具体节点数据内容分开定义， 供系统各个模块使用。...查看linux的源码， 发现linux中也为我们提供了相似的实现（源码）, 把一些共性统一起来。 类是 python 中for_each处理，有些意思。...linux 下的链表定义在文件 include/linux/types.h， 采用的是双向列表 struct list_head { struct list_head *next, *prev;...list 利用这个定义， 我定义了一个自己的list数据结构， 并copy了一些接口实现，感受下，linux 是如何管理链表的。
每日福利 “你，听过双向链表吗？”...“恩恩，最简单的线性数据组织……” “装逼，知道它的优缺点吗” “恩恩，插入删除快速，遍历比较慢，而且……” “行了，知道内核链表吗” “恩恩，传统链表没有实现逻辑分离，因此操作接口……” “喂！...“……”一脸懵逼的面试官 废话少讲，传统链表如下： ? 特点： 节点既包含了后续节点的指针，也包含了前趋节点的指针，而且一般都设计成循环，这样就可以非常方便地从链表的任意一个位置开始遍历整个链表。...内核链表如下： ? 特点： 把传统链表中的“链”抽象出来，使之成为一条只包含前后指针的纯粹的双循环链表，这样的链表由于不含有特殊的数据，因此它实质上就是链表的抽象。...最后将这样的标准链表镶嵌到具体节点里面。 内核链表通过将数据与逻辑分离，实现了统一管理Linux内核中成千上万种节点的操作，这种抽象方法在内核各个子系统中都有应用，比如设备模型管理，比如网络子系统等。
BLOCK_SIZE在fs.h中的定义为 #define BLOCK_SIZE 1024 因此两个可变参数NR_BUFFERS和NR_BUFFERS*BLOCK_SIZE都为int类型； 以前已经分析过可变参数的一系列实现函数...我们先不管write函数的实现，首先来看vsprint。...break; 138 } 139 } 140 *str = '\0';//设定str字符串的最后一位为'\0' 141 return str-buf;//返回值为字符串的长度 142 这样我们就实现了根据...分析同上 而write函数跟fork函数一样是由_syscall*来实现的，内嵌汇编就不多解释了，直接展开就行 write.c _syscall3(int,write,int,fd,const char
ECMP在不同版本的Linux内核实现方式不一样，总体上可分为4个阶段。 内核版本ECMP功能< Pre kernel v2.2无ECMP。...在内核中该变量是：“ip_rt_gc_timeout”。...内核的实现的关键变更历史。...时间：1997.11 版本：Pre kernel v2.2 事件：“IPV4 ECMP”实现被加入内核。.../kernel/git/torvalds/linux.git/commit/?
在实际的工作中，我们可能会经常使用链表结构来存储数据，特别是嵌入式开发，经常会使用linux内核最经典的双向链表 list_head。...本篇文章详细介绍了Linux内核的通用链表是如何实现的，对于经常使用的函数都给出了详细的说明和测试用例，并且移植了Linux内核的链表结构，在任意平台都可以方便的调用内核已经写好的函数。...链表简介 链表是一种常用的组织有序数据的数据结构，它通过指针将一系列数据节点连接成一条数据链，是线性表的一种重要实现方式。...Linux内核中的链表 上面介绍了普通链表的实现方式，可以看到数据域都是包裹在节点指针中的，通过节点指针访问下一组数据。...但是 Linux内核的链表实现可以说比较特殊，只有前驱和后继指针，而没有数据域。链表的头文件是在include/list.h（Linux2.6内核）下。
文中涉及的代码可访问 GitHub:https://github.com/UniqueDong/algorithms.git 上一篇《链表导论心法》讲解了链表的理论知识以及链表操作的实现原理。...接口定义 首先我们定义链表的基本接口,为了显示出 B 格，我们模仿我们 Java 中的 List 接口定义。...看起来是不是很像骚包，接着我们再抽象一个抽象类，后续我们还会继续写双向链表，循环链表。...双向循环链表。把他们的共性放在抽象类中，将不同点延迟到子类实现。...课后思考 Java 中的 LinkedList 是什么链表结构呢？ 如何使用 java 中的LinkedList 实现一个 LRU 缓存淘汰算法呢？
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频
