Android中的雙向鏈表

1.看源碼必須搞懂Android的數據結構。在init源代碼中雙向鏈表listnode使用很多，它只有prev和next兩個指針，沒有任何數據成員。這個和linux內核的list_head如出一轍，由此可見安卓深受linux內核的影響的。本來來分析一下這個listnode數據結構。

這裡需要考慮的一個問題是，鏈表操作都是通過listnode進行的，但是那不過是個連接件，如果我們手上有個宿主結構，那當然知道了它的某個listnode在哪裡，從而以此為參數調用list_add和list_del函數；可是，反過來，當我們順著鏈表取得其中一項的listnode結構時，又怎樣找到其宿主結構呢？在listnode結構中並沒有指向其宿主結構的指針啊。畢竟，我們我真正關心的是宿主結構，而不是連接件。對於這個問題，我們舉例內核中的list_head的例子來解決。內核的page結構體含有list_head成員，問題是：知道list_head的地址，如何獲取page宿主的地址？下面是取自mm/page_alloc.c中的一行代碼：

page = memlist_entry(curr, struct page, list);

這裡的memlist_entry將一個list_head指針curr換算成其宿主結構的起始地址，也就是取得指向其宿主page結構的指針。讀者可能會對memlist_entry()的實現感到困惑。

#define memlist_entry list_entry

而list_entry定義則在include/linux/list.h中

135 /**
136 * list_entry get
the struct for this entry
137 * @ptr: the &struct list_head pointer.
138 * @type: the type of the struct this is embedded in.
139 * @member: the name of the list_struct within the struct.
140 */
141 #define list_entry(ptr, type, member) \
142 ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

這樣我們應該就明白了，curr是一個page結構內部成分list的地址，而我們所需要的卻是那個page結構本身的地址，所以要從curr減去一個偏移量，即成分list在page內部的位移量。那麼這個位移量怎麼求？&((struct page*)0)->list就表示當結構page正好在地址0上時其成分list的地址，這就是所求的偏移量。

2.測試代碼

#include
#include

typedef struct _listnode
{
        struct _listnode *prev;
        struct _listnode *next;
}listnode;

#define node_to_item(node,container,member) \
(container*)(((char*)(node))-offsetof(container,member))

//向list雙向鏈表尾部添加node節點,list始終指向雙向鏈表的頭部（這個頭部只含有prev/next)
void list_add_tail(listnode *list,listnode *node)
{
        list->prev->next=node;
        node->prev=list->prev;
        node->next=list;
        list->prev=node;
}
//定義一個測試的宿主結構
typedef struct _node
{
        int data;
        listnode list;
}node;

int main()
{
        node n1,n2,n3,*n;
        listnode list,*p;
        n1.data=1;
        n2.data=2;
        n3.data=3;
        list.prev=&list;
        list.next=&list;
        list_add_tail(&list,&n1.list);
        list_add_tail(&list,&n2.list);
        list_add_tail(&list,&n3.list);
        for(p=list.next;p!=&list;p=p->next)
        {
                n=node_to_item(p,node,list);
                printf("%d\n",n->data);
        }
        return 0;
}