Python 列表源码解析

快来打我* 2022-05-29 05:24 227阅读 0赞

列表作为python 最常用的一种数据类型, 一直很好奇其是如何实现动态的扩展的，于是上github看了源代码（[https://github.com/python/cpython/blob/master/Include/listobject.h][https_github.com_python_cpython_blob_master_Include_listobject.h]， [https://github.com/python/cpython/blob/master/Objects/listobject.c][https_github.com_python_cpython_blob_master_Objects_listobject.c]），结合《python源码剖析》分享一下自己的收获!

列表源码定义

#ifndef Py_LIMITED_API
    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;
    #endif

allocated 记录了这个列表申请的内存大小, 假如一个列表中可以容纳10个元素，则allocated 就是10，当我们往列表中添加或者删除元素时这个大小都会跟着改变

ob\_size 则是记录了当前列表中 已经使用的大小

allocated 和 ob\_size 都和内存管理有关，python的列表总是会被频繁的添加或者删除元素，因此频繁的申请释放内存显然是不明智的,所以python的列表在创建时总是会申请一大块内存，申请的内存大小就记录在 allocated 上， 已经使用的就记录在 ob\_size

> 列表创建

通过`PyAPI_FUNC(PyObject *) PyList_New(Py_ssize_t size);` 方法来创建  
该方法需要指定 创建列表容量的大小  
创建列表代码如下

PyList_New(Py_ssize_t size)
    {
        PyListObject *op;
    #ifdef SHOW_ALLOC_COUNT
        static int initialized = 0;
        if (!initialized) {
            Py_AtExit(show_alloc);
            initialized = 1;
        }
    #endif
    
        if (size < 0) {
            PyErr_BadInternalCall();
            return NULL;
        }
        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_Calloc(size, sizeof(PyObject *));
            if (op->ob_item == NULL) {
                Py_DECREF(op);
                return PyErr_NoMemory();
            }
        }
        Py_SIZE(op) = size;
        op->allocated = size;
        _PyObject_GC_TRACK(op);
        return (PyObject *) op;
    }

新建列表主要做了:

*  1 参数检查 列表大小不能是 0
 *  2 检查是否有缓存可用
 *  3 内存检查 检查新建的列表大小不能超过 内存大小
 *  4 申请内存 新建列表
 *  5 为allocated 设置初始化的值

> 列表设置元素的实现

`lst = list() lst[0] = "hello world"`

当通过 PyObject\_GC\_New 创建列表之后，其实里面的元素都是null

![lst][]

假如 我们要给lst 第n元素赋值 其实就是通过 `PyList_SetItem(PyObject *op, Py_ssize_t i, PyObject *newitem)` 方法来实现的

代码如下:

PyList_SetItem(PyObject *op, Py_ssize_t i,
                   PyObject *newitem)
    {
        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;
        Py_XSETREF(*p, newitem);
        return 0;
    }

设置元素的过程大致的步骤是

*  1 参数类型检查
 *  2 索引 有效性检查 不可超出索引
 *  3 设置元素

> 列表 insert 插入元素的实现

插入元素 使用的是`ins1(PyListObject *self, Py_ssize_t where, PyObject *v)` 方法来实现  
源码 如下

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;
    }

其主要实现过程 如下

*  1 参数检查
 *  2 从新调整列表容量 通过 list\_resize 方法确定 是否需要申请内存
 *  3 确定插入点
 *  4 插入元素

可以看到列表插入时 都会将后面的位置的元素重新移动

![lst\_insert][lst]

> 列表的append 实现

通过 `PyList_Append(PyObject *op, PyObject *newitem)` 方法来实现

源码如下:

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

其主要是调用了 `app1(PyListObject *self, PyObject *v)` 来实现的

app1 方法主要做了以下工作

*  1 参数检查
 *  2 容量检查
 *  3 调用 `list_resize` 方法检查是否需要申请内存
 *  4 添加元素

> 列表转元组

列表转元组其实就是新建一个大小和列表一样大小的数组，并将该列表内的元素添加到元组中

源码如下:

PyObject *
    PyList_AsTuple(PyObject *v)
    {
        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;
    }

> 列表的反转 reverse

列表的反转是就地反转的，不会生成新的列表, 循环当前列表 使用了一个第三变量，然后将元素移位

static void
    reverse_slice(PyObject **lo, PyObject **hi)
    {
        assert(lo && hi);
    
        --hi;
        while (lo < hi) {
            PyObject *t = *lo;
            *lo = *hi;
            *hi = t;
            ++lo;
            --hi;
        }
    }

## 关于 列表的 extend 方法 看了源码才知道,只要是可迭代对象都可以放入extend(), 字典，元组，字符串都可以 ##

部分 源码定义 如下

if (PyList_CheckExact(iterable) || PyTuple_CheckExact(iterable) ||
                    (PyObject *)self == iterable) {
            PyObject **src, **dest;
            iterable = PySequence_Fast(iterable, "argument must be iterable");
            if (!iterable)
                return NULL;

还有很多的方法等着你们去探索和发现, 更多列表实现的源代码请看:  
[https://github.com/python/cpython/blob/master/Objects/listobject.c][https_github.com_python_cpython_blob_master_Objects_listobject.c]

[https_github.com_python_cpython_blob_master_Include_listobject.h]: https://github.com/python/cpython/blob/master/Include/listobject.h
[https_github.com_python_cpython_blob_master_Objects_listobject.c]: https://github.com/python/cpython/blob/master/Objects/listobject.c
[lst]: