服务器win7网站建设多用户购物商城系统

服务器win7网站建设,多用户购物商城系统,专业手机网站建设平台,公司总经理培训推广哪家好一、链表 链表是开发者学习数据结构时最初的一种数据结构#xff0c;它的应用是非常广泛的。而且在实际的开发#xff0c;特别是面试中#xff0c;对链表的各种应用都是无法绕开的。一些常见的算法也是以链表为基础的。链表的应用形式有很多#xff0c;一般在教材中学习到的…一、链表链表是开发者学习数据结构时最初的一种数据结构它的应用是非常广泛的。而且在实际的开发特别是面试中对链表的各种应用都是无法绕开的。一些常见的算法也是以链表为基础的。链表的应用形式有很多一般在教材中学习到的也就是开发中常见到的链表其基本的应用方式如下//双向链表structlist{intiValue;int*pData;structlist*pNext;// 下一个节点structlist*pPev;// 前一个节点};可以把链表当成一个一个索链的结点它们通过指针象“铁环一样”紧紧的链接在一起形成一条索链一样的表。二、内核中的链表与传统链表对比看过内核源码的开发者可能在内核中也看到过链表的定义形势会发现与教材中的传统的链表有些不同。下面先看一下内核中的代码的链表定义//双向链表structlist_head{structlist_head*next,*prev;};//linux-6.9.12/virt/kvm/eventfd.cstruct_ioeventfd{structlist_headlist;u64 addr;intlength;structeventfd_ctx*eventfd;u64 datamatch;structkvm_io_devicedev;u8 bus_idx;bool wildcard;};把上面的链表代码和教材中的链表代码比较大家可以发现有什么不同么最典型的就是教材中的链表包含着数据本身而在内核中则是数据本身包含链表这样说可能不太准确但容易理解。所以内核中这种链表也可以称为侵入式链表。另外这种链表可以嵌入到任何的数据结构中形成链表其通用性非常强应用非常灵活。对于这种链表其具体的操作时间复杂度为O(1)相对来说要稳定同时这种链表不再参与数据本身的内存分配和回收在设计上将数据结构与数据进行了解耦。最后这种数据链表内存中的数据存储连续对缓存友好访问速度快。这也是内核中使用这种链表的一个重要原因。三、应用分析理解内核中这种双向循环链表需要明白几个主要的宏//自己指向自己前向和后向都如此形成一个空的循环链表#defineLIST_HEAD_INIT(name){(name),(name)}#defineLIST_HEAD(name)\structlist_headnameLIST_HEAD_INIT(name)/** * INIT_LIST_HEAD - Initialize a list_head structure * list: list_head structure to be initialized. * * Initializes the list_head to point to itself. If it is a list header, * the result is an empty list. */staticinlinevoidINIT_LIST_HEAD(structlist_head*list){WRITE_ONCE(list-next,list);WRITE_ONCE(list-prev,list);}//写入数据#define__WRITE_ONCE(x,val)\do{\*(volatiletypeof(x)*)(x)(val);\}while(0)#defineWRITE_ONCE(x,val)\do{\compiletime_assert_rwonce_type(x);\__WRITE_ONCE(x,val);\}while(0)#ifdefined(__x86_64__)#definesmp_store_release(p,v)\do{\barrier();\WRITE_ONCE(*p,v);\}while(0)//遍历内核中还有数个相类似的实现/** * list_for_each - iterate over a list * pos: the struct list_head to use as a loop cursor. * head: the head for your list. */#definelist_for_each(pos,head)\for(pos(head)-next;!list_is_head(pos,(head));pospos-next)/** * list_for_each_reverse - iterate backwards over a list * pos: the struct list_head to use as a loop cursor. * head: the head for your list. */#definelist_for_each_reverse(pos,head)\for(pos(head)-prev;pos!(head);pospos-prev)这也算内核的特点底层大量使用了宏来处理一些基础的数据结构和相关的算法定义。只要掌握了这些底层的宏处理那么在阅读相关的数据结构和算法处理时就基本没有什么问题了。实际的应用上这种链表与普通链表的整体用法没有本质不同但在一些细节上却有自己的特点主要有使用container_of宏来处理数据结构与链表节点指针关系看下内核中的源码//typeof:用于类型检查确保传入的指针为成员类型指针#definetypeof_member(T,m)typeof(((T*)0)-m)/** * container_of - cast a member of a structure out to the containing structure * ptr: the pointer to the member. * type: the type of the container struct this is embedded in. * member: the name of the member within the struct. * * WARNING: any const qualifier of ptr is lost. */#definecontainer_of(ptr,type,member)({\void*__mptr(void*)(ptr);\static_assert(__same_type(*(ptr),((type*)0)-member)||\__same_type(*(ptr),void),\pointer type mismatch in container_of());\((type*)(__mptr-offsetof(type,member)));})/** * container_of_const - cast a member of a structure out to the containing * structure and preserve the const-ness of the pointer * ptr: the pointer to the member * type: the type of the container struct this is embedded in. * member: the name of the member within the struct. */#definecontainer_of_const(ptr,type,member)\_Generic(ptr,\consttypeof(*(ptr))*:((consttype*)container_of(ptr,type,member)),\default:((type*)container_of(ptr,type,member))\)//__builtin_offsetof GCC中内置的一个函数用来计算struct中特定成员相对于起始地址的字节偏移量#undefoffsetof#defineoffsetof(TYPE,MEMBER)__builtin_offsetof(TYPE,MEMBER)container_of首先将链表的指针类型转化为void的__mptr,然后用offsetof来获取成员到对象起始地址的偏移量所以是((T)0),而((T*)0)-m就是与0的偏移量不用再作减法此时再用__mptr减去偏移量的绝对值则可以得到包含指针成员变量的对象的地址。2. 支持相同数据在多个链表的处理这是一种比较特殊的应用就是说一个数据对象可以在多个链表中进行访问处理如下面的代码//arch/x86/kvm/svm/svm.hstructkvm_sev_info{bool active;/* SEV enabled guest */bool es_active;/* SEV-ES enabled guest */unsignedintasid;/* ASID used for this guest */unsignedinthandle;/* SEV firmware handle */intfd;/* SEV device fd */unsignedlongpages_locked;/* Number of pages locked */structlist_headregions_list;/* List of registered regions */u64 ap_jump_table;/* SEV-ES AP Jump Table address */structkvm*enc_context_owner;/* Owner of copied encryption context */structlist_headmirror_vms;/* List of VMs mirroring */structlist_headmirror_entry;/* Use as a list entry of mirrors */structmisc_cg*misc_cg;/* For misc cgroup accounting */atomic_tmigration_in_progress;};//arch/x86/kvm/svm/svm.cstaticintsev_guest_init(structkvm*kvm,structkvm_sev_cmd*argp){structkvm_sev_info*sevto_kvm_svm(kvm)-sev_info;......INIT_LIST_HEAD(sev-regions_list);INIT_LIST_HEAD(sev-mirror_vms);......returnret;}广泛使用宏来进行链表的操作这个除了前面的一些初始化等操作最典型的就是遍历//以下为几个遍历的方法还有很多可参看相关文件#definelist_for_each(pos,head)\for(pos(head)-next;!list_is_head(pos,(head));pospos-next)#definelist_for_each_reverse(pos,head)\for(pos(head)-prev;pos!(head);pospos-prev)#definelist_for_each_rcu(pos,head)\for(posrcu_dereference((head)-next);\!list_is_head(pos,(head));\posrcu_dereference(pos-next))#definelist_for_each_continue(pos,head)\for(pospos-next;!list_is_head(pos,(head));pospos-next)#definelist_for_each_safe(pos,n,head)\for(pos(head)-next,npos-next;\!list_is_head(pos,(head));\posn,npos-next)#definelist_for_each_prev_safe(pos,n,head)\for(pos(head)-prev,npos-prev;\!list_is_head(pos,(head));\posn,npos-prev)通用的链表相关接口这此只简单的说明一下在“include/linux/list.h”中有插入头插、尾插和中间插入、删除、交换、切片、替代等等。这种链表当然也有其不足之处主要有需要修改数据结构引入链表相关的数据定义实现较为复杂包括container_of等一系列宏的使用维护调试相对复杂四、应用场景一般来说这种链表会应用于以下几种场景内核相关的系统编程多链表数据结构的应用内存操作对大小及性能操作要求较高的场合其它一些特定的应用一般来说这种侵入式链表应该不算主流应用的方式但在某些方面很有应用价值。五、内核中的例子具体的用法如下//drivers/base/core.c//设备固件节点两个fwnode_handle的依赖关系创建即consumer消费者supplier供应者staticint__fwnode_link_add(structfwnode_handle*con,structfwnode_handle*sup,u8 flags){structfwnode_link*link;list_for_each_entry(link,sup-consumers,s_hook)if(link-consumercon){link-flags|flags;return0;}linkkzalloc(sizeof(*link),GFP_KERNEL);if(!link)return-ENOMEM;link-suppliersup;INIT_LIST_HEAD(link-s_hook);link-consumercon;INIT_LIST_HEAD(link-c_hook);link-flagsflags;list_add(link-s_hook,sup-consumers);list_add(link-c_hook,con-suppliers);pr_debug(%pfwf Linked as a fwnode consumer to %pfwf\n,con,sup);return0;}如果抛开链表所处理的功能外就只考虑链表实现本身只要理解了前面的相关实现代码还是没有什么大问题的。六、总结学习内核中的链表的目的除了为深入掌握内核相关的技术作准备外另外一个重要的目的是明白实现链表处理数据的其它方式。正所谓“它山之石可以攻玉”。与诸君共勉