Home CPython C

# Python List 实现原理

Python list 对象的一些介绍：https://www.runoob.com/python3/python3-list.html

基于 CPython3.9.12 版本阅读

在 CPython 中 list 对应 PyListObject，位于 objects/listobject.c

PyTypeObject PyList_Type = {
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    "list",
    sizeof(PyListObject),
    0,
    (destructor)list_dealloc,                   /* tp_dealloc */
    0,                                          /* tp_vectorcall_offset */
    0,                                          /* tp_getattr */
    0,                                          /* tp_setattr */
    0,                                          /* tp_as_async */
    (reprfunc)list_repr,                        /* tp_repr */
    0,                                          /* tp_as_number */
    &list_as_sequence,                          /* tp_as_sequence */
    &list_as_mapping,                           /* tp_as_mapping */
    PyObject_HashNotImplemented,                /* tp_hash */
    0,                                          /* tp_call */
    0,                                          /* tp_str */
    PyObject_GenericGetAttr,                    /* tp_getattro */
    0,                                          /* tp_setattro */
    0,                                          /* tp_as_buffer */
    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
        Py_TPFLAGS_BASETYPE | Py_TPFLAGS_LIST_SUBCLASS, /* tp_flags */
    list___init____doc__,                       /* tp_doc */
    (traverseproc)list_traverse,                /* tp_traverse */
    (inquiry)_list_clear,                       /* tp_clear */
    list_richcompare,                           /* tp_richcompare */
    0,                                          /* tp_weaklistoffset */
    list_iter,                                  /* tp_iter */
    0,                                          /* tp_iternext */
    list_methods,                               /* tp_methods */
    0,                                          /* tp_members */
    0,                                          /* tp_getset */
    0,                                          /* tp_base */
    0,                                          /* tp_dict */
    0,                                          /* tp_descr_get */
    0,                                          /* tp_descr_set */
    0,                                          /* tp_dictoffset */
    (initproc)list___init__,                    /* tp_init */
    PyType_GenericAlloc,                        /* tp_alloc */
    PyType_GenericNew,                          /* tp_new */
    PyObject_GC_Del,                            /* tp_free */
    .tp_vectorcall = list_vectorcall,
};

分别定义了__new__方法和__init__，先来看看在调用 list () 时，做了什么，__new__调用了 PyType_GenericNew

PyObject *
PyType_GenericNew(PyTypeObject *type, PyObject *args, PyObject *kwds)
{
    return type->tp_alloc(type, 0); // 先为对象分配空间
}

__init__调用了 list___init__方法

static int
list___init__(PyObject *self, PyObject *args, PyObject *kwargs)
{
    int return_value = -1; // 返回值，-1 在 CPython 里表示异常，(hash 不会出现 - 1, 为 - 1 的哈希会返回 - 2)
    PyObject *iterable = NULL;
    if (Py_IS_TYPE(self, &PyList_Type) &&
        !_PyArg_NoKeywords("list", kwargs)) {
	// 如果类型为 List 并且没有关键字，则直接结束
        goto exit;
    }
    if (!_PyArg_CheckPositional("list", PyTuple_GET_SIZE(args), 0, 1)) {
	// 如果传递的位置参数不为 0 到 1 个，
        goto exit;
    }
    if (PyTuple_GET_SIZE(args) < 1) {
	// 如果位置参数参数小于 1，则跳到 skip_optional 创建 list, 但是是空列表
        goto skip_optional;
    }
    iterable = PyTuple_GET_ITEM(args, 0); // 获取 args 的第一个元素，也就是 [...]
skip_optional:
    return_value = list___init___impl((PyListObject *)self, iterable); // 创建列表
exit:
    return return_value;
}
static int
list___init___impl(PyListObject *self, PyObject *iterable)
/*[clinic end generated code: output=0f3c21379d01de48 input=b3f3fe7206af8f6b]*/
{
    /* 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 (iterable != NULL) { // 如果传递了 [...] 对象，则进入 if statement
        if (_PyObject_HasLen(iterable)) {
	    /*
		_PyObject_HasLen 主要判断 iterable 对象是否实现了序列协议的对象相关字段附加结构 (tp_as_sequence) 或者
		是否实现了映射协议的对象相关字段的附加结构 (tp_as_mapping)
	    */
            Py_ssize_t iter_len = PyObject_Size(iterable);
	    /*
		PyObject_Size 主要用来获取 iterable 对象的长度，如果该对象定义了 tp_as_sequence 协议，
		则会判断 tp_as_sequence 协议是否实现__len__方法，定义了则调用__len__, 如果没有定义，
		则再次获取 tp_as_mapping 协议，并在 tp_as_mapping 协议里判断是否定义__len__，定义了则调用，如果两个协议都没有
		定义__len__, 则返回 - 1
	    */
            if (iter_len == -1) {
                if (!PyErr_ExceptionMatches(PyExc_TypeError)) {
		    // 创建失败
                    return -1;
                }
                PyErr_Clear();
            }
            if (iter_len > 0 && self->ob_item == NULL
                && list_preallocate_exact(self, iter_len)) {
		// 长度大于 0、ob_item 为 NULL, 用于真正存储列表的元素，list_preallocate_exact 为列表预分配内存，调用 C 的 malloc
                return -1;
            }
        }
        PyObject *rv = list_extend(self, iterable); // 最主要的方法，代码太长，分开粘
        if (rv == NULL)
            return -1;
        Py_DECREF(rv);
    }
    return 0;
}
经过源码分析发现，在调用 list ([…]) 时，实际上是调用了 list 对象的 extend 方法，代码也比较长，一点一点分析😵


static PyObject *
list_extend(PyListObject *self, PyObject *iterable)
/*[clinic end generated code: output=630fb3bca0c8e789 input=9ec5ba3a81be3a4d]*/
{
    PyObject *it;      /* iter(v) */
    Py_ssize_t m;                  /* size of self */
    Py_ssize_t n;                  /* guess for size of iterable */
    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(iterable) || PyTuple_CheckExact(iterable) ||
                (PyObject *)self == iterable) { // 判断 iterable 是否为 list 类型或者 tuple 类型
        PyObject **src, **dest; // 两个二级指针
        iterable = PySequence_Fast(iterable, "argument must be iterable");
        if (!iterable)
            return NULL;
        n = PySequence_Fast_GET_SIZE(iterable); // 获取 iterable 的大小
        if (n == 0) {
            /* short circuit when iterable is empty */
            Py_DECREF(iterable);
            Py_RETURN_NONE;
        }
        m = Py_SIZE(self); // 获取自身的大小
        /* It should not be possible to allocate a list large enough to cause
        an overflow on any relevant platform */
        assert(m < PY_SSIZE_T_MAX - n);
        if (list_resize(self, m + n) < 0) { // 扩容操作，比较重要，后面会讲
            Py_DECREF(iterable);
            return NULL;
        }
        /* note that we may still have self == iterable 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 iterable's items */
        src = PySequence_Fast_ITEMS(iterable); // 获取 iterable 的 ob_item, 真正用于存储元素
        dest = self->ob_item + m;
        for (i = 0; i < n; i++) { // 循环操作，将 iterable 里的每个元素设置到 self->ob_item 里
            PyObject *o = src[i];
            Py_INCREF(o);
            dest[i] = o;
        }
        Py_DECREF(iterable); // 引用计数 - 1
        Py_RETURN_NONE; // 返回 None, 结束
    }
    // 如果 iterable 不是 list 或者 tuple 类型，则会走到这
    it = PyObject_GetIter(iterable); // 获取 iterable 的__iter__方法、调用，获取 iterator
    if (it == NULL)
	// 如果__iter__返回空则调用结束，失败
        return NULL;
    iternext = *Py_TYPE(it)->tp_iternext; // 从 iterator 中获取__next__方法
    /* Guess a result list size. */
    n = PyObject_LengthHint(iterable, 8); // 猜测结果列表的大小
    if (n < 0) {
	// 如果小于 0, 失败，结束调用
        Py_DECREF(it);
        return NULL;
    }
    m = Py_SIZE(self); // 获取自身的大小
    if (m > PY_SSIZE_T_MAX - n) { // 表示溢出
        /* 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.
         */
    }
    else {
        mn = m + n; // 自身大小加上 iterator 的大小
        /* Make room. */
        if (list_resize(self, mn) < 0) // 判断是否需要扩容
            goto error;
        /* Make the list sane again. */
        Py_SET_SIZE(self, m); // 继续保持大小
    }
    /* Run iterator to exhaustion. */
    for (;;) {
	// 死循环，不断调用__next__, 直到消耗完
        PyObject *item = iternext(it);
        if (item == NULL) {
	    //__next__返回空，结束循环
            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_SET_SIZE(self, Py_SIZE(self) + 1); // 自身大小 ob_size + 1
        }
        else {
	    // 没有大于已分配大小
            int status = app1(self, item); // 调用 app1 设置元素
            Py_DECREF(item);  /* append creates a new ref */
            if (status < 0)
		// 小于 0 可能因为内存溢出或者扩容失败
                goto error;
        }
    }
    /* Cut back result list if initial guess was too large. */
    if (Py_SIZE(self) < self->allocated) {
	// 这里也比较重要，再次判断自身大小是否小于已分配大小，并进行缩容，不需要多余的内存
        if (list_resize(self, Py_SIZE(self)) < 0)
            goto error;
    }
    Py_DECREF(it);
    Py_RETURN_NONE;
  error:
    Py_DECREF(it);
    return NULL;
}
static int
app1(PyListObject *self, PyObject *v)
{
    Py_ssize_t n = PyList_GET_SIZE(self); // 获取 list 对象大小
    assert (v != NULL);
    if (n == PY_SSIZE_T_MAX) {
        PyErr_SetString(PyExc_OverflowError,
            "cannot add more objects to list");
        return -1;
    }
    // 扩容操作，self 是列表，n+1 就是 newsize, 或者说新的 ob_size
    // 里面有很重要的一步，就是将列表的 ob_size 设置为 newsize, 也就是 n+1
    // 因为 append 之后列表长度大小会变化，而 ob_size 则时刻维护着这个大小
    if (list_resize(self, n+1) < 0)
	// 是否需要扩容
        return -1;
    Py_INCREF(v);
    PyList_SET_ITEM(self, n, v); // 根据大小 n 作为下标设置元素的位置
    return 0;
}
PyObject *
PySequence_Fast(PyObject *v, const char *m)
{
    //v 为传递进来的 iterable 对象
    PyObject *it;
    if (v == NULL) {
	// 为空则抛异常
        return null_error();
    }
    if (PyList_CheckExact(v) || PyTuple_CheckExact(v)) {
	// 校验是否为 list 或者为 typle, 如果满足条件，则直接返回该对象，否则往下走，创建一个空 list, 再调用 list_extend
        Py_INCREF(v);
        return v;
    }
    it = PyObject_GetIter(v); // 从 iterable 对象中获取__iter__方法，调用返回 iterator
    if (it == NULL) {
	// 如果返回了空，抛异常
        if (PyErr_ExceptionMatches(PyExc_TypeError))
            PyErr_SetString(PyExc_TypeError, m);
        return NULL;
    }
    v = PySequence_List(it); // 创建一个 list 对象
    Py_DECREF(it);
    return v;
}
PyObject *
PySequence_List(PyObject *v)
{
    PyObject *result;  /* result list */
    PyObject *rv;          /* return value from PyList_Extend */
    if (v == NULL) {
        return null_error();
    }
    result = PyList_New(0); // 创建 list，大小为 0
    if (result == NULL)
        return NULL;
    rv = _PyList_Extend((PyListObject *)result, v); // 里面调用的就是 extend 方法
    if (rv == NULL) {
        Py_DECREF(result);
        return NULL;
    }
    Py_DECREF(rv);
    return result;
}
PyObject *
_PyList_Extend(PyListObject *self, PyObject *iterable)
{
    return list_extend(self, iterable);
}
list_extend 做的事情其实并不复杂，主要先判断你传递的参数是否为 list 对象或者 tuple 对象，如果满足，则将该对象里的每个元素通过 for 循环一个一个设置到列表里，如果不是判断不是 list、tuple 对象，就会尝试获取该对象的__iter__方法，并 new 一个空列表，再通过调用 list_extend 重新走一遍；如果你一开始传递的参数就不是 list 或者 tuple，它就会直接获取该对象的__iter__方法，调用获取 iterator，然后获取 iterator 的__next__方法，并通过 for 死循环不断调用__next__获取元素并设置到列表，中间会一直判断是否需要扩容操作，最后还会判断是否需要进行缩容操作


# 列表扩容操作


创建 list 时，app1 方法在每次设置元素时都会调用 list_resize 判断是否需要扩容，现在来看看具体实现


static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
    //self 就是列表，newsize 就是指元素在添加之后的 ob_size
    // 比如列表当前 ob_size 为 5，添加一个元素之后为 6，发现容量不够，就会扩容，那么 newsize 就为 6
    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.
    */
    // 如果 newsize 达到容量的一般，但还没有超过容量，那么意味着 newsize、或者新的 ob_size 和容量是匹配的，不需要扩容
    if (allocated >= newsize && newsize >= (allocated >> 1)) {
        assert(self->ob_item != NULL || newsize == 0);
        Py_SET_SIZE(self, newsize); // 只需要将列表的 ob_size 设置为 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().
     * Add padding to make the allocated size multiple of 4.
     * The growth pattern is:  0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...
     * 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.
     */
    // 走到这，说明容量与 ob_size 不匹配了，需要进行扩容或者缩容
    // 需要申请新的底层数组，具体申请多少个，这个是公式
    new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;
    /* Do not overallocate if the new size is closer to overalocated size
     * than to the old size.
     */
    if (newsize - Py_SIZE(self) > (Py_ssize_t)(new_allocated - newsize))
        new_allocated = ((size_t)newsize + 3) & ~(size_t)3;
    if (newsize == 0) // 如果 newsize 为 0，那么容量也会变成 0，假设将列表全部清空了，容量就会变为 0
        new_allocated = 0;
    num_allocated_bytes = new_allocated * sizeof(PyObject *); // 在 list 数组中，存放的都是 PyObject *，所以要计算内存
    // 调用 C malloc 申请相应大小的内存，将其指针交给 items
    items = (PyObject **)PyMem_Realloc(self->ob_item, num_allocated_bytes);
    if (items == NULL) {
	// 申请内存失败，没有内存了
        PyErr_NoMemory();
        return -1;
    }
    self->ob_item = items; // 指向新的数组，此时列表就发生了扩容或缩容
    Py_SET_SIZE(self, newsize); // 设置列表的 ob_size 为 newsize
    self->allocated = new_allocated; // 设置新的容量大小
    return 0;
}


The growth pattern is:  0, 4, 8, 16, 24, 32, 40, 52, 64, 76, …，当发现容量不够时才会开始扩容




newsize = 0
ob_size = 0
allocated = 0
for i in range(100):
    newsize += 1
    if (allocated >= newsize and newsize >= (allocated >> 1)):
        ob_size = newsize
        continue
    new_allocated = (newsize + (newsize >> 3) + 6) & ~3
    print("new allocated: ", new_allocated)
    if (newsize - ob_size > (new_allocated - newsize)):
        new_allocated = (newsize + 3) & ~3
        print("update new allocated: ", new_allocated)
    ob_size = newsize
    allocated = new_allocated
=====================> 打印结果
new allocated:  4
new allocated:  8
new allocated:  16
new allocated:  24
new allocated:  32
new allocated:  40
new allocated:  52
new allocated:  64
new allocated:  76
new allocated:  92
new allocated:  108
不断往空列表中 append 元素时，容量就会按上面的规律变化


lst = []
allocated = 0
for item in range(100):
    lst.append(item)
    # 计算 ob_size
    ob_size = len(lst)
    if ob_size > allocated:
        allocated = (lst.__sizeof__() - [].__sizeof__()) // 8
        print("new allocated: ", allocated, "ob size: ", lst.__sizeof__() - [].__sizeof__())
=====================> 打印结果
new allocated:  4 ob size:  32
new allocated:  8 ob size:  64
new allocated:  16 ob size:  128
new allocated:  24 ob size:  192
new allocated:  32 ob size:  256
new allocated:  40 ob size:  320
new allocated:  52 ob size:  416
new allocated:  64 ob size:  512
new allocated:  76 ob size:  608
new allocated:  92 ob size:  736
new allocated:  108 ob size:  864
如果直接通过 lst = [] 这种方式创建列表，那么其长度和容量是一样的


lst = [0] * 1000
# 长度与容量是一样的
print(len(lst), (lst.__sizeof__() - [].__sizeof__()) // 8)
# 如果此时添加一个元素，那么 ob_size 就会变为 1001, 大于容量 1000
# 此时列表会进行扩容，按照计算公式进行变化
# new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;
print("新容量: ", (1001 + (1001 >> 3) + 6) & ~3) # 新容量: 1132
# 添加一个元素
lst.append(0)
# 计算容量，结果是一样的
print((lst.__sizeof__() - [].__sizeof__()) // 8) # 1132
了解完扩容，还有一个缩容的情况，假如在扩容操作时，发现长度没有超过容量但又达到容量的一半，是不会缩容的，如果发现空闲了 8 个位置，但只需要两个，那么此时就会进行缩容操作


lst = [0] * 1000
# 长度与容量是一样的
print(len(lst), (lst.__sizeof__() - [].__sizeof__()) // 8) # 1000:1000
# 删除 500 个元素，此时 ob_size 为 500
lst[:500] = []
# 此时容量达到容量一半，不会缩容
print(len(lst), (lst.__sizeof__() - [].__sizeof__()) // 8) # 1000:1000
# 如果再删除一个元素，那么此时就会进行缩容操作 ob_size 变成 499, 小于 1000 // 2
# 缩容公式还是一样的: new_allocated = ((size_t) newsize + (newsize >> 3) + 6) & ~(size_t) 3;
print((499 + (499 >> 3) + 6) & ~3) # 564
_ = lst.pop()
print(len(lst), (lst.__sizeof__() - [].__sizeof__()) // 8) # 长度 499 容量 564
此外还有一个判断为 if (newsize == 0)，如果 newsize 为 0，那么容量也是 0


lst = [0] * 1000
print(len(lst), (lst.__sizeof__() - [].__sizeof__()) // 8) # 1000:1000
lst[:] = []
print(len(lst), (lst.__sizeof__() - [].__sizeof__()) // 8) # 0:0
print((0 + (0 >> 3) + 6) & ~3) # 4
当发现 newsize 为 0 时，就会把容量设置为 0，CPython 认为列表长度为 0 的话，可能你并不想使用这个列表


# 获取元素


我们在使用列表时，可以通过下标：lst [1] 这种方式获取元素，那么底层是怎么实现的？


PyListType 里定义了映射协议结构


static PyMappingMethods list_as_mapping = {
    (lenfunc)list_length,
    (binaryfunc)list_subscript,
    (objobjargproc)list_ass_subscript
};
通过下标获取元素时会触发 list_subscript 方法


static PyObject *
list_subscript(PyListObject* self, PyObject* item)
{
    // 先判断 item 是不是一个整数，item 除了整数之外，也可以是切片
    if (_PyIndex_Check(item)) {
        Py_ssize_t i;
	// 检测 i 是否合法，因为 Python 的整型没有限制，列表长度和容量是由具体类型的变量维护的，这个数是有范围的
	// 如果输入一个过大的数字，Python 会报错：IndexError: cannot fit 'int' into an index-sized integer
        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); // 调用 list_item 通过 ob_item [i] 获取元素，方法在下边
    }
    else if (PySlice_Check(item)) {
	// 走到这说明是一个切片
	//start: 切片起始位置、stop: 切片结束位置、step：步长
	//slicelength: 获取元素个数，比如 [1:5:2], 那么就为 2, 因为只能获取索引为 1 和 3 的元素
	//i: 循环变量，因为切片只能循环获取每一个元素，比如 [1:5:2], 需要循环两次，第一次 cur 为 1, 第二次 cur 为 3
        Py_ssize_t start, stop, step, slicelength, i;
        size_t cur; // 底层数组中元素的索引
        PyObject* result; // 返回结果
        PyObject* it;
        PyObject **src, **dest;
        if (PySlice_Unpack(item, &start, &stop, &step) < 0) {
	    // 对切片 item 进行解包，得到起始、结束、步长
            return NULL;
        }
	// 计算 slicelength, 我记得前面的文章好像分析过 PySlice_AdjustIndices 里面的源码，是不是 range 源码解析❓
        slicelength = PySlice_AdjustIndices(Py_SIZE(self), &start, &stop,
                                            step);
	// 如果 slicelength 为 0, 说明没有元素可以获取，因此直接返回一个空列表即可
        if (slicelength <= 0) {
            return PyList_New(0);
        }
	// 如果步长为 1, 那么在 list_slice 内部会创建一个 PyListObject *np, 申请相应的底层数组，设置 allocated
	//allocated 为 stop-start, 然后将参数列表中索引为 ilow 的元素到索引为 ihigh 的元素依次拷贝到 np->ob_item, 然后设置 ob_size 并返回
        else if (step == 1) {
            return list_slice(self, start, stop);
        }
        else {
	    // 走到这，说明步长不为 1, result 为 PyListObject *, 底层数组没有存储在 PyListObject 中，而是通过 ob_item 关联
	    //list_new_prealloc 就是申请底层数组、设置容量，这里容量为 slicelength
            result = list_new_prealloc(slicelength);
            if (!result) return NULL;
            src = self->ob_item; //src 为二级指针
            dest = ((PyListObject *)result)->ob_item; // 同理 src
	    // 进行循环操作，cur 从 start 开始遍历，每次加上 step 步长
            for (cur = start, i = 0; i < slicelength;
                 cur += (size_t)step, i++) {
                it = src[cur]; //it 就是 self->ob_item 中的元素
                Py_INCREF(it); // 获取元素的对象引用计数 + 1
                dest[i] = it; // 将获取元素设置到 dest
            }
            Py_SET_SIZE(result, slicelength); // 将大小设置为 slicelength, 说明通过切片创建新列表，其长度和容量也是一致的
            return result; // 返回结果
        }
    }
    else {
	//item 不合法
        PyErr_Format(PyExc_TypeError,
                     "list indices must be integers or slices, not %.200s",
                     Py_TYPE(item)->tp_name);
        return NULL;
    }
}
static PyObject *
list_item(PyListObject *a, Py_ssize_t i)
{
    // 检测索引 i 的合法性，如果 i > 列表长度，那么会报索引越界错误
    if (!valid_index(i, Py_SIZE(a))) {
	// 如果索引为负数也会报索引越界错误，因为上面已经对负数做了处理了，如果还是一个负数，那么同样报错
	// 假设列表长度为 3, 索引为 - 100, 加上长度后是 - 97, 结果还是负数，所以还是会报错
        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]); // 引用计数 + 1
    return a->ob_item[i]; // 通过下标获取第 i 个元素
}
分析过后，其实列表的切片操作也不是什么神奇的操作，实现的逻辑也比较简单


# 创建 PyListObject


创建一个列表，在 Python 底层只提供了唯一一个 Python/C API，此方法接收一个 size 参数，允许我们在创建一个 PyListObject 时，指定底层数组的长度


PyObject *
PyList_New(Py_ssize_t size)
{
    PyListObject *op; // 声明一个 PyListObject * 对象
    if (size < 0) {
	//size 大小小于 0, 抛异常
        PyErr_BadInternalCall();
        return NULL;
    }
    // 缓存池是否可用
    if (numfree) {
	// 将缓存池内对象个数 - 1
        numfree--;
	// 从缓存池中获取一个
        op = free_list[numfree];
	// 设置引用计数
        _Py_NewReference((PyObject *)op);
    } else {
	// 缓存池不可用时，就申请内存
        op = PyObject_GC_New(PyListObject, &PyList_Type);
        if (op == NULL) // 申请失败
            return NULL;
    }
    if (size <= 0)
	// 如果 size 小于等于 0, ob_item 就设置为 NULL
        op->ob_item = NULL;
    else {
	// 否则，创建一个指定容量的指针数组，然后让 ob_item 指向它
	// 所以是先创建 PyListObject 对象，然后创建底层数组，最后通过 ob_item 关联
        op->ob_item = (PyObject **) PyMem_Calloc(size, sizeof(PyObject *));
        if (op->ob_item == NULL) {
            Py_DECREF(op);
            return PyErr_NoMemory();
        }
    }
    Py_SET_SIZE(op, size); // 设置 ob_size
    op->allocated = size; // 设置 allocated
    _PyObject_GC_TRACK(op); // GC 管理
    return (PyObject *) op;
}
在创建 PyListObject 对象时，会先检测缓存池是否可用，有就直接拿来用，否则通过 malloc 在系统堆上申请，缓存池最多维护 80 个 PyListObject 对象


/* Empty list reuse scheme to save calls to malloc and free */
#ifndef PyList_MAXFREELIST
#  define PyList_MAXFREELIST 80
#endif
static PyListObject *free_list[PyList_MAXFREELIST];
既然能从缓存池中获取，那么在执行析构函数时，也要把列表放到缓存池中


static void
list_dealloc(PyListObject *op)
{
    Py_ssize_t i;
    PyObject_GC_UnTrack(op);
    Py_TRASHCAN_BEGIN(op, list_dealloc)
    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) {
	    // 将底层数组中每个指针指向的对象的引用计数都 - 1
            Py_XDECREF(op->ob_item[i]);
        }
        PyMem_FREE(op->ob_item); // 释放底层数组所占的内存
    }
    // 判断缓存池里面 PyLitObject 对象的个数，如果没满，就添加到缓存池
    if (numfree < PyList_MAXFREELIST && PyList_CheckExact(op))
        free_list[numfree++] = op;
    else
	// 否则缓存池满了，就将 PyListObject 对象所占的内存释放
        Py_TYPE(op)->tp_free((PyObject *)op);
    Py_TRASHCAN_END
}
在创建一个 PyListObject 对象时，实际上分为了两步，先创建 PyListObject 对象，然后创建底层数组，最后让 PyListObject 对象中的 ob_item 指向这个底层数组，那么销毁一个 PyListObject 对象时，也就先销毁 ob_item 维护的底层数组，然后再释放 PyListObject 对象本身（在缓存池已满的情况下）


16594995161.jpg


可以看到，b 对象与 a 对象的地址是一致的


还有一些方法，有需要可以自己去查看源码了解一下，我懒得看了😂


static PyMethodDef list_methods[] = {
    {"__getitem__", (PyCFunction)list_subscript, METH_O|METH_COEXIST, "x.__getitem__(y) <==> x[y]"},
    LIST___REVERSED___METHODDEF
    LIST___SIZEOF___METHODDEF
    LIST_CLEAR_METHODDEF
    LIST_COPY_METHODDEF
    LIST_APPEND_METHODDEF
    LIST_INSERT_METHODDEF
    LIST_EXTEND_METHODDEF
    LIST_POP_METHODDEF
    LIST_REMOVE_METHODDEF
    LIST_INDEX_METHODDEF
    LIST_COUNT_METHODDEF
    LIST_REVERSE_METHODDEF
    LIST_SORT_METHODDEF
    {"__class_getitem__", (PyCFunction)Py_GenericAlias, METH_O|METH_CLASS, PyDoc_STR("See PEP 585")},
    {NULL,              NULL}           /* sentinel */
};


      

          
          
      

  


   


    

  
    
      
    
    Edited on
    
  
  
      
        
      
      Views
      
      times
  



      


  
  
Give me a cup of [coffee]~(￣▽￣)~*

  

      
      

        小芳芳 WeChat Pay
        
WeChat Pay

      

      
      

        小芳芳 Alipay
        
Alipay