Branch data Line data Source code
1 : : /* Bisection algorithms. Drop in replacement for bisect.py
2 : :
3 : : Converted to C by Dmitry Vasiliev (dima at hlabs.spb.ru).
4 : : */
5 : :
6 : : #define PY_SSIZE_T_CLEAN
7 : : #include "Python.h"
8 : :
9 : : /*[clinic input]
10 : : module _bisect
11 : : [clinic start generated code]*/
12 : : /*[clinic end generated code: output=da39a3ee5e6b4b0d input=4d56a2b2033b462b]*/
13 : :
14 : : #include "clinic/_bisectmodule.c.h"
15 : :
16 : : typedef struct {
17 : : PyObject *str_insert;
18 : : } bisect_state;
19 : :
20 : : static inline bisect_state*
21 : 2724 : get_bisect_state(PyObject *module)
22 : : {
23 : 2724 : void *state = PyModule_GetState(module);
24 : : assert(state != NULL);
25 : 2724 : return (bisect_state *)state;
26 : : }
27 : :
28 : : static inline Py_ssize_t
29 : 180166 : internal_bisect_right(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi,
30 : : PyObject* key)
31 : : {
32 : : PyObject *litem;
33 : : Py_ssize_t mid;
34 : : int res;
35 : :
36 [ + + ]: 180166 : if (lo < 0) {
37 : 2 : PyErr_SetString(PyExc_ValueError, "lo must be non-negative");
38 : 2 : return -1;
39 : : }
40 [ + + ]: 180164 : if (hi == -1) {
41 : 129269 : hi = PySequence_Size(list);
42 [ + + ]: 129269 : if (hi < 0)
43 : 4 : return -1;
44 : : }
45 [ + + ]: 1429380 : while (lo < hi) {
46 : : /* The (size_t)cast ensures that the addition and subsequent division
47 : : are performed as unsigned operations, avoiding difficulties from
48 : : signed overflow. (See issue 13496.) */
49 : 1249224 : mid = ((size_t)lo + hi) / 2;
50 : 1249224 : litem = PySequence_GetItem(list, mid);
51 [ + + ]: 1249224 : if (litem == NULL)
52 : 2 : return -1;
53 [ + + ]: 1249222 : if (key != Py_None) {
54 : 236 : PyObject *newitem = PyObject_CallOneArg(key, litem);
55 [ - + ]: 236 : if (newitem == NULL) {
56 : 0 : Py_DECREF(litem);
57 : 0 : return -1;
58 : : }
59 : 236 : Py_SETREF(litem, newitem);
60 : : }
61 : 1249222 : res = PyObject_RichCompareBool(item, litem, Py_LT);
62 : 1249222 : Py_DECREF(litem);
63 [ + + ]: 1249222 : if (res < 0)
64 : 2 : return -1;
65 [ + + ]: 1249220 : if (res)
66 : 683287 : hi = mid;
67 : : else
68 : 565933 : lo = mid + 1;
69 : : }
70 : 180156 : return lo;
71 : : }
72 : :
73 : : /*[clinic input]
74 : : _bisect.bisect_right -> Py_ssize_t
75 : :
76 : : a: object
77 : : x: object
78 : : lo: Py_ssize_t = 0
79 : : hi: Py_ssize_t(c_default='-1', accept={int, NoneType}) = None
80 : : *
81 : : key: object = None
82 : :
83 : : Return the index where to insert item x in list a, assuming a is sorted.
84 : :
85 : : The return value i is such that all e in a[:i] have e <= x, and all e in
86 : : a[i:] have e > x. So if x already appears in the list, a.insert(i, x) will
87 : : insert just after the rightmost x already there.
88 : :
89 : : Optional args lo (default 0) and hi (default len(a)) bound the
90 : : slice of a to be searched.
91 : : [clinic start generated code]*/
92 : :
93 : : static Py_ssize_t
94 : 111650 : _bisect_bisect_right_impl(PyObject *module, PyObject *a, PyObject *x,
95 : : Py_ssize_t lo, Py_ssize_t hi, PyObject *key)
96 : : /*[clinic end generated code: output=3a4bc09cc7c8a73d input=40fcc5afa06ae593]*/
97 : : {
98 : 111650 : return internal_bisect_right(a, x, lo, hi, key);
99 : : }
100 : :
101 : : /*[clinic input]
102 : : _bisect.insort_right
103 : :
104 : : a: object
105 : : x: object
106 : : lo: Py_ssize_t = 0
107 : : hi: Py_ssize_t(c_default='-1', accept={int, NoneType}) = None
108 : : *
109 : : key: object = None
110 : :
111 : : Insert item x in list a, and keep it sorted assuming a is sorted.
112 : :
113 : : If x is already in a, insert it to the right of the rightmost x.
114 : :
115 : : Optional args lo (default 0) and hi (default len(a)) bound the
116 : : slice of a to be searched.
117 : : [clinic start generated code]*/
118 : :
119 : : static PyObject *
120 : 68517 : _bisect_insort_right_impl(PyObject *module, PyObject *a, PyObject *x,
121 : : Py_ssize_t lo, Py_ssize_t hi, PyObject *key)
122 : : /*[clinic end generated code: output=ac3bf26d07aedda2 input=44e1708e26b7b802]*/
123 : : {
124 : : PyObject *result, *key_x;
125 : : Py_ssize_t index;
126 : :
127 [ + + ]: 68517 : if (key == Py_None) {
128 : 68475 : index = internal_bisect_right(a, x, lo, hi, key);
129 : : } else {
130 : 42 : key_x = PyObject_CallOneArg(key, x);
131 [ + + ]: 42 : if (key_x == NULL) {
132 : 1 : return NULL;
133 : : }
134 : 41 : index = internal_bisect_right(a, key_x, lo, hi, key);
135 : 41 : Py_DECREF(key_x);
136 : : }
137 [ + + ]: 68516 : if (index < 0)
138 : 5 : return NULL;
139 [ + + ]: 68511 : if (PyList_CheckExact(a)) {
140 [ - + ]: 68266 : if (PyList_Insert(a, index, x) < 0)
141 : 0 : return NULL;
142 : : }
143 : : else {
144 : 245 : bisect_state *state = get_bisect_state(module);
145 : 245 : result = _PyObject_CallMethod(a, state->str_insert, "nO", index, x);
146 [ - + ]: 245 : if (result == NULL)
147 : 0 : return NULL;
148 : 245 : Py_DECREF(result);
149 : : }
150 : :
151 : 68511 : Py_RETURN_NONE;
152 : : }
153 : :
154 : : static inline Py_ssize_t
155 : 46837 : internal_bisect_left(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi,
156 : : PyObject *key)
157 : : {
158 : : PyObject *litem;
159 : : Py_ssize_t mid;
160 : : int res;
161 : :
162 [ + + ]: 46837 : if (lo < 0) {
163 : 2 : PyErr_SetString(PyExc_ValueError, "lo must be non-negative");
164 : 2 : return -1;
165 : : }
166 [ + + ]: 46835 : if (hi == -1) {
167 : 46050 : hi = PySequence_Size(list);
168 [ + + ]: 46050 : if (hi < 0)
169 : 4 : return -1;
170 : : }
171 [ + + ]: 195846 : while (lo < hi) {
172 : : /* The (size_t)cast ensures that the addition and subsequent division
173 : : are performed as unsigned operations, avoiding difficulties from
174 : : signed overflow. (See issue 13496.) */
175 : 149019 : mid = ((size_t)lo + hi) / 2;
176 : 149019 : litem = PySequence_GetItem(list, mid);
177 [ + + ]: 149019 : if (litem == NULL)
178 : 2 : return -1;
179 [ + + ]: 149017 : if (key != Py_None) {
180 : 242 : PyObject *newitem = PyObject_CallOneArg(key, litem);
181 [ - + ]: 242 : if (newitem == NULL) {
182 : 0 : Py_DECREF(litem);
183 : 0 : return -1;
184 : : }
185 : 242 : Py_SETREF(litem, newitem);
186 : : }
187 : 149017 : res = PyObject_RichCompareBool(litem, item, Py_LT);
188 : 149017 : Py_DECREF(litem);
189 [ + + ]: 149017 : if (res < 0)
190 : 2 : return -1;
191 [ + + ]: 149015 : if (res)
192 : 38200 : lo = mid + 1;
193 : : else
194 : 110815 : hi = mid;
195 : : }
196 : 46827 : return lo;
197 : : }
198 : :
199 : :
200 : : /*[clinic input]
201 : : _bisect.bisect_left -> Py_ssize_t
202 : :
203 : : a: object
204 : : x: object
205 : : lo: Py_ssize_t = 0
206 : : hi: Py_ssize_t(c_default='-1', accept={int, NoneType}) = None
207 : : *
208 : : key: object = None
209 : :
210 : : Return the index where to insert item x in list a, assuming a is sorted.
211 : :
212 : : The return value i is such that all e in a[:i] have e < x, and all e in
213 : : a[i:] have e >= x. So if x already appears in the list, a.insert(i, x) will
214 : : insert just before the leftmost x already there.
215 : :
216 : : Optional args lo (default 0) and hi (default len(a)) bound the
217 : : slice of a to be searched.
218 : : [clinic start generated code]*/
219 : :
220 : : static Py_ssize_t
221 : 46276 : _bisect_bisect_left_impl(PyObject *module, PyObject *a, PyObject *x,
222 : : Py_ssize_t lo, Py_ssize_t hi, PyObject *key)
223 : : /*[clinic end generated code: output=70749d6e5cae9284 input=90dd35b50ceb05e3]*/
224 : : {
225 : 46276 : return internal_bisect_left(a, x, lo, hi, key);
226 : : }
227 : :
228 : :
229 : : /*[clinic input]
230 : : _bisect.insort_left
231 : :
232 : : a: object
233 : : x: object
234 : : lo: Py_ssize_t = 0
235 : : hi: Py_ssize_t(c_default='-1', accept={int, NoneType}) = None
236 : : *
237 : : key: object = None
238 : :
239 : : Insert item x in list a, and keep it sorted assuming a is sorted.
240 : :
241 : : If x is already in a, insert it to the left of the leftmost x.
242 : :
243 : : Optional args lo (default 0) and hi (default len(a)) bound the
244 : : slice of a to be searched.
245 : : [clinic start generated code]*/
246 : :
247 : : static PyObject *
248 : 562 : _bisect_insort_left_impl(PyObject *module, PyObject *a, PyObject *x,
249 : : Py_ssize_t lo, Py_ssize_t hi, PyObject *key)
250 : : /*[clinic end generated code: output=b1d33e5e7ffff11e input=3ab65d8784f585b1]*/
251 : : {
252 : : PyObject *result, *key_x;
253 : : Py_ssize_t index;
254 : :
255 [ + + ]: 562 : if (key == Py_None) {
256 : 520 : index = internal_bisect_left(a, x, lo, hi, key);
257 : : } else {
258 : 42 : key_x = PyObject_CallOneArg(key, x);
259 [ + + ]: 42 : if (key_x == NULL) {
260 : 1 : return NULL;
261 : : }
262 : 41 : index = internal_bisect_left(a, key_x, lo, hi, key);
263 : 41 : Py_DECREF(key_x);
264 : : }
265 [ + + ]: 561 : if (index < 0)
266 : 5 : return NULL;
267 [ + + ]: 556 : if (PyList_CheckExact(a)) {
268 [ - + ]: 297 : if (PyList_Insert(a, index, x) < 0)
269 : 0 : return NULL;
270 : : } else {
271 : 259 : bisect_state *state = get_bisect_state(module);
272 : 259 : result = _PyObject_CallMethod(a, state->str_insert, "nO", index, x);
273 [ - + ]: 259 : if (result == NULL)
274 : 0 : return NULL;
275 : 259 : Py_DECREF(result);
276 : : }
277 : :
278 : 556 : Py_RETURN_NONE;
279 : : }
280 : :
281 : : static PyMethodDef bisect_methods[] = {
282 : : _BISECT_BISECT_RIGHT_METHODDEF
283 : : _BISECT_INSORT_RIGHT_METHODDEF
284 : : _BISECT_BISECT_LEFT_METHODDEF
285 : : _BISECT_INSORT_LEFT_METHODDEF
286 : : {NULL, NULL} /* sentinel */
287 : : };
288 : :
289 : : PyDoc_STRVAR(module_doc,
290 : : "Bisection algorithms.\n\
291 : : \n\
292 : : This module provides support for maintaining a list in sorted order without\n\
293 : : having to sort the list after each insertion. For long lists of items with\n\
294 : : expensive comparison operations, this can be an improvement over the more\n\
295 : : common approach.\n");
296 : :
297 : : static int
298 : 1114 : bisect_clear(PyObject *module)
299 : : {
300 : 1114 : bisect_state *state = get_bisect_state(module);
301 [ + + ]: 1114 : Py_CLEAR(state->str_insert);
302 : 1114 : return 0;
303 : : }
304 : :
305 : : static void
306 : 1106 : bisect_free(void *module)
307 : : {
308 : 1106 : bisect_clear((PyObject *)module);
309 : 1106 : }
310 : :
311 : : static int
312 : 1106 : bisect_modexec(PyObject *m)
313 : : {
314 : 1106 : bisect_state *state = get_bisect_state(m);
315 : 1106 : state->str_insert = PyUnicode_InternFromString("insert");
316 [ - + ]: 1106 : if (state->str_insert == NULL) {
317 : 0 : return -1;
318 : : }
319 : 1106 : return 0;
320 : : }
321 : :
322 : : static PyModuleDef_Slot bisect_slots[] = {
323 : : {Py_mod_exec, bisect_modexec},
324 : : {0, NULL}
325 : : };
326 : :
327 : : static struct PyModuleDef _bisectmodule = {
328 : : PyModuleDef_HEAD_INIT,
329 : : .m_name = "_bisect",
330 : : .m_size = sizeof(bisect_state),
331 : : .m_doc = module_doc,
332 : : .m_methods = bisect_methods,
333 : : .m_slots = bisect_slots,
334 : : .m_clear = bisect_clear,
335 : : .m_free = bisect_free,
336 : : };
337 : :
338 : : PyMODINIT_FUNC
339 : 1106 : PyInit__bisect(void)
340 : : {
341 : 1106 : return PyModuleDef_Init(&_bisectmodule);
342 : : }
|
