PostgreSQL源码中的List和ListCell的说明

概述首先在源码中这两个类型是这样定义的： typedef struct ListCell ListCell;typedef struct List{ NodeTag type; /* T_List, T_IntList, or T_OidList */ int length; ListCell *head; ListCell *tail;} List;struct

首先在源码中这两个类型是这样定义的：

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;};

这两个类型的关系是，ListCell是一个单独的个体，作为一个容器来存储内容以及下一个 ListCell的指针。
1、其中如果这是一个由int或者OID构成的List，那么ListCell直接存储int或者OID。若不是，则使用voID*来存储，这样可以存储的类型就多了。一般用的时候直接使用强制转换为(Type *)即可使用。
2、next存储的是下一个ListCell，由此可以说明List是一个线性链表，只能向后寻找。

接下来是有ListCell组成的List，List，没有将整个链存储起来，仅仅将由ListCell组成的线性链表的头和尾。在做查询的时候，也仅仅是通过头进行向后查询。同时还存储了链的两个属性：（1）ListCell的个数；（2）List的类型（T_List,or T_OIDList）。

List的类型是在构建List的时候指定的：

static List *new_List(NodeTag type){	List	   *new_List;	ListCell   *new_head;	new_head = (ListCell *) palloc(sizeof(*new_head));	new_head->next = NulL;	/* new_head->data is left undefined! */	new_List = (List *) palloc(sizeof(*new_List));	new_List->type = type;	new_List->length = 1;	new_List->head = new_head;	new_List->tail = new_head;	return new_List;}

遍历List的方法为：

#define foreach(cell,l)	\	for ((cell) = List_head(l); (cell) != NulL; (cell) = lnext(cell))

#define for_each_cell(cell,initcell)	\	for ((cell) = (initcell); (cell) != NulL; (cell) = lnext(cell))

方法有许多，可以参考 pg_List.h。 另附：pg_List.h

/*------------------------------------------------------------------------- * * pg_List.h *	  interface for Postgresql generic linked List package * * This package implements singly-linked homogeneous Lists. * * It is important to have constant-time length,append,and prepend * operations. To achIEve this,we deal with two distinct data * structures: * *		1. A set of "List cells": each cell contains a data fIEld and *		   a link to the next cell in the List or NulL. *		2. A single structure containing Metadata about the List: the *		   type of the List,pointers to the head and tail cells,and *		   the length of the List. * * We support three types of Lists: * *	T_List: Lists of pointers *		(in practice usually pointers to Nodes,but not always; *		declared as "voID *" to minimize casting annoyances) *	T_IntList: Lists of integers *	T_OIDList: Lists of OIDs * * (At the moment,ints and OIDs are the same size,but they may not * always be so; try to be careful to maintain the distinction.) * * * Portions copyright (c) 1996-2013,Postgresql Global Development Group * Portions copyright (c) 1994,Regents of the University of California * * src/include/nodes/pg_List.h * *------------------------------------------------------------------------- */#ifndef PG_List_H#define PG_List_H#include "nodes/nodes.h"typedef struct ListCell ListCell;typedef struct List{	NodeTag		type;			/* T_List,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;};/* * The *only* valID representation of an empty List is NIL; in other * words,a non-NIL List is guaranteed to have length >= 1 and * head/tail != NulL */#define NIL						((List *) NulL)/* * These routines are used frequently. However,we can't implement * them as macros,since we want to avoID double-evaluation of macro * arguments. Therefore,we implement them using static inline functions * if supported by the compiler,or as regular functions otherwise. * See STATIC_IF_INliNE in c.h. */#ifndef PG_USE_INliNEextern ListCell *List_head(const List *l);extern ListCell *List_tail(List *l);extern int	List_length(const List *l);#endif   /* PG_USE_INliNE */#if defined(PG_USE_INliNE) || defined(PG_List_INCLUDE_DEFinitioNS)STATIC_IF_INliNE ListCell *List_head(const List *l){	return l ? l->head : NulL;}STATIC_IF_INliNE ListCell *List_tail(List *l){	return l ? l->tail : NulL;}STATIC_IF_INliNE intList_length(const List *l){	return l ? l->length : 0;}#endif   /*-- PG_USE_INliNE || PG_List_INCLUDE_DEFinitioNS *//* * NB: There is an unfortunate legacy from a prevIoUs incarnation of * the List API: the macro lfirst() was used to mean "the data in this * cons cell". To avoID changing every usage of lfirst(),that meaning * has been kept. As a result,lfirst() takes a ListCell and returns * the data it contains; to get the data in the first cell of a * List,use linitial(). Worse,lsecond() is more closely related to * linitial() than lfirst(): given a List,lsecond() returns the data * in the second cons cell. */#define lnext(lc)				((lc)->next)#define lfirst(lc)				((lc)->data.ptr_value)#define lfirst_int(lc)			((lc)->data.int_value)#define lfirst_oID(lc)			((lc)->data.oID_value)#define linitial(l)				lfirst(List_head(l))#define linitial_int(l)			lfirst_int(List_head(l))#define linitial_oID(l)			lfirst_oID(List_head(l))#define lsecond(l)				lfirst(lnext(List_head(l)))#define lsecond_int(l)			lfirst_int(lnext(List_head(l)))#define lsecond_oID(l)			lfirst_oID(lnext(List_head(l)))#define lthird(l)				lfirst(lnext(lnext(List_head(l))))#define lthird_int(l)			lfirst_int(lnext(lnext(List_head(l))))#define lthird_oID(l)			lfirst_oID(lnext(lnext(List_head(l))))#define lfourth(l)				lfirst(lnext(lnext(lnext(List_head(l)))))#define lfourth_int(l)			lfirst_int(lnext(lnext(lnext(List_head(l)))))#define lfourth_oID(l)			lfirst_oID(lnext(lnext(lnext(List_head(l)))))#define llast(l)				lfirst(List_tail(l))#define llast_int(l)			lfirst_int(List_tail(l))#define llast_oID(l)			lfirst_oID(List_tail(l))/* * ConvenIEnce macros for building fixed-length Lists */#define List_make1(x1)				lcons(x1,NIL)#define List_make2(x1,x2)			lcons(x1,List_make1(x2))#define List_make3(x1,x2,x3)		lcons(x1,List_make2(x2,x3))#define List_make4(x1,x3,x4)		lcons(x1,List_make3(x2,x4))#define List_make1_int(x1)			lcons_int(x1,NIL)#define List_make2_int(x1,x2)		lcons_int(x1,List_make1_int(x2))#define List_make3_int(x1,x3)	lcons_int(x1,List_make2_int(x2,x3))#define List_make4_int(x1,x4) lcons_int(x1,List_make3_int(x2,x4))#define List_make1_oID(x1)			lcons_oID(x1,NIL)#define List_make2_oID(x1,x2)		lcons_oID(x1,List_make1_oID(x2))#define List_make3_oID(x1,x3)	lcons_oID(x1,List_make2_oID(x2,x3))#define List_make4_oID(x1,x4) lcons_oID(x1,List_make3_oID(x2,x4))/* * foreach - *	  a convenIEnce macro which loops through the List */#define foreach(cell,l)	\	for ((cell) = List_head(l); (cell) != NulL; (cell) = lnext(cell))/* * for_each_cell - *	  a convenIEnce macro which loops through a List starting from a *	  specifIEd cell */#define for_each_cell(cell,initcell)	\	for ((cell) = (initcell); (cell) != NulL; (cell) = lnext(cell))/* * forboth - *	  a convenIEnce macro for advancing through two linked Lists *	  simultaneously. This macro loops through both Lists at the same *	  time,stopPing when either List runs out of elements. Depending *	  on the requirements of the call site,it may also be wise to *	  assert that the lengths of the two Lists are equal. */#define forboth(cell1,List1,cell2,List2)							\	for ((cell1) = List_head(List1),(cell2) = List_head(List2);	\		 (cell1) != NulL && (cell2) != NulL;						\		 (cell1) = lnext(cell1),(cell2) = lnext(cell2))/* * forthree - *	  the same for three Lists */#define forthree(cell1,List2,cell3,List3)			\	for ((cell1) = List_head(List1),(cell2) = List_head(List2),(cell3) = List_head(List3); \		 (cell1) != NulL && (cell2) != NulL && (cell3) != NulL;		\		 (cell1) = lnext(cell1),(cell2) = lnext(cell2),(cell3) = lnext(cell3))extern List *lappend(List *List,voID *datum);extern List *lappend_int(List *List,int datum);extern List *lappend_oID(List *List,OID datum);extern ListCell *lappend_cell(List *List,ListCell *prev,voID *datum);extern ListCell *lappend_cell_int(List *List,int datum);extern ListCell *lappend_cell_oID(List *List,OID datum);extern List *lcons(voID *datum,List *List);extern List *lcons_int(int datum,List *List);extern List *lcons_oID(OID datum,List *List);extern List *List_concat(List *List1,List *List2);extern List *List_truncate(List *List,int new_size);extern voID *List_nth(const List *List,int n);extern int	List_nth_int(const List *List,int n);extern OID	List_nth_oID(const List *List,int n);extern bool List_member(const List *List,const voID *datum);extern bool List_member_ptr(const List *List,const voID *datum);extern bool List_member_int(const List *List,int datum);extern bool List_member_oID(const List *List,OID datum);extern List *List_delete(List *List,voID *datum);extern List *List_delete_ptr(List *List,voID *datum);extern List *List_delete_int(List *List,int datum);extern List *List_delete_oID(List *List,OID datum);extern List *List_delete_first(List *List);extern List *List_delete_cell(List *List,ListCell *cell,ListCell *prev);extern List *List_union(const List *List1,const List *List2);extern List *List_union_ptr(const List *List1,const List *List2);extern List *List_union_int(const List *List1,const List *List2);extern List *List_union_oID(const List *List1,const List *List2);extern List *List_intersection(const List *List1,const List *List2);/* currently,there's no need for List_intersection_int etc */extern List *List_difference(const List *List1,const List *List2);extern List *List_difference_ptr(const List *List1,const List *List2);extern List *List_difference_int(const List *List1,const List *List2);extern List *List_difference_oID(const List *List1,const List *List2);extern List *List_append_unique(List *List,voID *datum);extern List *List_append_unique_ptr(List *List,voID *datum);extern List *List_append_unique_int(List *List,int datum);extern List *List_append_unique_oID(List *List,OID datum);extern List *List_concat_unique(List *List1,List *List2);extern List *List_concat_unique_ptr(List *List1,List *List2);extern List *List_concat_unique_int(List *List1,List *List2);extern List *List_concat_unique_oID(List *List1,List *List2);extern voID List_free(List *List);extern voID List_free_deep(List *List);extern List *List_copy(const List *List);extern List *List_copy_tail(const List *List,int nskip);/* * To ease migration to the new List API,a set of compatibility * macros are provIDed that reduce the impact of the List API changes * as far as possible. Until clIEnt code has been rewritten to use the * new List API,the ENABLE_List_COMPAT symbol can be defined before * including pg_List.h */#ifdef ENABLE_List_COMPAT#define lfirsti(lc)					lfirst_int(lc)#define lfirsto(lc)					lfirst_oID(lc)#define makeList1(x1)				List_make1(x1)#define makeList2(x1,x2)			List_make2(x1,x2)#define makeList3(x1,x3)		List_make3(x1,x3)#define makeList4(x1,x4)	List_make4(x1,x4)#define makeListi1(x1)				List_make1_int(x1)#define makeListi2(x1,x2)			List_make2_int(x1,x2)#define makeListo1(x1)				List_make1_oID(x1)#define makeListo2(x1,x2)			List_make2_oID(x1,x2)#define lconsi(datum,List)			lcons_int(datum,List)#define lconso(datum,List)			lcons_oID(datum,List)#define lappendi(List,datum)		lappend_int(List,datum)#define lappendo(List,datum)		lappend_oID(List,datum)#define nconc(l1,l2)				List_concat(l1,l2)#define nth(n,List)				List_nth(List,n)#define member(datum,List)			List_member(List,datum)#define ptrMember(datum,List)		List_member_ptr(List,datum)#define intMember(datum,List)		List_member_int(List,datum)#define oIDMember(datum,List)		List_member_oID(List,datum)/* * Note that the old lremove() determined equality via pointer * comparison,whereas the new List_delete() uses equal(); in order to * keep the same behavior,we therefore need to map lremove() calls to * List_delete_ptr() rather than List_delete() */#define lremove(elem,List)			List_delete_ptr(List,elem)#define lispRemove(elem,List)		List_delete(List,elem)#define lremovei(elem,List)		List_delete_int(List,elem)#define lremoveo(elem,List)		List_delete_oID(List,elem)#define ltruncate(n,List)			List_truncate(List,n)#define set_union(l1,l2)			List_union(l1,l2)#define set_uniono(l1,l2)			List_union_oID(l1,l2)#define set_ptrUnion(l1,l2)		List_union_ptr(l1,l2)#define set_difference(l1,l2)		List_difference(l1,l2)#define set_differenceo(l1,l2)		List_difference_oID(l1,l2)#define set_ptrDifference(l1,l2)	List_difference_ptr(l1,l2)#define equali(l1,l2)				equal(l1,l2)#define equalo(l1,l2)#define freeList(List)				List_free(List)#define Listcopy(List)				List_copy(List)extern int	length(List *List);#endif   /* ENABLE_List_COMPAT */#endif   /* PG_List_H */

总结

以上是内存溢出为你收集整理的PostgreSQL源码中的List和ListCell的说明全部内容，希望文章能够帮你解决PostgreSQL源码中的List和ListCell的说明所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。