15 Linux内核链表.ppt

《15 Linux内核链表.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Linux内核链表Linux内核链表链表是一种常用的数据结构，它通过指针将一系列数据节点连接成一条数据链。相对于数组，链表具有更好的动态性，建立链表时无需预先知道数据总量，可以随机分配空间，可以高效地在链表中的任意位置实时插入或删除数据。链表的开销主要是访问的顺序性和组织链的空间损失。简介通常链表数据结构至少包含两个域：数据域和指针域，数据域用于存储数据，指针域用于建立与下一个节点的联系。按照指针域的组织以及各个节点之间的联系形式，链表又可以分为单链表、双链表、循环链表等多种类型。单向链表双向链表内核链表在Linux内核中使用了大量

2、的链表结构来组织数据。这些链表大多采用了[include/linux/list.h]中实现的一套精彩的链表数据结构。内核链表链表数据结构的定义：structlist_head{structlist_head*next,*prev;};list_head结构包含两个指向list_head结构的指针prev和next，由此可见，内核的链表具备双链表功能，实际上，通常它都组织成双向循环链表。链表操作Linux内核中提供的链表操作主要有：初始化链表头INIT_LIST_HEAD(list_head*head)插入节点list_add(str

3、uctlist_head*new,structlist_head*head)list_add_tail(structlist_head*new,structlist_head*head)链表操作删除节点list_del(structlist_head*entry)提取数据结构list_entry(ptr,type,member)已知数据结构中的节点指针ptr，找出数据结构，例：list_entry(aup,structautofs,list)链表操作遍历list_for_each(struclist_head*pos,strucli

4、st_head*head)例：structlist_head*entry;structlist_headcs46xx_devs;//链表头list_for_each(entry,&cs46xx_devs){card=list_entry(entry,structcs_card,list);if(card->dev_midi==minor)break;}实验内核链表操作编写内核模块1、完成结点的插入3、完成结点的删除2、完成链表的遍历（遍历时访问结点中的数据）