說明
- python源碼版本：3.8.3
參考：
python源碼剖析
https://yq.aliyun.com/users/1709307684254463
int
在源碼實現(xiàn)中，python3之前用int和long兩種類型來表示數(shù)字，而python3開始則統(tǒng)一使用long來表示數(shù)字（盡管在使用python時，顯示的是int，實際上在底層是long類型）
int定義
struct _longobject {
// python變長對象頭
PyObject_VAR_HEAD
// digit定義：typedef uint32_t digit;
// ob_digit是一個單一元素，內(nèi)容為uint型，并且是可變大小的數(shù)組（單一元素的數(shù)組放在一個struct的尾端，則數(shù)組大小是可變的），存放的是具體的數(shù)值
digit ob_digit[1];
};
從int的定義看出存放int具體數(shù)值的數(shù)據(jù)類型實際上是一個數(shù)組，因此python中int的大小沒有限制，而數(shù)組里存放的數(shù)組都是無符號數(shù)字，那么正負(fù)數(shù)如何區(qū)分呢？實際上其將判斷正負(fù)數(shù)、零的標(biāo)識存放在了頭部PyObject_VAR_HEAD的ob_size中，而ob_digit中只存儲其絕對值數(shù)值，后面從int對象的創(chuàng)建邏輯當(dāng)中可以看到這些
創(chuàng)建int對象
int對象的創(chuàng)建方式會根據(jù)傳入的數(shù)值或者類型轉(zhuǎn)換等情況來決定，例如：小于C中l(wèi)ong類型大小的數(shù)值，一般基于PyLong_FromLong方法創(chuàng)建，而大于該數(shù)的則可能基于PyLong_FromString方法創(chuàng)建，這里簡單介紹下通過long方式創(chuàng)建的邏輯：
// 通過數(shù)值創(chuàng)建python中int對象方法，例如：a = 100
PyObject *
PyLong_FromLong(long ival)
{
PyLongObject *v;
// abs_ival中存放絕對值數(shù)值
unsigned long abs_ival;
unsigned long t; /* unsigned so >> doesn't propagate sign bit */
int ndigits = 0;
// 數(shù)值標(biāo)記：正數(shù)(1)，負(fù)數(shù)(-1)，零(0)
int sign;
// 檢查如果是小整數(shù)，則直接返回緩沖池的小整數(shù)對象，后面會介紹，在python3.8中緩沖池范圍是[-5, 257)
CHECK_SMALL_INT(ival);
// 將數(shù)值和正負(fù)數(shù)的標(biāo)識分開
if (ival < 0) {
abs_ival = 0U-(unsigned long)ival;
sign = -1;
}
else {
abs_ival = (unsigned long)ival;
sign = ival == 0 ? 0 : 1;
}
// 對于小于PyLong_SHIFT位的數(shù)進入快速通道，PyLong_SHIFT的值基于當(dāng)前系統(tǒng)中定義指針的大小確定
// （指針在32位中size為4，64位中為8，因此例如32位平臺下32768以下的數(shù)字都可以進入該通道）
if (!(abs_ival >> PyLong_SHIFT)) {
// 創(chuàng)建一個數(shù)值指向區(qū)域size為1*sizeof(digit)的long對象
v = _PyLong_New(1);
if (v) {
// 可以看出ob_size用來標(biāo)識是正數(shù)、負(fù)數(shù)還是0
Py_SIZE(v) = sign;
// ob_digit[0]里存入的是無符號的數(shù)值
v->ob_digit[0] = Py_SAFE_DOWNCAST(
abs_ival, unsigned long, digit);
}
return (PyObject*)v;
}
// 對于指針大小為4字節(jié)的情況（例如32位系統(tǒng)），申請對象空間的方式
#if PyLong_SHIFT==15
/* 2 digits */
if (!(abs_ival >> 2*PyLong_SHIFT)) {
v = _PyLong_New(2);
if (v) {
Py_SIZE(v) = 2*sign;
v->ob_digit[0] = Py_SAFE_DOWNCAST(
abs_ival & PyLong_MASK, unsigned long, digit);
v->ob_digit[1] = Py_SAFE_DOWNCAST(
abs_ival >> PyLong_SHIFT, unsigned long, digit);
}
return (PyObject*)v;
}
#endif
// 對于較大的數(shù)值，需要獲取位數(shù)，然后申請對應(yīng)大小的long對象
t = abs_ival;
// 獲取數(shù)值所需的位數(shù)
while (t) {
++ndigits;
t >>= PyLong_SHIFT;
}
// 后面的邏輯跟之前的創(chuàng)建方式基本一樣
v = _PyLong_New(ndigits);
if (v != NULL) {
digit *p = v->ob_digit;
Py_SIZE(v) = ndigits*sign;
t = abs_ival;
while (t) {
*p++ = Py_SAFE_DOWNCAST(
t & PyLong_MASK, unsigned long, digit);
t >>= PyLong_SHIFT;
}
}
return (PyObject *)v;
}
小整數(shù)緩沖池
在python中對于int數(shù)據(jù)，其定義了緩沖池，對常用范圍的小整數(shù)都進行了緩存處理，從而提高數(shù)值使用的效率，緩沖池部分源碼如下：
// 定義小整數(shù)的緩沖池
// #define NSMALLPOSINTS 257
// #define NSMALLNEGINTS 5
static PyLongObject small_ints[NSMALLNEGINTS + NSMALLPOSINTS];
// 獲取小整數(shù)對象
static PyObject *
get_small_int(sdigit ival)
{
PyObject *v;
assert(-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS);
// 在符合小整數(shù)的范圍內(nèi)，返回直接緩沖池中的對象
v = (PyObject *)&small_ints[ival + NSMALLNEGINTS];
Py_INCREF(v);
...
return v;
}
// 如果是小整數(shù)，則直接從小整數(shù)緩沖池當(dāng)中獲取對象
#define CHECK_SMALL_INT(ival) \
do if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) { \
return get_small_int((sdigit)ival); \
} while(0)
可以看出在[-5, 257)之間是存在緩存的，證明如下：
>>> id(-5)
1665722640
>>> id(-5)
1665722640
# -5的id都一樣
>>> id(-6)
2331088351536
>>> id(-6)
2331088351312
# -6的id發(fā)生了變化
>>> id(256)
1665730992
>>> id(256)
1665730992
# 256的id都一樣
>>> id(257)
2331088351312
>>> id(257)
2331088351536
# 257的id發(fā)生了變化
因此對于小整數(shù)使用較多的場景，我們可以通過修改小整數(shù)的緩沖池范圍來進行優(yōu)化
加法邏輯
由于python中的int屬于不可變類型數(shù)據(jù)，因此在進行加法運算時，會創(chuàng)建一個新的int對象來存儲計算的結(jié)果值，并且由于int中數(shù)據(jù)的存儲是基于數(shù)據(jù)，因此在計算時實際上模擬了從低位開始逐位相加運算的方式來進行運算，而通過這種存儲和計算方式，一般也就不用擔(dān)心大數(shù)計算時的溢出等問題了，源碼邏輯如下：
// 加法運算邏輯
static PyLongObject *
x_add(PyLongObject *a, PyLongObject *b)
{
Py_ssize_t size_a = Py_ABS(Py_SIZE(a)), size_b = Py_ABS(Py_SIZE(b));
PyLongObject *z;
Py_ssize_t i;
digit carry = 0;
// 如果a比b小，就交換兩個數(shù)，以保證a是大的那個數(shù)
if (size_a < size_b) {
{ PyLongObject *temp = a; a = b; b = temp; }
{ Py_ssize_t size_temp = size_a;
size_a = size_b;
size_b = size_temp; }
}
// 以最大的那個值的size+1為新創(chuàng)建的long對象大小
z = _PyLong_New(size_a+1);
if (z == NULL)
return NULL;
// 低位開始逐位相加（兩個數(shù)中小的那個數(shù)的最高位及以下位相加）
for (i = 0; i < size_b; ++i) {
carry += a->ob_digit[i] + b->ob_digit[i];
z->ob_digit[i] = carry & PyLong_MASK;
carry >>= PyLong_SHIFT;
}
// 高位只剩下a的值，直接將a的值填充
for (; i < size_a; ++i) {
carry += a->ob_digit[i];
z->ob_digit[i] = carry & PyLong_MASK;
carry >>= PyLong_SHIFT;
}
// 新創(chuàng)建的對象保存對應(yīng)結(jié)果
z->ob_digit[i] = carry;
// long_normalize將數(shù)值前面的0刪除（并沒有真正刪除釋放，而是改變其允許指向數(shù)值的范圍大?。? return long_normalize(z);
}
list
結(jié)構(gòu)定義
typedef struct {
// python變長對象的頭部分，其中l(wèi)ist的真實數(shù)據(jù)的長度就存在頭部的ob_size里
PyObject_VAR_HEAD
// 存放所有數(shù)據(jù)的數(shù)組，每個數(shù)據(jù)都是PyObject類型
PyObject **ob_item;
// list申請的內(nèi)存大小
Py_ssize_t allocated;
} PyListObject;
緩沖池
// #define PyList_MAXFREELIST 80
// list緩沖池空間定義，可以看出大小是80
static PyListObject *free_list[PyList_MAXFREELIST];
// 緩沖池中已使用的數(shù)量
static int numfree = 0;
當(dāng)創(chuàng)建了一個list對象后，將會存入緩沖區(qū)，如果這個list對象沒有被使用，將會留在緩沖區(qū)，等到下一次創(chuàng)建list對象時，如果緩沖區(qū)里存在list對象，則直接返回該對象
創(chuàng)建list對象
例如對于a = [1,2,3]的字節(jié)碼指令如下：
0 LOAD_CONST 1 (1)
2 LOAD_CONST 2 (2)
4 LOAD_CONST 3 (3)
6 BUILD_LIST 3
8 STORE_FAST 0 (a)
前三個指令依次將1、2、3壓入棧中，然后通過BUILD_LIST創(chuàng)建一個list并從棧中取出的數(shù)據(jù)存入，其中build_list的操作源碼如下：
// BUILD_LIST指令操作
case TARGET(BUILD_LIST): {
// 創(chuàng)建一個空的list對象（里面沒有存放數(shù)據(jù)，但是已經(jīng)分配了對應(yīng)大小的內(nèi)存，oparg就是list需要的長度）
PyObject *list = PyList_New(oparg);
if (list == NULL)
goto error;
while (--oparg >= 0) {
// 依次從棧中取出list需要存入的元素（對應(yīng)上面的指令就是依次取出3、2、1），然后存入到list的指令位置當(dāng)中
PyObject *item = POP();
PyList_SET_ITEM(list, oparg, item);
}
PUSH(list);
DISPATCH();
}
其中通過PyList_New函數(shù)創(chuàng)建一個list對象，源碼如下：
PyObject *
PyList_New(Py_ssize_t size)
{
PyListObject *op;
if (size < 0) {
PyErr_BadInternalCall();
return NULL;
}
// 如果緩沖池里存在list對象，則取出
if (numfree) {
// 緩沖池list對象數(shù)量-1
numfree--;
// 獲取緩沖池的對應(yīng)list對象
op = free_list[numfree];
_Py_NewReference((PyObject *)op);
} else {
// 否則創(chuàng)建一個list空間大小的對象
op = PyObject_GC_New(PyListObject, &PyList_Type);
if (op == NULL)
return NULL;
}
// 如果list里沒有內(nèi)容，則ob_item（實際存放list內(nèi)容的地方）設(shè)置為空
if (size <= 0)
op->ob_item = NULL;
// list中存在內(nèi)容，則申請對應(yīng)大小的空間給ob_item
else {
op->ob_item = (PyObject **) PyMem_Calloc(size, sizeof(PyObject *));
if (op->ob_item == NULL) {
Py_DECREF(op);
return PyErr_NoMemory();
}
}
// 設(shè)置list數(shù)據(jù)長度
Py_SIZE(op) = size;
// 設(shè)置list容量大小，可以看出list初始化時的分配的容量大小跟數(shù)據(jù)長度是一樣的
op->allocated = size;
_PyObject_GC_TRACK(op);
return (PyObject *) op;
}
我們可以進行測試：
>>> id([1,2,3])
7002632
>>> id([1,2,3,4])
7002632
# 可以看出都是復(fù)用緩沖池的list對象
>>> id([1,2,3,4,5])
7002632
>>> a = [1,2,3]
>>> id(a)
7002632
# 將對象賦值指向后
>>> id([1,2,3])
8095848
# 可以看出創(chuàng)建了一個新的list對象
append邏輯
static int
app1(PyListObject *self, PyObject *v)
{
// 獲取當(dāng)前l(fā)ist尺寸
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;
}
// 更新list尺寸，使list能夠存入n+1數(shù)量的數(shù)據(jù)，如果失敗則返回-1
if (list_resize(self, n+1) < 0)
return -1;
Py_INCREF(v);
// 設(shè)置第n個位置的值為v
PyList_SET_ITEM(self, n, v);
return 0;
}
int
PyList_Append(PyObject *op, PyObject *newitem)
{
if (PyList_Check(op) && (newitem != NULL))
return app1((PyListObject *)op, newitem);
PyErr_BadInternalCall();
return -1;
}
extend主邏輯
...
// 插入數(shù)據(jù)是否可迭代判斷
iterable = PySequence_Fast(iterable, "argument must be iterable");
if (!iterable)
return NULL;
// 計算要插入的數(shù)據(jù)長度
n = PySequence_Fast_GET_SIZE(iterable);
if (n == 0) {
/* short circuit when iterable is empty */
Py_DECREF(iterable);
Py_RETURN_NONE;
}
// 獲取list當(dāng)前長度
m = Py_SIZE(self);
/* It should not be possible to allocate a list large enough to cause
an overflow on any relevant platform */
assert(m < PY_SSIZE_T_MAX - n);
// 當(dāng)前l(fā)ist長度+插入長度判斷，只申請一次
if (list_resize(self, m + n) < 0) {
Py_DECREF(iterable);
return NULL;
}
/* note that we may still have self == iterable here for the
* situation a.extend(a), but the following code works
* in that case too. Just make sure to resize self
* before calling PySequence_Fast_ITEMS.
*/
/* populate the end of self with iterable's items */
src = PySequence_Fast_ITEMS(iterable);
dest = self->ob_item + m;
// 遍歷設(shè)置值
for (i = 0; i < n; i++) {
PyObject *o = src[i];
Py_INCREF(o);
dest[i] = o;
}
Py_DECREF(iterable);
Py_RETURN_NONE;
...
insert邏輯
static int
ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
{
Py_ssize_t i, n = Py_SIZE(self);
PyObject **items;
if (v == NULL) {
PyErr_BadInternalCall();
return -1;
}
if (n == PY_SSIZE_T_MAX) {
PyErr_SetString(PyExc_OverflowError,
"cannot add more objects to list");
return -1;
}
// 尺寸判斷
if (list_resize(self, n+1) < 0)
return -1;
if (where < 0) {
where += n;
// 負(fù)值索引如果加上長度還<0，則置為0
if (where < 0)
where = 0;
}
// 索引大于最大長度，則設(shè)置為往后面添加
if (where > n)
where = n;
items = self->ob_item;
// insert位置后面的數(shù)據(jù)都后挪一位
for (i = n; --i >= where; )
items[i+1] = items[i];
Py_INCREF(v);
// 插入數(shù)據(jù)
items[where] = v;
return 0;
}
append/extend/insert效率問題
通過前面三種添加方式的源碼實現(xiàn)可以看出：insert的邏輯中，需要對插入部分后面的數(shù)據(jù)進行后移操作，以及對插入位置進行一些范圍處理，所以效率上會比append差一些；在append里每添加一條數(shù)據(jù)都需要進行尺寸判斷，不夠則重新申請，而extend則是一口氣算出最終需要的尺寸，只需要申請一次即可，所以效率上append會比extend差一些，特別是在添加的數(shù)據(jù)量越大時越明顯，所以在數(shù)據(jù)量大的情況下三者的效率應(yīng)該是：insert<append<extend（如果數(shù)據(jù)特別少，那么因為append邏輯最簡單，所以效率應(yīng)該是extend<insert<append），如下代碼可以驗證：
from time import time
l = 10000000
data = [i for i in range(l)]
def count_time(func):
def wrapper():
s = time()
func()
print(func.__name__, ":", time() - s)
wrapper()
@count_time
def insert():
li = []
for i in range(l):
li.insert(i, data[i])
@count_time
def append():
li = []
for i in range(l):
li.append(data[i])
@count_time
def extend():
li = []
li.extend(data)
# insert : 2.52603816986084
# append : 1.7159614562988281
# extend : 0.21300077438354492
而如果我們用Python去實現(xiàn)可變序列（MutableSequence）相關(guān)的類型時，由于Python無法進行像C那樣底層的操作，所以extend的實現(xiàn)實際上就是遍歷append而已，此時append和extend的效率就沒有多大的差別了，源碼如下：
def extend(self, values):
'S.extend(iterable) -- extend sequence by appending elements from the iterable'
for v in values:
self.append(v)
list尺寸更新邏輯
static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
PyObject **items;
size_t new_allocated, num_allocated_bytes;
Py_ssize_t allocated = self->allocated;
// 如果數(shù)據(jù)量在總大小的一半以上，且小于總大小，則無需重新計算尺寸
if (allocated >= newsize && newsize >= (allocated >> 1)) {
assert(self->ob_item != NULL || newsize == 0);
Py_SIZE(self) = newsize;
return 0;
}
// 新內(nèi)存大小分配規(guī)則
new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);
// 最大長度限制
if (new_allocated > (size_t)PY_SSIZE_T_MAX / sizeof(PyObject *)) {
PyErr_NoMemory();
return -1;
}
if (newsize == 0)
new_allocated = 0;
// 內(nèi)存大小計算
num_allocated_bytes = new_allocated * sizeof(PyObject *);
// 內(nèi)存申請
items = (PyObject **)PyMem_Realloc(self->ob_item, num_allocated_bytes);
if (items == NULL) {
PyErr_NoMemory();
return -1;
}
// list存放數(shù)據(jù)的地方
self->ob_item = items;
// list中存放的數(shù)據(jù)長度
Py_SIZE(self) = newsize;
// list內(nèi)存分配的長度
self->allocated = new_allocated;
return 0;
}
remove邏輯
static PyObject *
list_remove(PyListObject *self, PyObject *value)
/*[clinic end generated code: output=f087e1951a5e30d1 input=2dc2ba5bb2fb1f82]*/
{
Py_ssize_t i;
// 遍歷所有值，找到第一個要刪除的，將其刪除，然后返回
for (i = 0; i < Py_SIZE(self); i++) {
PyObject *obj = self->ob_item[i];
// 引用+1
Py_INCREF(obj);
// PyObject_RichCompareBool會根據(jù)第三個參數(shù)來進行比較，這里比較的是是否相等
// 相等則返回1，不相等返回0，還有相關(guān)判斷會返回-1
int cmp = PyObject_RichCompareBool(obj, value, Py_EQ);
// 操作完畢，引用-1
Py_DECREF(obj);
if (cmp > 0) {
// 刪除第i個操作，該方法邏輯較多，其中刪除的邏輯可以參考動態(tài)數(shù)組的刪除方式
if (list_ass_slice(self, i, i+1,
(PyObject *)NULL) == 0)
Py_RETURN_NONE;
// Py_RETURN_NONE源碼：
// #define Py_RETURN_NONE return Py_INCREF(Py_None), Py_None
// 將None引用+1，并返回None
return NULL;
}
// cmp小于0屬于其他情況
else if (cmp < 0)
return NULL;
}
// 遍歷完都沒有找到要刪除的，則會拋出異常
PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
return NULL;
}
包含邏輯(x in list)
static int
list_contains(PyListObject *a, PyObject *el)
{
PyObject *item;
Py_ssize_t i;
int cmp;
// 遍歷取出內(nèi)容進行比較，當(dāng)找到時停止遍歷
for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i) {
item = PyList_GET_ITEM(a, i);
Py_INCREF(item);
cmp = PyObject_RichCompareBool(el, item, Py_EQ);
Py_DECREF(item);
}
return cmp;
}
索引邏輯(index)
static PyObject *
list_index_impl(PyListObject *self, PyObject *value, Py_ssize_t start,
Py_ssize_t stop)
/*[clinic end generated code: output=ec51b88787e4e481 input=40ec5826303a0eb1]*/
{
Py_ssize_t i;
// 負(fù)值索引（如：list[-1]）的實質(zhì)就是`list[len(list) + (-1)]`
if (start < 0) {
start += Py_SIZE(self);
if (start < 0)
start = 0;
}
// stop會自動調(diào)整到>=0
if (stop < 0) {
stop += Py_SIZE(self);
if (stop < 0)
stop = 0;
}
// 遍歷查找
for (i = start; i < stop && i < Py_SIZE(self); i++) {
PyObject *obj = self->ob_item[i];
Py_INCREF(obj);
int cmp = PyObject_RichCompareBool(obj, value, Py_EQ);
Py_DECREF(obj);
// 找到了則將索引轉(zhuǎn)成long類型返回
if (cmp > 0)
return PyLong_FromSsize_t(i);
else if (cmp < 0)
return NULL;
}
PyErr_Format(PyExc_ValueError, "%R is not in list", value);
return NULL;
}
修改邏輯(li[i] = x)
int
PyList_SetItem(PyObject *op, Py_ssize_t i,
PyObject *newitem)
{
PyObject **p;
// list類型檢查
if (!PyList_Check(op)) {
Py_XDECREF(newitem);
PyErr_BadInternalCall();
return -1;
}
// 范圍檢查
if (!valid_index(i, Py_SIZE(op))) {
Py_XDECREF(newitem);
PyErr_SetString(PyExc_IndexError,
"list assignment index out of range");
return -1;
}
// 找到對應(yīng)位置進行修改操作
p = ((PyListObject *)op) -> ob_item + i;
Py_XSETREF(*p, newitem);
// Py_XSETREF源碼：
// #define Py_XSETREF(op, op2) \
// do { \
// PyObject *_py_tmp = _PyObject_CAST(op); \
// (op) = (op2); \
// Py_XDECREF(_py_tmp); \
// } while (0)
// 解釋：將舊的內(nèi)容替換成新的內(nèi)容，并將舊的內(nèi)容引用計數(shù)-1
return 0;
}
dict
python中大部分的運行機制當(dāng)中都采用了dict來進行數(shù)據(jù)的管理，所以為了最高效的查詢性能，dict底層選擇了基于哈希表實現(xiàn)。其中在python3.6之前，dict的實現(xiàn)里將數(shù)據(jù)存在了hash表里，所以之前的dict是無序且十分消耗內(nèi)存的，而在python3.6以后，官方對dict進行了很大地改進（主要是將數(shù)據(jù)和hash部分分離），包括從無序變?yōu)橛行?，在一定程度上減少了內(nèi)存的消耗，以及部分操作性能的提升等，具體參考：https://zhuanlan.zhihu.com/p/73426505
dict定義
在python3.6之前，字典的數(shù)組中的對應(yīng)位置都存放著完整的鍵值對信息-(hash, key, value)，這種字典類型被稱為combined型，后來為了提升性能，將完整的鍵值對信息存放到另一個數(shù)組entries當(dāng)中，而對于原來字典的數(shù)組里，對應(yīng)位置只存放了鍵值對在entries中的索引，這種字典類型被稱為split型，這里主要對split型字典進行介紹，官方提供的內(nèi)存布局如下：
+---------------+
| dk_refcnt | key集合的引用數(shù)
| dk_size | key集合的大小
| dk_lookup | 字典查詢方法
| dk_usable | 字典中key集合可用大小
| dk_nentries | 字典對應(yīng)的entries集合的內(nèi)容數(shù)量
+---------------+
| dk_indices | key集合（哈希表部分），存放所有key在entries中對應(yīng)的索引
| |
+---------------+
| dk_entries | 存放所有的鍵值對數(shù)據(jù)信息
| |
+---------------+
基于上面的布局，源碼中對于dict的結(jié)構(gòu)定義如下：
// dict總體結(jié)構(gòu)
typedef struct {
// 通用對象頭
PyObject_HEAD
// 鍵值對的數(shù)量
Py_ssize_t ma_used;
// 版本標(biāo)記
uint64_t ma_version_tag;
// key集合，哈希表就存在這里面
PyDictKeysObject *ma_keys;
// entries集合，split中，所有的鍵值對都存在ma_values里，而combined型的ma_values將會是null
PyObject **ma_values;
} PyDictObject;
// key集合結(jié)構(gòu)
typedef struct _dictkeysobject PyDictKeysObject;
struct _dictkeysobject {
// key集合的引用數(shù)
Py_ssize_t dk_refcnt;
// 哈希表索引數(shù)組的大小
Py_ssize_t dk_size;
// 字典查詢方法
dict_lookup_func dk_lookup;
// 字典中key集合可用大小
Py_ssize_t dk_usable;
// entries中鍵值對的數(shù)量
Py_ssize_t dk_nentries;
// 每個鍵對應(yīng)存放數(shù)據(jù)位置的索引
char dk_indices[];
};
// entries集合中單個元素的結(jié)構(gòu)
typedef struct {
Py_hash_t me_hash;
PyObject *me_key;
// 在split型中，value存放在ma_values中，所以只有combined型的時候，me_value才存放value
PyObject *me_value;
} PyDictKeyEntry;
dict的幾種狀態(tài)
在python3.6之前，dict中的鍵值對主要有以下三種狀態(tài)：
- Unused：此時key為null，即還未使用當(dāng)前位置，此時索引值被設(shè)為
-1 - Active：如果當(dāng)前位置設(shè)置了鍵值對，那么就會進入該狀態(tài)，表示正在使用中，此時索引值就是所在位置的索引
- Dummy：當(dāng)被使用的key刪除時，將會進入該狀態(tài)，用于避免探測鏈斷開而導(dǎo)致索引出錯的問題，此時索引值為
-2
在python3.6以后，由于索引和鍵值對分開存儲，于是便取消了Dummy態(tài)，而使用Pending態(tài)來進行代替：
- Pending：同樣是刪除鍵值對以后進入的狀態(tài)，此時索引不變，但是對應(yīng)索引存儲的value將會被刪除，從而等待新的對應(yīng)索引的key插入
幾種狀態(tài)的源碼定義如下：
#define DKIX_EMPTY (-1)
#define DKIX_DUMMY (-2)
#define DKIX_ERROR (-3)
dict基本配置
// 哈希表的起始尺寸為8
#define PyDict_MINSIZE 8
// 哈希表相對于索引數(shù)量的尺寸
#define ESTIMATE_SIZE(n) (((n)*3+1) >> 1)
// 當(dāng)需要更新dict尺寸時，尺寸大小為索引數(shù)*3
#define GROWTH_RATE(d) ((d)->ma_used*3)
dict緩沖池
// dict緩沖池大小，可以看出尺寸和list緩沖池一樣是80
#ifndef PyDict_MAXFREELIST
#define PyDict_MAXFREELIST 80
#endif
// 可以發(fā)現(xiàn)對dict對象和dict中的key集合對象都有進行緩沖池操作
static PyDictObject *free_list[PyDict_MAXFREELIST];
static int numfree = 0;
static PyDictKeysObject *keys_free_list[PyDict_MAXFREELIST];
static int numfreekeys = 0;
創(chuàng)建dict
// 空字典的key集合
static PyDictKeysObject empty_keys_struct = {
1, /* dk_refcnt */
1, /* dk_size */
lookdict_split, /* dk_lookup */
0, /* dk_usable (immutable) */
0, /* dk_nentries */
// 可以看到初始化的哈希表里都是Unused狀態(tài)
// #define DKIX_EMPTY (-1)
{DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY,
DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY}, /* dk_indices */
};
// 空的entries
static PyObject *empty_values[1] = { NULL };
// 空的key集合
#define Py_EMPTY_KEYS &empty_keys_struct
// dict對象創(chuàng)建入口
PyObject *
PyDict_New(void)
{
// 引用+1
dictkeys_incref(Py_EMPTY_KEYS);
// 通過空集合和空entries創(chuàng)建一個空字典
return new_dict(Py_EMPTY_KEYS, empty_values);
}
// 創(chuàng)建一個dict對象
static PyObject *
new_dict(PyDictKeysObject *keys, PyObject **values)
{
PyDictObject *mp;
assert(keys != NULL);
// 緩存池操作，和list的差不多
if (numfree) {
mp = free_list[--numfree];
assert (mp != NULL);
assert (Py_TYPE(mp) == &PyDict_Type);
_Py_NewReference((PyObject *)mp);
}
else {
mp = PyObject_GC_New(PyDictObject, &PyDict_Type);
if (mp == NULL) {
dictkeys_decref(keys);
if (values != empty_values) {
free_values(values);
}
return NULL;
}
}
// 初始化操作，設(shè)置keys、values等內(nèi)容，注意這里的keys和values的內(nèi)容還都是空的
mp->ma_keys = keys;
mp->ma_values = values;
mp->ma_used = 0;
mp->ma_version_tag = DICT_NEXT_VERSION();
ASSERT_CONSISTENT(mp);
return (PyObject *)mp;
}
dict添加
// 添加/設(shè)置邏輯
int
PyDict_SetItem(PyObject *op, PyObject *key, PyObject *value)
{
PyDictObject *mp;
Py_hash_t hash;
if (!PyDict_Check(op)) {
PyErr_BadInternalCall();
return -1;
}
assert(key);
assert(value);
mp = (PyDictObject *)op;
// 獲取對象的哈希值，如果不是可哈希的，則無法執(zhí)行setitem操作
if (!PyUnicode_CheckExact(key) ||
(hash = ((PyASCIIObject *) key)->hash) == -1)
{
hash = PyObject_Hash(key);
if (hash == -1)
return -1;
}
// 如果哈希表是一個空表，則直接往空字典插入數(shù)據(jù)
if (mp->ma_keys == Py_EMPTY_KEYS) {
return insert_to_emptydict(mp, key, hash, value);
}
// 添加或修改操作函數(shù)
return insertdict(mp, key, hash, value);
}
// dict添加和更新的主邏輯
static int
insertdict(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject *value)
{
PyObject *old_value;
PyDictKeyEntry *ep;
Py_INCREF(key);
Py_INCREF(value);
if (mp->ma_values != NULL && !PyUnicode_CheckExact(key)) {
if (insertion_resize(mp) < 0)
goto Fail;
}
// 尋找對應(yīng)key的索引
Py_ssize_t ix = mp->ma_keys->dk_lookup(mp, key, hash, &old_value);
// 異常情況處理
if (ix == DKIX_ERROR)
goto Fail;
assert(PyUnicode_CheckExact(key) || mp->ma_keys->dk_lookup == lookdict);
MAINTAIN_TRACKING(mp, key, value);
if (_PyDict_HasSplitTable(mp) &&
((ix >= 0 && old_value == NULL && mp->ma_used != ix) ||
(ix == DKIX_EMPTY && mp->ma_used != mp->ma_keys->dk_nentries))) {
if (insertion_resize(mp) < 0)
goto Fail;
ix = DKIX_EMPTY;
}
// 如果對應(yīng)的key的映射為空，則代表添加數(shù)據(jù)
if (ix == DKIX_EMPTY) {
assert(old_value == NULL);
if (mp->ma_keys->dk_usable <= 0) {
if (insertion_resize(mp) < 0)
goto Fail;
}
// 尋找哈希表中當(dāng)前key的插入位置
Py_ssize_t hashpos = find_empty_slot(mp->ma_keys, hash);
// ep指向entries的最后一位（索引為dk_nentries處）
ep = &DK_ENTRIES(mp->ma_keys)[mp->ma_keys->dk_nentries];
// 設(shè)置indices中對應(yīng)entries的索引，可以看到設(shè)置的entries索引就是entries的數(shù)量，因為鍵值對每次都是往entries的最后一位添加的
dictkeys_set_index(mp->ma_keys, hashpos, mp->ma_keys->dk_nentries);
// 設(shè)置新加入entries的鍵值對數(shù)據(jù)
ep->me_key = key;
ep->me_hash = hash;
if (mp->ma_values) {
assert (mp->ma_values[mp->ma_keys->dk_nentries] == NULL);
mp->ma_values[mp->ma_keys->dk_nentries] = value;
}
else {
ep->me_value = value;
}
// 添加成功操作
mp->ma_used++;
mp->ma_version_tag = DICT_NEXT_VERSION();
mp->ma_keys->dk_usable--;
mp->ma_keys->dk_nentries++;
assert(mp->ma_keys->dk_usable >= 0);
ASSERT_CONSISTENT(mp);
return 0;
}
// 如果不是添加操作，并且指定entries的value和當(dāng)前傳入的value不同，則需要更新value
if (old_value != value) {
// split型表的操作
if (_PyDict_HasSplitTable(mp)) {
// 直接更新entries中對應(yīng)索引的value
mp->ma_values[ix] = value;
// 當(dāng)前位置屬于pending狀態(tài)（已刪除狀態(tài)），則說明之前沒有使用，現(xiàn)在使用了，所以使用數(shù)+1
if (old_value == NULL) {
assert(ix == mp->ma_used);
mp->ma_used++;
}
}
// combined型表的操作
else {
assert(old_value != NULL);
// 由于key、value都是存在哈希表中，直接修改哈希表對應(yīng)位置的value
DK_ENTRIES(mp->ma_keys)[ix].me_value = value;
}
mp->ma_version_tag = DICT_NEXT_VERSION();
}
Py_XDECREF(old_value);
ASSERT_CONSISTENT(mp);
Py_DECREF(key);
return 0;
Fail:
Py_DECREF(value);
Py_DECREF(key);
return -1;
}
// 查找hash值在哈希表中的映射
static Py_ssize_t
find_empty_slot(PyDictKeysObject *keys, Py_hash_t hash)
{
assert(keys != NULL);
const size_t mask = DK_MASK(keys);
size_t i = hash & mask;
// 獲取哈希表索引
Py_ssize_t ix = dictkeys_get_index(keys, i);
// 哈希沖突處理
for (size_t perturb = hash; ix >= 0;) {
perturb >>= PERTURB_SHIFT;
i = (i*5 + perturb + 1) & mask;
ix = dictkeys_get_index(keys, i);
}
return i;
}
dict查詢
源碼邏輯如下：
// 查詢函數(shù)主邏輯
static Py_ssize_t _Py_HOT_FUNCTION
lookdict_unicode_nodummy(PyDictObject *mp, PyObject *key,
Py_hash_t hash, PyObject **value_addr)
{
assert(mp->ma_values == NULL);
// key不為字符串時，直接調(diào)用lookdict函數(shù)查詢
if (!PyUnicode_CheckExact(key)) {
mp->ma_keys->dk_lookup = lookdict;
return lookdict(mp, key, hash, value_addr);
}
// 字符串的索引情況，邏輯上基本和lookdict函數(shù)相同（分析在下面），但是簡化了一些操作
PyDictKeyEntry *ep0 = DK_ENTRIES(mp->ma_keys);
size_t mask = DK_MASK(mp->ma_keys);
size_t perturb = (size_t)hash;
size_t i = (size_t)hash & mask;
for (;;) {
Py_ssize_t ix = dictkeys_get_index(mp->ma_keys, i);
assert (ix != DKIX_DUMMY);
if (ix == DKIX_EMPTY) {
*value_addr = NULL;
return DKIX_EMPTY;
}
PyDictKeyEntry *ep = &ep0[ix];
assert(ep->me_key != NULL);
assert(PyUnicode_CheckExact(ep->me_key));
if (ep->me_key == key ||
(ep->me_hash == hash && unicode_eq(ep->me_key, key))) {
*value_addr = ep->me_value;
return ix;
}
perturb >>= PERTURB_SHIFT;
i = mask & (i*5 + perturb + 1);
}
Py_UNREACHABLE();
}
// 字典非字符串查詢的邏輯實現(xiàn)
static Py_ssize_t _Py_HOT_FUNCTION
lookdict(PyDictObject *mp, PyObject *key,
Py_hash_t hash, PyObject **value_addr)
{
size_t i, mask, perturb;
PyDictKeysObject *dk;
PyDictKeyEntry *ep0;
top:
// 字典對應(yīng)的所有key
dk = mp->ma_keys;
// 字典對應(yīng)的所有結(jié)果
ep0 = DK_ENTRIES(dk);
// 防止哈希越界的mask（類似對哈希取余作用），DK_MASK定義如下：
// #define DK_MASK(dk) (((dk)->dk_size)-1)
mask = DK_MASK(dk);
// 對應(yīng)的哈希值
perturb = hash;
// 哈希映射到字典的位置
i = (size_t)hash & mask;
for (;;) {
// 獲取映射位置存放的索引（即在entries中的索引）
Py_ssize_t ix = dictkeys_get_index(dk, i);
// 索引位置存儲索引值不存在的情況
if (ix == DKIX_EMPTY) {
// 設(shè)置返回的value為空
*value_addr = NULL;
return ix;
}
// 索引位置對應(yīng)的entry索引存在
if (ix >= 0) {
// 到entry集中取出對應(yīng)位置的entry結(jié)果
PyDictKeyEntry *ep = &ep0[ix];
assert(ep->me_key != NULL);
// 如果entry中的key和查詢的key相同，說明是要查找的數(shù)據(jù)
if (ep->me_key == key) {
// 設(shè)置對應(yīng)的返回value
*value_addr = ep->me_value;
return ix;
}
// 如果key不同哈希卻相同的情況
if (ep->me_hash == hash) {
PyObject *startkey = ep->me_key;
Py_INCREF(startkey);
// 比較兩個key是否相等，1代表相等，0代表不等，-1代表比較失敗
int cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
Py_DECREF(startkey);
// 比較失敗的情況，說明是異常情況，返回一個錯誤狀態(tài)
if (cmp < 0) {
*value_addr = NULL;
return DKIX_ERROR;
}
if (dk == mp->ma_keys && ep->me_key == startkey) {
// 比較相等
if (cmp > 0) {
*value_addr = ep->me_value;
return ix;
}
}
// 如果能到這里（哈希相同，key卻不同），說明字典在使用期間發(fā)生了改變，因此需要重新查詢
else {
/* The dict was mutated, restart */
goto top;
}
}
}
// 不是對應(yīng)的key，則通過下面探測函數(shù)繼續(xù)尋找下一個位置
perturb >>= PERTURB_SHIFT;
i = (i*5 + perturb + 1) & mask;
}
Py_UNREACHABLE();
}
// 獲取對應(yīng)key的索引中存放的entry索引（具體內(nèi)容存放的地方）
static inline Py_ssize_t
dictkeys_get_index(PyDictKeysObject *keys, Py_ssize_t i)
{
// 字典大小
Py_ssize_t s = DK_SIZE(keys);
Py_ssize_t ix;
// 基于字典大小，選擇對應(yīng)的數(shù)據(jù)類型存放索引值
if (s <= 0xff) {
// 獲取到存放所有key的地方
int8_t *indices = (int8_t*)(keys->dk_indices);
// 獲取當(dāng)前key對應(yīng)的索引
ix = indices[i];
}
else if (s <= 0xffff) {
// 基本和前面一樣，只是存放索引的類型不同
int16_t *indices = (int16_t*)(keys->dk_indices);
ix = indices[i];
}
#if SIZEOF_VOID_P > 4
else if (s > 0xffffffff) {
int64_t *indices = (int64_t*)(keys->dk_indices);
ix = indices[i];
}
#endif
else {
int32_t *indices = (int32_t*)(keys->dk_indices);
ix = indices[i];
}
// 結(jié)果必須是索引存儲的值存在或者為空
assert(ix >= DKIX_DUMMY);
return ix;
}
dict刪除
dict的刪除操作并不會真正將entries中對應(yīng)的索引刪除，而是進行一種偽刪除操作-將entries中對應(yīng)位置的內(nèi)容清空（否則需要對后面的數(shù)據(jù)進行前挪操作，并且還要更新后面幾個數(shù)據(jù)的key，效率上的問題可想而知...），源碼邏輯如下：
// 刪除操作邏輯
static int
delitem_common(PyDictObject *mp, Py_hash_t hash, Py_ssize_t ix,
PyObject *old_value)
{
PyObject *old_key;
PyDictKeyEntry *ep;
Py_ssize_t hashpos = lookdict_index(mp->ma_keys, hash, ix);
assert(hashpos >= 0);
// 使用數(shù)-1
mp->ma_used--;
mp->ma_version_tag = DICT_NEXT_VERSION();
ep = &DK_ENTRIES(mp->ma_keys)[ix];
// 設(shè)置對應(yīng)位置為dummy態(tài)
dictkeys_set_index(mp->ma_keys, hashpos, DKIX_DUMMY);
// 因為存在dummy態(tài)，所以需要修改索引方式為支持dummy態(tài)的
ENSURE_ALLOWS_DELETIONS(mp);
old_key = ep->me_key;
// 設(shè)置entries中對應(yīng)位置的key和value為空
ep->me_key = NULL;
ep->me_value = NULL;
Py_DECREF(old_key);
Py_DECREF(old_value);
ASSERT_CONSISTENT(mp);
return 0;
}
// 刪除主邏輯
int
PyDict_DelItem(PyObject *op, PyObject *key)
{
Py_hash_t hash;
assert(key);
// 可hash校驗
if (!PyUnicode_CheckExact(key) ||
(hash = ((PyASCIIObject *) key)->hash) == -1) {
hash = PyObject_Hash(key);
if (hash == -1)
return -1;
}
return _PyDict_DelItem_KnownHash(op, key, hash);
}
int
_PyDict_DelItem_KnownHash(PyObject *op, PyObject *key, Py_hash_t hash)
{
Py_ssize_t ix;
PyDictObject *mp;
PyObject *old_value;
if (!PyDict_Check(op)) {
PyErr_BadInternalCall();
return -1;
}
assert(key);
assert(hash != -1);
mp = (PyDictObject *)op;
// 找到對應(yīng)的entries索引
ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &old_value);
// 異常情況處理
if (ix == DKIX_ERROR)
return -1;
// 如果索引的entry位置內(nèi)容為空，則報錯
if (ix == DKIX_EMPTY || old_value == NULL) {
_PyErr_SetKeyError(key);
return -1;
}
// Split table doesn't allow deletion. Combine it.
if (_PyDict_HasSplitTable(mp)) {
if (dictresize(mp, DK_SIZE(mp->ma_keys))) {
return -1;
}
ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &old_value);
assert(ix >= 0);
}
// 偽刪除邏輯
return delitem_common(mp, hash, ix, old_value);
}
update主邏輯
static int
dict_merge(PyObject *a, PyObject *b, int override)
{
PyDictObject *mp, *other;
Py_ssize_t i, n;
PyDictKeyEntry *entry, *ep0;
assert(0 <= override && override <= 2);
if (a == NULL || !PyDict_Check(a) || b == NULL) {
PyErr_BadInternalCall();
return -1;
}
// 左邊的轉(zhuǎn)字典類型
mp = (PyDictObject*)a;
// 如果右邊的是字典類型，且可以用字典的方法迭代
if (PyDict_Check(b) && (Py_TYPE(b)->tp_iter == (getiterfunc)dict_iter)) {
// 右邊的也轉(zhuǎn)字典類型
other = (PyDictObject*)b;
// 如果兩個字典是同一個或者右邊的字典為空，則直接返回
if (other == mp || other->ma_used == 0)
return 0;
// 如果左邊的字典為空，到時候就直接將右邊的內(nèi)容覆蓋到左邊的字典里
if (mp->ma_used == 0)
override = 1;
// 如果左邊字典允許使用的數(shù)量比右邊已使用的key數(shù)量小，則進行擴容操作
if (USABLE_FRACTION(mp->ma_keys->dk_size) < other->ma_used) {
if (dictresize(mp, ESTIMATE_SIZE(mp->ma_used + other->ma_used))) {
return -1;
}
}
// 獲取entries數(shù)組進行迭代
ep0 = DK_ENTRIES(other->ma_keys);
for (i = 0, n = other->ma_keys->dk_nentries; i < n; i++) {
PyObject *key, *value;
Py_hash_t hash;
entry = &ep0[i];
key = entry->me_key;
hash = entry->me_hash;
// split/combined型獲取value方式兼容
if (other->ma_values)
value = other->ma_values[i];
else
value = entry->me_value;
if (value != NULL) {
int err = 0;
Py_INCREF(key);
Py_INCREF(value);
// 如果覆蓋模式的話，則直接將右邊字典的key設(shè)置進去（如果左邊字典有該key，則會被覆蓋）
if (override == 1)
err = insertdict(mp, key, hash, value);
// 如果在左邊的字典里沒找到對應(yīng)的key，則插入數(shù)據(jù)
else if (_PyDict_GetItem_KnownHash(a, key, hash) == NULL) {
if (PyErr_Occurred()) {
Py_DECREF(value);
Py_DECREF(key);
return -1;
}
err = insertdict(mp, key, hash, value);
}
// 如果左邊的字典里有該key，且override為2，則不允許覆蓋，報錯
else if (override != 0) {
_PyErr_SetKeyError(key);
Py_DECREF(value);
Py_DECREF(key);
return -1;
}
// 所以如果override==0，那么如果左邊有該key，則不進行任何操作
Py_DECREF(value);
Py_DECREF(key);
if (err != 0)
return -1;
// 字典update期間被修改導(dǎo)致的entries發(fā)生改變
if (n != other->ma_keys->dk_nentries) {
PyErr_SetString(PyExc_RuntimeError,
"dict mutated during update");
return -1;
}
}
}
}
// 左邊不為字典類型的情況
else {
PyObject *keys = PyMapping_Keys(b);
PyObject *iter;
PyObject *key, *value;
int status;
if (keys == NULL)
return -1;
// 獲取key的迭代器
iter = PyObject_GetIter(keys);
Py_DECREF(keys);
if (iter == NULL)
return -1;
// 迭代key進行賦值操作
for (key = PyIter_Next(iter); key; key = PyIter_Next(iter)) {
// 非覆蓋的情況
if (override != 1) {
// 如果左邊的字典里存在該key
if (PyDict_GetItemWithError(a, key) != NULL) {
// 如果override==2，則報錯
if (override != 0) {
_PyErr_SetKeyError(key);
Py_DECREF(key);
Py_DECREF(iter);
return -1;
}
// 如果override==0，則直接跳到下一個key
Py_DECREF(key);
continue;
}
// 當(dāng)線程當(dāng)中存在異常
else if (PyErr_Occurred()) {
Py_DECREF(key);
Py_DECREF(iter);
return -1;
}
}
// 如果覆蓋模式，則直接設(shè)置對應(yīng)的鍵值對
value = PyObject_GetItem(b, key);
if (value == NULL) {
Py_DECREF(iter);
Py_DECREF(key);
return -1;
}
status = PyDict_SetItem(a, key, value);
Py_DECREF(key);
Py_DECREF(value);
if (status < 0) {
Py_DECREF(iter);
return -1;
}
}
Py_DECREF(iter);
if (PyErr_Occurred())
return -1;
}
// 對combined/split型字典的相關(guān)檢查
ASSERT_CONSISTENT(a);
return 0;
}
// update字典
int
PyDict_Update(PyObject *a, PyObject *b)
{
// update字典主邏輯，依次傳入2個字典，第三個參數(shù)代表是否覆蓋（0-不覆蓋，1-覆蓋，2-有相同key則報錯）
return dict_merge(a, b, 1);
}
迭代器
迭代原理
通用迭代器的本質(zhì)（有些特殊對象會根據(jù)自身迭代特點，實現(xiàn)特定格式的迭代器，這里主要介紹最常用的迭代器）就是在內(nèi)部定義了一個索引，代表迭代到的位置，然后再將一個指針指向要迭代的序列（同時對序列引用+1），當(dāng)進行next遍歷時則取出當(dāng)前序列對應(yīng)索引位置的值，并將索引+1，源碼如下：
// 迭代器定義
typedef struct {
PyObject_HEAD
// 迭代到的位置索引
Py_ssize_t it_index;
// 指向迭代的序列
PyObject *it_seq; /* Set to NULL when iterator is exhausted */
} seqiterobject;
// 創(chuàng)建一個迭代器
PyObject *
PySeqIter_New(PyObject *seq)
{
seqiterobject *it;
if (!PySequence_Check(seq)) {
PyErr_BadInternalCall();
return NULL;
}
it = PyObject_GC_New(seqiterobject, &PySeqIter_Type);
if (it == NULL)
return NULL;
// 初始化索引為0
it->it_index = 0;
// 對指向的序列引用+1
Py_INCREF(seq);
// 指向要迭代的序列
it->it_seq = seq;
_PyObject_GC_TRACK(it);
return (PyObject *)it;
}
// next邏輯
static PyObject *
iter_iternext(PyObject *iterator)
{
seqiterobject *it;
PyObject *seq;
PyObject *result;
assert(PySeqIter_Check(iterator));
it = (seqiterobject *)iterator;
seq = it->it_seq;
if (seq == NULL)
return NULL;
if (it->it_index == PY_SSIZE_T_MAX) {
PyErr_SetString(PyExc_OverflowError,
"iter index too large");
return NULL;
}
// 取出序列中對應(yīng)索引的值
result = PySequence_GetItem(seq, it->it_index);
if (result != NULL) {
// 索引+1
it->it_index++;
return result;
}
if (PyErr_ExceptionMatches(PyExc_IndexError) ||
PyErr_ExceptionMatches(PyExc_StopIteration))
{
PyErr_Clear();
it->it_seq = NULL;
Py_DECREF(seq);
}
return NULL;
}
例如list轉(zhuǎn)迭代器時，會將list的引用計數(shù)+1，并在內(nèi)部維護一個變量存放當(dāng)前索引的位置，當(dāng)對list迭代完成時，會將list的引用計數(shù)-1，從而釋放list，舉例：
class MyList(list):
def __del__(self):
print("list被回收...")
l = MyList([1,2,3])
# 迭代器使用到了list，因此list的引用+1
it = iter(l)
# list的引用-1
del l
# 迭代list
for i in it:
print(i)
# list迭代完成，list引用-1
print("end...")
# 可以看到list的回收在end之前，即迭代器完成了對list的全部迭代以后，就會釋放list，即使后面還會用到這個迭代器
print(it)
# 1
# 2
# 3
# list被回收...
# end...
# <list_iterator object at 0x000002530C65DE80>
迭代器其他接口
python中為通用迭代器提供了一些額外的接口，如：獲取迭代器的長度、修改當(dāng)前索引到的位置，源碼如下：
// 獲取迭代器長度
static PyObject *
iter_len(seqiterobject *it, PyObject *Py_UNUSED(ignored))
{
Py_ssize_t seqsize, len;
if (it->it_seq) {
if (_PyObject_HasLen(it->it_seq)) {
// 獲取指向的序列長度
seqsize = PySequence_Size(it->it_seq);
if (seqsize == -1)
return NULL;
}
else {
Py_RETURN_NOTIMPLEMENTED;
}
// 迭代器的長度就是序列的長度減去當(dāng)前迭代的位置索引
len = seqsize - it->it_index;
if (len >= 0)
return PyLong_FromSsize_t(len);
}
return PyLong_FromLong(0);
}
// 修改索引位置
static PyObject *
iter_setstate(seqiterobject *it, PyObject *state)
{
Py_ssize_t index = PyLong_AsSsize_t(state);
if (index == -1 && PyErr_Occurred())
return NULL;
if (it->it_seq != NULL) {
if (index < 0)
index = 0;
it->it_index = index;
}
Py_RETURN_NONE;
}
// 對外接口定義
static PyMethodDef seqiter_methods[] = {
{"__length_hint__", (PyCFunction)iter_len, METH_NOARGS, length_hint_doc},
{"__reduce__", (PyCFunction)iter_reduce, METH_NOARGS, reduce_doc},
{"__setstate__", (PyCFunction)iter_setstate, METH_O, setstate_doc},
{NULL, NULL} /* sentinel */
};
- 獲取迭代器長度示例：
a = [1,2,3]
b = iter(a)
# 獲取迭代器的剩余長度
print(b.__length_hint__())
next(b)
print(b.__length_hint__())
# 3
# 2
- 修改索引位置示例：
a = [1,2,3]
b = iter(a)
print(next(b))
# 迭代索引重新設(shè)為0
b.__setstate__(0)
print(next(b))
# 1
# 1
待更新...
