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里面的实现可以作为我们的一个借鉴。


添加新评论

选择表情 captcha

友情提醒:不填或错填验证码会引起页面刷新,导致已填的评论内容丢失。

|