链表宏list_entry

corosync代码, 其中有一个list的实现, 用到了list_entry这个宏。 了解linux内核的同学估计会眼睛一亮, nod, 就是内核里的那个list_entry。 在内核里, 几乎所有的链表实现, 都用到了一个通用的list_head结构, 但读它的声明发现, 它与链表里保存的实际数据结构完全无关, 仅包含前后两个指针。 当需要访问实际的数据结构时候, 便使用这个list_entry计算出实际数据的地址。

下边是list_entry宏的定义(新版内核移到了container_of里):

#define list_entry(ptr, type, member)                            \
    ((type*)((char*)(ptr) - (unsigned long)(&((type*)0)->member)))

具体使用的时候是这样的:

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

struct test_list {
    int data;                   /* other items */
    struct list_head list;
};

/* travel list with list head ptr. itr & head_ptr are both list_head pointers. */
for (itr = head_ptr->next; itr != head_ptr; itr = itr->next) {
    element = list_entry(itr, struct list_element, list);
    /* deal with element->data */
}

我们可以看到, 只需要知道 list_head 头指针, 就可以通过 list_entry 访问整个 test_list, 虽然 list_headtest_list 的具体数据结构没有任何关系。 是不是联想到了C++里的继承? 所有的 list 都继承自 list_head 这个“基类”,可以通过这个基类指针和函数,访问实际的派生类对象。所有的关键就在于 list_entry 这个宏,我们来分析一下。这个宏分为两部分:

第一部分很简单, (char*)(ptr), 获取 ptr 的地址。

第二部分是关键, (&((type*)0)->member), 这是一个类型转换, 告诉编译器地址0处有一个类型为type的对象, 因为编译器知道type的类型声明, 所以它能够取得其对象成员member的地址, 又因为这个地址是从地址0开始的, 这样实际就获得了member成员在type结构中的相对偏移。 unsigned long类型转换表明这是一个偏移量, 并且保证在32位和64位机器上都正确。

两者相减就获取到了实际数据结构的地址。

这是指针的强大之处, 突然联想起为何C++中会限制指针。 POD类型, 简单, 直接, 而其他C++类型由于要实现OO、多态, 编译器会自动插入代码, 这导致指针的使用容易触碰到很多暗礁。 为了更强大的功能, 引入了更高的复杂度, 而这复杂度同时也限制了一部分功能。

2009-12-19 09:07
status: part
comments powered by Disqus