1.PyListObject
[listobject.h]
typedef struct {
PyObject_VAR_HEAD //其中的obsize记录实际使用内存的对象数量
PyObject **ob_item; //指向列表存储空间中第一个元素地址
int allocated; //一共分配的内存空间对象数量（含未使用），obsize<=allocated
} PyListObject;
2.创建列表对象
首先会对传入的size做检查，其后检查缓冲池是否可用，根据情况创建或服用列表对象。列表对象创建完毕后，根据size大小为元素列表申请合理空间，并初始化。
[listobject.c]
PyObject *
PyList_New(Py_ssize_t size)
{
PyListObject *op;
size_t nbytes;
#ifdef SHOW_ALLOC_COUNT
static int initialized = 0;
if (!initialized) {
Py_AtExit(show_alloc);
initialized = 1;
}
#endif
if (size < 0) { //检查size是否为负数
PyErr_BadInternalCall();
return NULL;
}
if ((size_t)size > PY_SIZE_MAX / sizeof(PyObject *)) //检查size的值是否会导致内存溢出
return PyErr_NoMemory();
nbytes = size * sizeof(PyObject *);//计算创建元素列表所需的空间大小
if (numfree) { //检查list缓冲区是否可用
numfree--;
op = free_list[numfree];
_Py_NewReference((PyObject *)op);
#ifdef SHOW_ALLOC_COUNT
count_reuse++;
#endif
} else { //若缓冲区不可用，则需分配新的内存空间
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_MALLOC(nbytes); //为元素列表申请内存
if (op->ob_item == NULL) {
Py_DECREF(op);
return PyErr_NoMemory();
}
memset(op->ob_item, 0, nbytes);//元素值初始化
}
/*将allocated和ob_size初始化为0*/
Py_SIZE(op) = size;
op->allocated = size;
_PyObject_GC_TRACK(op);
return (PyObject *) op;
}
3.设置列表元素
[listobject.c]
int
PyList_SetItem(register PyObject *op, register Py_ssize_t i,
register PyObject *newitem)
{
register PyObject *olditem;
register 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; //计算待设置索引值
olditem = *p;
*p = newitem;
Py_XDECREF(olditem);
return 0;
}
4.插入元素
当将某对象插入元素时，先判断是否需要resize列表内存，再将待插入位置开始的元素依次向后移动，让出一个空闲位置，再将该位置的值设置为待插入对象
[listobject.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); //返回ins1函数
}
ins1函数:
[listobject.c]
static int
ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
{
Py_ssize_t i, n = Py_SIZE(self); //n就是ob_size
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;
}
if (list_resize(self, n+1) == -1)//调整元素列表空间大小
return -1;
if (where < 0) { //索引为负数时的转换
where += n;
if (where < 0) //当负索引过小（小于|ob_size|）时自动转向0索引处
where = 0;
}
if (where > n)//当索引过大（大于ob_size）时自动转向末尾n
where = n;
items = self->ob_item;
for (i = n; --i >= where; ) //i后边的元素依次向后移位，让出一个空间给v
items[i+1] = items[i];
Py_INCREF(v);
items[where] = v;
return 0;
}
list_resize函数:
[listobject.c]
static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
PyObject **items;
size_t new_allocated;
Py_ssize_t allocated = self->allocated;
/*当newsize大于allocated的一半时不需要重新申请内存*/
if (allocated >= newsize && newsize >= (allocated >> 1)) {
assert(self->ob_item != NULL || newsize == 0);
Py_SIZE(self) = newsize;
return 0;
}
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
/* 检查new_allocated是否会溢出（int） */
if (new_allocated > PY_SIZE_MAX - newsize) {
PyErr_NoMemory();
return -1;
} else {
new_allocated += newsize;
}
if (newsize == 0)
new_allocated = 0;
items = self->ob_item;
if (new_allocated <= (PY_SIZE_MAX / sizeof(PyObject *)))//检查是否会超过最大对象数量
PyMem_RESIZE(items, PyObject *, new_allocated);//进行resize操作
else
items = NULL;
if (items == NULL) {
PyErr_NoMemory();
return -1;
}
self->ob_item = items;
Py_SIZE(self) = newsize;
self->allocated = new_allocated;
return 0;
}
append函数：与插入类似，不过是直接设置在ob_size+1位置处
[listobject.c]
int
PyList_Append(PyObject *op, PyObject *newitem)
{
if (PyList_Check(op) && (newitem != NULL))
return app1((PyListObject *)op, newitem);
PyErr_BadInternalCall();
return -1;
}
static int
app1(PyListObject *self, PyObject *v)
{
Py_ssize_t n = PyList_GET_SIZE(self);
assert (v != NULL);
if (n == PY_SSIZE_T_MAX) {
PyErr_SetString(PyExc_OverflowError,
"cannot add more objects to list");
return -1;
}
if (list_resize(self, n+1) == -1)
return -1;
Py_INCREF(v);
PyList_SET_ITEM(self, n, v);
return 0;c
}
5.删除元素
[listobject.c]
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) {//当匹配相同时返回大于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;
}
list_ass_slice函数原型
static int
list_ass_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)
当v==NULL时，实现的是删除功能
当v!=NULL时，实现的是替换功能
6.列表对象缓冲池
上文中关于列表对象的创建时，已经提及缓冲池free_list的使用，而free_list[]的填充实际上是在某个列表对象删除时加入到free_list中的。具体是先减少其关联的元素列表中每个元素的引用，再释放掉这个元素列表所占用的内存空间，最后将该列表对象加入到free_list中
[listobject.c]
static void
list_dealloc(PyListObject *op)
{
Py_ssize_t i;
PyObject_GC_UnTrack(op);
Py_TRASHCAN_SAFE_BEGIN(op)
if (op->ob_item != NULL) {
i = Py_SIZE(op);
while (--i >= 0) {//逐一减少元素的引用计数
Py_XDECREF(op->ob_item[i]);
}
PyMem_FREE(op->ob_item);//释放掉元素数组
}
if (numfree < PyList_MAXFREELIST && PyList_CheckExact(op))
free_list[numfree++] = op;//加入到缓冲池中
else
Py_TYPE(op)->tp_free((PyObject *)op);
Py_TRASHCAN_SAFE_END(op)
}
[listobject.c]
#define PyList_MAXFREELIST 80
