双向链表:分析list_head结构＆建立双向链表的一种常见来源: 发布时间:星期一, 2009年2月23日 浏览:46次 评论:0
="t18">
作者:opera 代码: ;  /Linux/list.h 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(entry,head); 将entry添加到head的后,用于构造堆栈 head->next->prev = entry; entry->next = head->next; entry->prev = head; head->next = entry; list_add_tail(entry,head) : 将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(list,head) : 将两个环形链表合成 个大表 list->prev->next = head->next; list->next->prev = head; head->next->prev = list->prev; head->next = list->next; list_entry(ptr,type,member) : 假如type结构中member 地址是ptr,则返回type结构地址 ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member))) list_for_each(entry,head) : 遍历链表 for (entry = (head)->next; entry != (head); entry = entry->next) 建立双向链表 种常见思路方法 作者:西安交通大学 王灏 在分析内核时经常碰到以“pprev”作为尾缀 2次指针和带有“next”尾缀次指针 而且在链表治理时使用这么对指针这里以网络bind哈希表建立为例解释(内核2.2.18) 代码: struct **skp = &udp_hash[sk->num & (UDP_HTABLE_SIZE -1)] SOCKHASH_LOCK  ;  ((sk->next = *skp) != NULL) (*skp)->pprev = &sk->next; 请注重这里pprev通常是指向前 个结点next地址 *skp = sk; sk->pprev =skp; SOCKHASH_UNLOCK ; 第 句赋值语句将skp指向以sk->num为参数哈希链起始地址 而哈希 每项都是指向sock结构指针所以* skp就是指向哈希链中第个sock结构整个语句完成在第个sock结点和当前插入结点间链接关系(包括前向指针和后向指针)后面两条语句在哈希项和当前插入结点的间建立链接关系 用这种思路方法这里 链表通常pprev指针只在链表治理时(插入和删除)使用而在查找时仅使用next指针也就是说这种链表查找通常是单向(pprev通常不指向结点起始位置若进行前向查找必须有个类似于list_head双向链表计算结点起始位置宏)这使得这种链表只是在链表建立和链表删除时有双向链表效率而查找时仅是单向链表效率但是这种链表通常用在哈希表中这样虽然查找是单向链表效率但是由于具有同个哈希值链较短所以执行效率也非常好而且兼有双向链表插入删除效率0
相关文章读者评论发表评论 |
 |
专注于互联网--专注于架构 |
最新标签 网站地图 文章索引 Rss订阅 |
