Python C语言API系列教程（四、Python内置容器C语言接口）

在上一篇文章中，我们了解到Python的内置对象的C语言表示及其API，并优化了datetimecpy.date对象。在这篇文章中，我们会继续探讨Python的内置容器，比如list、tuple、dict和set。同时，我们也会进一步扩展date对象。关于本系列教程的repo戳这里。

要点讲解

PyListObject及其相关函数

Java的List有两种实现，分别是数组实现（ArrayList）和链表实现（LinkedList）。那么Python的list是怎么实现的呢？这个问题我觉得不是很好回答，因为Python的list底层是一段连续分配的内存，然后通过指针来获取指定位置的数据。如果强行分类的话，它可能更贴近数组实现。不妨直接看一下源码——

typedef struct {
    PyObject_VAR_HEAD
   
    PyObject **ob_item;

    Py_ssize_t allocated;
} PyListObject;

来自Python 3.9

实现很直接，ob_item用来存放元素的数据，allocated表示已分配的内存。有一点需要强调，allocated并不表示这个list的实际长度，实际长度是存放在这个PyObject的ob_type的ob_size中的，且这个ob_size必须小于allocated。类似这种特殊处理的操作在整个Python虚拟机中有很多，因为CPython非常强调重复利用内存空间。

这里的ob_item用到了一个指针的指针，我们应该这样理解：一般情况下，用户应该把PyObject*看成一个整体，因为所有对Python对象的操作都是引用，而Python对象的数组在C语言的环境下自然就是指针的指针了。

重点看一下API——

• PyList_New：新建一个list对象，可以传入一个Py_ssize_t类型规定其长度，如果返回NULL说明创建失败，否则返回一个对list的新引用，即用户对这个引用的生命周期负责。其实，一般传入0即可，要用的时候可以通过PyList_Append方法在尾部追加新元素。如果传入确定数值的话，其元素对象是NULL而不是PyNone对象，如果使用不谨慎可能会给维护带来麻烦。
• PyList_SetItem：对给定list在给定位置设置一个对象，类似于替换原有的元素。在使用的时候也需要注意几点：首先它是“偷引用”，虚拟机会给传入的对象的引用次数加一。其次，虚拟机不会处理被替换对象的引用次数，因此如果使用不当会造成内存泄漏。所以最佳实践是替换NULL对象。
• PyList_GetItem：获取给定list的指定位置的值。和PyList_SetItem相反，它是获取一个对象，但是这个对象是“借引用”。这意味着用户不需要对这个对象的生命周期负责。如果需要对这个对象用作其他地方，就需要用户去“偷引用”，也就是调用Py_INCREF宏让其引用次数加一。
• PyList_Append：在尾部追加一个对象，相当于Python的append方法。这个是我最常用的方法，比较普适。 类似的API还有很多，可以参考官方文档。

PyTupleObject及其相关函数

和list一样，tuple也是sequence容器，区别在于tuple是不可变的。因此，其底层实现也是极为相似——

typedef struct {
    PyObject_VAR_HEAD
    
    PyObject *ob_item[1];
} PyTupleObject;

来自Python 3.9

由于是不可变的，所以它不需要动态分配内存，也就没有allocated字段。其他也是类似，同样也是通过ob_size存储长度。

这里有个细节，就算ob_item的定义和PyListObject有显著的不一样。这里是明确定义成一个数组，也就是说它在编译阶段就被当成数组去处理，即元素的存储空间是连续的。如果再次回答tuple底层实现是数组还是链表，那么答案显然是数组。

重点关注其API——

• PyTuple_New：新建一个tuple对象。和PyList_New一样，可以传入一个Py_ssize_t类型规定其长度，如果返回NULL说明创建失败，否则返回一个对tuple的新引用。
• PyTuple_SetItem：虽然在Python中，tuple无法修改，但是C语言是提供了这个API。和list对象一样，可以将给定tuple的给定位置的对象替换掉。同样也需要关注内存泄漏，因为虚拟机“偷引用”行为。
• PyTuple_GetItem：获取给定tuple的给定位置的对象，也是借引用。

PyDictObject及其相关函数

dict是Python中的字典。类似于Java，Python中的字典也是哈希表构造的，但不同的是其负载因子为2/3.也就是说，如果一个哈希表中有超过2/3的“槽位”被使用了就应该扩容。先直接看一下其定义——

#define DK_ENTRIES(dk) \
    ((PyDictKeyEntry*)(&((int8_t*)((dk)->dk_indices))[DK_SIZE(dk) * DK_IXSIZE(dk)]))

typedef struct {
    Py_hash_t me_hash;
    PyObject *me_key;
    PyObject *me_value; 
} PyDictKeyEntry;

struct _dictkeysobject {
    Py_ssize_t dk_refcnt; // value的下标，split 类型时有意义且其值大于1，否则为1
    ...
    dict_lookup_func dk_lookup; // 查找函数
    char dk_indices[]; // combined 类型存储value的地方

};

typedef struct _dictkeysobject PyDictKeysObject;

typedef struct {
    PyObject_HEAD
    Py_ssize_t ma_used;
    uint64_t ma_version_tag;
    PyDictKeysObject *ma_keys;
    PyObject **ma_values; // split 类型存储value的地方
} PyDictObject;

来自Python 3.9

你看懂了吗？其实这个版本的dict有两种类型，分别是split类型和combined类型。顾名思义，combined类型就是将key和value都存放在一起，即存放在PyDictKeyEntry内（me_key是key，me_value是value），而split类型将key和value分开来存储，即me_key仍存放key，但value以“数组”的形式存放在ma_values里面，并通过dk_refcnt标识是哪个key对应的value。后者更像Java中的HashMap的实现。

不妨画个图展示——

左边是combined类型，key和value存放在entry内，右边是split，key和value分开放且value通过entry的其他信息找到。

至于为什么要使用两套数据结构标识dict，这可能涉及到历史原因。早期采用的是combined类型，后来考虑到采用split类型更能节省内存空间所以又加了一种类型。具体可以参考当年开发的邮件列表[Python-Dev] More compact dictionaries with faster iteration

这里又运用了一个C语言内存技巧。PyDictKeysObject在存储dk_indices的时候是以char数组的形式存储的，而使用时通过DK_ENTRIES宏强行转换成PyDictKeyEntry进行读取，这样做的好处是更节约内存。

再讲下去要偏离我们的主题了，我们主题是介绍API，有机会会专门出一个专题介绍Python虚拟机。几个常用的API如下：

• PyDict_Contains：检查给定的dict是否包含某个key对象，如果包含则返回1，否则返回0.如果返回-1则说明出错。类似于Python的in操作符。
• PyDict_SetItem：在给定的dict中添加键值对，和前面的sequence对象一样，虚拟机不对被替换的对象负责。另外这个key是必须可哈希的。
• PyDict_GetItem：在给定的dict中根据key获取value，同样也是借引用。另外，如果返回NULL则说明当前key在字典中不存在。
• PyDict_Items：Python中的items函数的C语言实现，返回的是PyListObject，类似的还有PyDict_Keys和PyDict_Values。

更多API可以参考官方文档。

PySetObject及其相关函数

众所周知，Java中的HashSet本质上是对HashMap的复用，但是Python虚拟机对set重新实现了。重新实现的部分是它的查找函数，但是底层原理仍然是哈希表的形式。，先看一下它的结构——

typedef struct {
    PyObject *key;
    Py_hash_t hash;
} setentry;

typedef struct {
    PyObject_HEAD
    Py_ssize_t used;
    Py_ssize_t mask;  // set的插槽数-1，直接通过hash & mask计算插槽位置
    setentry *table;  // 哈希表，存放数据的地方
    ...
} PySetObject;

来自Python 3.9

和dict相比稍微简单点，数据都存储在table中。如果要插入一个对象，首先会将其哈希值与mask做与运算获取到对应插槽的位置，如果该位置在table中是空的则直接插入，否则插槽位置加一继续尝试插入。了解一下相关API——

• PySet_Contains：检查给定set中是否包含给定对象，如果包含返回1否则返回0。如果返回-1则说明内部异常。另外，它不会将非set类型的对象转换成set类型。
• PySet_Add：为给定set插入一个对象，也可以作用于frozenset。如果成功返回1否则返回0。
• PySet_Discard：为给定set删除一个对象。同样如果成功返回1否则返回0。如果返回-1则说明内部异常。

更多API可以参考官方文档

操作实践

我们继续完善datetimecpy项目，该项目的repo在这里，本章对应的代码在Ch-4分支上。

由于datetime这个模块本身就很少用到容器，所以本章“操作实践”部分稍微简单点，实现一个timetuple函数。还是按照老规矩，先用Python打个草稿——

>>> import datetimecpy
>>> date = datetimecpy.date(year=2023, month=5, day=25)
>>> date
datetimecpy.date(year=2023, month=5, day=25)
>>> date.timetuple()
(2023, 5, 25, 0, 0, 0, 3, 145, -1)

首先，在上一章的基础上新增一个timetuple函数的声明，然后在函数描述里面添加对该函数的描述——

PyObject* Date_timetuple(PyObject* self, PyObject* Py_UNUSED(args));

static PyMethodDef date_methods[] = {
    ...
    {"timetuple", Date_timetuple, METH_NOARGS, PyDoc_STR("timetuple\n-\n\n Get the tuple-like value of the current date.") },
    {NULL, NULL}
};

然后直接实现这个函数，在实现的过程中用到了PyTupleObject相关API——

PyObject* Date_timetuple(PyObject* self, PyObject* Py_UNUSED(args)) {
    PyObject* retval = PyTuple_New(9);
    PyTuple_SetItem(retval, 0, ((Date*)self)->year);
    PyTuple_SetItem(retval, 1, ((Date*)self)->month);
    PyTuple_SetItem(retval, 2, ((Date*)self)->day);
    PyTuple_SetItem(retval, 3, PyLong_FromLong(0L));
    PyTuple_SetItem(retval, 4, PyLong_FromLong(0L));
    PyTuple_SetItem(retval, 5, PyLong_FromLong(0L));
    PyTuple_SetItem(retval, 6, PyLong_FromLong((long)_Date_get_wday(PyLong_AsLong(((Date*)self)->year),PyLong_AsLong(((Date*)self)->month), PyLong_AsLong(((Date*)self)->day))));
    PyTuple_SetItem(retval, 7,PyLong_FromLong((long)_Date_get_yday(PyLong_AsLong(((Date*)self)->year),PyLong_AsLong(((Date*)self)->month), PyLong_AsLong(((Date*)self)->day))));
    PyTuple_SetItem(retval, 8, PyLong_FromLong(-1L));
    return retval;

}

timetuple是返回一个tuple，对应的元素分别是year、month、day、hour、minute、second、wday、yday和dst，其中wday代表周几，yday代表一年中第几天。所以实现起来简单粗暴，新建一个PyTupleObject，然后填值并返回就好了。

如果实现都没问题运行结果如下图所示——

小结

本章讲解了Python的内置容器的实现和对应的C语言API，同时继续完善了datetimecpy。下一章会将模块和方法相关的的C语言API，并开始构建datetime中新的对象——time对象。