Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

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

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit2f5b8eb

Browse files
committed
Clean up some ad-hoc code for sorting and de-duplicating Lists.
heap.c and relcache.c contained nearly identical copies of logicto insert OIDs into an OID list while preserving the list's OIDordering (and rejecting duplicates, in one case but not the other).The comments argue that this is faster than qsort for small numbersof OIDs, which is at best unproven, and seems even less likely to betrue now that lappend_cell_oid has to move data around. In any caseit's ugly and hard-to-follow code, and if we do have a lot of OIDsto consider, it's O(N^2).Hence, replace with simply lappend'ing OIDs to a List, then list_sortthe completed List, then remove adjacent duplicates if necessary.This is demonstrably O(N log N) and it's much simpler for thecallers. It's possible that this would be somewhat inefficientif there were a very large number of duplicates, but that seemsunlikely in the existing usage.This adds list_deduplicate_oid and list_oid_cmp infrastructureto list.c. I didn't bother with equivalent functionality forinteger or pointer Lists, but such could always be added laterif we find a use for it.Discussion:https://postgr.es/m/26193.1563228600@sss.pgh.pa.us
1 parent569ed7f commit2f5b8eb

File tree

4 files changed

+63
-80
lines changed

4 files changed

+63
-80
lines changed

‎src/backend/catalog/heap.c

Lines changed: 6 additions & 43 deletions
Original file line numberDiff line numberDiff line change
@@ -125,7 +125,6 @@ static void SetRelationNumChecks(Relation rel, int numchecks);
125125
staticNode*cookConstraint(ParseState*pstate,
126126
Node*raw_constraint,
127127
char*relname);
128-
staticList*insert_ordered_unique_oid(List*list,Oiddatum);
129128

130129

131130
/* ----------------------------------------------------------------
@@ -3384,55 +3383,19 @@ heap_truncate_find_FKs(List *relationIds)
33843383
if (!list_member_oid(relationIds,con->confrelid))
33853384
continue;
33863385

3387-
/* Add referencer unlessalready in input or result list */
3386+
/* Add referencerto result,unlesspresent in input list */
33883387
if (!list_member_oid(relationIds,con->conrelid))
3389-
result=insert_ordered_unique_oid(result,con->conrelid);
3388+
result=lappend_oid(result,con->conrelid);
33903389
}
33913390

33923391
systable_endscan(fkeyScan);
33933392
table_close(fkeyRel,AccessShareLock);
33943393

3395-
returnresult;
3396-
}
3394+
/* Now sort and de-duplicate the result list */
3395+
list_sort(result,list_oid_cmp);
3396+
list_deduplicate_oid(result);
33973397

3398-
/*
3399-
* insert_ordered_unique_oid
3400-
*Insert a new Oid into a sorted list of Oids, preserving ordering,
3401-
*and eliminating duplicates
3402-
*
3403-
* Building the ordered list this way is O(N^2), but with a pretty small
3404-
* constant, so for the number of entries we expect it will probably be
3405-
* faster than trying to apply qsort(). It seems unlikely someone would be
3406-
* trying to truncate a table with thousands of dependent tables ...
3407-
*/
3408-
staticList*
3409-
insert_ordered_unique_oid(List*list,Oiddatum)
3410-
{
3411-
ListCell*prev;
3412-
3413-
/* Does the datum belong at the front? */
3414-
if (list==NIL||datum<linitial_oid(list))
3415-
returnlcons_oid(datum,list);
3416-
/* Does it match the first entry? */
3417-
if (datum==linitial_oid(list))
3418-
returnlist;/* duplicate, so don't insert */
3419-
/* No, so find the entry it belongs after */
3420-
prev=list_head(list);
3421-
for (;;)
3422-
{
3423-
ListCell*curr=lnext(list,prev);
3424-
3425-
if (curr==NULL||datum<lfirst_oid(curr))
3426-
break;/* it belongs after 'prev', before 'curr' */
3427-
3428-
if (datum==lfirst_oid(curr))
3429-
returnlist;/* duplicate, so don't insert */
3430-
3431-
prev=curr;
3432-
}
3433-
/* Insert datum into list after 'prev' */
3434-
lappend_cell_oid(list,prev,datum);
3435-
returnlist;
3398+
returnresult;
34363399
}
34373400

34383401
/*

‎src/backend/nodes/list.c

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1297,6 +1297,34 @@ list_concat_unique_oid(List *list1, const List *list2)
12971297
returnlist1;
12981298
}
12991299

1300+
/*
1301+
* Remove adjacent duplicates in a list of OIDs.
1302+
*
1303+
* It is caller's responsibility to have sorted the list to bring duplicates
1304+
* together, perhaps via list_sort(list, list_oid_cmp).
1305+
*/
1306+
void
1307+
list_deduplicate_oid(List*list)
1308+
{
1309+
intlen;
1310+
1311+
Assert(IsOidList(list));
1312+
len=list_length(list);
1313+
if (len>1)
1314+
{
1315+
ListCell*elements=list->elements;
1316+
inti=0;
1317+
1318+
for (intj=1;j<len;j++)
1319+
{
1320+
if (elements[i].oid_value!=elements[j].oid_value)
1321+
elements[++i].oid_value=elements[j].oid_value;
1322+
}
1323+
list->length=i+1;
1324+
}
1325+
check_list_invariants(list);
1326+
}
1327+
13001328
/*
13011329
* Free all storage in a list, and optionally the pointed-to elements
13021330
*/
@@ -1444,3 +1472,19 @@ list_sort(List *list, list_sort_comparator cmp)
14441472
if (len>1)
14451473
qsort(list->elements,len,sizeof(ListCell), (qsort_comparator)cmp);
14461474
}
1475+
1476+
/*
1477+
* list_sort comparator for sorting a list into ascending OID order.
1478+
*/
1479+
int
1480+
list_oid_cmp(constListCell*p1,constListCell*p2)
1481+
{
1482+
Oidv1=lfirst_oid(p1);
1483+
Oidv2=lfirst_oid(p2);
1484+
1485+
if (v1<v2)
1486+
return-1;
1487+
if (v1>v2)
1488+
return1;
1489+
return0;
1490+
}

‎src/backend/utils/cache/relcache.c

Lines changed: 9 additions & 37 deletions
Original file line numberDiff line numberDiff line change
@@ -285,7 +285,6 @@ static TupleDesc GetPgIndexDescriptor(void);
285285
staticvoidAttrDefaultFetch(Relationrelation);
286286
staticvoidCheckConstraintFetch(Relationrelation);
287287
staticintCheckConstraintCmp(constvoid*a,constvoid*b);
288-
staticList*insert_ordered_oid(List*list,Oiddatum);
289288
staticvoidInitIndexAmRoutine(Relationrelation);
290289
staticvoidIndexSupportInitialize(oidvector*indclass,
291290
RegProcedure*indexSupport,
@@ -4387,8 +4386,8 @@ RelationGetIndexList(Relation relation)
43874386
if (!index->indislive)
43884387
continue;
43894388

4390-
/*Add index's OID to result list in the proper order */
4391-
result=insert_ordered_oid(result,index->indexrelid);
4389+
/*add index's OID to result list */
4390+
result=lappend_oid(result,index->indexrelid);
43924391

43934392
/*
43944393
* Invalid, non-unique, non-immediate or predicate indexes aren't
@@ -4413,6 +4412,9 @@ RelationGetIndexList(Relation relation)
44134412

44144413
table_close(indrel,AccessShareLock);
44154414

4415+
/* Sort the result list into OID order, per API spec. */
4416+
list_sort(result,list_oid_cmp);
4417+
44164418
/* Now save a copy of the completed list in the relcache entry. */
44174419
oldcxt=MemoryContextSwitchTo(CacheMemoryContext);
44184420
oldlist=relation->rd_indexlist;
@@ -4494,13 +4496,16 @@ RelationGetStatExtList(Relation relation)
44944496
{
44954497
Oidoid= ((Form_pg_statistic_ext)GETSTRUCT(htup))->oid;
44964498

4497-
result=insert_ordered_oid(result,oid);
4499+
result=lappend_oid(result,oid);
44984500
}
44994501

45004502
systable_endscan(indscan);
45014503

45024504
table_close(indrel,AccessShareLock);
45034505

4506+
/* Sort the result list into OID order, per API spec. */
4507+
list_sort(result,list_oid_cmp);
4508+
45044509
/* Now save a copy of the completed list in the relcache entry. */
45054510
oldcxt=MemoryContextSwitchTo(CacheMemoryContext);
45064511
oldlist=relation->rd_statlist;
@@ -4515,39 +4520,6 @@ RelationGetStatExtList(Relation relation)
45154520
returnresult;
45164521
}
45174522

4518-
/*
4519-
* insert_ordered_oid
4520-
*Insert a new Oid into a sorted list of Oids, preserving ordering
4521-
*
4522-
* Building the ordered list this way is O(N^2), but with a pretty small
4523-
* constant, so for the number of entries we expect it will probably be
4524-
* faster than trying to apply qsort(). Most tables don't have very many
4525-
* indexes...
4526-
*/
4527-
staticList*
4528-
insert_ordered_oid(List*list,Oiddatum)
4529-
{
4530-
ListCell*prev;
4531-
4532-
/* Does the datum belong at the front? */
4533-
if (list==NIL||datum<linitial_oid(list))
4534-
returnlcons_oid(datum,list);
4535-
/* No, so find the entry it belongs after */
4536-
prev=list_head(list);
4537-
for (;;)
4538-
{
4539-
ListCell*curr=lnext(list,prev);
4540-
4541-
if (curr==NULL||datum<lfirst_oid(curr))
4542-
break;/* it belongs after 'prev', before 'curr' */
4543-
4544-
prev=curr;
4545-
}
4546-
/* Insert datum into list after 'prev' */
4547-
lappend_cell_oid(list,prev,datum);
4548-
returnlist;
4549-
}
4550-
45514523
/*
45524524
* RelationGetPrimaryKeyIndex -- get OID of the relation's primary key index
45534525
*

‎src/include/nodes/pg_list.h

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -563,6 +563,8 @@ extern List *list_concat_unique_ptr(List *list1, const List *list2);
563563
externList*list_concat_unique_int(List*list1,constList*list2);
564564
externList*list_concat_unique_oid(List*list1,constList*list2);
565565

566+
externvoidlist_deduplicate_oid(List*list);
567+
566568
externvoidlist_free(List*list);
567569
externvoidlist_free_deep(List*list);
568570

@@ -573,4 +575,6 @@ extern List *list_copy_deep(const List *oldlist);
573575
typedefint (*list_sort_comparator) (constListCell*a,constListCell*b);
574576
externvoidlist_sort(List*list,list_sort_comparatorcmp);
575577

578+
externintlist_oid_cmp(constListCell*p1,constListCell*p2);
579+
576580
#endif/* PG_LIST_H */

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp