Python 源码阅读：list
（点击上方蓝字，快速关注我们）
来源：伯乐在线 - wklken
源码位置 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]
本系列
看完本文有收获？请转发分享给更多人
关注「Python开发者」，提升Python技能