一、列表结构体
创建列表c语言底层的结构体
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;
c源码来自 listobject.c
二、创建列表
name_list = [ ]
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; //返回列表的指针
}
三、添加元素
list中插入一个元素时，扩容连续的内存地址（容量），在内存创建需要插入的内容p，将地址*p放入list的空间中，所以，pylistobject的ob_item是指针的指针
扩容的曲线一般就是0，4，8，16，24…
// 添加元素
static int
app1(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: 已存在元素个数+1
static int
list_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;
}
四、移除元素
list.pop()
删除最后一个元素只需要修改size，不需要清除数据，下次append可以直接覆盖这个位置
指定索引位置移除后，向前补位
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;
}
五、清空
list.clear()
static int
list_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;
}
六、销毁
del list
销毁列表对象的操作
将列表的引用计数-1
引用计数>0，还有应用的话不做操作
引用计数=0，没人使用
- 处理列表的元素，将所有引用计数-1（gc回收0计数）
- ob_item=0,ob_size=0,ob_allocated=0
- 将列表从双向链表移除，可以销毁
- 为了提高效率，python结束期在内部为free_list缓存80个list，存放无使用的list，再创建的时候直接从缓存中拿来初始化。如果已经存了80个，del 的时候直接在内存中销毁对象
static void
list_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)
}
就是说创建列表时，实际上不会直接开辟内存，而是先看看free_list
# 两次list的地址相同 >>> list1=[1,2,3] >>> id(list1) 69070216l >>> del list1 >>> list2=[0,0,0] >>> id(list2) 69303304l >>>
到此这篇关于python源码解析之list的文章就介绍到这了,更多相关python list内容请搜索www.887551.com以前的文章或继续浏览下面的相关文章希望大家以后多多支持www.887551.com！
黄山市民网：https://www.huangshanshimin.com/
