Skip to content

Commit 871620d

Browse files
rhettingerrhettinger
committed
Simplify and speedup the internals of the heapq module.
1 parent 4ce5f3f commit 871620d

1 file changed

Lines changed: 36 additions & 71 deletions

File tree

‎Modules/_heapqmodule.c‎

Lines changed: 36 additions & 71 deletions
Original file line numberDiff line numberDiff line change
@@ -11,7 +11,7 @@ annotated by François Pinard, and converted to C by Raymond Hettinger.
1111
static int
1212
_siftdown(PyListObject *heap, Py_ssize_t startpos, Py_ssize_t pos)
1313
{
14-
PyObject *newitem, *parent, *olditem;
14+
PyObject *newitem, *parent;
1515
int cmp;
1616
Py_ssize_t parentpos;
1717
Py_ssize_t size;
@@ -23,60 +23,45 @@ _siftdown(PyListObject *heap, Py_ssize_t startpos, Py_ssize_t pos)
2323
return -1;
2424
}
2525

26-
newitem = PyList_GET_ITEM(heap, pos);
27-
Py_INCREF(newitem);
2826
/* Follow the path to the root, moving parents down until finding
2927
a place newitem fits. */
28+
newitem = PyList_GET_ITEM(heap, pos);
3029
while (pos > startpos){
3130
parentpos = (pos - 1) >> 1;
3231
parent = PyList_GET_ITEM(heap, parentpos);
3332
cmp = PyObject_RichCompareBool(newitem, parent, Py_LT);
34-
if (cmp == -1) {
35-
Py_DECREF(newitem);
33+
if (cmp == -1)
3634
return -1;
37-
}
3835
if (size != PyList_GET_SIZE(heap)) {
39-
Py_DECREF(newitem);
4036
PyErr_SetString(PyExc_RuntimeError,
4137
"list changed size during iteration");
4238
return -1;
4339
}
4440
if (cmp == 0)
4541
break;
46-
Py_INCREF(parent);
47-
olditem = PyList_GET_ITEM(heap, pos);
42+
parent = PyList_GET_ITEM(heap, parentpos);
43+
newitem = PyList_GET_ITEM(heap, pos);
44+
PyList_SET_ITEM(heap, parentpos, newitem);
4845
PyList_SET_ITEM(heap, pos, parent);
49-
Py_DECREF(olditem);
5046
pos = parentpos;
51-
if (size != PyList_GET_SIZE(heap)) {
52-
PyErr_SetString(PyExc_RuntimeError,
53-
"list changed size during iteration");
54-
return -1;
55-
}
5647
}
57-
Py_DECREF(PyList_GET_ITEM(heap, pos));
58-
PyList_SET_ITEM(heap, pos, newitem);
5948
return 0;
6049
}
6150

6251
static int
6352
_siftup(PyListObject *heap, Py_ssize_t pos)
6453
{
6554
Py_ssize_t startpos, endpos, childpos, rightpos, limit;
55+
PyObject *tmp1, *tmp2;
6656
int cmp;
67-
PyObject *newitem, *tmp, *olditem;
68-
Py_ssize_t size;
6957

7058
assert(PyList_Check(heap));
71-
size = PyList_GET_SIZE(heap);
72-
endpos = size;
59+
endpos = PyList_GET_SIZE(heap);
7360
startpos = pos;
7461
if (pos >= endpos) {
7562
PyErr_SetString(PyExc_IndexError, "index out of range");
7663
return -1;
7764
}
78-
newitem = PyList_GET_ITEM(heap, pos);
79-
Py_INCREF(newitem);
8065

8166
/* Bubble up the smaller child until hitting a leaf. */
8267
limit = endpos / 2; /* smallest pos that has no child */
@@ -89,37 +74,24 @@ _siftup(PyListObject *heap, Py_ssize_t pos)
8974
PyList_GET_ITEM(heap, childpos),
9075
PyList_GET_ITEM(heap, rightpos),
9176
Py_LT);
92-
if (cmp == -1) {
93-
Py_DECREF(newitem);
77+
if (cmp == -1)
9478
return -1;
95-
}
9679
if (cmp == 0)
9780
childpos = rightpos;
98-
}
99-
if (size != PyList_GET_SIZE(heap)) {
100-
Py_DECREF(newitem);
101-
PyErr_SetString(PyExc_RuntimeError,
102-
"list changed size during iteration");
103-
return -1;
81+
if (endpos != PyList_GET_SIZE(heap)) {
82+
PyErr_SetString(PyExc_RuntimeError,
83+
"list changed size during iteration");
84+
return -1;
85+
}
10486
}
10587
/* Move the smaller child up. */
106-
tmp = PyList_GET_ITEM(heap, childpos);
107-
Py_INCREF(tmp);
108-
olditem = PyList_GET_ITEM(heap, pos);
109-
PyList_SET_ITEM(heap, pos, tmp);
110-
Py_DECREF(olditem);
88+
tmp1 = PyList_GET_ITEM(heap, childpos);
89+
tmp2 = PyList_GET_ITEM(heap, pos);
90+
PyList_SET_ITEM(heap, childpos, tmp2);
91+
PyList_SET_ITEM(heap, pos, tmp1);
11192
pos = childpos;
112-
if (size != PyList_GET_SIZE(heap)) {
113-
PyErr_SetString(PyExc_RuntimeError,
114-
"list changed size during iteration");
115-
return -1;
116-
}
11793
}
118-
119-
/* The leaf at pos is empty now. Put newitem there, and bubble
120-
it up to its final resting place (by sifting its parents down). */
121-
Py_DECREF(PyList_GET_ITEM(heap, pos));
122-
PyList_SET_ITEM(heap, pos, newitem);
94+
/* Bubble it up to its final resting place (by sifting its parents down). */
12395
return _siftdown(heap, startpos, pos);
12496
}
12597

@@ -392,36 +364,32 @@ _siftdownmax(PyListObject *heap, Py_ssize_t startpos, Py_ssize_t pos)
392364
return -1;
393365
}
394366

395-
newitem = PyList_GET_ITEM(heap, pos);
396-
Py_INCREF(newitem);
397367
/* Follow the path to the root, moving parents down until finding
398368
a place newitem fits. */
369+
newitem = PyList_GET_ITEM(heap, pos);
399370
while (pos > startpos){
400371
parentpos = (pos - 1) >> 1;
401372
parent = PyList_GET_ITEM(heap, parentpos);
402373
cmp = PyObject_RichCompareBool(parent, newitem, Py_LT);
403-
if (cmp == -1) {
404-
Py_DECREF(newitem);
374+
if (cmp == -1)
405375
return -1;
406-
}
407376
if (cmp == 0)
408377
break;
409-
Py_INCREF(parent);
410-
Py_DECREF(PyList_GET_ITEM(heap, pos));
378+
parent = PyList_GET_ITEM(heap, parentpos);
379+
newitem = PyList_GET_ITEM(heap, pos);
380+
PyList_SET_ITEM(heap, parentpos, newitem);
411381
PyList_SET_ITEM(heap, pos, parent);
412382
pos = parentpos;
413383
}
414-
Py_DECREF(PyList_GET_ITEM(heap, pos));
415-
PyList_SET_ITEM(heap, pos, newitem);
416384
return 0;
417385
}
418386

419387
static int
420388
_siftupmax(PyListObject *heap, Py_ssize_t pos)
421389
{
422390
Py_ssize_t startpos, endpos, childpos, rightpos, limit;
391+
PyObject *tmp1, *tmp2;
423392
int cmp;
424-
PyObject *newitem, *tmp;
425393

426394
assert(PyList_Check(heap));
427395
endpos = PyList_GET_SIZE(heap);
@@ -430,8 +398,6 @@ _siftupmax(PyListObject *heap, Py_ssize_t pos)
430398
PyErr_SetString(PyExc_IndexError, "index out of range");
431399
return -1;
432400
}
433-
newitem = PyList_GET_ITEM(heap, pos);
434-
Py_INCREF(newitem);
435401

436402
/* Bubble up the smaller child until hitting a leaf. */
437403
limit = endpos / 2; /* smallest pos that has no child */
@@ -444,25 +410,24 @@ _siftupmax(PyListObject *heap, Py_ssize_t pos)
444410
PyList_GET_ITEM(heap, rightpos),
445411
PyList_GET_ITEM(heap, childpos),
446412
Py_LT);
447-
if (cmp == -1) {
448-
Py_DECREF(newitem);
413+
if (cmp == -1)
449414
return -1;
450-
}
451415
if (cmp == 0)
452416
childpos = rightpos;
417+
if (endpos != PyList_GET_SIZE(heap)) {
418+
PyErr_SetString(PyExc_RuntimeError,
419+
"list changed size during iteration");
420+
return -1;
421+
}
453422
}
454423
/* Move the smaller child up. */
455-
tmp = PyList_GET_ITEM(heap, childpos);
456-
Py_INCREF(tmp);
457-
Py_DECREF(PyList_GET_ITEM(heap, pos));
458-
PyList_SET_ITEM(heap, pos, tmp);
424+
tmp1 = PyList_GET_ITEM(heap, childpos);
425+
tmp2 = PyList_GET_ITEM(heap, pos);
426+
PyList_SET_ITEM(heap, childpos, tmp2);
427+
PyList_SET_ITEM(heap, pos, tmp1);
459428
pos = childpos;
460429
}
461-
462-
/* The leaf at pos is empty now. Put newitem there, and bubble
463-
it up to its final resting place (by sifting its parents down). */
464-
Py_DECREF(PyList_GET_ITEM(heap, pos));
465-
PyList_SET_ITEM(heap, pos, newitem);
430+
/* Bubble it up to its final resting place (by sifting its parents down). */
466431
return _siftdownmax(heap, startpos, pos);
467432
}
468433

0 commit comments

Comments
 (0)