list链表分析(一)

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

在文件include/linux/list.h

定义:

struct list_head {
struct list_head *next;
struct list_head *prev;
}

初始化链表

static inline void INIT_LIST_HEAD(struct list_head *list)
{
    list ->next = list;
    list ->prev = list;
}

向链表中添加元素

/**
*在prev和next之间插入元素new
**/
static inline void __list_add(struct list_head *new,struct list_head*prev,struct list_head *next)
{
    next ->prev = new;
    new ->next = next;
    new ->prev = prev;
    prev ->next = new;
}

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

/**
*在head后面插入new
**/
static inline void list_add(struct list_head *new,struct list_head *head)
{
    __list_add(new,head,head->next);
}
/**
*在head前面插入new
**/
static inline void list_add_tail(struct list_head *new,struct list_head *head)
{
    __list_add(new,head->prev,head);
}

删除链表元素

/*
*prev,next 之间进行互联
*/
static inline void __list_del(struct list_head *prev,struct list_head *next)
{
    next ->prev = prev;
    prev->next = next;
}

由此产生的操作有

//删除链表entry
static inline void __list_del_entry(struct list_head *entry)
{
__list_del(entry->prev,entry->next);
}
static inline void  list_del(struct list_head *entry)
{
__list_del_entry(entry->prev,entry->next);
entry -> next = LIST_POISON1;//代表未被初始化标志,类似用户空间NULL
entry -> prev = LIST_POISON2;//代表未被初始化标志,类似用户空间NULL
}
//删除元素，并将该元素进行初始化
static inline void list_del_init(struct list_head *entry)
{
__list_del_entry(entry);
INIT_LIST_HEAD(entry);
}

链表替换操作

//用新元素new去代替旧元素old
static inline void list_replace(struct list_head *old,struct list_head *new)
{
    new ->next = old->next;
    new ->next->prev = new;
    new ->prev = old->prev;
    new->prev->next = new;
}
//替换完元素，并将旧元素进行初始化
static inline void list_replace_init(struct list_head *old,struct list_head *new)
{
    list_replace(old,new)
    INIT_LIST_HEAD(old);
}

移动链表

//将list链表移动到head的后面
static inline void  list_move(struct list_head *list,struct list_head *head)
{
    __list_del_entry(list);//从原来链表中删除该元素
    list_add(list,head);//添加到head后面
}
//将list链表移动到head的尾部
static inline void list_move_tail(struct list_head *list,struct list_head *head)
{
    __list_del_entry(list);
    list_add_tail(list,head);
}

判断链表

//链表元素list是否为head中最后一个元素
static inline int list_is_last(const struct list_head *list,const list_head *head)
{
    return list->next = head;
}
//判断链表是否为空
static inline int list_empty(const struct list_head *head)
{
    return head->next == head;
}
//在使用时需要进行同步
static inline int list_empty_careful(struct struct list_head *head)
{
    struct list_head *next = head->next;
    return (next==head) && (next == head->prev);
}
//判断链表是否只有一个元素
static inline int list_is_singular(const struct list_head *head)
{
    return !list_empty(head)&& (head->next == head->prev);
}

高级操作

将链表左移一个元素

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);
}
}

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

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

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

static inline void __list_cut_position(struct list_head *list,struct list_head *head,
            struct list_entry *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_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);
}