Skip to main content

Browse the archive

Staging
v0.5.1
https://github.com/python/cpython
09 December 2020, 11:06:31 UTC
Revision fe34d0facd54a6f471d73f3cba114dedc4f04969 authored by Guido van Rossum on 28 March 2002, 20:18:48 UTC, committed by Guido van Rossum on 28 March 2002, 20:18:48 UTC 
Backport to 2.2.1.
 
Fix an issue that was reported in but unrelated to the main problem of
SF bug 535905 (Evil Trashcan and GC interaction).

The SETLOCAL() macro should not DECREF the local variable in-place and
then store the new value; it should copy the old value to a temporary
value, then store the new value, and then DECREF the temporary value.
This is because it is possible that during the DECREF the frame is
accessed by other code (e.g. a __del__ method or gc.collect()) and the
variable would be pointing to already-freed memory.

BUGFIX CANDIDATE!
1 parent 8812776
Raw File
Tip revision: fe34d0facd54a6f471d73f3cba114dedc4f04969 authored by Guido van Rossum on 28 March 2002, 20:18:48 UTC
Backport to 2.2.1.
Tip revision: fe34d0f
bisect.py 
"""Bisection algorithms."""

def insort_right(a, x, lo=0, hi=None):
    """Insert item x in list a, and keep it sorted assuming a is sorted.

    If x is already in a, insert it to the right of the rightmost x.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x < a[mid]: hi = mid
        else: lo = mid+1
    a.insert(lo, x)

insort = insort_right   # backward compatibility

def bisect_right(a, x, lo=0, hi=None):
    """Return the index where to insert item x in list a, assuming a is sorted.

    The return value i is such that all e in a[:i] have e <= x, and all e in
    a[i:] have e > x.  So if x already appears in the list, i points just
    beyond the rightmost x already there.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x < a[mid]: hi = mid
        else: lo = mid+1
    return lo

bisect = bisect_right   # backward compatibility

def insort_left(a, x, lo=0, hi=None):
    """Insert item x in list a, and keep it sorted assuming a is sorted.

    If x is already in a, insert it to the left of the leftmost x.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x: lo = mid+1
        else: hi = mid
    a.insert(lo, x)


def bisect_left(a, x, lo=0, hi=None):
    """Return the index where to insert item x in list a, assuming a is sorted.

    The return value i is such that all e in a[:i] have e < x, and all e in
    a[i:] have e >= x.  So if x already appears in the list, i points just
    before the leftmost x already there.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x: lo = mid+1
        else: hi = mid
    return lo
back to top