From 7eb75bccb5dacb658c63db1a9a980950c3d54d42 Mon Sep 17 00:00:00 2001 From: Daryl McDaniel Date: Sat, 7 Nov 2015 19:25:02 +0000 Subject: AppPkg/Applications/Python/Python-2.7.10: Initial Checkin part 2/5. The Modules directory from the cPython 2.7.10 distribution. These files are unchanged and set the baseline for subsequent commits. Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Daryl McDaniel git-svn-id: https://svn.code.sf.net/p/edk2/code/trunk/edk2@18738 6f19259b-4bc3-4df7-8a09-765794883524 --- .../Python/Python-2.7.10/Modules/_bisectmodule.c | 246 +++++++++++++++++++++ 1 file changed, 246 insertions(+) create mode 100644 AppPkg/Applications/Python/Python-2.7.10/Modules/_bisectmodule.c (limited to 'AppPkg/Applications/Python/Python-2.7.10/Modules/_bisectmodule.c') diff --git a/AppPkg/Applications/Python/Python-2.7.10/Modules/_bisectmodule.c b/AppPkg/Applications/Python/Python-2.7.10/Modules/_bisectmodule.c new file mode 100644 index 0000000000..e4f02f0e00 --- /dev/null +++ b/AppPkg/Applications/Python/Python-2.7.10/Modules/_bisectmodule.c @@ -0,0 +1,246 @@ +/* Bisection algorithms. Drop in replacement for bisect.py + +Converted to C by Dmitry Vasiliev (dima at hlabs.spb.ru). +*/ + +#include "Python.h" + +static Py_ssize_t +internal_bisect_right(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi) +{ + PyObject *litem; + Py_ssize_t mid, res; + + if (lo < 0) { + PyErr_SetString(PyExc_ValueError, "lo must be non-negative"); + return -1; + } + if (hi == -1) { + hi = PySequence_Size(list); + if (hi < 0) + return -1; + } + while (lo < hi) { + /* The (size_t)cast ensures that the addition and subsequent division + are performed as unsigned operations, avoiding difficulties from + signed overflow. (See issue 13496.) */ + mid = ((size_t)lo + hi) / 2; + litem = PySequence_GetItem(list, mid); + if (litem == NULL) + return -1; + res = PyObject_RichCompareBool(item, litem, Py_LT); + Py_DECREF(litem); + if (res < 0) + return -1; + if (res) + hi = mid; + else + lo = mid + 1; + } + return lo; +} + +static PyObject * +bisect_right(PyObject *self, PyObject *args, PyObject *kw) +{ + PyObject *list, *item; + Py_ssize_t lo = 0; + Py_ssize_t hi = -1; + Py_ssize_t index; + static char *keywords[] = {"a", "x", "lo", "hi", NULL}; + + if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn:bisect_right", + keywords, &list, &item, &lo, &hi)) + return NULL; + index = internal_bisect_right(list, item, lo, hi); + if (index < 0) + return NULL; + return PyInt_FromSsize_t(index); +} + +PyDoc_STRVAR(bisect_right_doc, +"bisect(a, x[, lo[, hi]]) -> index\n\ +bisect_right(a, x[, lo[, hi]]) -> index\n\ +\n\ +Return the index where to insert item x in list a, assuming a is sorted.\n\ +\n\ +The return value i is such that all e in a[:i] have e <= x, and all e in\n\ +a[i:] have e > x. So if x already appears in the list, i points just\n\ +beyond the rightmost x already there\n\ +\n\ +Optional args lo (default 0) and hi (default len(a)) bound the\n\ +slice of a to be searched.\n"); + +static PyObject * +insort_right(PyObject *self, PyObject *args, PyObject *kw) +{ + PyObject *list, *item, *result; + Py_ssize_t lo = 0; + Py_ssize_t hi = -1; + Py_ssize_t index; + static char *keywords[] = {"a", "x", "lo", "hi", NULL}; + + if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn:insort_right", + keywords, &list, &item, &lo, &hi)) + return NULL; + index = internal_bisect_right(list, item, lo, hi); + if (index < 0) + return NULL; + if (PyList_CheckExact(list)) { + if (PyList_Insert(list, index, item) < 0) + return NULL; + } else { + result = PyObject_CallMethod(list, "insert", "nO", + index, item); + if (result == NULL) + return NULL; + Py_DECREF(result); + } + + Py_RETURN_NONE; +} + +PyDoc_STRVAR(insort_right_doc, +"insort(a, x[, lo[, hi]])\n\ +insort_right(a, x[, lo[, hi]])\n\ +\n\ +Insert item x in list a, and keep it sorted assuming a is sorted.\n\ +\n\ +If x is already in a, insert it to the right of the rightmost x.\n\ +\n\ +Optional args lo (default 0) and hi (default len(a)) bound the\n\ +slice of a to be searched.\n"); + +static Py_ssize_t +internal_bisect_left(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi) +{ + PyObject *litem; + Py_ssize_t mid, res; + + if (lo < 0) { + PyErr_SetString(PyExc_ValueError, "lo must be non-negative"); + return -1; + } + if (hi == -1) { + hi = PySequence_Size(list); + if (hi < 0) + return -1; + } + while (lo < hi) { + /* The (size_t)cast ensures that the addition and subsequent division + are performed as unsigned operations, avoiding difficulties from + signed overflow. (See issue 13496.) */ + mid = ((size_t)lo + hi) / 2; + litem = PySequence_GetItem(list, mid); + if (litem == NULL) + return -1; + res = PyObject_RichCompareBool(litem, item, Py_LT); + Py_DECREF(litem); + if (res < 0) + return -1; + if (res) + lo = mid + 1; + else + hi = mid; + } + return lo; +} + +static PyObject * +bisect_left(PyObject *self, PyObject *args, PyObject *kw) +{ + PyObject *list, *item; + Py_ssize_t lo = 0; + Py_ssize_t hi = -1; + Py_ssize_t index; + static char *keywords[] = {"a", "x", "lo", "hi", NULL}; + + if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn:bisect_left", + keywords, &list, &item, &lo, &hi)) + return NULL; + index = internal_bisect_left(list, item, lo, hi); + if (index < 0) + return NULL; + return PyInt_FromSsize_t(index); +} + +PyDoc_STRVAR(bisect_left_doc, +"bisect_left(a, x[, lo[, hi]]) -> index\n\ +\n\ +Return the index where to insert item x in list a, assuming a is sorted.\n\ +\n\ +The return value i is such that all e in a[:i] have e < x, and all e in\n\ +a[i:] have e >= x. So if x already appears in the list, i points just\n\ +before the leftmost x already there.\n\ +\n\ +Optional args lo (default 0) and hi (default len(a)) bound the\n\ +slice of a to be searched.\n"); + +static PyObject * +insort_left(PyObject *self, PyObject *args, PyObject *kw) +{ + PyObject *list, *item, *result; + Py_ssize_t lo = 0; + Py_ssize_t hi = -1; + Py_ssize_t index; + static char *keywords[] = {"a", "x", "lo", "hi", NULL}; + + if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn:insort_left", + keywords, &list, &item, &lo, &hi)) + return NULL; + index = internal_bisect_left(list, item, lo, hi); + if (index < 0) + return NULL; + if (PyList_CheckExact(list)) { + if (PyList_Insert(list, index, item) < 0) + return NULL; + } else { + result = PyObject_CallMethod(list, "insert", "nO", + index, item); + if (result == NULL) + return NULL; + Py_DECREF(result); + } + + Py_RETURN_NONE; +} + +PyDoc_STRVAR(insort_left_doc, +"insort_left(a, x[, lo[, hi]])\n\ +\n\ +Insert item x in list a, and keep it sorted assuming a is sorted.\n\ +\n\ +If x is already in a, insert it to the left of the leftmost x.\n\ +\n\ +Optional args lo (default 0) and hi (default len(a)) bound the\n\ +slice of a to be searched.\n"); + +static PyMethodDef bisect_methods[] = { + {"bisect_right", (PyCFunction)bisect_right, + METH_VARARGS|METH_KEYWORDS, bisect_right_doc}, + {"bisect", (PyCFunction)bisect_right, + METH_VARARGS|METH_KEYWORDS, bisect_right_doc}, + {"insort_right", (PyCFunction)insort_right, + METH_VARARGS|METH_KEYWORDS, insort_right_doc}, + {"insort", (PyCFunction)insort_right, + METH_VARARGS|METH_KEYWORDS, insort_right_doc}, + {"bisect_left", (PyCFunction)bisect_left, + METH_VARARGS|METH_KEYWORDS, bisect_left_doc}, + {"insort_left", (PyCFunction)insort_left, + METH_VARARGS|METH_KEYWORDS, insort_left_doc}, + {NULL, NULL} /* sentinel */ +}; + +PyDoc_STRVAR(module_doc, +"Bisection algorithms.\n\ +\n\ +This module provides support for maintaining a list in sorted order without\n\ +having to sort the list after each insertion. For long lists of items with\n\ +expensive comparison operations, this can be an improvement over the more\n\ +common approach.\n"); + +PyMODINIT_FUNC +init_bisect(void) +{ + Py_InitModule3("_bisect", bisect_methods, module_doc); +} -- cgit v1.2.3