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

Commit3cb1b2a

Browse files
committed
Rewrite list_qsort() to avoid trashing its input list.
The initial implementation of list_qsort(), from commitab72716,re-used the ListCells of the input list while not touching the Listheader. This meant that anybody who still had a pointer to theoriginal header would now be in possession of a corrupted list,a problem that seems sure to bite us eventually.One possible solution is to re-use the original List header as well,giving the function the semantics of update-in-place. However, thatdoesn't seem like a very good idea either given the way that thefunction is used in the planner: create_path functions aren't normallysupposed to modify their input lists. It doesn't look like there wouldbe a problem today, but it's not hard to foresee a time when modifyinga list of Paths in-place could have side-effects on some other appendpath.On the whole, and in view of the likelihood that this function mightbe used in other contexts in the future, it seems best to get rid ofthe micro-optimization of re-using the input list cells. Just builda new list.Discussion:https://postgr.es/m/16912.1515449066@sss.pgh.pa.us
1 parent624e440 commit3cb1b2a

File tree

1 file changed

+40
-16
lines changed

1 file changed

+40
-16
lines changed

‎src/backend/nodes/list.c

Lines changed: 40 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -1250,41 +1250,65 @@ list_copy_tail(const List *oldlist, int nskip)
12501250
}
12511251

12521252
/*
1253-
* Sort a list using qsort. A sorted list is built but the cells of the
1254-
* original list are re-used. The comparator function receives arguments of
1255-
* type ListCell **
1253+
* Sort a list as though by qsort.
1254+
*
1255+
* A new list is built and returned. Like list_copy, this doesn't make
1256+
* fresh copies of any pointed-to data.
1257+
*
1258+
* The comparator function receives arguments of type ListCell **.
12561259
*/
12571260
List*
12581261
list_qsort(constList*list,list_qsort_comparatorcmp)
12591262
{
1260-
ListCell*cell;
1261-
inti;
12621263
intlen=list_length(list);
12631264
ListCell**list_arr;
1264-
List*new_list;
1265+
List*newlist;
1266+
ListCell*newlist_prev;
1267+
ListCell*cell;
1268+
inti;
12651269

1270+
/* Empty list is easy */
12661271
if (len==0)
12671272
returnNIL;
12681273

1274+
/* Flatten list cells into an array, so we can use qsort */
1275+
list_arr= (ListCell**)palloc(sizeof(ListCell*)*len);
12691276
i=0;
1270-
list_arr=palloc(sizeof(ListCell*)*len);
12711277
foreach(cell,list)
12721278
list_arr[i++]=cell;
12731279

12741280
qsort(list_arr,len,sizeof(ListCell*),cmp);
12751281

1276-
new_list= (List*)palloc(sizeof(List));
1277-
new_list->type=list->type;
1278-
new_list->length=len;
1279-
new_list->head=list_arr[0];
1280-
new_list->tail=list_arr[len-1];
1282+
/* Construct new list (this code is much like list_copy) */
1283+
newlist=new_list(list->type);
1284+
newlist->length=len;
1285+
1286+
/*
1287+
* Copy over the data in the first cell; new_list() has already allocated
1288+
* the head cell itself
1289+
*/
1290+
newlist->head->data=list_arr[0]->data;
1291+
1292+
newlist_prev=newlist->head;
1293+
for (i=1;i<len;i++)
1294+
{
1295+
ListCell*newlist_cur;
1296+
1297+
newlist_cur= (ListCell*)palloc(sizeof(*newlist_cur));
1298+
newlist_cur->data=list_arr[i]->data;
1299+
newlist_prev->next=newlist_cur;
12811300

1282-
for (i=0;i<len-1;i++)
1283-
list_arr[i]->next=list_arr[i+1];
1301+
newlist_prev=newlist_cur;
1302+
}
12841303

1285-
list_arr[len-1]->next=NULL;
1304+
newlist_prev->next=NULL;
1305+
newlist->tail=newlist_prev;
1306+
1307+
/* Might as well free the workspace array */
12861308
pfree(list_arr);
1287-
returnnew_list;
1309+
1310+
check_list_invariants(newlist);
1311+
returnnewlist;
12881312
}
12891313

12901314
/*

0 commit comments

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