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*
get_bisect_state(PyObject * module)21 get_bisect_state(PyObject *module)
22 {
23 void *state = PyModule_GetState(module);
24 assert(state != NULL);
25 return (bisect_state *)state;
26 }
27
28 static inline Py_ssize_t
internal_bisect_right(PyObject * list,PyObject * item,Py_ssize_t lo,Py_ssize_t hi,PyObject * key)29 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 if (lo < 0) {
37 PyErr_SetString(PyExc_ValueError, "lo must be non-negative");
38 return -1;
39 }
40 if (hi == -1) {
41 hi = PySequence_Size(list);
42 if (hi < 0)
43 return -1;
44 }
45 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 mid = ((size_t)lo + hi) / 2;
50 litem = PySequence_GetItem(list, mid);
51 if (litem == NULL)
52 return -1;
53 if (key != Py_None) {
54 PyObject *newitem = PyObject_CallOneArg(key, litem);
55 if (newitem == NULL) {
56 Py_DECREF(litem);
57 return -1;
58 }
59 Py_SETREF(litem, newitem);
60 }
61 res = PyObject_RichCompareBool(item, litem, Py_LT);
62 Py_DECREF(litem);
63 if (res < 0)
64 return -1;
65 if (res)
66 hi = mid;
67 else
68 lo = mid + 1;
69 }
70 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
_bisect_bisect_right_impl(PyObject * module,PyObject * a,PyObject * x,Py_ssize_t lo,Py_ssize_t hi,PyObject * key)94 _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 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 *
_bisect_insort_right_impl(PyObject * module,PyObject * a,PyObject * x,Py_ssize_t lo,Py_ssize_t hi,PyObject * key)120 _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 if (key == Py_None) {
128 index = internal_bisect_right(a, x, lo, hi, key);
129 } else {
130 key_x = PyObject_CallOneArg(key, x);
131 if (key_x == NULL) {
132 return NULL;
133 }
134 index = internal_bisect_right(a, key_x, lo, hi, key);
135 Py_DECREF(key_x);
136 }
137 if (index < 0)
138 return NULL;
139 if (PyList_CheckExact(a)) {
140 if (PyList_Insert(a, index, x) < 0)
141 return NULL;
142 }
143 else {
144 bisect_state *state = get_bisect_state(module);
145 result = _PyObject_CallMethod(a, state->str_insert, "nO", index, x);
146 if (result == NULL)
147 return NULL;
148 Py_DECREF(result);
149 }
150
151 Py_RETURN_NONE;
152 }
153
154 static inline Py_ssize_t
internal_bisect_left(PyObject * list,PyObject * item,Py_ssize_t lo,Py_ssize_t hi,PyObject * key)155 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 if (lo < 0) {
163 PyErr_SetString(PyExc_ValueError, "lo must be non-negative");
164 return -1;
165 }
166 if (hi == -1) {
167 hi = PySequence_Size(list);
168 if (hi < 0)
169 return -1;
170 }
171 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 mid = ((size_t)lo + hi) / 2;
176 litem = PySequence_GetItem(list, mid);
177 if (litem == NULL)
178 return -1;
179 if (key != Py_None) {
180 PyObject *newitem = PyObject_CallOneArg(key, litem);
181 if (newitem == NULL) {
182 Py_DECREF(litem);
183 return -1;
184 }
185 Py_SETREF(litem, newitem);
186 }
187 res = PyObject_RichCompareBool(litem, item, Py_LT);
188 Py_DECREF(litem);
189 if (res < 0)
190 return -1;
191 if (res)
192 lo = mid + 1;
193 else
194 hi = mid;
195 }
196 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
_bisect_bisect_left_impl(PyObject * module,PyObject * a,PyObject * x,Py_ssize_t lo,Py_ssize_t hi,PyObject * key)221 _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 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 *
_bisect_insort_left_impl(PyObject * module,PyObject * a,PyObject * x,Py_ssize_t lo,Py_ssize_t hi,PyObject * key)248 _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 if (key == Py_None) {
256 index = internal_bisect_left(a, x, lo, hi, key);
257 } else {
258 key_x = PyObject_CallOneArg(key, x);
259 if (key_x == NULL) {
260 return NULL;
261 }
262 index = internal_bisect_left(a, key_x, lo, hi, key);
263 Py_DECREF(key_x);
264 }
265 if (index < 0)
266 return NULL;
267 if (PyList_CheckExact(a)) {
268 if (PyList_Insert(a, index, x) < 0)
269 return NULL;
270 } else {
271 bisect_state *state = get_bisect_state(module);
272 result = _PyObject_CallMethod(a, state->str_insert, "nO", index, x);
273 if (result == NULL)
274 return NULL;
275 Py_DECREF(result);
276 }
277
278 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
bisect_clear(PyObject * module)298 bisect_clear(PyObject *module)
299 {
300 bisect_state *state = get_bisect_state(module);
301 Py_CLEAR(state->str_insert);
302 return 0;
303 }
304
305 static void
bisect_free(void * module)306 bisect_free(void *module)
307 {
308 bisect_clear((PyObject *)module);
309 }
310
311 static int
bisect_modexec(PyObject * m)312 bisect_modexec(PyObject *m)
313 {
314 bisect_state *state = get_bisect_state(m);
315 state->str_insert = PyUnicode_InternFromString("insert");
316 if (state->str_insert == NULL) {
317 return -1;
318 }
319 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
PyInit__bisect(void)339 PyInit__bisect(void)
340 {
341 return PyModuleDef_Init(&_bisectmodule);
342 }
343