由于最近准备深入学习一下Linux驱动。因此见到不少内核中的数据结构，其中List是应用非常广泛的数据结构，因此在这里做个记录。

Linux内核中相关的文件是/include/list.h

这里先贴一下代码：

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

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

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

一般，我们在使用时，先定义一个链表头static LIST_HEAD(test_list);

将其展开后为：

static struct list_head test_list = {&test_list, &test_list};

而在我们使用的时候这个链表并不是像普通链表那样，直接拿到节点后取出成员进行操作。普通的链表都是先定义节点，然后节点中有数据以及前后节点的指针。但是这样有个不好的地方是，当数据有不同类型时就需要定义不同的链表，这样就没法使用通用的操作手法来使用链表了。因此在Linux中采用的是链表节点放在数据节点中，再将这些节点串联起来。操作链表的时候就可以使用一套通用的方式来操作了。不过前提是取得链表节点后需要反推得到数据节点的地址。这里以SPI驱动中的一个结构体来举例说明：

struct spidev_data {
	dev_t			devt;
	spinlock_t		spi_lock;
	struct spi_device	*spi;
	struct list_head	device_entry;

	/* buffer is NULL unless this device is open (users > 0) */
	struct mutex		buf_lock;
	unsigned		users;
	u8			*buffer;
};

这里只要关注device_entry成员，它是一个链表节点。操作链表的时候就是通过它将所有spi设备串联起来的。

首先，将链表节点初始化，即next,prev都指向自己。

INIT_LIST_HEAD(&spidev->device_entry);

其次，将其添加到一个链表头：

list_add(&spidev->device_entry, &device_list);

当需要遍历链表的时候使用：

list_for_each_entry(spidev, &device_list, device_entry) {
		if (spidev->devt == inode->i_rdev) {
			status = 0;
			break;
		}
	}


#define list_for_each_entry(pos, list, member)			\
	for (pos = list_head(list, typeof(*pos), member);	\
	     &pos->member != (list);				\
	     pos = list_next(pos, member))


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

list_for_each_entry宏展开后得到一个fort循环，不断取出链表节点的父结构指针。这里就是spidev结构了。循环变量就是每个链表的节点，起始是节点头，这里应该比较好理解，也是常规操作。唯一比较难理解的是如何取得父结构的指针。实现功能的即list_entry宏，它先将0转为父结构指针类型，再得到其成员结构指针，由于它是0地址作为起始，因此成员地址也等于它与父结构地址的偏移了。因此再将实际成员（link）的地址减去偏移就可以得到父结构地址，再将其强制转换为父结构类型指针。这样就实现了虽然链表遍历是通过成员结构进行，但操作却用父结构指针来操作。

转载请注明：OpenMind » Linux内核中的List