江都建设招标网站,做网站怎么给图片加连接,html企业网站模板免费下载,s9视频直播前言#xff1a;linux内核中有很多经典的数据结构#xff0c;list(也称list_head)为其中之一#xff0c;这些数据结构都是使用C语言实#xff0c;并且定义和实现都在单独的头文件list.h中。可以随时拿出来使用。list.h的定义不同linux发行版本路径不同,我们可以在/usr/incl…前言 linux内核中有很多经典的数据结构list(也称list_head)为其中之一这些数据结构都是使用C语言实并且定义和实现都在单独的头文件list.h中。可以随时拿出来使用。list.h的定义不同linux发行版本路径不同,我们可以在/usr/include目录下find。 虽然list_head是基于C语言实现但其设计初衷是使用在linux内核中所以其中用了许多GUN的方法而并非C标准如typeof该宏的作用是获取变量类型。所以list_head存在一定的平台相关性如果要做跨平台需要进行改造。现我们只对内核原始list_head进行详细说明及实例演示。原理list_head属于一个双向循环链表表头只是一个指针。当链表为空时表头的前驱和后继分别指向自己。 list_head的特点 不包含数据链表中只有prev和next这样使得我们的链表使用起来就比较灵活使用时只需要将其包含进使用的对象即可有一种面向对象的感觉。例如在使用时只需要在宿主结构中嵌入list_head类型节点并将节点插入到list_head表头中。 这样多个宿主结构体内容就通过链表关联了起来。使用时只需要使用宿主结构中的list_head节点反推宿主结构体的首地址就可以访问宿主结构体。 相对于传统链表的包含数据解决了链表结构冗余通用性差不方便移植等问题。 该链表不包含互斥锁所以在多线程使用下需要加互斥锁进行同步如下 struct list_item { list_head list; pthread_mutex_t lmutex; } struct list_item g_list_item;//包含了链表头及互斥锁。 链表定义 struct list_head { struct list_head *next, *prev; };实现方法函数说明作用接口类型函数原型参数说明函数说明备注增加内部接口static inline void __list_add(struct list_head *xnew, struct list_head *prev,struct list_head *next){ next-prev xnew; xnew-next next; xnew-prev prev; prev-next xnew;}xnew:新增节点prev:插入位置的前一个节点next:插入位置的后一个节点双向循环链表的插入。对于双向循环链表节点插入时我们一般需要考虑4个元素插入节点前驱插入节点后继插入位置前的一个节点后继插入位置后的一个点解前驱所以这里的prev我们可以理解为插入位置前的一个节点next则为插入位置后的一个节点增加对外接口static inline void list_add(struct list_head *xnew, struct list_head *head){ __list_add(xnew, head, head-next);}xnew:新增节点head:链表头头插法的方式插入链表。尾插与头插不同从这里调用__list_add函数时传参进行区分。增加对外接口static inline void list_add_tail(struct list_head *xnew, struct list_head *head){ __list_add(xnew, head-prev, head);}xnew:新增节点head:链表头尾插法的方式插入链表。删除内部接口static inline void __list_del(struct list_head * prev, struct list_head * next){ next-prev prev; prev-next next;}prev:要删除节点的前驱。next:要删除节点的后继。将要删除节点的前驱作为下一个节点的前驱将后继作为前一个节点的后继这样要删除的节点就与原链表断开。同时该节点删除后该节点原先的前驱和后继连了起来保证了链表不产生断点。删除对外接口static inline void list_del(struct list_head *entry){ __list_del(entry-prev, entry-next); entry-next LIST_POISON1; entry-prev LIST_POISON2;}entry:要删除的节点删除节点并将节点的next,prev分别指向LIST_POISON1LIST_POISON2。两个函数都调用了__list_del函数但是list_del最后将prev,next分别指向了LIST_POSTION2和LIST_POSTION1两个特殊位置对这两个位置的访问会引起页故障。属于不安全函数而list_del_init最后调用INIT_LIST_HEAD将next,prev都指向了自己属于安全函数。一般建议使用list_del_init。注意如果链表中的节点是通过malloc或new申请的看空间这里调用删除接口后需要取手动释放空间删除对外接口static inline void list_del_init(struct list_head *entry){ __list_del(entry-prev, entry-next); INIT_LIST_HEAD(entry);}entry:要删除的节点删除节点并将节点的next,prev指向自己即初始化。替换对外接口static inline void list_replace(struct list_head *old, struct list_head *xnew){ xnew-next old-next; xnew-next-prev xnew; xnew-prev old-prev; xnew-prev-next xnew;}old被替换的节点new替换节点使用新的节点替换原有的旧节点。通过实现可以看出list_replace函数替换后old节点与new节点指向的前驱和后继都一样属于不安全函数而list_replace_init则会将old的前驱和后继分开属于安全函数一般建议使用list_replace_init。替换对外接口static inline void list_replace_init(struct list_head *old, struct list_head *xnew){ list_replace(old, xnew); INIT_LIST_HEAD(old);}old被替换的节点new替换节点使用新的节点替换原有的旧节点。移动对外接口static inline void list_move(struct list_head *list, struct list_head *head){ __list_del(list-prev, list-next); list_add(list, head);}list要移动的节点head表头移动节点到head之后移动接口如果的操作的是非链表内部元素则相当于增加接口的作用。移动对外接口static inline void list_move_tail(struct list_head *list,struct list_head *head){ __list_del(list-prev, list-next); list_add_tail(list, head);}list要移动的节点head表头移动节点到head之前判空对外接口static inline int list_empty(const struct list_head *head){ return head-next head;}head表头判断链表是否为空返回1表示链表为空0表示非空。判空对外接口static inline int list_empty_careful(const struct list_head *head){ struct list_head *next head-next; return (next head) (next head-prev);}head表头判断链表是否为空返回1表示链表为空0表示非空。因为内核在运行时候可能有多个进程同时修改内存判断链表是否为空需要判断他的前一个节点和后一个节点是否为空。但是注释也承认了这种判断方法的不安全性要是保证安全操作还需要加锁保护。判断是否为最后一个节点对外接口static inline int list_is_last(const struct list_head *list, const struct list_head *head){ return list-next head;}list当前节点head链表表头判断当前节点是否为链表的最后一个节点。链表合并内部接口static inline void __list_splice(const struct list_head *list, struct list_head *prev,struct list_head *next){ struct list_head *first list-next; struct list_head *last list-prev; first-prev prev; prev-next first; last-next next; next-prev last;}list被合并的链表prev合并位置的前一个节点next合并位置的后一个节点ist作为被合并链表的表头合并相当于将一个链表作为一个整体插入到另一个链表的某一个位置。first作为表头list的后继last作为表头list的前驱表头list的后继的前驱(first→prev)指向合并位置的前一个节点表头list的前驱的后继(last→next)指向合并位置的后一个节点。注意合并后的方要保持一致还是一个环形。链表合并对外接口static inline void list_splice(struct list_head *list, struct list_head *head){ if (!list_empty(list)) __list_splice(list, head, head-next);}list被合并的链表head将list合并到head链表将list链表合并到head链表合并方式为头插法合入即将list加入到head之后。该函数内部实现调用了__list_splice合并原理见__list_splice详细说明list_splice于list_splice_init的区别是list_splice_init在合并后将list进行了初始化属于安全函数。建议使用list_splice_init链表合并对外接口static inline void list_splice_init(struct list_head *list, struct list_head *head){ if (!list_empty(list)) { __list_splice(list, head, head-next); INIT_LIST_HEAD(list); }}链表合并对外接口static inline void list_splice_tail(struct list_head *list,struct list_head *head){ if (!list_empty(list)) __list_splice(list, head-prev, head);}list被合并的链表head将list合并到head链表将list链表合并到head链表合并方式为尾插法合入即将list加入到head之前。list_splice_tail于list_splice_tail_init的区别是list_splice_tail_init在合并后将list进行了初始化属于安全函数。建议使用list_splice_tail_init链表合并对外接口static inline void list_splice_tail_init(struct list_head *list,struct list_head *head){ if (!list_empty(list)) { __list_splice(list, head-prev, head); INIT_LIST_HEAD(list); }}部分宏说明附demo宏定义实现说明备注offsetof#define offsetof(TYPE, MEMBER) ((size_t) ((TYPE *)0)-MEMBER)获取变量在宿主结构中的偏移量TYPE*0 这个是欺骗编译器有一个TYPE类型的指针它的地址是0然后对这个指针的MEMBER取地址因为基地址是0所以对MEMBER取地址后就是MEMBER在TYPE中的偏移量了。 欺骗编译器的用法类似如下 int *p (int *)0; 打印p的地址是nilcontainer_of#define container_of(ptr, type, member) (\ {const typeof( ((type *)0)-member ) *__mptr (ptr);\ (type *)( (char *)__mptr - offsetof(type,member) );})根据结构中某个成员的地址获取宿主结构的地址ptr成员地址。type宿主结构类型。member宿主结构中定义的成员。与ptr同类型。使用与list_entry相同。由于type是类型member是成员所以这里还是使用(type *)0)-member则表示type类型指针的member成员然后用typeof取member的类型这样__mptr就与member成员类型是一样的最终目的还是为了定义一个与ptr类型相同的中间变量并且将ptr赋值给它。 (type *)( (char *)__mptr - offsetof(type,member) ); 这一步骤是通过成员现地址减去成员偏移量计算宿主结构体首地址这里必须对mptr强转成(char*)类型指针原因是指针加减操作不同于我们int变量的加减 比如指针的1操作是指针当前地址1*N(指针类型大小)。强转成char*后n就是指针当前地址n。如果不强转直接偏移会越界。 其实定于中间变量这一步我们可以省略因为我们是通过成员prt的地址来计算宿主结构体的首地址所以我们可以直接使用ptr现对container_of改造如下 #define container_of(ptr, type, member) (\ {(type*)((char *)ptr - offsetof(type,member));})list_entry#define list_entry(ptr, type, member) \ container_of(ptr, type, member)根据成员ptr的地址获取宿主结构体的首地址。type宿主结构体的类型。memberptr在宿主结构体中的成员变量名。struct student{ char name[32]; int age; struct list_head list;};ptr则表示一个一个list_head类型的指针type则是struct student类型member则是成员变量list。list_first_entry#define list_first_entry(ptr, type, member) \ list_entry((ptr)-next, type, member)根据成员ptr的地址获取ptr下一个节点的宿主结构体首地址。type宿主结构体的类型memberptr在宿主结构体中的成员变量名。同list_entrylist_for_each#define list_for_each(pos, head) \ for (pos (head)-next; pos ! (head); \ pos pos-next)从head之后的一个节点开始向后循环一般与list_entry或其它方法配合使用。循环时节点无法操作。poslist_head类型的指针。head链表头。void Data_list_for_each(){ struct list_head *postion NULL; struct student *p NULL; /* 参数1:struct list_head结构体指针 参数2:头指针 */ //list_for_each_prev(postion,g_list) list_for_each(postion,g_list) { /* 参数1struct list_head结构体指针 参数2链表容器结构体类型这里即struct student 参数3链表容器中链表的成员变量 */ //二选一list_entry的实现内部其实调用了container_of p list_entry(postion,struct student,list); //p container_of(postion,struct student,list); printf(%s-%d\n,p-name,p-age); } return;}list_for_each_prev#define list_for_each_prev(pos, head) \ for (pos (head)-prev; pos ! (head); \ pos pos→prev)从head之后的一个节点开始向前循环一般与list_entry或其它方法配合使用。poslist_head类型的指针。head链表头。list_for_each_safe#define list_for_each_safe(pos, n, head) \ for (pos (head)-next, n pos-next; pos ! (head); \ pos n, n pos-next)list_for_each的安全版本循环时可以操作节点。从该宏的实现我们可以看到相对于list_for_each多了一个临时变量nvoid Data_list_del_1(){ struct list_head *postion NULL; struct list_head *tmp NULL; struct student *p NULL; list_for_each_safe(postion,tmp,g_list) { p list_entry(postion,struct student,list); list_del(p-list); //list_del_init(p-list); free(p); } return;}list_for_each_entry#define list_for_each_entry(pos, head, member) \ for (pos list_entry((head)-next, typeof(*pos), member); \ pos-member ! (head); \ pos list_entry(pos-member.next, typeof(*pos), member))与list_for_each功能相似只是参数不同这里的pos是宿主结构体类型我们可以理解为这个就是list_for_each与list_entry的使用结合体。比如我们要使用list_for_each对链表进行遍历并且遍历宿主结构体时就需要与list_entry进行配合。list_for_each_entry刚好实现了这个功能。pos宿主结构体类型指针。head链表头。member宿主结构中链表的成员变量。void Data_list_for_each_entry(){ struct student *p NULL; /* 参数1链表容器结构体指针 参数2头指针 参数3链表容器中链表的成员变量 */ list_for_each_entry(p,g_list,list) { printf(%s-%d\n,p-name,p-age); } return;}list_for_each_entry_reverse#define list_for_each_entry_reverse(pos, head, member) \ for (pos list_entry((head)-prev, typeof(*pos), member); \ pos-member ! (head); \ pos list_entry(pos-member.prev, typeof(*pos), member))反向遍历list_for_each_entry为正向遍历void Data_list_for_each_entry_reverse(){ struct student head; struct student *p NULL; //参数定义同Data_list_for_each_entry函数 list_for_each_entry_reverse(p,g_list,list) { printf(%s-%d\n,p-name,p-age); } return;}list_for_each_entry_continue#define list_for_each_entry_continue(pos, head, member) \ for (pos list_entry(pos-member.next, typeof(*pos), member); \ pos-member ! (head); \ pos list_entry(pos-member.next, typeof(*pos), member))从某个节点开始遍历。需要与list_prepare_entry(pos,head,member) 配合使用list_prepare_entry的返回值作为list_for_each_entry_continue的pos。list_for_each_entry_safe_continue与list_for_each_entry_continue一样只不过list_for_each_entry_safe_continue遍历后可以直接操作节点比如删除。因此带safe的函数多了一个中间的临时变量。pos宿主结构体类型指针。head链表头。member宿主结构中链表的成员变量。void Data_list_for_each_entry_continue(){ struct student *pos NULL; struct student *n NULL; n list_prepare_entry(pos,g_list,list); /* list_for_each_entry_safe_continue与list_for_each_entry_continue一样只不过 list_for_each_entry_safe_continue遍历后可以直接操作节点比如删除。因此带safe的 函数多了一个中间的临时变量。 */ list_for_each_entry_continue(n,g_list,list) { printf(%s-%d\n,n-name,n-age); } return;}list_for_each_entry_safe#define list_for_each_entry_safe(pos, n, head, member) \ for (pos list_entry((head)-next, typeof(*pos), member), \ n list_entry(pos-member.next, typeof(*pos), member); \ pos-member ! (head); \ pos n, n list_entry(n-member.next, typeof(*n), member))list_for_each_entry的安全版本即在遍历的时候可以操作节点。属于正向遍历。这里我们看到用临时节点n保存了pos的下一个节点地址这样我们就可以进项删除操作了删除pos之后再将n赋值给pos整个链表结构是完整的。pos宿主结构体类型指针。n宿主结构体临时指针。head链表头。member宿主结构中链表的成员变量。void Data_list_del_2(){ //删除链表中元素 struct student *n NULL; struct student *pos NULL; list_for_each_entry_safe(pos,n,g_list,list) { /*list_del与list_del_init都是删除节点但是list_del_init属于安全删除*/ //list_del(pos-list); list_del_init(pos-list); free(pos); } return;}list_for_each_entry_safe_continue#define list_for_each_entry_safe_continue(pos, n, head, member) \ for (pos list_entry(pos-member.next, typeof(*pos), member), \ n list_entry(pos-member.next, typeof(*pos), member); \ pos-member ! (head); \ pos n, n list_entry(n-member.next, typeof(*n), member))同list_for_each_entry_continue属于安全函数遍历的时候节点看可以进行操作例如删除。list_for_each_entry_safe_reverse#define list_for_each_entry_safe_reverse(pos, n, head, member) \ for (pos list_entry((head)-prev, typeof(*pos), member), \ n list_entry(pos-member.prev, typeof(*pos), member); \ pos-member ! (head); \ pos n, n list_entry(n-member.prev, typeof(*n), member))功能与list_for_each_entry_safe类似属于反向遍历。平台通用性及移植 通用性list_head虽然时使用C语言实现的但是其设置的初衷是使用在linux内核所以引入了GUN的一些方法如typeof该宏是用于获取参数的类型。typeof在windowsfreeRtos等平台是不支持所以在不同平台使用需要做平台适配。 例如在win32下我们可以如下定义 #define list_for_each_entry(pos, head, member, type) \ for (pos list_entry((head)-next, type, member); \ pos-member ! (head); \ pos list_entry(pos-member.next, type, member)) 跨平台移植跨平台移植时list_head的实现只保留C标注其余GUN的方法我们需要完全使用C标准的方式进行替换。示例代码
#include list.h
#include string.h
#include stdio.h
#include errno.h
#include stdlib.hstruct list_head g_list;/*头指针*/struct student
{char name[32];int age;struct list_head list;
};int Data_Add(char *name,int age,int len)
{if(name NULL){printf(NULL......\n);return -1;}struct student *st malloc(sizeof(struct student));if(st NULL){printf(malloc failed,reason:%d-%s\n,errno,strerror(errno));return -1;}memcpy(st-name,name,len);st-age age;INIT_LIST_HEAD((st-list));//二选一//头插法//list_add((st-list),g_list);//尾插法list_add_tail((st-list),g_list);return 0;
}//方法1遍历
void Data_list_for_each()
{struct list_head *postion NULL;struct student *p NULL;/*参数1:struct list_head结构体指针参数2:头指针*/list_for_each(postion,g_list){/*参数1struct list_head结构体指针参数2链表容器结构体类型这里即struct student参数3链表容器中链表的成员变量*///二选一list_entry的实现内部其实调用了container_ofp list_entry(postion,struct student,list);//p container_of(postion,struct student,list);printf(%s-%d\n,p-name,p-age);}return;
}//方法2遍历
void Data_list_for_each_entry()
{struct student *p NULL;/*参数1链表容器结构体指针参数2头指针参数3链表容器中链表的成员变量*/list_for_each_entry(p,g_list,list){printf(%s-%d\n,p-name,p-age);}return;
}//从某个节点开始遍历
/*需要与list_prepare_entry(pos,head,member) 配合使用list_prepare_entry的返回值作为list_for_each_entry_continue的pos
*/
void Data_list_for_each_entry_continue()
{struct student *pos NULL;struct student *n NULL;n list_prepare_entry(pos,g_list,list);/*list_for_each_entry_safe_continue与list_for_each_entry_continue一样只不过list_for_each_entry_safe_continue遍历后可以直接操作节点比如删除。因此带safe的函数多了一个中间的临时变量。*/list_for_each_entry_continue(n,g_list,list){printf(%s-%d\n,n-name,n-age);}return;
}//方法1反向遍历
void Data_list_for_each_prev()
{struct list_head *postion NULL;struct student *p NULL;//参数定义同Data_list_for_each函数list_for_each_prev(postion,g_list){p list_entry(postion,struct student,list);printf(%s-%d\n,p-name,p-age);}return;
}//方法2反向遍历
void Data_list_for_each_entry_reverse()
{struct student head;struct student *p NULL;//参数定义同Data_list_for_each_entry函数list_for_each_entry_reverse(p,g_list,list){printf(%s-%d\n,p-name,p-age);}return;
}//数据替换1
void Data_list_replace()
{//用liangchaowei替换zhouxingxingstruct student head;struct student *pos NULL;struct student *data malloc(sizeof(struct student));if(data NULL){return ;}memcpy(data-name,liangchaowei,sizeof(liangchaowei));data-age 57;list_for_each_entry(pos,g_list,list){if(memcmp(pos-name,zhouxingxing,sizeof(zhouxingxing)) 0){/*list_replace没有将pos的前驱和后继分开所以建议使用list_replace_init*///list_replace(pos-list,data-list);list_replace_init(pos-list,data-list);free(pos);break;}}return;
}//方法1删除
//使用与Data_list_for_each类似的方法进行遍历删除
void Data_list_del_1()
{struct list_head *postion NULL;struct list_head *tmp NULL;struct student *p NULL;list_for_each_safe(postion,tmp,g_list){p list_entry(postion,struct student,list);if(memcmp(p-name,liangchaowei,sizeof(liangchaowei)) 0){list_del(p-list);//list_del_init(p-list);free(p);}}return;
}//方法2删除
//删除节点名为liangchaowei的节点
void Data_list_del_2()
{//删除链表中元素struct student *n NULL;struct student *pos NULL;list_for_each_entry_safe(pos,n,g_list,list){if(memcmp(pos-name,zhangguorong,sizeof(zhangguorong)) 0){/*list_del与list_del_init都是删除节点但是list_del_init属于安全删除*///list_del(pos-list);list_del_init(pos-list);free(pos);}}return;
}/*移动节点将某个第三方节点添加到当前链表上功能与新增节点相似*/
int Data_list_move(char *name,int age,int len)
{if(name NULL){printf(NULL......\n);return -1;}struct student *st malloc(sizeof(struct student));if(st NULL){printf(malloc failed,reason:%d-%s\n,errno,strerror(errno));return -1;}memcpy(st-name,name,len);st-age age;INIT_LIST_HEAD((st-list));/*相当于将节点进行头部插入到链表*///list_move((st-list),g_list);/*相当于将节点进行尾部插入到链表*/list_move_tail((st-list),g_list);return 0;
}int main()
{int res -1;INIT_LIST_HEAD(g_list);//数据添加res Data_Add(liudehua,50,sizeof(liudehua));res Data_Add(zhangxueyou,51,sizeof(zhangxueyou));res Data_Add(zhourunfa,52,sizeof(zhourunfa));res Data_Add(zhangxueyou,55,sizeof(zhangxueyou));res Data_Add(zhouxingxing,56,sizeof(zhouxingxing));res Data_Add(zhangguorong,60,sizeof(zhangguorong));if(res ! 0){return -1;}//方法1遍历printf(------------list for each-------------------\n\n);Data_list_for_each();//方法2遍历printf(------------list for each entry-------------------\n\n);Data_list_for_each_entry();//方法1反向遍历printf(------------------list for each prev-------------\n\n);Data_list_for_each_prev();//方法2反向遍历printf(---------------list for each entry reverse----------------\n\n);Data_list_for_each_entry_reverse();//从某个节点开始遍历printf(----------------list for each entry continue---------------\n\n);Data_list_for_each_entry_continue();//数据替换printf(-----------------replace--------------\n\n);Data_list_replace();Data_list_for_each_entry();//数据删除printf(-----------------del 1--------------\n\n);Data_list_del_1();Data_list_for_each_entry();//数据删除printf(-----------------del 2--------------\n\n);Data_list_del_2();Data_list_for_each();//节点移动printf(-----------------move--------------\n\n);Data_list_move(linqingxia,61,sizeof(linqingxia));Data_list_move(gutianle,62,sizeof(gutianle));Data_list_for_each();return 0;
}
