自学教程：Python源码解析之List

lists = []list.append('name')list.append('age')list.append('grade')

typedef struct{	struct _object *_ob_next;	struct _object *_ob_prev; 	// python内部将对象放在链表进行内存管理	Py_ssize_t ob_refcnt;		// 引用计数器，就是多少变量用了它	PyObject **ob_item;			// 指针的指针，存列表的元素	Py_ssize_t ob_size;			// 已有元素个数	Py_ssize_t allocated;		// 列表容量，可容纳个数} PyListObject;

PyObject *PyList_New(Py_ssize_t size){    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;Py#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; //返回列表的指针}

// 添加元素static intapp1(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) == -1)        return -1;    // 将元素添加到ob_item，v    Py_INCREF(v);    PyList_SET_ITEM(self, n, v);    return 0;}

// 扩容机制 // newsize: 已存在元素个数+1static intlist_resize(PyListObject *self, Py_ssize_t newsize){    PyObject **items;    size_t new_allocated;    Py_ssize_t allocated = self->allocated; // 当前的容量    // 1,容量大于个数    // 2,个数大于容量的一半（容量足够且没有内存浪费）    if (allocated >= newsize && newsize >= (allocated >> 1)) {        assert(self->ob_item != NULL || newsize == 0);        Py_SIZE(self) = newsize;        return 0;    }    /*      * 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 <= (PY_SIZE_MAX / 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;}

static PyObject *listpop(PyListObject *self, PyObject *args){    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];    // 删除最后一个，仅改变size    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;}

static intlist_clear(PyListObject *a){    Py_ssize_t i;    PyObject **item = a->ob_item;    if (item != NULL) {        i = Py_SIZE(a);        // 各个元素设置为空        Py_SIZE(a) = 0;        a->ob_item = NULL;        a->allocated = 0;        // 引用计数器-1        while (--i >= 0) {            Py_XDECREF(item[i]);        }        PyMem_FREE(item);    }     return 0;}

static voidlist_dealloc(PyListObject *op){    Py_ssize_t i;    // 判断引用计数是否为0    PyObject_GC_UnTrack(op);    Py_TRASHCAN_SAFE_BEGIN(op)    if (op->ob_item != NULL) {        i = Py_SIZE(op);        while (--i >= 0) {            Py_XDECREF(op->ob_item[i]);        }        PyMem_FREE(op->ob_item);    }    // free_list没有80个的话缓存这个list    if (numfree < PyList_MAXFREELIST && PyList_CheckExact(op))        free_list[numfree++] = op;    else        Py_TYPE(op)->tp_free((PyObject *)op);    Py_TRASHCAN_SAFE_END(op)}

# 两次list的地址相同>>> list1=[1,2,3]>>> id(list1)69070216L>>> del list1>>> list2=[0,0,0]>>> id(list2)69303304L>>>