Chinaunix首页 | 论坛 | 博客
  • 博客访问: 2008580
  • 博文数量: 505
  • 博客积分: 1552
  • 博客等级: 上尉
  • 技术积分: 2524
  • 用 户 组: 普通用户
  • 注册时间: 2007-09-23 18:24
文章分类

全部博文(505)

文章存档

2019年(12)

2018年(15)

2017年(1)

2016年(17)

2015年(14)

2014年(93)

2013年(233)

2012年(108)

2011年(1)

2009年(11)

分类: C/C++

2013-01-23 08:40:40

(四)删除结点
指定一个结点,删除这个结点
我们调用的话,调用
static inline void list_del(struct list_head *entry)
这个函数接口就可以了。
  1. static inline void __list_del(struct list_head * prev, struct list_head * next)
  2. {
  3.     next->prev = prev;
  4.     prev->next = next;
  5. }
  6. static inline void list_del(struct list_head *entry)
  7. {
  8.     __list_del(entry->prev, entry->next);
  9.     entry->next = LIST_POISON1;
  10.     entry->prev = LIST_POISON2;
  11. }
__list_del(entry->prev, entry->next)表示将entry的前一个和后一个之间建立关联。
至于让,
entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;
LIST_POISON1和LIST_POISON2这两个变量在poison.h中定义的:
#define LIST_POISON1  ((void *) 0x00100100 + POISON_POINTER_DELTA)
#define LIST_POISON2  ((void *) 0x00200200 + POISON_POINTER_DELTA)
prev、next指针分别被设为LIST_POSITION2和LIST_POSITION1两个特殊值,这样设置是为了保证不在链表中的节点项不可访问(对LIST_POSITION1和LIST_POSITION2的访问都将引起页故障)。
还有一个删除操作的接口函数
  1. static inline void list_del_init(struct list_head *entry)
  2. {
  3.     __list_del(entry->prev, entry->next);
  4.     INIT_LIST_HEAD(entry);
  5. }
这个函数首先将entry从双向链表中删除之后,并且将entry初始化为一个空链表。
list_del(entry)和list_del_init(entry)唯一不同的是对entry的处理,前者是将entry设置为不可用,后者是将其设置为一个空的链表的开始。
(五)替换结点
结点的替换操作是将old的结点替换成new,提供的接口是
static inline void list_replace_init(struct list_head *old,
struct list_head *new);
下面是替换的有关代码
  1. static inline void list_replace(struct list_head *old,
  2.                 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. static inline void list_replace_init(struct list_head *old,
  10.                     struct list_head *new)
  11. {
  12.     list_replace(old, new);
  13.     INIT_LIST_HEAD(old);
  14. }
List_replace_init首先调用list_replace改变new和old的指针关系,然后调用INIT_LIST_HEAD(old)将其设置为一个指向自己的结点(这个操作和前面的删除操作是一样的——初始化)。
(六)结点搬移
搬移就是将一个结点从一个链表但终删除之后,加入到其他的一新的链表当中。这里提供了两个接口:
static inline void list_move(struct list_head *list, struct list_head *head)
static inline void list_move_tail(struct list_head *list,struct list_head *head)
前者是加入的时候使用头插法,后者使用的是尾插法。
static inline void list_move(struct list_head *list, struct list_head *head)
{
__list_del(list->prev, list->next);
list_add(list, head);
}
首先调用__list_del(list->prev, list->next),将list的前一个结点和后一个结点建立联系,之后调用list_add(list, head)将list添加到head的链表。下面的和这个类似,不同的是使用的是尾插法。
static inline void list_move_tail(struct list_head *list,
 struct list_head *head)
{
__list_del(list->prev, list->next);
list_add_tail(list, head);
}
(七)检测是否为最后节点、检测链表是否为空、检测链表是不是有一个成员结点
判断list这个结点是不是链表head的最后一个节点。
static inline int list_is_last(const struct list_head *list,
const struct list_head *head)
{
return list->next == head;
}
下面两个接口都是判断head这个链表是不是为一个空链表(也就是只进行过初始化操作或者是刚申请的一个变量)。
  1. static inline int list_empty(const struct list_head *head)
  2. {
  3.     return head->next == head;
  4. }
  5. static inline int list_empty_careful(const struct list_head *head)
  6. {
  7.     struct list_head *next = head->next;
  8.     return (next == head) && (next == head->prev);
  9. }
list_empty()函数和list_empty_careful()函数都是用来检测链表是否为空的。但是稍有区别的就是第一个链表使用的检测方法是判断表头的结点的下一个结点是否为其本身,如果是则返回为1,否则返回0。第二个函数使用的检测方法是判断表头的前一个结点和后一个结点是否为其本身,如果同时满足则返回0,否则返回值为1。
这主要是为了应付另一个cpu正在处理同一个链表而造成next、prev不一致的情况。但代码注释也承认,这一安全保障能力有限:除非其他cpu的链表操作只有list_del_init(),否则仍然不能保证安全,也就是说,还是需要加锁保护。
下面的这个函数是用来判断head这个链表是不是只有一个成员结点(不算带头结点的那个head)。
  1. static inline int list_is_singular(const struct list_head *head)
  2. {
  3.     return !list_empty(head) && (head->next == head->prev);
  4. }
阅读(534) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册