Mercurial > cpython-lru_cache-weakref
annotate Modules/_bisectmodule.c @ 73323:dad02a080bbc
Improve byte-compilation in packaging to be independent of -O or -B.
The code I fixed to comply with PEP 3147 still had one bug: When run
under python -O, some paths for pyc files would be pyo, because I called
imp.cache_from_source without explicit debug_override argument in some
places, and under -O that would return .pyo (this is well explained in
the imp docs). Now all code (util.byte_compile, build_py, install_lib)
can create .pyo files according to options given by users,
without interference from the calling Python’s own optimize mode.
On a related topic, I also removed the code that prevented byte
compilation under python -B. The rationale is that packaging gives
control over the creation of pyc files to the user with its own explicit
option, and the behavior should not be changed if the calling Python
happens to run with -B for whatever reason. I will argue that this is a
bug fix and ask to be allowed to backport this change to distutils.
Finally, I moved one nugget of information about the --compile and
--optimize options from the source into the doc. It clears up a
misunderstanding that I (and maybe other people) had.
| author | Éric Araujo <merwok@netwok.org> |
|---|---|
| date | Thu, 03 Nov 2011 05:08:28 +0100 |
| parents | 7109f31300fb |
| children | 1a9252280f07 |
| 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 { |
|
61466
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
11 PyObject *litem; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
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 |
|
61466
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
14 if (lo < 0) { |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
15 PyErr_SetString(PyExc_ValueError, "lo must be non-negative"); |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
16 return -1; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
17 } |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
18 if (hi == -1) { |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
19 hi = PySequence_Size(list); |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
20 if (hi < 0) |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
21 return -1; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
22 } |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
23 while (lo < hi) { |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
24 mid = (lo + hi) / 2; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
25 litem = PySequence_GetItem(list, mid); |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
26 if (litem == NULL) |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
27 return -1; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
28 res = PyObject_RichCompareBool(item, litem, Py_LT); |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
29 Py_DECREF(litem); |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
30 if (res < 0) |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
31 return -1; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
32 if (res) |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
33 hi = mid; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
34 else |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
35 lo = mid + 1; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
36 } |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
37 return lo; |
|
31353
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 { |
|
61466
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
43 PyObject *list, *item; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
44 Py_ssize_t lo = 0; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
45 Py_ssize_t hi = -1; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
46 Py_ssize_t index; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
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 |
|
61466
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
49 if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn:bisect_right", |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
50 keywords, &list, &item, &lo, &hi)) |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
51 return NULL; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
52 index = internal_bisect_right(list, item, lo, hi); |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
53 if (index < 0) |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
54 return NULL; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
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 { |
|
61466
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
73 PyObject *list, *item, *result; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
74 Py_ssize_t lo = 0; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
75 Py_ssize_t hi = -1; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
76 Py_ssize_t index; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
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 |
|
61466
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
79 if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn:insort_right", |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
80 keywords, &list, &item, &lo, &hi)) |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
81 return NULL; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
82 index = internal_bisect_right(list, item, lo, hi); |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
83 if (index < 0) |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
84 return NULL; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
85 if (PyList_CheckExact(list)) { |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
86 if (PyList_Insert(list, index, item) < 0) |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
87 return NULL; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
88 } else { |
|
72925
7109f31300fb
Rename _Py_identifier to _Py_IDENTIFIER.
Martin v. Löwis <martin@v.loewis.de>
parents:
72835
diff
changeset
|
89 _Py_IDENTIFIER(insert); |
|
72835
5e33219492bc
Add API for static strings, primarily good for identifiers.
Martin v. Löwis <martin@v.loewis.de>
parents:
64339
diff
changeset
|
90 |
|
5e33219492bc
Add API for static strings, primarily good for identifiers.
Martin v. Löwis <martin@v.loewis.de>
parents:
64339
diff
changeset
|
91 result = _PyObject_CallMethodId(list, &PyId_insert, "nO", index, item); |
|
61466
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
92 if (result == NULL) |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
93 return NULL; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
94 Py_DECREF(result); |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
95 } |
|
31353
ed20259a1ea5
SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff
changeset
|
96 |
|
61466
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
97 Py_RETURN_NONE; |
|
31353
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 |
|
ed20259a1ea5
SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff
changeset
|
100 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
|
101 "insort_right(a, x[, lo[, hi]])\n\ |
|
31353
ed20259a1ea5
SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff
changeset
|
102 \n\ |
|
ed20259a1ea5
SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff
changeset
|
103 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
|
104 \n\ |
|
ed20259a1ea5
SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff
changeset
|
105 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
|
106 \n\ |
|
ed20259a1ea5
SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff
changeset
|
107 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
|
108 slice of a to be searched.\n"); |
|
ed20259a1ea5
SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff
changeset
|
109 |
|
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
|
110 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
|
111 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
|
112 { |
|
61466
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
113 PyObject *litem; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
114 Py_ssize_t mid, res; |
|
31353
ed20259a1ea5
SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff
changeset
|
115 |
|
61466
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
116 if (lo < 0) { |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
117 PyErr_SetString(PyExc_ValueError, "lo must be non-negative"); |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
118 return -1; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
119 } |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
120 if (hi == -1) { |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
121 hi = PySequence_Size(list); |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
122 if (hi < 0) |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
123 return -1; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
124 } |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
125 while (lo < hi) { |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
126 mid = (lo + hi) / 2; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
127 litem = PySequence_GetItem(list, mid); |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
128 if (litem == NULL) |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
129 return -1; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
130 res = PyObject_RichCompareBool(litem, item, Py_LT); |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
131 Py_DECREF(litem); |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
132 if (res < 0) |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
133 return -1; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
134 if (res) |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
135 lo = mid + 1; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
136 else |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
137 hi = mid; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
138 } |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
139 return lo; |
|
31353
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 |
|
ed20259a1ea5
SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff
changeset
|
142 static PyObject * |
|
35699
3572249c1e77
SF #1313496: bisect C replacement doesn't accept named args
Raymond Hettinger <python@rcn.com>
parents:
32898
diff
changeset
|
143 bisect_left(PyObject *self, PyObject *args, PyObject *kw) |
|
31353
ed20259a1ea5
SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff
changeset
|
144 { |
|
61466
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
145 PyObject *list, *item; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
146 Py_ssize_t lo = 0; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
147 Py_ssize_t hi = -1; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
148 Py_ssize_t index; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
149 static char *keywords[] = {"a", "x", "lo", "hi", NULL}; |
|
31353
ed20259a1ea5
SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff
changeset
|
150 |
|
61466
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
151 if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn:bisect_left", |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
152 keywords, &list, &item, &lo, &hi)) |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
153 return NULL; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
154 index = internal_bisect_left(list, item, lo, hi); |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
155 if (index < 0) |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
156 return NULL; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
157 return PyLong_FromSsize_t(index); |
|
31353
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 |
|
ed20259a1ea5
SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff
changeset
|
160 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
|
161 "bisect_left(a, x[, lo[, hi]]) -> index\n\ |
|
31353
ed20259a1ea5
SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff
changeset
|
162 \n\ |
|
ed20259a1ea5
SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff
changeset
|
163 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
|
164 \n\ |
|
ed20259a1ea5
SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff
changeset
|
165 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
|
166 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
|
167 before the leftmost x already there.\n\ |
|
ed20259a1ea5
SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff
changeset
|
168 \n\ |
|
ed20259a1ea5
SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff
changeset
|
169 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
|
170 slice of a to be searched.\n"); |
|
ed20259a1ea5
SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff
changeset
|
171 |
|
ed20259a1ea5
SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff
changeset
|
172 static PyObject * |
|
35699
3572249c1e77
SF #1313496: bisect C replacement doesn't accept named args
Raymond Hettinger <python@rcn.com>
parents:
32898
diff
changeset
|
173 insort_left(PyObject *self, PyObject *args, PyObject *kw) |
|
31353
ed20259a1ea5
SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff
changeset
|
174 { |
|
61466
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
175 PyObject *list, *item, *result; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
176 Py_ssize_t lo = 0; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
177 Py_ssize_t hi = -1; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
178 Py_ssize_t index; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
179 static char *keywords[] = {"a", "x", "lo", "hi", NULL}; |
|
31353
ed20259a1ea5
SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff
changeset
|
180 |
|
61466
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
181 if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn:insort_left", |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
182 keywords, &list, &item, &lo, &hi)) |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
183 return NULL; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
184 index = internal_bisect_left(list, item, lo, hi); |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
185 if (index < 0) |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
186 return NULL; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
187 if (PyList_CheckExact(list)) { |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
188 if (PyList_Insert(list, index, item) < 0) |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
189 return NULL; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
190 } else { |
|
72925
7109f31300fb
Rename _Py_identifier to _Py_IDENTIFIER.
Martin v. Löwis <martin@v.loewis.de>
parents:
72835
diff
changeset
|
191 _Py_IDENTIFIER(insert); |
|
72835
5e33219492bc
Add API for static strings, primarily good for identifiers.
Martin v. Löwis <martin@v.loewis.de>
parents:
64339
diff
changeset
|
192 |
|
5e33219492bc
Add API for static strings, primarily good for identifiers.
Martin v. Löwis <martin@v.loewis.de>
parents:
64339
diff
changeset
|
193 result = _PyObject_CallMethodId(list, &PyId_insert, "iO", index, item); |
|
61466
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
194 if (result == NULL) |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
195 return NULL; |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
196 Py_DECREF(result); |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
197 } |
|
31353
ed20259a1ea5
SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff
changeset
|
198 |
|
61466
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
199 Py_RETURN_NONE; |
|
31353
ed20259a1ea5
SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff
changeset
|
200 } |
|
ed20259a1ea5
SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff
changeset
|
201 |
|
ed20259a1ea5
SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff
changeset
|
202 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
|
203 "insort_left(a, x[, lo[, hi]])\n\ |
|
31353
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 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
|
206 \n\ |
|
ed20259a1ea5
SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff
changeset
|
207 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
|
208 \n\ |
|
ed20259a1ea5
SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff
changeset
|
209 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
|
210 slice of a to be searched.\n"); |
|
ed20259a1ea5
SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff
changeset
|
211 |
|
ed20259a1ea5
SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff
changeset
|
212 PyDoc_STRVAR(bisect_doc, "Alias for bisect_right().\n"); |
|
ed20259a1ea5
SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff
changeset
|
213 PyDoc_STRVAR(insort_doc, "Alias for insort_right().\n"); |
|
ed20259a1ea5
SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff
changeset
|
214 |
|
ed20259a1ea5
SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff
changeset
|
215 static PyMethodDef bisect_methods[] = { |
|
61466
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
216 {"bisect_right", (PyCFunction)bisect_right, |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
217 METH_VARARGS|METH_KEYWORDS, bisect_right_doc}, |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
218 {"bisect", (PyCFunction)bisect_right, |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
219 METH_VARARGS|METH_KEYWORDS, bisect_doc}, |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
220 {"insort_right", (PyCFunction)insort_right, |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
221 METH_VARARGS|METH_KEYWORDS, insort_right_doc}, |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
222 {"insort", (PyCFunction)insort_right, |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
223 METH_VARARGS|METH_KEYWORDS, insort_doc}, |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
224 {"bisect_left", (PyCFunction)bisect_left, |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
225 METH_VARARGS|METH_KEYWORDS, bisect_left_doc}, |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
226 {"insort_left", (PyCFunction)insort_left, |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
227 METH_VARARGS|METH_KEYWORDS, insort_left_doc}, |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
228 {NULL, NULL} /* sentinel */ |
|
31353
ed20259a1ea5
SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff
changeset
|
229 }; |
|
ed20259a1ea5
SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff
changeset
|
230 |
|
ed20259a1ea5
SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff
changeset
|
231 PyDoc_STRVAR(module_doc, |
|
ed20259a1ea5
SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff
changeset
|
232 "Bisection algorithms.\n\ |
|
ed20259a1ea5
SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff
changeset
|
233 \n\ |
|
ed20259a1ea5
SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff
changeset
|
234 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
|
235 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
|
236 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
|
237 common approach.\n"); |
|
ed20259a1ea5
SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff
changeset
|
238 |
|
47580
94f64f11fdd0
Implement PEP 3121: new module initialization and finalization API.
Martin v. Löwis <martin@v.loewis.de>
parents:
44099
diff
changeset
|
239 |
|
94f64f11fdd0
Implement PEP 3121: new module initialization and finalization API.
Martin v. Löwis <martin@v.loewis.de>
parents:
44099
diff
changeset
|
240 static struct PyModuleDef _bisectmodule = { |
|
61466
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
241 PyModuleDef_HEAD_INIT, |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
242 "_bisect", |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
243 module_doc, |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
244 -1, |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
245 bisect_methods, |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
246 NULL, |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
247 NULL, |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
248 NULL, |
|
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
249 NULL |
|
47580
94f64f11fdd0
Implement PEP 3121: new module initialization and finalization API.
Martin v. Löwis <martin@v.loewis.de>
parents:
44099
diff
changeset
|
250 }; |
|
94f64f11fdd0
Implement PEP 3121: new module initialization and finalization API.
Martin v. Löwis <martin@v.loewis.de>
parents:
44099
diff
changeset
|
251 |
|
31353
ed20259a1ea5
SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff
changeset
|
252 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
|
253 PyInit__bisect(void) |
|
31353
ed20259a1ea5
SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff
changeset
|
254 { |
|
61466
cab14be0ada1
Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents:
49493
diff
changeset
|
255 return PyModule_Create(&_bisectmodule); |
|
31353
ed20259a1ea5
SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff
changeset
|
256 } |
