list对象定义:
typedef struct {
PyObject_VAR_HEAD
PyObject **ob_item;
Py_ssize_t allocated;
} PyListObject;
list对象是变长对象,所以有变长对象头.
ob_item数组为真正的存储容器,用来存储PyObject对象指针。
ob_size表示list长度。
allocated表示list已分配了多少存储空间。
list创建与销毁
list的创建分两步。
- 创建list对象本身。
- 为ob_item分配内存。
list的销毁也分两步。 - 回收ob_item的内存。
- 销毁list对象本身。
这样的对象创建和销毁方案是为对象池(free_lists)服务的。
在创建list阶段,Python会查看free_lists中是否有缓存对象。若有,则直接从free_lists取出。若没有,则从堆上分配list对象内存。
在销毁list阶段,若缓存list数(num_free_lists)小于最大可缓存数(MAXFREELISTS ),则将list对象缓存到free_lists备用。若超过了num_free_lists,则直接释放对象内存。
赋值操作
设置元素操作可以理解为list[i] = obj。
插入操作
插入元素操作:实质是函数ins1的包装。ins1函数的关键操作是,先通过list_resize(下面细说)调整list长度,然后确定插入点。由于Python list的索引可以为负数(即末尾元素索引为-1),所以索引值小于0时得加上长度得到C数组的索引。接着将插入点后的元素向后搬运,在插入点写入对象。从此可以看出list就是C里数组的概念。
list_resize函数:int list_resize(PyListObject *self, Py_ssize_t newsize)
如果allocated / 2 <= newsize <= allocated,则直接把ob_size设置成newsize。如果不在这个范围内,就按如下方案realloc内存:new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
不是很理解为什么采用这个方案,求指教。
删除元素
删除元素操作:实质是函数app1的包装。app1函数的关键操作是,先找到第一个对象的位置,然后通过list_ass_slice函数将删除点前后的两段合并。