Ignore:
Timestamp:
Mar 19, 2014, 11:31:01 PM (11 years ago)
Author:
dmik
Message:

python: Merge vendor 2.7.6 to trunk.

Location:
python/trunk
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • python/trunk

  • python/trunk/Modules/_bisectmodule.c

    r2 r391  
    99internal_bisect_right(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi)
    1010{
    11         PyObject *litem;
    12         Py_ssize_t mid, res;
    13 
    14         if (lo < 0) {
    15                 PyErr_SetString(PyExc_ValueError, "lo must be non-negative");
    16                 return -1;
    17         }
    18         if (hi == -1) {
    19                 hi = PySequence_Size(list);
    20                 if (hi < 0)
    21                         return -1;
    22         }
    23         while (lo < hi) {
    24                 mid = (lo + hi) / 2;
    25                 litem = PySequence_GetItem(list, mid);
    26                 if (litem == NULL)
    27                         return -1;
    28                 res = PyObject_RichCompareBool(item, litem, Py_LT);
    29                 Py_DECREF(litem);
    30                 if (res < 0)
    31                         return -1;
    32                 if (res)
    33                         hi = mid;
    34                 else
    35                         lo = mid + 1;
    36         }
    37         return lo;
     11    PyObject *litem;
     12    Py_ssize_t mid, res;
     13
     14    if (lo < 0) {
     15        PyErr_SetString(PyExc_ValueError, "lo must be non-negative");
     16        return -1;
     17    }
     18    if (hi == -1) {
     19        hi = PySequence_Size(list);
     20        if (hi < 0)
     21            return -1;
     22    }
     23    while (lo < hi) {
     24        /* The (size_t)cast ensures that the addition and subsequent division
     25           are performed as unsigned operations, avoiding difficulties from
     26           signed overflow.  (See issue 13496.) */
     27        mid = ((size_t)lo + hi) / 2;
     28        litem = PySequence_GetItem(list, mid);
     29        if (litem == NULL)
     30            return -1;
     31        res = PyObject_RichCompareBool(item, litem, Py_LT);
     32        Py_DECREF(litem);
     33        if (res < 0)
     34            return -1;
     35        if (res)
     36            hi = mid;
     37        else
     38            lo = mid + 1;
     39    }
     40    return lo;
    3841}
    3942
    … …  
    4144bisect_right(PyObject *self, PyObject *args, PyObject *kw)
    4245{
    43         PyObject *list, *item;
    44         Py_ssize_t lo = 0;
    45         Py_ssize_t hi = -1;
    46         Py_ssize_t index;
    47         static char *keywords[] = {"a", "x", "lo", "hi", NULL};
    48 
    49         if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn:bisect_right",
    50                 keywords, &list, &item, &lo, &hi))
    51                 return NULL;
    52         index = internal_bisect_right(list, item, lo, hi);
    53         if (index < 0)
    54                 return NULL;
    55         return PyInt_FromSsize_t(index);
     46    PyObject *list, *item;
     47    Py_ssize_t lo = 0;
     48    Py_ssize_t hi = -1;
     49    Py_ssize_t index;
     50    static char *keywords[] = {"a", "x", "lo", "hi", NULL};
     51
     52    if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn:bisect_right",
     53        keywords, &list, &item, &lo, &hi))
     54        return NULL;
     55    index = internal_bisect_right(list, item, lo, hi);
     56    if (index < 0)
     57        return NULL;
     58    return PyInt_FromSsize_t(index);
    5659}
    5760
    5861PyDoc_STRVAR(bisect_right_doc,
    59 "bisect_right(a, x[, lo[, hi]]) -> index\n\
     62"bisect(a, x[, lo[, hi]]) -> index\n\
     63bisect_right(a, x[, lo[, hi]]) -> index\n\
    6064\n\
    6165Return the index where to insert item x in list a, assuming a is sorted.\n\
    … …  
    7175insort_right(PyObject *self, PyObject *args, PyObject *kw)
    7276{
    73         PyObject *list, *item, *result;
    74         Py_ssize_t lo = 0;
    75         Py_ssize_t hi = -1;
    76         Py_ssize_t index;
    77         static char *keywords[] = {"a", "x", "lo", "hi", NULL};
    78 
    79         if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn:insort_right",
    80                 keywords, &list, &item, &lo, &hi))
    81                 return NULL;
    82         index = internal_bisect_right(list, item, lo, hi);
    83         if (index < 0)
    84                 return NULL;
    85         if (PyList_CheckExact(list)) {
    86                 if (PyList_Insert(list, index, item) < 0)
    87                         return NULL;
    88         } else {
    89                 result = PyObject_CallMethod(list, "insert", "nO",
    90                                              index, item);
    91                 if (result == NULL)
    92                         return NULL;
    93                 Py_DECREF(result);
    94         }
    95 
    96         Py_RETURN_NONE;
     77    PyObject *list, *item, *result;
     78    Py_ssize_t lo = 0;
     79    Py_ssize_t hi = -1;
     80    Py_ssize_t index;
     81    static char *keywords[] = {"a", "x", "lo", "hi", NULL};
     82
     83    if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn:insort_right",
     84        keywords, &list, &item, &lo, &hi))
     85        return NULL;
     86    index = internal_bisect_right(list, item, lo, hi);
     87    if (index < 0)
     88        return NULL;
     89    if (PyList_CheckExact(list)) {
     90        if (PyList_Insert(list, index, item) < 0)
     91            return NULL;
     92    } else {
     93        result = PyObject_CallMethod(list, "insert", "nO",
     94                                     index, item);
     95        if (result == NULL)
     96            return NULL;
     97        Py_DECREF(result);
     98    }
     99
     100    Py_RETURN_NONE;
    97101}
    98102
    99103PyDoc_STRVAR(insort_right_doc,
    100 "insort_right(a, x[, lo[, hi]])\n\
     104"insort(a, x[, lo[, hi]])\n\
     105insort_right(a, x[, lo[, hi]])\n\
    101106\n\
    102107Insert item x in list a, and keep it sorted assuming a is sorted.\n\
    … …  
    110115internal_bisect_left(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi)
    111116{
    112         PyObject *litem;
    113         Py_ssize_t mid, res;
    114 
    115         if (lo < 0) {
    116                 PyErr_SetString(PyExc_ValueError, "lo must be non-negative");
    117                 return -1;
    118         }
    119         if (hi == -1) {
    120                 hi = PySequence_Size(list);
    121                 if (hi < 0)
    122                         return -1;
    123         }
    124         while (lo < hi) {
    125                 mid = (lo + hi) / 2;
    126                 litem = PySequence_GetItem(list, mid);
    127                 if (litem == NULL)
    128                         return -1;
    129                 res = PyObject_RichCompareBool(litem, item, Py_LT);
    130                 Py_DECREF(litem);
    131                 if (res < 0)
    132                         return -1;
    133                 if (res)
    134                         lo = mid + 1;
    135                 else
    136                         hi = mid;
    137         }
    138         return lo;
     117    PyObject *litem;
     118    Py_ssize_t mid, res;
     119
     120    if (lo < 0) {
     121        PyErr_SetString(PyExc_ValueError, "lo must be non-negative");
     122        return -1;
     123    }
     124    if (hi == -1) {
     125        hi = PySequence_Size(list);
     126        if (hi < 0)
     127            return -1;
     128    }
     129    while (lo < hi) {
     130        /* The (size_t)cast ensures that the addition and subsequent division
     131           are performed as unsigned operations, avoiding difficulties from
     132           signed overflow.  (See issue 13496.) */
     133        mid = ((size_t)lo + hi) / 2;
     134        litem = PySequence_GetItem(list, mid);
     135        if (litem == NULL)
     136            return -1;
     137        res = PyObject_RichCompareBool(litem, item, Py_LT);
     138        Py_DECREF(litem);
     139        if (res < 0)
     140            return -1;
     141        if (res)
     142            lo = mid + 1;
     143        else
     144            hi = mid;
     145    }
     146    return lo;
    139147}
    140148
    … …  
    142150bisect_left(PyObject *self, PyObject *args, PyObject *kw)
    143151{
    144         PyObject *list, *item;
    145         Py_ssize_t lo = 0;
    146         Py_ssize_t hi = -1;
    147         Py_ssize_t index;
    148         static char *keywords[] = {"a", "x", "lo", "hi", NULL};
    149 
    150         if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn:bisect_left",
    151                 keywords, &list, &item, &lo, &hi))
    152                 return NULL;
    153         index = internal_bisect_left(list, item, lo, hi);
    154         if (index < 0)
    155                 return NULL;
    156         return PyInt_FromSsize_t(index);
     152    PyObject *list, *item;
     153    Py_ssize_t lo = 0;
     154    Py_ssize_t hi = -1;
     155    Py_ssize_t index;
     156    static char *keywords[] = {"a", "x", "lo", "hi", NULL};
     157
     158    if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn:bisect_left",
     159        keywords, &list, &item, &lo, &hi))
     160        return NULL;
     161    index = internal_bisect_left(list, item, lo, hi);
     162    if (index < 0)
     163        return NULL;
     164    return PyInt_FromSsize_t(index);
    157165}
    158166
    … …  
    172180insort_left(PyObject *self, PyObject *args, PyObject *kw)
    173181{
    174         PyObject *list, *item, *result;
    175         Py_ssize_t lo = 0;
    176         Py_ssize_t hi = -1;
    177         Py_ssize_t index;
    178         static char *keywords[] = {"a", "x", "lo", "hi", NULL};
    179 
    180         if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn:insort_left",
    181                 keywords, &list, &item, &lo, &hi))
    182                 return NULL;
    183         index = internal_bisect_left(list, item, lo, hi);
    184         if (index < 0)
    185                 return NULL;
    186         if (PyList_CheckExact(list)) {
    187                 if (PyList_Insert(list, index, item) < 0)
    188                         return NULL;
    189         } else {
    190                 result = PyObject_CallMethod(list, "insert", "iO",
    191                                              index, item);
    192                 if (result == NULL)
    193                         return NULL;
    194                 Py_DECREF(result);
    195         }
    196 
    197         Py_RETURN_NONE;
     182    PyObject *list, *item, *result;
     183    Py_ssize_t lo = 0;
     184    Py_ssize_t hi = -1;
     185    Py_ssize_t index;
     186    static char *keywords[] = {"a", "x", "lo", "hi", NULL};
     187
     188    if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn:insort_left",
     189        keywords, &list, &item, &lo, &hi))
     190        return NULL;
     191    index = internal_bisect_left(list, item, lo, hi);
     192    if (index < 0)
     193        return NULL;
     194    if (PyList_CheckExact(list)) {
     195        if (PyList_Insert(list, index, item) < 0)
     196            return NULL;
     197    } else {
     198        result = PyObject_CallMethod(list, "insert", "nO",
     199                                     index, item);
     200        if (result == NULL)
     201            return NULL;
     202        Py_DECREF(result);
     203    }
     204
     205    Py_RETURN_NONE;
    198206}
    199207
    … …  
    208216slice of a to be searched.\n");
    209217
    210 PyDoc_STRVAR(bisect_doc, "Alias for bisect_right().\n");
    211 PyDoc_STRVAR(insort_doc, "Alias for insort_right().\n");
    212 
    213218static PyMethodDef bisect_methods[] = {
    214         {"bisect_right", (PyCFunction)bisect_right,
    215                 METH_VARARGS|METH_KEYWORDS, bisect_right_doc},
    216         {"bisect", (PyCFunction)bisect_right,
    217                 METH_VARARGS|METH_KEYWORDS, bisect_doc},
    218         {"insort_right", (PyCFunction)insort_right,
    219                 METH_VARARGS|METH_KEYWORDS, insort_right_doc},
    220         {"insort", (PyCFunction)insort_right,
    221                 METH_VARARGS|METH_KEYWORDS, insort_doc},
    222         {"bisect_left", (PyCFunction)bisect_left,
    223                 METH_VARARGS|METH_KEYWORDS, bisect_left_doc},
    224         {"insort_left", (PyCFunction)insort_left,
    225                 METH_VARARGS|METH_KEYWORDS, insort_left_doc},
    226         {NULL, NULL} /* sentinel */
     219    {"bisect_right", (PyCFunction)bisect_right,
     220        METH_VARARGS|METH_KEYWORDS, bisect_right_doc},
     221    {"bisect", (PyCFunction)bisect_right,
     222        METH_VARARGS|METH_KEYWORDS, bisect_right_doc},
     223    {"insort_right", (PyCFunction)insort_right,
     224        METH_VARARGS|METH_KEYWORDS, insort_right_doc},
     225    {"insort", (PyCFunction)insort_right,
     226        METH_VARARGS|METH_KEYWORDS, insort_right_doc},
     227    {"bisect_left", (PyCFunction)bisect_left,
     228        METH_VARARGS|METH_KEYWORDS, bisect_left_doc},
     229    {"insort_left", (PyCFunction)insort_left,
     230        METH_VARARGS|METH_KEYWORDS, insort_left_doc},
     231    {NULL, NULL} /* sentinel */
    227232};
    228233
    … …  
    238243init_bisect(void)
    239244{
    240         PyObject *m;
    241 
    242         m = Py_InitModule3("_bisect", bisect_methods, module_doc);
    243 }
     245    Py_InitModule3("_bisect", bisect_methods, module_doc);
     246}
Note: See TracChangeset for help on using the changeset viewer.