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

全部博文(72)

文章存档

2013年(1)

2012年(17)

2011年(51)

2010年(3)

分类: LINUX

2011-06-20 20:50:58

内核中的所有数据结构,凡是使用链表进行操作的都采用了此链表结构,一般使用的部分如下:

在文件include/linux/list.h

定义:

  1. struct list_head {
  2. struct list_head *next;
  3. struct list_head *prev;
  4. }

初始化链表

  1. static inline void INIT_LIST_HEAD(struct list_head *list)
  2. {
  3.     list ->next = list;
  4.     list ->prev = list;
  5. }

向链表中添加元素

  1. /**
  2. *在prev和next之间插入元素new
  3. **/
  4. static inline void __list_add(struct list_head *new,struct list_head*prev,struct list_head *next)
  5. {
  6.     next ->prev = new;
  7.     new ->next = next;
  8.     new ->prev = prev;
  9.     prev ->next = new;
  10. }

由此产生的链表操作如下:

  1. /**
  2. *在head后面插入new
  3. **/
  4. static inline void list_add(struct list_head *new,struct list_head *head)
  5. {
  6.     __list_add(new,head,head->next);
  7. }
  8. /**
  9. *在head前面插入new
  10. **/
  11. static inline void list_add_tail(struct list_head *new,struct list_head *head)
  12. {
  13.     __list_add(new,head->prev,head);
  14. }

删除链表元素

  1. /*
  2. *prev,next 之间进行互联
  3. */
  4. static inline void __list_del(struct list_head *prev,struct list_head *next)
  5. {
  6.     next ->prev = prev;
  7.     prev->next = next;
  8. }

由此产生的操作有

  1. //删除链表entry
  2. static inline void __list_del_entry(struct list_head *entry)
  3. {
  4. __list_del(entry->prev,entry->next);
  5. }
  6. static inline void list_del(struct list_head *entry)
  7. {
  8. __list_del_entry(entry->prev,entry->next);
  9. entry -> next = LIST_POISON1;//代表未被初始化标志,类似用户空间NULL
  10. entry -> prev = LIST_POISON2;//代表未被初始化标志,类似用户空间NULL
  11. }
  12. //删除元素,并将该元素进行初始化
  13. static inline void list_del_init(struct list_head *entry)
  14. {
  15. __list_del_entry(entry);
  16. INIT_LIST_HEAD(entry);
  17. }

链表替换操作

  1. //用新元素new去代替旧元素old
  2. static inline void list_replace(struct list_head *old,struct list_head *new)
  3. {
  4.     new ->next = old->next;
  5.     new ->next->prev = new;
  6.     new ->prev = old->prev;
  7.     new->prev->next = new;
  8. }
  9. //替换完元素,并将旧元素进行初始化
  10. static inline void list_replace_init(struct list_head *old,struct list_head *new)
  11. {
  12.     list_replace(old,new)
  13.     INIT_LIST_HEAD(old);
  14. }

移动链表

  1. //将list链表移动到head的后面
  2. static inline void list_move(struct list_head *list,struct list_head *head)
  3. {
  4.     __list_del_entry(list);//从原来链表中删除该元素
  5.     list_add(list,head);//添加到head后面
  6. }
  7. //将list链表移动到head的尾部
  8. static inline void list_move_tail(struct list_head *list,struct list_head *head)
  9. {
  10.     __list_del_entry(list);
  11.     list_add_tail(list,head);
  12. }

判断链表

  1. //链表元素list是否为head中最后一个元素
  2. static inline int list_is_last(const struct list_head *list,const list_head *head)
  3. {
  4.     return list->next = head;
  5. }
  6. //判断链表是否为空
  7. static inline int list_empty(const struct list_head *head)
  8. {
  9.     return head->next == head;
  10. }
  11. //在使用时需要进行同步
  12. static inline int list_empty_careful(struct struct list_head *head)
  13. {
  14.     struct list_head *next = head->next;
  15.     return (next==head) && (next == head->prev);
  16. }
  17. //判断链表是否只有一个元素
  18. static inline int list_is_singular(const struct list_head *head)
  19. {
  20.     return !list_empty(head)&& (head->next == head->prev);
  21. }

高级操作

将链表左移一个元素

  1. static inline void list_rotate_left(struct list_head *head)
  2. {
  3.     struct list_head *first;
  4.     if(!list_empty(head)) {
  5.      first = head->next;//将头部后面的一个元素移动到尾部,相当于左旋转
  6.      list_move_tail(first,head);
  7. }
  8. }

list链表元素删除,将head中从head->nextentry的所有元素形成新的链表list,headentry->next为一链表,实际将链表一分为二:

list:head->next  <---> entry

head:entry<--->head->prev

  1. static inline void __list_cut_position(struct list_head *list,struct list_head *head,
  2.             struct list_entry *entry)
  3. {
  4.     struct list_head *new_first = entry->next;
  5.     list ->next = head->next;
  6.     list ->next->prev = list;
  7.     list ->prev = entry;
  8.     entry ->next = list;
  9.     head->next = new_first;
  10.     new_first->prev = head;
  11. }

由此产生的函数有:

  1. static inline void list_cut_position(struct list_head *list
  2. ,struct list_head *head,struct list_head *entry)
  3. {
  4. //链表不为空
  5. if(list_empty(head)) return;
  6. //单个元素的链表
  7. if(list_is_singular(head) &&
  8. (head->next != entry && head !=entry))
  9. return;
  10. //如果分割从头部开始,就不需要进行分割
  11. if(entry == head) INIT_LIST_HEAD(list);
  12. //进行分割
  13. else __list_cut_position(list,head,entry);
  14. }


阅读(1249) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~