Mercurial > cpython-lru_cache-weakref

annotate Modules/_bisectmodule.c @ 66978:aed2bbafa550 3.1

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Blocked revisions 87324 via svnmerge ........ r87324 | r.david.murray | 2010-12-16 14:08:51 -0500 (Thu, 16 Dec 2010) | 9 lines #10719: restore messages generated on invalid compileall args Before the introduction of filename arguments to compileall it gave semi useful messages about not being able to 'list' names that weren't valid directories. This fix restores that behavior. In addition to the test for this case, the patch also adds a test for the default behavior of compileall when no arguments are provided, and fixes a bug in one of the previously added tests. ........
author R. David Murray <rdmurray@bitdance.com>
date Thu, 16 Dec 2010 19:10:16 +0000
parents f197407bdba2
children 9fd326af62d4
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
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 {
61467
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
11 PyObject *litem;
f197407bdba2 Recorded merge of revisions 81032 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
61467
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
14 if (lo < 0) {
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
15 PyErr_SetString(PyExc_ValueError, "lo must be non-negative");
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
16 return -1;
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
17 }
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
18 if (hi == -1) {
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
19 hi = PySequence_Size(list);
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
20 if (hi < 0)
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
21 return -1;
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
22 }
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
23 while (lo < hi) {
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
24 mid = (lo + hi) / 2;
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
25 litem = PySequence_GetItem(list, mid);
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
26 if (litem == NULL)
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
27 return -1;
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
28 res = PyObject_RichCompareBool(item, litem, Py_LT);
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
29 Py_DECREF(litem);
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
30 if (res < 0)
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
31 return -1;
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
32 if (res)
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
33 hi = mid;
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
34 else
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
35 lo = mid + 1;
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
36 }
f197407bdba2 Recorded merge of revisions 81032 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 {
61467
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
43 PyObject *list, *item;
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
44 Py_ssize_t lo = 0;
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
45 Py_ssize_t hi = -1;
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
46 Py_ssize_t index;
f197407bdba2 Recorded merge of revisions 81032 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
61467
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
49 if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn:bisect_right",
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
50 keywords, &list, &item, &lo, &hi))
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
51 return NULL;
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
52 index = internal_bisect_right(list, item, lo, hi);
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
53 if (index < 0)
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
54 return NULL;
f197407bdba2 Recorded merge of revisions 81032 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 {
61467
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
73 PyObject *list, *item, *result;
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
74 Py_ssize_t lo = 0;
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
75 Py_ssize_t hi = -1;
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
76 Py_ssize_t index;
f197407bdba2 Recorded merge of revisions 81032 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
61467
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
79 if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn:insort_right",
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
80 keywords, &list, &item, &lo, &hi))
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
81 return NULL;
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
82 index = internal_bisect_right(list, item, lo, hi);
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
83 if (index < 0)
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
84 return NULL;
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
85 if (PyList_CheckExact(list)) {
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
86 if (PyList_Insert(list, index, item) < 0)
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
87 return NULL;
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
88 } else {
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
89 result = PyObject_CallMethod(list, "insert", "nO",
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
90 index, item);
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
91 if (result == NULL)
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
92 return NULL;
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
93 Py_DECREF(result);
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
94 }
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
95
61467
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
96 Py_RETURN_NONE;
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
97 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
98
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
99 PyDoc_STRVAR(insort_right_doc,
35699
3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args
Raymond Hettinger <python@rcn.com>
parents: 32898
diff changeset
100 "insort_right(a, x[, lo[, hi]])\n\
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
101 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
102 Insert item x in list a, and keep it sorted assuming a is sorted.\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
103 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
104 If x is already in a, insert it to the right of the rightmost x.\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
105 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
106 Optional args lo (default 0) and hi (default len(a)) bound the\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
107 slice of a to be searched.\n");
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
108
48594
35b1a20470db Merged revisions 65209-65216,65225-65226,65233,65239,65246-65247,65255-65256 via svnmerge from
Benjamin Peterson <benjamin@python.org>
parents: 48499
diff changeset
109 static Py_ssize_t
35b1a20470db Merged revisions 65209-65216,65225-65226,65233,65239,65246-65247,65255-65256 via svnmerge from
Benjamin Peterson <benjamin@python.org>
parents: 48499
diff changeset
110 internal_bisect_left(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi)
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
111 {
61467
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
112 PyObject *litem;
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
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
61467
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
115 if (lo < 0) {
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
116 PyErr_SetString(PyExc_ValueError, "lo must be non-negative");
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
117 return -1;
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
118 }
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
119 if (hi == -1) {
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
120 hi = PySequence_Size(list);
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
121 if (hi < 0)
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
122 return -1;
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
123 }
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
124 while (lo < hi) {
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
125 mid = (lo + hi) / 2;
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
126 litem = PySequence_GetItem(list, mid);
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
127 if (litem == NULL)
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
128 return -1;
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
129 res = PyObject_RichCompareBool(litem, item, Py_LT);
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
130 Py_DECREF(litem);
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
131 if (res < 0)
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
132 return -1;
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
133 if (res)
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
134 lo = mid + 1;
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
135 else
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
136 hi = mid;
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
137 }
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
138 return lo;
31353
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 {
61467
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
144 PyObject *list, *item;
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
145 Py_ssize_t lo = 0;
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
146 Py_ssize_t hi = -1;
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
147 Py_ssize_t index;
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
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
61467
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
150 if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn:bisect_left",
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
151 keywords, &list, &item, &lo, &hi))
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
152 return NULL;
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
153 index = internal_bisect_left(list, item, lo, hi);
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
154 if (index < 0)
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
155 return NULL;
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
156 return PyLong_FromSsize_t(index);
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
157 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
158
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
159 PyDoc_STRVAR(bisect_left_doc,
35699
3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args
Raymond Hettinger <python@rcn.com>
parents: 32898
diff changeset
160 "bisect_left(a, x[, lo[, hi]]) -> index\n\
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
161 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
162 Return the index where to insert item x in list a, assuming a is sorted.\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
163 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
164 The return value i is such that all e in a[:i] have e < x, and all e in\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
165 a[i:] have e >= x. So if x already appears in the list, i points just\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
166 before the leftmost x already there.\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
167 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
168 Optional args lo (default 0) and hi (default len(a)) bound the\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
169 slice of a to be searched.\n");
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
170
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
171 static PyObject *
35699
3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args
Raymond Hettinger <python@rcn.com>
parents: 32898
diff changeset
172 insort_left(PyObject *self, PyObject *args, PyObject *kw)
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
173 {
61467
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
174 PyObject *list, *item, *result;
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
175 Py_ssize_t lo = 0;
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
176 Py_ssize_t hi = -1;
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
177 Py_ssize_t index;
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
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
61467
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
180 if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn:insort_left",
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
181 keywords, &list, &item, &lo, &hi))
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
182 return NULL;
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
183 index = internal_bisect_left(list, item, lo, hi);
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
184 if (index < 0)
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
185 return NULL;
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
186 if (PyList_CheckExact(list)) {
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
187 if (PyList_Insert(list, index, item) < 0)
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
188 return NULL;
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
189 } else {
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
190 result = PyObject_CallMethod(list, "insert", "iO",
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
191 index, item);
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
192 if (result == NULL)
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
193 return NULL;
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
194 Py_DECREF(result);
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
195 }
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
196
61467
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
197 Py_RETURN_NONE;
31353
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[] = {
61467
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
214 {"bisect_right", (PyCFunction)bisect_right,
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
215 METH_VARARGS|METH_KEYWORDS, bisect_right_doc},
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
216 {"bisect", (PyCFunction)bisect_right,
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
217 METH_VARARGS|METH_KEYWORDS, bisect_doc},
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
218 {"insort_right", (PyCFunction)insort_right,
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
219 METH_VARARGS|METH_KEYWORDS, insort_right_doc},
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
220 {"insort", (PyCFunction)insort_right,
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
221 METH_VARARGS|METH_KEYWORDS, insort_doc},
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
222 {"bisect_left", (PyCFunction)bisect_left,
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
223 METH_VARARGS|METH_KEYWORDS, bisect_left_doc},
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
224 {"insort_left", (PyCFunction)insort_left,
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
225 METH_VARARGS|METH_KEYWORDS, insort_left_doc},
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
226 {NULL, NULL} /* sentinel */
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
227 };
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
228
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
229 PyDoc_STRVAR(module_doc,
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
230 "Bisection algorithms.\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
231 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
232 This module provides support for maintaining a list in sorted order without\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
233 having to sort the list after each insertion. For long lists of items with\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
234 expensive comparison operations, this can be an improvement over the more\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
235 common approach.\n");
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
236
47580
94f64f11fdd0 Implement PEP 3121: new module initialization and finalization API.
Martin v. Löwis <martin@v.loewis.de>
parents: 44099
diff changeset
237
94f64f11fdd0 Implement PEP 3121: new module initialization and finalization API.
Martin v. Löwis <martin@v.loewis.de>
parents: 44099
diff changeset
238 static struct PyModuleDef _bisectmodule = {
61467
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
239 PyModuleDef_HEAD_INIT,
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
240 "_bisect",
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
241 module_doc,
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
242 -1,
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
243 bisect_methods,
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
244 NULL,
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
245 NULL,
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
246 NULL,
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
247 NULL
47580
94f64f11fdd0 Implement PEP 3121: new module initialization and finalization API.
Martin v. Löwis <martin@v.loewis.de>
parents: 44099
diff changeset
248 };
94f64f11fdd0 Implement PEP 3121: new module initialization and finalization API.
Martin v. Löwis <martin@v.loewis.de>
parents: 44099
diff changeset
249
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
250 PyMODINIT_FUNC
47580
94f64f11fdd0 Implement PEP 3121: new module initialization and finalization API.
Martin v. Löwis <martin@v.loewis.de>
parents: 44099
diff changeset
251 PyInit__bisect(void)
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
252 {
61467
f197407bdba2 Recorded merge of revisions 81032 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 49493
diff changeset
253 return PyModule_Create(&_bisectmodule);
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
254 }