【Linux】Kernel中链表及常用函数和宏

处理链表：

内核基本都是双向链表，其基本结构：

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

xx/include/linux/list.h 文件记录了操作双向链表函数

初始化双向链表：
1.用INIT_LIST_HEAD函数初始化一个双向链表

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

2.使用宏创建并初始化一个双向链表

#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) \
    struct list_head name = LIST_HEAD_INIT(name)

还有其他链表操作函数，认真分析还是很容易搞定，在此不多介绍；


下面介绍下内核中经常会用到的（跟链表相关的）宏：

1. list_entry: 与container_of功能相同；

/**
 * list_entry - get the struct for this entry
 * @ptr:    the &struct list_head pointer.
 * @type:    the type of the struct this is embedded in.
 * @member:    the name of the list_struct within the struct.
 */
#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

2. list_for_each：向后（next）遍历head所指链表每个节点

/**
 * list_for_each    -    iterate over a list
 * @pos:    the &struct list_head to use as a loop cursor.
 * @head:    the head for your list.
 */
#define list_for_each(pos, head) \
    for (pos = (head)->next; pos != (head); pos = pos->next)

3. list_for_each_prev：向前（prev）遍历head所指链表每个节点

/**
     * list_for_each_prev    -    iterate over a list backwards
     * @pos:    the &struct list_head to use as a loop cursor.
     * @head:    the head for your list.
     */
    #define list_for_each_prev(pos, head) \
        for (pos = (head)->prev; pos != (head); pos = pos->prev)

4. list_for_each_entry：

/**
 * list_for_each_entry    -    iterate over list of given type
 * @pos:    the type * to use as a loop cursor.
 * @head:    the head for your list.
 * @member:    the name of the list_struct within the struct.
 */
#define list_for_each_entry(pos, head, member)                \
    for (pos = list_entry((head)->next, typeof(*pos), member);    \
         &pos->member != (head);     \
         pos = list_entry(pos->member.next, typeof(*pos), member))

注：关于typeof可见：http://paullu.blog.51cto.com/828864/169145
举个例子：

struct kobject *k;

list_for_each_entry(k, &kset->list, entry) {
        if (kobject_name(k) && !strcmp(kobject_name(k), name)) {
            ret = kobject_get(k);
            break;
        }
//这是在kset_find_obj_hinted函数中使用的遍历kset中的kobject链表，寻找与name同名的kobject；

#####################################################################
接下来看看Klist，内核中使用的非常频繁，它是对list_head的扩展

相关代码位于：xx/include/linux/klist.h，xx/lib/klist.c

struct klist {
    spinlock_t        k_lock;
    struct list_head    k_list;
    void            (*get)(struct klist_node *);
    void            (*put)(struct klist_node *);
} __attribute__ ((aligned (sizeof(void *))));    /* 按指针大小对齐 */

struct klist_node {
    void            *n_klist;    /* never access directly */
    struct list_head    n_node;
    struct kref        n_ref;
};

struct klist_iter {
    struct klist        *i_klist;
    struct klist_node    *i_cur;
};

待续。。。