想起前段时间， 看到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 是如何管理链表的。...另外一种做法是定义list_head中， 包含一个成员变量，指向其所属，FreeRTOS是如此做的。
前言： 在上期文章中，已经给大家分享过offsetof()和container_of两个宏函数，这两个宏函数在Linux内核链表里面有大量的应用，对于我们平时工作写代码有很大的帮助。...下面是Linux内核链表的内容分享。...做内核驱动开发经常会使用linux内核最经典的双向链表 list_head， 以及它的拓展接口(或者宏定义)： list_add , list_add_tail, list_del , list_entry...; }; 然后就开始围绕这个结构开始构建链表，然后插入、删除节点 ，遍历整个链表等等，其实内核已经提供好了现成的接口，接下来就让我们进入 kernel/include/linux/list.h中： 一...2. list_add_tail 接口 ： 上面所讲的list_add接口是从链表头header后添加的节点。同样，内核也提供了从链表尾处向前添加节点的接口list_add_tail.
描述 在linux内核中封装了一个通用的双向链表库，这个通用的链表库有很好的扩展性和封装性，它给我们提供了一个固定的指针域结构体，我们在使用的时候，只需要在我们定义的数据域结构体中包含这个指针域结构体就可以了...传统的链表结构 struct node{ int key; int val; node* prev; node* next; } linux 内核通用链表库结构 提供给我们的指针域结构体...内核中是一个常用的宏，用于从包含在某个 //结构中的指针获得结构本身的指针，通俗地讲就是通过结构体变 //量中某个成员的首地址进而获得整个结构体变量的首地址 #define container_of(ptr...方式一 list_add(&a->list,&head); list_add(&b->list,&head); //插入链表 方式二 list_add_tail(&a->list,&head); list_add_tail...list_add-先入先出模式 我们的链表节点，实际在内存中的展示形态 ?
linux kernel中的list估计已经被各位前辈们写烂了,但是我还是想在这里记录一下; linux kernel里的很多数据结构都很经典, list链表就是其中之一 本篇要介绍的内容: list.../linux/types.h找到; 定义 实际上这就是一个双向循环链表, 且有一个头指针 list head的定义: struct list_head { struct list_head *next...思想很巧妙, 对用户定义的数据结构侵入性很小, 实现了c++中std::List模板的功能; 虽然这个定义是叫head, 但其实嵌入到用户定义的数据结构中的也是这个....__list_del_entry(list); // 添加到新链表的头部 list_add(list, head); } 将一个元素移动到另一个list的队尾 static...struct中,这个宏就是由这个list_head ptr来获取当前所处的struct对象的指针, 用了linux的经典宏定义 container_of #define list_entry(ptr,
在实际的工作中，我们可能会经常使用链表结构来存储数据，特别是嵌入式开发，经常会使用linux内核最经典的双向链表 list_head。...本篇文章详细介绍了Linux内核的通用链表是如何实现的，对于经常使用的函数都给出了详细的说明和测试用例，并且移植了Linux内核的链表结构，在任意平台都可以方便的调用内核已经写好的函数。...Linux内核中的链表 上面介绍了普通链表的实现方式，可以看到数据域都是包裹在节点指针中的，通过节点指针访问下一组数据。...但是 Linux内核的链表实现可以说比较特殊，只有前驱和后继指针，而没有数据域。链表的头文件是在include/list.h（Linux2.6内核）下。...在实际工作中，也可以将内核中的链表拷贝出来供我们使用，就需不要造轮子了。 链表的定义 内核链表只有前驱和后继指针，并不包含数据域，这个链表具备通用性，使用非常方便。
概要 本文对双向链表进行探讨，介绍的内容是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...中双向链表的使用思想 它是将双向链表节点嵌套在其它的结构体中；在遍历链表的时候，根据双链表节点的指针获取"它所在结构体的指针"，从而再获取数据。
在 Linux 内核中使用最多的数据结构就是链表了，其中就包含了许多高级思想。 比如面向对象、类似C++模板的实现、堆和栈的实现。 1....如果去掉前驱指针，就是单循环链表。 ? 2. 内核链表 在Linux内核中使用了大量的链表结构来组织数据，包括设备列表以及各种功能模块中的数据组织。...这些链表大多采用在[include/linux/list.h]实现的一个相当精彩的链表数据结构。事实上，内核链表就是采用双循环链表机制。 内核链表有别于传统链表就在节点本身不包含数据域，只包含指针域。...2.3 添加节点 内核相应的提供了添加节点的接口： list_add list_add 如下，最终调用的是__list_add 函数，根据注释可知，list_add 是头部插入，总是在链表的头部插入一个新的节点...总结 本文详细分析了 linux 内核 中的双链表结构，以图文的方式旨在帮助大家理解。
引言 链表的实现是基于结构体与指针两者实现的，常用的链表数据结构如下： //将int起别名ELEMTYPE，是为了方便修改链表中的数据域类型。...在Linux中设计了一种适合于各种类型数据域都可以使用的通用型链表： struct list_head { struct list_head *prev, *next; }; 摒弃掉数据域，只保留头尾指针...内核链表 链表的主要意义就是将分散地址的数据域通过指针排列成有序的队列。因此数据域是链表不可或缺的一部分，但是在实际使用中需要不同类型的数据域，因此也就限制了链表的通用。...Linux中在声明中抛弃了数据域，也就解决掉了这一问题。 原理 Linux使用链表的方法：使用时，自定义结构体包含数据域+链表结构体。...链表.png 如上图所示，将结构体A、B、C中的内核结构体指针构建成双链表，这样结构体A、B、C中的链表成员就可以互相索引了。
链表结构介绍 在前面章节已经学习了数组的使用，数组的空间是连续空间，数组的大小恒定的，在很多动态数据存储的应用场景下，使用不方便；而这篇文章介绍的链表结构，支持动态增加节点，释放节点，比较适合存储动态数据的应用场景...实现的功能如下: 初始化链表头 插入节点的函数(链表任意位置插入，链表尾插入) 删除节点的函数（链表任意位置删除、链表尾删除） 遍历链表，输出链表里的所有信息 #include #include...在链表尾插入数据 list_add(10,list_head); list_add(11,list_head); list_add(12,list_head); list_add...在链表尾插入数据 list_add(10,list_head); list_add(11,list_head); list_add(12,list_head); list_add...添加链表节点*/ list_add(10,list_head); list_add(11,list_head); list_add(12,list_head); list_add
伙伴系统是常用的内存分配算法，linux内核的底层页分配算法就是伙伴系统，伙伴系统的优点就是分配和回收速度快，减少外部碎片。...然后又看了一下linux4.8的buddy system实现，linux的buddy system主要进行page分配也是linux最底层的分配，其他的分配算法都是以这个分配为基础，在x86架构下一个page...linux对内存进行了分区包括低端内存区，高端内存区，dma区，而且还对numa架构做了很多处理，对页面也进行了分类，这些不是讨论的重点，现在主要是提取linux的buddy算法，只提取核心部分，可以在控制台下运行...buddy system的数据结构就是下图所示，看着像哈希表中的拉链法，每个链表保存相同大小的内存块。最大的是10，也就是1024个基本单位，所以linux在x86下一次最多可分配4MB内存。 ...顺便学习下linux内核对链表的各种操作，代码实现 #include #include #include #include <assert.h
(new, head->prev, head); } static void list_add(struct list_head *new, struct list_head *head) { _..._list_add(new, head, head->next); } static void __list_del(struct list_head *prev, struct list_head...printf("num = %d, math = %d\n", temp->num, temp->math); } printf("\n"); return 0; } 运行效果： 内核双链表效果图...： 大体的效果图就是如此，增加一个节点，删除一个节点都是基于这个模型展开的。...读者可以手动画画增加和删除的操作。 其实关于内核中链表的操作还有很多的函数，目前就分析这几个。其余留给自己尝试。
应要求分享一下内核链表结构，故写了本blog。本文对内核链表做一个简单介绍，以及引出内核中大量使用的分离思想和数据结构的定义。...传统链表的困境 内核中数据结构千变万化，采用传统的链表结构形式，需要为各种数据都定义出一个链表。...内核链表 内核链表正是采用了如上的思想进行设计的，内核链表位于内核代码的include/linux/list.h中，该链表定义为双向循环链表，所有的相关操作都定义在该头文件中，该文件中每个函数极为简洁。...(struct list_head *new, struct list_head *head) { __list_add(new, head, head->next); } 使用内核链表的方式，将链表节点嵌入到数据结构体中...*fops; struct list_head list; /* 用内核链表管理所有注册在内核中的misc设备 */ struct device *parent; struct
\n"); return; } // 2.操作pos的前后节点，使他们联系起来。...1.kernel_list.h #ifndef __DLIST_H #define __DLIST_H /* This file is from Linux Kernel (include/linux...\n"); return; } // 1.遍历链表，对比找到指定节点，找到则跳出break // 如果在遍历中删除、移动节点，必须使用安全模式 // 如果只是遍历访问，不修改节点，使用安全...node, list); // if(get_node->data%2 == 0) // list_move_tail(pos, &head->list); // } // 自行添加的前序遍历安全模式...\n"); return; } // 1.遍历链表，对比找到指定节点，找到则跳出break // 如果在遍历中删除、移动节点，必须使用安全模式 // 如果只是遍历访问，不修改节点，使用安全
} list_del(&(page->page_link)); //删掉原先链表中的节点 nr_free -= n; ClearPageProperty(page...考虑first-fit算法，在释放页的时候应该按照大小顺序插入链表，但该函数里面仍采用了list_add函数， static void default_free_pages(struct Page *base...算法是通过采用链表来实现查找的，实际上可以采用更高效的数据结构比如bst,红黑树这些。...challenge 1 我的建议是仔细阅读文档里给的链接:coolshell 伙伴分配的实质就是一种特殊的“分离适配”，即将内存按2的幂进行划分，相当于分离出若干个块大小一致的空闲链表，搜索该链表并给出同需求最佳匹配的大小...Kiprey就是采用双向链表实现，内存上的开销会比较小，但在双向链表中难以确定块之间的合并操作。ZebornDuan采用了二叉树实现，我决定参考他的代码写一写。
本文讨论的是不带头节点的双向循环链表，如下图： [qowp0vrk7c.png] 2. 双向循环链表的实现 TencentOS-tiny中的双向链表实现在tos_list.h中。 2.1....插入节点 向双向链表中插入一个节点非常简单： void _list_add(k_list_t *node, k_list_t *prev, k_list_t *next) { next->prev...插入前的双向循环链表如下： [12x9hk0jf4.png] 插入后的双向循环链表如下： [g8b3e5w8ks.png] 图中的四个插入过程分别对应代码中的四行代码。...{ _list_add(node, list->prev, list); } 因为是双向循环链表，所以尾部插入是在第一个节点和最后一个节点之间插入。...TencentOS-tiny中依然提供了两个宏定义来解决这一问题，在tos_klib.h中。
相较于其他形式的链表，双向循环链表的添加节点，删除节点，遍历节点都非常的简单。 2. 双向循环链表的实现 TencentOS-tiny中的双向链表实现在tos_list.h中。 2.1....插入节点 向双向链表中插入一个节点非常简单： void _list_add(k_list_t *node, k_list_t *prev, k_list_t *next) { next->prev...插入前的双向循环链表如下： ? 插入后的双向循环链表如下： ? 图中的四个插入过程分别对应代码中的四行代码。...{ _list_add(node, list->prev, list); } 因为是双向循环链表，所以尾部插入是在第一个节点和最后一个节点之间插入。...TencentOS-tiny中依然提供了两个宏定义来解决这一问题，在tos_klib.h中。
****************************************** 文件内容:内核之链队操作 版本V1.0 作者：HFL 时间：2013-12-22 说明：用户态中链表每个节点包含数据域和指针域...，而内核态是每个数据中包含链表 因此内核态链表一般是嵌套在某个包含数据成员的结构体来实现。...内核的链表应用非常广泛：进程管理，定时器，工作队列，运行队列。总之 内核对于多个数据的组织和多个熟悉的描述都是通过链表串起来的。 ... #include #include #include MODULE_DESCRIPTION...{ sprintf(Mystudent[i].name,"Student%d",j+1); Mystudent[j].counter = j+1; list_add
Linux内存管理是一个非常复杂的子系统，要完全说清的话估计要一本书的篇幅。但Linux内存管理可以划分成多个部分来阐述，这篇文章主要介绍slab算法。...Linux有个叫伙伴系统的分配算法，这个算法主要解决分配连续个内存页的问题。...在kmem_cache_t结构中的slab_free链表的slab是内存回收的主要备选对象。由于对象是从slab中分配和释放，所以单个slab可以在slab列表中进行一定。...4) 初始化slab_full / slab_partial / slab_free链表。5) 把申请的kmem_cache_t对象保存到cache_chain链表中。...的空闲对象链表中，然后根据slab的使用情况移动slab到合适的列表中。
数据结构 使用三个链表分别记录管理当前的freelist，依据其size不同进行划分： 0 ~ 256 Bytes，添加到small list中，后续分配即在此list中查询； 256 ~ 1024 Bytes...slob_list中 static void set_slob_page_free(struct page *sp, struct list_head *list) { list_add(&...= prev->next) list_move_tail(slob_list, prev->next); //将page2从链表中移除，插入到head->next static inline void..., head); //__list_add(slob_list, page2->prev, page2); } static inline void __list_add(struct list_head.../include/linux/list.h 涉及到list操作的定义实现部分 /include/linux/kernel.h 涉及到相关宏的依赖 /include/linux/mm_types.h
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
即时通信 IM
ICP备案
云直播
实时音视频
