Mercurial > cpython-lru_cache-weakref

annotate Modules/_bisectmodule.c @ 80661:94de77bd0b4b 2.7

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Issue #16194: document imp.load_dynamic problems when read several extension modules from the same binary object file.
author Andrew Svetlov <andrew.svetlov@gmail.com>
date Thu, 29 Nov 2012 19:51:28 +0200
parents e957b93571a8
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
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 {
61465
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
11 PyObject *litem;
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
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
61465
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
14 if (lo < 0) {
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
15 PyErr_SetString(PyExc_ValueError, "lo must be non-negative");
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
16 return -1;
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
17 }
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
18 if (hi == -1) {
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
19 hi = PySequence_Size(list);
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
20 if (hi < 0)
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
21 return -1;
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
22 }
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
23 while (lo < hi) {
76325
709af2d0e862 Issue 13496: Fix bisect.bisect overflow bug for large collections.
Mark Dickinson <mdickinson@enthought.com>
parents: 68256
diff changeset
24 /* The (size_t)cast ensures that the addition and subsequent division
709af2d0e862 Issue 13496: Fix bisect.bisect overflow bug for large collections.
Mark Dickinson <mdickinson@enthought.com>
parents: 68256
diff changeset
25 are performed as unsigned operations, avoiding difficulties from
709af2d0e862 Issue 13496: Fix bisect.bisect overflow bug for large collections.
Mark Dickinson <mdickinson@enthought.com>
parents: 68256
diff changeset
26 signed overflow. (See issue 13496.) */
709af2d0e862 Issue 13496: Fix bisect.bisect overflow bug for large collections.
Mark Dickinson <mdickinson@enthought.com>
parents: 68256
diff changeset
27 mid = ((size_t)lo + hi) / 2;
61465
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
28 litem = PySequence_GetItem(list, mid);
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
29 if (litem == NULL)
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
30 return -1;
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
31 res = PyObject_RichCompareBool(item, litem, Py_LT);
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
32 Py_DECREF(litem);
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
33 if (res < 0)
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
34 return -1;
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
35 if (res)
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
36 hi = mid;
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
37 else
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
38 lo = mid + 1;
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
39 }
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
40 return lo;
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
41 }
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 static PyObject *
35699
3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args
Raymond Hettinger <python@rcn.com>
parents: 32898
diff changeset
44 bisect_right(PyObject *self, PyObject *args, PyObject *kw)
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
45 {
61465
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
46 PyObject *list, *item;
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
47 Py_ssize_t lo = 0;
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
48 Py_ssize_t hi = -1;
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
49 Py_ssize_t index;
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
50 static char *keywords[] = {"a", "x", "lo", "hi", NULL};
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
51
61465
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
52 if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn:bisect_right",
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
53 keywords, &list, &item, &lo, &hi))
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
54 return NULL;
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
55 index = internal_bisect_right(list, item, lo, hi);
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
56 if (index < 0)
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
57 return NULL;
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
58 return PyInt_FromSsize_t(index);
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
59 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
60
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
61 PyDoc_STRVAR(bisect_right_doc,
76572
097b72d73594 Improve docstring
Raymond Hettinger <python@rcn.com>
parents: 76326
diff changeset
62 "bisect(a, x[, lo[, hi]]) -> index\n\
097b72d73594 Improve docstring
Raymond Hettinger <python@rcn.com>
parents: 76326
diff changeset
63 bisect_right(a, x[, lo[, hi]]) -> index\n\
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
64 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
65 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
66 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
67 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
68 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
69 beyond the rightmost x already there\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
70 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
71 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
72 slice of a to be searched.\n");
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
73
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
74 static PyObject *
35699
3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args
Raymond Hettinger <python@rcn.com>
parents: 32898
diff changeset
75 insort_right(PyObject *self, PyObject *args, PyObject *kw)
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
76 {
61465
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
77 PyObject *list, *item, *result;
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
78 Py_ssize_t lo = 0;
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
79 Py_ssize_t hi = -1;
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
80 Py_ssize_t index;
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
81 static char *keywords[] = {"a", "x", "lo", "hi", NULL};
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
82
61465
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
83 if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn:insort_right",
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
84 keywords, &list, &item, &lo, &hi))
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
85 return NULL;
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
86 index = internal_bisect_right(list, item, lo, hi);
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
87 if (index < 0)
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
88 return NULL;
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
89 if (PyList_CheckExact(list)) {
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
90 if (PyList_Insert(list, index, item) < 0)
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
91 return NULL;
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
92 } else {
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
93 result = PyObject_CallMethod(list, "insert", "nO",
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
94 index, item);
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
95 if (result == NULL)
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
96 return NULL;
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
97 Py_DECREF(result);
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
98 }
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
99
61465
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
100 Py_RETURN_NONE;
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
101 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
102
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
103 PyDoc_STRVAR(insort_right_doc,
76572
097b72d73594 Improve docstring
Raymond Hettinger <python@rcn.com>
parents: 76326
diff changeset
104 "insort(a, x[, lo[, hi]])\n\
097b72d73594 Improve docstring
Raymond Hettinger <python@rcn.com>
parents: 76326
diff changeset
105 insort_right(a, x[, lo[, hi]])\n\
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
106 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
107 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
108 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
109 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
110 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
111 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
112 slice of a to be searched.\n");
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
113
48064
07b89653145e Finish conversion from int to Py_ssize_t.
Raymond Hettinger <python@rcn.com>
parents: 47919
diff changeset
114 static Py_ssize_t
07b89653145e Finish conversion from int to Py_ssize_t.
Raymond Hettinger <python@rcn.com>
parents: 47919
diff changeset
115 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
116 {
61465
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
117 PyObject *litem;
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
118 Py_ssize_t mid, res;
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
119
61465
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
120 if (lo < 0) {
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
121 PyErr_SetString(PyExc_ValueError, "lo must be non-negative");
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
122 return -1;
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
123 }
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
124 if (hi == -1) {
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
125 hi = PySequence_Size(list);
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
126 if (hi < 0)
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
127 return -1;
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
128 }
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
129 while (lo < hi) {
76325
709af2d0e862 Issue 13496: Fix bisect.bisect overflow bug for large collections.
Mark Dickinson <mdickinson@enthought.com>
parents: 68256
diff changeset
130 /* The (size_t)cast ensures that the addition and subsequent division
709af2d0e862 Issue 13496: Fix bisect.bisect overflow bug for large collections.
Mark Dickinson <mdickinson@enthought.com>
parents: 68256
diff changeset
131 are performed as unsigned operations, avoiding difficulties from
709af2d0e862 Issue 13496: Fix bisect.bisect overflow bug for large collections.
Mark Dickinson <mdickinson@enthought.com>
parents: 68256
diff changeset
132 signed overflow. (See issue 13496.) */
709af2d0e862 Issue 13496: Fix bisect.bisect overflow bug for large collections.
Mark Dickinson <mdickinson@enthought.com>
parents: 68256
diff changeset
133 mid = ((size_t)lo + hi) / 2;
61465
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
134 litem = PySequence_GetItem(list, mid);
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
135 if (litem == NULL)
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
136 return -1;
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
137 res = PyObject_RichCompareBool(litem, item, Py_LT);
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
138 Py_DECREF(litem);
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
139 if (res < 0)
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
140 return -1;
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
141 if (res)
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
142 lo = mid + 1;
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
143 else
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
144 hi = mid;
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
145 }
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
146 return lo;
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
147 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
148
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
149 static PyObject *
35699
3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args
Raymond Hettinger <python@rcn.com>
parents: 32898
diff changeset
150 bisect_left(PyObject *self, PyObject *args, PyObject *kw)
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
151 {
61465
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
152 PyObject *list, *item;
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
153 Py_ssize_t lo = 0;
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
154 Py_ssize_t hi = -1;
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
155 Py_ssize_t index;
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
156 static char *keywords[] = {"a", "x", "lo", "hi", NULL};
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
157
61465
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
158 if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn:bisect_left",
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
159 keywords, &list, &item, &lo, &hi))
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
160 return NULL;
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
161 index = internal_bisect_left(list, item, lo, hi);
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
162 if (index < 0)
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
163 return NULL;
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
164 return PyInt_FromSsize_t(index);
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
165 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
166
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
167 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
168 "bisect_left(a, x[, lo[, hi]]) -> index\n\
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
169 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
170 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
171 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
172 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
173 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
174 before the leftmost x already there.\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
175 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
176 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
177 slice of a to be searched.\n");
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
178
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
179 static PyObject *
35699
3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args
Raymond Hettinger <python@rcn.com>
parents: 32898
diff changeset
180 insort_left(PyObject *self, PyObject *args, PyObject *kw)
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
181 {
61465
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
182 PyObject *list, *item, *result;
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
183 Py_ssize_t lo = 0;
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
184 Py_ssize_t hi = -1;
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
185 Py_ssize_t index;
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
186 static char *keywords[] = {"a", "x", "lo", "hi", NULL};
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
187
61465
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
188 if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn:insort_left",
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
189 keywords, &list, &item, &lo, &hi))
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
190 return NULL;
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
191 index = internal_bisect_left(list, item, lo, hi);
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
192 if (index < 0)
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
193 return NULL;
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
194 if (PyList_CheckExact(list)) {
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
195 if (PyList_Insert(list, index, item) < 0)
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
196 return NULL;
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
197 } else {
76994
e957b93571a8 Issue #14829: Fix bisect issues under 64-bit Windows.
Antoine Pitrou <solipsis@pitrou.net>
parents: 76572
diff changeset
198 result = PyObject_CallMethod(list, "insert", "nO",
61465
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
199 index, item);
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
200 if (result == NULL)
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
201 return NULL;
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
202 Py_DECREF(result);
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
203 }
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
204
61465
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
205 Py_RETURN_NONE;
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
206 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
207
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
208 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
209 "insort_left(a, x[, lo[, hi]])\n\
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
210 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
211 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
212 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
213 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
214 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
215 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
216 slice of a to be searched.\n");
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
217
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
218 static PyMethodDef bisect_methods[] = {
61465
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
219 {"bisect_right", (PyCFunction)bisect_right,
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
220 METH_VARARGS|METH_KEYWORDS, bisect_right_doc},
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
221 {"bisect", (PyCFunction)bisect_right,
76572
097b72d73594 Improve docstring
Raymond Hettinger <python@rcn.com>
parents: 76326
diff changeset
222 METH_VARARGS|METH_KEYWORDS, bisect_right_doc},
61465
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
223 {"insort_right", (PyCFunction)insort_right,
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
224 METH_VARARGS|METH_KEYWORDS, insort_right_doc},
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
225 {"insort", (PyCFunction)insort_right,
76572
097b72d73594 Improve docstring
Raymond Hettinger <python@rcn.com>
parents: 76326
diff changeset
226 METH_VARARGS|METH_KEYWORDS, insort_right_doc},
61465
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
227 {"bisect_left", (PyCFunction)bisect_left,
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
228 METH_VARARGS|METH_KEYWORDS, bisect_left_doc},
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
229 {"insort_left", (PyCFunction)insort_left,
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
230 METH_VARARGS|METH_KEYWORDS, insort_left_doc},
e38335d4df91 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49677
diff changeset
231 {NULL, NULL} /* sentinel */
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
232 };
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
233
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
234 PyDoc_STRVAR(module_doc,
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
235 "Bisection algorithms.\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
236 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
237 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
238 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
239 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
240 common approach.\n");
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 PyMODINIT_FUNC
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
243 init_bisect(void)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
244 {
61463
fd25030223b0 Untabify C files. Will watch buildbots.
Antoine Pitrou <solipsis@pitrou.net>
parents: 61193
diff changeset
245 Py_InitModule3("_bisect", bisect_methods, module_doc);
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
246 }