NotificationsYou must be signed in to change notification settings
Fork28
Star153

Commitd0b4399

Neil Conway

committed

Reimplement the linked list data structure used throughout the backend.

In the past, we used a 'Lispy' linked list implementation: a "list" wasmerely a pointer to the head node of the list. The problem with thatdesign is that it makes lappend() and length() linear time. This patchfixes that problem (and others) by maintaining a count of the listlength 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-dataabout the list; the head and tail pointers in that structure referto 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 arestill available; they will be disabled-by-default once the rest ofthe tree has been updated to use the new API names.

1 parent18d0d10 commitd0b4399Copy full SHA for d0b4399

File tree

125 files changed

+3438

-2837

lines changed

src
- backend
  - access
    - common
      - printtup.c
      - tupdesc.c
    - nbtree
      - nbtxlog.c
  - bootstrap
    - bootparse.y
  - catalog
  - commands
  - executor
  - libpq
    - crypt.c
    - hba.c
  - nodes
  - optimizer
    - geqo
      - geqo_eval.c
    - path
    - plan
    - prep
    - util
  - parser
  - rewrite
  - tcop
  - utils
    - adt
    - cache
    - init
      - miscinit.c
    - misc
      - guc.c
- include
  - nodes
    - nodes.h
    - pg_list.h
  - parser
    - parsetree.h
- pl
  - plpgsql/src
    - pl_exec.c
  - tcl
    - pltcl.c

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

125 files changed

+3438

-2837

lines changed

`‎src/backend/access/common/printtup.c‎`

Lines changed: 9 additions & 8 deletions

Original file line number	Diff line number	Diff line change
`@@ -9,7 +9,7 @@`
`9`	`9`	`* Portions Copyright (c) 1994, Regents of the University of California`
`10`	`10`	`*`
`11`	`11`	`* IDENTIFICATION`
`12`		`- * $PostgreSQL: pgsql/src/backend/access/common/printtup.c,v 1.80 2004/01/07 18:56:23 neilc Exp $`
	`12`	`+ * $PostgreSQL: pgsql/src/backend/access/common/printtup.c,v 1.81 2004/05/26 04:41:03 neilc Exp $`
`13`	`13`	`*`
`14`	`14`	`*-------------------------------------------------------------------------`
`15`	`15`	`*/`
`@@ -138,7 +138,7 @@ printtup_startup(DestReceiver *self, int operation, TupleDesc typeinfo)`
`138`	`138`	`List*targetlist;`
`139`	`139`
`140`	`140`	`if (portal->strategy==PORTAL_ONE_SELECT)`
`141`		`-targetlist= ((Query*)lfirst(portal->parseTrees))->targetList;`
	`141`	`+targetlist= ((Query*)linitial(portal->parseTrees))->targetList;`
`142`	`142`	`else`
`143`	`143`	`targetlist=NIL;`
`144`	`144`
`@@ -176,6 +176,7 @@ SendRowDescriptionMessage(TupleDesc typeinfo, List targetlist, int16 formats)`
`176`	`176`	`intproto=PG_PROTOCOL_MAJOR(FrontendProtocol);`
`177`	`177`	`inti;`
`178`	`178`	`StringInfoDatabuf;`
	`179`	`+ListCell*tlist_item=list_head(targetlist);`
`179`	`180`
`180`	`181`	`pq_beginmessage(&buf,'T');/* tuple descriptor message type */`
`181`	`182`	`pq_sendint(&buf,natts,2);/* # of attrs in tuples */`
`@@ -191,16 +192,16 @@ SendRowDescriptionMessage(TupleDesc typeinfo, List targetlist, int16 formats)`
`191`	`192`	`if (proto >=3)`
`192`	`193`	`{`
`193`	`194`	`/* Do we have a non-resjunk tlist item? */`
`194`		`-while (targetlist&&`
`195`		`- ((TargetEntry*)lfirst(targetlist))->resdom->resjunk)`
`196`		`-targetlist=lnext(targetlist);`
`197`		`-if (targetlist)`
	`195`	`+while (tlist_item&&`
	`196`	`+ ((TargetEntry*)lfirst(tlist_item))->resdom->resjunk)`
	`197`	`+tlist_item=lnext(tlist_item);`
	`198`	`+if (tlist_item)`
`198`	`199`	`{`
`199`		`-Resdomres= ((TargetEntry)lfirst(targetlist))->resdom;`
	`200`	`+Resdomres= ((TargetEntry)lfirst(tlist_item))->resdom;`
`200`	`201`
`201`	`202`	`pq_sendint(&buf,res->resorigtbl,4);`
`202`	`203`	`pq_sendint(&buf,res->resorigcol,2);`
`203`		`-targetlist=lnext(targetlist);`
	`204`	`+tlist_item=lnext(tlist_item);`
`204`	`205`	`}`
`205`	`206`	`else`
`206`	`207`	`{`

`‎src/backend/access/common/tupdesc.c‎`

Lines changed: 5 additions & 5 deletions

Original file line number	Diff line number	Diff line change
`@@ -8,7 +8,7 @@`
`8`	`8`	`*`
`9`	`9`	`*`
`10`	`10`	`* IDENTIFICATION`
`11`		`- * $PostgreSQL: pgsql/src/backend/access/common/tupdesc.c,v 1.102 2004/04/01 21:28:43 tgl Exp $`
	`11`	`+ * $PostgreSQL: pgsql/src/backend/access/common/tupdesc.c,v 1.103 2004/05/26 04:41:03 neilc Exp $`
`12`	`12`	`*`
`13`	`13`	`* NOTES`
`14`	`14`	`* some of the executor utility code such as "ExecTypeFromTL" should be`
`@@ -472,7 +472,7 @@ BuildDescForRelation(List *schema)`
`472`	`472`	`{`
`473`	`473`	`intnatts;`
`474`	`474`	`AttrNumberattnum;`
`475`		`-List*p;`
	`475`	`+ListCell*l;`
`476`	`476`	`TupleDescdesc;`
`477`	`477`	`AttrDefault*attrdef=NULL;`
`478`	`478`	`TupleConstrconstr= (TupleConstr)palloc0(sizeof(TupleConstr));`
`@@ -490,9 +490,9 @@ BuildDescForRelation(List *schema)`
`490`	`490`
`491`	`491`	`attnum=0;`
`492`	`492`
`493`		`-foreach(p,schema)`
	`493`	`+foreach(l,schema)`
`494`	`494`	`{`
`495`		`-ColumnDef*entry=lfirst(p);`
	`495`	`+ColumnDef*entry=lfirst(l);`
`496`	`496`
`497`	`497`	`/*`
`498`	`498`	`* for each entry in the list, get the name and type information`
`@@ -661,7 +661,7 @@ TypeGetTupleDesc(Oid typeoid, List *colaliases)`
`661`	`661`	`errmsg("number of aliases does not match number of columns")));`
`662`	`662`
`663`	`663`	`/* OK, get the column alias */`
`664`		`-attname=strVal(lfirst(colaliases));`
	`664`	`+attname=strVal(linitial(colaliases));`
`665`	`665`
`666`	`666`	`tupdesc=CreateTemplateTupleDesc(1, false);`
`667`	`667`	`TupleDescInitEntry(tupdesc,`

`‎src/backend/access/nbtree/nbtxlog.c‎`

Lines changed: 3 additions & 3 deletions

Original file line number	Diff line number	Diff line change
`@@ -8,7 +8,7 @@`
`8`	`8`	`* Portions Copyright (c) 1994, Regents of the University of California`
`9`	`9`	`*`
`10`	`10`	`* IDENTIFICATION`
`11`		`- * $PostgreSQL: pgsql/src/backend/access/nbtree/nbtxlog.c,v 1.10 2004/01/07 18:56:24 neilc Exp $`
	`11`	`+ * $PostgreSQL: pgsql/src/backend/access/nbtree/nbtxlog.c,v 1.11 2004/05/26 04:41:05 neilc Exp $`
`12`	`12`	`*`
`13`	`13`	`*-------------------------------------------------------------------------`
`14`	`14`	`*/`
`@@ -59,7 +59,7 @@ forget_matching_split(Relation reln, RelFileNode node,`
`59`	`59`	`Pagepage;`
`60`	`60`	`BTItembtitem;`
`61`	`61`	`BlockNumberrightblk;`
`62`		`-List*l;`
	`62`	`+ListCell*l;`
`63`	`63`
`64`	`64`	`/* Get downlink TID from page */`
`65`	`65`	`buffer=XLogReadBuffer(false,reln,insertblk);`
`@@ -964,7 +964,7 @@ btree_xlog_startup(void)`
`964`	`964`	`void`
`965`	`965`	`btree_xlog_cleanup(void)`
`966`	`966`	`{`
`967`		`-List*l;`
	`967`	`+ListCell*l;`
`968`	`968`
`969`	`969`	`foreach(l,incomplete_splits)`
`970`	`970`	`{`

`‎src/backend/bootstrap/bootparse.y‎`

Lines changed: 3 additions & 3 deletions

Original file line number	Diff line number	Diff line change
`@@ -9,7 +9,7 @@`
`9`	`9`	`*`
`10`	`10`	`*`
`11`	`11`	`* IDENTIFICATION`
`12`		`- * $PostgreSQL: pgsql/src/backend/bootstrap/bootparse.y,v 1.67 2004/05/21 05:07:56 tgl Exp $`
	`12`	`+ * $PostgreSQL: pgsql/src/backend/bootstrap/bootparse.y,v 1.68 2004/05/26 04:41:05 neilc Exp $`
`13`	`13`	`*`
`14`	`14`	`*-------------------------------------------------------------------------`
`15`	`15`	`*/`
`@@ -271,7 +271,7 @@ Boot_BuildIndsStmt:`
`271`	`271`
`272`	`272`	`boot_index_params:`
`273`	`273`	`boot_index_params COMMA boot_index_param{ $$ =lappend($1, $3); }`
`274`		`-\| boot_index_param{ $$ =makeList1($1); }`
	`274`	`+\| boot_index_param{ $$ =list_make1($1); }`
`275`	`275`	`;`
`276`	`276`
`277`	`277`	`boot_index_param:`
`@@ -280,7 +280,7 @@ boot_index_param:`
`280`	`280`	`IndexElem *n =makeNode(IndexElem);`
`281`	`281`	`n->name =LexIDStr($1);`
`282`	`282`	`n->expr =NULL;`
`283`		`-n->opclass =makeList1(makeString(LexIDStr($2)));`
	`283`	`+n->opclass =list_make1(makeString(LexIDStr($2)));`
`284`	`284`	`$$ = n;`
`285`	`285`	`}`
`286`	`286`	`;`

`‎src/backend/catalog/aclchk.c‎`

Lines changed: 17 additions & 17 deletions

Original file line number	Diff line number	Diff line change
`@@ -8,7 +8,7 @@`
`8`	`8`	`*`
`9`	`9`	`*`
`10`	`10`	`* IDENTIFICATION`
`11`		`- * $PostgreSQL: pgsql/src/backend/catalog/aclchk.c,v 1.98 2004/05/11 17:36:12 tgl Exp $`
	`11`	`+ * $PostgreSQL: pgsql/src/backend/catalog/aclchk.c,v 1.99 2004/05/26 04:41:06 neilc Exp $`
`12`	`12`	`*`
`13`	`13`	`* NOTES`
`14`	`14`	`* See acl.h.`
`@@ -110,7 +110,7 @@ merge_acl_with_grant(Acl *old_acl, bool is_grant,`
`110`	`110`	`AclIdgrantor_uid,AclIdowner_uid)`
`111`	`111`	`{`
`112`	`112`	`unsignedmodechg;`
`113`		`-List*j;`
	`113`	`+ListCell*j;`
`114`	`114`	`Acl*new_acl;`
`115`	`115`
`116`	`116`	`modechg=is_grant ?ACL_MODECHG_ADD :ACL_MODECHG_DEL;`
`@@ -221,16 +221,16 @@ static void`
`221`	`221`	`ExecuteGrantStmt_Relation(GrantStmt*stmt)`
`222`	`222`	`{`
`223`	`223`	`AclModeprivileges;`
`224`		`-List*i;`
	`224`	`+ListCell*i;`
`225`	`225`
`226`		`-if (lfirsti(stmt->privileges)==ACL_ALL_RIGHTS)`
	`226`	`+if (linitial_int(stmt->privileges)==ACL_ALL_RIGHTS)`
`227`	`227`	`privileges=ACL_ALL_RIGHTS_RELATION;`
`228`	`228`	`else`
`229`	`229`	`{`
`230`	`230`	`privileges=ACL_NO_RIGHTS;`
`231`	`231`	`foreach(i,stmt->privileges)`
`232`	`232`	`{`
`233`		`-AclModepriv=lfirsti(i);`
	`233`	`+AclModepriv=lfirst_int(i);`
`234`	`234`
`235`	`235`	`if (priv& ~((AclMode)ACL_ALL_RIGHTS_RELATION))`
`236`	`236`	`ereport(ERROR,`
`@@ -328,16 +328,16 @@ static void`
`328`	`328`	`ExecuteGrantStmt_Database(GrantStmt*stmt)`
`329`	`329`	`{`
`330`	`330`	`AclModeprivileges;`
`331`		`-List*i;`
	`331`	`+ListCell*i;`
`332`	`332`
`333`		`-if (lfirsti(stmt->privileges)==ACL_ALL_RIGHTS)`
	`333`	`+if (linitial_int(stmt->privileges)==ACL_ALL_RIGHTS)`
`334`	`334`	`privileges=ACL_ALL_RIGHTS_DATABASE;`
`335`	`335`	`else`
`336`	`336`	`{`
`337`	`337`	`privileges=ACL_NO_RIGHTS;`
`338`	`338`	`foreach(i,stmt->privileges)`
`339`	`339`	`{`
`340`		`-AclModepriv=lfirsti(i);`
	`340`	`+AclModepriv=lfirst_int(i);`
`341`	`341`
`342`	`342`	`if (priv& ~((AclMode)ACL_ALL_RIGHTS_DATABASE))`
`343`	`343`	`ereport(ERROR,`
`@@ -433,16 +433,16 @@ static void`
`433`	`433`	`ExecuteGrantStmt_Function(GrantStmt*stmt)`
`434`	`434`	`{`
`435`	`435`	`AclModeprivileges;`
`436`		`-List*i;`
	`436`	`+ListCell*i;`
`437`	`437`
`438`		`-if (lfirsti(stmt->privileges)==ACL_ALL_RIGHTS)`
	`438`	`+if (linitial_int(stmt->privileges)==ACL_ALL_RIGHTS)`
`439`	`439`	`privileges=ACL_ALL_RIGHTS_FUNCTION;`
`440`	`440`	`else`
`441`	`441`	`{`
`442`	`442`	`privileges=ACL_NO_RIGHTS;`
`443`	`443`	`foreach(i,stmt->privileges)`
`444`	`444`	`{`
`445`		`-AclModepriv=lfirsti(i);`
	`445`	`+AclModepriv=lfirst_int(i);`
`446`	`446`
`447`	`447`	`if (priv& ~((AclMode)ACL_ALL_RIGHTS_FUNCTION))`
`448`	`448`	`ereport(ERROR,`
`@@ -534,16 +534,16 @@ static void`
`534`	`534`	`ExecuteGrantStmt_Language(GrantStmt*stmt)`
`535`	`535`	`{`
`536`	`536`	`AclModeprivileges;`
`537`		`-List*i;`
	`537`	`+ListCell*i;`
`538`	`538`
`539`		`-if (lfirsti(stmt->privileges)==ACL_ALL_RIGHTS)`
	`539`	`+if (linitial_int(stmt->privileges)==ACL_ALL_RIGHTS)`
`540`	`540`	`privileges=ACL_ALL_RIGHTS_LANGUAGE;`
`541`	`541`	`else`
`542`	`542`	`{`
`543`	`543`	`privileges=ACL_NO_RIGHTS;`
`544`	`544`	`foreach(i,stmt->privileges)`
`545`	`545`	`{`
`546`		`-AclModepriv=lfirsti(i);`
	`546`	`+AclModepriv=lfirst_int(i);`
`547`	`547`
`548`	`548`	`if (priv& ~((AclMode)ACL_ALL_RIGHTS_LANGUAGE))`
`549`	`549`	`ereport(ERROR,`
`@@ -643,16 +643,16 @@ static void`
`643`	`643`	`ExecuteGrantStmt_Namespace(GrantStmt*stmt)`
`644`	`644`	`{`
`645`	`645`	`AclModeprivileges;`
`646`		`-List*i;`
	`646`	`+ListCell*i;`
`647`	`647`
`648`		`-if (lfirsti(stmt->privileges)==ACL_ALL_RIGHTS)`
	`648`	`+if (linitial_int(stmt->privileges)==ACL_ALL_RIGHTS)`
`649`	`649`	`privileges=ACL_ALL_RIGHTS_NAMESPACE;`
`650`	`650`	`else`
`651`	`651`	`{`
`652`	`652`	`privileges=ACL_NO_RIGHTS;`
`653`	`653`	`foreach(i,stmt->privileges)`
`654`	`654`	`{`
`655`		`-AclModepriv=lfirsti(i);`
	`655`	`+AclModepriv=lfirst_int(i);`
`656`	`656`
`657`	`657`	`if (priv& ~((AclMode)ACL_ALL_RIGHTS_NAMESPACE))`
`658`	`658`	`ereport(ERROR,`

`‎src/backend/catalog/dependency.c‎`

Lines changed: 17 additions & 25 deletions

Original file line number	Diff line number	Diff line change
`@@ -8,7 +8,7 @@`
`8`	`8`	`* Portions Copyright (c) 1994, Regents of the University of California`
`9`	`9`	`*`
`10`	`10`	`* IDENTIFICATION`
`11`		`- * $PostgreSQL: pgsql/src/backend/catalog/dependency.c,v 1.35 2004/05/05 04:48:45 tgl Exp $`
	`11`	`+ * $PostgreSQL: pgsql/src/backend/catalog/dependency.c,v 1.36 2004/05/26 04:41:06 neilc Exp $`
`12`	`12`	`*`
`13`	`13`	`*-------------------------------------------------------------------------`
`14`	`14`	`*/`
`@@ -841,7 +841,7 @@ recordDependencyOnExpr(const ObjectAddress *depender,`
`841`	`841`	`init_object_addresses(&context.addrs);`
`842`	`842`
`843`	`843`	`/* Set up interpretation for Vars at varlevelsup = 0 */`
`844`		`-context.rtables=makeList1(rtable);`
	`844`	`+context.rtables=list_make1(rtable);`
`845`	`845`
`846`	`846`	`/* Scan the expression tree for referenceable objects */`
`847`	`847`	`find_expr_references_walker(expr,&context);`
`@@ -883,7 +883,7 @@ recordDependencyOnSingleRelExpr(const ObjectAddress *depender,`
`883`	`883`	`rte.rtekind=RTE_RELATION;`
`884`	`884`	`rte.relid=relId;`
`885`	`885`
`886`		`-context.rtables=makeList1(makeList1(&rte));`
	`886`	`+context.rtables=list_make1(list_make1(&rte));`
`887`	`887`
`888`	`888`	`/* Scan the expression tree for referenceable objects */`
`889`	`889`	`find_expr_references_walker(expr,&context);`
`@@ -960,24 +960,14 @@ find_expr_references_walker(Node *node,`
`960`	`960`	`if (IsA(node,Var))`
`961`	`961`	`{`
`962`	`962`	`Varvar= (Var)node;`
`963`		`-intlevelsup;`
`964`		`-List*rtable,`
`965`		`-*rtables;`
	`963`	`+List*rtable;`
`966`	`964`	`RangeTblEntry*rte;`
`967`	`965`
`968`	`966`	`/* Find matching rtable entry, or complain if not found */`
`969`		`-levelsup=var->varlevelsup;`
`970`		`-rtables=context->rtables;`
`971`		`-while (levelsup--)`
`972`		`-{`
`973`		`-if (rtables==NIL)`
`974`		`-break;`
`975`		`-rtables=lnext(rtables);`
`976`		`-}`
`977`		`-if (rtables==NIL)`
	`967`	`+if (var->varlevelsup >=list_length(context->rtables))`
`978`	`968`	`elog(ERROR,"invalid varlevelsup %d",var->varlevelsup);`
`979`		`-rtable=lfirst(rtables);`
`980`		`-if (var->varno <=0\|\|var->varno>length(rtable))`
	`969`	`+rtable=(List*)list_nth(context->rtables,var->varlevelsup);`
	`970`	`+if (var->varno <=0\|\|var->varno>list_length(rtable))`
`981`	`971`	`elog(ERROR,"invalid varno %d",var->varno);`
`982`	`972`	`rte=rt_fetch(var->varno,rtable);`
`983`	`973`	`if (rte->rtekind==RTE_RELATION)`
`@@ -994,13 +984,15 @@ find_expr_references_walker(Node *node,`
`994`	`984`
`995`	`985`	`/* We must make the context appropriate for join's level */`
`996`	`986`	`save_rtables=context->rtables;`
`997`		`-context->rtables=rtables;`
	`987`	`+context->rtables=list_copy_tail(context->rtables,`
	`988`	`+var->varlevelsup);`
`998`	`989`	`if (var->varattno <=0\|\|`
`999`		`-var->varattno>length(rte->joinaliasvars))`
	`990`	`+var->varattno>list_length(rte->joinaliasvars))`
`1000`	`991`	`elog(ERROR,"invalid varattno %d",var->varattno);`
`1001`		`-find_expr_references_walker((Node*)nth(var->varattno-1,`
`1002`		`-rte->joinaliasvars),`
	`992`	`+find_expr_references_walker((Node*)list_nth(rte->joinaliasvars,`
	`993`	`+var->varattno-1),`
`1003`	`994`	`context);`
	`995`	`+list_free(context->rtables);`
`1004`	`996`	`context->rtables=save_rtables;`
`1005`	`997`	`}`
`1006`	`998`	`return false;`
`@@ -1056,11 +1048,11 @@ find_expr_references_walker(Node *node,`
`1056`	`1048`	`if (IsA(node,SubLink))`
`1057`	`1049`	`{`
`1058`	`1050`	`SubLinksublink= (SubLink)node;`
`1059`		`-List*opid;`
	`1051`	`+ListCell*opid;`
`1060`	`1052`
`1061`	`1053`	`foreach(opid,sublink->operOids)`
`1062`	`1054`	`{`
`1063`		`-add_object_address(OCLASS_OPERATOR,lfirsto(opid),0,`
	`1055`	`+add_object_address(OCLASS_OPERATOR,lfirst_oid(opid),0,`
`1064`	`1056`	`&context->addrs);`
`1065`	`1057`	`}`
`1066`	`1058`	`/* fall through to examine arguments */`
`@@ -1074,7 +1066,7 @@ find_expr_references_walker(Node *node,`
`1074`	`1066`	`{`
`1075`	`1067`	`/* Recurse into RTE subquery or not-yet-planned sublink subquery */`
`1076`	`1068`	`Queryquery= (Query)node;`
`1077`		`-List*rtable;`
	`1069`	`+ListCell*rtable;`
`1078`	`1070`	`boolresult;`
`1079`	`1071`
`1080`	`1072`	`/*`
`@@ -1099,7 +1091,7 @@ find_expr_references_walker(Node *node,`
`1099`	`1091`	`find_expr_references_walker,`
`1100`	`1092`	`(void*)context,`
`1101`	`1093`	`QTW_IGNORE_JOINALIASES);`
`1102`		`-context->rtables=lnext(context->rtables);`
	`1094`	`+context->rtables=list_delete_first(context->rtables);`
`1103`	`1095`	`returnresult;`
`1104`	`1096`	`}`
`1105`	`1097`	`returnexpression_tree_walker(node,find_expr_references_walker,`

0 commit comments

Comments

(0)

Movatterモバイル変換

Navigation Menu

Search code, repositories, users, issues, pull requests...

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Commitd0b4399

File tree

125 files changed

Some content is hidden

125 files changed

`‎src/backend/access/common/printtup.c‎`

`‎src/backend/access/common/tupdesc.c‎`

`‎src/backend/access/nbtree/nbtxlog.c‎`

`‎src/backend/bootstrap/bootparse.y‎`

`‎src/backend/catalog/aclchk.c‎`

`‎src/backend/catalog/dependency.c‎`

0 commit comments