(八)旋转链表的第一个节点到最后
这个函数的操作的最终结果是将head的next与head自己本身进行了交换。
- static inline void list_rotate_left(struct list_head *head)
-
{
-
struct list_head *first;
-
if (!list_empty(head)) {
-
first = head->next;
-
list_move_tail(first, head);
-
}
-
}
(九)分割链表
这里提供的函数接口是:
static inline void __list_cut_position(struct list_head *list,
struct list_head *head, struct list_head *entry)
list:将剪切的结点要加进来的链表
head:被剪切的链表
entry:所指位于由head所指领头的链表内,它可以指向head,但是这样的话,head就不能被剪切了,在代码中调用了INIT_LIST_HEAD(list)。
是将head(不包括head)到entry之间的所有结点剪切下来加到list所指向的链表中。这个操作之后就有了两个链表head和list。具体的结果参看下面的截图:
- static inline void list_cut_position(struct list_head *list,
-
struct list_head *head, struct list_head *entry)
-
{
-
if (list_empty(head))
-
return;
-
if (list_is_singular(head) &&
-
(head->next != entry && head != entry))
-
return;
-
if (entry == head)
-
INIT_LIST_HEAD(list);
-
else
-
__list_cut_position(list, head, entry);
-
}
真正的分割操作是下面的函数:
- static inline void __list_cut_position(struct list_head *list,
-
struct list_head *head, struct list_head *entry)
-
{
-
struct list_head *new_first = entry->next;
-
list->next = head->next;
-
list->next->prev = list;
-
list->prev = entry;
-
entry->next = list;
-
head->next = new_first;
-
new_first->prev = head;
-
}
分割之前的情况:
分割之后的结果:
(十)链表的合并
提供的接口有四个:
static inline void list_splice(const struct list_head *list,
struct list_head *head)
static inline void list_splice_tail(struct list_head *list,
struct list_head *head)
static inline void list_splice_init(struct list_head *list,
struct list_head *head)
static inline void list_splice_tail_init(struct list_head *list,
struct list_head *head)
真正的合并操作是这个函数实现的:
- static inline void __list_splice(const struct list_head *list,
-
struct list_head *prev,
-
struct list_head *next)
-
{
-
struct list_head *first = list->next;
-
struct list_head *last = list->prev;
-
-
first->prev = prev;
-
prev->next = first;
-
-
last->next = next;
-
next->prev = last;
-
}
这个函数实现的结果是将list领头的这个链表合并到prev和next之间,不包括list这个结点。
- static inline void list_splice(const struct list_head *list,
-
struct list_head *head)
-
{
-
if (!list_empty(list))
-
__list_splice(list, head, head->next);
-
}
将list所指链的内容加到head和head->next之间(类似于头插法)。
- static inline void list_splice_tail(struct list_head *list,
-
struct list_head *head)
-
{
-
if (!list_empty(list))
-
__list_splice(list, head->prev, head);
-
}
将list所指链的内容加到head->prev和head(类似于尾插法),插入之后,head->prev将会是原来的list->prev,这点需要注意。
- static inline void list_splice_init(struct list_head *list,
-
struct list_head *head)
-
{
-
if (!list_empty(list)) {
-
__list_splice(list, head, head->next);
-
INIT_LIST_HEAD(list);
-
}
-
}
将list所指链的内容加到head和head->next之间(类似于头插法),完了之后,将list初始化为一个空链表。
- static inline void list_splice_tail_init(struct list_head *list,
-
struct list_head *head)
-
{
-
if (!list_empty(list)) {
-
__list_splice(list, head->prev, head);
-
INIT_LIST_HEAD(list);
-
}
-
}
将list所指链的内容加到head->prev和head(类似于尾插法),插入之后,head->prev将会是原来的list->prev,这点需要注意,完了之后,将list初始化为一个空链表。
阅读(8053) | 评论(5) | 转发(9) |