Back to index

python3.2  3.2.2
Classes | Defines | Typedefs | Functions | Variables
listobject.c File Reference
#include "Python.h"
#include <sys/types.h>

Go to the source code of this file.

Classes

struct  sortslice
struct  s_slice
struct  s_MergeState
struct  listiterobject
struct  listreviterobject

Defines

#define PyList_MAXFREELIST   80
#define b   ((PyListObject *)bb)
#define b   ((PyListObject *)v)
#define ISLT(X, Y)   (PyObject_RichCompareBool(X, Y, Py_LT))
#define IFLT(X, Y)
#define MAX_MERGE_PENDING   85
#define MIN_GALLOP   7
#define MERGESTATE_TEMP_SIZE   256
#define MERGE_GETMEM(MS, NEED)

Typedefs

typedef struct s_MergeState MergeState

Functions

static int list_resize (PyListObject *self, Py_ssize_t newsize)
void PyList_Fini (void)
PyObjectPyList_New (Py_ssize_t size)
Py_ssize_t PyList_Size (PyObject *op)
PyObjectPyList_GetItem (PyObject *op, Py_ssize_t i)
int PyList_SetItem (register PyObject *op, register Py_ssize_t i, register PyObject *newitem)
static int ins1 (PyListObject *self, Py_ssize_t where, PyObject *v)
int PyList_Insert (PyObject *op, Py_ssize_t where, PyObject *newitem)
static int app1 (PyListObject *self, PyObject *v)
int PyList_Append (PyObject *op, PyObject *newitem)
static void list_dealloc (PyListObject *op)
static PyObjectlist_repr (PyListObject *v)
static Py_ssize_t list_length (PyListObject *a)
static int list_contains (PyListObject *a, PyObject *el)
static PyObjectlist_item (PyListObject *a, Py_ssize_t i)
static PyObjectlist_slice (PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
PyObjectPyList_GetSlice (PyObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
static PyObjectlist_concat (PyListObject *a, PyObject *bb)
static PyObjectlist_repeat (PyListObject *a, Py_ssize_t n)
static int list_clear (PyListObject *a)
static int list_ass_slice (PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)
int PyList_SetSlice (PyObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)
static PyObjectlist_inplace_repeat (PyListObject *self, Py_ssize_t n)
static int list_ass_item (PyListObject *a, Py_ssize_t i, PyObject *v)
static PyObjectlistinsert (PyListObject *self, PyObject *args)
static PyObjectlistappend (PyListObject *self, PyObject *v)
static PyObjectlistextend (PyListObject *self, PyObject *b)
PyObject_PyList_Extend (PyListObject *self, PyObject *b)
static PyObjectlist_inplace_concat (PyListObject *self, PyObject *other)
static PyObjectlistpop (PyListObject *self, PyObject *args)
static void reverse_slice (PyObject **lo, PyObject **hi)
 Py_LOCAL_INLINE (void)
static int binarysort (sortslice lo, PyObject **hi, PyObject **start)
static Py_ssize_t count_run (PyObject **lo, PyObject **hi, int *descending)
static Py_ssize_t gallop_left (PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint)
static Py_ssize_t gallop_right (PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint)
static void merge_init (MergeState *ms, Py_ssize_t list_size, int has_keyfunc)
static void merge_freemem (MergeState *ms)
static int merge_getmem (MergeState *ms, Py_ssize_t need)
static Py_ssize_t merge_lo (MergeState *ms, sortslice ssa, Py_ssize_t na, sortslice ssb, Py_ssize_t nb)
static Py_ssize_t merge_hi (MergeState *ms, sortslice ssa, Py_ssize_t na, sortslice ssb, Py_ssize_t nb)
static Py_ssize_t merge_at (MergeState *ms, Py_ssize_t i)
static int merge_collapse (MergeState *ms)
static int merge_force_collapse (MergeState *ms)
static Py_ssize_t merge_compute_minrun (Py_ssize_t n)
static void reverse_sortslice (sortslice *s, Py_ssize_t n)
static PyObjectlistsort (PyListObject *self, PyObject *args, PyObject *kwds)
int PyList_Sort (PyObject *v)
static PyObjectlistreverse (PyListObject *self)
int PyList_Reverse (PyObject *v)
PyObjectPyList_AsTuple (PyObject *v)
static PyObjectlistindex (PyListObject *self, PyObject *args)
static PyObjectlistcount (PyListObject *self, PyObject *v)
static PyObjectlistremove (PyListObject *self, PyObject *v)
static int list_traverse (PyListObject *o, visitproc visit, void *arg)
static PyObjectlist_richcompare (PyObject *v, PyObject *w, int op)
static int list_init (PyListObject *self, PyObject *args, PyObject *kw)
static PyObjectlist_sizeof (PyListObject *self)
static PyObjectlist_iter (PyObject *seq)
static PyObjectlist_reversed (PyListObject *seq, PyObject *unused)
 PyDoc_STRVAR (getitem_doc,"x.__getitem__(y) <==> x[y]")
 PyDoc_STRVAR (reversed_doc,"L.__reversed__() -- return a reverse iterator over the list")
 PyDoc_STRVAR (sizeof_doc,"L.__sizeof__() -- size of L in memory, in bytes")
 PyDoc_STRVAR (append_doc,"L.append(object) -- append object to end")
 PyDoc_STRVAR (extend_doc,"L.extend(iterable) -- extend list by appending elements from the iterable")
 PyDoc_STRVAR (insert_doc,"L.insert(index, object) -- insert object before index")
 PyDoc_STRVAR (pop_doc,"L.pop([index]) -> item -- remove and return item at index (default last).\n""Raises IndexError if list is empty or index is out of range.")
 PyDoc_STRVAR (remove_doc,"L.remove(value) -- remove first occurrence of value.\n""Raises ValueError if the value is not present.")
 PyDoc_STRVAR (index_doc,"L.index(value, [start, [stop]]) -> integer -- return first index of value.\n""Raises ValueError if the value is not present.")
 PyDoc_STRVAR (count_doc,"L.count(value) -> integer -- return number of occurrences of value")
 PyDoc_STRVAR (reverse_doc,"L.reverse() -- reverse *IN PLACE*")
 PyDoc_STRVAR (sort_doc,"L.sort(key=None, reverse=False) -- stable sort *IN PLACE*")
static PyObjectlist_subscript (PyListObject *, PyObject *)
 PyDoc_STRVAR (list_doc,"list() -> new empty list\n""list(iterable) -> new list initialized from iterable's items")
static int list_ass_subscript (PyListObject *self, PyObject *item, PyObject *value)
static void listiter_dealloc (listiterobject *)
static int listiter_traverse (listiterobject *, visitproc, void *)
static PyObjectlistiter_next (listiterobject *)
static PyObjectlistiter_len (listiterobject *)
 PyDoc_STRVAR (length_hint_doc,"Private method returning an estimate of len(list(it)).")
static void listreviter_dealloc (listreviterobject *)
static int listreviter_traverse (listreviterobject *, visitproc, void *)
static PyObjectlistreviter_next (listreviterobject *)
static PyObjectlistreviter_len (listreviterobject *)

Variables

static PyListObjectfree_list [PyList_MAXFREELIST]
static int numfree = 0
static PyObjectindexerr = NULL
static PyMethodDef list_methods []
static PySequenceMethods list_as_sequence
static PyMappingMethods list_as_mapping
PyTypeObject PyList_Type
static PyMethodDef listiter_methods []
PyTypeObject PyListIter_Type
static PyMethodDef listreviter_methods []
PyTypeObject PyListRevIter_Type

Class Documentation

struct sortslice

Definition at line 952 of file listobject.c.

Collaboration diagram for sortslice:
Class Members
PyObject ** keys
PyObject ** values
struct s_slice

Definition at line 1348 of file listobject.c.

Collaboration diagram for s_slice:
Class Members
sortslice base
Py_ssize_t len
struct s_MergeState

Definition at line 1353 of file listobject.c.

Collaboration diagram for s_MergeState:
Class Members
sortslice a
Py_ssize_t alloced
Py_ssize_t min_gallop
int n
PyObject * temparray
struct listiterobject

Definition at line 2652 of file listobject.c.

Collaboration diagram for listiterobject:
Class Members
PyObject_HEAD long it_index
PyListObject * it_seq
struct listreviterobject

Definition at line 2776 of file listobject.c.

Collaboration diagram for listreviterobject:
Class Members
PyObject_HEAD Py_ssize_t it_index
PyListObject * it_seq

Define Documentation

#define b   ((PyListObject *)bb)
#define b   ((PyListObject *)v)
#define IFLT (   X,
 
)
Value:
if ((k = ISLT(X, Y)) < 0) goto fail;  \
           if (k)

Definition at line 1018 of file listobject.c.

#define ISLT (   X,
 
)    (PyObject_RichCompareBool(X, Y, Py_LT))

Definition at line 1012 of file listobject.c.

#define MAX_MERGE_PENDING   85

Definition at line 1335 of file listobject.c.

#define MERGE_GETMEM (   MS,
  NEED 
)
Value:
((NEED) <= (MS)->alloced ? 0 :   \
                                merge_getmem(MS, NEED))

Definition at line 1456 of file listobject.c.

#define MERGESTATE_TEMP_SIZE   256

Definition at line 1343 of file listobject.c.

#define MIN_GALLOP   7

Definition at line 1340 of file listobject.c.

#define PyList_MAXFREELIST   80

Definition at line 95 of file listobject.c.


Typedef Documentation

typedef struct s_MergeState MergeState

Function Documentation

PyObject* _PyList_Extend ( PyListObject self,
PyObject b 
)

Definition at line 867 of file listobject.c.

{
    return listextend(self, b);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int app1 ( PyListObject self,
PyObject v 
) [static]

Definition at line 266 of file listobject.c.

{
    Py_ssize_t n = PyList_GET_SIZE(self);

    assert (v != NULL);
    if (n == PY_SSIZE_T_MAX) {
        PyErr_SetString(PyExc_OverflowError,
            "cannot add more objects to list");
        return -1;
    }

    if (list_resize(self, n+1) == -1)
        return -1;

    Py_INCREF(v);
    PyList_SET_ITEM(self, n, v);
    return 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int binarysort ( sortslice  lo,
PyObject **  hi,
PyObject **  start 
) [static]

Definition at line 1033 of file listobject.c.

{
    register Py_ssize_t k;
    register PyObject **l, **p, **r;
    register PyObject *pivot;

    assert(lo.keys <= start && start <= hi);
    /* assert [lo, start) is sorted */
    if (lo.keys == start)
        ++start;
    for (; start < hi; ++start) {
        /* set l to where *start belongs */
        l = lo.keys;
        r = start;
        pivot = *r;
        /* Invariants:
         * pivot >= all in [lo, l).
         * pivot  < all in [r, start).
         * The second is vacuously true at the start.
         */
        assert(l < r);
        do {
            p = l + ((r - l) >> 1);
            IFLT(pivot, *p)
                r = p;
            else
                l = p+1;
        } while (l < r);
        assert(l == r);
        /* The invariants still hold, so pivot >= all in [lo, l) and
           pivot < all in [l, start), so pivot belongs at l.  Note
           that if there are elements equal to pivot, l points to the
           first slot after them -- that's why this sort is stable.
           Slide over to make room.
           Caution: using memmove is much slower under MSVC 5;
           we're not usually moving many slots. */
        for (p = start; p > l; --p)
            *p = *(p-1);
        *l = pivot;
        if (lo.values != NULL) {
            Py_ssize_t offset = lo.values - lo.keys;
            p = start + offset;
            pivot = *p;
            l += offset;
            for (p = start + offset; p > l; --p)
                *p = *(p-1);
            *l = pivot;
        }
    }
    return 0;

 fail:
    return -1;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static Py_ssize_t count_run ( PyObject **  lo,
PyObject **  hi,
int descending 
) [static]

Definition at line 1107 of file listobject.c.

{
    Py_ssize_t k;
    Py_ssize_t n;

    assert(lo < hi);
    *descending = 0;
    ++lo;
    if (lo == hi)
        return 1;

    n = 2;
    IFLT(*lo, *(lo-1)) {
        *descending = 1;
        for (lo = lo+1; lo < hi; ++lo, ++n) {
            IFLT(*lo, *(lo-1))
                ;
            else
                break;
        }
    }
    else {
        for (lo = lo+1; lo < hi; ++lo, ++n) {
            IFLT(*lo, *(lo-1))
                break;
        }
    }

    return n;
fail:
    return -1;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static Py_ssize_t gallop_left ( PyObject key,
PyObject **  a,
Py_ssize_t  n,
Py_ssize_t  hint 
) [static]

Definition at line 1162 of file listobject.c.

{
    Py_ssize_t ofs;
    Py_ssize_t lastofs;
    Py_ssize_t k;

    assert(key && a && n > 0 && hint >= 0 && hint < n);

    a += hint;
    lastofs = 0;
    ofs = 1;
    IFLT(*a, key) {
        /* a[hint] < key -- gallop right, until
         * a[hint + lastofs] < key <= a[hint + ofs]
         */
        const Py_ssize_t maxofs = n - hint;             /* &a[n-1] is highest */
        while (ofs < maxofs) {
            IFLT(a[ofs], key) {
                lastofs = ofs;
                ofs = (ofs << 1) + 1;
                if (ofs <= 0)                   /* int overflow */
                    ofs = maxofs;
            }
            else                /* key <= a[hint + ofs] */
                break;
        }
        if (ofs > maxofs)
            ofs = maxofs;
        /* Translate back to offsets relative to &a[0]. */
        lastofs += hint;
        ofs += hint;
    }
    else {
        /* key <= a[hint] -- gallop left, until
         * a[hint - ofs] < key <= a[hint - lastofs]
         */
        const Py_ssize_t maxofs = hint + 1;             /* &a[0] is lowest */
        while (ofs < maxofs) {
            IFLT(*(a-ofs), key)
                break;
            /* key <= a[hint - ofs] */
            lastofs = ofs;
            ofs = (ofs << 1) + 1;
            if (ofs <= 0)               /* int overflow */
                ofs = maxofs;
        }
        if (ofs > maxofs)
            ofs = maxofs;
        /* Translate back to positive offsets relative to &a[0]. */
        k = lastofs;
        lastofs = hint - ofs;
        ofs = hint - k;
    }
    a -= hint;

    assert(-1 <= lastofs && lastofs < ofs && ofs <= n);
    /* Now a[lastofs] < key <= a[ofs], so key belongs somewhere to the
     * right of lastofs but no farther right than ofs.  Do a binary
     * search, with invariant a[lastofs-1] < key <= a[ofs].
     */
    ++lastofs;
    while (lastofs < ofs) {
        Py_ssize_t m = lastofs + ((ofs - lastofs) >> 1);

        IFLT(a[m], key)
            lastofs = m+1;              /* a[m] < key */
        else
            ofs = m;                    /* key <= a[m] */
    }
    assert(lastofs == ofs);             /* so a[ofs-1] < key <= a[ofs] */
    return ofs;

fail:
    return -1;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static Py_ssize_t gallop_right ( PyObject key,
PyObject **  a,
Py_ssize_t  n,
Py_ssize_t  hint 
) [static]

Definition at line 1253 of file listobject.c.

{
    Py_ssize_t ofs;
    Py_ssize_t lastofs;
    Py_ssize_t k;

    assert(key && a && n > 0 && hint >= 0 && hint < n);

    a += hint;
    lastofs = 0;
    ofs = 1;
    IFLT(key, *a) {
        /* key < a[hint] -- gallop left, until
         * a[hint - ofs] <= key < a[hint - lastofs]
         */
        const Py_ssize_t maxofs = hint + 1;             /* &a[0] is lowest */
        while (ofs < maxofs) {
            IFLT(key, *(a-ofs)) {
                lastofs = ofs;
                ofs = (ofs << 1) + 1;
                if (ofs <= 0)                   /* int overflow */
                    ofs = maxofs;
            }
            else                /* a[hint - ofs] <= key */
                break;
        }
        if (ofs > maxofs)
            ofs = maxofs;
        /* Translate back to positive offsets relative to &a[0]. */
        k = lastofs;
        lastofs = hint - ofs;
        ofs = hint - k;
    }
    else {
        /* a[hint] <= key -- gallop right, until
         * a[hint + lastofs] <= key < a[hint + ofs]
        */
        const Py_ssize_t maxofs = n - hint;             /* &a[n-1] is highest */
        while (ofs < maxofs) {
            IFLT(key, a[ofs])
                break;
            /* a[hint + ofs] <= key */
            lastofs = ofs;
            ofs = (ofs << 1) + 1;
            if (ofs <= 0)               /* int overflow */
                ofs = maxofs;
        }
        if (ofs > maxofs)
            ofs = maxofs;
        /* Translate back to offsets relative to &a[0]. */
        lastofs += hint;
        ofs += hint;
    }
    a -= hint;

    assert(-1 <= lastofs && lastofs < ofs && ofs <= n);
    /* Now a[lastofs] <= key < a[ofs], so key belongs somewhere to the
     * right of lastofs but no farther right than ofs.  Do a binary
     * search, with invariant a[lastofs-1] <= key < a[ofs].
     */
    ++lastofs;
    while (lastofs < ofs) {
        Py_ssize_t m = lastofs + ((ofs - lastofs) >> 1);

        IFLT(key, a[m])
            ofs = m;                    /* key < a[m] */
        else
            lastofs = m+1;              /* a[m] <= key */
    }
    assert(lastofs == ofs);             /* so a[ofs-1] <= key < a[ofs] */
    return ofs;

fail:
    return -1;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int ins1 ( PyListObject self,
Py_ssize_t  where,
PyObject v 
) [static]

Definition at line 223 of file listobject.c.

{
    Py_ssize_t i, n = Py_SIZE(self);
    PyObject **items;
    if (v == NULL) {
        PyErr_BadInternalCall();
        return -1;
    }
    if (n == PY_SSIZE_T_MAX) {
        PyErr_SetString(PyExc_OverflowError,
            "cannot add more objects to list");
        return -1;
    }

    if (list_resize(self, n+1) == -1)
        return -1;

    if (where < 0) {
        where += n;
        if (where < 0)
            where = 0;
    }
    if (where > n)
        where = n;
    items = self->ob_item;
    for (i = n; --i >= where; )
        items[i+1] = items[i];
    Py_INCREF(v);
    items[where] = v;
    return 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int list_ass_item ( PyListObject a,
Py_ssize_t  i,
PyObject v 
) [static]

Definition at line 720 of file listobject.c.

{
    PyObject *old_value;
    if (i < 0 || i >= Py_SIZE(a)) {
        PyErr_SetString(PyExc_IndexError,
                        "list assignment index out of range");
        return -1;
    }
    if (v == NULL)
        return list_ass_slice(a, i, i+1, v);
    Py_INCREF(v);
    old_value = a->ob_item[i];
    a->ob_item[i] = v;
    Py_DECREF(old_value);
    return 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int list_ass_slice ( PyListObject a,
Py_ssize_t  ilow,
Py_ssize_t  ihigh,
PyObject v 
) [static]

Definition at line 573 of file listobject.c.

{
    /* Because [X]DECREF can recursively invoke list operations on
       this list, we must postpone all [X]DECREF activity until
       after the list is back in its canonical shape.  Therefore
       we must allocate an additional array, 'recycle', into which
       we temporarily copy the items that are deleted from the
       list. :-( */
    PyObject *recycle_on_stack[8];
    PyObject **recycle = recycle_on_stack; /* will allocate more if needed */
    PyObject **item;
    PyObject **vitem = NULL;
    PyObject *v_as_SF = NULL; /* PySequence_Fast(v) */
    Py_ssize_t n; /* # of elements in replacement list */
    Py_ssize_t norig; /* # of elements in list getting replaced */
    Py_ssize_t d; /* Change in size */
    Py_ssize_t k;
    size_t s;
    int result = -1;            /* guilty until proved innocent */
#define b ((PyListObject *)v)
    if (v == NULL)
        n = 0;
    else {
        if (a == b) {
            /* Special case "a[i:j] = a" -- copy b first */
            v = list_slice(b, 0, Py_SIZE(b));
            if (v == NULL)
                return result;
            result = list_ass_slice(a, ilow, ihigh, v);
            Py_DECREF(v);
            return result;
        }
        v_as_SF = PySequence_Fast(v, "can only assign an iterable");
        if(v_as_SF == NULL)
            goto Error;
        n = PySequence_Fast_GET_SIZE(v_as_SF);
        vitem = PySequence_Fast_ITEMS(v_as_SF);
    }
    if (ilow < 0)
        ilow = 0;
    else if (ilow > Py_SIZE(a))
        ilow = Py_SIZE(a);

    if (ihigh < ilow)
        ihigh = ilow;
    else if (ihigh > Py_SIZE(a))
        ihigh = Py_SIZE(a);

    norig = ihigh - ilow;
    assert(norig >= 0);
    d = n - norig;
    if (Py_SIZE(a) + d == 0) {
        Py_XDECREF(v_as_SF);
        return list_clear(a);
    }
    item = a->ob_item;
    /* recycle the items that we are about to remove */
    s = norig * sizeof(PyObject *);
    if (s > sizeof(recycle_on_stack)) {
        recycle = (PyObject **)PyMem_MALLOC(s);
        if (recycle == NULL) {
            PyErr_NoMemory();
            goto Error;
        }
    }
    memcpy(recycle, &item[ilow], s);

    if (d < 0) { /* Delete -d items */
        memmove(&item[ihigh+d], &item[ihigh],
            (Py_SIZE(a) - ihigh)*sizeof(PyObject *));
        list_resize(a, Py_SIZE(a) + d);
        item = a->ob_item;
    }
    else if (d > 0) { /* Insert d items */
        k = Py_SIZE(a);
        if (list_resize(a, k+d) < 0)
            goto Error;
        item = a->ob_item;
        memmove(&item[ihigh+d], &item[ihigh],
            (k - ihigh)*sizeof(PyObject *));
    }
    for (k = 0; k < n; k++, ilow++) {
        PyObject *w = vitem[k];
        Py_XINCREF(w);
        item[ilow] = w;
    }
    for (k = norig - 1; k >= 0; --k)
        Py_XDECREF(recycle[k]);
    result = 0;
 Error:
    if (recycle != recycle_on_stack)
        PyMem_FREE(recycle);
    Py_XDECREF(v_as_SF);
    return result;
#undef b
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int list_ass_subscript ( PyListObject self,
PyObject item,
PyObject value 
) [static]

Definition at line 2438 of file listobject.c.

{
    if (PyIndex_Check(item)) {
        Py_ssize_t i = PyNumber_AsSsize_t(item, PyExc_IndexError);
        if (i == -1 && PyErr_Occurred())
            return -1;
        if (i < 0)
            i += PyList_GET_SIZE(self);
        return list_ass_item(self, i, value);
    }
    else if (PySlice_Check(item)) {
        Py_ssize_t start, stop, step, slicelength;

        if (PySlice_GetIndicesEx(item, Py_SIZE(self),
                         &start, &stop, &step, &slicelength) < 0) {
            return -1;
        }

        if (step == 1)
            return list_ass_slice(self, start, stop, value);

        /* Make sure s[5:2] = [..] inserts at the right place:
           before 5, not before 2. */
        if ((step < 0 && start < stop) ||
            (step > 0 && start > stop))
            stop = start;

        if (value == NULL) {
            /* delete slice */
            PyObject **garbage;
            size_t cur;
            Py_ssize_t i;

            if (slicelength <= 0)
                return 0;

            if (step < 0) {
                stop = start + 1;
                start = stop + step*(slicelength - 1) - 1;
                step = -step;
            }

            assert((size_t)slicelength <=
                   PY_SIZE_MAX / sizeof(PyObject*));

            garbage = (PyObject**)
                PyMem_MALLOC(slicelength*sizeof(PyObject*));
            if (!garbage) {
                PyErr_NoMemory();
                return -1;
            }

            /* drawing pictures might help understand these for
               loops. Basically, we memmove the parts of the
               list that are *not* part of the slice: step-1
               items for each item that is part of the slice,
               and then tail end of the list that was not
               covered by the slice */
            for (cur = start, i = 0;
                 cur < (size_t)stop;
                 cur += step, i++) {
                Py_ssize_t lim = step - 1;

                garbage[i] = PyList_GET_ITEM(self, cur);

                if (cur + step >= (size_t)Py_SIZE(self)) {
                    lim = Py_SIZE(self) - cur - 1;
                }

                memmove(self->ob_item + cur - i,
                    self->ob_item + cur + 1,
                    lim * sizeof(PyObject *));
            }
            cur = start + slicelength*step;
            if (cur < (size_t)Py_SIZE(self)) {
                memmove(self->ob_item + cur - slicelength,
                    self->ob_item + cur,
                    (Py_SIZE(self) - cur) *
                     sizeof(PyObject *));
            }

            Py_SIZE(self) -= slicelength;
            list_resize(self, Py_SIZE(self));

            for (i = 0; i < slicelength; i++) {
                Py_DECREF(garbage[i]);
            }
            PyMem_FREE(garbage);

            return 0;
        }
        else {
            /* assign slice */
            PyObject *ins, *seq;
            PyObject **garbage, **seqitems, **selfitems;
            Py_ssize_t cur, i;

            /* protect against a[::-1] = a */
            if (self == (PyListObject*)value) {
                seq = list_slice((PyListObject*)value, 0,
                                   PyList_GET_SIZE(value));
            }
            else {
                seq = PySequence_Fast(value,
                                      "must assign iterable "
                                      "to extended slice");
            }
            if (!seq)
                return -1;

            if (PySequence_Fast_GET_SIZE(seq) != slicelength) {
                PyErr_Format(PyExc_ValueError,
                    "attempt to assign sequence of "
                    "size %zd to extended slice of "
                    "size %zd",
                         PySequence_Fast_GET_SIZE(seq),
                         slicelength);
                Py_DECREF(seq);
                return -1;
            }

            if (!slicelength) {
                Py_DECREF(seq);
                return 0;
            }

            garbage = (PyObject**)
                PyMem_MALLOC(slicelength*sizeof(PyObject*));
            if (!garbage) {
                Py_DECREF(seq);
                PyErr_NoMemory();
                return -1;
            }

            selfitems = self->ob_item;
            seqitems = PySequence_Fast_ITEMS(seq);
            for (cur = start, i = 0; i < slicelength;
                 cur += step, i++) {
                garbage[i] = selfitems[cur];
                ins = seqitems[i];
                Py_INCREF(ins);
                selfitems[cur] = ins;
            }

            for (i = 0; i < slicelength; i++) {
                Py_DECREF(garbage[i]);
            }

            PyMem_FREE(garbage);
            Py_DECREF(seq);

            return 0;
        }
    }
    else {
        PyErr_Format(PyExc_TypeError,
                     "list indices must be integers, not %.200s",
                     item->ob_type->tp_name);
        return -1;
    }
}

Here is the call graph for this function:

static int list_clear ( PyListObject a) [static]

Definition at line 544 of file listobject.c.

{
    Py_ssize_t i;
    PyObject **item = a->ob_item;
    if (item != NULL) {
        /* Because XDECREF can recursively invoke operations on
           this list, we make it empty first. */
        i = Py_SIZE(a);
        Py_SIZE(a) = 0;
        a->ob_item = NULL;
        a->allocated = 0;
        while (--i >= 0) {
            Py_XDECREF(item[i]);
        }
        PyMem_FREE(item);
    }
    /* Never fails; the return value can be ignored.
       Note that there is no guarantee that the list is actually empty
       at this point, because XDECREF may have populated it again! */
    return 0;
}

Here is the caller graph for this function:

static PyObject* list_concat ( PyListObject a,
PyObject bb 
) [static]

Definition at line 465 of file listobject.c.

{
    Py_ssize_t size;
    Py_ssize_t i;
    PyObject **src, **dest;
    PyListObject *np;
    if (!PyList_Check(bb)) {
        PyErr_Format(PyExc_TypeError,
                  "can only concatenate list (not \"%.200s\") to list",
                  bb->ob_type->tp_name);
        return NULL;
    }
#define b ((PyListObject *)bb)
    size = Py_SIZE(a) + Py_SIZE(b);
    if (size < 0)
        return PyErr_NoMemory();
    np = (PyListObject *) PyList_New(size);
    if (np == NULL) {
        return NULL;
    }
    src = a->ob_item;
    dest = np->ob_item;
    for (i = 0; i < Py_SIZE(a); i++) {
        PyObject *v = src[i];
        Py_INCREF(v);
        dest[i] = v;
    }
    src = b->ob_item;
    dest = np->ob_item + Py_SIZE(a);
    for (i = 0; i < Py_SIZE(b); i++) {
        PyObject *v = src[i];
        Py_INCREF(v);
        dest[i] = v;
    }
    return (PyObject *)np;
#undef b
}

Here is the call graph for this function:

static int list_contains ( PyListObject a,
PyObject el 
) [static]

Definition at line 397 of file listobject.c.

{
    Py_ssize_t i;
    int cmp;

    for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i)
        cmp = PyObject_RichCompareBool(el, PyList_GET_ITEM(a, i),
                                           Py_EQ);
    return cmp;
}

Here is the call graph for this function:

static void list_dealloc ( PyListObject op) [static]

Definition at line 297 of file listobject.c.

{
    Py_ssize_t i;
    PyObject_GC_UnTrack(op);
    Py_TRASHCAN_SAFE_BEGIN(op)
    if (op->ob_item != NULL) {
        /* Do it backwards, for Christian Tismer.
           There's a simple test case where somehow this reduces
           thrashing when a *very* large list is created and
           immediately deleted. */
        i = Py_SIZE(op);
        while (--i >= 0) {
            Py_XDECREF(op->ob_item[i]);
        }
        PyMem_FREE(op->ob_item);
    }
    if (numfree < PyList_MAXFREELIST && PyList_CheckExact(op))
        free_list[numfree++] = op;
    else
        Py_TYPE(op)->tp_free((PyObject *)op);
    Py_TRASHCAN_SAFE_END(op)
}

Here is the call graph for this function:

static int list_init ( PyListObject self,
PyObject args,
PyObject kw 
) [static]

Definition at line 2282 of file listobject.c.

{
    PyObject *arg = NULL;
    static char *kwlist[] = {"sequence", 0};

    if (!PyArg_ParseTupleAndKeywords(args, kw, "|O:list", kwlist, &arg))
        return -1;

    /* Verify list invariants established by PyType_GenericAlloc() */
    assert(0 <= Py_SIZE(self));
    assert(Py_SIZE(self) <= self->allocated || self->allocated == -1);
    assert(self->ob_item != NULL ||
           self->allocated == 0 || self->allocated == -1);

    /* Empty previous contents */
    if (self->ob_item != NULL) {
        (void)list_clear(self);
    }
    if (arg != NULL) {
        PyObject *rv = listextend(self, arg);
        if (rv == NULL)
            return -1;
        Py_DECREF(rv);
    }
    return 0;
}

Here is the call graph for this function:

static PyObject* list_inplace_concat ( PyListObject self,
PyObject other 
) [static]

Definition at line 873 of file listobject.c.

{
    PyObject *result;

    result = listextend(self, other);
    if (result == NULL)
        return result;
    Py_DECREF(result);
    Py_INCREF(self);
    return (PyObject *)self;
}

Here is the call graph for this function:

static PyObject* list_inplace_repeat ( PyListObject self,
Py_ssize_t  n 
) [static]

Definition at line 681 of file listobject.c.

{
    PyObject **items;
    Py_ssize_t size, i, j, p;


    size = PyList_GET_SIZE(self);
    if (size == 0 || n == 1) {
        Py_INCREF(self);
        return (PyObject *)self;
    }

    if (n < 1) {
        (void)list_clear(self);
        Py_INCREF(self);
        return (PyObject *)self;
    }

    if (size > PY_SSIZE_T_MAX / n) {
        return PyErr_NoMemory();
    }

    if (list_resize(self, size*n) == -1)
        return NULL;

    p = size;
    items = self->ob_item;
    for (i = 1; i < n; i++) { /* Start counting at 1, not 0 */
        for (j = 0; j < size; j++) {
            PyObject *o = items[j];
            Py_INCREF(o);
            items[p++] = o;
        }
    }
    Py_INCREF(self);
    return (PyObject *)self;
}

Here is the call graph for this function:

static PyObject* list_item ( PyListObject a,
Py_ssize_t  i 
) [static]

Definition at line 409 of file listobject.c.

{
    if (i < 0 || i >= Py_SIZE(a)) {
        if (indexerr == NULL) {
            indexerr = PyUnicode_FromString(
                "list index out of range");
            if (indexerr == NULL)
                return NULL;
        }
        PyErr_SetObject(PyExc_IndexError, indexerr);
        return NULL;
    }
    Py_INCREF(a->ob_item[i]);
    return a->ob_item[i];
}

Here is the call graph for this function:

Here is the caller graph for this function:

static PyObject * list_iter ( PyObject seq) [static]

Definition at line 2706 of file listobject.c.

{
    listiterobject *it;

    if (!PyList_Check(seq)) {
        PyErr_BadInternalCall();
        return NULL;
    }
    it = PyObject_GC_New(listiterobject, &PyListIter_Type);
    if (it == NULL)
        return NULL;
    it->it_index = 0;
    Py_INCREF(seq);
    it->it_seq = (PyListObject *)seq;
    _PyObject_GC_TRACK(it);
    return (PyObject *)it;
}
static Py_ssize_t list_length ( PyListObject a) [static]

Definition at line 391 of file listobject.c.

{
    return Py_SIZE(a);
}
static PyObject* list_repeat ( PyListObject a,
Py_ssize_t  n 
) [static]

Definition at line 504 of file listobject.c.

{
    Py_ssize_t i, j;
    Py_ssize_t size;
    PyListObject *np;
    PyObject **p, **items;
    PyObject *elem;
    if (n < 0)
        n = 0;
    size = Py_SIZE(a) * n;
    if (n && size/n != Py_SIZE(a))
        return PyErr_NoMemory();
    if (size == 0)
        return PyList_New(0);
    np = (PyListObject *) PyList_New(size);
    if (np == NULL)
        return NULL;

    items = np->ob_item;
    if (Py_SIZE(a) == 1) {
        elem = a->ob_item[0];
        for (i = 0; i < n; i++) {
            items[i] = elem;
            Py_INCREF(elem);
        }
        return (PyObject *) np;
    }
    p = np->ob_item;
    items = a->ob_item;
    for (i = 0; i < n; i++) {
        for (j = 0; j < Py_SIZE(a); j++) {
            *p = items[j];
            Py_INCREF(*p);
            p++;
        }
    }
    return (PyObject *) np;
}

Here is the call graph for this function:

static PyObject* list_repr ( PyListObject v) [static]

Definition at line 321 of file listobject.c.

{
    Py_ssize_t i;
    PyObject *s, *temp;
    PyObject *pieces = NULL, *result = NULL;

    i = Py_ReprEnter((PyObject*)v);
    if (i != 0) {
        return i > 0 ? PyUnicode_FromString("[...]") : NULL;
    }

    if (Py_SIZE(v) == 0) {
        result = PyUnicode_FromString("[]");
        goto Done;
    }

    pieces = PyList_New(0);
    if (pieces == NULL)
        goto Done;

    /* Do repr() on each element.  Note that this may mutate the list,
       so must refetch the list size on each iteration. */
    for (i = 0; i < Py_SIZE(v); ++i) {
        int status;
        if (Py_EnterRecursiveCall(" while getting the repr of a list"))
            goto Done;
        s = PyObject_Repr(v->ob_item[i]);
        Py_LeaveRecursiveCall();
        if (s == NULL)
            goto Done;
        status = PyList_Append(pieces, s);
        Py_DECREF(s);  /* append created a new ref */
        if (status < 0)
            goto Done;
    }

    /* Add "[]" decorations to the first and last items. */
    assert(PyList_GET_SIZE(pieces) > 0);
    s = PyUnicode_FromString("[");
    if (s == NULL)
        goto Done;
    temp = PyList_GET_ITEM(pieces, 0);
    PyUnicode_AppendAndDel(&s, temp);
    PyList_SET_ITEM(pieces, 0, s);
    if (s == NULL)
        goto Done;

    s = PyUnicode_FromString("]");
    if (s == NULL)
        goto Done;
    temp = PyList_GET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1);
    PyUnicode_AppendAndDel(&temp, s);
    PyList_SET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1, temp);
    if (temp == NULL)
        goto Done;

    /* Paste them all together with ", " between. */
    s = PyUnicode_FromString(", ");
    if (s == NULL)
        goto Done;
    result = PyUnicode_Join(s, pieces);
    Py_DECREF(s);

Done:
    Py_XDECREF(pieces);
    Py_ReprLeave((PyObject *)v);
    return result;
}

Here is the call graph for this function:

static int list_resize ( PyListObject self,
Py_ssize_t  newsize 
) [static]

Definition at line 25 of file listobject.c.

{
    PyObject **items;
    size_t new_allocated;
    Py_ssize_t allocated = self->allocated;

    /* Bypass realloc() when a previous overallocation is large enough
       to accommodate the newsize.  If the newsize falls lower than half
       the allocated size, then proceed with the realloc() to shrink the list.
    */
    if (allocated >= newsize && newsize >= (allocated >> 1)) {
        assert(self->ob_item != NULL || newsize == 0);
        Py_SIZE(self) = newsize;
        return 0;
    }

    /* This over-allocates proportional to the list size, making room
     * for additional growth.  The over-allocation is mild, but is
     * enough to give linear-time amortized behavior over a long
     * sequence of appends() in the presence of a poorly-performing
     * system realloc().
     * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
     */
    new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

    /* check for integer overflow */
    if (new_allocated > PY_SIZE_MAX - newsize) {
        PyErr_NoMemory();
        return -1;
    } else {
        new_allocated += newsize;
    }

    if (newsize == 0)
        new_allocated = 0;
    items = self->ob_item;
    if (new_allocated <= ((~(size_t)0) / sizeof(PyObject *)))
        PyMem_RESIZE(items, PyObject *, new_allocated);
    else
        items = NULL;
    if (items == NULL) {
        PyErr_NoMemory();
        return -1;
    }
    self->ob_item = items;
    Py_SIZE(self) = newsize;
    self->allocated = new_allocated;
    return 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static PyObject * list_reversed ( PyListObject seq,
PyObject unused 
) [static]

Definition at line 2827 of file listobject.c.

{
    listreviterobject *it;

    it = PyObject_GC_New(listreviterobject, &PyListRevIter_Type);
    if (it == NULL)
        return NULL;
    assert(PyList_Check(seq));
    it->it_index = PyList_GET_SIZE(seq) - 1;
    Py_INCREF(seq);
    it->it_seq = seq;
    PyObject_GC_Track(it);
    return (PyObject *)it;
}

Here is the call graph for this function:

static PyObject* list_richcompare ( PyObject v,
PyObject w,
int  op 
) [static]

Definition at line 2210 of file listobject.c.

{
    PyListObject *vl, *wl;
    Py_ssize_t i;

    if (!PyList_Check(v) || !PyList_Check(w)) {
        Py_INCREF(Py_NotImplemented);
        return Py_NotImplemented;
    }

    vl = (PyListObject *)v;
    wl = (PyListObject *)w;

    if (Py_SIZE(vl) != Py_SIZE(wl) && (op == Py_EQ || op == Py_NE)) {
        /* Shortcut: if the lengths differ, the lists differ */
        PyObject *res;
        if (op == Py_EQ)
            res = Py_False;
        else
            res = Py_True;
        Py_INCREF(res);
        return res;
    }

    /* Search for the first index where items are different */
    for (i = 0; i < Py_SIZE(vl) && i < Py_SIZE(wl); i++) {
        int k = PyObject_RichCompareBool(vl->ob_item[i],
                                         wl->ob_item[i], Py_EQ);
        if (k < 0)
            return NULL;
        if (!k)
            break;
    }

    if (i >= Py_SIZE(vl) || i >= Py_SIZE(wl)) {
        /* No more items to compare -- compare sizes */
        Py_ssize_t vs = Py_SIZE(vl);
        Py_ssize_t ws = Py_SIZE(wl);
        int cmp;
        PyObject *res;
        switch (op) {
        case Py_LT: cmp = vs <  ws; break;
        case Py_LE: cmp = vs <= ws; break;
        case Py_EQ: cmp = vs == ws; break;
        case Py_NE: cmp = vs != ws; break;
        case Py_GT: cmp = vs >  ws; break;
        case Py_GE: cmp = vs >= ws; break;
        default: return NULL; /* cannot happen */
        }
        if (cmp)
            res = Py_True;
        else
            res = Py_False;
        Py_INCREF(res);
        return res;
    }

    /* We have an item that differs -- shortcuts for EQ/NE */
    if (op == Py_EQ) {
        Py_INCREF(Py_False);
        return Py_False;
    }
    if (op == Py_NE) {
        Py_INCREF(Py_True);
        return Py_True;
    }

    /* Compare the final item again using the proper operator */
    return PyObject_RichCompare(vl->ob_item[i], wl->ob_item[i], op);
}

Here is the call graph for this function:

static PyObject* list_sizeof ( PyListObject self) [static]

Definition at line 2310 of file listobject.c.

{
    Py_ssize_t res;

    res = sizeof(PyListObject) + self->allocated * sizeof(void*);
    return PyLong_FromSsize_t(res);
}
static PyObject* list_slice ( PyListObject a,
Py_ssize_t  ilow,
Py_ssize_t  ihigh 
) [static]

Definition at line 426 of file listobject.c.

{
    PyListObject *np;
    PyObject **src, **dest;
    Py_ssize_t i, len;
    if (ilow < 0)
        ilow = 0;
    else if (ilow > Py_SIZE(a))
        ilow = Py_SIZE(a);
    if (ihigh < ilow)
        ihigh = ilow;
    else if (ihigh > Py_SIZE(a))
        ihigh = Py_SIZE(a);
    len = ihigh - ilow;
    np = (PyListObject *) PyList_New(len);
    if (np == NULL)
        return NULL;

    src = a->ob_item + ilow;
    dest = np->ob_item;
    for (i = 0; i < len; i++) {
        PyObject *v = src[i];
        Py_INCREF(v);
        dest[i] = v;
    }
    return (PyObject *)np;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static PyObject * list_subscript ( PyListObject self,
PyObject item 
) [static]

Definition at line 2385 of file listobject.c.

{
    if (PyIndex_Check(item)) {
        Py_ssize_t i;
        i = PyNumber_AsSsize_t(item, PyExc_IndexError);
        if (i == -1 && PyErr_Occurred())
            return NULL;
        if (i < 0)
            i += PyList_GET_SIZE(self);
        return list_item(self, i);
    }
    else if (PySlice_Check(item)) {
        Py_ssize_t start, stop, step, slicelength, cur, i;
        PyObject* result;
        PyObject* it;
        PyObject **src, **dest;

        if (PySlice_GetIndicesEx(item, Py_SIZE(self),
                         &start, &stop, &step, &slicelength) < 0) {
            return NULL;
        }

        if (slicelength <= 0) {
            return PyList_New(0);
        }
        else if (step == 1) {
            return list_slice(self, start, stop);
        }
        else {
            result = PyList_New(slicelength);
            if (!result) return NULL;

            src = self->ob_item;
            dest = ((PyListObject *)result)->ob_item;
            for (cur = start, i = 0; i < slicelength;
                 cur += step, i++) {
                it = src[cur];
                Py_INCREF(it);
                dest[i] = it;
            }

            return result;
        }
    }
    else {
        PyErr_Format(PyExc_TypeError,
                     "list indices must be integers, not %.200s",
                     item->ob_type->tp_name);
        return NULL;
    }
}

Here is the call graph for this function:

static int list_traverse ( PyListObject o,
visitproc  visit,
void arg 
) [static]

Definition at line 2200 of file listobject.c.

{
    Py_ssize_t i;

    for (i = Py_SIZE(o); --i >= 0; )
        Py_VISIT(o->ob_item[i]);
    return 0;
}
static PyObject* listappend ( PyListObject self,
PyObject v 
) [static]

Definition at line 750 of file listobject.c.

{
    if (app1(self, v) == 0)
        Py_RETURN_NONE;
    return NULL;
}

Here is the call graph for this function:

static PyObject* listcount ( PyListObject self,
PyObject v 
) [static]

Definition at line 2164 of file listobject.c.

{
    Py_ssize_t count = 0;
    Py_ssize_t i;

    for (i = 0; i < Py_SIZE(self); i++) {
        int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
        if (cmp > 0)
            count++;
        else if (cmp < 0)
            return NULL;
    }
    return PyLong_FromSsize_t(count);
}

Here is the call graph for this function:

static PyObject* listextend ( PyListObject self,
PyObject b 
) [static]

Definition at line 758 of file listobject.c.

{
    PyObject *it;      /* iter(v) */
    Py_ssize_t m;                  /* size of self */
    Py_ssize_t n;                  /* guess for size of b */
    Py_ssize_t mn;                 /* m + n */
    Py_ssize_t i;
    PyObject *(*iternext)(PyObject *);

    /* Special cases:
       1) lists and tuples which can use PySequence_Fast ops
       2) extending self to self requires making a copy first
    */
    if (PyList_CheckExact(b) || PyTuple_CheckExact(b) || (PyObject *)self == b) {
        PyObject **src, **dest;
        b = PySequence_Fast(b, "argument must be iterable");
        if (!b)
            return NULL;
        n = PySequence_Fast_GET_SIZE(b);
        if (n == 0) {
            /* short circuit when b is empty */
            Py_DECREF(b);
            Py_RETURN_NONE;
        }
        m = Py_SIZE(self);
        if (list_resize(self, m + n) == -1) {
            Py_DECREF(b);
            return NULL;
        }
        /* note that we may still have self == b here for the
         * situation a.extend(a), but the following code works
         * in that case too.  Just make sure to resize self
         * before calling PySequence_Fast_ITEMS.
         */
        /* populate the end of self with b's items */
        src = PySequence_Fast_ITEMS(b);
        dest = self->ob_item + m;
        for (i = 0; i < n; i++) {
            PyObject *o = src[i];
            Py_INCREF(o);
            dest[i] = o;
        }
        Py_DECREF(b);
        Py_RETURN_NONE;
    }

    it = PyObject_GetIter(b);
    if (it == NULL)
        return NULL;
    iternext = *it->ob_type->tp_iternext;

    /* Guess a result list size. */
    n = _PyObject_LengthHint(b, 8);
    if (n == -1) {
        Py_DECREF(it);
        return NULL;
    }
    m = Py_SIZE(self);
    mn = m + n;
    if (mn >= m) {
        /* Make room. */
        if (list_resize(self, mn) == -1)
            goto error;
        /* Make the list sane again. */
        Py_SIZE(self) = m;
    }
    /* Else m + n overflowed; on the chance that n lied, and there really
     * is enough room, ignore it.  If n was telling the truth, we'll
     * eventually run out of memory during the loop.
     */

    /* Run iterator to exhaustion. */
    for (;;) {
        PyObject *item = iternext(it);
        if (item == NULL) {
            if (PyErr_Occurred()) {
                if (PyErr_ExceptionMatches(PyExc_StopIteration))
                    PyErr_Clear();
                else
                    goto error;
            }
            break;
        }
        if (Py_SIZE(self) < self->allocated) {
            /* steals ref */
            PyList_SET_ITEM(self, Py_SIZE(self), item);
            ++Py_SIZE(self);
        }
        else {
            int status = app1(self, item);
            Py_DECREF(item);  /* append creates a new ref */
            if (status < 0)
                goto error;
        }
    }

    /* Cut back result list if initial guess was too large. */
    if (Py_SIZE(self) < self->allocated)
        list_resize(self, Py_SIZE(self));  /* shrinking can't fail */

    Py_DECREF(it);
    Py_RETURN_NONE;

  error:
    Py_DECREF(it);
    return NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static PyObject* listindex ( PyListObject self,
PyObject args 
) [static]

Definition at line 2119 of file listobject.c.

{
    Py_ssize_t i, start=0, stop=Py_SIZE(self);
    PyObject *v, *format_tuple, *err_string;
    static PyObject *err_format = NULL;

    if (!PyArg_ParseTuple(args, "O|O&O&:index", &v,
                                _PyEval_SliceIndex, &start,
                                _PyEval_SliceIndex, &stop))
        return NULL;
    if (start < 0) {
        start += Py_SIZE(self);
        if (start < 0)
            start = 0;
    }
    if (stop < 0) {
        stop += Py_SIZE(self);
        if (stop < 0)
            stop = 0;
    }
    for (i = start; i < stop && i < Py_SIZE(self); i++) {
        int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
        if (cmp > 0)
            return PyLong_FromSsize_t(i);
        else if (cmp < 0)
            return NULL;
    }
    if (err_format == NULL) {
        err_format = PyUnicode_FromString("%r is not in list");
        if (err_format == NULL)
            return NULL;
    }
    format_tuple = PyTuple_Pack(1, v);
    if (format_tuple == NULL)
        return NULL;
    err_string = PyUnicode_Format(err_format, format_tuple);
    Py_DECREF(format_tuple);
    if (err_string == NULL)
        return NULL;
    PyErr_SetObject(PyExc_ValueError, err_string);
    Py_DECREF(err_string);
    return NULL;
}

Here is the call graph for this function:

static PyObject* listinsert ( PyListObject self,
PyObject args 
) [static]

Definition at line 738 of file listobject.c.

{
    Py_ssize_t i;
    PyObject *v;
    if (!PyArg_ParseTuple(args, "nO:insert", &i, &v))
        return NULL;
    if (ins1(self, i, v) == 0)
        Py_RETURN_NONE;
    return NULL;
}

Here is the call graph for this function:

static void listiter_dealloc ( listiterobject it) [static]

Definition at line 2725 of file listobject.c.

Here is the call graph for this function:

static PyObject * listiter_len ( listiterobject it) [static]

Definition at line 2764 of file listobject.c.

{
    Py_ssize_t len;
    if (it->it_seq) {
        len = PyList_GET_SIZE(it->it_seq) - it->it_index;
        if (len >= 0)
            return PyLong_FromSsize_t(len);
    }
    return PyLong_FromLong(0);
}

Here is the call graph for this function:

static PyObject * listiter_next ( listiterobject it) [static]

Definition at line 2740 of file listobject.c.

{
    PyListObject *seq;
    PyObject *item;

    assert(it != NULL);
    seq = it->it_seq;
    if (seq == NULL)
        return NULL;
    assert(PyList_Check(seq));

    if (it->it_index < PyList_GET_SIZE(seq)) {
        item = PyList_GET_ITEM(seq, it->it_index);
        ++it->it_index;
        Py_INCREF(item);
        return item;
    }

    Py_DECREF(seq);
    it->it_seq = NULL;
    return NULL;
}
static int listiter_traverse ( listiterobject it,
visitproc  visit,
void arg 
) [static]

Definition at line 2733 of file listobject.c.

{
    Py_VISIT(it->it_seq);
    return 0;
}
static PyObject* listpop ( PyListObject self,
PyObject args 
) [static]

Definition at line 886 of file listobject.c.

{
    Py_ssize_t i = -1;
    PyObject *v;
    int status;

    if (!PyArg_ParseTuple(args, "|n:pop", &i))
        return NULL;

    if (Py_SIZE(self) == 0) {
        /* Special-case most common failure cause */
        PyErr_SetString(PyExc_IndexError, "pop from empty list");
        return NULL;
    }
    if (i < 0)
        i += Py_SIZE(self);
    if (i < 0 || i >= Py_SIZE(self)) {
        PyErr_SetString(PyExc_IndexError, "pop index out of range");
        return NULL;
    }
    v = self->ob_item[i];
    if (i == Py_SIZE(self) - 1) {
        status = list_resize(self, Py_SIZE(self) - 1);
        assert(status >= 0);
        return v; /* and v now owns the reference the list had */
    }
    Py_INCREF(v);
    status = list_ass_slice(self, i, i+1, (PyObject *)NULL);
    assert(status >= 0);
    /* Use status, so that in a release build compilers don't
     * complain about the unused name.
     */
    (void) status;

    return v;
}

Here is the call graph for this function:

static PyObject* listremove ( PyListObject self,
PyObject v 
) [static]

Definition at line 2180 of file listobject.c.

{
    Py_ssize_t i;

    for (i = 0; i < Py_SIZE(self); i++) {
        int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
        if (cmp > 0) {
            if (list_ass_slice(self, i, i+1,
                               (PyObject *)NULL) == 0)
                Py_RETURN_NONE;
            return NULL;
        }
        else if (cmp < 0)
            return NULL;
    }
    PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
    return NULL;
}

Here is the call graph for this function:

static PyObject* listreverse ( PyListObject self) [static]

Definition at line 2072 of file listobject.c.

{
    if (Py_SIZE(self) > 1)
        reverse_slice(self->ob_item, self->ob_item + Py_SIZE(self));
    Py_RETURN_NONE;
}

Here is the call graph for this function:

static void listreviter_dealloc ( listreviterobject it) [static]

Definition at line 2843 of file listobject.c.

Here is the call graph for this function:

static PyObject * listreviter_len ( listreviterobject it) [static]

Definition at line 2879 of file listobject.c.

{
    Py_ssize_t len = it->it_index + 1;
    if (it->it_seq == NULL || PyList_GET_SIZE(it->it_seq) < len)
        len = 0;
    return PyLong_FromSsize_t(len);
}
static PyObject * listreviter_next ( listreviterobject it) [static]

Definition at line 2858 of file listobject.c.

{
    PyObject *item;
    Py_ssize_t index = it->it_index;
    PyListObject *seq = it->it_seq;

    if (index>=0 && index < PyList_GET_SIZE(seq)) {
        item = PyList_GET_ITEM(seq, index);
        it->it_index--;
        Py_INCREF(item);
        return item;
    }
    it->it_index = -1;
    if (seq != NULL) {
        it->it_seq = NULL;
        Py_DECREF(seq);
    }
    return NULL;
}
static int listreviter_traverse ( listreviterobject it,
visitproc  visit,
void arg 
) [static]

Definition at line 2851 of file listobject.c.

{
    Py_VISIT(it->it_seq);
    return 0;
}
static PyObject* listsort ( PyListObject self,
PyObject args,
PyObject kwds 
) [static]

Definition at line 1883 of file listobject.c.

{
    MergeState ms;
    Py_ssize_t nremaining;
    Py_ssize_t minrun;
    sortslice lo;
    Py_ssize_t saved_ob_size, saved_allocated;
    PyObject **saved_ob_item;
    PyObject **final_ob_item;
    PyObject *result = NULL;            /* guilty until proved innocent */
    int reverse = 0;
    PyObject *keyfunc = NULL;
    Py_ssize_t i;
    static char *kwlist[] = {"key", "reverse", 0};
    PyObject **keys;

    assert(self != NULL);
    assert (PyList_Check(self));
    if (args != NULL) {
        if (!PyArg_ParseTupleAndKeywords(args, kwds, "|Oi:sort",
            kwlist, &keyfunc, &reverse))
            return NULL;
        if (Py_SIZE(args) > 0) {
            PyErr_SetString(PyExc_TypeError,
                "must use keyword argument for key function");
            return NULL;
        }
    }
    if (keyfunc == Py_None)
        keyfunc = NULL;

    /* The list is temporarily made empty, so that mutations performed
     * by comparison functions can't affect the slice of memory we're
     * sorting (allowing mutations during sorting is a core-dump
     * factory, since ob_item may change).
     */
    saved_ob_size = Py_SIZE(self);
    saved_ob_item = self->ob_item;
    saved_allocated = self->allocated;
    Py_SIZE(self) = 0;
    self->ob_item = NULL;
    self->allocated = -1; /* any operation will reset it to >= 0 */

    if (keyfunc == NULL) {
        keys = NULL;
        lo.keys = saved_ob_item;
        lo.values = NULL;
    }
    else {
        if (saved_ob_size < MERGESTATE_TEMP_SIZE/2)
            /* Leverage stack space we allocated but won't otherwise use */
            keys = &ms.temparray[saved_ob_size+1];
        else {
            keys = PyMem_MALLOC(sizeof(PyObject *) * saved_ob_size);
            if (keys == NULL)
                return NULL;
        }

        for (i = 0; i < saved_ob_size ; i++) {
            keys[i] = PyObject_CallFunctionObjArgs(keyfunc, saved_ob_item[i],
                                                   NULL);
            if (keys[i] == NULL) {
                for (i=i-1 ; i>=0 ; i--)
                    Py_DECREF(keys[i]);
                if (keys != &ms.temparray[saved_ob_size+1])
                    PyMem_FREE(keys);
                goto keyfunc_fail;
            }
        }

        lo.keys = keys;
        lo.values = saved_ob_item;
    }

    merge_init(&ms, saved_ob_size, keys != NULL);

    nremaining = saved_ob_size;
    if (nremaining < 2)
        goto succeed;

    /* Reverse sort stability achieved by initially reversing the list,
    applying a stable forward sort, then reversing the final result. */
    if (reverse) {
        if (keys != NULL)
            reverse_slice(&keys[0], &keys[saved_ob_size]);
        reverse_slice(&saved_ob_item[0], &saved_ob_item[saved_ob_size]);
    }

    /* March over the array once, left to right, finding natural runs,
     * and extending short natural runs to minrun elements.
     */
    minrun = merge_compute_minrun(nremaining);
    do {
        int descending;
        Py_ssize_t n;

        /* Identify next run. */
        n = count_run(lo.keys, lo.keys + nremaining, &descending);
        if (n < 0)
            goto fail;
        if (descending)
            reverse_sortslice(&lo, n);
        /* If short, extend to min(minrun, nremaining). */
        if (n < minrun) {
            const Py_ssize_t force = nremaining <= minrun ?
                              nremaining : minrun;
            if (binarysort(lo, lo.keys + force, lo.keys + n) < 0)
                goto fail;
            n = force;
        }
        /* Push run onto pending-runs stack, and maybe merge. */
        assert(ms.n < MAX_MERGE_PENDING);
        ms.pending[ms.n].base = lo;
        ms.pending[ms.n].len = n;
        ++ms.n;
        if (merge_collapse(&ms) < 0)
            goto fail;
        /* Advance to find next run. */
        sortslice_advance(&lo, n);
        nremaining -= n;
    } while (nremaining);

    if (merge_force_collapse(&ms) < 0)
        goto fail;
    assert(ms.n == 1);
    assert(keys == NULL
           ? ms.pending[0].base.keys == saved_ob_item
           : ms.pending[0].base.keys == &keys[0]);
    assert(ms.pending[0].len == saved_ob_size);
    lo = ms.pending[0].base;

succeed:
    result = Py_None;
fail:
    if (keys != NULL) {
        for (i = 0; i < saved_ob_size; i++)
            Py_DECREF(keys[i]);
        if (keys != &ms.temparray[saved_ob_size+1])
            PyMem_FREE(keys);
    }

    if (self->allocated != -1 && result != NULL) {
        /* The user mucked with the list during the sort,
         * and we don't already have another error to report.
         */
        PyErr_SetString(PyExc_ValueError, "list modified during sort");
        result = NULL;
    }

    if (reverse && saved_ob_size > 1)
        reverse_slice(saved_ob_item, saved_ob_item + saved_ob_size);

    merge_freemem(&ms);

keyfunc_fail:
    final_ob_item = self->ob_item;
    i = Py_SIZE(self);
    Py_SIZE(self) = saved_ob_size;
    self->ob_item = saved_ob_item;
    self->allocated = saved_allocated;
    if (final_ob_item != NULL) {
        /* we cannot use list_clear() for this because it does not
           guarantee that the list is really empty when it returns */
        while (--i >= 0) {
            Py_XDECREF(final_ob_item[i]);
        }
        PyMem_FREE(final_ob_item);
    }
    Py_XINCREF(result);
    return result;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static Py_ssize_t merge_at ( MergeState ms,
Py_ssize_t  i 
) [static]

Definition at line 1737 of file listobject.c.

{
    sortslice ssa, ssb;
    Py_ssize_t na, nb;
    Py_ssize_t k;

    assert(ms != NULL);
    assert(ms->n >= 2);
    assert(i >= 0);
    assert(i == ms->n - 2 || i == ms->n - 3);

    ssa = ms->pending[i].base;
    na = ms->pending[i].len;
    ssb = ms->pending[i+1].base;
    nb = ms->pending[i+1].len;
    assert(na > 0 && nb > 0);
    assert(ssa.keys + na == ssb.keys);

    /* Record the length of the combined runs; if i is the 3rd-last
     * run now, also slide over the last run (which isn't involved
     * in this merge).  The current run i+1 goes away in any case.
     */
    ms->pending[i].len = na + nb;
    if (i == ms->n - 3)
        ms->pending[i+1] = ms->pending[i+2];
    --ms->n;

    /* Where does b start in a?  Elements in a before that can be
     * ignored (already in place).
     */
    k = gallop_right(*ssb.keys, ssa.keys, na, 0);
    if (k < 0)
        return -1;
    sortslice_advance(&ssa, k);
    na -= k;
    if (na == 0)
        return 0;

    /* Where does a end in b?  Elements in b after that can be
     * ignored (already in place).
     */
    nb = gallop_left(ssa.keys[na-1], ssb.keys, nb, nb-1);
    if (nb <= 0)
        return nb;

    /* Merge what remains of the runs, using a temp array with
     * min(na, nb) elements.
     */
    if (na <= nb)
        return merge_lo(ms, ssa, na, ssb, nb);
    else
        return merge_hi(ms, ssa, na, ssb, nb);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int merge_collapse ( MergeState ms) [static]

Definition at line 1802 of file listobject.c.

{
    struct s_slice *p = ms->pending;

    assert(ms);
    while (ms->n > 1) {
        Py_ssize_t n = ms->n - 2;
        if (n > 0 && p[n-1].len <= p[n].len + p[n+1].len) {
            if (p[n-1].len < p[n+1].len)
                --n;
            if (merge_at(ms, n) < 0)
                return -1;
        }
        else if (p[n].len <= p[n+1].len) {
                 if (merge_at(ms, n) < 0)
                        return -1;
        }
        else
            break;
    }
    return 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static Py_ssize_t merge_compute_minrun ( Py_ssize_t  n) [static]

Definition at line 1857 of file listobject.c.

{
    Py_ssize_t r = 0;           /* becomes 1 if any 1 bits are shifted off */

    assert(n >= 0);
    while (n >= 64) {
        r |= n & 1;
        n >>= 1;
    }
    return n + r;
}

Here is the caller graph for this function:

static int merge_force_collapse ( MergeState ms) [static]

Definition at line 1831 of file listobject.c.

{
    struct s_slice *p = ms->pending;

    assert(ms);
    while (ms->n > 1) {
        Py_ssize_t n = ms->n - 2;
        if (n > 0 && p[n-1].len < p[n+1].len)
            --n;
        if (merge_at(ms, n) < 0)
            return -1;
    }
    return 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void merge_freemem ( MergeState ms) [static]

Definition at line 1416 of file listobject.c.

{
    assert(ms != NULL);
    if (ms->a.keys != ms->temparray)
        PyMem_Free(ms->a.keys);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int merge_getmem ( MergeState ms,
Py_ssize_t  need 
) [static]

Definition at line 1427 of file listobject.c.

{
    int multiplier;

    assert(ms != NULL);
    if (need <= ms->alloced)
        return 0;

    multiplier = ms->a.values != NULL ? 2 : 1;

    /* Don't realloc!  That can cost cycles to copy the old data, but
     * we don't care what's in the block.
     */
    merge_freemem(ms);
    if ((size_t)need > PY_SSIZE_T_MAX / sizeof(PyObject*) / multiplier) {
        PyErr_NoMemory();
        return -1;
    }
    ms->a.keys = (PyObject**)PyMem_Malloc(multiplier * need
                                          * sizeof(PyObject *));
    if (ms->a.keys != NULL) {
        ms->alloced = need;
        if (ms->a.values != NULL)
            ms->a.values = &ms->a.keys[need];
        return 0;
    }
    PyErr_NoMemory();
    return -1;
}

Here is the call graph for this function:

static Py_ssize_t merge_hi ( MergeState ms,
sortslice  ssa,
Py_ssize_t  na,
sortslice  ssb,
Py_ssize_t  nb 
) [static]

Definition at line 1598 of file listobject.c.

{
    Py_ssize_t k;
    sortslice dest, basea, baseb;
    int result = -1;            /* guilty until proved innocent */
    Py_ssize_t min_gallop;

    assert(ms && ssa.keys && ssb.keys && na > 0 && nb > 0);
    assert(ssa.keys + na == ssb.keys);
    if (MERGE_GETMEM(ms, nb) < 0)
        return -1;
    dest = ssb;
    sortslice_advance(&dest, nb-1);
    sortslice_memcpy(&ms->a, 0, &ssb, 0, nb);
    basea = ssa;
    baseb = ms->a;
    ssb.keys = ms->a.keys + nb - 1;
    if (ssb.values != NULL)
        ssb.values = ms->a.values + nb - 1;
    sortslice_advance(&ssa, na - 1);

    sortslice_copy_decr(&dest, &ssa);
    --na;
    if (na == 0)
        goto Succeed;
    if (nb == 1)
        goto CopyA;

    min_gallop = ms->min_gallop;
    for (;;) {
        Py_ssize_t acount = 0;          /* # of times A won in a row */
        Py_ssize_t bcount = 0;          /* # of times B won in a row */

        /* Do the straightforward thing until (if ever) one run
         * appears to win consistently.
         */
        for (;;) {
            assert(na > 0 && nb > 1);
            k = ISLT(ssb.keys[0], ssa.keys[0]);
            if (k) {
                if (k < 0)
                    goto Fail;
                sortslice_copy_decr(&dest, &ssa);
                ++acount;
                bcount = 0;
                --na;
                if (na == 0)
                    goto Succeed;
                if (acount >= min_gallop)
                    break;
            }
            else {
                sortslice_copy_decr(&dest, &ssb);
                ++bcount;
                acount = 0;
                --nb;
                if (nb == 1)
                    goto CopyA;
                if (bcount >= min_gallop)
                    break;
            }
        }

        /* One run is winning so consistently that galloping may
         * be a huge win.  So try that, and continue galloping until
         * (if ever) neither run appears to be winning consistently
         * anymore.
         */
        ++min_gallop;
        do {
            assert(na > 0 && nb > 1);
            min_gallop -= min_gallop > 1;
            ms->min_gallop = min_gallop;
            k = gallop_right(ssb.keys[0], basea.keys, na, na-1);
            if (k < 0)
                goto Fail;
            k = na - k;
            acount = k;
            if (k) {
                sortslice_advance(&dest, -k);
                sortslice_advance(&ssa, -k);
                sortslice_memmove(&dest, 1, &ssa, 1, k);
                na -= k;
                if (na == 0)
                    goto Succeed;
            }
            sortslice_copy_decr(&dest, &ssb);
            --nb;
            if (nb == 1)
                goto CopyA;

            k = gallop_left(ssa.keys[0], baseb.keys, nb, nb-1);
            if (k < 0)
                goto Fail;
            k = nb - k;
            bcount = k;
            if (k) {
                sortslice_advance(&dest, -k);
                sortslice_advance(&ssb, -k);
                sortslice_memcpy(&dest, 1, &ssb, 1, k);
                nb -= k;
                if (nb == 1)
                    goto CopyA;
                /* nb==0 is impossible now if the comparison
                 * function is consistent, but we can't assume
                 * that it is.
                 */
                if (nb == 0)
                    goto Succeed;
            }
            sortslice_copy_decr(&dest, &ssa);
            --na;
            if (na == 0)
                goto Succeed;
        } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP);
        ++min_gallop;           /* penalize it for leaving galloping mode */
        ms->min_gallop = min_gallop;
    }
Succeed:
    result = 0;
Fail:
    if (nb)
        sortslice_memcpy(&dest, -(nb-1), &baseb, 0, nb);
    return result;
CopyA:
    assert(nb == 1 && na > 0);
    /* The first element of ssb belongs at the front of the merge. */
    sortslice_memmove(&dest, 1-na, &ssa, 1-na, na);
    sortslice_advance(&dest, -na);
    sortslice_advance(&ssa, -na);
    sortslice_copy(&dest, 0, &ssb, 0);
    return 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void merge_init ( MergeState ms,
Py_ssize_t  list_size,
int  has_keyfunc 
) [static]

Definition at line 1384 of file listobject.c.

{
    assert(ms != NULL);
    if (has_keyfunc) {
        /* The temporary space for merging will need at most half the list
         * size rounded up.  Use the minimum possible space so we can use the
         * rest of temparray for other things.  In particular, if there is
         * enough extra space, listsort() will use it to store the keys.
         */
        ms->alloced = (list_size + 1) / 2;

        /* ms->alloced describes how many keys will be stored at
           ms->temparray, but we also need to store the values.  Hence,
           ms->alloced is capped at half of MERGESTATE_TEMP_SIZE. */
        if (MERGESTATE_TEMP_SIZE / 2 < ms->alloced)
            ms->alloced = MERGESTATE_TEMP_SIZE / 2;
        ms->a.values = &ms->temparray[ms->alloced];
    }
    else {
        ms->alloced = MERGESTATE_TEMP_SIZE;
        ms->a.values = NULL;
    }
    ms->a.keys = ms->temparray;
    ms->n = 0;
    ms->min_gallop = MIN_GALLOP;
}

Here is the caller graph for this function:

static Py_ssize_t merge_lo ( MergeState ms,
sortslice  ssa,
Py_ssize_t  na,
sortslice  ssb,
Py_ssize_t  nb 
) [static]

Definition at line 1466 of file listobject.c.

{
    Py_ssize_t k;
    sortslice dest;
    int result = -1;            /* guilty until proved innocent */
    Py_ssize_t min_gallop;

    assert(ms && ssa.keys && ssb.keys && na > 0 && nb > 0);
    assert(ssa.keys + na == ssb.keys);
    if (MERGE_GETMEM(ms, na) < 0)
        return -1;
    sortslice_memcpy(&ms->a, 0, &ssa, 0, na);
    dest = ssa;
    ssa = ms->a;

    sortslice_copy_incr(&dest, &ssb);
    --nb;
    if (nb == 0)
        goto Succeed;
    if (na == 1)
        goto CopyB;

    min_gallop = ms->min_gallop;
    for (;;) {
        Py_ssize_t acount = 0;          /* # of times A won in a row */
        Py_ssize_t bcount = 0;          /* # of times B won in a row */

        /* Do the straightforward thing until (if ever) one run
         * appears to win consistently.
         */
        for (;;) {
            assert(na > 1 && nb > 0);
            k = ISLT(ssb.keys[0], ssa.keys[0]);
            if (k) {
                if (k < 0)
                    goto Fail;
                sortslice_copy_incr(&dest, &ssb);
                ++bcount;
                acount = 0;
                --nb;
                if (nb == 0)
                    goto Succeed;
                if (bcount >= min_gallop)
                    break;
            }
            else {
                sortslice_copy_incr(&dest, &ssa);
                ++acount;
                bcount = 0;
                --na;
                if (na == 1)
                    goto CopyB;
                if (acount >= min_gallop)
                    break;
            }
        }

        /* One run is winning so consistently that galloping may
         * be a huge win.  So try that, and continue galloping until
         * (if ever) neither run appears to be winning consistently
         * anymore.
         */
        ++min_gallop;
        do {
            assert(na > 1 && nb > 0);
            min_gallop -= min_gallop > 1;
            ms->min_gallop = min_gallop;
            k = gallop_right(ssb.keys[0], ssa.keys, na, 0);
            acount = k;
            if (k) {
                if (k < 0)
                    goto Fail;
                sortslice_memcpy(&dest, 0, &ssa, 0, k);
                sortslice_advance(&dest, k);
                sortslice_advance(&ssa, k);
                na -= k;
                if (na == 1)
                    goto CopyB;
                /* na==0 is impossible now if the comparison
                 * function is consistent, but we can't assume
                 * that it is.
                 */
                if (na == 0)
                    goto Succeed;
            }
            sortslice_copy_incr(&dest, &ssb);
            --nb;
            if (nb == 0)
                goto Succeed;

            k = gallop_left(ssa.keys[0], ssb.keys, nb, 0);
            bcount = k;
            if (k) {
                if (k < 0)
                    goto Fail;
                sortslice_memmove(&dest, 0, &ssb, 0, k);
                sortslice_advance(&dest, k);
                sortslice_advance(&ssb, k);
                nb -= k;
                if (nb == 0)
                    goto Succeed;
            }
            sortslice_copy_incr(&dest, &ssa);
            --na;
            if (na == 1)
                goto CopyB;
        } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP);
        ++min_gallop;           /* penalize it for leaving galloping mode */
        ms->min_gallop = min_gallop;
    }
Succeed:
    result = 0;
Fail:
    if (na)
        sortslice_memcpy(&dest, 0, &ssa, 0, na);
    return result;
CopyB:
    assert(na == 1 && nb > 0);
    /* The last element of ssa belongs at the end of the merge. */
    sortslice_memmove(&dest, 0, &ssb, 0, nb);
    sortslice_copy(&dest, nb, &ssa, 0);
    return 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 957 of file listobject.c.

{
    s1->keys[i] = s2->keys[j];
    if (s1->values != NULL)
        s1->values[i] = s2->values[j];
}

Here is the call graph for this function:

PyDoc_STRVAR ( getitem_doc  ,
"x.__getitem__(y) <=  ,
x [y] 
)
PyDoc_STRVAR ( reversed_doc  ,
"L.__reversed__() -- return a reverse iterator over the list"   
)
PyDoc_STRVAR ( sizeof_doc  ,
"L.__sizeof__() -- size of L in  memory,
in bytes  
)
PyDoc_STRVAR ( append_doc  ,
"L.append(object) -- append object to end  
)
PyDoc_STRVAR ( extend_doc  ,
"L.extend(iterable) -- extend list by appending elements from the iterable  
)
PyDoc_STRVAR ( insert_doc  ,
"L.insert(index, object) -- insert object before index  
)
PyDoc_STRVAR ( pop_doc  ,
"L.pop([index]) -> item -- remove and return item at index (default last).\n""Raises IndexError if list is empty or index is out of range."   
)
PyDoc_STRVAR ( remove_doc  ,
"L.remove(value) -- remove first occurrence of value.\n""Raises ValueError if the value is not present."   
)
PyDoc_STRVAR ( index_doc  ,
"L.index(value, [start, [stop]]) -> integer -- return first index of value.\n""Raises ValueError if the value is not present."   
)
PyDoc_STRVAR ( count_doc  ,
"L.count(value) -> integer -- return number of occurrences of value  
)
PyDoc_STRVAR ( reverse_doc  ,
"L.reverse() -- reverse *IN PLACE*"   
)
PyDoc_STRVAR ( sort_doc  ,
"L.sort(key=None, reverse=False) -- stable sort *IN PLACE*"   
)
PyDoc_STRVAR ( list_doc  ,
"list() -> new empty list\n""list(iterable) -> new list initialized from iterable's items"   
)
PyDoc_STRVAR ( length_hint_doc  ,
"Private method returning an estimate of len(list(it))."   
)
int PyList_Append ( PyObject op,
PyObject newitem 
)

Definition at line 286 of file listobject.c.

{
    if (PyList_Check(op) && (newitem != NULL))
        return app1((PyListObject *)op, newitem);
    PyErr_BadInternalCall();
    return -1;
}

Here is the call graph for this function:

Definition at line 2094 of file listobject.c.

{
    PyObject *w;
    PyObject **p, **q;
    Py_ssize_t n;
    if (v == NULL || !PyList_Check(v)) {
        PyErr_BadInternalCall();
        return NULL;
    }
    n = Py_SIZE(v);
    w = PyTuple_New(n);
    if (w == NULL)
        return NULL;
    p = ((PyTupleObject *)w)->ob_item;
    q = ((PyListObject *)v)->ob_item;
    while (--n >= 0) {
        Py_INCREF(*q);
        *p = *q;
        p++;
        q++;
    }
    return w;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 101 of file listobject.c.

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 179 of file listobject.c.

{
    if (!PyList_Check(op)) {
        PyErr_BadInternalCall();
        return NULL;
    }
    if (i < 0 || i >= Py_SIZE(op)) {
        if (indexerr == NULL) {
            indexerr = PyUnicode_FromString(
                "list index out of range");
            if (indexerr == NULL)
                return NULL;
        }
        PyErr_SetObject(PyExc_IndexError, indexerr);
        return NULL;
    }
    return ((PyListObject *)op) -> ob_item[i];
}

Here is the call graph for this function:

Here is the caller graph for this function:

PyObject* PyList_GetSlice ( PyObject a,
Py_ssize_t  ilow,
Py_ssize_t  ihigh 
)

Definition at line 455 of file listobject.c.

{
    if (!PyList_Check(a)) {
        PyErr_BadInternalCall();
        return NULL;
    }
    return list_slice((PyListObject *)a, ilow, ihigh);
}

Here is the call graph for this function:

Here is the caller graph for this function:

int PyList_Insert ( PyObject op,
Py_ssize_t  where,
PyObject newitem 
)

Definition at line 256 of file listobject.c.

{
    if (!PyList_Check(op)) {
        PyErr_BadInternalCall();
        return -1;
    }
    return ins1((PyListObject *)op, where, newitem);
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 113 of file listobject.c.

{
    PyListObject *op;
    size_t nbytes;
#ifdef SHOW_ALLOC_COUNT
    static int initialized = 0;
    if (!initialized) {
        Py_AtExit(show_alloc);
        initialized = 1;
    }
#endif

    if (size < 0) {
        PyErr_BadInternalCall();
        return NULL;
    }
    /* Check for overflow without an actual overflow,
     *  which can cause compiler to optimise out */
    if ((size_t)size > PY_SIZE_MAX / sizeof(PyObject *))
        return PyErr_NoMemory();
    nbytes = size * sizeof(PyObject *);
    if (numfree) {
        numfree--;
        op = free_list[numfree];
        _Py_NewReference((PyObject *)op);
#ifdef SHOW_ALLOC_COUNT
        count_reuse++;
#endif
    } else {
        op = PyObject_GC_New(PyListObject, &PyList_Type);
        if (op == NULL)
            return NULL;
#ifdef SHOW_ALLOC_COUNT
        count_alloc++;
#endif
    }
    if (size <= 0)
        op->ob_item = NULL;
    else {
        op->ob_item = (PyObject **) PyMem_MALLOC(nbytes);
        if (op->ob_item == NULL) {
            Py_DECREF(op);
            return PyErr_NoMemory();
        }
        memset(op->ob_item, 0, nbytes);
    }
    Py_SIZE(op) = size;
    op->allocated = size;
    _PyObject_GC_TRACK(op);
    return (PyObject *) op;
}

Here is the call graph for this function:

Definition at line 2080 of file listobject.c.

{
    PyListObject *self = (PyListObject *)v;

    if (v == NULL || !PyList_Check(v)) {
        PyErr_BadInternalCall();
        return -1;
    }
    if (Py_SIZE(self) > 1)
        reverse_slice(self->ob_item, self->ob_item + Py_SIZE(self));
    return 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int PyList_SetItem ( register PyObject op,
register Py_ssize_t  i,
register PyObject newitem 
)

Definition at line 199 of file listobject.c.

{
    register PyObject *olditem;
    register PyObject **p;
    if (!PyList_Check(op)) {
        Py_XDECREF(newitem);
        PyErr_BadInternalCall();
        return -1;
    }
    if (i < 0 || i >= Py_SIZE(op)) {
        Py_XDECREF(newitem);
        PyErr_SetString(PyExc_IndexError,
                        "list assignment index out of range");
        return -1;
    }
    p = ((PyListObject *)op) -> ob_item + i;
    olditem = *p;
    *p = newitem;
    Py_XDECREF(olditem);
    return 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int PyList_SetSlice ( PyObject a,
Py_ssize_t  ilow,
Py_ssize_t  ihigh,
PyObject v 
)

Definition at line 671 of file listobject.c.

{
    if (!PyList_Check(a)) {
        PyErr_BadInternalCall();
        return -1;
    }
    return list_ass_slice((PyListObject *)a, ilow, ihigh, v);
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 166 of file listobject.c.

{
    if (!PyList_Check(op)) {
        PyErr_BadInternalCall();
        return -1;
    }
    else
        return Py_SIZE(op);
}

Here is the caller graph for this function:

Definition at line 2058 of file listobject.c.

{
    if (v == NULL || !PyList_Check(v)) {
        PyErr_BadInternalCall();
        return -1;
    }
    v = listsort((PyListObject *)v, (PyObject *)NULL, (PyObject *)NULL);
    if (v == NULL)
        return -1;
    Py_DECREF(v);
    return 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void reverse_slice ( PyObject **  lo,
PyObject **  hi 
) [static]

Definition at line 925 of file listobject.c.

{
    assert(lo && hi);

    --hi;
    while (lo < hi) {
        PyObject *t = *lo;
        *lo = *hi;
        *hi = t;
        ++lo;
        --hi;
    }
}

Here is the caller graph for this function:

static void reverse_sortslice ( sortslice s,
Py_ssize_t  n 
) [static]

Definition at line 1870 of file listobject.c.

{
    reverse_slice(s->keys, &s->keys[n]);
    if (s->values != NULL)
        reverse_slice(s->values, &s->values[n]);
}

Here is the call graph for this function:

Here is the caller graph for this function:


Variable Documentation

Definition at line 97 of file listobject.c.

PyObject* indexerr = NULL [static]

Definition at line 176 of file listobject.c.

Initial value:

Definition at line 2600 of file listobject.c.

Initial value:
 {
    {"__getitem__", (PyCFunction)list_subscript, METH_O|METH_COEXIST, getitem_doc},
    {"__reversed__",(PyCFunction)list_reversed, METH_NOARGS, reversed_doc},
    {"__sizeof__",  (PyCFunction)list_sizeof, METH_NOARGS, sizeof_doc},
    {"append",          (PyCFunction)listappend,  METH_O, append_doc},
    {"insert",          (PyCFunction)listinsert,  METH_VARARGS, insert_doc},
    {"extend",      (PyCFunction)listextend,  METH_O, extend_doc},
    {"pop",             (PyCFunction)listpop,     METH_VARARGS, pop_doc},
    {"remove",          (PyCFunction)listremove,  METH_O, remove_doc},
    {"index",           (PyCFunction)listindex,   METH_VARARGS, index_doc},
    {"count",           (PyCFunction)listcount,   METH_O, count_doc},
    {"reverse",         (PyCFunction)listreverse, METH_NOARGS, reverse_doc},
    {"sort",            (PyCFunction)listsort,    METH_VARARGS | METH_KEYWORDS, sort_doc},
    {NULL,              NULL}           
}

Definition at line 2351 of file listobject.c.

Initial value:
 {
    {"__length_hint__", (PyCFunction)listiter_len, METH_NOARGS, length_hint_doc},
    {NULL,              NULL}           
}

Definition at line 2666 of file listobject.c.

Initial value:
 {
    {"__length_hint__", (PyCFunction)listreviter_len, METH_NOARGS, length_hint_doc},
    {NULL,              NULL}           
}

Definition at line 2788 of file listobject.c.

int numfree = 0 [static]

Definition at line 98 of file listobject.c.

Definition at line 2606 of file listobject.c.

Definition at line 2671 of file listobject.c.

Definition at line 2793 of file listobject.c.