Python code coverage for Modules/_bisectmodule.c

#	count	content
1	n/a	/* Bisection algorithms. Drop in replacement for bisect.py
2	n/a
3	n/a	Converted to C by Dmitry Vasiliev (dima at hlabs.spb.ru).
4	n/a	*/
5	n/a
6	n/a	#define PY_SSIZE_T_CLEAN
7	n/a	#include "Python.h"
8	n/a
9	n/a	_Py_IDENTIFIER(insert);
10	n/a
11	n/a	static Py_ssize_t
12	n/a	internal_bisect_right(PyObject list, PyObject item, Py_ssize_t lo, Py_ssize_t hi)
13	n/a	{
14	n/a	PyObject *litem;
15	n/a	Py_ssize_t mid;
16	n/a	int res;
17	n/a
18	n/a	if (lo < 0) {
19	n/a	PyErr_SetString(PyExc_ValueError, "lo must be non-negative");
20	n/a	return -1;
21	n/a	}
22	n/a	if (hi == -1) {
23	n/a	hi = PySequence_Size(list);
24	n/a	if (hi < 0)
25	n/a	return -1;
26	n/a	}
27	n/a	while (lo < hi) {
28	n/a	/* The (size_t)cast ensures that the addition and subsequent division
29	n/a	are performed as unsigned operations, avoiding difficulties from
30	n/a	signed overflow. (See issue 13496.) */
31	n/a	mid = ((size_t)lo + hi) / 2;
32	n/a	litem = PySequence_GetItem(list, mid);
33	n/a	if (litem == NULL)
34	n/a	return -1;
35	n/a	res = PyObject_RichCompareBool(item, litem, Py_LT);
36	n/a	Py_DECREF(litem);
37	n/a	if (res < 0)
38	n/a	return -1;
39	n/a	if (res)
40	n/a	hi = mid;
41	n/a	else
42	n/a	lo = mid + 1;
43	n/a	}
44	n/a	return lo;
45	n/a	}
46	n/a
47	n/a	static PyObject *
48	n/a	bisect_right(PyObject self, PyObject args, PyObject *kw)
49	n/a	{
50	n/a	PyObject list, item;
51	n/a	Py_ssize_t lo = 0;
52	n/a	Py_ssize_t hi = -1;
53	n/a	Py_ssize_t index;
54	n/a	static char *keywords[] = {"a", "x", "lo", "hi", NULL};
55	n/a
56	n/a	if (!PyArg_ParseTupleAndKeywords(args, kw, "OO\|nn:bisect_right",
57	n/a	keywords, &list, &item, &lo, &hi))
58	n/a	return NULL;
59	n/a	index = internal_bisect_right(list, item, lo, hi);
60	n/a	if (index < 0)
61	n/a	return NULL;
62	n/a	return PyLong_FromSsize_t(index);
63	n/a	}
64	n/a
65	n/a	PyDoc_STRVAR(bisect_right_doc,
66	n/a	"bisect_right(a, x[, lo[, hi]]) -> index\n\
67	n/a	\n\
68	n/a	Return the index where to insert item x in list a, assuming a is sorted.\n\
69	n/a	\n\
70	n/a	The return value i is such that all e in a[:i] have e <= x, and all e in\n\
71	n/a	a[i:] have e > x. So if x already appears in the list, i points just\n\
72	n/a	beyond the rightmost x already there\n\
73	n/a	\n\
74	n/a	Optional args lo (default 0) and hi (default len(a)) bound the\n\
75	n/a	slice of a to be searched.\n");
76	n/a
77	n/a	static PyObject *
78	n/a	insort_right(PyObject self, PyObject args, PyObject *kw)
79	n/a	{
80	n/a	PyObject list, item, *result;
81	n/a	Py_ssize_t lo = 0;
82	n/a	Py_ssize_t hi = -1;
83	n/a	Py_ssize_t index;
84	n/a	static char *keywords[] = {"a", "x", "lo", "hi", NULL};
85	n/a
86	n/a	if (!PyArg_ParseTupleAndKeywords(args, kw, "OO\|nn:insort_right",
87	n/a	keywords, &list, &item, &lo, &hi))
88	n/a	return NULL;
89	n/a	index = internal_bisect_right(list, item, lo, hi);
90	n/a	if (index < 0)
91	n/a	return NULL;
92	n/a	if (PyList_CheckExact(list)) {
93	n/a	if (PyList_Insert(list, index, item) < 0)
94	n/a	return NULL;
95	n/a	} else {
96	n/a	result = _PyObject_CallMethodId(list, &PyId_insert, "nO", index, item);
97	n/a	if (result == NULL)
98	n/a	return NULL;
99	n/a	Py_DECREF(result);
100	n/a	}
101	n/a
102	n/a	Py_RETURN_NONE;
103	n/a	}
104	n/a
105	n/a	PyDoc_STRVAR(insort_right_doc,
106	n/a	"insort_right(a, x[, lo[, hi]])\n\
107	n/a	\n\
108	n/a	Insert item x in list a, and keep it sorted assuming a is sorted.\n\
109	n/a	\n\
110	n/a	If x is already in a, insert it to the right of the rightmost x.\n\
111	n/a	\n\
112	n/a	Optional args lo (default 0) and hi (default len(a)) bound the\n\
113	n/a	slice of a to be searched.\n");
114	n/a
115	n/a	static Py_ssize_t
116	n/a	internal_bisect_left(PyObject list, PyObject item, Py_ssize_t lo, Py_ssize_t hi)
117	n/a	{
118	n/a	PyObject *litem;
119	n/a	Py_ssize_t mid;
120	n/a	int res;
121	n/a
122	n/a	if (lo < 0) {
123	n/a	PyErr_SetString(PyExc_ValueError, "lo must be non-negative");
124	n/a	return -1;
125	n/a	}
126	n/a	if (hi == -1) {
127	n/a	hi = PySequence_Size(list);
128	n/a	if (hi < 0)
129	n/a	return -1;
130	n/a	}
131	n/a	while (lo < hi) {
132	n/a	/* The (size_t)cast ensures that the addition and subsequent division
133	n/a	are performed as unsigned operations, avoiding difficulties from
134	n/a	signed overflow. (See issue 13496.) */
135	n/a	mid = ((size_t)lo + hi) / 2;
136	n/a	litem = PySequence_GetItem(list, mid);
137	n/a	if (litem == NULL)
138	n/a	return -1;
139	n/a	res = PyObject_RichCompareBool(litem, item, Py_LT);
140	n/a	Py_DECREF(litem);
141	n/a	if (res < 0)
142	n/a	return -1;
143	n/a	if (res)
144	n/a	lo = mid + 1;
145	n/a	else
146	n/a	hi = mid;
147	n/a	}
148	n/a	return lo;
149	n/a	}
150	n/a
151	n/a	static PyObject *
152	n/a	bisect_left(PyObject self, PyObject args, PyObject *kw)
153	n/a	{
154	n/a	PyObject list, item;
155	n/a	Py_ssize_t lo = 0;
156	n/a	Py_ssize_t hi = -1;
157	n/a	Py_ssize_t index;
158	n/a	static char *keywords[] = {"a", "x", "lo", "hi", NULL};
159	n/a
160	n/a	if (!PyArg_ParseTupleAndKeywords(args, kw, "OO\|nn:bisect_left",
161	n/a	keywords, &list, &item, &lo, &hi))
162	n/a	return NULL;
163	n/a	index = internal_bisect_left(list, item, lo, hi);
164	n/a	if (index < 0)
165	n/a	return NULL;
166	n/a	return PyLong_FromSsize_t(index);
167	n/a	}
168	n/a
169	n/a	PyDoc_STRVAR(bisect_left_doc,
170	n/a	"bisect_left(a, x[, lo[, hi]]) -> index\n\
171	n/a	\n\
172	n/a	Return the index where to insert item x in list a, assuming a is sorted.\n\
173	n/a	\n\
174	n/a	The return value i is such that all e in a[:i] have e < x, and all e in\n\
175	n/a	a[i:] have e >= x. So if x already appears in the list, i points just\n\
176	n/a	before the leftmost x already there.\n\
177	n/a	\n\
178	n/a	Optional args lo (default 0) and hi (default len(a)) bound the\n\
179	n/a	slice of a to be searched.\n");
180	n/a
181	n/a	static PyObject *
182	n/a	insort_left(PyObject self, PyObject args, PyObject *kw)
183	n/a	{
184	n/a	PyObject list, item, *result;
185	n/a	Py_ssize_t lo = 0;
186	n/a	Py_ssize_t hi = -1;
187	n/a	Py_ssize_t index;
188	n/a	static char *keywords[] = {"a", "x", "lo", "hi", NULL};
189	n/a
190	n/a	if (!PyArg_ParseTupleAndKeywords(args, kw, "OO\|nn:insort_left",
191	n/a	keywords, &list, &item, &lo, &hi))
192	n/a	return NULL;
193	n/a	index = internal_bisect_left(list, item, lo, hi);
194	n/a	if (index < 0)
195	n/a	return NULL;
196	n/a	if (PyList_CheckExact(list)) {
197	n/a	if (PyList_Insert(list, index, item) < 0)
198	n/a	return NULL;
199	n/a	} else {
200	n/a	result = _PyObject_CallMethodId(list, &PyId_insert, "nO", index, item);
201	n/a	if (result == NULL)
202	n/a	return NULL;
203	n/a	Py_DECREF(result);
204	n/a	}
205	n/a
206	n/a	Py_RETURN_NONE;
207	n/a	}
208	n/a
209	n/a	PyDoc_STRVAR(insort_left_doc,
210	n/a	"insort_left(a, x[, lo[, hi]])\n\
211	n/a	\n\
212	n/a	Insert item x in list a, and keep it sorted assuming a is sorted.\n\
213	n/a	\n\
214	n/a	If x is already in a, insert it to the left of the leftmost x.\n\
215	n/a	\n\
216	n/a	Optional args lo (default 0) and hi (default len(a)) bound the\n\
217	n/a	slice of a to be searched.\n");
218	n/a
219	n/a	static PyMethodDef bisect_methods[] = {
220	n/a	{"bisect_right", (PyCFunction)bisect_right,
221	n/a	METH_VARARGS\|METH_KEYWORDS, bisect_right_doc},
222	n/a	{"insort_right", (PyCFunction)insort_right,
223	n/a	METH_VARARGS\|METH_KEYWORDS, insort_right_doc},
224	n/a	{"bisect_left", (PyCFunction)bisect_left,
225	n/a	METH_VARARGS\|METH_KEYWORDS, bisect_left_doc},
226	n/a	{"insort_left", (PyCFunction)insort_left,
227	n/a	METH_VARARGS\|METH_KEYWORDS, insort_left_doc},
228	n/a	{NULL, NULL} /* sentinel */
229	n/a	};
230	n/a
231	n/a	PyDoc_STRVAR(module_doc,
232	n/a	"Bisection algorithms.\n\
233	n/a	\n\
234	n/a	This module provides support for maintaining a list in sorted order without\n\
235	n/a	having to sort the list after each insertion. For long lists of items with\n\
236	n/a	expensive comparison operations, this can be an improvement over the more\n\
237	n/a	common approach.\n");
238	n/a
239	n/a
240	n/a	static struct PyModuleDef _bisectmodule = {
241	n/a	PyModuleDef_HEAD_INIT,
242	n/a	"_bisect",
243	n/a	module_doc,
244	n/a	-1,
245	n/a	bisect_methods,
246	n/a	NULL,
247	n/a	NULL,
248	n/a	NULL,
249	n/a	NULL
250	n/a	};
251	n/a
252	n/a	PyMODINIT_FUNC
253	n/a	PyInit__bisect(void)
254	n/a	{
255	n/a	return PyModule_Create(&_bisectmodule);
256	n/a	}