Skip to content

Commit e2f48bf

Browse files
pablogsalrhettinger
pablogsal
authored and
rhettinger
committed
bpo-34797: Convert heapq to the argument clinic (GH-9560)
1 parent 37aae9d commit e2f48bf

2 files changed

Lines changed: 296 additions & 67 deletions

File tree

‎Modules/_heapqmodule.c‎

Lines changed: 124 additions & 67 deletions
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,13 @@ annotated by François Pinard, and converted to C by Raymond Hettinger.
88

99
#include "Python.h"
1010

11+
#include "clinic/_heapqmodule.c.h"
12+
13+
/*[clinic input]
14+
module _heapq
15+
[clinic start generated code]*/
16+
/*[clinic end generated code: output=da39a3ee5e6b4b0d input=d7cca0a2e4c0ceb3]*/
17+
1118
static int
1219
siftdown(PyListObject *heap, Py_ssize_t startpos, Py_ssize_t pos)
1320
{
@@ -96,14 +103,20 @@ siftup(PyListObject *heap, Py_ssize_t pos)
96103
return siftdown(heap, startpos, pos);
97104
}
98105

99-
static PyObject *
100-
heappush(PyObject *self, PyObject *args)
101-
{
102-
PyObject *heap, *item;
106+
/*[clinic input]
107+
_heapq.heappush
103108
104-
if (!PyArg_UnpackTuple(args, "heappush", 2, 2, &heap, &item))
105-
return NULL;
109+
heap: object
110+
item: object
111+
/
106112
113+
Push item onto heap, maintaining the heap invariant.
114+
[clinic start generated code]*/
115+
116+
static PyObject *
117+
_heapq_heappush_impl(PyObject *module, PyObject *heap, PyObject *item)
118+
/*[clinic end generated code: output=912c094f47663935 input=7913545cb5118842]*/
119+
{
107120
if (!PyList_Check(heap)) {
108121
PyErr_SetString(PyExc_TypeError, "heap argument must be a list");
109122
return NULL;
@@ -117,9 +130,6 @@ heappush(PyObject *self, PyObject *args)
117130
Py_RETURN_NONE;
118131
}
119132

120-
PyDoc_STRVAR(heappush_doc,
121-
"heappush(heap, item) -> None. Push item onto heap, maintaining the heap invariant.");
122-
123133
static PyObject *
124134
heappop_internal(PyObject *heap, int siftup_func(PyListObject *, Py_ssize_t))
125135
{
@@ -157,22 +167,26 @@ heappop_internal(PyObject *heap, int siftup_func(PyListObject *, Py_ssize_t))
157167
return returnitem;
158168
}
159169

170+
/*[clinic input]
171+
_heapq.heappop
172+
173+
heap: object
174+
/
175+
176+
Pop the smallest item off the heap, maintaining the heap invariant.
177+
[clinic start generated code]*/
178+
160179
static PyObject *
161-
heappop(PyObject *self, PyObject *heap)
180+
_heapq_heappop(PyObject *module, PyObject *heap)
181+
/*[clinic end generated code: output=e1bbbc9866bce179 input=9bd36317b806033d]*/
162182
{
163183
return heappop_internal(heap, siftup);
164184
}
165185

166-
PyDoc_STRVAR(heappop_doc,
167-
"Pop the smallest item off the heap, maintaining the heap invariant.");
168-
169186
static PyObject *
170-
heapreplace_internal(PyObject *args, int siftup_func(PyListObject *, Py_ssize_t))
187+
heapreplace_internal(PyObject *heap, PyObject *item, int siftup_func(PyListObject *, Py_ssize_t))
171188
{
172-
PyObject *heap, *item, *returnitem;
173-
174-
if (!PyArg_UnpackTuple(args, "heapreplace", 2, 2, &heap, &item))
175-
return NULL;
189+
PyObject *returnitem;
176190

177191
if (!PyList_Check(heap)) {
178192
PyErr_SetString(PyExc_TypeError, "heap argument must be a list");
@@ -194,31 +208,52 @@ heapreplace_internal(PyObject *args, int siftup_func(PyListObject *, Py_ssize_t)
194208
return returnitem;
195209
}
196210

211+
212+
/*[clinic input]
213+
_heapq.heapreplace
214+
215+
heap: object
216+
item: object
217+
/
218+
219+
Pop and return the current smallest value, and add the new item.
220+
221+
This is more efficient than heappop() followed by heappush(), and can be
222+
more appropriate when using a fixed-size heap. Note that the value
223+
returned may be larger than item! That constrains reasonable uses of
224+
this routine unless written as part of a conditional replacement:
225+
226+
if item > heap[0]:
227+
item = heapreplace(heap, item)
228+
[clinic start generated code]*/
229+
197230
static PyObject *
198-
heapreplace(PyObject *self, PyObject *args)
231+
_heapq_heapreplace_impl(PyObject *module, PyObject *heap, PyObject *item)
232+
/*[clinic end generated code: output=82ea55be8fbe24b4 input=e57ae8f4ecfc88e3]*/
199233
{
200-
return heapreplace_internal(args, siftup);
234+
return heapreplace_internal(heap, item, siftup);
201235
}
202236

203-
PyDoc_STRVAR(heapreplace_doc,
204-
"heapreplace(heap, item) -> value. Pop and return the current smallest value, and add the new item.\n\
205-
\n\
206-
This is more efficient than heappop() followed by heappush(), and can be\n\
207-
more appropriate when using a fixed-size heap. Note that the value\n\
208-
returned may be larger than item! That constrains reasonable uses of\n\
209-
this routine unless written as part of a conditional replacement:\n\n\
210-
if item > heap[0]:\n\
211-
item = heapreplace(heap, item)\n");
237+
/*[clinic input]
238+
_heapq.heappushpop
239+
240+
heap: object
241+
item: object
242+
/
243+
244+
Push item on the heap, then pop and return the smallest item from the heap.
245+
246+
The combined action runs more efficiently than heappush() followed by
247+
a separate call to heappop().
248+
[clinic start generated code]*/
212249

213250
static PyObject *
214-
heappushpop(PyObject *self, PyObject *args)
251+
_heapq_heappushpop_impl(PyObject *module, PyObject *heap, PyObject *item)
252+
/*[clinic end generated code: output=67231dc98ed5774f input=eb48c90ba77b2214]*/
215253
{
216-
PyObject *heap, *item, *returnitem;
254+
PyObject *returnitem;
217255
int cmp;
218256

219-
if (!PyArg_UnpackTuple(args, "heappushpop", 2, 2, &heap, &item))
220-
return NULL;
221-
222257
if (!PyList_Check(heap)) {
223258
PyErr_SetString(PyExc_TypeError, "heap argument must be a list");
224259
return NULL;
@@ -252,11 +287,6 @@ heappushpop(PyObject *self, PyObject *args)
252287
return returnitem;
253288
}
254289

255-
PyDoc_STRVAR(heappushpop_doc,
256-
"heappushpop(heap, item) -> value. Push item on the heap, then pop and return the smallest item\n\
257-
from the heap. The combined action runs more efficiently than\n\
258-
heappush() followed by a separate call to heappop().");
259-
260290
static Py_ssize_t
261291
keep_top_bit(Py_ssize_t n)
262292
{
@@ -353,15 +383,22 @@ heapify_internal(PyObject *heap, int siftup_func(PyListObject *, Py_ssize_t))
353383
Py_RETURN_NONE;
354384
}
355385

386+
/*[clinic input]
387+
_heapq.heapify
388+
389+
heap: object
390+
/
391+
392+
Transform list into a heap, in-place, in O(len(heap)) time.
393+
[clinic start generated code]*/
394+
356395
static PyObject *
357-
heapify(PyObject *self, PyObject *heap)
396+
_heapq_heapify(PyObject *module, PyObject *heap)
397+
/*[clinic end generated code: output=11483f23627c4616 input=872c87504b8de970]*/
358398
{
359399
return heapify_internal(heap, siftup);
360400
}
361401

362-
PyDoc_STRVAR(heapify_doc,
363-
"Transform list into a heap, in-place, in O(len(heap)) time.");
364-
365402
static int
366403
siftdown_max(PyListObject *heap, Py_ssize_t startpos, Py_ssize_t pos)
367404
{
@@ -450,48 +487,68 @@ siftup_max(PyListObject *heap, Py_ssize_t pos)
450487
return siftdown_max(heap, startpos, pos);
451488
}
452489

490+
491+
/*[clinic input]
492+
_heapq._heappop_max
493+
494+
heap: object
495+
/
496+
497+
Maxheap variant of heappop.
498+
[clinic start generated code]*/
499+
453500
static PyObject *
454-
heappop_max(PyObject *self, PyObject *heap)
501+
_heapq__heappop_max(PyObject *module, PyObject *heap)
502+
/*[clinic end generated code: output=acd30acf6384b13c input=62ede3ba9117f541]*/
455503
{
456504
return heappop_internal(heap, siftup_max);
457505
}
458506

459-
PyDoc_STRVAR(heappop_max_doc, "Maxheap variant of heappop.");
507+
/*[clinic input]
508+
_heapq._heapreplace_max
509+
510+
heap: object
511+
item: object
512+
/
513+
514+
Maxheap variant of heapreplace.
515+
[clinic start generated code]*/
460516

461517
static PyObject *
462-
heapreplace_max(PyObject *self, PyObject *args)
518+
_heapq__heapreplace_max_impl(PyObject *module, PyObject *heap,
519+
PyObject *item)
520+
/*[clinic end generated code: output=8ad7545e4a5e8adb input=6d8f25131e0f0e5f]*/
463521
{
464-
return heapreplace_internal(args, siftup_max);
522+
return heapreplace_internal(heap, item, siftup_max);
465523
}
466524

467-
PyDoc_STRVAR(heapreplace_max_doc, "Maxheap variant of heapreplace");
525+
/*[clinic input]
526+
_heapq._heapify_max
527+
528+
heap: object
529+
/
530+
531+
Maxheap variant of heapify.
532+
[clinic start generated code]*/
468533

469534
static PyObject *
470-
heapify_max(PyObject *self, PyObject *heap)
535+
_heapq__heapify_max(PyObject *module, PyObject *heap)
536+
/*[clinic end generated code: output=1c6bb6b60d6a2133 input=cdfcc6835b14110d]*/
471537
{
472538
return heapify_internal(heap, siftup_max);
473539
}
474540

475-
PyDoc_STRVAR(heapify_max_doc, "Maxheap variant of heapify.");
476541

477542
static PyMethodDef heapq_methods[] = {
478-
{"heappush", (PyCFunction)heappush,
479-
METH_VARARGS, heappush_doc},
480-
{"heappushpop", (PyCFunction)heappushpop,
481-
METH_VARARGS, heappushpop_doc},
482-
{"heappop", (PyCFunction)heappop,
483-
METH_O, heappop_doc},
484-
{"heapreplace", (PyCFunction)heapreplace,
485-
METH_VARARGS, heapreplace_doc},
486-
{"heapify", (PyCFunction)heapify,
487-
METH_O, heapify_doc},
488-
{"_heappop_max", (PyCFunction)heappop_max,
489-
METH_O, heappop_max_doc},
490-
{"_heapreplace_max",(PyCFunction)heapreplace_max,
491-
METH_VARARGS, heapreplace_max_doc},
492-
{"_heapify_max", (PyCFunction)heapify_max,
493-
METH_O, heapify_max_doc},
494-
{NULL, NULL} /* sentinel */
543+
_HEAPQ_HEAPPUSH_METHODDEF
544+
_HEAPQ_HEAPPUSHPOP_METHODDEF
545+
_HEAPQ_HEAPPOP_METHODDEF
546+
_HEAPQ_HEAPREPLACE_METHODDEF
547+
_HEAPQ_HEAPIFY_METHODDEF
548+
_HEAPQ__HEAPPOP_MAX_METHODDEF
549+
_HEAPQ__HEAPIFY_MAX_METHODDEF
550+
_HEAPQ__HEAPREPLACE_MAX_METHODDEF
551+
{NULL, NULL} /* sentinel */
495552
};
496553

497554
PyDoc_STRVAR(module_doc,

0 commit comments

Comments
 (0)