python3.7源码分析－集合（set）
python集合
set是⽆序且不重复的集合，是可变的，通常⽤来从列表中删除重复项以及计算数学运算，如交集、并集、差分和对称差分等集合操作。set ⽀持 x in set, len(set)，和 for x in set。作为⼀个⽆序的集合，set不记录元素位置或者插⼊点。因此，sets不⽀持 indexing, 或其它类序列的操作。
python集合概述
在set中，对应的set的值的存储是通过结构setentry来保存数据值的；
typedef struct {
PyObject *key;
Py_hash_t hash; /* Cached hash code of the key */
} setentry;
key就是保存的数据，hash就是保存的数据的hash，便于查，set也是基于hash表来实现。对应的sete
ntry所对应的set的数据结构如下；
typedef struct {
PyObject_HEAD
Py_ssize_t fill; /* Number active and dummy entries*/ // 包括已经使⽤的entry与空entry值的总和
Py_ssize_t used; /* Number active entries */ // 已经使⽤可⽤的总量
/* The table contains mask + 1 slots, and that's a power of 2.
* We store the mask instead of the size because the mask is more
* frequently needed.
*/
Py_ssize_t mask; // 与hash求和的mask
/* The table points to a fixed-size smalltable for small tables
* or to additional malloc'ed memory for bigger tables.
* The table pointer is never NULL which saves us from repeated
* runtime null-tests.
*/
setentry *table; // 保存数据的数组数组指针
Py_hash_t hash; /* Only used by frozenset objects */
Py_ssize_t finger; /* Search finger for pop() */
setentry smalltable[PySet_MINSIZE]; // 保存数据的数组 默认初始化为8个元素，通过table指向
PyObject *weakreflist; /* List of weak references */
} PySetObject;
⼀个set就对应⼀个PySetObject类型数据，set会根据保存的元素⾃动调整⼤⼩。相关的内存布局如下；
python集合(set)⽰例
⽰例脚本如下：
set_a = {1,2}
set_a.add(3)
set_a.add(4)
ve(1)
set_a.update({3,})
set_a.union({1,5})
通过python反汇编获取该脚本的字节码；python -m dis set_test.py
输出的字节码如下所⽰；
1 0 LOAD_CONST 0 (1)
3 LOAD_CONST 1 (2)
6 BUILD_SET 2
9 STORE_NAME 0 (set_a)
2 12 LOAD_NAME 0 (set_a)
15 LOAD_ATTR 1 (add)
18 LOAD_CONST 2 (3)
21 CALL_FUNCTION 1
24 POP_TOP
3 25 LOAD_NAME 0 (set_a)
28 LOAD_ATTR 1 (add)
31 LOAD_CONST 3 (4)
34 CALL_FUNCTION 1
37 POP_TOP
4 38 LOAD_NAME 0 (set_a)
41 LOAD_ATTR 2 (remove)
44 LOAD_CONST 0 (1)
47 CALL_FUNCTION 1
50 POP_TOP
5 51 LOAD_NAME 0 (set_a)
54 LOAD_ATTR 3 (update)
57 LOAD_CONST 2 (3)
60 BUILD_SET 1
63 CALL_FUNCTION 1
66 POP_TOP
6 6
7 LOAD_NAME 0 (set_a)
70 LOAD_ATTR 4 (union)
73 LOAD_CONST 0 (1)
76 LOAD_CONST 4 (5)
79 BUILD_SET 2
82 CALL_FUNCTION 1
85 POP_TOP
86 LOAD_CONST 5 (None)
89 RETURN_VALUE
通过该字节码指令可知，创建set调⽤了BUILD_SET指令，初始化完成之后，就调⽤set的add⽅法添
加元素，调⽤remove删除元素，调⽤update来更新集合，通过union来合并集合。接下来就详细分析⼀下相关的操作流程。
set的创建与初始化
查BUILD_SET的虚拟机执⾏函数如下；
// Python/ceval.c
TARGET(BUILD_SET) {
PyObject *set = PySet_New(NULL); // 新建并初始化⼀个set
int err = 0;
int i;
if (set == NULL)
goto error;
for (i = oparg; i > 0; i--) { // 将传⼊初始化的参数传⼊
PyObject *item = PEEK(i);
if (err == 0)
err = PySet_Add(set, item); // 并依次对set进⾏添加操作
Py_DECREF(item);
}
STACKADJ(-oparg); // 移动弹栈
if (err != 0) {
Py_DECREF(set);
goto error;
}
PUSH(set); // 讲set压栈
DISPATCH(); // 执⾏下⼀条指令
}
此时继续查看PySet_New函数的执⾏流程；
PyObject *
PySet_New(PyObject *iterable)
{
return make_new_set(&PySet_Type, iterable);
}
...
static PyObject *
make_new_set(PyTypeObject *type, PyObject *iterable)
{
PySetObject *so;
so = (PySetObject *)type->tp_alloc(type, 0); // 申请该元素的内存
if (so == NULL) // 内存申请失败则返回为空
return NULL;
so->fill = 0; // 初始化的时候都为０
so->used = 0;
so->mask = PySet_MINSIZE - 1; // PySet_MINSIZE默认我８，mask为７ so->table = so->smalltable; // 将保存数据的头指针指向table
so->hash = -1; // 设置hash值为-1
so->finger = 0;
so->weakreflist = NULL;
if (iterable != NULL) { // 如果有迭代器
if (set_update_internal(so, iterable)) { // 将内容更新到so中
Py_DECREF(so);
return NULL;
}
}
return (PyObject *)so; // 返回初始化完成的set
}
从PySet_New的执⾏流程可知，字典的初始化过程就是初始化相关数据结构。set的插⼊
在本例的初始化过程中，由于传⼊了初始值1,2，所以会在执⾏字节码指令的时候，执⾏PySet_Add，该函数的本质与set_a.add(3)本质都调⽤了更底层set_add_key函数；
int
PySet_Add(PyObject *anyset, PyObject *key)
{
if (!PySet_Check(anyset) &&
(!PyFrozenSet_Check(anyset) || Py_REFCNT(anyset) != 1)) {
PyErr_BadInternalCall();
return -1;
}
return set_add_key((PySetObject *)anyset, key); // 向字典中添加key;
python虚拟机}
继续查看set_add_key函数的执⾏过程；
static int
set_add_key(PySetObject *so, PyObject *key)
{
Py_hash_t hash;
if (!PyUnicode_CheckExact(key) ||
(hash = ((PyASCIIObject *) key)->hash) == -1) {
hash = PyObject_Hash(key); // 获取传⼊值的hash值
if (hash == -1) // 如果不能hash则返回-1
return -1;
}
return set_add_entry(so, key, hash); // 计算完成后添加值
}
该函数主要就是检查传⼊的key是否能够被hash，如果能够被hash则直接返回，如果能被hash则继续调⽤set_add_entry函数将值加⼊到set中；
static int
set_add_entry(PySetObject *so, PyObject *key, Py_hash_t hash)
{
setentry *table;
setentry *freeslot;
setentry *entry;
size_t perturb;
size_t mask;
size_t i; /* Unsigned for defined overflow behavior */
size_t j;
int cmp;
/* Pre-increment is necessary to prevent arbitrary code in the rich
comparison from deallocating the key just before the insertion. */
Py_INCREF(key); // 提⾼key的引⽤计数
restart:
mask = so->mask; // 获取so->mask
i = (size_t)hash & mask; // 通过传⼊的hash与mask求索引下标
entry = &so->table[i]; // 获取索引对应的值
if (entry->key == NULL) // 如果获取索引的值没有被使⽤则直接跳转到found_unused处执⾏
goto found_unused;
freeslot = NULL;
perturb = hash; // perturb设置为当前hash值
while (1) {
if (entry->hash == hash) { // 如果当前hash值相等
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论