list.h分析

在讲list.h前，我们必须对链表有一个大体了解。
      首先链表是一种存放和操作可变数量元素的数据结构。链表和数组有何不同？他们的不同之处在于，链表所包含的元素都是动态创建的，在编译时，不必知道具体需要创建多少个元素，另外也因为链表的每个元素的创建时间各不相同，所以他们在内存中无需占用连续的内存空间。
        链表存放数据的理想情况是：需要遍历所有数据或需要动态加入和删除数据。
         链表分为单链表，双链表和循环链表。简单说下单链表就是其域中只有一个指针域。
        当然我现在分析的是循环双链表。
        1、链表的初始化
#define LIST_HEAD_INIT(name) { &(name), &(name) }
 
 #define LIST_HEAD(name)     struct list_head name = LIST_HEAD_INIT(name)
 
 static inline void INIT_LIST_HEAD(struct list_head *list)
 {
         list->next = list;
        list->prev = list;
 }上面分别使用宏和函数实现了链表的初始化，至于里面的inline函数，我上一篇已做了分析。
2、链表节点的定义
     struct list_head
{
         struct list_head *prev, *next;
}
从其函数名就可以看出链表没有“头节点”，因为其是双向的，任何一个节点都可以做头节点。
3、相关链表的插入操作，对节点的插入操作，在我们做起来就是通过写个代码实现，没神嘛，但是不觉得再在插入的基础上出现什么头插，尾插。是不是我们都要写？看牛人写代码就是不一样，人家使用了内部函数，实现了代码的重复利用率。
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;
};这就是内部函数，接下来实现头插和尾插就很方便了。
头插：实现了栈操作
static inline void list_add(struct list_head *new, struct list_head *head)
  {
          __list_add(new, head, head->next);
  }
尾插：实现了队操作
static inline void list_add_tail(struct list_head *new, struct list_head *he    ad)
  {
          __list_add(new, head->prev, head);
  }
4、接下来是节点的删除（也使用了内部函数）
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->prev, entry->next);
}
对节点的删除，内核并没有回收删除节点的数据结构所占用的内存，而是仅仅将其从链表中移走。
好了，链表的基本操作大体介绍了。现在如何遍历链表？
内核提供了list_for_each()宏来实现链表的遍历，具体原型如下：
#define list_for_each(pos, head) \
         for (pos = (head)->next; prefetch(pos->next), pos != (head); \
                pos = pos->next)

其中head是已经定义并初始化的一个数据结构体。（切记）
链表的初始化：
首先定义一个数据结构体
struct datainfo
{
   int num;
   struct list_head list;
};
做动态初始化：
struct datainfo *head;
head->num=0;
INIT_LIST_HEAD (&head->list);
有了遍历函数，如何通过list_head成员访问到它所在数据结构中其他数据？
list_entry()宏就实现了这样的操作。
#define list_entry(ptr, type, member)       container_of(ptr, type, member)
其中ptr指向list_head的指针，type是定义的数据结构，member则是数据结构定义中list_head的成元变量名。
具体实现如下：
struct  list_head *p;
struct  datainfo *data;
list_for_each(p,data->list)
{
   data=list_entry(p,struct datainfo,list);
}
自此，一个链表基本就分析完了。当然链表中还有其他操作，我只介绍了几种常用操作。