Chinaunix首页 | 论坛 | 博客
  • 博客访问: 458320
  • 博文数量: 72
  • 博客积分: 1851
  • 博客等级: 上尉
  • 技术积分: 1464
  • 用 户 组: 普通用户
  • 注册时间: 2010-09-16 17:50
文章分类

全部博文(72)

文章存档

2013年(1)

2012年(17)

2011年(51)

2010年(3)

分类: LINUX

2011-06-20 21:01:06

合并链表

  1. //将prev,next的链表与list链表合并,prev代表新的头部
  2. static inline void __list_splice(const struct list_head *list,
  3. struct list_head *prev,struct list_head *next)
  4. {
  5. struct list_head *first = list->next;
  6. struct list_head *last = list->prev;
  7. first ->prev = prev;
  8. prev->next = first;
  9. last ->next = next;
  10. next ->prev = last;
  11. }

在此基础上,产生的函数有:

  1. //将list链表与head链表合并,head指向新的链表头(为栈设计)
  2. static inline void list_splice(const struct list_head *list,struct list_head *head)
  3. {
  4. if(!list_empty(list))
  5. __list_splice(list,head,head->next);
  6. }
  7. //为队列设计的链表合并
  8. static inline void list_splice_tail(struct list_head *list,struct list_head *head)
  9. {
  10. if(!list_empty(list))
  11. __list_splice(list,head->prev,head);
  12. }

类似函数有:

  1. static inline void list_splice_init(struct list_head *list,struct list_head *head)
  2. static inline void list_splice_tail_init(struct list_head *list,struct list_head *head);

链表遍历

最为复杂的部分为链表遍历,通过链表在被调用结构中的项,来获取整个结构的指针(精妙!!)

  1. //ptr:struct list_head类型指针,type:被调用结构体类型,
  2. //member:被调用结构体类型中的struct list_head成员名
  3. #define list_entry(ptr,type,member) \
  4.     container_of(ptr,type,member)
  5. #define container_of(ptr,type,member) ({    \
  6.     const typeof( ((type*)0)->member)*__mptr = (ptr);        \
  7.     (type*)( (char*)__mptr – offsetof(type,member) );    })
  8. #define offsetof(TYPE,MEMBER) ((size_t)&((TYPE*)0)->MEMBER)

将指针指向member对象:const typeof( ((type*)0)->member) *__mptr = ptr;这是通过计算偏移量来实现,具体如下:

而下面一句就绝了:

(type*)( (char *)__mptr – offset(type,member)) //将指针直接偏移到ptr所指向的具体结构体头部,也就是获得到所指定的结构体指针:

这样通过它来遍历所有的结构体就简单多了:

获取目标结构体的项

  1. #define list_entry(ptr,type,member)      \
  2.     container_of(ptr,type,member)

获取链表指向的下一项

  1. #define list_first_entry(ptr,type,member)     \
  2.     list_entry((ptr)->next,type,member)

遍历整个链表

  1. #define list_for_each(pos,head)    \
  2.     for(pos = (head)->next;prefetch(pos->next),pos != (head); \
  3.         pos = pos->next)

prefetch(pos->next):pos->next 地址处所指向的内容预读到CPU L1级缓存

  1. #define __list_for_each(pos,head)    \
  2.     for(pos = (head)->next;pos!=(head);pos = pos->next)

最为常用的是下面的遍历方式:

  1. /**
  2. *pos:list所嵌入的目标结构体变量
  3. *head: 需要进行遍历的链表
  4. *member:目标结构体中链表的成员名称
  5. *返回:具体指向每一项的pos
  6. **/
  7. #define list_for_each_entry(pos,head,member)        \
  8.      for(pos = list_entry((head)->next,typeof(*pos),member);    \
  9.      prefetch(pos->member.next),&pos->member != (head);
  10.      pos = list_entry(pos->member.next,typeof(*pos),member))

阅读(1064) | 评论(0) | 转发(0) |
0

上一篇:list链表分析(一)

下一篇:数据结构--堆

给主人留下些什么吧!~~