Python 源码阅读：list
新媒体管家
点击上方“
Python开发
”，选择“置顶公众号”
关键时刻，第一时间送达！
源码位置 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
]
来源：
伯乐在线 - wklken
Python开发整理发布，转载请
联系作者获得授权
【点击成为安卓大神】
※python源码阅读笔记之GC
※Python 中的属性访问与描述符
※Python 源码阅读：类型
※Python 面向对象（进阶篇）
※让你的 Python 代码优雅又地道
TAG:Python开发 |