企业官网建设流程全解析

使用 Python 3 C-API 实现一个单向链表扩展

Python 的开发效率很高，但在已经通过性能分析确认的热点路径中，C 扩展可以减少计算开销。本教程用一个单向链表演示如何通过 Python 3 C-API 创建扩展类型，并实现：

• append(value)：尾部追加元素；
• len(items)：获取元素数量；
• items[index]：按下标读取元素，支持负索引；
• for value in items：独立迭代器；
• Python 对象的正确引用计数与析构。

代码地址：https://github.com/marskang/python-ext-linklist

这是学习 C-API 的示例，而非内置list的替代品。链表随机访问需要遍历，items[index]的时间复杂度是 O(n)；Python 日常业务通常应优先使用内置list。

1. 构建与运行

需要 Python 3、C 编译器和对应版本的 Python 开发头文件。

python3 setup.py build_ext--inplacepython3 test.py

build_ext --inplace会在当前目录生成与 Python 版本、操作系统和 CPU 架构相关的扩展文件，例如linklist.cpython-39-darwin.so。这是构建产物，不应提交到 Git；项目的.gitignore已忽略所有.so文件。

运行示例：

importlinklist items=linklist.LinkList()items.append("张三")items.append("12")items.append(666)print(len(items))# 3print(items[1])# 12print(items[-1])# 666print(list(items))# ['张三', '12', 666]

2. 设计：区分 Python 对象和内部 C 节点

一个常见误区是让每个链表节点都包含PyObject_HEAD。这会让每个节点都变成 Python 对象，不仅增加复杂度，也很容易把节点析构和链表析构混在一起。

这里分成三种结构：

typedefstructLinkListItem{PyObject*content;structLinkListItem*next;}LinkListItem;typedefstruct{PyObject_HEAD Py_ssize_t count;LinkListItem*head;LinkListItem*tail;}PyLinkList;typedefstruct{PyObject_HEAD PyLinkList*list;LinkListItem*current;}PyLinkListIter;

其中：

• PyLinkList是 Python 中的linklist.LinkList对象，因此以PyObject_HEAD开头；
• LinkListItem只是内部 C 节点，由PyMem_Malloc分配；
• PyLinkListIter是独立迭代器。它持有链表引用，使遍历期间链表不会被提前销毁。

3. Python 对象的引用计数

C-API 中最重要的规则是明确每个PyObject *的所有权。

METH_O方法收到的参数是借用引用，不能直接保存。链表追加元素时必须增加引用；否则 Python 调用方释放该对象后，节点中会留下悬垂指针。

staticPyObject*py_link_list_append(PyLinkList*self,PyObject*obj){LinkListItem*item=PyMem_Malloc(sizeof(*item));if(item==NULL){returnPyErr_NoMemory();}Py_INCREF(obj);/* 节点现在拥有 content 的一个引用 */item->content=obj;item->next=NULL;if(self->tail==NULL){self->head=item;}else{self->tail->next=item;}self->tail=item;self->count++;Py_RETURN_NONE;}

Python 方法必须返回PyObject *：成功时返回新引用的Py_None，出错时返回NULL且设置异常。不能把返回void的 C 函数强制转换后注册为METH_O。

链表销毁时，逐个释放节点持有的 Python 对象和 C 内存：

staticvoidpy_link_list_dealloc(PyLinkList*self){LinkListItem*item=self->head;while(item!=NULL){LinkListItem*next=item->next;Py_XDECREF(item->content);PyMem_Free(item);item=next;}Py_TYPE(self)->tp_free((PyObject*)self);}

析构函数中不能对self再执行Py_DECREF或Py_CLEAR(self)：解释器调用tp_dealloc时，该对象的引用计数已经降到零。

4. 实现长度和下标访问

Python 的len(obj)和obj[index]通过序列协议调用。这里仅实现长度和取项：

staticPySequenceMethods py_link_list_as_sequence={.sq_length=(lenfunc)py_link_list_length,.sq_item=(ssizeargfunc)py_link_list_item,};

sq_item返回给 Python 的对象必须是新引用。下列实现也支持-1这类负索引：

staticPyObject*py_link_list_item(PyLinkList*self,Py_ssize_t index){LinkListItem*item;if(index<0){index+=self->count;}if(index<0||index>=self->count){PyErr_SetString(PyExc_IndexError,"link list index out of range");returnNULL;}item=self->head;while(index-->0){item=item->next;}Py_INCREF(item->content);returnitem->content;}

len(items)是 O(1)，因为链表保存了count；items[index]需要从头遍历，因此是 O(n)。

5. 实现独立迭代器

不要把遍历游标保存到链表对象自身。否则两个iter(items)会共享状态，嵌套循环会产生跳项或重复项。

每次调用iter(items)创建一个新对象：

staticPyObject*py_link_list_getiter(PyLinkList*self){PyLinkListIter*iterator=PyObject_New(PyLinkListIter,&PyLinkListIterType);if(iterator==NULL){returnNULL;}Py_INCREF(self);iterator->list=self;iterator->current=self->head;return(PyObject*)iterator;}

迭代器的tp_iternext返回下一个元素的新引用；没有元素时返回NULL且不设置异常，解释器会将其视为StopIteration。

staticPyObject*py_link_list_iter_next(PyLinkListIter*self){LinkListItem*item=self->current;if(item==NULL){returnNULL;}self->current=item->next;Py_INCREF(item->content);returnitem->content;}

迭代器自身在销毁时释放其持有的链表引用：

staticvoidpy_link_list_iter_dealloc(PyLinkListIter*self){Py_XDECREF(self->list);Py_TYPE(self)->tp_free((PyObject*)self);}

6. 注册类型和初始化模块

Python 3 的扩展模块入口必须命名为PyInit_<模块名>，并返回PyObject *。这与 Python 2 的init<模块名>和Py_InitModule3不兼容。

本项目先配置两个类型，再调用PyType_Ready：

PyLinkListType.tp_name="linklist.LinkList";PyLinkListType.tp_basicsize=sizeof(PyLinkList);PyLinkListType.tp_dealloc=(destructor)py_link_list_dealloc;PyLinkListType.tp_flags=Py_TPFLAGS_DEFAULT;PyLinkListType.tp_as_sequence=&py_link_list_as_sequence;PyLinkListType.tp_methods=py_link_list_methods;PyLinkListType.tp_init=(initproc)py_link_list_init;PyLinkListType.tp_new=PyType_GenericNew;PyLinkListType.tp_iter=(getiterfunc)py_link_list_getiter;PyLinkListIterType.tp_name="linklist._LinkListIterator";PyLinkListIterType.tp_basicsize=sizeof(PyLinkListIter);PyLinkListIterType.tp_dealloc=(destructor)py_link_list_iter_dealloc;PyLinkListIterType.tp_flags=Py_TPFLAGS_DEFAULT;PyLinkListIterType.tp_iter=PyObject_SelfIter;PyLinkListIterType.tp_iternext=(iternextfunc)py_link_list_iter_next;

模块初始化函数如下：

PyMODINIT_FUNCPyInit_linklist(void){PyObject*module;if(PyType_Ready(&PyLinkListType)<0||PyType_Ready(&PyLinkListIterType)<0){returnNULL;}module=PyModule_Create(&linklist_module);if(module==NULL){returnNULL;}Py_INCREF(&PyLinkListType);if(PyModule_AddObject(module,"LinkList",(PyObject*)&PyLinkListType)<0){Py_DECREF(&PyLinkListType);Py_DECREF(module);returnNULL;}returnmodule;}

PyModule_AddObject成功后会接管传入引用，因此先对类型对象Py_INCREF；失败时则由当前函数负责释放该引用和模块对象。

7. 测试重点

test.py覆盖了以下行为：

1. append、长度、正负索引和越界IndexError；
2. 两个迭代器分别维护进度；
3. 链表在外部引用消失后仍持有元素；
4. 链表销毁后会释放元素引用。

修改 C-API 代码后，应重新构建并运行测试：

python3 setup.py build_ext--inplacepython3 test.py

总结

一个可靠的 Python C 扩展并不只是“把 C 函数暴露给 Python”。需要同时满足 Python 的对象模型：正确的函数签名、引用计数、新引用/借用引用约定、异常返回方式、析构逻辑和迭代协议。掌握这些基础后，再扩展插入、删除、切片或更复杂的数据结构会更安全。