PostgreSQL源码里面的List结构

PostgreSQL中广泛使用了一种List数据结构，该结构是一个单链表。其定义在pg_list.h和list.c文件中：

typedef struct ListCell ListCell;

typedef struct List
{
	NodeTag		type;			/* T_List, T_IntList, or T_OidList */
	int			length;
	ListCell   *head;
	ListCell   *tail;
} List;

struct ListCell
{
	union
	{
		void	   *ptr_value;
		int			int_value;
		Oid			oid_value;
	}			data;
	ListCell   *next;
};

List是链表的表头，包含四个成员：
• type：该成员是一个枚举类型，有三个取值：T_List、T_IntList、T_OidList，用于表示该链表里面数据的类型。
• length：列表的长度。
• head：列表的头指针
• tail：列表的尾指针
ListCell是链表的每一个表节点类型，包含一个联合和一个指针：
• 联合里面有三种类型的取值，一个无类型指针，和两个整形（Oid一般定义为整形），这里的取值和链表头List里面的type成员对应。通过这个联合，我们可以定义三种类型的单链表。
• next指针指向下一个节点。

当然，光有数据结构还不行，PG还定义了一套非常丰富的创建、初始化、增、删、遍历的函数。对于比较简单的实现为静态内联函数。因为函数都比较简单，这里不再一一介绍。单链表是我们平时编程里面使用非常普遍的数据结构，我觉得PG里面的实现可以作为我们的一个借鉴。