Python内建类型list源码学习

>>> l = [1, 2, 3]
>>> l.append(4)
>>> l
[1, 2, 3, 4]

>>> l = [1, 2, 3, 4]
>>> l.pop()
4
>>> l
[1, 2, 3]

>>> l = [1, 2, 3, 4]
>>> l.pop(0)  # 指定index
1
>>> l
[2, 3, 4]

>>> l = [1, 2, 3]
>>> l.insert(0, 4)
>>> l
[4, 1, 2, 3]

>>> l = [1, 2, 3, 4]
>>> l.index(1)
0

>>> l = [1, 2, 3]
>>> l.extend({1: 2, 3: 4})
>>> l
[1, 2, 3, 1, 3]

>>> l = [1, 2, 3, 1]
>>> l.count(1)
2
>>> l.count(2)
1

>>> l = [1, 2, 3]
>>> l.reverse()
>>> l
[3, 2, 1]

>>> l = [1, 2, 3]
>>> l.clear()
>>> l
[]

typedef struct {
    PyObject_VAR_HEAD
    /* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */
    PyObject **ob_item;
    /* ob_item contains space for 'allocated' elements.  The number
     * currently in use is ob_size.
     * Invariants:
     *     0 <= ob_size <= allocated
     *     len(list) == ob_size
     *     ob_item == NULL implies ob_size == allocated == 0
     * list.sort() temporarily sets allocated to -1 to detect mutations.
     * Items must normally not be NULL, except during construction when
     * the list is not yet visible outside the function that builds it.
     */
    Py_ssize_t allocated;
} PyListObject;

q = []
q.append(1)
q.append(2)
q.append(3)
# deque
q.pop(0)

from collections import deque
q = deque()
# enqueue
q.append(job)
# deque
q.popleft()

>>> l1 = [1, [1, 2, 3]]
>>> l1
[1, [1, 2, 3]]
# 浅拷贝
>>> l2 = l1.copy()
>>> l2
[1, [1, 2, 3]]
# 修改新列表中的可变元素
>>> l2[1][0] = 6
>>> l2
[1, [6, 2, 3]]
>>> l1
[1, [6, 2, 3]]

>>> l1 = [1, [1, 2, 3]]
>>> l1
[1, [1, 2, 3]]
# 浅拷贝
>>> l2 = l1.copy()
>>> l2
[1, [1, 2, 3]]
# 修改新列表中的不可变元素
>>> l2[0] = 2
>>> l2
[2, [1, 2, 3]]
>>> l1
[1, [1, 2, 3]]

>>> l1 = [1, [1, 2, 3]]
>>> l1
[1, [1, 2, 3]]
# 浅拷贝
>>> l2 = l1.copy()
>>> l2
[1, [1, 2, 3]]
# 这里要注意并没有修改可变元素[1, 2, 3]，而是将l2[1]处的指针修改了，指向了一个新对象[3, 4]
>>> l2[1] = [3, 4]
>>> l2
[2, [3, 4]]
>>> l1
[1, [1, 2, 3]]

>>> from copy import deepcopy
>>> l1 = [1, [1, 2, 3]]
>>> l1
[1, [1, 2, 3]]
# 深拷贝
>>> l2 = deepcopy(l1)
>>> l2
[1, [1, 2, 3]]
>>> l2[1][0] = 5
>>> l2
[1, [5, 2, 3]]
>>> l1
[1, [1, 2, 3]]
>>> l2[0] = 2
>>> l2
[2, [5, 2, 3]]
>>> l1
[1, [1, 2, 3]]

static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
    PyObject **items;
    size_t new_allocated, num_allocated_bytes;
    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, ...
     * Note: new_allocated won't overflow because the largest possible value
     *       is PY_SSIZE_T_MAX * (9 / 8) + 6 which always fits in a size_t.
     */
    new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);
    if (new_allocated > (size_t)PY_SSIZE_T_MAX / sizeof(PyObject *)) {
        PyErr_NoMemory();
        return -1;
    }

    if (newsize == 0)
        new_allocated = 0;
    num_allocated_bytes = new_allocated * sizeof(PyObject *);
    items = (PyObject **)PyMem_Realloc(self->ob_item, num_allocated_bytes);
    if (items == NULL) {
        PyErr_NoMemory();
        return -1;
    }
    self->ob_item = items;
    Py_SIZE(self) = newsize;
    self->allocated = new_allocated;
    return 0;
}

PyAPI_FUNC(void *) PyMem_Realloc(void *ptr, size_t new_size);

static int
app1(PyListObject *self, PyObject *v)
{
    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) < 0)
        return -1;

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

static int
ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
{
    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) < 0)
        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;
}

static PyObject *
list_pop_impl(PyListObject *self, Py_ssize_t index)
/*[clinic end generated code: output=6bd69dcb3f17eca8 input=b83675976f329e6f]*/
{
    PyObject *v;
    int status;

    if (Py_SIZE(self) == 0) {
        /* Special-case most common failure cause */
        PyErr_SetString(PyExc_IndexError, "pop from empty list");
        return NULL;
    }
    if (index < 0)
        index += Py_SIZE(self);
    if (index < 0 || index >= Py_SIZE(self)) {
        PyErr_SetString(PyExc_IndexError, "pop index out of range");
        return NULL;
    }
    v = self->ob_item[index];
    if (index == Py_SIZE(self) - 1) {
        status = list_resize(self, Py_SIZE(self) - 1);
        if (status >= 0)
            return v; /* and v now owns the reference the list had */
        else
            return NULL;
    }
    Py_INCREF(v);
    status = list_ass_slice(self, index, index+1, (PyObject *)NULL);
    if (status < 0) {
        Py_DECREF(v);
        return NULL;
    }
    return v;
}

static PyObject *
list_remove(PyListObject *self, PyObject *value)
/*[clinic end generated code: output=f087e1951a5e30d1 input=2dc2ba5bb2fb1f82]*/
{
    Py_ssize_t i;

    for (i = 0; i < Py_SIZE(self); i++) {
        int cmp = PyObject_RichCompareBool(self->ob_item[i], value, 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;
}

static PyObject *
list_remove(PyListObject *self, PyObject *value)
/*[clinic end generated code: output=f087e1951a5e30d1 input=2dc2ba5bb2fb1f82]*/
{
    Py_ssize_t i;

    for (i = 0; i < Py_SIZE(self); i++) {
        int cmp = PyObject_RichCompareBool(self->ob_item[i], value, 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;
}