世界上只有一种真正的英雄主义,那就是认清生活的真相后还依然热爱生活。

Linux内核中的List

C语言 smallfish 14℃ 0评论

由于最近准备深入学习一下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

喜欢 (0)
发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址