cpython-lru_cache-weakref: Modules/_bisectmodule.c annotate

annotate Modules/_bisectmodule.c @ 58689:514b56efd89a 3.1

Merged revisions 77962 via svnmerge from svn+ssh://pythondev@svn.python.org/python/branches/py3k ................ r77962 | r.david.murray | 2010-02-04 11:41:57 -0500 (Thu, 04 Feb 2010) | 17 lines Merged revisions 77943,77959-77960 via svnmerge from svn+ssh://pythondev@svn.python.org/python/trunk ........ r77943 | r.david.murray | 2010-02-03 08:36:23 -0500 (Wed, 03 Feb 2010) | 2 lines Explicitly mention the default value for formatdate's usegmt parameter. ........ r77959 | nick.coghlan | 2010-02-04 07:43:58 -0500 (Thu, 04 Feb 2010) | 1 line Issue 6760: Clarify args handling for subprocess.Popen. Patch by Chris Rebert ........ r77960 | r.david.murray | 2010-02-04 11:33:31 -0500 (Thu, 04 Feb 2010) | 2 lines Add Chris Rebert to ACKS for issue 6760 Popen doc improvements. ........ ................

author	R. David Murray <rdmurray@bitdance.com>
date	Thu, 04 Feb 2010 16:44:31 +0000
parents	bdf4da5d04ad
children	cab14be0ada1

rev	line source
31353 ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	1 /* Bisection algorithms. Drop in replacement for bisect.py
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	2
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	3 Converted to C by Dmitry Vasiliev (dima at hlabs.spb.ru).
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	4 */
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	5
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	6 #include "Python.h"
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	7
48594 35b1a20470db Merged revisions 65209-65216,65225-65226,65233,65239,65246-65247,65255-65256 via svnmerge from Benjamin Peterson <benjamin@python.org> parents: 48499 diff changeset	8 static Py_ssize_t
36518 9f3f87e920a6 Use Py_ssize_t for counts and sizes. Martin v. Löwis <martin@v.loewis.de> parents: 35999 diff changeset	9 internal_bisect_right(PyObject list, PyObject item, Py_ssize_t lo, Py_ssize_t hi)
31353 ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	10 {
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	11 PyObject *litem;
36518 9f3f87e920a6 Use Py_ssize_t for counts and sizes. Martin v. Löwis <martin@v.loewis.de> parents: 35999 diff changeset	12 Py_ssize_t mid, res;
31353 ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	13
48499 de0bf60f1245 Merged revisions 64722,64729,64753,64845-64846,64849,64871,64880-64882,64885,64888,64897,64900-64901,64915,64926-64929,64938-64941,64944,64961,64966,64973 via svnmerge from Georg Brandl <georg@python.org> parents: 47580 diff changeset	14 if (lo < 0) {
de0bf60f1245 Merged revisions 64722,64729,64753,64845-64846,64849,64871,64880-64882,64885,64888,64897,64900-64901,64915,64926-64929,64938-64941,64944,64961,64966,64973 via svnmerge from Georg Brandl <georg@python.org> parents: 47580 diff changeset	15 PyErr_SetString(PyExc_ValueError, "lo must be non-negative");
de0bf60f1245 Merged revisions 64722,64729,64753,64845-64846,64849,64871,64880-64882,64885,64888,64897,64900-64901,64915,64926-64929,64938-64941,64944,64961,64966,64973 via svnmerge from Georg Brandl <georg@python.org> parents: 47580 diff changeset	16 return -1;
de0bf60f1245 Merged revisions 64722,64729,64753,64845-64846,64849,64871,64880-64882,64885,64888,64897,64900-64901,64915,64926-64929,64938-64941,64944,64961,64966,64973 via svnmerge from Georg Brandl <georg@python.org> parents: 47580 diff changeset	17 }
31353 ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	18 if (hi == -1) {
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	19 hi = PySequence_Size(list);
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	20 if (hi < 0)
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	21 return -1;
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	22 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	23 while (lo < hi) {
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	24 mid = (lo + hi) / 2;
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	25 litem = PySequence_GetItem(list, mid);
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	26 if (litem == NULL)
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	27 return -1;
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	28 res = PyObject_RichCompareBool(item, litem, Py_LT);
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	29 Py_DECREF(litem);
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	30 if (res < 0)
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	31 return -1;
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	32 if (res)
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	33 hi = mid;
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	34 else
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	35 lo = mid + 1;
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	36 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	37 return lo;
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	38 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	39
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	40 static PyObject *
35699 3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args Raymond Hettinger <python@rcn.com> parents: 32898 diff changeset	41 bisect_right(PyObject self, PyObject args, PyObject *kw)
31353 ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	42 {
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	43 PyObject list, item;
48594 35b1a20470db Merged revisions 65209-65216,65225-65226,65233,65239,65246-65247,65255-65256 via svnmerge from Benjamin Peterson <benjamin@python.org> parents: 48499 diff changeset	44 Py_ssize_t lo = 0;
35b1a20470db Merged revisions 65209-65216,65225-65226,65233,65239,65246-65247,65255-65256 via svnmerge from Benjamin Peterson <benjamin@python.org> parents: 48499 diff changeset	45 Py_ssize_t hi = -1;
35b1a20470db Merged revisions 65209-65216,65225-65226,65233,65239,65246-65247,65255-65256 via svnmerge from Benjamin Peterson <benjamin@python.org> parents: 48499 diff changeset	46 Py_ssize_t index;
36684 0bebeb393045 More unconsting. Martin v. Löwis <martin@v.loewis.de> parents: 36518 diff changeset	47 static char *keywords[] = {"a", "x", "lo", "hi", NULL};
31353 ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	48
48594 35b1a20470db Merged revisions 65209-65216,65225-65226,65233,65239,65246-65247,65255-65256 via svnmerge from Benjamin Peterson <benjamin@python.org> parents: 48499 diff changeset	49 if (!PyArg_ParseTupleAndKeywords(args, kw, "OO\|nn:bisect_right",
35699 3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args Raymond Hettinger <python@rcn.com> parents: 32898 diff changeset	50 keywords, &list, &item, &lo, &hi))
31353 ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	51 return NULL;
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	52 index = internal_bisect_right(list, item, lo, hi);
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	53 if (index < 0)
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	54 return NULL;
48594 35b1a20470db Merged revisions 65209-65216,65225-65226,65233,65239,65246-65247,65255-65256 via svnmerge from Benjamin Peterson <benjamin@python.org> parents: 48499 diff changeset	55 return PyLong_FromSsize_t(index);
31353 ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	56 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	57
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	58 PyDoc_STRVAR(bisect_right_doc,
35699 3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args Raymond Hettinger <python@rcn.com> parents: 32898 diff changeset	59 "bisect_right(a, x[, lo[, hi]]) -> index\n\
31353 ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	60 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	61 Return the index where to insert item x in list a, assuming a is sorted.\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	62 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	63 The return value i is such that all e in a[:i] have e <= x, and all e in\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	64 a[i:] have e > x. So if x already appears in the list, i points just\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	65 beyond the rightmost x already there\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	66 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	67 Optional args lo (default 0) and hi (default len(a)) bound the\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	68 slice of a to be searched.\n");
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	69
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	70 static PyObject *
35699 3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args Raymond Hettinger <python@rcn.com> parents: 32898 diff changeset	71 insort_right(PyObject self, PyObject args, PyObject *kw)
31353 ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	72 {
32898 daec2d311def Any call to insort_{left,right} with a non-list leaked a reference to None Michael W. Hudson <mwh@python.net> parents: 31353 diff changeset	73 PyObject list, item, *result;
48594 35b1a20470db Merged revisions 65209-65216,65225-65226,65233,65239,65246-65247,65255-65256 via svnmerge from Benjamin Peterson <benjamin@python.org> parents: 48499 diff changeset	74 Py_ssize_t lo = 0;
35b1a20470db Merged revisions 65209-65216,65225-65226,65233,65239,65246-65247,65255-65256 via svnmerge from Benjamin Peterson <benjamin@python.org> parents: 48499 diff changeset	75 Py_ssize_t hi = -1;
35b1a20470db Merged revisions 65209-65216,65225-65226,65233,65239,65246-65247,65255-65256 via svnmerge from Benjamin Peterson <benjamin@python.org> parents: 48499 diff changeset	76 Py_ssize_t index;
36684 0bebeb393045 More unconsting. Martin v. Löwis <martin@v.loewis.de> parents: 36518 diff changeset	77 static char *keywords[] = {"a", "x", "lo", "hi", NULL};
31353 ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	78
48594 35b1a20470db Merged revisions 65209-65216,65225-65226,65233,65239,65246-65247,65255-65256 via svnmerge from Benjamin Peterson <benjamin@python.org> parents: 48499 diff changeset	79 if (!PyArg_ParseTupleAndKeywords(args, kw, "OO\|nn:insort_right",
35699 3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args Raymond Hettinger <python@rcn.com> parents: 32898 diff changeset	80 keywords, &list, &item, &lo, &hi))
31353 ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	81 return NULL;
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	82 index = internal_bisect_right(list, item, lo, hi);
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	83 if (index < 0)
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	84 return NULL;
49493 bdf4da5d04ad merge from trunk Benjamin Peterson <benjamin@python.org> parents: 48594 diff changeset	85 if (PyList_CheckExact(list)) {
31353 ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	86 if (PyList_Insert(list, index, item) < 0)
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	87 return NULL;
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	88 } else {
48594 35b1a20470db Merged revisions 65209-65216,65225-65226,65233,65239,65246-65247,65255-65256 via svnmerge from Benjamin Peterson <benjamin@python.org> parents: 48499 diff changeset	89 result = PyObject_CallMethod(list, "insert", "nO",
32898 daec2d311def Any call to insort_{left,right} with a non-list leaked a reference to None Michael W. Hudson <mwh@python.net> parents: 31353 diff changeset	90 index, item);
daec2d311def Any call to insort_{left,right} with a non-list leaked a reference to None Michael W. Hudson <mwh@python.net> parents: 31353 diff changeset	91 if (result == NULL)
31353 ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	92 return NULL;
32898 daec2d311def Any call to insort_{left,right} with a non-list leaked a reference to None Michael W. Hudson <mwh@python.net> parents: 31353 diff changeset	93 Py_DECREF(result);
31353 ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	94 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	95
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	96 Py_RETURN_NONE;
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	97 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	98
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	99 PyDoc_STRVAR(insort_right_doc,
35699 3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args Raymond Hettinger <python@rcn.com> parents: 32898 diff changeset	100 "insort_right(a, x[, lo[, hi]])\n\
31353 ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	101 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	102 Insert item x in list a, and keep it sorted assuming a is sorted.\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	103 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	104 If x is already in a, insert it to the right of the rightmost x.\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	105 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	106 Optional args lo (default 0) and hi (default len(a)) bound the\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	107 slice of a to be searched.\n");
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	108
48594 35b1a20470db Merged revisions 65209-65216,65225-65226,65233,65239,65246-65247,65255-65256 via svnmerge from Benjamin Peterson <benjamin@python.org> parents: 48499 diff changeset	109 static Py_ssize_t
35b1a20470db Merged revisions 65209-65216,65225-65226,65233,65239,65246-65247,65255-65256 via svnmerge from Benjamin Peterson <benjamin@python.org> parents: 48499 diff changeset	110 internal_bisect_left(PyObject list, PyObject item, Py_ssize_t lo, Py_ssize_t hi)
31353 ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	111 {
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	112 PyObject *litem;
48594 35b1a20470db Merged revisions 65209-65216,65225-65226,65233,65239,65246-65247,65255-65256 via svnmerge from Benjamin Peterson <benjamin@python.org> parents: 48499 diff changeset	113 Py_ssize_t mid, res;
31353 ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	114
48499 de0bf60f1245 Merged revisions 64722,64729,64753,64845-64846,64849,64871,64880-64882,64885,64888,64897,64900-64901,64915,64926-64929,64938-64941,64944,64961,64966,64973 via svnmerge from Georg Brandl <georg@python.org> parents: 47580 diff changeset	115 if (lo < 0) {
de0bf60f1245 Merged revisions 64722,64729,64753,64845-64846,64849,64871,64880-64882,64885,64888,64897,64900-64901,64915,64926-64929,64938-64941,64944,64961,64966,64973 via svnmerge from Georg Brandl <georg@python.org> parents: 47580 diff changeset	116 PyErr_SetString(PyExc_ValueError, "lo must be non-negative");
de0bf60f1245 Merged revisions 64722,64729,64753,64845-64846,64849,64871,64880-64882,64885,64888,64897,64900-64901,64915,64926-64929,64938-64941,64944,64961,64966,64973 via svnmerge from Georg Brandl <georg@python.org> parents: 47580 diff changeset	117 return -1;
de0bf60f1245 Merged revisions 64722,64729,64753,64845-64846,64849,64871,64880-64882,64885,64888,64897,64900-64901,64915,64926-64929,64938-64941,64944,64961,64966,64973 via svnmerge from Georg Brandl <georg@python.org> parents: 47580 diff changeset	118 }
31353 ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	119 if (hi == -1) {
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	120 hi = PySequence_Size(list);
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	121 if (hi < 0)
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	122 return -1;
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	123 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	124 while (lo < hi) {
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	125 mid = (lo + hi) / 2;
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	126 litem = PySequence_GetItem(list, mid);
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	127 if (litem == NULL)
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	128 return -1;
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	129 res = PyObject_RichCompareBool(litem, item, Py_LT);
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	130 Py_DECREF(litem);
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	131 if (res < 0)
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	132 return -1;
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	133 if (res)
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	134 lo = mid + 1;
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	135 else
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	136 hi = mid;
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	137 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	138 return lo;
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	139 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	140
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	141 static PyObject *
35699 3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args Raymond Hettinger <python@rcn.com> parents: 32898 diff changeset	142 bisect_left(PyObject self, PyObject args, PyObject *kw)
31353 ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	143 {
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	144 PyObject list, item;
48594 35b1a20470db Merged revisions 65209-65216,65225-65226,65233,65239,65246-65247,65255-65256 via svnmerge from Benjamin Peterson <benjamin@python.org> parents: 48499 diff changeset	145 Py_ssize_t lo = 0;
35b1a20470db Merged revisions 65209-65216,65225-65226,65233,65239,65246-65247,65255-65256 via svnmerge from Benjamin Peterson <benjamin@python.org> parents: 48499 diff changeset	146 Py_ssize_t hi = -1;
35b1a20470db Merged revisions 65209-65216,65225-65226,65233,65239,65246-65247,65255-65256 via svnmerge from Benjamin Peterson <benjamin@python.org> parents: 48499 diff changeset	147 Py_ssize_t index;
36684 0bebeb393045 More unconsting. Martin v. Löwis <martin@v.loewis.de> parents: 36518 diff changeset	148 static char *keywords[] = {"a", "x", "lo", "hi", NULL};
31353 ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	149
48594 35b1a20470db Merged revisions 65209-65216,65225-65226,65233,65239,65246-65247,65255-65256 via svnmerge from Benjamin Peterson <benjamin@python.org> parents: 48499 diff changeset	150 if (!PyArg_ParseTupleAndKeywords(args, kw, "OO\|nn:bisect_left",
35699 3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args Raymond Hettinger <python@rcn.com> parents: 32898 diff changeset	151 keywords, &list, &item, &lo, &hi))
31353 ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	152 return NULL;
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	153 index = internal_bisect_left(list, item, lo, hi);
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	154 if (index < 0)
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	155 return NULL;
48594 35b1a20470db Merged revisions 65209-65216,65225-65226,65233,65239,65246-65247,65255-65256 via svnmerge from Benjamin Peterson <benjamin@python.org> parents: 48499 diff changeset	156 return PyLong_FromSsize_t(index);
31353 ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	157 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	158
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	159 PyDoc_STRVAR(bisect_left_doc,
35699 3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args Raymond Hettinger <python@rcn.com> parents: 32898 diff changeset	160 "bisect_left(a, x[, lo[, hi]]) -> index\n\
31353 ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	161 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	162 Return the index where to insert item x in list a, assuming a is sorted.\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	163 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	164 The return value i is such that all e in a[:i] have e < x, and all e in\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	165 a[i:] have e >= x. So if x already appears in the list, i points just\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	166 before the leftmost x already there.\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	167 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	168 Optional args lo (default 0) and hi (default len(a)) bound the\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	169 slice of a to be searched.\n");
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	170
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	171 static PyObject *
35699 3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args Raymond Hettinger <python@rcn.com> parents: 32898 diff changeset	172 insort_left(PyObject self, PyObject args, PyObject *kw)
31353 ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	173 {
32898 daec2d311def Any call to insort_{left,right} with a non-list leaked a reference to None Michael W. Hudson <mwh@python.net> parents: 31353 diff changeset	174 PyObject list, item, *result;
48594 35b1a20470db Merged revisions 65209-65216,65225-65226,65233,65239,65246-65247,65255-65256 via svnmerge from Benjamin Peterson <benjamin@python.org> parents: 48499 diff changeset	175 Py_ssize_t lo = 0;
35b1a20470db Merged revisions 65209-65216,65225-65226,65233,65239,65246-65247,65255-65256 via svnmerge from Benjamin Peterson <benjamin@python.org> parents: 48499 diff changeset	176 Py_ssize_t hi = -1;
35b1a20470db Merged revisions 65209-65216,65225-65226,65233,65239,65246-65247,65255-65256 via svnmerge from Benjamin Peterson <benjamin@python.org> parents: 48499 diff changeset	177 Py_ssize_t index;
36684 0bebeb393045 More unconsting. Martin v. Löwis <martin@v.loewis.de> parents: 36518 diff changeset	178 static char *keywords[] = {"a", "x", "lo", "hi", NULL};
31353 ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	179
48594 35b1a20470db Merged revisions 65209-65216,65225-65226,65233,65239,65246-65247,65255-65256 via svnmerge from Benjamin Peterson <benjamin@python.org> parents: 48499 diff changeset	180 if (!PyArg_ParseTupleAndKeywords(args, kw, "OO\|nn:insort_left",
35699 3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args Raymond Hettinger <python@rcn.com> parents: 32898 diff changeset	181 keywords, &list, &item, &lo, &hi))
31353 ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	182 return NULL;
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	183 index = internal_bisect_left(list, item, lo, hi);
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	184 if (index < 0)
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	185 return NULL;
49493 bdf4da5d04ad merge from trunk Benjamin Peterson <benjamin@python.org> parents: 48594 diff changeset	186 if (PyList_CheckExact(list)) {
31353 ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	187 if (PyList_Insert(list, index, item) < 0)
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	188 return NULL;
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	189 } else {
32898 daec2d311def Any call to insort_{left,right} with a non-list leaked a reference to None Michael W. Hudson <mwh@python.net> parents: 31353 diff changeset	190 result = PyObject_CallMethod(list, "insert", "iO",
daec2d311def Any call to insort_{left,right} with a non-list leaked a reference to None Michael W. Hudson <mwh@python.net> parents: 31353 diff changeset	191 index, item);
daec2d311def Any call to insort_{left,right} with a non-list leaked a reference to None Michael W. Hudson <mwh@python.net> parents: 31353 diff changeset	192 if (result == NULL)
31353 ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	193 return NULL;
32898 daec2d311def Any call to insort_{left,right} with a non-list leaked a reference to None Michael W. Hudson <mwh@python.net> parents: 31353 diff changeset	194 Py_DECREF(result);
31353 ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	195 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	196
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	197 Py_RETURN_NONE;
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	198 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	199
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	200 PyDoc_STRVAR(insort_left_doc,
35699 3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args Raymond Hettinger <python@rcn.com> parents: 32898 diff changeset	201 "insort_left(a, x[, lo[, hi]])\n\
31353 ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	202 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	203 Insert item x in list a, and keep it sorted assuming a is sorted.\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	204 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	205 If x is already in a, insert it to the left of the leftmost x.\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	206 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	207 Optional args lo (default 0) and hi (default len(a)) bound the\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	208 slice of a to be searched.\n");
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	209
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	210 PyDoc_STRVAR(bisect_doc, "Alias for bisect_right().\n");
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	211 PyDoc_STRVAR(insort_doc, "Alias for insort_right().\n");
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	212
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	213 static PyMethodDef bisect_methods[] = {
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	214 {"bisect_right", (PyCFunction)bisect_right,
35699 3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args Raymond Hettinger <python@rcn.com> parents: 32898 diff changeset	215 METH_VARARGS\|METH_KEYWORDS, bisect_right_doc},
31353 ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	216 {"bisect", (PyCFunction)bisect_right,
35699 3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args Raymond Hettinger <python@rcn.com> parents: 32898 diff changeset	217 METH_VARARGS\|METH_KEYWORDS, bisect_doc},
31353 ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	218 {"insort_right", (PyCFunction)insort_right,
35699 3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args Raymond Hettinger <python@rcn.com> parents: 32898 diff changeset	219 METH_VARARGS\|METH_KEYWORDS, insort_right_doc},
31353 ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	220 {"insort", (PyCFunction)insort_right,
35699 3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args Raymond Hettinger <python@rcn.com> parents: 32898 diff changeset	221 METH_VARARGS\|METH_KEYWORDS, insort_doc},
31353 ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	222 {"bisect_left", (PyCFunction)bisect_left,
35699 3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args Raymond Hettinger <python@rcn.com> parents: 32898 diff changeset	223 METH_VARARGS\|METH_KEYWORDS, bisect_left_doc},
31353 ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	224 {"insort_left", (PyCFunction)insort_left,
35699 3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args Raymond Hettinger <python@rcn.com> parents: 32898 diff changeset	225 METH_VARARGS\|METH_KEYWORDS, insort_left_doc},
31353 ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	226 {NULL, NULL} /* sentinel */
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	227 };
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	228
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	229 PyDoc_STRVAR(module_doc,
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	230 "Bisection algorithms.\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	231 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	232 This module provides support for maintaining a list in sorted order without\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	233 having to sort the list after each insertion. For long lists of items with\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	234 expensive comparison operations, this can be an improvement over the more\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	235 common approach.\n");
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	236
47580 94f64f11fdd0 Implement PEP 3121: new module initialization and finalization API. Martin v. Löwis <martin@v.loewis.de> parents: 44099 diff changeset	237
94f64f11fdd0 Implement PEP 3121: new module initialization and finalization API. Martin v. Löwis <martin@v.loewis.de> parents: 44099 diff changeset	238 static struct PyModuleDef _bisectmodule = {
94f64f11fdd0 Implement PEP 3121: new module initialization and finalization API. Martin v. Löwis <martin@v.loewis.de> parents: 44099 diff changeset	239 PyModuleDef_HEAD_INIT,
94f64f11fdd0 Implement PEP 3121: new module initialization and finalization API. Martin v. Löwis <martin@v.loewis.de> parents: 44099 diff changeset	240 "_bisect",
94f64f11fdd0 Implement PEP 3121: new module initialization and finalization API. Martin v. Löwis <martin@v.loewis.de> parents: 44099 diff changeset	241 module_doc,
94f64f11fdd0 Implement PEP 3121: new module initialization and finalization API. Martin v. Löwis <martin@v.loewis.de> parents: 44099 diff changeset	242 -1,
94f64f11fdd0 Implement PEP 3121: new module initialization and finalization API. Martin v. Löwis <martin@v.loewis.de> parents: 44099 diff changeset	243 bisect_methods,
94f64f11fdd0 Implement PEP 3121: new module initialization and finalization API. Martin v. Löwis <martin@v.loewis.de> parents: 44099 diff changeset	244 NULL,
94f64f11fdd0 Implement PEP 3121: new module initialization and finalization API. Martin v. Löwis <martin@v.loewis.de> parents: 44099 diff changeset	245 NULL,
94f64f11fdd0 Implement PEP 3121: new module initialization and finalization API. Martin v. Löwis <martin@v.loewis.de> parents: 44099 diff changeset	246 NULL,
94f64f11fdd0 Implement PEP 3121: new module initialization and finalization API. Martin v. Löwis <martin@v.loewis.de> parents: 44099 diff changeset	247 NULL
94f64f11fdd0 Implement PEP 3121: new module initialization and finalization API. Martin v. Löwis <martin@v.loewis.de> parents: 44099 diff changeset	248 };
94f64f11fdd0 Implement PEP 3121: new module initialization and finalization API. Martin v. Löwis <martin@v.loewis.de> parents: 44099 diff changeset	249
31353 ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	250 PyMODINIT_FUNC
47580 94f64f11fdd0 Implement PEP 3121: new module initialization and finalization API. Martin v. Löwis <martin@v.loewis.de> parents: 44099 diff changeset	251 PyInit__bisect(void)
31353 ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	252 {
47580 94f64f11fdd0 Implement PEP 3121: new module initialization and finalization API. Martin v. Löwis <martin@v.loewis.de> parents: 44099 diff changeset	253 return PyModule_Create(&_bisectmodule);
31353 ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	254 }

Mercurial > cpython-lru_cache-weakref

annotate Modules/_bisectmodule.c @ 58689:514b56efd89a 3.1