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/_heapqmodule.c

    r2 r391  
    1 /* Drop in replacement for heapq.py 
     1/* Drop in replacement for heapq.py
    22
    33C implementation derived directly from heapq.py in Py2.3
    44which was written by Kevin O'Connor, augmented by Tim Peters,
    5 annotated by François Pinard, and converted to C by Raymond Hettinger.
     5annotated by François Pinard, and converted to C by Raymond Hettinger.
    66
    77*/
    … …  
    1212   Py_LT so it will match min(), sorted(), and bisect().  Unfortunately, some
    1313   client code (Twisted for example) relied on Py_LE, so this little function
    14    restores compatability by trying both.
     14   restores compatibility by trying both.
    1515*/
    1616static int
    1717cmp_lt(PyObject *x, PyObject *y)
    1818{
    19         int cmp;
    20         static PyObject *lt = NULL;
    21 
    22         if (lt == NULL) {
    23                 lt = PyString_FromString("__lt__");
    24                 if (lt == NULL)
    25                         return -1;
    26         }
    27         if (PyObject_HasAttr(x, lt))
    28                 return PyObject_RichCompareBool(x, y, Py_LT);
    29         cmp = PyObject_RichCompareBool(y, x, Py_LE);
    30         if (cmp != -1)
    31                 cmp = 1 - cmp;
    32         return cmp;
     19    int cmp;
     20    static PyObject *lt = NULL;
     21
     22    if (lt == NULL) {
     23        lt = PyString_FromString("__lt__");
     24        if (lt == NULL)
     25            return -1;
     26    }
     27    if (PyObject_HasAttr(x, lt))
     28        return PyObject_RichCompareBool(x, y, Py_LT);
     29    cmp = PyObject_RichCompareBool(y, x, Py_LE);
     30    if (cmp != -1)
     31        cmp = 1 - cmp;
     32    return cmp;
    3333}
    3434
    … …  
    3636_siftdown(PyListObject *heap, Py_ssize_t startpos, Py_ssize_t pos)
    3737{
    38         PyObject *newitem, *parent;
    39         int cmp;
    40         Py_ssize_t parentpos;
    41 
    42         assert(PyList_Check(heap));
    43         if (pos >= PyList_GET_SIZE(heap)) {
    44                 PyErr_SetString(PyExc_IndexError, "index out of range");
    45                 return -1;
    46         }
    47 
    48         newitem = PyList_GET_ITEM(heap, pos);
    49         Py_INCREF(newitem);
    50         /* Follow the path to the root, moving parents down until finding
    51            a place newitem fits. */
    52         while (pos > startpos){
    53                 parentpos = (pos - 1) >> 1;
    54                 parent = PyList_GET_ITEM(heap, parentpos);
    55                 cmp = cmp_lt(newitem, parent);
    56                 if (cmp == -1) {
    57                         Py_DECREF(newitem);
    58                         return -1;
    59                 }
    60                 if (cmp == 0)
    61                         break;
    62                 Py_INCREF(parent);
    63                 Py_DECREF(PyList_GET_ITEM(heap, pos));
    64                 PyList_SET_ITEM(heap, pos, parent);
    65                 pos = parentpos;
    66         }
    67         Py_DECREF(PyList_GET_ITEM(heap, pos));
    68         PyList_SET_ITEM(heap, pos, newitem);
    69         return 0;
     38    PyObject *newitem, *parent, *olditem;
     39    int cmp;
     40    Py_ssize_t parentpos;
     41    Py_ssize_t size;
     42
     43    assert(PyList_Check(heap));
     44    size = PyList_GET_SIZE(heap);
     45    if (pos >= size) {
     46        PyErr_SetString(PyExc_IndexError, "index out of range");
     47        return -1;
     48    }
     49
     50    newitem = PyList_GET_ITEM(heap, pos);
     51    Py_INCREF(newitem);
     52    /* Follow the path to the root, moving parents down until finding
     53       a place newitem fits. */
     54    while (pos > startpos){
     55        parentpos = (pos - 1) >> 1;
     56        parent = PyList_GET_ITEM(heap, parentpos);
     57        cmp = cmp_lt(newitem, parent);
     58        if (cmp == -1) {
     59            Py_DECREF(newitem);
     60            return -1;
     61        }
     62        if (size != PyList_GET_SIZE(heap)) {
     63            Py_DECREF(newitem);
     64            PyErr_SetString(PyExc_RuntimeError,
     65                            "list changed size during iteration");
     66            return -1;
     67        }
     68        if (cmp == 0)
     69            break;
     70        Py_INCREF(parent);
     71        olditem = PyList_GET_ITEM(heap, pos);
     72        PyList_SET_ITEM(heap, pos, parent);
     73        Py_DECREF(olditem);
     74        pos = parentpos;
     75        if (size != PyList_GET_SIZE(heap)) {
     76            PyErr_SetString(PyExc_RuntimeError,
     77                            "list changed size during iteration");
     78            return -1;
     79        }
     80    }
     81    Py_DECREF(PyList_GET_ITEM(heap, pos));
     82    PyList_SET_ITEM(heap, pos, newitem);
     83    return 0;
    7084}
    7185
    … …  
    7387_siftup(PyListObject *heap, Py_ssize_t pos)
    7488{
    75         Py_ssize_t startpos, endpos, childpos, rightpos;
    76         int cmp;
    77         PyObject *newitem, *tmp;
    78 
    79         assert(PyList_Check(heap));
    80         endpos = PyList_GET_SIZE(heap);
    81         startpos = pos;
    82         if (pos >= endpos) {
    83                 PyErr_SetString(PyExc_IndexError, "index out of range");
    84                 return -1;
    85         }
    86         newitem = PyList_GET_ITEM(heap, pos);
    87         Py_INCREF(newitem);
    88 
    89         /* Bubble up the smaller child until hitting a leaf. */
    90         childpos = 2*pos + 1;    /* leftmost child position  */
    91         while (childpos < endpos) {
    92                 /* Set childpos to index of smaller child.   */
    93                 rightpos = childpos + 1;
    94                 if (rightpos < endpos) {
    95                         cmp = cmp_lt(
    96                                 PyList_GET_ITEM(heap, childpos),
    97                                 PyList_GET_ITEM(heap, rightpos));
    98                         if (cmp == -1) {
    99                                 Py_DECREF(newitem);
    100                                 return -1;
    101                         }
    102                         if (cmp == 0)
    103                                 childpos = rightpos;
    104                 }
    105                 /* Move the smaller child up. */
    106                 tmp = PyList_GET_ITEM(heap, childpos);
    107                 Py_INCREF(tmp);
    108                 Py_DECREF(PyList_GET_ITEM(heap, pos));
    109                 PyList_SET_ITEM(heap, pos, tmp);
    110                 pos = childpos;
    111                 childpos = 2*pos + 1;
    112         }
    113 
    114         /* The leaf at pos is empty now.  Put newitem there, and and bubble
    115            it up to its final resting place (by sifting its parents down). */
    116         Py_DECREF(PyList_GET_ITEM(heap, pos));
    117         PyList_SET_ITEM(heap, pos, newitem);
    118         return _siftdown(heap, startpos, pos);
     89    Py_ssize_t startpos, endpos, childpos, rightpos;
     90    int cmp;
     91    PyObject *newitem, *tmp, *olditem;
     92    Py_ssize_t size;
     93
     94    assert(PyList_Check(heap));
     95    size = PyList_GET_SIZE(heap);
     96    endpos = size;
     97    startpos = pos;
     98    if (pos >= endpos) {
     99        PyErr_SetString(PyExc_IndexError, "index out of range");
     100        return -1;
     101    }
     102    newitem = PyList_GET_ITEM(heap, pos);
     103    Py_INCREF(newitem);
     104
     105    /* Bubble up the smaller child until hitting a leaf. */
     106    childpos = 2*pos + 1;    /* leftmost child position  */
     107    while (childpos < endpos) {
     108        /* Set childpos to index of smaller child.   */
     109        rightpos = childpos + 1;
     110        if (rightpos < endpos) {
     111            cmp = cmp_lt(
     112                PyList_GET_ITEM(heap, childpos),
     113                PyList_GET_ITEM(heap, rightpos));
     114            if (cmp == -1) {
     115                Py_DECREF(newitem);
     116                return -1;
     117            }
     118            if (cmp == 0)
     119                childpos = rightpos;
     120        }
     121        if (size != PyList_GET_SIZE(heap)) {
     122            Py_DECREF(newitem);
     123            PyErr_SetString(PyExc_RuntimeError,
     124                            "list changed size during iteration");
     125            return -1;
     126        }
     127        /* Move the smaller child up. */
     128        tmp = PyList_GET_ITEM(heap, childpos);
     129        Py_INCREF(tmp);
     130        olditem = PyList_GET_ITEM(heap, pos);
     131        PyList_SET_ITEM(heap, pos, tmp);
     132        Py_DECREF(olditem);
     133        pos = childpos;
     134        childpos = 2*pos + 1;
     135        if (size != PyList_GET_SIZE(heap)) {
     136            PyErr_SetString(PyExc_RuntimeError,
     137                            "list changed size during iteration");
     138            return -1;
     139        }
     140    }
     141
     142    /* The leaf at pos is empty now.  Put newitem there, and bubble
     143       it up to its final resting place (by sifting its parents down). */
     144    Py_DECREF(PyList_GET_ITEM(heap, pos));
     145    PyList_SET_ITEM(heap, pos, newitem);
     146    return _siftdown(heap, startpos, pos);
    119147}
    120148
    … …  
    122150heappush(PyObject *self, PyObject *args)
    123151{
    124         PyObject *heap, *item;
    125 
    126         if (!PyArg_UnpackTuple(args, "heappush", 2, 2, &heap, &item))
    127                 return NULL;
    128 
    129         if (!PyList_Check(heap)) {
    130                 PyErr_SetString(PyExc_TypeError, "heap argument must be a list");
    131                 return NULL;
    132         }
    133 
    134         if (PyList_Append(heap, item) == -1)
    135                 return NULL;
    136 
    137         if (_siftdown((PyListObject *)heap, 0, PyList_GET_SIZE(heap)-1) == -1)
    138                 return NULL;
    139         Py_INCREF(Py_None);
    140         return Py_None;
     152    PyObject *heap, *item;
     153
     154    if (!PyArg_UnpackTuple(args, "heappush", 2, 2, &heap, &item))
     155        return NULL;
     156
     157    if (!PyList_Check(heap)) {
     158        PyErr_SetString(PyExc_TypeError, "heap argument must be a list");
     159        return NULL;
     160    }
     161
     162    if (PyList_Append(heap, item) == -1)
     163        return NULL;
     164
     165    if (_siftdown((PyListObject *)heap, 0, PyList_GET_SIZE(heap)-1) == -1)
     166        return NULL;
     167    Py_INCREF(Py_None);
     168    return Py_None;
    141169}
    142170
    143171PyDoc_STRVAR(heappush_doc,
    144 "Push item onto heap, maintaining the heap invariant.");
     172"heappush(heap, item) -> None. Push item onto heap, maintaining the heap invariant.");
    145173
    146174static PyObject *
    147175heappop(PyObject *self, PyObject *heap)
    148176{
    149         PyObject *lastelt, *returnitem;
    150         Py_ssize_t n;
    151 
    152         if (!PyList_Check(heap)) {
    153                 PyErr_SetString(PyExc_TypeError, "heap argument must be a list");
    154                 return NULL;
    155         }
    156 
    157         /* # raises appropriate IndexError if heap is empty */
    158         n = PyList_GET_SIZE(heap);
    159         if (n == 0) {
    160                 PyErr_SetString(PyExc_IndexError, "index out of range");
    161                 return NULL;
    162         }
    163 
    164         lastelt = PyList_GET_ITEM(heap, n-1) ;
    165         Py_INCREF(lastelt);
    166         PyList_SetSlice(heap, n-1, n, NULL);
    167         n--;
    168 
    169         if (!n)
    170                 return lastelt;
    171         returnitem = PyList_GET_ITEM(heap, 0);
    172         PyList_SET_ITEM(heap, 0, lastelt);
    173         if (_siftup((PyListObject *)heap, 0) == -1) {
    174                 Py_DECREF(returnitem);
    175                 return NULL;
    176         }
    177         return returnitem;
     177    PyObject *lastelt, *returnitem;
     178    Py_ssize_t n;
     179
     180    if (!PyList_Check(heap)) {
     181        PyErr_SetString(PyExc_TypeError, "heap argument must be a list");
     182        return NULL;
     183    }
     184
     185    /* # raises appropriate IndexError if heap is empty */
     186    n = PyList_GET_SIZE(heap);
     187    if (n == 0) {
     188        PyErr_SetString(PyExc_IndexError, "index out of range");
     189        return NULL;
     190    }
     191
     192    lastelt = PyList_GET_ITEM(heap, n-1) ;
     193    Py_INCREF(lastelt);
     194    PyList_SetSlice(heap, n-1, n, NULL);
     195    n--;
     196
     197    if (!n)
     198        return lastelt;
     199    returnitem = PyList_GET_ITEM(heap, 0);
     200    PyList_SET_ITEM(heap, 0, lastelt);
     201    if (_siftup((PyListObject *)heap, 0) == -1) {
     202        Py_DECREF(returnitem);
     203        return NULL;
     204    }
     205    return returnitem;
    178206}
    179207
    … …  
    184212heapreplace(PyObject *self, PyObject *args)
    185213{
    186         PyObject *heap, *item, *returnitem;
    187 
    188         if (!PyArg_UnpackTuple(args, "heapreplace", 2, 2, &heap, &item))
    189                 return NULL;
    190 
    191         if (!PyList_Check(heap)) {
    192                 PyErr_SetString(PyExc_TypeError, "heap argument must be a list");
    193                 return NULL;
    194         }
    195 
    196         if (PyList_GET_SIZE(heap) < 1) {
    197                 PyErr_SetString(PyExc_IndexError, "index out of range");
    198                 return NULL;
    199         }
    200 
    201         returnitem = PyList_GET_ITEM(heap, 0);
    202         Py_INCREF(item);
    203         PyList_SET_ITEM(heap, 0, item);
    204         if (_siftup((PyListObject *)heap, 0) == -1) {
    205                 Py_DECREF(returnitem);
    206                 return NULL;
    207         }
    208         return returnitem;
     214    PyObject *heap, *item, *returnitem;
     215
     216    if (!PyArg_UnpackTuple(args, "heapreplace", 2, 2, &heap, &item))
     217        return NULL;
     218
     219    if (!PyList_Check(heap)) {
     220        PyErr_SetString(PyExc_TypeError, "heap argument must be a list");
     221        return NULL;
     222    }
     223
     224    if (PyList_GET_SIZE(heap) < 1) {
     225        PyErr_SetString(PyExc_IndexError, "index out of range");
     226        return NULL;
     227    }
     228
     229    returnitem = PyList_GET_ITEM(heap, 0);
     230    Py_INCREF(item);
     231    PyList_SET_ITEM(heap, 0, item);
     232    if (_siftup((PyListObject *)heap, 0) == -1) {
     233        Py_DECREF(returnitem);
     234        return NULL;
     235    }
     236    return returnitem;
    209237}
    210238
    211239PyDoc_STRVAR(heapreplace_doc,
    212 "Pop and return the current smallest value, and add the new item.\n\
     240"heapreplace(heap, item) -> value. Pop and return the current smallest value, and add the new item.\n\
    213241\n\
    214242This is more efficient than heappop() followed by heappush(), and can be\n\
    … …  
    216244returned may be larger than item!  That constrains reasonable uses of\n\
    217245this routine unless written as part of a conditional replacement:\n\n\
    218         if item > heap[0]:\n\
    219             item = heapreplace(heap, item)\n");
     246    if item > heap[0]:\n\
     247        item = heapreplace(heap, item)\n");
    220248
    221249static PyObject *
    222250heappushpop(PyObject *self, PyObject *args)
    223251{
    224         PyObject *heap, *item, *returnitem;
    225         int cmp;
    226 
    227         if (!PyArg_UnpackTuple(args, "heappushpop", 2, 2, &heap, &item))
    228                 return NULL;
    229 
    230         if (!PyList_Check(heap)) {
    231                 PyErr_SetString(PyExc_TypeError, "heap argument must be a list");
    232                 return NULL;
    233         }
    234 
    235         if (PyList_GET_SIZE(heap) < 1) {
    236                 Py_INCREF(item);
    237                 return item;
    238         }
    239 
    240         cmp = cmp_lt(PyList_GET_ITEM(heap, 0), item);
    241         if (cmp == -1)
    242                 return NULL;
    243         if (cmp == 0) {
    244                 Py_INCREF(item);
    245                 return item;
    246         }
    247 
    248         returnitem = PyList_GET_ITEM(heap, 0);
    249         Py_INCREF(item);
    250         PyList_SET_ITEM(heap, 0, item);
    251         if (_siftup((PyListObject *)heap, 0) == -1) {
    252                 Py_DECREF(returnitem);
    253                 return NULL;
    254         }
    255         return returnitem;
     252    PyObject *heap, *item, *returnitem;
     253    int cmp;
     254
     255    if (!PyArg_UnpackTuple(args, "heappushpop", 2, 2, &heap, &item))
     256        return NULL;
     257
     258    if (!PyList_Check(heap)) {
     259        PyErr_SetString(PyExc_TypeError, "heap argument must be a list");
     260        return NULL;
     261    }
     262
     263    if (PyList_GET_SIZE(heap) < 1) {
     264        Py_INCREF(item);
     265        return item;
     266    }
     267
     268    cmp = cmp_lt(PyList_GET_ITEM(heap, 0), item);
     269    if (cmp == -1)
     270        return NULL;
     271    if (cmp == 0) {
     272        Py_INCREF(item);
     273        return item;
     274    }
     275
     276    returnitem = PyList_GET_ITEM(heap, 0);
     277    Py_INCREF(item);
     278    PyList_SET_ITEM(heap, 0, item);
     279    if (_siftup((PyListObject *)heap, 0) == -1) {
     280        Py_DECREF(returnitem);
     281        return NULL;
     282    }
     283    return returnitem;
    256284}
    257285
    258286PyDoc_STRVAR(heappushpop_doc,
    259 "Push item on the heap, then pop and return the smallest item\n\
     287"heappushpop(heap, item) -> value. Push item on the heap, then pop and return the smallest item\n\
    260288from the heap. The combined action runs more efficiently than\n\
    261289heappush() followed by a separate call to heappop().");
    … …  
    264292heapify(PyObject *self, PyObject *heap)
    265293{
    266         Py_ssize_t i, n;
    267 
    268         if (!PyList_Check(heap)) {
    269                 PyErr_SetString(PyExc_TypeError, "heap argument must be a list");
    270                 return NULL;
    271         }
    272 
    273         n = PyList_GET_SIZE(heap);
    274         /* Transform bottom-up.  The largest index there's any point to
    275            looking at is the largest with a child index in-range, so must
    276            have 2*i + 1 < n, or i < (n-1)/2.  If n is even = 2*j, this is
    277            (2*j-1)/2 = j-1/2 so j-1 is the largest, which is n//2 - 1.  If
    278            n is odd = 2*j+1, this is (2*j+1-1)/2 = j so j-1 is the largest,
    279            and that's again n//2-1.
    280         */
    281         for (i=n/2-1 ; i>=0 ; i--)
    282                 if(_siftup((PyListObject *)heap, i) == -1)
    283                         return NULL;
    284         Py_INCREF(Py_None);
    285         return Py_None;
     294    Py_ssize_t i, n;
     295
     296    if (!PyList_Check(heap)) {
     297        PyErr_SetString(PyExc_TypeError, "heap argument must be a list");
     298        return NULL;
     299    }
     300
     301    n = PyList_GET_SIZE(heap);
     302    /* Transform bottom-up.  The largest index there's any point to
     303       looking at is the largest with a child index in-range, so must
     304       have 2*i + 1 < n, or i < (n-1)/2.  If n is even = 2*j, this is
     305       (2*j-1)/2 = j-1/2 so j-1 is the largest, which is n//2 - 1.  If
     306       n is odd = 2*j+1, this is (2*j+1-1)/2 = j so j-1 is the largest,
     307       and that's again n//2-1.
     308    */
     309    for (i=n/2-1 ; i>=0 ; i--)
     310        if(_siftup((PyListObject *)heap, i) == -1)
     311            return NULL;
     312    Py_INCREF(Py_None);
     313    return Py_None;
    286314}
    287315
    … …  
    292320nlargest(PyObject *self, PyObject *args)
    293321{
    294         PyObject *heap=NULL, *elem, *iterable, *sol, *it, *oldelem;
    295         Py_ssize_t i, n;
    296         int cmp;
    297 
    298         if (!PyArg_ParseTuple(args, "nO:nlargest", &n, &iterable))
    299                 return NULL;
    300 
    301         it = PyObject_GetIter(iterable);
    302         if (it == NULL)
    303                 return NULL;
    304 
    305         heap = PyList_New(0);
    306         if (heap == NULL)
    307                 goto fail;
    308 
    309         for (i=0 ; i<n ; i++ ){
    310                 elem = PyIter_Next(it);
    311                 if (elem == NULL) {
    312                         if (PyErr_Occurred())
    313                                 goto fail;
    314                         else
    315                                 goto sortit;
    316                 }
    317                 if (PyList_Append(heap, elem) == -1) {
    318                         Py_DECREF(elem);
    319                         goto fail;
    320                 }
    321                 Py_DECREF(elem);
    322         }
    323         if (PyList_GET_SIZE(heap) == 0)
    324                 goto sortit;
    325 
    326         for (i=n/2-1 ; i>=0 ; i--)
    327                 if(_siftup((PyListObject *)heap, i) == -1)
    328                         goto fail;
    329 
    330         sol = PyList_GET_ITEM(heap, 0);
    331         while (1) {
    332                 elem = PyIter_Next(it);
    333                 if (elem == NULL) {
    334                         if (PyErr_Occurred())
    335                                 goto fail;
    336                         else
    337                                 goto sortit;
    338                 }
    339                 cmp = cmp_lt(sol, elem);
    340                 if (cmp == -1) {
    341                         Py_DECREF(elem);
    342                         goto fail;
    343                 }
    344                 if (cmp == 0) {
    345                         Py_DECREF(elem);
    346                         continue;
    347                 }
    348                 oldelem = PyList_GET_ITEM(heap, 0);
    349                 PyList_SET_ITEM(heap, 0, elem);
    350                 Py_DECREF(oldelem);
    351                 if (_siftup((PyListObject *)heap, 0) == -1)
    352                         goto fail;
    353                 sol = PyList_GET_ITEM(heap, 0);
    354         }
     322    PyObject *heap=NULL, *elem, *iterable, *sol, *it, *oldelem;
     323    Py_ssize_t i, n;
     324    int cmp;
     325
     326    if (!PyArg_ParseTuple(args, "nO:nlargest", &n, &iterable))
     327        return NULL;
     328
     329    it = PyObject_GetIter(iterable);
     330    if (it == NULL)
     331        return NULL;
     332
     333    heap = PyList_New(0);
     334    if (heap == NULL)
     335        goto fail;
     336
     337    for (i=0 ; i<n ; i++ ){
     338        elem = PyIter_Next(it);
     339        if (elem == NULL) {
     340            if (PyErr_Occurred())
     341                goto fail;
     342            else
     343                goto sortit;
     344        }
     345        if (PyList_Append(heap, elem) == -1) {
     346            Py_DECREF(elem);
     347            goto fail;
     348        }
     349        Py_DECREF(elem);
     350    }
     351    if (PyList_GET_SIZE(heap) == 0)
     352        goto sortit;
     353
     354    for (i=n/2-1 ; i>=0 ; i--)
     355        if(_siftup((PyListObject *)heap, i) == -1)
     356            goto fail;
     357
     358    sol = PyList_GET_ITEM(heap, 0);
     359    while (1) {
     360        elem = PyIter_Next(it);
     361        if (elem == NULL) {
     362            if (PyErr_Occurred())
     363                goto fail;
     364            else
     365                goto sortit;
     366        }
     367        cmp = cmp_lt(sol, elem);
     368        if (cmp == -1) {
     369            Py_DECREF(elem);
     370            goto fail;
     371        }
     372        if (cmp == 0) {
     373            Py_DECREF(elem);
     374            continue;
     375        }
     376        oldelem = PyList_GET_ITEM(heap, 0);
     377        PyList_SET_ITEM(heap, 0, elem);
     378        Py_DECREF(oldelem);
     379        if (_siftup((PyListObject *)heap, 0) == -1)
     380            goto fail;
     381        sol = PyList_GET_ITEM(heap, 0);
     382    }
    355383sortit:
    356         if (PyList_Sort(heap) == -1)
    357                 goto fail;
    358         if (PyList_Reverse(heap) == -1)
    359                 goto fail;
    360         Py_DECREF(it);
    361         return heap;
     384    if (PyList_Sort(heap) == -1)
     385        goto fail;
     386    if (PyList_Reverse(heap) == -1)
     387        goto fail;
     388    Py_DECREF(it);
     389    return heap;
    362390
    363391fail:
    364         Py_DECREF(it);
    365         Py_XDECREF(heap);
    366         return NULL;
     392    Py_DECREF(it);
     393    Py_XDECREF(heap);
     394    return NULL;
    367395}
    368396
    … …  
    375403_siftdownmax(PyListObject *heap, Py_ssize_t startpos, Py_ssize_t pos)
    376404{
    377         PyObject *newitem, *parent;
    378         int cmp;
    379         Py_ssize_t parentpos;
    380 
    381         assert(PyList_Check(heap));
    382         if (pos >= PyList_GET_SIZE(heap)) {
    383                 PyErr_SetString(PyExc_IndexError, "index out of range");
    384                 return -1;
    385         }
    386 
    387         newitem = PyList_GET_ITEM(heap, pos);
    388         Py_INCREF(newitem);
    389         /* Follow the path to the root, moving parents down until finding
    390            a place newitem fits. */
    391         while (pos > startpos){
    392                 parentpos = (pos - 1) >> 1;
    393                 parent = PyList_GET_ITEM(heap, parentpos);
    394                 cmp = cmp_lt(parent, newitem);
    395                 if (cmp == -1) {
    396                         Py_DECREF(newitem);
    397                         return -1;
    398                 }
    399                 if (cmp == 0)
    400                         break;
    401                 Py_INCREF(parent);
    402                 Py_DECREF(PyList_GET_ITEM(heap, pos));
    403                 PyList_SET_ITEM(heap, pos, parent);
    404                 pos = parentpos;
    405         }
    406         Py_DECREF(PyList_GET_ITEM(heap, pos));
    407         PyList_SET_ITEM(heap, pos, newitem);
    408         return 0;
     405    PyObject *newitem, *parent;
     406    int cmp;
     407    Py_ssize_t parentpos;
     408
     409    assert(PyList_Check(heap));
     410    if (pos >= PyList_GET_SIZE(heap)) {
     411        PyErr_SetString(PyExc_IndexError, "index out of range");
     412        return -1;
     413    }
     414
     415    newitem = PyList_GET_ITEM(heap, pos);
     416    Py_INCREF(newitem);
     417    /* Follow the path to the root, moving parents down until finding
     418       a place newitem fits. */
     419    while (pos > startpos){
     420        parentpos = (pos - 1) >> 1;
     421        parent = PyList_GET_ITEM(heap, parentpos);
     422        cmp = cmp_lt(parent, newitem);
     423        if (cmp == -1) {
     424            Py_DECREF(newitem);
     425            return -1;
     426        }
     427        if (cmp == 0)
     428            break;
     429        Py_INCREF(parent);
     430        Py_DECREF(PyList_GET_ITEM(heap, pos));
     431        PyList_SET_ITEM(heap, pos, parent);
     432        pos = parentpos;
     433    }
     434    Py_DECREF(PyList_GET_ITEM(heap, pos));
     435    PyList_SET_ITEM(heap, pos, newitem);
     436    return 0;
    409437}
    410438
    … …  
    412440_siftupmax(PyListObject *heap, Py_ssize_t pos)
    413441{
    414         Py_ssize_t startpos, endpos, childpos, rightpos;
    415         int cmp;
    416         PyObject *newitem, *tmp;
    417 
    418         assert(PyList_Check(heap));
    419         endpos = PyList_GET_SIZE(heap);
    420         startpos = pos;
    421         if (pos >= endpos) {
    422                 PyErr_SetString(PyExc_IndexError, "index out of range");
    423                 return -1;
    424         }
    425         newitem = PyList_GET_ITEM(heap, pos);
    426         Py_INCREF(newitem);
    427 
    428         /* Bubble up the smaller child until hitting a leaf. */
    429         childpos = 2*pos + 1;    /* leftmost child position  */
    430         while (childpos < endpos) {
    431                 /* Set childpos to index of smaller child.   */
    432                 rightpos = childpos + 1;
    433                 if (rightpos < endpos) {
    434                         cmp = cmp_lt(
    435                                 PyList_GET_ITEM(heap, rightpos),
    436                                 PyList_GET_ITEM(heap, childpos));
    437                         if (cmp == -1) {
    438                                 Py_DECREF(newitem);
    439                                 return -1;
    440                         }
    441                         if (cmp == 0)
    442                                 childpos = rightpos;
    443                 }
    444                 /* Move the smaller child up. */
    445                 tmp = PyList_GET_ITEM(heap, childpos);
    446                 Py_INCREF(tmp);
    447                 Py_DECREF(PyList_GET_ITEM(heap, pos));
    448                 PyList_SET_ITEM(heap, pos, tmp);
    449                 pos = childpos;
    450                 childpos = 2*pos + 1;
    451         }
    452 
    453         /* The leaf at pos is empty now.  Put newitem there, and and bubble
    454            it up to its final resting place (by sifting its parents down). */
    455         Py_DECREF(PyList_GET_ITEM(heap, pos));
    456         PyList_SET_ITEM(heap, pos, newitem);
    457         return _siftdownmax(heap, startpos, pos);
     442    Py_ssize_t startpos, endpos, childpos, rightpos;
     443    int cmp;
     444    PyObject *newitem, *tmp;
     445
     446    assert(PyList_Check(heap));
     447    endpos = PyList_GET_SIZE(heap);
     448    startpos = pos;
     449    if (pos >= endpos) {
     450        PyErr_SetString(PyExc_IndexError, "index out of range");
     451        return -1;
     452    }
     453    newitem = PyList_GET_ITEM(heap, pos);
     454    Py_INCREF(newitem);
     455
     456    /* Bubble up the smaller child until hitting a leaf. */
     457    childpos = 2*pos + 1;    /* leftmost child position  */
     458    while (childpos < endpos) {
     459        /* Set childpos to index of smaller child.   */
     460        rightpos = childpos + 1;
     461        if (rightpos < endpos) {
     462            cmp = cmp_lt(
     463                PyList_GET_ITEM(heap, rightpos),
     464                PyList_GET_ITEM(heap, childpos));
     465            if (cmp == -1) {
     466                Py_DECREF(newitem);
     467                return -1;
     468            }
     469            if (cmp == 0)
     470                childpos = rightpos;
     471        }
     472        /* Move the smaller child up. */
     473        tmp = PyList_GET_ITEM(heap, childpos);
     474        Py_INCREF(tmp);
     475        Py_DECREF(PyList_GET_ITEM(heap, pos));
     476        PyList_SET_ITEM(heap, pos, tmp);
     477        pos = childpos;
     478        childpos = 2*pos + 1;
     479    }
     480
     481    /* The leaf at pos is empty now.  Put newitem there, and bubble
     482       it up to its final resting place (by sifting its parents down). */
     483    Py_DECREF(PyList_GET_ITEM(heap, pos));
     484    PyList_SET_ITEM(heap, pos, newitem);
     485    return _siftdownmax(heap, startpos, pos);
    458486}
    459487
    … …  
    461489nsmallest(PyObject *self, PyObject *args)
    462490{
    463         PyObject *heap=NULL, *elem, *iterable, *los, *it, *oldelem;
    464         Py_ssize_t i, n;
    465         int cmp;
    466 
    467         if (!PyArg_ParseTuple(args, "nO:nsmallest", &n, &iterable))
    468                 return NULL;
    469 
    470         it = PyObject_GetIter(iterable);
    471         if (it == NULL)
    472                 return NULL;
    473 
    474         heap = PyList_New(0);
    475         if (heap == NULL)
    476                 goto fail;
    477 
    478         for (i=0 ; i<n ; i++ ){
    479                 elem = PyIter_Next(it);
    480                 if (elem == NULL) {
    481                         if (PyErr_Occurred())
    482                                 goto fail;
    483                         else
    484                                 goto sortit;
    485                 }
    486                 if (PyList_Append(heap, elem) == -1) {
    487                         Py_DECREF(elem);
    488                         goto fail;
    489                 }
    490                 Py_DECREF(elem);
    491         }
    492         n = PyList_GET_SIZE(heap);
    493         if (n == 0)
    494                 goto sortit;
    495 
    496         for (i=n/2-1 ; i>=0 ; i--)
    497                 if(_siftupmax((PyListObject *)heap, i) == -1)
    498                         goto fail;
    499 
    500         los = PyList_GET_ITEM(heap, 0);
    501         while (1) {
    502                 elem = PyIter_Next(it);
    503                 if (elem == NULL) {
    504                         if (PyErr_Occurred())
    505                                 goto fail;
    506                         else
    507                                 goto sortit;
    508                 }
    509                 cmp = cmp_lt(elem, los);
    510                 if (cmp == -1) {
    511                         Py_DECREF(elem);
    512                         goto fail;
    513                 }
    514                 if (cmp == 0) {
    515                         Py_DECREF(elem);
    516                         continue;
    517                 }
    518 
    519                 oldelem = PyList_GET_ITEM(heap, 0);
    520                 PyList_SET_ITEM(heap, 0, elem);
    521                 Py_DECREF(oldelem);
    522                 if (_siftupmax((PyListObject *)heap, 0) == -1)
    523                         goto fail;
    524                 los = PyList_GET_ITEM(heap, 0);
    525         }
     491    PyObject *heap=NULL, *elem, *iterable, *los, *it, *oldelem;
     492    Py_ssize_t i, n;
     493    int cmp;
     494
     495    if (!PyArg_ParseTuple(args, "nO:nsmallest", &n, &iterable))
     496        return NULL;
     497
     498    it = PyObject_GetIter(iterable);
     499    if (it == NULL)
     500        return NULL;
     501
     502    heap = PyList_New(0);
     503    if (heap == NULL)
     504        goto fail;
     505
     506    for (i=0 ; i<n ; i++ ){
     507        elem = PyIter_Next(it);
     508        if (elem == NULL) {
     509            if (PyErr_Occurred())
     510                goto fail;
     511            else
     512                goto sortit;
     513        }
     514        if (PyList_Append(heap, elem) == -1) {
     515            Py_DECREF(elem);
     516            goto fail;
     517        }
     518        Py_DECREF(elem);
     519    }
     520    n = PyList_GET_SIZE(heap);
     521    if (n == 0)
     522        goto sortit;
     523
     524    for (i=n/2-1 ; i>=0 ; i--)
     525        if(_siftupmax((PyListObject *)heap, i) == -1)
     526            goto fail;
     527
     528    los = PyList_GET_ITEM(heap, 0);
     529    while (1) {
     530        elem = PyIter_Next(it);
     531        if (elem == NULL) {
     532            if (PyErr_Occurred())
     533                goto fail;
     534            else
     535                goto sortit;
     536        }
     537        cmp = cmp_lt(elem, los);
     538        if (cmp == -1) {
     539            Py_DECREF(elem);
     540            goto fail;
     541        }
     542        if (cmp == 0) {
     543            Py_DECREF(elem);
     544            continue;
     545        }
     546
     547        oldelem = PyList_GET_ITEM(heap, 0);
     548        PyList_SET_ITEM(heap, 0, elem);
     549        Py_DECREF(oldelem);
     550        if (_siftupmax((PyListObject *)heap, 0) == -1)
     551            goto fail;
     552        los = PyList_GET_ITEM(heap, 0);
     553    }
    526554
    527555sortit:
    528         if (PyList_Sort(heap) == -1)
    529                 goto fail;
    530         Py_DECREF(it);
    531         return heap;
     556    if (PyList_Sort(heap) == -1)
     557        goto fail;
     558    Py_DECREF(it);
     559    return heap;
    532560
    533561fail:
    534         Py_DECREF(it);
    535         Py_XDECREF(heap);
    536         return NULL;
     562    Py_DECREF(it);
     563    Py_XDECREF(heap);
     564    return NULL;
    537565}
    538566
    … …  
    543571
    544572static PyMethodDef heapq_methods[] = {
    545         {"heappush",    (PyCFunction)heappush,         
    546                 METH_VARARGS,   heappush_doc},
    547         {"heappushpop", (PyCFunction)heappushpop,               
    548                 METH_VARARGS,   heappushpop_doc},
    549         {"heappop",     (PyCFunction)heappop,
    550                 METH_O,         heappop_doc},
    551         {"heapreplace", (PyCFunction)heapreplace,
    552                 METH_VARARGS,   heapreplace_doc},
    553         {"heapify",     (PyCFunction)heapify,
    554                 METH_O,         heapify_doc},
    555         {"nlargest",    (PyCFunction)nlargest,
    556                 METH_VARARGS,   nlargest_doc},
    557         {"nsmallest",   (PyCFunction)nsmallest,
    558                 METH_VARARGS,   nsmallest_doc},
    559         {NULL,          NULL}           /* sentinel */
     573    {"heappush",        (PyCFunction)heappush,
     574        METH_VARARGS,           heappush_doc},
     575    {"heappushpop",     (PyCFunction)heappushpop,
     576        METH_VARARGS,           heappushpop_doc},
     577    {"heappop",         (PyCFunction)heappop,
     578        METH_O,                 heappop_doc},
     579    {"heapreplace",     (PyCFunction)heapreplace,
     580        METH_VARARGS,           heapreplace_doc},
     581    {"heapify",         (PyCFunction)heapify,
     582        METH_O,                 heapify_doc},
     583    {"nlargest",        (PyCFunction)nlargest,
     584        METH_VARARGS,           nlargest_doc},
     585    {"nsmallest",       (PyCFunction)nsmallest,
     586        METH_VARARGS,           nsmallest_doc},
     587    {NULL,              NULL}           /* sentinel */
    560588};
    561589
    … …  
    688716init_heapq(void)
    689717{
    690         PyObject *m;
    691 
    692         m = Py_InitModule3("_heapq", heapq_methods, module_doc);
    693         if (m == NULL)
    694                 return;
    695         PyModule_AddObject(m, "__about__", PyString_FromString(__about__));
    696 }
    697 
     718    PyObject *m;
     719
     720    m = Py_InitModule3("_heapq", heapq_methods, module_doc);
     721    if (m == NULL)
     722        return;
     723    PyModule_AddObject(m, "__about__", PyString_FromString(__about__));
     724}
     725
Note: See TracChangeset for help on using the changeset viewer.