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

Commit569ed7f

Browse files
committed
Redesign the API for list sorting (list_qsort becomes list_sort).
In the wake of commit1cff1b9, the obvious way to sort a Listis to apply qsort() directly to the array of ListCells. list_qsortwas building an intermediate array of pointers-to-ListCells, whichwe no longer need, but getting rid of it forces an API change:the comparator functions need to do one less level of indirection.Since we're having to touch the callers anyway, let's do two additionalchanges: sort the given list in-place rather than making a copy (asnone of the existing callers have any use for the copying behavior),and rename list_qsort to list_sort. It was argued that the old nameexposes more about the implementation than it should, which I findpretty questionable, but a better reason to rename it is to be surewe get the attention of any external callers about the need to fixtheir comparator functions.While we're at it, change four existing callers of qsort() to uselist_sort instead; previously, they all had local reinventionsof list_qsort, ie build-an-array-from-a-List-and-qsort-it.(There are some other places where changing to list_sort perhapswould be worthwhile, but they're less obviously wins.)Discussion:https://postgr.es/m/29361.1563220190@sss.pgh.pa.us
1 parent0896ae5 commit569ed7f

File tree

7 files changed

+82
-157
lines changed

7 files changed

+82
-157
lines changed

‎src/backend/nodes/list.c

Lines changed: 18 additions & 35 deletions
Original file line numberDiff line numberDiff line change
@@ -1419,45 +1419,28 @@ list_copy_deep(const List *oldlist)
14191419
}
14201420

14211421
/*
1422-
* Sort a listas though by qsort.
1422+
* Sort a listaccording to the specified comparator function.
14231423
*
1424-
* A new list is built and returned. Like list_copy, this doesn't make
1425-
* fresh copies of any pointed-to data.
1424+
* The list is sorted in-place.
14261425
*
1427-
* The comparator function receives arguments of type ListCell **.
1428-
* (XXX that's really inefficient now, but changing it seems like
1429-
* material for a standalone patch.)
1426+
* The comparator function is declared to receive arguments of type
1427+
* const ListCell *; this allows it to use lfirst() and variants
1428+
* without casting its arguments. Otherwise it behaves the same as
1429+
* the comparator function for standard qsort().
1430+
*
1431+
* Like qsort(), this provides no guarantees about sort stability
1432+
* for equal keys.
14301433
*/
1431-
List*
1432-
list_qsort(constList*list,list_qsort_comparatorcmp)
1434+
void
1435+
list_sort(List*list,list_sort_comparatorcmp)
14331436
{
1434-
intlen=list_length(list);
1435-
ListCell**list_arr;
1436-
List*newlist;
1437-
ListCell*cell;
1438-
inti;
1439-
1440-
/* Empty list is easy */
1441-
if (len==0)
1442-
returnNIL;
1437+
typedefint (*qsort_comparator) (constvoid*a,constvoid*b);
1438+
intlen;
14431439

1444-
/* We have to make an array of pointers to satisfy the API */
1445-
list_arr= (ListCell**)palloc(sizeof(ListCell*)*len);
1446-
i=0;
1447-
foreach(cell,list)
1448-
list_arr[i++]=cell;
1449-
1450-
qsort(list_arr,len,sizeof(ListCell*),cmp);
1451-
1452-
/* Construct new list (this code is much like list_copy) */
1453-
newlist=new_list(list->type,len);
1454-
1455-
for (i=0;i<len;i++)
1456-
newlist->elements[i]=*list_arr[i];
1457-
1458-
/* Might as well free the workspace array */
1459-
pfree(list_arr);
1440+
check_list_invariants(list);
14601441

1461-
check_list_invariants(newlist);
1462-
returnnewlist;
1442+
/* Nothing to do if there's less than two elements */
1443+
len=list_length(list);
1444+
if (len>1)
1445+
qsort(list->elements,len,sizeof(ListCell), (qsort_comparator)cmp);
14631446
}

‎src/backend/optimizer/util/pathnode.c

Lines changed: 16 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -52,8 +52,8 @@ typedef enum
5252
#defineSTD_FUZZ_FACTOR 1.01
5353

5454
staticList*translate_sub_tlist(List*tlist,intrelid);
55-
staticintappend_total_cost_compare(constvoid*a,constvoid*b);
56-
staticintappend_startup_cost_compare(constvoid*a,constvoid*b);
55+
staticintappend_total_cost_compare(constListCell*a,constListCell*b);
56+
staticintappend_startup_cost_compare(constListCell*a,constListCell*b);
5757
staticList*reparameterize_pathlist_by_child(PlannerInfo*root,
5858
List*pathlist,
5959
RelOptInfo*child_rel);
@@ -1239,9 +1239,8 @@ create_append_path(PlannerInfo *root,
12391239
*/
12401240
Assert(pathkeys==NIL);
12411241

1242-
subpaths=list_qsort(subpaths,append_total_cost_compare);
1243-
partial_subpaths=list_qsort(partial_subpaths,
1244-
append_startup_cost_compare);
1242+
list_sort(subpaths,append_total_cost_compare);
1243+
list_sort(partial_subpaths,append_startup_cost_compare);
12451244
}
12461245
pathnode->first_partial_path=list_length(subpaths);
12471246
pathnode->subpaths=list_concat(subpaths,partial_subpaths);
@@ -1296,17 +1295,18 @@ create_append_path(PlannerInfo *root,
12961295

12971296
/*
12981297
* append_total_cost_compare
1299-
* qsort comparator for sorting append child paths by total_cost descending
1298+
* list_sort comparator for sorting append child paths
1299+
* by total_cost descending
13001300
*
13011301
* For equal total costs, we fall back to comparing startup costs; if those
13021302
* are equal too, break ties using bms_compare on the paths' relids.
1303-
* (This is to avoid getting unpredictable results fromqsort.)
1303+
* (This is to avoid getting unpredictable results fromlist_sort.)
13041304
*/
13051305
staticint
1306-
append_total_cost_compare(constvoid*a,constvoid*b)
1306+
append_total_cost_compare(constListCell*a,constListCell*b)
13071307
{
1308-
Path*path1= (Path*)lfirst(*(ListCell**)a);
1309-
Path*path2= (Path*)lfirst(*(ListCell**)b);
1308+
Path*path1= (Path*)lfirst(a);
1309+
Path*path2= (Path*)lfirst(b);
13101310
intcmp;
13111311

13121312
cmp=compare_path_costs(path1,path2,TOTAL_COST);
@@ -1317,17 +1317,18 @@ append_total_cost_compare(const void *a, const void *b)
13171317

13181318
/*
13191319
* append_startup_cost_compare
1320-
* qsort comparator for sorting append child paths by startup_cost descending
1320+
* list_sort comparator for sorting append child paths
1321+
* by startup_cost descending
13211322
*
13221323
* For equal startup costs, we fall back to comparing total costs; if those
13231324
* are equal too, break ties using bms_compare on the paths' relids.
1324-
* (This is to avoid getting unpredictable results fromqsort.)
1325+
* (This is to avoid getting unpredictable results fromlist_sort.)
13251326
*/
13261327
staticint
1327-
append_startup_cost_compare(constvoid*a,constvoid*b)
1328+
append_startup_cost_compare(constListCell*a,constListCell*b)
13281329
{
1329-
Path*path1= (Path*)lfirst(*(ListCell**)a);
1330-
Path*path2= (Path*)lfirst(*(ListCell**)b);
1330+
Path*path1= (Path*)lfirst(a);
1331+
Path*path2= (Path*)lfirst(b);
13311332
intcmp;
13321333

13331334
cmp=compare_path_costs(path1,path2,STARTUP_COST);

‎src/backend/parser/parse_agg.c

Lines changed: 6 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -1722,11 +1722,12 @@ expand_groupingset_node(GroupingSet *gs)
17221722
returnresult;
17231723
}
17241724

1725+
/* list_sort comparator to sort sub-lists by length */
17251726
staticint
1726-
cmp_list_len_asc(constvoid*a,constvoid*b)
1727+
cmp_list_len_asc(constListCell*a,constListCell*b)
17271728
{
1728-
intla=list_length(*(List*const*)a);
1729-
intlb=list_length(*(List*const*)b);
1729+
intla=list_length((constList*)lfirst(a));
1730+
intlb=list_length((constList*)lfirst(b));
17301731

17311732
return (la>lb) ?1 : (la==lb) ?0 :-1;
17321733
}
@@ -1797,27 +1798,8 @@ expand_grouping_sets(List *groupingSets, int limit)
17971798
result=new_result;
17981799
}
17991800

1800-
if (list_length(result)>1)
1801-
{
1802-
intresult_len=list_length(result);
1803-
List**buf=palloc(sizeof(List*)*result_len);
1804-
List**ptr=buf;
1805-
1806-
foreach(lc,result)
1807-
{
1808-
*ptr++=lfirst(lc);
1809-
}
1810-
1811-
qsort(buf,result_len,sizeof(List*),cmp_list_len_asc);
1812-
1813-
result=NIL;
1814-
ptr=buf;
1815-
1816-
while (result_len-->0)
1817-
result=lappend(result,*ptr++);
1818-
1819-
pfree(buf);
1820-
}
1801+
/* Now sort the lists by length */
1802+
list_sort(result,cmp_list_len_asc);
18211803

18221804
returnresult;
18231805
}

‎src/backend/replication/basebackup.c

Lines changed: 22 additions & 29 deletions
Original file line numberDiff line numberDiff line change
@@ -70,7 +70,7 @@ static void base_backup_cleanup(int code, Datum arg);
7070
staticvoidperform_base_backup(basebackup_options*opt);
7171
staticvoidparse_basebackup_options(List*options,basebackup_options*opt);
7272
staticvoidSendXlogRecPtrResult(XLogRecPtrptr,TimeLineIDtli);
73-
staticintcompareWalFileNames(constvoid*a,constvoid*b);
73+
staticintcompareWalFileNames(constListCell*a,constListCell*b);
7474
staticvoidthrottle(size_tincrement);
7575
staticboolis_checksummed_file(constchar*fullpath,constchar*filename);
7676

@@ -379,13 +379,10 @@ perform_base_backup(basebackup_options *opt)
379379
structstatstatbuf;
380380
List*historyFileList=NIL;
381381
List*walFileList=NIL;
382-
char**walFiles;
383-
intnWalFiles;
384382
charfirstoff[MAXFNAMELEN];
385383
charlastoff[MAXFNAMELEN];
386384
DIR*dir;
387385
structdirent*de;
388-
inti;
389386
ListCell*lc;
390387
TimeLineIDtli;
391388

@@ -428,32 +425,26 @@ perform_base_backup(basebackup_options *opt)
428425
CheckXLogRemoved(startsegno,ThisTimeLineID);
429426

430427
/*
431-
*Put the WAL filenames into an array, and sort. Wesend the files in
432-
*order fromoldest to newest, to reduce the chance that a file is
433-
*recycledbefore we get a chance to send it over.
428+
*Sort the WAL filenames. We want tosend the files in order from
429+
* oldest to newest, to reduce the chance that a file is recycled
430+
* before we get a chance to send it over.
434431
*/
435-
nWalFiles=list_length(walFileList);
436-
walFiles=palloc(nWalFiles*sizeof(char*));
437-
i=0;
438-
foreach(lc,walFileList)
439-
{
440-
walFiles[i++]=lfirst(lc);
441-
}
442-
qsort(walFiles,nWalFiles,sizeof(char*),compareWalFileNames);
432+
list_sort(walFileList,compareWalFileNames);
443433

444434
/*
445435
* There must be at least one xlog file in the pg_wal directory, since
446436
* we are doing backup-including-xlog.
447437
*/
448-
if (nWalFiles<1)
438+
if (walFileList==NIL)
449439
ereport(ERROR,
450440
(errmsg("could not find any WAL files")));
451441

452442
/*
453443
* Sanity check: the first and last segment should cover startptr and
454444
* endptr, with no gaps in between.
455445
*/
456-
XLogFromFileName(walFiles[0],&tli,&segno,wal_segment_size);
446+
XLogFromFileName((char*)linitial(walFileList),
447+
&tli,&segno,wal_segment_size);
457448
if (segno!=startsegno)
458449
{
459450
charstartfname[MAXFNAMELEN];
@@ -463,12 +454,13 @@ perform_base_backup(basebackup_options *opt)
463454
ereport(ERROR,
464455
(errmsg("could not find WAL file \"%s\"",startfname)));
465456
}
466-
for (i=0;i<nWalFiles;i++)
457+
foreach(lc,walFileList)
467458
{
459+
char*walFileName= (char*)lfirst(lc);
468460
XLogSegNocurrsegno=segno;
469461
XLogSegNonextsegno=segno+1;
470462

471-
XLogFromFileName(walFiles[i],&tli,&segno,wal_segment_size);
463+
XLogFromFileName(walFileName,&tli,&segno,wal_segment_size);
472464
if (!(nextsegno==segno||currsegno==segno))
473465
{
474466
charnextfname[MAXFNAMELEN];
@@ -489,15 +481,16 @@ perform_base_backup(basebackup_options *opt)
489481
}
490482

491483
/* Ok, we have everything we need. Send the WAL files. */
492-
for (i=0;i<nWalFiles;i++)
484+
foreach(lc,walFileList)
493485
{
486+
char*walFileName= (char*)lfirst(lc);
494487
FILE*fp;
495488
charbuf[TAR_SEND_SIZE];
496489
size_tcnt;
497490
pgoff_tlen=0;
498491

499-
snprintf(pathbuf,MAXPGPATH,XLOGDIR"/%s",walFiles[i]);
500-
XLogFromFileName(walFiles[i],&tli,&segno,wal_segment_size);
492+
snprintf(pathbuf,MAXPGPATH,XLOGDIR"/%s",walFileName);
493+
XLogFromFileName(walFileName,&tli,&segno,wal_segment_size);
501494

502495
fp=AllocateFile(pathbuf,"rb");
503496
if (fp==NULL)
@@ -527,7 +520,7 @@ perform_base_backup(basebackup_options *opt)
527520
CheckXLogRemoved(segno,tli);
528521
ereport(ERROR,
529522
(errcode_for_file_access(),
530-
errmsg("unexpected WAL file size \"%s\"",walFiles[i])));
523+
errmsg("unexpected WAL file size \"%s\"",walFileName)));
531524
}
532525

533526
/* send the WAL file itself */
@@ -555,7 +548,7 @@ perform_base_backup(basebackup_options *opt)
555548
CheckXLogRemoved(segno,tli);
556549
ereport(ERROR,
557550
(errcode_for_file_access(),
558-
errmsg("unexpected WAL file size \"%s\"",walFiles[i])));
551+
errmsg("unexpected WAL file size \"%s\"",walFileName)));
559552
}
560553

561554
/* wal_segment_size is a multiple of 512, so no need for padding */
@@ -568,7 +561,7 @@ perform_base_backup(basebackup_options *opt)
568561
* walreceiver.c always doing an XLogArchiveForceDone() after a
569562
* complete segment.
570563
*/
571-
StatusFilePath(pathbuf,walFiles[i],".done");
564+
StatusFilePath(pathbuf,walFileName,".done");
572565
sendFileWithContent(pathbuf,"");
573566
}
574567

@@ -618,14 +611,14 @@ perform_base_backup(basebackup_options *opt)
618611
}
619612

620613
/*
621-
*qsort comparison function, to compare log/seg portion of WAL segment
614+
*list_sort comparison function, to compare log/seg portion of WAL segment
622615
* filenames, ignoring the timeline portion.
623616
*/
624617
staticint
625-
compareWalFileNames(constvoid*a,constvoid*b)
618+
compareWalFileNames(constListCell*a,constListCell*b)
626619
{
627-
char*fna=*((char**)a);
628-
char*fnb=*((char**)b);
620+
char*fna=(char*)lfirst(a);
621+
char*fnb=(char*)lfirst(b);
629622

630623
returnstrcmp(fna+8,fnb+8);
631624
}

‎src/backend/replication/logical/reorderbuffer.c

Lines changed: 8 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -3236,7 +3236,7 @@ ReorderBufferToastReset(ReorderBuffer *rb, ReorderBufferTXN *txn)
32363236
* -------------------------------------------------------------------------
32373237
*/
32383238

3239-
/* struct forqsort()ing mapping files bylsn somewhat efficiently */
3239+
/* struct forsorting mapping files byLSN efficiently */
32403240
typedefstructRewriteMappingFile
32413241
{
32423242
XLogRecPtrlsn;
@@ -3378,13 +3378,13 @@ TransactionIdInArray(TransactionId xid, TransactionId *xip, Size num)
33783378
}
33793379

33803380
/*
3381-
*qsort() comparator for sorting RewriteMappingFiles in LSN order.
3381+
*list_sort() comparator for sorting RewriteMappingFiles in LSN order.
33823382
*/
33833383
staticint
3384-
file_sort_by_lsn(constvoid*a_p,constvoid*b_p)
3384+
file_sort_by_lsn(constListCell*a_p,constListCell*b_p)
33853385
{
3386-
RewriteMappingFile*a=*(RewriteMappingFile**)a_p;
3387-
RewriteMappingFile*b=*(RewriteMappingFile**)b_p;
3386+
RewriteMappingFile*a= (RewriteMappingFile*)lfirst(a_p);
3387+
RewriteMappingFile*b= (RewriteMappingFile*)lfirst(b_p);
33883388

33893389
if (a->lsn<b->lsn)
33903390
return-1;
@@ -3404,8 +3404,6 @@ UpdateLogicalMappings(HTAB *tuplecid_data, Oid relid, Snapshot snapshot)
34043404
structdirent*mapping_de;
34053405
List*files=NIL;
34063406
ListCell*file;
3407-
RewriteMappingFile**files_a;
3408-
size_toff;
34093407
Oiddboid=IsSharedRelation(relid) ?InvalidOid :MyDatabaseId;
34103408

34113409
mapping_dir=AllocateDir("pg_logical/mappings");
@@ -3459,21 +3457,12 @@ UpdateLogicalMappings(HTAB *tuplecid_data, Oid relid, Snapshot snapshot)
34593457
}
34603458
FreeDir(mapping_dir);
34613459

3462-
/* build array we can easily sort */
3463-
files_a=palloc(list_length(files)*sizeof(RewriteMappingFile*));
3464-
off=0;
3465-
foreach(file,files)
3466-
{
3467-
files_a[off++]=lfirst(file);
3468-
}
3469-
34703460
/* sort files so we apply them in LSN order */
3471-
qsort(files_a,list_length(files),sizeof(RewriteMappingFile*),
3472-
file_sort_by_lsn);
3461+
list_sort(files,file_sort_by_lsn);
34733462

3474-
for (off=0;off<list_length(files);off++)
3463+
foreach(file,files)
34753464
{
3476-
RewriteMappingFile*f=files_a[off];
3465+
RewriteMappingFile*f=(RewriteMappingFile*)lfirst(file);
34773466

34783467
elog(DEBUG1,"applying mapping: \"%s\" in %u",f->fname,
34793468
snapshot->subxip[0]);

0 commit comments

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