Linux | 数据结构之内核链表

Linux | 数据结构之内核链表时间2023年12月20日15:42:45文章目录Linux | 数据结构之内核链表1.参考2.内核链表2-1.源码2-2.节点类型2-3.内核链表相关算法2-3-1.初始化2-3-1-1.宏的实现2-3-1-2.内联函数的实现2-3-2.插入2-3-2-1.将new指向的结点插入到head指向的结点后面(表头)2-3-2-2.将new指向的结点插入到head指向的结点前面(表尾)2-3-3.删除2-3-4.移动链表中的某个结点1)将链表中的某个结点list移动到head指向的结点后面(表头)2)将链表中的某个结点list移动到head指向的结点前面(表尾)2-3-5、内核链表相关的宏1》通过内核结点指针ptr获得内核结点所在的结构体的地址2》基于内核结点指针向后循环3》基于内核结点指针向后循环4》基于数据结点指针向后循环3.示例4.拓展1.参考1.数据结构与算法教程数据结构C语言版教程 (biancheng.net)2.双向链表及创建C语言详解 (biancheng.net)3.内核数据结构 —— 内核链表_内核链表长度怎么表示-CSDN博客4.内核链表 - 搜索 (bing.com)5.Linux | 内核链表-CSDN博客6.structure/1_kernellist · cProgram/100Example - 码云 - 开源中国 (gitee.com)2.内核链表2-1.源码[fly752fac4b02e9 kernel]$find./-namelist.h ./include/linux/list.h ./include/config/debug/pi/list.h ./include/config/defconfig/list.h ./tools/perf/util/include/linux/list.h#ifndef_LINUX_LIST_H#define_LINUX_LIST_H#ifndefARCH_HAS_PREFETCH#defineARCH_HAS_PREFETCHstaticinlinevoidprefetch(constvoid*x){;}#endif/* * Simple doubly linked list implementation. * * Some of the internal functions (__xxx) are useful when * manipulating whole lists rather than single entries, as * sometimes we already know the next/prev entries and we can * generate better code by using them directly rather than * using the generic single-entry routines. */structlist_head{structlist_head*next,*prev;};#defineLIST_HEAD_INIT(name){(name),(name)}#defineLIST_HEAD(name)\structlist_headnameLIST_HEAD_INIT(name)#defineINIT_LIST_HEAD(ptr)do{\(ptr)-next(ptr);(ptr)-prev(ptr);\}while(0)/* * Insert a new entry between two known consecutive entries. * * This is only for internal list manipulation where we know * the prev/next entries already! */staticinlinevoid__list_add(structlist_head*new,structlist_head*prev,structlist_head*next){next-prevnew;new-nextnext;new-prevprev;prev-nextnew;}/** * list_add - add a new entry * new: new entry to be added * head: list head to add it after * * Insert a new entry after the specified head. * This is good for implementing stacks. */staticinlinevoidlist_add(structlist_head*new,structlist_head*head){__list_add(new,head,head-next);}/** * list_add_tail - add a new entry * new: new entry to be added * head: list head to add it before * * Insert a new entry before the specified head. * This is useful for implementing queues. */staticinlinevoidlist_add_tail(structlist_head*new,structlist_head*head){__list_add(new,head-prev,head);}/* * Delete a list entry by making the prev/next entries * point to each other. * * This is only for internal list manipulation where we know * the prev/next entries already! */staticinlinevoid__list_del(structlist_head*prev,structlist_head*next){next-prevprev;prev-nextnext;}/** * list_del - deletes entry from list. * entry: the element to delete from the list. * Note: list_empty on entry does not return true after this, the entry is in an undefined state. */staticinlinevoidlist_del(structlist_head*entry){__list_del(entry-prev,entry-next);entry-next(void*)0;entry-prev(void*)0;}/** * list_del_init - deletes entry from list and reinitialize it. * entry: the element to delete from the list. */staticinlinevoidlist_del_init(structlist_head*entry){__list_del(entry-prev,entry-next);INIT_LIST_HEAD(entry);}/** * list_move - delete from one list and add as anothers head * list: the entry to move * head: the head that will precede our entry */staticinlinevoidlist_move(structlist_head*list,structlist_head*head){__list_del(list-prev,list-next);list_add(list,head);}/** * list_move_tail - delete from one list and add as anothers tail * list: the entry to move * head: the head that will follow our entry */staticinlinevoidlist_move_tail(structlist_head*list,structlist_head*head){__list_del(list-prev,list-next);list_add_tail(list,head);}/** * list_empty - tests whether a list is empty * head: the list to test. */staticinlineintlist_empty(structlist_head*head){returnhead-nexthead;}staticinlinevoid__list_splice(structlist_head*list,structlist_head*head){structlist_head*firstlist-next;structlist_head*lastlist-prev;structlist_head*athead-next;first-prevhead;head-nextfirst;last-nextat;at-prevlast;}/** * list_splice - join two lists * list: the new list to add. * head: the place to add it in the first list. */staticinlinevoidlist_splice(structlist_head*list,structlist_head*head){if(!list_empty(list))__list_splice(list,head);}/** * list_splice_init - join two lists and reinitialise the emptied list. * list: the new list to add. * head: the place to add it in the first list. * * The list at list is reinitialised */staticinlinevoidlist_splice_init(structlist_head*list,structlist_head*head){if(!list_empty(list)){__list_splice(list,head);INIT_LIST_HEAD(list);}}/** * list_entry - get the struct for this entry * ptr: the struct list_head pointer. * type: the type of the struct this is embedded in. * member: the name of the list_struct within the struct. */#definelist_entry(ptr,type,member)\((type*)((char*)(ptr)-(unsignedlong)(((type*)0)-member)))/** * list_for_each - iterate over a list * pos: the struct list_head to use as a loop counter. * head: the head for your list. */#definelist_for_each(pos,head)\for(pos(head)-next,prefetch(pos-next);pos!(head);\pospos-next,prefetch(pos-next))/** * list_for_each_prev - iterate over a list backwards * pos: the struct list_head to use as a loop counter. * head: the head for your list. */#definelist_for_each_prev(pos,head)\for(pos(head)-prev,prefetch(pos-prev);pos!(head);\pospos-prev,prefetch(pos-prev))/** * list_for_each_safe - iterate over a list safe against removal of list entry * pos: the struct list_head to use as a loop counter. * n: another struct list_head to use as temporary storage * head: the head for your list. */#definelist_for_each_safe(pos,n,head)\for(pos(head)-next,npos-next;pos!(head);\posn,npos-next)/** * list_for_each_entry - iterate over list of given type * pos: the type * to use as a loop counter. * head: the head for your list. * member: the name of the list_struct within the struct. */#definelist_for_each_entry(pos,head,member)\for(poslist_entry((head)-next,typeof(*pos),member),\prefetch(pos-member.next);\pos-member!(head);\poslist_entry(pos-member.next,typeof(*pos),member),\prefetch(pos-member.next))/** * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry * pos: the type * to use as a loop counter. * n: another type * to use as temporary storage * head: the head for your list. * member: the name of the list_struct within the struct. */#definelist_for_each_entry_safe(pos,n,head,member)\for(poslist_entry((head)-next,typeof(*pos),member),\nlist_entry(pos-member.next,typeof(*pos),member);\pos-member!(head);\posn,nlist_entry(n-member.next,typeof(*n),member))/** * list_for_each_entry_continue - iterate over list of given type * continuing after existing point * pos: the type * to use as a loop counter. * head: the head for your list. * member: the name of the list_struct within the struct. */#definelist_for_each_entry_continue(pos,head,member)\for(poslist_entry(pos-member.next,typeof(*pos),member),\prefetch(pos-member.next);\pos-member!(head);\poslist_entry(pos-member.next,typeof(*pos),member),\prefetch(pos-member.next))#endif2-2.节点类型2-3.内核链表相关算法2-3-1.初始化2-3-1-1.宏的实现2-3-1-2.内联函数的实现2-3-2.插入2-3-2-1.将new指向的结点插入到head指向的结点后面(表头)2-3-2-2.将new指向的结点插入到head指向的结点前面(表尾)2-3-3.删除2-3-4.移动链表中的某个结点1)将链表中的某个结点list移动到head指向的结点后面(表头)2)将链表中的某个结点list移动到head指向的结点前面(表尾)2-3-5、内核链表相关的宏1》通过内核结点指针ptr获得内核结点所在的结构体的地址2》基于内核结点指针向后循环3》基于内核结点指针向后循环4》基于数据结点指针向后循环3.示例structure/1_kernellist · cProgram/100Example - 码云 - 开源中国 (gitee.com)4.拓展1、用顺序栈实现整数的逆序输出。例如输入整数123输出321.2、用链栈实现十进制向八进制转换。例如输入123输出0173.3、分别用循环队列和链式队列实现如下功能用户从键盘输入整数程序将其入队用户输入字母程序将队头元素出队并在每一次出队和入队之后打印队列元素。