|
作者opera 代码: ; include/linux/listh struct list_head { struct list_head *next *prev; }; list_head结构用于构造双向环形链表 LIST_HEAD(head) : 定义一个空表头 struct list_head head = {&head&head}; INIT_LIST_HEAD(head) : 初始化一个已定义的表头; head>next = head; head>prev = head; list_add(entryhead); 将entry添加到head之后用于构造堆栈 head>next>prev = entry; entry>next = head>next; entry>prev = head; head>next = entry; list_add_tail(entryhead) : 将entry添加到head之前用于构造队列 head>prev = entry; entry>next = head; entry>prev = head>prev; head>prev>next = entry; list_del(entry) : 删除entry entry>next>prev = entry>prev; entry>prev>next = entry>next; list_del_init(entry) : 删除并复位entry entry>next>prev = entry>prev; entry>prev>next = entry>next; entry>next = entry; entry>prev = entry; list_empty(head) : 测试环形链表是否为空 (head>next == head) list_splice(listhead) : 将两个环形链表合成一个大表 list>prev>next = head>next; list>next>prev = head; head>next>prev = list>prev; head>next = list>next; list_entry(ptrtypemember) : 如果type结构中member的地址是ptr则返回type结构的地址 ((type *)((char *)(ptr)(unsigned long)(&((type *))>member))) list_for_each(entryhead) : 遍历链表 for (entry = (head)>next; entry != (head); entry = entry>next) ======================================================== 建立双向链表的一种常见方法 作者西安交通大学 王灏 ======================================================== 在分析内核时常常碰到以pprev作为尾缀的二次指针和带有next尾缀的一次指针而且在链表管理时使用这么一对指针这里以网络bind哈希表建立为例解释（内核） 代码: struct **skp = &udp_hash[sk>num & (UDP_HTABLE_SIZE )] SOCKHASH_LOCK(); if((sk>next = *skp) != NULL) (*skp)>pprev = &sk>next; 请注意这里pprev通常是指向前一个结点的next的地址 *skp = sk; sk>pprev =skp; SOCKHASH_UNLOCK(); 第一句赋值语句将skp指向以sk>num为参数的哈希链的起始地址而哈希数组的每一项都是指向sock结构的指针所以* skp就是指向哈希链中的第一个sock结构整个if语句完成在第一个sock结点和当前插入结点间的链接关系（包括前向指针和后向指针）后面两条语句在哈希数组项和当前插入结点之间建立链接关系 用这种方法这里的链表通常pprev指针只在链表管理时（插入与删除）使用而在查找时仅使用next指针也就是说这种链表的查找通常是单向的（pprev通常不指向结点的起始位置若进行前向查找必须有一个类似于list_head双向链表的计算结点起始位置的宏）这使得这种链表只是在链表建立和链表删除时有双向链表的效率而查找时仅是单向链表的效率但是这种链表通常用在哈希表中这样虽然查找是单向链表的效率但是由于具有同一个哈希值的链较短所以执行效率也非常好而且兼有双向链表的插入删除效率 |
