内核链表与Linux常用数据结构

0.这是什么?有什么用?
Linux大神将双向循环链表需要开发者对链表基本操作函数的封装,便于直接调用(复杂到用指针套了很多层指针,不过还有反转等功能哦)
使用:#include "kernel_list.h"

struct kernel_list{//宿主
struct student std;
struct list_head myList;//包含两个指针的(小)结构体
}

内核链表中封装好的这些宏函数以及普通函数绝大部分都是在对小结构体指针进行操作


1.先上来个式子热热身
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
含义:

2.大结构体(宿主)
小结构体
使用时要处理小结构体,操作小就能影响大

3.list_entry是什么

4.注意list_for_each的使用
list_for_each_entry:第一个参数不能传错
参数代表意思很重要
list_for_each_entry_safe
例子:
//重点:指定位置前插
int kernel_assign(struct kernel_list head ,struct kernel_list new ,char name){
struct kernel_list pos;
/
list_for_each list_for_each_entry_safe
/
list_for_each_entry(pos,&head->myList,myList){
if(strcmp(pos->stu.name,name)==0)
break;
}
//注意:这里的pos是大结构体的,不能直接用
pos->myList.prev->next = &new->myList;
new->myList.next = &pos->myList;
new->myList.prev = pos->myList.prev;//与下面交换,连接会断,转换处理
pos->myList.prev = &new->myList;//本来在第三,连接会断,所以放第四
/
list_add()又有什么不同
/
return 0;
//什么时候会要pos.myList=pos.myList->next;
}

5.坑:static inline void __list_add(struct list_head *new,struct list_head *prev,struct list_head *next)里三参数的解析

6.涉及知识点:static inline(多次调用的且循环较少或无循环的函数,牺牲空间实现快速调用) & 宏定义(带参数)

7.相关参考
http://blog.chinaunix.net/uid-27037833-id-3237153.html
http://blog.csdn.net/tigerjibo/article/details/8299599
http://blog.csdn.net/coding__madman/article/details/51325646

所有的内核链表的操作函数都是对小结构体进行操作的,不要错误理解成大结构体
(3)内核链表的遍历:
方法一:list_for_each()跟list_entry()相互配合实现遍历
方法二:list_for_each_entry(pos, head, member) 将方法一的二个宏函数合并了
pos ---》大结构体指针
head ---》小结构体指针
member ---》小结构体在大结构体中的名字
注意:第一个参数一定不要传参错误,是大结构体
方法三:list_for_each_entry_safe(pos, n, head, member) 往往在删除节点的时候使用
pos ---》大结构体指针
n ---》大结构体指针
head ---》小结构体指针
member ---》小结构体在大结构体中的名字
(4)删除
list_for_each_entry_safe(pos, n, head, member)
list_del(struct list_head *entry)
entry ---》你想要删除的那个节点里面的小结构体指针
(5)list_move(struct list_head *list,
struct list_head *head)
list_move() ---》将指定的节点移动到head的下一个位置
list_move_tail()---》将指定的节点移动到最后面
(6)container_of(ptr, type, member) 求ptr对应的大结构体
虽然内核链表没有给我们封装指定位置插入的函数,但是你可以自己去写,注意使用的指针是小结构体里面的next和prev
总结:(1)经过反复使用内核链表,加上分析了源码,我们发现内核链表跟前面学的双向循环链表的操作模式是类似的,只是要注意内核链表是操作的小结构体指针,所有在指针的写法上变得很啰嗦(自己体会,查看我写的最终代码)
(2)内核链表中封装的那个小结构体一般都写成普通结构体,注意在使用的时候取地址

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,214评论 6 481
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,307评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 152,543评论 0 341
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,221评论 1 279
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,224评论 5 371
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,007评论 1 284
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,313评论 3 399
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,956评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,441评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,925评论 2 323
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,018评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,685评论 4 322
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,234评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,240评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,464评论 1 261
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,467评论 2 352
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,762评论 2 345

推荐阅读更多精彩内容