Reimplement the linked list data structure used throughout the backend.

In the past, we used a 'Lispy' linked list implementation: a "list" was
merely a pointer to the head node of the list. The problem with that
design is that it makes lappend() and length() linear time. This patch
fixes that problem (and others) by maintaining a count of the list
length and a pointer to the tail node along with each head node pointer.
A "list" is now a pointer to a structure containing some meta-data
about the list; the head and tail pointers in that structure refer
to ListCell structures that maintain the actual linked list of nodes.

The function names of the list API have also been changed to, I hope,
be more logically consistent. By default, the old function names are
still available; they will be disabled-by-default once the rest of
the tree has been updated to use the new API names.

5 files changed, 144 insertions, 143 deletions

diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index 1b4c9d47809..efa7dd77122 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -10,7 +10,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/optimizer/plan/createplan.c,v 1.169 2004/04/25 18:23:56 neilc Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/plan/createplan.c,v 1.170 2004/05/26 04:41:24 neilc Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -263,7 +263,7 @@ build_relation_tlist(RelOptInfo *rel)
 {
 	FastList	tlist;
 	int			resdomno = 1;
-	List	   *v;
+	ListCell   *v;
 
 	FastListInit(&tlist);
 	foreach(v, FastListValue(&rel->reltargetlist))
@@ -415,7 +415,7 @@ create_append_plan(Query *root, AppendPath *best_path)
 	Append	   *plan;
 	List	   *tlist = build_relation_tlist(best_path->path.parent);
 	List	   *subplans = NIL;
-	List	   *subpaths;
+	ListCell   *subpaths;
 
 	foreach(subpaths, best_path->subpaths)
 	{
@@ -505,7 +505,7 @@ create_unique_plan(Query *root, UniquePath *best_path)
 	List	   *newtlist;
 	int			nextresno;
 	bool		newitems;
-	List	   *l;
+	ListCell   *l;
 
 	subplan = create_plan(root, best_path->subpath);
 
@@ -544,7 +544,7 @@ create_unique_plan(Query *root, UniquePath *best_path)
 			break;
 		}
 	}
-	if (l == NIL)				/* fell out of loop? */
+	if (l == NULL)				/* fell out of loop? */
 		elog(ERROR, "could not find UniquePath in in_info_list");
 
 	/* set up to record positions of unique columns */
@@ -702,7 +702,7 @@ create_indexscan_plan(Query *root,
 	List	   *indxsubtype;
 	List	   *indxlossy;
 	FastList	indexids;
-	List	   *i;
+	ListCell   *l;
 	IndexScan  *scan_plan;
 
 	/* it should be a base rel... */
@@ -727,7 +727,7 @@ create_indexscan_plan(Query *root,
 		 */
 		Assert(length(best_path->indexclauses) == 1);
 		scan_clauses = set_ptrUnion(scan_clauses,
-									(List *) lfirst(best_path->indexclauses));
+									(List *) linitial(best_path->indexclauses));
 	}
 
 	/* Reduce RestrictInfo list to bare expressions */
@@ -738,9 +738,9 @@ create_indexscan_plan(Query *root,
 
 	/* Build list of index OIDs */
 	FastListInit(&indexids);
-	foreach(i, best_path->indexinfo)
+	foreach(l, best_path->indexinfo)
 	{
-		IndexOptInfo *index = (IndexOptInfo *) lfirst(i);
+		IndexOptInfo *index = (IndexOptInfo *) lfirst(l);
 
 		FastAppendo(&indexids, index->indexoid);
 	}
@@ -750,9 +750,9 @@ create_indexscan_plan(Query *root,
 	 * executor as indxqualorig
 	 */
 	stripped_indxquals = NIL;
-	foreach(i, indxquals)
+	foreach(l, indxquals)
 	{
-		List   *andlist = (List *) lfirst(i);
+		List   *andlist = (List *) lfirst(l);
 
 		stripped_indxquals = lappend(stripped_indxquals,
 									 get_actual_clauses(andlist));
@@ -785,7 +785,7 @@ create_indexscan_plan(Query *root,
 		 * behavior.
 		 */
 		Assert(stripped_indxquals != NIL);
-		qpqual = set_difference(scan_clauses, lfirst(stripped_indxquals));
+		qpqual = set_difference(scan_clauses, linitial(stripped_indxquals));
 	}
 
 	/*
@@ -955,7 +955,7 @@ create_nestloop_plan(Query *root,
 			joinrestrictclauses =
 				select_nonredundant_join_clauses(root,
 												 joinrestrictclauses,
-												 lfirst(indexclauses),
+												 linitial(indexclauses),
 												 best_path->jointype);
 		}
 	}
@@ -1182,17 +1182,17 @@ fix_indxqual_references(List *indexquals, IndexPath *index_path,
 {
 	Relids		baserelids = index_path->path.parent->relids;
 	int			baserelid = index_path->path.parent->relid;
-	List	   *ixinfo = index_path->indexinfo;
-	List	   *i;
+	List	   *index_info = index_path->indexinfo;
+	ListCell   *iq, *ii;
 
 	*fixed_indexquals = NIL;
 	*indxstrategy = NIL;
 	*indxsubtype = NIL;
 	*indxlossy = NIL;
-	foreach(i, indexquals)
+	forboth(iq, indexquals, ii, index_info)
 	{
-		List	   *indexqual = lfirst(i);
-		IndexOptInfo *index = (IndexOptInfo *) lfirst(ixinfo);
+		List	   *indexqual = (List *) lfirst(iq);
+		IndexOptInfo *index = (IndexOptInfo *) lfirst(ii);
 		List	   *fixed_qual;
 		List	   *strategy;
 		List	   *subtype;
@@ -1204,8 +1204,6 @@ fix_indxqual_references(List *indexquals, IndexPath *index_path,
 		*indxstrategy = lappend(*indxstrategy, strategy);
 		*indxsubtype = lappend(*indxsubtype, subtype);
 		*indxlossy = lappend(*indxlossy, lossy);
-
-		ixinfo = lnext(ixinfo);
 	}
 }
 
@@ -1232,15 +1230,15 @@ fix_indxqual_sublist(List *indexqual,
 					 List **subtype,
 					 List **lossy)
 {
-	List	   *i;
+	ListCell   *l;
 
 	*fixed_quals = NIL;
 	*strategy = NIL;
 	*subtype = NIL;
 	*lossy = NIL;
-	foreach(i, indexqual)
+	foreach(l, indexqual)
 	{
-		RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
+		RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
 		OpExpr	   *clause;
 		OpExpr	   *newclause;
 		Oid			opclass;
@@ -1250,8 +1248,7 @@ fix_indxqual_sublist(List *indexqual,
 
 		Assert(IsA(rinfo, RestrictInfo));
 		clause = (OpExpr *) rinfo->clause;
-		if (!IsA(clause, OpExpr) ||
-			length(clause->args) != 2)
+		if (!IsA(clause, OpExpr) || length(clause->args) != 2)
 			elog(ERROR, "indexqual clause is not binary opclause");
 
 		/*
@@ -1275,7 +1272,7 @@ fix_indxqual_sublist(List *indexqual,
 		 * Now, determine which index attribute this is, change the
 		 * indexkey operand as needed, and get the index opclass.
 		 */
-		lfirst(newclause->args) = fix_indxqual_operand(lfirst(newclause->args),
+		linitial(newclause->args) = fix_indxqual_operand(linitial(newclause->args),
 													   baserelid,
 													   index,
 													   &opclass);
@@ -1309,7 +1306,7 @@ fix_indxqual_operand(Node *node, int baserelid, IndexOptInfo *index,
 	 */
 	Var		   *result;
 	int			pos;
-	List	   *indexprs;
+	ListCell   *indexpr_item;
 
 	/*
 	 * Remove any binary-compatible relabeling of the indexkey
@@ -1340,29 +1337,29 @@ fix_indxqual_operand(Node *node, int baserelid, IndexOptInfo *index,
 	}
 
 	/* Try to match against index expressions */
-	indexprs = index->indexprs;
+	indexpr_item = list_head(index->indexprs);
 	for (pos = 0; pos < index->ncolumns; pos++)
 	{
 		if (index->indexkeys[pos] == 0)
 		{
 			Node	   *indexkey;
 
-			if (indexprs == NIL)
+			if (indexpr_item == NULL)
 				elog(ERROR, "too few entries in indexprs list");
-			indexkey = (Node *) lfirst(indexprs);
+			indexkey = (Node *) lfirst(indexpr_item);
 			if (indexkey && IsA(indexkey, RelabelType))
 				indexkey = (Node *) ((RelabelType *) indexkey)->arg;
 			if (equal(node, indexkey))
 			{
 				/* Found a match */
 				result = makeVar(baserelid, pos + 1,
-								 exprType(lfirst(indexprs)), -1,
+								 exprType(lfirst(indexpr_item)), -1,
 								 0);
 				/* return the correct opclass, too */
 				*opclass = index->classlist[pos];
 				return (Node *) result;
 			}
-			indexprs = lnext(indexprs);
+			indexpr_item = lnext(indexpr_item);
 		}
 	}
 
@@ -1383,11 +1380,11 @@ static List *
 get_switched_clauses(List *clauses, Relids outerrelids)
 {
 	List	   *t_list = NIL;
-	List	   *i;
+	ListCell   *l;
 
-	foreach(i, clauses)
+	foreach(l, clauses)
 	{
-		RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(i);
+		RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
 		OpExpr	   *clause = (OpExpr *) restrictinfo->clause;
 
 		Assert(is_opclause(clause));
@@ -1432,7 +1429,7 @@ order_qual_clauses(Query *root, List *clauses)
 {
 	FastList	nosubplans;
 	FastList	withsubplans;
-	List	   *l;
+	ListCell   *l;
 
 	/* No need to work hard if the query is subselect-free */
 	if (!root->hasSubLinks)
@@ -1442,7 +1439,7 @@ order_qual_clauses(Query *root, List *clauses)
 	FastListInit(&withsubplans);
 	foreach(l, clauses)
 	{
-		Node	   *clause = lfirst(l);
+		Node	   *clause = (Node *) lfirst(l);
 
 		if (contain_subplans(clause))
 			FastAppend(&withsubplans, clause);
@@ -1632,7 +1629,7 @@ make_append(List *appendplans, bool isTarget, List *tlist)
 {
 	Append	   *node = makeNode(Append);
 	Plan	   *plan = &node->plan;
-	List	   *subnode;
+	ListCell   *subnode;
 
 	/*
 	 * Compute cost as sum of subplan costs.  We charge nothing extra for
@@ -1647,7 +1644,7 @@ make_append(List *appendplans, bool isTarget, List *tlist)
 	{
 		Plan	   *subplan = (Plan *) lfirst(subnode);
 
-		if (subnode == appendplans)		/* first node? */
+		if (subnode == list_head(appendplans))		/* first node? */
 			plan->startup_cost = subplan->startup_cost;
 		plan->total_cost += subplan->total_cost;
 		plan->plan_rows += subplan->plan_rows;
@@ -1837,7 +1834,7 @@ static Sort *
 make_sort_from_pathkeys(Query *root, Plan *lefttree, List *pathkeys)
 {
 	List	   *tlist = lefttree->targetlist;
-	List	   *i;
+	ListCell   *i;
 	int			numsortkeys;
 	AttrNumber *sortColIdx;
 	Oid		   *sortOperators;
@@ -1854,7 +1851,7 @@ make_sort_from_pathkeys(Query *root, Plan *lefttree, List *pathkeys)
 		List	   *keysublist = (List *) lfirst(i);
 		PathKeyItem *pathkey = NULL;
 		Resdom	   *resdom = NULL;
-		List	   *j;
+		ListCell   *j;
 
 		/*
 		 * We can sort by any one of the sort key items listed in this
@@ -1870,7 +1867,7 @@ make_sort_from_pathkeys(Query *root, Plan *lefttree, List *pathkeys)
 		 */
 		foreach(j, keysublist)
 		{
-			pathkey = lfirst(j);
+			pathkey = (PathKeyItem *) lfirst(j);
 			Assert(IsA(pathkey, PathKeyItem));
 			resdom = tlist_member(pathkey->key, tlist);
 			if (resdom)
@@ -1881,10 +1878,10 @@ make_sort_from_pathkeys(Query *root, Plan *lefttree, List *pathkeys)
 			/* No matching Var; look for a computable expression */
 			foreach(j, keysublist)
 			{
-				List   *exprvars;
-				List   *k;
+				List		*exprvars;
+				ListCell	*k;
 
-				pathkey = lfirst(j);
+				pathkey = (PathKeyItem *) lfirst(j);
 				exprvars = pull_var_clause(pathkey->key, false);
 				foreach(k, exprvars)
 				{
@@ -1948,7 +1945,7 @@ Sort *
 make_sort_from_sortclauses(Query *root, List *sortcls, Plan *lefttree)
 {
 	List	   *sub_tlist = lefttree->targetlist;
-	List	   *i;
+	ListCell   *l;
 	int			numsortkeys;
 	AttrNumber *sortColIdx;
 	Oid		   *sortOperators;
@@ -1960,9 +1957,9 @@ make_sort_from_sortclauses(Query *root, List *sortcls, Plan *lefttree)
 
 	numsortkeys = 0;
 
-	foreach(i, sortcls)
+	foreach(l, sortcls)
 	{
-		SortClause *sortcl = (SortClause *) lfirst(i);
+		SortClause *sortcl = (SortClause *) lfirst(l);
 		TargetEntry *tle = get_sortgroupclause_tle(sortcl, sub_tlist);
 
 		/*
@@ -2001,7 +1998,7 @@ make_sort_from_groupcols(Query *root,
 {
 	List	   *sub_tlist = lefttree->targetlist;
 	int			grpno = 0;
-	List	   *i;
+	ListCell   *l;
 	int			numsortkeys;
 	AttrNumber *sortColIdx;
 	Oid		   *sortOperators;
@@ -2013,9 +2010,9 @@ make_sort_from_groupcols(Query *root,
 
 	numsortkeys = 0;
 
-	foreach(i, groupcls)
+	foreach(l, groupcls)
 	{
-		GroupClause *grpcl = (GroupClause *) lfirst(i);
+		GroupClause *grpcl = (GroupClause *) lfirst(l);
 		TargetEntry *tle = get_tle_by_resno(sub_tlist, grpColIdx[grpno]);
 
 		/*
@@ -2213,7 +2210,7 @@ make_unique(Plan *lefttree, List *distinctList)
 	int			numCols = length(distinctList);
 	int			keyno = 0;
 	AttrNumber *uniqColIdx;
-	List	   *slitem;
+	ListCell   *slitem;
 
 	copy_plan_costsize(plan, lefttree);
 
@@ -2270,7 +2267,7 @@ make_setop(SetOpCmd cmd, Plan *lefttree,
 	int			numCols = length(distinctList);
 	int			keyno = 0;
 	AttrNumber *dupColIdx;
-	List	   *slitem;
+	ListCell   *slitem;
 
 	copy_plan_costsize(plan, lefttree);
 
diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c
index 46fde263456..f8a4bfaaac4 100644
--- a/src/backend/optimizer/plan/initsplan.c
+++ b/src/backend/optimizer/plan/initsplan.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/optimizer/plan/initsplan.c,v 1.98 2004/02/27 21:42:00 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/plan/initsplan.c,v 1.99 2004/05/26 04:41:24 neilc Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -81,7 +81,7 @@ add_base_rels_to_query(Query *root, Node *jtnode)
 	else if (IsA(jtnode, FromExpr))
 	{
 		FromExpr   *f = (FromExpr *) jtnode;
-		List	   *l;
+		ListCell   *l;
 
 		foreach(l, f->fromlist)
 			add_base_rels_to_query(root, lfirst(l));
@@ -135,7 +135,7 @@ build_base_rel_tlists(Query *root, List *final_tlist)
 static void
 add_vars_to_targetlist(Query *root, List *vars, Relids where_needed)
 {
-	List	   *temp;
+	ListCell   *temp;
 
 	Assert(!bms_is_empty(where_needed));
 
@@ -205,8 +205,7 @@ distribute_quals_to_rels(Query *root, Node *jtnode)
 	else if (IsA(jtnode, FromExpr))
 	{
 		FromExpr   *f = (FromExpr *) jtnode;
-		List	   *l;
-		List	   *qual;
+		ListCell   *l;
 
 		/*
 		 * First, recurse to handle child joins.
@@ -222,8 +221,8 @@ distribute_quals_to_rels(Query *root, Node *jtnode)
 		 * Now process the top-level quals.  These are always marked as
 		 * "pushed down", since they clearly didn't come from a JOIN expr.
 		 */
-		foreach(qual, (List *) f->quals)
-			distribute_qual_to_rels(root, (Node *) lfirst(qual),
+		foreach(l, (List *) f->quals)
+			distribute_qual_to_rels(root, (Node *) lfirst(l),
 									true, false, NULL, result);
 	}
 	else if (IsA(jtnode, JoinExpr))
@@ -233,7 +232,7 @@ distribute_quals_to_rels(Query *root, Node *jtnode)
 					rightids,
 					nonnullable_rels,
 					nullable_rels;
-		List	   *qual;
+		ListCell   *qual;
 
 		/*
 		 * Order of operations here is subtle and critical.  First we
@@ -636,7 +635,7 @@ process_implied_equality(Query *root,
 	BMS_Membership membership;
 	RelOptInfo *rel1;
 	List	   *restrictlist;
-	List	   *itm;
+	ListCell   *itm;
 	Oid			ltype,
 				rtype;
 	Operator	eq_operator;
@@ -803,7 +802,7 @@ qual_is_redundant(Query *root,
 	Node	   *newleft;
 	Node	   *newright;
 	List	   *oldquals;
-	List	   *olditem;
+	ListCell   *olditem;
 	List	   *equalexprs;
 	bool		someadded;
 
@@ -860,7 +859,7 @@ qual_is_redundant(Query *root,
 	{
 		someadded = false;
 		/* cannot use foreach here because of possible lremove */
-		olditem = oldquals;
+		olditem = list_head(oldquals);
 		while (olditem)
 		{
 			RestrictInfo *oldrinfo = (RestrictInfo *) lfirst(olditem);
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index e094620d620..7b5d44c732b 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/optimizer/plan/planner.c,v 1.169 2004/05/11 02:21:37 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/plan/planner.c,v 1.170 2004/05/26 04:41:24 neilc Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -174,6 +174,7 @@ subquery_planner(Query *parse, double tuple_fraction)
 	Plan	   *plan;
 	List	   *newHaving;
 	List	   *lst;
+	ListCell   *l;
 
 	/* Set up for a new level of subquery */
 	PlannerQueryLevel++;
@@ -206,9 +207,9 @@ subquery_planner(Query *parse, double tuple_fraction)
 	 */
 	parse->hasJoinRTEs = false;
 	hasOuterJoins = false;
-	foreach(lst, parse->rtable)
+	foreach(l, parse->rtable)
 	{
-		RangeTblEntry *rte = (RangeTblEntry *) lfirst(lst);
+		RangeTblEntry *rte = (RangeTblEntry *) lfirst(l);
 
 		if (rte->rtekind == RTE_JOIN)
 		{
@@ -244,9 +245,9 @@ subquery_planner(Query *parse, double tuple_fraction)
 							  EXPRKIND_ININFO);
 
 	/* Also need to preprocess expressions for function RTEs */
-	foreach(lst, parse->rtable)
+	foreach(l, parse->rtable)
 	{
-		RangeTblEntry *rte = (RangeTblEntry *) lfirst(lst);
+		RangeTblEntry *rte = (RangeTblEntry *) lfirst(l);
 
 		if (rte->rtekind == RTE_FUNCTION)
 			rte->funcexpr = preprocess_expression(parse, rte->funcexpr,
@@ -271,9 +272,9 @@ subquery_planner(Query *parse, double tuple_fraction)
 	 * declared as Node *.
 	 */
 	newHaving = NIL;
-	foreach(lst, (List *) parse->havingQual)
+	foreach(l, (List *) parse->havingQual)
 	{
-		Node	   *havingclause = (Node *) lfirst(lst);
+		Node	   *havingclause = (Node *) lfirst(l);
 
 		if (contain_agg_clause(havingclause))
 			newHaving = lappend(newHaving, havingclause);
@@ -337,9 +338,9 @@ subquery_planner(Query *parse, double tuple_fraction)
 		 */
 		plan->initPlan = PlannerInitPlan;
 
-		foreach(lst, plan->initPlan)
+		foreach(l, plan->initPlan)
 		{
-			SubPlan    *initplan = (SubPlan *) lfirst(lst);
+			SubPlan    *initplan = (SubPlan *) lfirst(l);
 
 			plan->extParam = bms_add_members(plan->extParam,
 											 initplan->plan->extParam);
@@ -445,7 +446,7 @@ preprocess_qual_conditions(Query *parse, Node *jtnode)
 	else if (IsA(jtnode, FromExpr))
 	{
 		FromExpr   *f = (FromExpr *) jtnode;
-		List	   *l;
+		ListCell   *l;
 
 		foreach(l, f->fromlist)
 			preprocess_qual_conditions(parse, lfirst(l));
@@ -495,7 +496,7 @@ inheritance_planner(Query *parse, List *inheritlist)
 	int			mainrtlength = length(parse->rtable);
 	List	   *subplans = NIL;
 	List	   *tlist = NIL;
-	List	   *l;
+	ListCell   *l;
 
 	foreach(l, inheritlist)
 	{
@@ -524,10 +525,9 @@ inheritance_planner(Query *parse, List *inheritlist)
 		subrtlength = length(subquery->rtable);
 		if (subrtlength > mainrtlength)
 		{
-			List	   *subrt = subquery->rtable;
+			List	   *subrt;
 
-			while (mainrtlength-- > 0)	/* wish we had nthcdr() */
-				subrt = lnext(subrt);
+			subrt = list_copy_tail(subquery->rtable, mainrtlength);
 			parse->rtable = nconc(parse->rtable, subrt);
 			mainrtlength = subrtlength;
 		}
@@ -650,7 +650,7 @@ grouping_planner(Query *parse, double tuple_fraction)
 		 */
 		if (parse->rowMarks)
 		{
-			List	   *l;
+			ListCell   *l;
 
 			/*
 			 * We've got trouble if the FOR UPDATE appears inside
@@ -1328,7 +1328,7 @@ grouping_planner(Query *parse, double tuple_fraction)
 static bool
 hash_safe_grouping(Query *parse)
 {
-	List	   *gl;
+	ListCell   *gl;
 
 	foreach(gl, parse->groupClause)
 	{
@@ -1435,17 +1435,17 @@ make_subplanTargetList(Query *parse,
 	{
 		int			keyno = 0;
 		AttrNumber *grpColIdx;
-		List	   *gl;
+		ListCell   *gl;
 
 		grpColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
 		*groupColIdx = grpColIdx;
 
 		foreach(gl, parse->groupClause)
 		{
-			GroupClause *grpcl = (GroupClause *) lfirst(gl);
-			Node	   *groupexpr = get_sortgroupclause_expr(grpcl, tlist);
-			TargetEntry *te = NULL;
-			List	   *sl;
+			GroupClause		*grpcl = (GroupClause *) lfirst(gl);
+			Node			*groupexpr = get_sortgroupclause_expr(grpcl, tlist);
+			TargetEntry		*te = NULL;
+			ListCell		*sl;
 
 			/* Find or make a matching sub_tlist entry */
 			foreach(sl, sub_tlist)
@@ -1489,7 +1489,7 @@ locate_grouping_columns(Query *parse,
 						AttrNumber *groupColIdx)
 {
 	int			keyno = 0;
-	List	   *gl;
+	ListCell   *gl;
 
 	/*
 	 * No work unless grouping.
@@ -1503,10 +1503,10 @@ locate_grouping_columns(Query *parse,
 
 	foreach(gl, parse->groupClause)
 	{
-		GroupClause *grpcl = (GroupClause *) lfirst(gl);
-		Node	   *groupexpr = get_sortgroupclause_expr(grpcl, tlist);
-		TargetEntry *te = NULL;
-		List	   *sl;
+		GroupClause		*grpcl = (GroupClause *) lfirst(gl);
+		Node			*groupexpr = get_sortgroupclause_expr(grpcl, tlist);
+		TargetEntry		*te = NULL;
+		ListCell		*sl;
 
 		foreach(sl, sub_tlist)
 		{
@@ -1534,7 +1534,8 @@ locate_grouping_columns(Query *parse,
 static List *
 postprocess_setop_tlist(List *new_tlist, List *orig_tlist)
 {
-	List	   *l;
+	ListCell   *l;
+	ListCell   *orig_tlist_item = list_head(orig_tlist);
 
 	foreach(l, new_tlist)
 	{
@@ -1545,16 +1546,16 @@ postprocess_setop_tlist(List *new_tlist, List *orig_tlist)
 		if (new_tle->resdom->resjunk)
 			continue;
 
-		Assert(orig_tlist != NIL);
-		orig_tle = (TargetEntry *) lfirst(orig_tlist);
-		orig_tlist = lnext(orig_tlist);
+		Assert(orig_tlist_item != NULL);
+		orig_tle = (TargetEntry *) lfirst(orig_tlist_item);
+		orig_tlist_item = lnext(orig_tlist_item);
 		if (orig_tle->resdom->resjunk)	/* should not happen */
 			elog(ERROR, "resjunk output columns are not implemented");
 		Assert(new_tle->resdom->resno == orig_tle->resdom->resno);
 		Assert(new_tle->resdom->restype == orig_tle->resdom->restype);
 		new_tle->resdom->ressortgroupref = orig_tle->resdom->ressortgroupref;
 	}
-	if (orig_tlist != NIL)
+	if (orig_tlist_item != NULL)
 		elog(ERROR, "resjunk output columns are not implemented");
 	return new_tlist;
 }
diff --git a/src/backend/optimizer/plan/setrefs.c b/src/backend/optimizer/plan/setrefs.c
index 84b2aa82805..b8fe70e9350 100644
--- a/src/backend/optimizer/plan/setrefs.c
+++ b/src/backend/optimizer/plan/setrefs.c
@@ -9,7 +9,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/optimizer/plan/setrefs.c,v 1.101 2004/05/11 13:15:15 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/plan/setrefs.c,v 1.102 2004/05/26 04:41:24 neilc Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -84,7 +84,7 @@ static void set_sa_opfuncid(ScalarArrayOpExpr *opexpr);
 void
 set_plan_references(Plan *plan, List *rtable)
 {
-	List	   *pl;
+	ListCell *l;
 
 	if (plan == NULL)
 		return;
@@ -213,15 +213,14 @@ set_plan_references(Plan *plan, List *rtable)
 			fix_expr_references(plan, ((Result *) plan)->resconstantqual);
 			break;
 		case T_Append:
-
 			/*
 			 * Append, like Sort et al, doesn't actually evaluate its
-			 * targetlist or quals, and we haven't bothered to give it its
-			 * own tlist copy.	So, don't fix targetlist/qual. But do
-			 * recurse into child plans.
+			 * targetlist or quals, and we haven't bothered to give it
+			 * its own tlist copy. So, don't fix targetlist/qual. But
+			 * do recurse into child plans.
 			 */
-			foreach(pl, ((Append *) plan)->appendplans)
-				set_plan_references((Plan *) lfirst(pl), rtable);
+			foreach(l, ((Append *) plan)->appendplans)
+				set_plan_references((Plan *) lfirst(l), rtable);
 			break;
 		default:
 			elog(ERROR, "unrecognized node type: %d",
@@ -242,9 +241,9 @@ set_plan_references(Plan *plan, List *rtable)
 	set_plan_references(plan->lefttree, rtable);
 	set_plan_references(plan->righttree, rtable);
 
-	foreach(pl, plan->initPlan)
+	foreach(l, plan->initPlan)
 	{
-		SubPlan    *sp = (SubPlan *) lfirst(pl);
+		SubPlan    *sp = (SubPlan *) lfirst(l);
 
 		Assert(IsA(sp, SubPlan));
 		set_plan_references(sp->plan, sp->rtable);
@@ -440,8 +439,8 @@ set_uppernode_references(Plan *plan, Index subvarno)
 {
 	Plan	   *subplan = plan->lefttree;
 	List	   *subplan_targetlist,
-			   *output_targetlist,
-			   *l;
+			   *output_targetlist;
+	ListCell   *l;
 	bool		tlist_has_non_vars;
 
 	if (subplan != NULL)
@@ -483,7 +482,7 @@ set_uppernode_references(Plan *plan, Index subvarno)
 static bool
 targetlist_has_non_vars(List *tlist)
 {
-	List	   *l;
+	ListCell   *l;
 
 	foreach(l, tlist)
 	{
diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c
index af33da1184e..9245da803e2 100644
--- a/src/backend/optimizer/plan/subselect.c
+++ b/src/backend/optimizer/plan/subselect.c
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1994, Regents of the University of California
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/optimizer/plan/subselect.c,v 1.89 2004/05/11 13:15:15 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/plan/subselect.c,v 1.90 2004/05/26 04:41:24 neilc Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -101,7 +101,7 @@ static Param *
 replace_outer_var(Var *var)
 {
 	Param	   *retval;
-	List	   *ppl;
+	ListCell   *ppl;
 	PlannerParamItem *pitem;
 	Index		abslevel;
 	int			i;
@@ -250,7 +250,6 @@ make_subplan(SubLink *slink, List *lefthand, bool isTopQual)
 	Plan	   *plan;
 	Bitmapset  *tmpset;
 	int			paramid;
-	List	   *lst;
 	Node	   *result;
 
 	/*
@@ -348,7 +347,7 @@ make_subplan(SubLink *slink, List *lefthand, bool isTopQual)
 	}
 	else if (node->parParam == NIL && slink->subLinkType == EXPR_SUBLINK)
 	{
-		TargetEntry *te = lfirst(plan->targetlist);
+		TargetEntry *te = linitial(plan->targetlist);
 		Param	   *prm;
 
 		Assert(!te->resdom->resjunk);
@@ -359,7 +358,7 @@ make_subplan(SubLink *slink, List *lefthand, bool isTopQual)
 	}
 	else if (node->parParam == NIL && slink->subLinkType == ARRAY_SUBLINK)
 	{
-		TargetEntry *te = lfirst(plan->targetlist);
+		TargetEntry *te = linitial(plan->targetlist);
 		Oid			arraytype;
 		Param	   *prm;
 
@@ -395,11 +394,12 @@ make_subplan(SubLink *slink, List *lefthand, bool isTopQual)
 			result = (Node *) (node->useOr ? make_orclause(exprs) :
 							   make_andclause(exprs));
 		else
-			result = (Node *) lfirst(exprs);
+			result = (Node *) linitial(exprs);
 	}
 	else
 	{
 		List	   *args;
+		ListCell   *l;
 
 		/*
 		 * We can't convert subplans of ALL_SUBLINK or ANY_SUBLINK types
@@ -471,9 +471,9 @@ make_subplan(SubLink *slink, List *lefthand, bool isTopQual)
 		 * Make node->args from parParam.
 		 */
 		args = NIL;
-		foreach(lst, node->parParam)
+		foreach(l, node->parParam)
 		{
-			PlannerParamItem *pitem = nth(lfirsti(lst), PlannerParamList);
+			PlannerParamItem *pitem = nth(lfirsti(l), PlannerParamList);
 
 			/*
 			 * The Var or Aggref has already been adjusted to have the
@@ -509,15 +509,17 @@ convert_sublink_opers(List *lefthand, List *operOids,
 					  List **righthandIds)
 {
 	List	   *result = NIL;
-	List	   *lst;
+	ListCell   *l, *lefthand_item, *tlist_item;
 
 	*righthandIds = NIL;
+	lefthand_item = list_head(lefthand);
+	tlist_item = list_head(targetlist);
 
-	foreach(lst, operOids)
+	foreach(l, operOids)
 	{
-		Oid			opid = lfirsto(lst);
-		Node	   *leftop = lfirst(lefthand);
-		TargetEntry *te = lfirst(targetlist);
+		Oid			opid = lfirsto(l);
+		Node	   *leftop = (Node *) lfirst(lefthand_item);
+		TargetEntry *te = (TargetEntry *) lfirst(tlist_item);
 		Node	   *rightop;
 		Operator	tup;
 
@@ -574,8 +576,8 @@ convert_sublink_opers(List *lefthand, List *operOids,
 
 		ReleaseSysCache(tup);
 
-		lefthand = lnext(lefthand);
-		targetlist = lnext(targetlist);
+		lefthand_item = lnext(lefthand_item);
+		tlist_item = lnext(tlist_item);
 	}
 
 	return result;
@@ -591,7 +593,7 @@ static bool
 subplan_is_hashable(SubLink *slink, SubPlan *node)
 {
 	double		subquery_size;
-	List	   *opids;
+	ListCell   *l;
 
 	/*
 	 * The sublink type must be "= ANY" --- that is, an IN operator. (We
@@ -602,7 +604,7 @@ subplan_is_hashable(SubLink *slink, SubPlan *node)
 	if (slink->subLinkType != ANY_SUBLINK)
 		return false;
 	if (length(slink->operName) != 1 ||
-		strcmp(strVal(lfirst(slink->operName)), "=") != 0)
+		strcmp(strVal(linitial(slink->operName)), "=") != 0)
 		return false;
 
 	/*
@@ -636,9 +638,9 @@ subplan_is_hashable(SubLink *slink, SubPlan *node)
 	 * different sets of operators with the hash table, but there is no
 	 * obvious usefulness to that at present.)
 	 */
-	foreach(opids, slink->operOids)
+	foreach(l, slink->operOids)
 	{
-		Oid			opid = lfirsto(opids);
+		Oid			opid = lfirsto(l);
 		HeapTuple	tup;
 		Form_pg_operator optup;
 
@@ -690,7 +692,7 @@ convert_IN_to_join(Query *parse, SubLink *sublink)
 	if (sublink->subLinkType != ANY_SUBLINK)
 		return NULL;
 	if (length(sublink->operName) != 1 ||
-		strcmp(strVal(lfirst(sublink->operName)), "=") != 0)
+		strcmp(strVal(linitial(sublink->operName)), "=") != 0)
 		return NULL;
 
 	/*
@@ -859,8 +861,8 @@ process_sublinks_mutator(Node *node, bool *isTopQual)
 	 */
 	if (and_clause(node))
 	{
-		List   *newargs = NIL;
-		List   *l;
+		List		*newargs = NIL;
+		ListCell	*l;
 
 		/* Still at qual top-level */
 		locTopQual = *isTopQual;
@@ -884,8 +886,8 @@ process_sublinks_mutator(Node *node, bool *isTopQual)
 
 	if (or_clause(node))
 	{
-		List   *newargs = NIL;
-		List   *l;
+		List		*newargs = NIL;
+		ListCell	*l;
 
 		foreach(l, ((BoolExpr *) node)->args)
 		{
@@ -918,7 +920,7 @@ SS_finalize_plan(Plan *plan, List *rtable)
 	Bitmapset  *outer_params = NULL;
 	Bitmapset  *valid_params = NULL;
 	int			paramid;
-	List	   *lst;
+	ListCell   *l;
 
 	/*
 	 * First, scan the param list to discover the sets of params that are
@@ -926,9 +928,9 @@ SS_finalize_plan(Plan *plan, List *rtable)
 	 * this once to save time in the per-plan recursion steps.
 	 */
 	paramid = 0;
-	foreach(lst, PlannerParamList)
+	foreach(l, PlannerParamList)
 	{
-		PlannerParamItem *pitem = (PlannerParamItem *) lfirst(lst);
+		PlannerParamItem *pitem = (PlannerParamItem *) lfirst(l);
 
 		if (pitem->abslevel < PlannerQueryLevel)
 		{
@@ -966,7 +968,6 @@ finalize_plan(Plan *plan, List *rtable,
 			  Bitmapset *outer_params, Bitmapset *valid_params)
 {
 	finalize_primnode_context context;
-	List	   *lst;
 
 	if (plan == NULL)
 		return NULL;
@@ -1033,14 +1034,18 @@ finalize_plan(Plan *plan, List *rtable,
 			break;
 
 		case T_Append:
-			foreach(lst, ((Append *) plan)->appendplans)
 			{
-				context.paramids =
-					bms_add_members(context.paramids,
-									finalize_plan((Plan *) lfirst(lst),
-												  rtable,
-												  outer_params,
-												  valid_params));
+				ListCell *l;
+
+				foreach(l, ((Append *) plan)->appendplans)
+				{
+					context.paramids =
+						bms_add_members(context.paramids,
+										finalize_plan((Plan *) lfirst(l),
+													  rtable,
+													  outer_params,
+													  valid_params));
+				}
 			}
 			break;