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

annotate Modules/_bisectmodule.c @ 49955:878d40468c4e legacy-trunk

Issue #4384: Added logging integration with warnings module using captureWarnings(). This change includes a NullHandler which does nothing; it will be of use to library developers who want to avoid the "No handlers could be found for logger XXX" message which can appear if the library user doesn't configure logging.

author	Vinay Sajip <vinay_sajip@yahoo.co.uk>
date	Wed, 03 Dec 2008 23:22:58 +0000
parents	82ccc7e77ec5
children	e38335d4df91 982eec9a8c28

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
48064 07b89653145e Finish conversion from int to Py_ssize_t. Raymond Hettinger <python@rcn.com> parents: 47919 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
47919 8e7383cbe56e Issue 3301: Bisect functions behaved badly when lo was negative. Raymond Hettinger <python@rcn.com> parents: 36684 diff changeset	14 if (lo < 0) {
8e7383cbe56e Issue 3301: Bisect functions behaved badly when lo was negative. Raymond Hettinger <python@rcn.com> parents: 36684 diff changeset	15 PyErr_SetString(PyExc_ValueError, "lo must be non-negative");
8e7383cbe56e Issue 3301: Bisect functions behaved badly when lo was negative. Raymond Hettinger <python@rcn.com> parents: 36684 diff changeset	16 return -1;
8e7383cbe56e Issue 3301: Bisect functions behaved badly when lo was negative. Raymond Hettinger <python@rcn.com> parents: 36684 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;
48064 07b89653145e Finish conversion from int to Py_ssize_t. Raymond Hettinger <python@rcn.com> parents: 47919 diff changeset	44 Py_ssize_t lo = 0;
07b89653145e Finish conversion from int to Py_ssize_t. Raymond Hettinger <python@rcn.com> parents: 47919 diff changeset	45 Py_ssize_t hi = -1;
07b89653145e Finish conversion from int to Py_ssize_t. Raymond Hettinger <python@rcn.com> parents: 47919 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
48064 07b89653145e Finish conversion from int to Py_ssize_t. Raymond Hettinger <python@rcn.com> parents: 47919 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;
48064 07b89653145e Finish conversion from int to Py_ssize_t. Raymond Hettinger <python@rcn.com> parents: 47919 diff changeset	55 return PyInt_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;
48064 07b89653145e Finish conversion from int to Py_ssize_t. Raymond Hettinger <python@rcn.com> parents: 47919 diff changeset	74 Py_ssize_t lo = 0;
07b89653145e Finish conversion from int to Py_ssize_t. Raymond Hettinger <python@rcn.com> parents: 47919 diff changeset	75 Py_ssize_t hi = -1;
07b89653145e Finish conversion from int to Py_ssize_t. Raymond Hettinger <python@rcn.com> parents: 47919 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
48064 07b89653145e Finish conversion from int to Py_ssize_t. Raymond Hettinger <python@rcn.com> parents: 47919 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;
49677 82ccc7e77ec5 Merged revisions 66801,66803-66804,66813,66854-66856,66866,66870-66872,66874,66887,66903,66905,66911,66913,66927,66932,66938,66942,66962,66964,66973-66974,66977,66992,66998-66999,67002,67005,67007,67028,67040-67041,67044,67070,67089,67091,67101,67117-67119,67123-67124 via svnmerge from Georg Brandl <georg@python.org> parents: 48064 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 {
48064 07b89653145e Finish conversion from int to Py_ssize_t. Raymond Hettinger <python@rcn.com> parents: 47919 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
48064 07b89653145e Finish conversion from int to Py_ssize_t. Raymond Hettinger <python@rcn.com> parents: 47919 diff changeset	109 static Py_ssize_t
07b89653145e Finish conversion from int to Py_ssize_t. Raymond Hettinger <python@rcn.com> parents: 47919 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;
48064 07b89653145e Finish conversion from int to Py_ssize_t. Raymond Hettinger <python@rcn.com> parents: 47919 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
47919 8e7383cbe56e Issue 3301: Bisect functions behaved badly when lo was negative. Raymond Hettinger <python@rcn.com> parents: 36684 diff changeset	115 if (lo < 0) {
8e7383cbe56e Issue 3301: Bisect functions behaved badly when lo was negative. Raymond Hettinger <python@rcn.com> parents: 36684 diff changeset	116 PyErr_SetString(PyExc_ValueError, "lo must be non-negative");
8e7383cbe56e Issue 3301: Bisect functions behaved badly when lo was negative. Raymond Hettinger <python@rcn.com> parents: 36684 diff changeset	117 return -1;
8e7383cbe56e Issue 3301: Bisect functions behaved badly when lo was negative. Raymond Hettinger <python@rcn.com> parents: 36684 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;
48064 07b89653145e Finish conversion from int to Py_ssize_t. Raymond Hettinger <python@rcn.com> parents: 47919 diff changeset	145 Py_ssize_t lo = 0;
07b89653145e Finish conversion from int to Py_ssize_t. Raymond Hettinger <python@rcn.com> parents: 47919 diff changeset	146 Py_ssize_t hi = -1;
07b89653145e Finish conversion from int to Py_ssize_t. Raymond Hettinger <python@rcn.com> parents: 47919 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
48064 07b89653145e Finish conversion from int to Py_ssize_t. Raymond Hettinger <python@rcn.com> parents: 47919 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;
48064 07b89653145e Finish conversion from int to Py_ssize_t. Raymond Hettinger <python@rcn.com> parents: 47919 diff changeset	156 return PyInt_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;
48064 07b89653145e Finish conversion from int to Py_ssize_t. Raymond Hettinger <python@rcn.com> parents: 47919 diff changeset	175 Py_ssize_t lo = 0;
07b89653145e Finish conversion from int to Py_ssize_t. Raymond Hettinger <python@rcn.com> parents: 47919 diff changeset	176 Py_ssize_t hi = -1;
07b89653145e Finish conversion from int to Py_ssize_t. Raymond Hettinger <python@rcn.com> parents: 47919 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
48064 07b89653145e Finish conversion from int to Py_ssize_t. Raymond Hettinger <python@rcn.com> parents: 47919 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;
49677 82ccc7e77ec5 Merged revisions 66801,66803-66804,66813,66854-66856,66866,66870-66872,66874,66887,66903,66905,66911,66913,66927,66932,66938,66942,66962,66964,66973-66974,66977,66992,66998-66999,67002,67005,67007,67028,67040-67041,67044,67070,67089,67091,67101,67117-67119,67123-67124 via svnmerge from Georg Brandl <georg@python.org> parents: 48064 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
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	237 PyMODINIT_FUNC
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	238 init_bisect(void)
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	239 {
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	240 PyObject *m;
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	241
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	242 m = Py_InitModule3("_bisect", bisect_methods, module_doc);
ed20259a1ea5 SF Patch #864863: Bisect C implementation Raymond Hettinger <python@rcn.com> parents: diff changeset	243 }

Mercurial > cpython-lru_cache-weakref

annotate Modules/_bisectmodule.c @ 49955:878d40468c4e legacy-trunk