python-源码阅读(3)-python中基本类型

yuan lang

2024-03-21

python

整型

PyTypeObject PyLong_Type = {
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    "int",                                      /* tp_name */
    offsetof(PyLongObject, ob_digit),           /* tp_basicsize */
    sizeof(digit),                              /* tp_itemsize */
    long_dealloc,                               /* tp_dealloc */
    0,                                          /* tp_print */
    0,                                          /* tp_getattr */
    0,                                          /* tp_setattr */
    0,                                          /* tp_reserved */
    long_to_decimal_string,                     /* tp_repr */
    &long_as_number,                            /* tp_as_number */
    0,                                          /* tp_as_sequence */
    0,                                          /* tp_as_mapping */
    (hashfunc)long_hash,                        /* tp_hash */
    0,                                          /* tp_call */
    long_to_decimal_string,                     /* tp_str */
    PyObject_GenericGetAttr,                    /* tp_getattro */
    0,                                          /* tp_setattro */
    0,                                          /* tp_as_buffer */
    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE |
        Py_TPFLAGS_LONG_SUBCLASS,               /* tp_flags */
    long_doc,                                   /* tp_doc */
    0,                                          /* tp_traverse */
    0,                                          /* tp_clear */
    long_richcompare,                           /* tp_richcompare */
    0,                                          /* tp_weaklistoffset */
    0,                                          /* tp_iter */
    0,                                          /* tp_iternext */
    long_methods,                               /* tp_methods */
    0,                                          /* tp_members */
    long_getset,                                /* tp_getset */
    0,                                          /* tp_base */
    0,                                          /* tp_dict */
    0,                                          /* tp_descr_get */
    0,                                          /* tp_descr_set */
    0,                                          /* tp_dictoffset */
    0,                                          /* tp_init */
    0,                                          /* tp_alloc */
    long_new,                                   /* tp_new */
    PyObject_Del,                               /* tp_free */
};

python3统一采用长整型8 bit
id() 内存地址; is 是判断内存地址id是否相等，==判断内容是否相等
相同代码块的缓存机制 int str bool 使用相同的常量池对象
在不同代码块下，采用小整数驻留机制[-5,256]
该tp_new函数应该调用subtype->tp_alloc(subtype, nitems)为对象分配空间。于不可变类型，所有初始化都应该在tp_new，而对于可变类型，大多数初始化应该延迟到tp_init。

字符串

PyObject *
PyUnicode_FromString(const char *u)
{
    size_t size = strlen(u);
    if (size > PY_SSIZE_T_MAX) {
        PyErr_SetString(PyExc_OverflowError, "input too long");
        return NULL;
    }
    return PyUnicode_DecodeUTF8Stateful(u, (Py_ssize_t)size, NULL, NULL);
}

字符串对象的共享机制intern

# 字符串创建
void PyUnicode_InternInPlace(PyObject **p)
{
    PyObject *s = *p;
    PyObject *t;

    if (s == NULL || !PyUnicode_Check(s))
        return;

    // 对PyUnicodeObjec进行类型和状态检查
    if (!PyUnicode_CheckExact(s))
        return;
    if (PyUnicode_CHECK_INTERNED(s))
        return;
    // 创建intern机制的dict
    if (interned == NULL) {
        interned = PyDict_New();
        if (interned == NULL) {
            PyErr_Clear(); /* Don't leave an exception */
            return;
        }
    }

    // 对象是否存在于inter中
    t = PyDict_SetDefault(interned, s, s);

    // 存在， 调整引用计数
    if (t != s) {
        Py_INCREF(t);
        Py_SETREF(*p, t);
        return;
    }
    /* The two references in interned are not counted by refcnt.
       The deallocator will take care of this */
    Py_REFCNT(s) -= 2;
    _PyUnicode_STATE(s).interned = SSTATE_INTERNED_MORTAL;
}


[unicodeobjec.c]
PyObject * PyUnicode_DecodeUTF8Stateful(const char *s,
                             Py_ssize_t size,
                             const char *errors,
                             Py_ssize_t *consumed)
{
    ...

    /* ASCII is equivalent to the first 128 ordinals in Unicode. */
    if (size == 1 && (unsigned char)s[0] < 128) {
        if (consumed)
            *consumed = 1;
        return get_latin1_char((unsigned char)s[0]);
    }
    ...
}
static PyObject *unicode_latin1[256] = {NULL};
static PyObject* get_latin1_char(unsigned char ch)
{
    PyObject *unicode = unicode_latin1[ch];
    if (!unicode) {
        unicode = PyUnicode_New(1, ch);
        if (!unicode)
            return NULL;
        PyUnicode_1BYTE_DATA(unicode)[0] = ch;
        assert(_PyUnicode_CheckConsistency(unicode, 1));
        unicode_latin1[ch] = unicode;
    }
    Py_INCREF(unicode);
    return unicode;
}

总结：先对所创建的字符串（只有一个字符）对象进行intern操作，再将inter的结果缓存到字符缓冲池 unicode_latin1 中,两者都是指向同一个字符对象。

intern机制中的PyUnicodObject采用了特殊的引用计数机制。将一个PyUnicodeObject对象a的PyObject指针作为key和valu添加到intered中时，PyDictObjec对象会通过这两个指针对a的引用计数进行两次+1操作。这会造成a的引用计数在python程序结束前永远不会为0，这也是 Py_REFCNT(s) -= 2; 将计数减2的原因。
字符串对象有两种状态，一个是 SSTATE_INTERNED_IMMORTAL 另一个是 SSTATE_INTERNED_MORTAL，处于SSTATE_INTERNED_IMMORTAL这种状态的字符串永远不会被销毁，它将与python虚拟机共存亡。 PyUnicode_InternInPlace 函数只能创建SSTATE_INTERNED_MORTAL 状态的对象
python中使用 “+” 符号进行字符串拼接，这种方法效率极低，建议使用jion

list

typedef struct {
    PyObject_VAR_HEAD
    // ob_item为指向元素列表的指针，实际上python中list[0]就是ob_item[0]
    PyObject **ob_item;

    Py_ssize_t allocated;
} PyListObject;

PyObject * PyList_New(Py_ssize_t size)
{
    PyListObject *op;
    ...
    // 缓冲池是否可用
    if (numfree) {
        numfree--;
        op = free_list[numfree];
        _Py_NewReference((PyObject *)op);
    } else {
        // 缓冲池不可用时
        op = PyObject_GC_New(PyListObject, &PyList_Type);
        if (op == NULL)
            return NULL;
    }
    // 申请为PyListObject对象中维护的元素列表空间
    if (size <= 0)
        op->ob_item = NULL;
    else {
        // 空间申请size个空间的数组并重置0
        op->ob_item = (PyObject **) PyMem_Calloc(size, sizeof(PyObject *));
    }

    Py_SIZE(op) = size;
    op->allocated = size;
    _PyObject_GC_TRACK(op);
    return (PyObject *) op;
}

缓冲池 free_list 中最多会维护80个PyListObject对象

1
2
3

#define PyList_MAXFREELIST 80
static PyListObject *free_list[PyList_MAXFREELIST];
static int numfree = 0;

设置元素 list[2] = 200

int PyList_SetItem(PyObject *op, Py_ssize_t i,
               PyObject *newitem)
{
    PyObject **p;

    // 索引越界检查
    if (i < 0 || i >= Py_SIZE(op)) {
        Py_XDECREF(newitem);
        PyErr_SetString(PyExc_IndexError,
                        "list assignment index out of range");
        return -1;
    }
    // 找到ob_item[i]
    p = ((PyListObject *)op) -> ob_item + i;
    Py_XSETREF(*p, newitem);
    return 0;
}

#define Py_XSETREF(op, op2)                     \
    do {                                        \
        PyObject *_py_tmp = (PyObject *)(op);   \
        (op) = (op2);                           \
        Py_XDECREF(_py_tmp);                    \
    } while (0)

插入元素

[longobject.c]
int PyList_Insert(PyObject *op, Py_ssize_t where, PyObject *newitem)
{
    // 类型检查
    if (!PyList_Check(op)) {
        PyErr_BadInternalCall();
        return -1;
    }
    return ins1((PyListObject *)op, where, newitem);
}

static int
ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
{
    Py_ssize_t i, n = Py_SIZE(self);
    PyObject **items;

    if (list_resize(self, n+1) < 0)
        return -1;

    // 确定插入点
    if (where < 0) {
        where += n;
        if (where < 0)
            where = 0;
    }
    if (where > n)
        where = n;
    items = self->ob_item;
    // 元素后移
    for (i = n; --i >= where; )
        items[i+1] = items[i];
    Py_INCREF(v);
    items[where] = v;
    return 0;
}

删除元素

static PyObject *
listremove(PyListObject *self, PyObject *v)
{
    Py_ssize_t i;

    for (i = 0; i < Py_SIZE(self); i++) {
        int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
        // 如果相等, 删除元素
        if (cmp > 0) {
            if (list_ass_slice(self, i, i+1,
                               (PyObject *)NULL) == 0)
                Py_RETURN_NONE;
            return NULL;
        }
        else if (cmp < 0)
            return NULL;
    }
    PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
    return NULL;
}

Dict

闭散列法也称为开放定址法.当产生冲突时,python会通过一个二次探测函数f,计算下一个候选索引, 如果索引不可用,就再次用f探测.直到找到一个可用的位置.

[dict-common.h]
typedef struct {
    Py_hash_t me_hash;
    PyObject *me_key;
    PyObject *me_value;
} PyDictKeyEntry;

[dictobject.h]
PyObject * PyDict_New(void)
{
    PyDictKeysObject *keys = new_keys_object(PyDict_MINSIZE);
    if (keys == NULL)
        return NULL;
    return new_dict(keys, NULL);
}
static PyDictKeysObject *new_keys_object(Py_ssize_t size)
{
    PyDictKeysObject *dk;
    Py_ssize_t es, usable;

    usable = USABLE_FRACTION(size);
    es = 4;

    if (size == PyDict_MINSIZE && numfreekeys > 0) {
        // 使用缓冲池
        dk = keys_free_list[--numfreekeys];
    }
    else {
        dk = PyObject_MALLOC(sizeof(PyDictKeysObject)
                             - Py_MEMBER_SIZE(PyDictKeysObject, dk_indices)
                             + es * size
                             + sizeof(PyDictKeyEntry) * usable);
    }
    DK_DEBUG_INCREF dk->dk_refcnt = 1;
    dk->dk_size = size;
    dk->dk_usable = usable;
    dk->dk_lookup = lookdict_unicode_nodummy;
    dk->dk_nentries = 0;
    // hash table 初始化
    memset(&dk->dk_indices.as_1[0], 0xff, es * size);
    memset(DK_ENTRIES(dk), 0, sizeof(PyDictKeyEntry) * usable);
    return dk;
}

PyDict_MINSIZE 值为8, 默认情况下, PyDict_New会创建8个entry
Unused： me_key == me_value == NULL (Unused是entry的初始状态，key和value都为NULL。插入元素时，Unused状态转换成Active状态。这是me_key为NULL的唯一情况。)

Active： me_key != NULL and me_key != dummy 且 me_value != NULL(插入元素后，entry就成了Active状态，这是me_value唯一不为NULL的情况，删除元素时Active状态刻转换成Dummy状态。)

Dummy： me_key == dummy 且 me_value == NULL(Dummy是一种类似的伪删除方式，保证探测链的连续性 ABC 删除B 保证A->c)

lookdict(k,v)

 1. index <- hash1(k)，freeslot<-Null,根据me_key与me_value选择2、3、4一个执行;
 2. 查看index处的值处于’有效元素占据‘状态，判断data[index]与v是否一致(地址或内容),一致,则返回查找成功;否则转5
 3. index所指向的位置处于’原始空‘状态，查找失败，若freeslot==Null返回index;否则返回freeslot;转5
 4. index所指向的位置处于’有效元素离去‘状态，freeslot<-index, 转5
 5. index <- hash2(index),，转2

加载因子 2/3 ，大于则扩容