Python 源码阅读：list

源码位置 Include/listobject.h | Objects/listobject.c

定义

typedef struct {

    PyObject_VAR_HEAD

 

    PyObject **ob_item;

 

    Py_ssize_t allocated;

} PyListObject;

说明

1. PyObject_VAR_HEAD

PyListObject是变长对象

 

2. PyObject **ob_item;

指向列表元素的指针数组, list[0] 即 ob_item[0]

 

3. Py_ssize_t allocated;

allocated列表分配的空间, ob_size为已使用的空间

allocated 总的申请到的内存数量

ob_size 实际使用内存数量

 

等式:

 

    0

结构

构造

只有一个方法

定义如下

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

 

    // 大小为负数, return

    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();

 

    // 计算需要的字节数(PyObject指针数组)

    nbytes = size * sizeof(PyObject *);

 

    // 如果缓冲池非空, 从缓冲池取

    if (numfree) {

        // 取缓冲池数组最后一个对象

        numfree—;

        op = free_list[numfree];

 

        // set refcnt=1

        _Py_NewReference((PyObject *)op);

#ifdef SHOW_ALLOC_COUNT

        count_reuse++;

#endif

    } else {

 

        // 否则, GC_New分配内存空间

        op = PyObject_GC_New(PyListObject, &PyList_Type);

 

        // 分配失败

        if (op == NULL)

            return NULL;

#ifdef SHOW_ALLOC_COUNT

        count_alloc++;

#endif

    }

 

    // 确定ob_item列表元素指针的值

    // 若大小

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

    }

 

    // ob_size = size

    Py_SIZE(op) = size;

    // allocated

    op->allocated = size;

 

    // gc用

    _PyObject_GC_TRACK(op);

    return (PyObject *) op;

}

简化步骤

1. 判断列表缓冲池是否为空, 是的话从缓冲池取(复用)

2. 否则, 从内存中分配空间

3. 然后初始化数据

结论

Py_SIZE(op) = size;

op->allocated = size;

第一次生成list, 其allocated = ob_size

list_resize

同时注意list_resize方法

extends方法, list_resize(self, m + n)

pop方法,  list_resize(self, Py_SIZE(self) – 1)

append方法, list_resize(self, n+1)

其定义

list_resize(PyListObject *self, Py_ssize_t newsize)

{

  ………..

 

  // 如果   allocated/2 <= newsize <= allocated

  // 直接修改ob_size

  if (allocated >= newsize && newsize >= (allocated >> 1)) {

      assert(self->ob_item != NULL || newsize == 0);

      Py_SIZE(self) = newsize;

      return 0;

  }

 

 

  //否则

 

  new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

  new_allocated += newsize;

 

  ………….

 

  Py_SIZE(self) = newsize;

  self->allocated = new_allocated;

 

}

即

if allocated/2 <= newsize <= allocated

 

    allocated 不变

    ob_size = newsize

 

else

 

    allocated =  newsize +   ((newsize >> 3) + (newsize < 9 ? 3 : 6))

    ob_size = newsize

回收和PyListObject对象缓冲池

看下缓冲池相关的定义

/* Empty list reuse scheme to save calls to malloc and free */

#ifndef PyList_MAXFREELIST

#define PyList_MAXFREELIST 80

#endif

 

// 80个

static PyListObject *free_list[PyList_MAXFREELIST];

 

static int numfree = 0;

我们先看下list_dealloc的定义

static void

list_dealloc(PyListObject *op)

{

    Py_ssize_t i;

    PyObject_GC_UnTrack(op);

    Py_TRASHCAN_SAFE_BEGIN(op)

 

    // 遍历ob_item, 释放所有类表内元素空间

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

    }

 

    // 如果free_list还没满, PyListObject加入到列表中

    if (numfree tp_free((PyObject *)op);

 

    Py_TRASHCAN_SAFE_END(op)

}

即

对一个列表对象PyListObject, 回收时, ob_item会被回收, 其每个元素指向的对象引用–1.

但是PyListObject对象本身, 如果缓冲池未满, 会被放入缓冲池, 复用

缓冲池结构

List的操作过程

插入

1. resize n+1

2. 确定插入点

3. 插入点后所有元素后移

4. 执行插入

示例

>>> a = [1, 2, 3]

>>> a.insert(0, 9)

>>> a

[9, 1, 2, 3]

append

1. resize n+1

2. 放入最后一个位置(ob_size)

示例

>>> a = [1, 2, 3]

>>> a.append(4)

>>> a

[1, 2, 3, 4]

extend

1. 计算两个list大小 m n

2. resize m+n(此时本身被复制)

3. 遍历长度为n的数组, 从ob_item+m的位置开始加入

示例

>>> m = [1, 2, 3]

>>> n = [4, 5]

>>> m.extend(n)

>>> m

[1, 2, 3, 4, 5]

删除

1. 找到要删除元素位置

2. 删除之, 后面元素前移

示例

>>> a = [1, 2, 3, 2]

>>> a.remove(2)

>>> a

[1, 3, 2]