1. PyListObject
变长对象(数据长度在定义时是不知道的,只能在创建时才能确定)
与字符串对象不同的是支持插入删除操作,运行时动态地调整其维护的内存和元素
与C++中的Vector(动态顺序表,连续的空间)很相似,与list(带头节点的双向循环链表)反而不像
可变对象(改变值内存地址不会发生改变)
1.1 定义
// Include/listobject.h #ifndef Py_LIMITED_API typedef struct {
PyObject_VAR_HEAD /* Vector of pointers to list elements. list[0] is ob_item[0], etc. */ PyObject **ob_item; // 指向元素列表所在的内存块的首地址 /* ob_item contains space for 'allocated' elements. The number * currently in use is ob_size. * Invariants: * 0 <= ob_size <= allocated * len(list) == ob_size * ob_item == NULL implies ob_size == allocated == 0 * list.sort() temporarily sets allocated to -1 to detect mutations. * * Items must normally not be NULL, except during construction when * the list is not yet visible outside the function that builds it. */ Py_ssize_t allocated; // 可容纳的元素的总数 } PyListObject; #endif
讯享网
讯享网#define PyObject_VAR_HEAD PyVarObject ob_base; typedef struct {
PyObject ob_base; Py_ssize_t ob_size; /* Number of items in variable part */ } PyVarObject;
ob_size与allocated是什么关系?
都与内存管理有关系,实际使用的内存数量记录在ob_size中。(类似C++中Vevtor的size与capacity)
PyTypeObject PyList_Type = {
PyVarObject_HEAD_INIT(&PyType_Type, 0) "list", sizeof(PyListObject), 0, (reprfunc)list_repr, /* tp_repr */ 0, /* tp_as_number */ &list_as_sequence, /* tp_as_sequence */ &list_as_mapping, /* tp_as_mapping */ // ....... (initproc)list___init__, /* tp_init */ PyType_GenericAlloc, /* tp_alloc */ PyType_GenericNew, /* tp_new */ PyObject_GC_Del, /* tp_free */ };
1.2 创建PyListObject
Python只提供了唯一的路径创建PyListObject对象
- PyList_New(Py_ssize_t size)
讯享网
PyObject * PyList_New(Py_ssize_t size) { PyListObject *op; #ifdef SHOW_ALLOC_COUNT static int initialized = 0; if (!initialized) { Py_AtExit(show_alloc); initialized = 1; } #endif if (size < 0) { PyErr_BadInternalCall(); return NULL; } // 检查缓冲池中是否有可用对象 // 第一次创建PyListObject对象时,绕过这个机制,直接调用PyObject_GC_New创建对象 // 问题:缓冲池中的对象从哪里来的? if (numfree) { numfree--; op = free_list[numfree]; _Py_NewReference((PyObject *)op); #ifdef SHOW_ALLOC_COUNT count_reuse++; #endif } else { // 两部分:PyListObject+其维护的元素列表的内存首地址 // 通过ob_item建立联系 // 与垃圾回收机制也有关系 op = PyObject_GC_New(PyListObject, &PyList_Type); if (op == NULL) return NULL; #ifdef SHOW_ALLOC_COUNT count_alloc++; #endif } if (size <= 0) op->ob_item = NULL; else { op->ob_item = (PyObject **) PyMem_Calloc(size, sizeof(PyObject *)); if (op->ob_item == NULL) { Py_DECREF(op); return PyErr_NoMemory(); } } Py_SIZE(op) = size; op->allocated = size; _PyObject_GC_TRACK(op); return (PyObject *) op; }

1.3 List的增删改查
本质就是顺序表的增删改查
1.3.1 增加元素
list[3] = "Huamanlou"
讯享网int PyList_SetItem(PyObject *op, Py_ssize_t i, PyObject *newitem) {
PyObject **p; // 类型检查 if (!PyList_Check(op)) {
Py_XDECREF(newitem); PyErr_BadInternalCall(); return -1; } // 索引的有效性检查 if (i < 0 || i >= Py_SIZE(op)) {
Py_XDECREF(newitem); PyErr_SetString(PyExc_IndexError, "list assignment index out of range"); return -1; } // 设置元素 p = ((PyListObject *)op) -> ob_item + i; // 处理“创实际块”为空的情况 Py_XSETREF(*p, newitem); return 0; }
1.3.2 插入元素
list.insert(2, "Huamanlou")
顺序表的元素插入:会移动后面的所有元素
与增加元素的区别:插入元素的动作有可能导致ob_item指向的内存发生变化。
讯享网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; } // 保证有足够内存:(1)不需要重新申请;(2)重新申请 if (list_resize(self, n+1) < 0) return -1; // 确定插入点:Python支持负索引,灵活(但也有代价,得处理负数的情况) if (where < 0) {
where += n; if (where < 0) where = 0; } // 与C++中的Vector的内存管理机制类似 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; }
1.3.3 追加元素append
注意:追加在第ob_szie+1个位置,即list[ob_size] = “py”。
1.3.4 删除元素
一一匹配,等值删除,后面元素一一前移。
static int list_ass_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v) {
// ...... } //
1.4 列表对象缓冲池
缓冲池中的缓冲对象是从哪里来的?
讯享网static void list_dealloc(PyListObject *op) {
Py_ssize_t i; PyObject_GC_UnTrack(op); Py_TRASHCAN_SAFE_BEGIN(op) // 销毁list对象维护的PyObject对象 if (op->ob_item != NULL) {
/* Do it backwards, for Christian Tismer. There's a simple test case where somehow this reduces thrashing when a *very* large list is created and immediately deleted. */ i = Py_SIZE(op); while (--i >= 0) {
Py_XDECREF(op->ob_item[i]); } PyMem_FREE(op->ob_item); } // 销毁list自身,并放进缓冲池 if (numfree < PyList_MAXFREELIST && PyList_CheckExact(op)) free_list[numfree++] = op; else Py_TYPE(op)->tp_free((PyObject *)op); Py_TRASHCAN_SAFE_END(op) }
思考:能不能保留list维护的PyObject对象的内存?
引用计数,类似Py2中大整数对象缓冲池(公用一些内存)。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/131258.html