建设一个连接的网站,服装企业网站源码,济南建筑工程网,怎么在网站底部做备案号大多数的读者在学习编程语言的时候都不喜欢那些枯燥的文字描述#xff0c;包括我自己在开始学习编程的时候也是这样#xff0c;对于代码的热情远远高于文字#xff0c;所以我在我写东西的时候也不喜欢用枯燥的文字描述来向读者讲解#xff0c;更喜欢用代码加上适当的文字描…大多数的读者在学习编程语言的时候都不喜欢那些枯燥的文字描述包括我自己在开始学习编程的时候也是这样对于代码的热情远远高于文字所以我在我写东西的时候也不喜欢用枯燥的文字描述来向读者讲解更喜欢用代码加上适当的文字描述的方式进行讲解因为有些东西可能用枯燥的文字描述半天还不如实实在在的给读者呈现出一段简单的代码让读者理解得更加的透彻些。但是并不是说文字描述就没用文字描述也很重要只是绝大部分读者都更加的希望直接达到最终的效果都想跳过那些中间的步骤。接下来我们接着上一篇博客《C语言的那些小秘密之链表(三)》的内容继续讲解linux内核双向循环链表。[cpp] view plaincopystatic inline int list_empty(const struct list_head *head){return head-next head;}static inline int list_empty_careful(const struct list_head *head){struct list_head *next head-next;return (next head) (next head-prev);}运行结果为[html] view plaincopyrootubuntu:/home/paixu/dlist_node# ./astudent num: 5 student name: Stu5student num: 4 student name: Stu4student num: 3 student name: Stu3student num: 2 student name: Stu2student num: 1 student name: Stu1使用list_empty()检测链表非空使用list_empty_careful()检测链表非空看看代码就知道如何使用了接下来看看链表的合成。[html] view plaincopystatic inline void __list_splice(struct list_head *list,struct list_head *head){struct list_head *first list-next;struct list_head *last list-prev;struct list_head *at head-next;first-prev head;head-next first;last-next at;at-prev last;}在这种情况下会丢弃list所指向的头结点因为两个链表有两个头结点所以我们必须要去掉其中一个头结点。只要list非空链head无任何限制该函数就能实现链表的合并。[cpp] view plaincopystatic inline void list_splice_init(struct list_head *list,struct list_head *head){if (!list_empty(list)) {__list_splice(list, head);INIT_LIST_HEAD(list);}}以上函数的功能是将一个链表list的有效信息合并到另外一个链表head后重新初始化被去掉的空的链表头。这样的描述可能不是太好理解接下来看看一段代码。[html] view plaincopy#include#include#include list.htypedef struct _stu{char name[20];int num;struct list_head list;}stu;int main(){stu *pstu,*pstu2;stu *tmp_stu;struct list_head stu_list,stu_list2;struct list_head *pos;int i 0;INIT_LIST_HEAD(stu_list);INIT_LIST_HEAD(stu_list2);pstu malloc(sizeof(stu)*3);pstu2 malloc(sizeof(stu)*3);for(i0;i3;i){sprintf(pstu[i].name,Stu%d,i1);sprintf(pstu2[i].name,Stu%d,i4);pstu[i].num i1;pstu2[i].num i4;list_add( (pstu[i].list), stu_list);list_add( (pstu2[i].list), stu_list2);}printf(stu_list 链表\n);list_for_each(pos,stu_list){tmp_stu list_entry(pos, stu, list);printf(student num: %d\tstudent name: %s\n,tmp_stu-num,tmp_stu-name);}printf(stu_list2 链表\n);list_for_each(pos,stu_list2){tmp_stu list_entry(pos, stu, list);printf(student num: %d\tstudent name: %s\n,tmp_stu-num,tmp_stu-name);}printf(stu_list链表和stu_list2 链表合并以后\n);list_splice(stu_list2,stu_list);list_for_each(pos,stu_list){tmp_stu list_entry(pos, stu, list);printf(student num: %d\tstudent name: %s\n,tmp_stu-num,tmp_stu-name);}free(pstu);return 0;}运行结果为[html] view plaincopyrootubuntu:/home/paixu/dlist_node# ./astu_list 链表student num: 3 student name: Stu3student num: 2 student name: Stu2student num: 1 student name: Stu1stu_list2 链表student num: 6 student name: Stu6student num: 5 student name: Stu5student num: 4 student name: Stu4stu_list链表和stu_list2 链表合并以后student num: 6 student name: Stu6student num: 5 student name: Stu5student num: 4 student name: Stu4student num: 3 student name: Stu3student num: 2 student name: Stu2student num: 1 student name: Stu1有了直观的代码和运行结果理解起来也更加的容易了。有了上面的这些操作但是我们还一直没有讲到我们最终所关心的宿主结构那么接下来我们一起来看看我们该如何取出宿主结构的指针呢?这也是我认为linux内核双向循环链表实现最为巧妙的地方了。[cpp] view plaincopy#define list_entry(ptr, type, member) \((type *)((char *)(ptr)-(unsigned long)(((type *)0)-member)))看看上面的代码发现一个很熟悉的身影(unsigned long)(((type *)0)-member))这个我在前一篇博客《C语言的那些小秘密之字节对齐》中已经讲解过了多以在此就不再做过多的讲解如果有不明白的读者可以回过去看看讲解再回过来阅读。通过(unsigned long)(((type *)0)-member))我们得出了成员变量member的偏移量而ptr为指向member的指针因为指针类型不同的原因所以我们再次要先进行(char*)的转换之后再进行计算。所以我们用ptr减去member的偏移量就得到了宿主结构体的指针这就是一个非常巧妙的地方这也就使得linux内核双向循环链表能够区别于传统链表的关键所在。可能看到这儿的时候读者已经感觉非常的枯燥了但是别放弃坚持看完因为虽然这样的讲解枯燥了点但是非常有用。所以坚持坚持吧![cpp] view plaincopy#define list_for_each(pos, head) \for (pos (head)-next; prefetch(pos-next), pos ! (head); \pos pos-next)#define __list_for_each(pos, head) \for (pos (head)-next; pos ! (head); pos pos-next)#define list_for_each_prev(pos, head) \for (pos (head)-prev; prefetch(pos-prev), pos ! (head); \pos pos-prev)遍历是双循环链表的基本操作head为头节点遍历过程中首先从(head)-next开始当poshead时退出故head节点并没有访问这和链表的结构设计有关通常头节点都不含有其它有效信息因此可以把头节点作为双向链表遍历一遍的检测标志来使用。在list_for_each宏中读者可能发现一个比较陌生的面孔我们在此就不将prefetch展开了讲解了有兴趣的读者可以自己查看下它的实现其功能是预取内存的内容也就是程序告诉CPU哪些内容可能马上用到CPU预先其取出内存操作数然后将其送入高速缓存用于优化是的执行速度更快。接下来的__list_for_each()宏和list_for_each_prev()宏就不在此做一一的讲解了和list_for_each()宏类似。 就是遍历的方向有所改变或者不使用预取。通过上面的讲解和前面那么多的代码相信读者这个时候对于list_for_each()已经不再感到陌生了。上面的但三个遍历链表的宏都类似继续往下看。[cpp] view plaincopy#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_safe()宏也同样是用于遍历的不同的是里边多出了一个n暂存pos下一个节点的地址避免了因为pos节点被释放而造成的断链这也就体现出了safe。也就是说你可以遍历完当前节点后将其删除同时可以接着访问下一个节点遍历完毕后就只剩下一个头节点。当然这有一个最为典型的应用那就是我们在多进程编程时候多个进程等待在同一个等待队列上若事件发生时唤醒所有进程则可以唤醒后将其依次从等待队列中删除。[html] view plaincopy#include#include#include list.htypedef struct _stu{char name[20];int num;struct list_head list;}stu;int main(){stu *pstu;stu *tmp_stu;struct list_head stu_list;struct list_head *pos,*n;int i 0;INIT_LIST_HEAD(stu_list);pstu malloc(sizeof(stu)*3);for(i0;i3;i){sprintf(pstu[i].name,Stu%d,i1);pstu[i].num i1;list_add( (pstu[i].list), stu_list);}printf(通过list_for_each_safe()遍历使用list_del(pos)删除结点前\n);list_for_each_safe(pos, n, stu_list){tmp_stu list_entry(pos, stu, list);printf(student num: %d\tstudent name: %s\n,tmp_stu-num,tmp_stu-name);list_del(pos);}printf(通过list_for_each()遍历使用list_del(pos)删除结点后\n);list_for_each(pos,stu_list){tmp_stu list_entry(pos, stu, list);printf(student num: %d\tstudent name: %s\n,tmp_stu-num,tmp_stu-name);}free(pstu);return 0;}运行结果为[html] view plaincopyrootubuntu:/home/paixu/dlist_node# ./a通过list_for_each_safe()遍历使用list_del(pos)删除结点前student num: 3 student name: Stu3student num: 2 student name: Stu2student num: 1 student name: Stu1通过list_for_each()遍历使用list_del(pos)删除结点后读者可以结合运行结果再去阅读上面的文字描述部分。如果只提供对list_head结构的遍历操作是远远不够的我们希望实现的是对宿主结构的遍历即在遍历时直接获得当前链表节点所在的宿主结构项而不是每次要同时调用list_for_each()和list_entry()。为此Linux特地提供了list_for_each_entry()宏来实现[cpp] view plaincopy#define list_for_each_entry(pos, head, member) \for (pos list_entry((head)-next, typeof(*pos), member); \prefetch(pos-member.next), pos-member ! (head); \pos list_entry(pos-member.next, typeof(*pos), member))第一个参数为传入的遍历指针指向宿主数据结构第二个参数为链表头为list_head结构第三个参数为list_head结构在宿主结构中的成员名。有时候做过多的讲解反而没有看看代码的效果好我们还是用段代码来说明下吧。[html] view plaincopy#include#include#include list.htypedef struct _stu{char name[20];int num;struct list_head list;}stu;int main(){stu *pstu;stu *tmp_stu;struct list_head stu_list;struct list_head *pos,*n;int i 0;INIT_LIST_HEAD(stu_list);pstu malloc(sizeof(stu)*3);for(i0;i3;i){sprintf(pstu[i].name,Stu%d,i1);pstu[i].num i1;list_add( (pstu[i].list), stu_list);}list_for_each_entry(tmp_stu, stu_list, list)printf(student num: %d\tstudent name: %s\n,tmp_stu-num,tmp_stu-name);free(pstu);return 0;}运行结果为[html] view plaincopyrootubuntu:/home/paixu/dlist_node# ./astudent num: 3 student name: Stu3student num: 2 student name: Stu2student num: 1 student name: Stu1如果读者一开始对于文字描述感到陌生的话那么就再次结合代码去阅读。接下来再来看看最后几个。[html] view plaincopy#define list_for_each_entry_reverse(pos, head, member) \for (pos list_entry((head)-prev, typeof(*pos), member); \prefetch(pos-member.prev), pos-member ! (head); \pos list_entry(pos-member.prev, typeof(*pos), member))#define list_prepare_entry(pos, head, member) \((pos) ? : list_entry(head, typeof(*pos), member))#define list_for_each_entry_continue(pos, head, member) \for (pos list_entry(pos-member.next, typeof(*pos), member); \prefetch(pos-member.next), pos-member ! (head); \pos list_entry(pos-member.next, typeof(*pos), member))#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类似只是其中略有差别list_prepare_entry()中含有prefetch()它的作用在上面已经讲解有什么疑惑可以返回去阅读下在此不再做过多的讲解;list_for_each_entry_continue()和list_for_each_entry()的区别主要是list_for_each_entry_continue()可以不从链表头开始遍历而是从已知的某个pos结点的下一个结点开始遍历。在某些时候如果不是从头结点开始遍历那么为了保证pos的初始值有效必须使用list_prepare_entry()。其含义就是如果pos非空那么pos的值就为其本身如果pos为空那么就从链表头强制扩展一个虚pos指针读者自己分析list_prepare_entry()的实现就明白了。list_for_each_entry_safe()要求调用者另外提供一个与pos同类型的指针n在for循环中暂存pos下一个节点的宿主结构体的地址避免因pos节点被释放而造成的断链。到此我们linux内核双向循环链表的旅程就结束了下一篇我们将开始一个新的旅程。由于本人水平有限博客中的不妥或错误之处在所难免殷切希望读者批评指正。同时也欢迎读者共同探讨相关的内容如果乐意交流的话请留下你宝贵的意见。
