首先在源码中这两个类型是这样定义的：
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_INLINE extern 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 int list_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 */
