还剩 tuple 和 dict就把几个基本类型写完了, 然后歇歇先找工作>_<

---

源码位置 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 <= ob_size <= allocated
    len(list) == ob_size
    ob_item == NULL implies ob_size == allocated == 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列表元素指针的值
    // 若大小<=0
    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 < PyList_MAXFREELIST && PyList_CheckExact(op))
        free_list[numfree++] = op;
    else
        // free_list已经满了, 则回收内存
        Py_TYPE(op)->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]

---

changelog

2014-08-10 first version