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 源碼閱讀：對象》
《Python 源碼閱讀：String》
《Python 源碼閱讀：int》
看完本文有收穫？請轉
發分享給更多人
關注「P
ython開發者」，提升Python技能
※讓你的 Python 代碼優雅又地道，15篇 Python 技術熱文
※Flask 應用中的 URL 處理
※Python 中的作用域規則和閉包簡析
※Python 源碼閱讀：int
※Python 源碼閱讀: String
TAG:Python開發者 |