第一部分 Python内建对象

chapter 0. Python源码剖析——编译Python

Python总体架构

左边是Python提供的大量的模板、库以及用户自定义的模块

右边是Python的运行环境，包括对象/类型系统、内存分配器和运行时状态信息

中间是Python的核心，解释器/虚拟机（箭头表示数据流方向）

Scanner对应词法分析

Parser对应语法分析

Compiler根据建立的AST生成指令集合——Python字节码

Code Evaluator执行字节码，因此它也被称为虚拟机

Python源代码的组织

Include: 包含Python提供的所有头文件

Lib: 包含Python自带的所有标准库，库都是用Python编写的

Modules: 包含所有用C语言编写的模块。它们是那些对速度要求非常严格的模块

Parser: 包含Python解释器的Scanner和Parser部分，及一些有用的工具

Objects: 包含所有Python内建对象，还包括了Python在运行时需要的所有的内部使用对象的实现

Python: 包含Python解释器中的Compiler和执行引擎，是Python运行的核心

PCbuild: 包含VS工程文件，研究Python源代码从这里开始

编译Python

打开工程

Solution -> Properties ->Start Project -> choose "python"

Solution -> Properties ->Configuration Properties -> 删除除了python和pythoncore之外的工程

编译make_buildinfo和make_versioninfo子工程：Project Only -> Rebuild Only xxx

编译Python

修改Python源代码

int PyObject_Print(PyObject *, FILE *, int);
位于object.h中的一个输出对象的接口

一些注意事项

凡是以New结尾的，都以C++中的new操作符视之；凡是以Malloc结尾的，都以C中的malloc操作符视之

chapter 1. Python对象初探

Python内的对象

除了类型对象，Python中所有的内建的类型对象都是被静态初始化的。

Python中万物皆对象，所有对象拥有的相同内容在PyObject中定义，它是整个Python对象机制的核心：
typedef struct _object {
    _PyObject_HEAD_EXTRA
    Py_ssize_t ob_refcnt;
    struct _typeobject *ob_type;
} PyObject; // in object.h of Python 3.4.4

整型变量ob_refcnt与Python的内存管理机制有关，它实现了基于引用计数的垃圾收集机制

变量ob_type指向一个对象类型，提供类型信息

PyObject中定义的内容仅仅是每个Python对象都必须拥有的一部分内容，这些内容将出现在每一个Python对象所占有的内存的最开始的字节中。

PyVarObject表示变长对象：
typedef struct {
    PyObject ob_base;
    Py_ssize_t ob_size; /* Number of items in variable part */
} PyVarObject; // in object.h of Python 3.4.4

变量ob_size指明的是所容纳元素的个数，而不是字节的数量

由于在Python内部，每个对象都拥有相同的对象头部（PyObject），因此只需要用一个PyObject *指针就可以引用任意的一个对象，而不论该对象实际是一个什么对象。

类型对象 _typeobject:
typedef struct _typeobject {
    PyObject_VAR_HEAD
    const char *tp_name; /* For printing, in format "<module>.<name>" */
    Py_ssize_t tp_basicsize, tp_itemsize; /* For allocation */

    /* Methods to implement standard operations */
    destructor tp_dealloc;
    printfunc tp_print;
    ......
    /* More standard operations (here for binary compatibility) */
    hashfunc tp_hash;
    ternaryfunc tp_call;
   ......
} PyTypeObject;

 _typeobject定义中包含4类信息

类型名：tp_name，主要是Python内部以及调试的时候使用

创建该类型对象时分配内存空间大小的信息，即tp_basicsize和tp_itemsize

与该类型对象相关联的操作对象，例如tp_print

将要描述的类型的类型信息

对象的创建

Python C API分类

范型API，或AOL(Abstract Object Layer)：都具有诸如PyObject_***的形式，可以应用在任何Python对象上

与类型相关的API，或COL(Concrete Object Layer)：通常只能作用在某一种类型的对象上，对于每一种内建对象，Python都提供了这样的一组API

对于用户自定义的类型A，Python会通过A所对应的类型对象创建实例对象

基类object：在Python内部对应PyBaseObject_Type

对象的行为

PyTypeObject中定义了大量的函数指针，这些函数指针最终都会指向某个函数，或指向NULL

有三种重要的操作族，在PyTypeObject中，是tp_as_number, tp_as_sequence, tp_as_mapping。它们分别指向PyNumberMethods（定义作为一个数值对象应该支持的操作）, PySequenceMethods（定义作为一个序列对象应该支持的行为）和PyMappingMethods（定义作为一个关联对象应该支持的行为）函数族

类型的类型：PyType_Type
PyTypeObject PyType_Type = {
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    "type", /* tp_name */
    sizeof(PyHeapTypeObject), /* tp_basicsize */
    sizeof(PyMemberDef), /* tp_itemsize */
    ......
};

所有用户自定义class所对应的PyTypeObject对象都是通过PyType_Type创建的。它们的关系可以从下面看出：
A.__class__ # output: <type 'type'>
int.__class__ # output: <type 'type'>
type.__class__ # output: <type 'type'>
这里，<type 'type'>就是Python 内部的PyType_Type，它是所有class的class，因此在Python中被称为metaclass（元类）

#ifdef Py_TRACE_REFS
        #define _PyObject_EXTRA_INIT 0, 0,
#else
        #define _PyObject_EXTRA_INIT
#endif

#define PyObject_HEAD_INIT(type)
    { _PyObject_EXTRA_INIT
    1, type },

从中可以看到，其实PyType_Type也是以PyObject作为头的一个对象，其中，PyObject.ob_refcnt=1, PyObject.ob_type="type"

Python对象的多态性：
在Python中创建一个对象，例如PyIntObject对象时，会分配内存，进行初始化。然后Python内会用一个PyObject *变量，而不是通过一个PyIntObject *变量来保存和维护这个对象。因此在Python内部各个函数之间传递的都是一个范型指针——PyObject *。这个指针所指对象的类型只能从指针所指对象的ob_type域动态进行判断。正是通过这个域，Python实现了多态机制

引用计数

Python垃圾收集机制的一部分

Python通过对一个对象的引用计数（ob_refcnt变量）的管理来维护对象在内存中的存在与否。

在Python中，主要通过Py_INCREF(op)和Py_DECREF(op)两个宏来增加和减少一个对象的引用计数的。当一个对象的引用计数减少到0之后，Py_DECREF将调用该对象的析构函数（通过对象对应类型对象中定义的一个函数指针，即tp_dealloc来指定）来释放该对象所占内存和系统资源

PyObject中的ob_refcnt是一个32位的整型变量，这蕴含Python的一个假设，即对一个对象的引用不会超过一个整型变量的最大值。

类型对象是超越引用计数规则的，它永远都不会被析构。每个对象中指向类型对象的指针不被视为对类型对象的引用

每个对象创建时，Python提供了一个_Py_NewReference(op)宏来将对象的引用计数初始化为1

Python对象的分类

Fundamental对象：类型对象

Numeric对象：数值对象

Sequence对象：容纳其他对象的序列集合对象

Mapping对象：类似于C++中map的关联对象

Internal对象：Python虚拟机在运行时内部使用的对象

chapter 2. Python中的整数对象
注：所有c代码均来自Python-2.7.10Includeintobject.h/c

初识PyIntObject对象：
typedef struct {
    PyObject_HEAD
    long ob_ival;
} PyIntObject; // in Python-2.7.10Includeintobject.h

整数对象池：以应对系统堆面临着的堆整数对象狂风骤雨般的访问

PyIntObject的类型对象是PyInt_Type：
PyTypeObject PyInt_Type = {
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    "int",
    sizeof(PyIntObject),
    0,
    (destructor)int_dealloc, /* tp_dealloc PyIntObject对象的析构操作*/
    (printfunc)int_print, /* tp_print 打印PyIntObject对象*/
    0, /* tp_getattr */
    0, /* tp_setattr */
    (cmpfunc)int_compare, /* tp_compare 比较操作*/
    (reprfunc)int_to_decimal_string, /* tp_repr 转化成PyStringObject对象*/
    &int_as_number, /* tp_as_number 数值操作集合*/
    0, /* tp_as_sequence */
    0, /* tp_as_mapping */
    (hashfunc)int_hash, /* tp_hash 获得HASH值*/
    0, /* tp_call */
    (reprfunc)int_to_decimal_string, /* tp_str */
    PyObject_GenericGetAttr, /* tp_getattro */
    0, /* tp_setattro */
    0, /* tp_as_buffer */
    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_CHECKTYPES |
        Py_TPFLAGS_BASETYPE | Py_TPFLAGS_INT_SUBCLASS, /* tp_flags */
    int_doc, /* tp_doc 对象的文档信息*/
    0, /* tp_traverse */
    0, /* tp_clear */
    0, /* tp_richcompare */
    0, /* tp_weaklistoffset */
    0, /* tp_iter */
    0, /* tp_iternext */
    int_methods, /* tp_methods 成员函数集合*/
    0, /* tp_members */
    int_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 */
    int_new, /* tp_new */
    (freefunc)int_free, /* tp_free PyIntObject对象的释放操作*/
};

Python实现中，对某些会频繁执行的代码，会同时提供函数和宏两种版本，因此需要在安全性和效率之间权衡使用

static PyObject *
int_add(PyIntObject *v, PyIntObject *w) //加法操作
{
    register long a, b, x;
    CONVERT_TO_LONG(v, a);
    CONVERT_TO_LONG(w, b);
    /* 检查加法结果是否溢出，溢出则返回PyLongObject对象上的加法，否则返回根据结果新建的一个PyIntObject */
    x = (long)((unsigned long)a + b);
    if ((x^a) >= 0 || (x^b) >= 0)
        return PyInt_FromLong(x);
    return PyLong_Type.tp_as_number->nb_add((PyObject *)v, (PyObject *)w);
}

从其加法操作可以清晰看出，PyIntObject确实是一个immutable对象。因为操作完成后，原来参与操作的任何一个对象都没有发生改变，取而代之的是一个全新的PyIntObject对象

在Python中，可以通过对象的__doc__属性看到int_doc所维护的文档

PyIntObject对象的创建和维护

对象创建的3种途经

PyObject * PyInt_FromLong(long ival); //从long值生成

PyObject * PyInt_FromString(char *s, char **pend, int base);
// 从字符串生成

PyObject * PyInt_FromUnicode(Py_UNICODE *s, Py_ssize_t length, int base);
// 从Py_UNICODE对象生成

小整数对象

由于PyIntObject对象是不可变对象，所以对象池里的每一个PyIntObject对象都能够被任意地共享

#ifndef NSMALLPOSINTS
        #define NSMALLPOSINTS 257
#endif
#ifndef NSMALLNEGINTS
        #define NSMALLNEGINTS 5
#endif
#if NSMALLNEGINTS + NSMALLPOSINTS > 0
        /* 小整数对象的对象池 */
        /* 默认小整数集合的范围为[-5,257)。可以通过修改NSMALLPOSINTS和NSMALLNEGINTS并重新编译Python以将此范围向两端伸展或收缩*/
        static PyIntObject *small_ints[NSMALLNEGINTS + NSMALLPOSINTS];
#endif

对于小整数对象，Python直接将这些整数对应的PyIntObject缓存在内存中，并将其指针存放在small_ints里。对于其他整数，Python运行环境提供一块内存空间，这些内存空间由这些大整数轮流使用

大整数对象

#define BLOCK_SIZE 1000 /* 1K less typical malloc overhead */
#define BHEAD_SIZE 8 /* Enough for a 64-bit pointer */
#define N_INTOBJECTS ((BLOCK_SIZE - BHEAD_SIZE) / sizeof(PyIntObject))

struct _intblock {
    struct _intblock *next;
    PyIntObject objects[N_INTOBJECTS]; //用于存储被缓存的PyIntObject对象的内存
};
typedef struct _intblock PyIntBlock;

static PyIntBlock *block_list = NULL; //实现了一个单向列表
static PyIntObject *free_list = NULL;
//Python使用一个单向链表管理全部block的objects中所有空闲内存，这个自由内存链表的表头就是free_list

添加和删除

PyIntObject对象的创建

若小整数对象池机制被激活（NSMALLNEGINTS + NSMALLPOSINTS > 0），则尝试使用小整数对象池：判断传入的long值是否属于小整数范围，若是则只需返回在小整数对象池中对应的对象即可

若不能使用小整数对象池，则使用(block_list维护的)通用的整数对象池：首次调用PyInt_FromLong时，由于free_list必为NULL，因此会调用fill_free_list以创建新的block。

注意，只要所有block的空闲内存被使用完了，从而导致free_list变为NULL，那么在下一次PyInt_FromLong调用时就会激发对fill_free_list的调用

static PyIntObject * fill_free_list(void) //申请新的block
{
    PyIntObject *p, *q;
    /* 申请一个新的PyIntBlock结构p，并链接p到已有的block_list中 */
    p = (PyIntObject *) PyMem_MALLOC(sizeof(PyIntBlock));
    if (p == NULL) return (PyIntObject *) PyErr_NoMemory();
    ((PyIntBlock *)p)->next = block_list;
    block_list = (PyIntBlock *)p;
    /* 将PyIntBlock中的PyIntObject数组objects转变成单向链表 */
    p = &((PyIntBlock *)p)->objects[0];
    q = p + N_INTOBJECTS;
    while (--q > p) //使用PyObject中的ob_type指针作为连接指针组成单向链表
        Py_TYPE(q) = (struct _typeobject *)(q-1);
    Py_TYPE(q) = NULL;
    return p + N_INTOBJECTS - 1;
}

使用通用整数对象池

不同PyIntBlock对象的objects中的空闲内存块是被链接在一起的（发生那个在一个PyIntObject对象被销毁的时候），形成了一个单向链表，指向表头的指针就是free_list

PyIntObject对象的tp_dealloc：
static void int_dealloc(PyIntObject *v)
{
    if (PyInt_CheckExact(v)) {//将对象链入free_list所维护的自由内存链表中
        Py_TYPE(v) = (struct _typeobject *)free_list;
        free_list = v;
    }
    else //若删除的对象是一个整数的派生类对象，那么不做任何操作
        Py_TYPE(v)->tp_free((PyObject *)v); //只是简单调用派生类型中指定的tp_free
}

在int_dealloc中，永远不会向系统堆交还任何内存。一旦系统堆中的某块内存被Python申请用于整数对象，那么这块内存在Python结束之前，永远不会被释放。（可以利用这个漏洞将系统内存全部吃光）

小整数对象池的初始化：
int _PyInt_Init(void)
{
    PyIntObject *v;
    int ival;
#if NSMALLNEGINTS + NSMALLPOSINTS > 0
    for (ival = -NSMALLNEGINTS; ival < NSMALLPOSINTS; ival++) {
          if (!free_list && (free_list = fill_free_list()) == NULL)
                    return 0;
        /* 内联(inline)PyObject_New的行为 */
        v = free_list;
        free_list = (PyIntObject *)Py_TYPE(v);
        PyObject_INIT(v, &PyInt_Type);
        v->ob_ival = ival;
        small_ints[ival + NSMALLNEGINTS] = v;
    }
#endif
    return 1;
}

小整数对象也是生存在由block_list所维护的内存上的

Hack PyIntObject

chapter 3. Python中的字符串对象
注：所有c代码均来自Python-2.7.10Includestringobject.h或Python-2.7.10Objectsstringobject.c

PyStringObject与PyString_Type

Python 3中没有PyStringObject对象

typedef struct {
    PyObject_VAR_HEAD
    long ob_shash; //缓存该对象的hash值，初始值是-1
    int ob_sstate; //标记对象是否已经过intern机制的处理
        /*作为一个字符指针指向一段内存，长度为ob_size+1个字节
        必须满足ob_sval[ob_size]==''*/
    char ob_sval[1];
} PyStringObject; // in Python-2.7.10Includestringobject.h

PyStringObject对应的类型对象：
PyTypeObject PyString_Type = {
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    "str",
    PyStringObject_SIZE,
    sizeof(char), /* tp_itemsize 指明由变长对象保存的元素(item)的单位长度。与ob_size共同决定了应该额外申请的内存总大小*/
    ......
    string_repr, /* tp_repr */
    &string_as_number, /* tp_as_number 支持数值操作*/
    &string_as_sequence, /* tp_as_sequence 支持序列操作*/
    &string_as_mapping, /* tp_as_mapping 支持映射操作*/
    (hashfunc)string_hash, /* tp_hash */
    0, /* tp_call */
   ......
    string_new, /* tp_new */
    PyObject_Del, /* tp_free */
};

创建PyStringObject对象（两种方法）

PyObject * PyString_FromString(const char *str)
{/*传入的参数必须是以''结尾的字符数组的指针*/
    register size_t size;
    register PyStringObject *op;
        /*判断字符串长度*/
    assert(str != NULL);
    size = strlen(str);
    if (size > PY_SSIZE_T_MAX - PyStringObject_SIZE) {
        PyErr_SetString(PyExc_OverflowError,
            "string is too long for a Python string");
        return NULL;
    }
    if (size == 0 && (op = nullstring) != NULL) {
#ifdef COUNT_ALLOCS
        null_strings++;
#endif
        Py_INCREF(op);
        return (PyObject *)op;
    } /*处理null string*/
    if (size == 1 && (op = characters[*str & UCHAR_MAX]) != NULL) {
#ifdef COUNT_ALLOCS
        one_strings++;
#endif
        Py_INCREF(op);
        return (PyObject *)op;
    } /*处理字符*/
        /*创建新的PyStringObject对象并初始化*/
    /* Inline PyObject_NewVar */
    op = (PyStringObject *)PyObject_MALLOC(PyStringObject_SIZE + size);
    if (op == NULL)
        return PyErr_NoMemory();
    PyObject_INIT_VAR(op, &PyString_Type, size);
    op->ob_shash = -1;
    op->ob_sstate = SSTATE_NOT_INTERNED;
    Py_MEMCPY(op->ob_sval, str, size+1);
    ......
    return (PyObject *) op;
}

PyObject * PyString_FromStringAndSize(const char *str, Py_ssize_t size)
{/*不要求传入的参数必须是以''结尾的字符数组的指针*/
    register PyStringObject *op;
    if (size < 0) {
        PyErr_SetString(PyExc_SystemError,
            "Negative size passed to PyString_FromStringAndSize");
        return NULL;
    }
    if (size == 0 && (op = nullstring) != NULL) {/*处理null string*/
#ifdef COUNT_ALLOCS
        null_strings++;
#endif
        Py_INCREF(op);
        return (PyObject *)op;
    }
    if (size == 1 && str != NULL &&
        (op = characters[*str & UCHAR_MAX]) != NULL) {/*处理字符*/
#ifdef COUNT_ALLOCS
        one_strings++;
#endif
        Py_INCREF(op);
        return (PyObject *)op;
    }
        .........
        /*创建新的PyStringObject对象并初始化*/
    /* Inline PyObject_NewVar */
    op = (PyStringObject *)PyObject_MALLOC(PyStringObject_SIZE + size);
    if (op == NULL)
        return PyErr_NoMemory();
    PyObject_INIT_VAR(op, &PyString_Type, size);
    op->ob_shash = -1;
    op->ob_sstate = SSTATE_NOT_INTERNED;
    if (str != NULL)
        Py_MEMCPY(op->ob_sval, str, size);
    op->ob_sval[size] = '';
    .........
    return (PyObject *) op;
}

字符串对象的intern机制

当字符数组的长度为0或1时，都会调用PyString_InternInPlace，这个就是其intern机制
void PyString_InternInPlace(PyObject **p)
{
    register PyStringObject *s = (PyStringObject *)(*p);
    PyObject *t;
    .......
        /*对PyStringObject进行类型和状态检查*/
    if (!PyString_CheckExact(s)) /*intern机制只能作用在PyStringObject对象上*/
        return;
    if (PyString_CHECK_INTERNED(s))
        return; /*不会对同一个PyStringObject对象进行一次以上的intern操作*/
    if (interned == NULL) {
        interned = PyDict_New();
        if (interned == NULL) {
            PyErr_Clear(); /* Don't leave an exception */
            return;
        }
    } /*创建记录经intern机制处理后的PyStringObject的dict*/
        /*检查PyStringObject对象s是否存在对应的intern后的PyStringObject对象*/
    t = PyDict_GetItem(interned, (PyObject *)s);
    if (t) {
        Py_INCREF(t); /*对引用计数进行调整*/
        Py_DECREF(*p);
        *p = t;
        return;
    }
        /*在interned中记录检查PyStringObject对象s*/
    if (PyDict_SetItem(interned, (PyObject *)s, (PyObject *)s) < 0) {
        PyErr_Clear();
        return;
    }
   /*对引用计数进行调整（interned中的指针不能作为a的有效引用）*/
    Py_REFCNT(s) -= 2;
        /*调整s中的intern状态标志*/
    PyString_CHECK_INTERNED(s) = SSTATE_INTERNED_MORTAL;
}

intern机制的关键：系统中有一个键值对映射关系的集合interned。这个集合中记录着被intern机制处理过的PyStringObject对象。党对一个PyStringObject对象a应用intern机制时，先会在interned这个dict中检查是否有满足以下条件的对象b：b中维护的原生字符串与a相同。若存在，那么指向a的PyObject指针将会指向b，而a的引用计数减1；若不存在，那么就将a记录到interned中

在销毁a的同时，会在interned中删除指向a的指针

PyStringObject对象的intern机制目的是：对于被intern之后的字符串，在整个Python运行期间，系统中都只有唯一的一个与该字符串对应的PyStringObject对象。这样，当判断两个PyStringObject对象是否相同时，若它们都被intern了，那么只需简单地检查它们对应的PyObject *是否相同即可

如果对于PyStringObject对象a应用了intern机制，那么之后要创建PyStringObject对象b时，Python会首先在系统中记录的已经被intern机制处理了的PyStringObject对象中查找，若发现该字符数组对应的PyStringObject对象已存在，那么就将该对象的引用返回，而不重新创建一个PyStringObject对象

被intern机制处理后的PyStringObject对象分为两类：
1. 处于SSTATE_INTERNED_IMMORTAL状态。该状态的PyStringObject对象是永远不会被销毁的，它与Python虚拟机一起死掉
2. 处于SSTATE_INTERNED_MORTAL状态。PyString_InternInPlace只能创建这种状态的PyStringObject对象。

字符缓冲池:
static PyStringObject *characters[UCHAR_MAX + 1];

字符串对象体系中的字符缓冲池是以静态变量的形式存在着的，在Python初始化完成之后，缓冲池中的所有PyStringObject指针都为空

字符串连接引起的效率问题（据闻地球人都知道的问题，但是我不知道，所以我不是地球人？！噢，请叫我E教授）

原因：PyStringObject对象是一个不可变对象，因此在进行字符串连接时，必须要创建一个新的PyStringObject对象。这样，若要连接N个PyStringObject对象，那么就必须进行N-1次内存申请及内存搬运工作。

通过“+”操作符对字符串进行连接时，会调用：
static PyObject * string_concat(register PyStringObject *a, register PyObject *bb)
{
    register Py_ssize_t size;
    register PyStringObject *op;
   ......
    size = Py_SIZE(a) + Py_SIZE(b); /*计算字符串连接后的长度size*/
   .......
/*创建新的PyStringObject对象，其维护的用于存储字符的内存长度为size*/
    op = (PyStringObject *)PyObject_MALLOC(PyStringObject_SIZE + size);
    if (op == NULL)
        return PyErr_NoMemory();
    PyObject_INIT_VAR(op, &PyString_Type, size);
    op->ob_shash = -1;
    op->ob_sstate = SSTATE_NOT_INTERNED;
/*将a和b中的字符拷贝到新创建的PyStringObject中*/
    Py_MEMCPY(op->ob_sval, a->ob_sval, Py_SIZE(a));
    Py_MEMCPY(op->ob_sval + Py_SIZE(a), b->ob_sval, Py_SIZE(b));
    op->ob_sval[size] = '';
    return (PyObject *) op;
#undef b
}

官方推荐做法：利用PyStringObject对象的join操作来存储在list或tuple中的一组PyStringObject对象连接操作。（这种做法只需分配一次内存）

利用PyStringObject对象的join操作，会进行如下动作：
static PyObject * string_join(PyStringObject *self, PyObject *orig)
{
    char *sep = PyString_AS_STRING(self);
/*假设调用"abc".join(list)，那么self就是"abc"对应的PyStringObject对象*/
/*所以，seplen中存储这个“abc”的长度*/
    const Py_ssize_t seplen = PyString_GET_SIZE(self);
    PyObject *res = NULL;
    char *p;
    Py_ssize_t seqlen = 0;
    size_t sz = 0;
    Py_ssize_t i;
    PyObject *seq, *item;
        ......
/*获得list中PyStringObject对象的个数，保存在seqlen中*/
/*遍历list中的每个字符串，累加获得连接list中所有字符串后的长度*/
    for (i = 0; i < seqlen; i++) {
        const size_t old_sz = sz;
                /*seq为Python中的list对象，这里获得其中第i个字符串*/
        item = PySequence_Fast_GET_ITEM(seq, i);
        ......
        sz += PyString_GET_SIZE(item);
        if (i != 0)
            sz += seplen;
        ......
    }
    /* 创建长度为sz的PyStringObject对象 */
    res = PyString_FromStringAndSize((char*)NULL, sz);
    .....
    /* 将list中的字符串拷贝到新创建的PyStringObject对象中 */
    p = PyString_AS_STRING(res);
    for (i = 0; i < seqlen; ++i) {
        size_t n;
        item = PySequence_Fast_GET_ITEM(seq, i);
        n = PyString_GET_SIZE(item);
        Py_MEMCPY(p, PyString_AS_STRING(item), n);
        p += n;
        if (i < seqlen - 1) {
            Py_MEMCPY(p, sep, seplen);
            p += seplen;
        }
    }
    Py_DECREF(seq);
    return res;
}

Hack PyStringObject

在string_length中增加操作以查看intern机制

chapter 4. Python中的List对象
注：所有c代码均来自Python-2.7.10Includelistobject.h或Python-2.7.10Objectslistobject.c

PyListObject对象

可以将Python中的PyListObject看成vector<PyObject*>

typedef struct {
    PyObject_VAR_HEAD
    /* ob_item为指向元素列表的指针，实际上，Python中的list[0]就是ob_item[0] */
    PyObject **ob_item;
        /*维护当前列表中可容纳的元素总数*/
    Py_ssize_t allocated;
} PyListObject;

申请的总内存大小记录在allocated中，其中实际被使用了的内存数量则记录在了ob_size中。即：
0 <= ob_size <= allocated
len(list) == ob_size
ob_item == NULL 意味着ob_size == allocated == 0

PyListObject对象的创建与维护

PyObject * PyList_New(Py_ssize_t size) /*size是列表初始元素个数*/
{
    PyListObject *op;
    size_t nbytes;
.....
/*内存数量计算*/
    nbytes = size * sizeof(PyObject *);
/*为PyListObject对象申请空间*/
    if (numfree) {
        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
    }
/*为PyListObject对象中维护的元素列表申请空间*/
    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);
    }
    Py_SIZE(op) = size;
    op->allocated = size;
    _PyObject_GC_TRACK(op);
    return (PyObject *) op;
}

默认情况下，free_list中最多会维护80个PyListObject对象：
#ifndef PyList_MAXFREELIST
        #define PyList_MAXFREELIST 80
#endif
static PyListObject *free_list[PyList_MAXFREELIST];

设置元素（不会导致ob_item指向的内存发生变化）list[i]=xx：
int PyList_SetItem(register PyObject *op, register Py_ssize_t i,
               register PyObject *newitem)
/*会先进行索引检查，然后再设置元素*/

插入元素（有可能使得ob_item指向的内存发生变化）list.insert：
int PyList_Insert(PyObject *op, Py_ssize_t where, PyObject *newitem)
/*类型检查，然后调用ins1*/
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) == -1)
        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; //插入元素v
    return 0;
}

static int list_resize(PyListObject *self, Py_ssize_t newsize)
//判断需不需要重新申请内存
        1. newsize < allocated && newsize > allocated/2：简单调整ob_size值
        2. 其他情况，调用realloc，重新分配空间
//计算重新申请的内存大小
//扩展列表

另一种插入操作list.append（添加的元素是添加在第ob_size+1个位置上的）：
int PyList_Append(PyObject *op, PyObject *newitem)
/*类型检查后，调用app1*/
static int app1(PyListObject *self, PyObject *v)
/*list_resize后，设置值*/

删除操作list.remove：
static PyObject *
listremove(PyListObject *self, PyObject *v)
{
    Py_ssize_t i;
        /*比较list中的元素与待删除的元素v*/
    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;
}

比较操作：PyObject_RichCompareBool
返回值大于0，则表示两者匹配

static int
list_ass_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)
/*
1. a[ilow:ihigh] = v if v != NULL 替换
2. del a[ilow:ihigh] if v == NULL 删除（通过memmove简单地搬移内存来实现）
*/

PyListObject对象缓冲池free_lists

在一个PyListObject被销毁的过程中（ list_dealloc），获得/创建free_lists中所缓冲的PyListObject

static void list_dealloc(PyListObject *op)
{
    Py_ssize_t i;
    ....
/*销毁PyListObject对象维护的元素列表*/
    if (op->ob_item != NULL) {
        i = Py_SIZE(op);
        while (--i >= 0) {
            Py_XDECREF(op->ob_item[i]);
        }
        PyMem_FREE(op->ob_item);
    }
/*释放PyListObject自身*/
/*检查缓存池缓存的PyListObject数量是否已满，若未满，则将要删除的PyListObject对象放到缓冲池中，以备后用*/
    if (numfree < PyList_MAXFREELIST && PyList_CheckExact(op))
        free_list[numfree++] = op;
    else
        Py_TYPE(op)->tp_free((PyObject *)op);
    Py_TRASHCAN_SAFE_END(op)
}

也就是说，Python启动时空荡荡的缓冲池是由本应该死掉的PyListObject对象给填充了，在以后创建新的PyListObject时，Python会首先唤醒这些已死掉的PyListObject，给它们“重新做人”的机会
注意：这里缓冲的仅仅是PyListObject对象，而没有这个对象曾经拥有的PyObject *元素列表

Hack PyListObject

查看allocated和ob_size的值以观察PyListObject对象的内存管理机制

观察PyListObject对象的创建和删除对于Python维护的PyListObject对象缓冲池的影响

chapter 5. Python中的Dict对象
注：所有c代码均来自Python-2.7.10Includedictobject.h或Python-2.7.10Objectsdictobject.c

散列表概述

用于映射的函数称为散列函数，而映射后的值称为元素的散列值

装载率：与散列冲突相关的概念，指的是散列表中已使用空间和总空间的比值

解决散列冲突：开放定址法。当产生散列冲突时，Python会通过一个二次探测函数f，计算下一个候选位置addr，若位置addr可用，则可将待插入元素放到位置addr；若位置addr不可用，则Python会再次使用探测函数f，获得下一个候选位置，如此不断探测，总会找到一个可用的位置

为了防止冲突探测链断裂导致的无法搜索，在采用开放定址的冲突解决策略的散列表中，删除某条探测链上的元素时不进行真正的删除（伪删除）

PyDictObject

把关联容器中的一个（键，值）元素对称为一个entry或slot：
typedef struct {
    /* Cached hash code of me_key. Note that hash codes are C longs. */
    Py_ssize_t me_hash;
    PyObject *me_key;
    PyObject *me_value;
} PyDictEntry;

PyDictObject中entry可以在3种状态间转换：unused, active, dummy

当一个entry的me_key和me_value都是NULL时，entry处于unused态。unused态表明目前该entry中并没有存储(key, value)对，而且在此之前，也没有存储过它们。每一个entry在初始化的时候都会处于这种状态，而且只有在unused态下，entry的me_key域才会为NULL

当entry中存储了一个(key,value)对时，entry便转换到了active态。在active态下，me_key和me_value都不能为NULL

当entry中存储的(key, value)对被删除后，为了防止冲突探测链的中断，entry的状态不能直接从active态转为unused态。此时，entry中的me_key将指向dummy对象，从而entry进入dummy态（伪删除）

一个PyDictObject对象是一大堆entry的集合：
#define PyDict_MINSIZE 8
typedef struct _dictobject PyDictObject;
struct _dictobject {
    PyObject_HEAD
    Py_ssize_t ma_fill; /* 元素个数：# Active + # Dummy */
    Py_ssize_t ma_used; /* 元素个数：# Active */
    Py_ssize_t ma_mask;
    PyDictEntry *ma_table;
    PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);
    PyDictEntry ma_smalltable[PyDict_MINSIZE];
};

ma_smalltable：意味着当创建一个PyDictObject对象时，至少有PyDict_MINISIZE个entry被同时创建

ma_table：关联对象的关键所在，它指向一片作为PyDictEntry结合的内存的开始位置。当entry的数量少于PyDict_MINISIZE，ma_table域将指向ma_smalltable，而当超过时，将会让ma_table指向一个重新申请的额外内存空间。因此ma_table总是有效的

ma_mask：记录了一个PyDictObject对象所拥有的entry数量

PyDictObject的创建与维护

PyDictObject对象的创建：
PyObject * PyDict_New(void)
{
    register PyDictObject *mp;
    if (dummy == NULL) { /* 自动创建dummy对象 */
        dummy = PyString_FromString("<dummy key>");
        if (dummy == NULL)
            return NULL;
                ....
    }
    if (numfree) {
       /*使用缓冲池*/
        .....
    } else {/*创建PyDictObject对象
        mp = PyObject_GC_New(PyDictObject, &PyDict_Type);
        if (mp == NULL)
            return NULL;
        EMPTY_TO_MINSIZE(mp);
                ......
    }
    mp->ma_lookup = lookdict_string;
        ......
    return (PyObject *)mp;
}

EMPTY_TO_MINSIZE：将ma_smalltable清零，同时设置ma_size和ma_fill。在一个PyDictObject对象刚被创建时，这两个变量都应该是0

INIT_NONZERO_DICT_SLOT：将ma_table指向ma_smalltable，并设置ma_mask为7

ma_lookup：指定了PyDictObject在entry集合中搜索某一特定entry时需要进行的动作，它包含了散列函数和发生冲突时二次探测函数的具体实现

对新生的PyDictObject对象进行初始化
(EMPTY_TO_MINSIZE：将ma_smalltable清零，同时设置ma_size和ma_fill。在一个PyDictObject对象刚被创建时，这两个变量都应该是0, INIT_NONZERO_DICT_SLOT：将ma_table指向ma_smalltable，并设置ma_mask为7, ma_lookup：指定了PyDictObject在entry集合中搜索某一特定entry时需要进行的动作，它包含了散列函数和发生冲突时二次探测函数的具体实现)

通用搜索策略
static PyDictEntry * lookdict(PyDictObject *mp, PyObject *key, register long hash)
{
    register size_t i;
    register size_t perturb;
    register PyDictEntry *freeslot;
    register size_t mask = (size_t)mp->ma_mask;
    PyDictEntry *ep0 = mp->ma_table;
    register PyDictEntry *ep;
    register int cmp;
    PyObject *startkey;
        /*散列，定位冲突探测链的第一个entry*/
    i = (size_t)hash & mask;
    ep = &ep0[i];
        /*1. entry处于unused态
                2. entry中的key与待搜索的key匹配*/
    if (ep->me_key == NULL || ep->me_key == key)
        return ep;
        /*第一个entry处于dummy态，设置freeslot*/
    if (ep->me_key == dummy)
        freeslot = ep;
    else { /*检查active态entry*/
        if (ep->me_hash == hash) {/*前提：两个对象的hash值相同*/
            startkey = ep->me_key;
            Py_INCREF(startkey);
            cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
            Py_DECREF(startkey);
            if (cmp < 0)
                return NULL;
            if (ep0 == mp->ma_table && ep->me_key == startkey) {
                if (cmp > 0)
                    return ep;
            }
            else {
                return lookdict(mp, key, hash);
            }
        }
        freeslot = NULL;
    }
 for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {//寻找探测链上下一个entry
        i = (i << 2) + i + perturb + 1;
        ep = &ep0[i & mask];
        if (ep->me_key == NULL) //到达unused态entry，搜索失败
            return freeslot == NULL ? ep : freeslot;
        if (ep->me_key == key) //检查“引用相同”是否成立
            return ep;
        if (ep->me_hash == hash && ep->me_key != dummy) {//检查“值相同”是否成立
            startkey = ep->me_key;
            Py_INCREF(startkey);
            cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
            Py_DECREF(startkey);
            if (cmp < 0)
                return NULL;
            if (ep0 == mp->ma_table && ep->me_key == startkey) {
                if (cmp > 0)
                    return ep;
            }
            else {
                return lookdict(mp, key, hash);
            }
        }
        else if (ep->me_key == dummy && freeslot == NULL)/* 设置freeslot*/
            freeslot = ep;
    }
    return 0;
}

直接将hash值与entry的数量做一个与操作，使得结果落在entry的数量之下

如果在PyDictObject中搜索不到待查找的key，会返回一个me_value为NULL的entry。表示搜索失败，而返回的entry是一个空闲的entry

freeslot用来指向探测序列中第一个处于dummy态的entry

另一个搜索策略：lookdict_string。它是lookdict的一种针对PyStringObject对象的特殊形式，是PyDictObject创建时所默认采用的搜索策略。只要待搜索的key是PyStringObject对象，就会采用这种策略进行搜索

Python的dict中相同包含：
1. 引用相同：两个符号引用的是内存中的同一个地址
2. 值相同：在内存中不同位置，但是对象的值相同

总结下lookdict中进行第一次检查时所进行的主要动作：
1. 根据hash值获得entry的索引，这是冲突检测链上第一个entry索引
2. 在下面两种情况下，搜索结束
        - entry处于unused态，表明冲突检测搜索完成，搜索失败
        - ep->me_key == key，表明entry的key与待搜索的key匹配
3. 若当前entry处于dummy态，设置freeslot
4. 检查active态entry中的key与待查找的key是否“值相同”，若成立，搜索成功

lookdict中对探测链上其他entry进行的操作：
5. 根据python所采用的探测函数，获得探测链中的下一个待检查的entry
6. 检查到一个unused态entry，表明搜索失败，此时有两种结果：
        - 若freeslot不为空，则返回freeslot所指entry
        - 若freeslot为空，则返回该unused态entry
7. 检查entry中的key与待查找的key是否符合“引用相同”规则
8. 检查entry中的key与待查找的key是否符合“值相同”规则
9. 在遍历过程中，若发现dummy态entry，且freeslot未设置，则设置freeslot

插入（PyDict_SetItem）：
1. 计算hash值：PyObject_Hash
2. 插入(key, value)元素对（insertdict）
        - 搜索成功，返回处于active的entry，直接替换me_value
        - 搜索失败，返回unused或dummy的entry，完整设置me_key, me_hash和me_value
3. 必要时调整dict的内存空间（table的装载率是否大于或等于2/3，以及在insertdict中是否使用了一个处于unused态或dummy态entry）：
        1. 若一个PyDictObject对象的table中只有几个entry处于active态，而大多数entry都处于dummy态，那么改变table大小的结果则是减小table的空间大小
        2. (mp->ma_used > 50000 ? 2 : 4)：通常新的table大小的选用策略是新的table中entry的数量是现在table中active态entry数量的4倍。但是当table中active态的entry数量非常大（>50000）时，python只会要求2倍空间
        3. 改变table大小：static int dictresize(PyDictObject *mp, Py_ssize_t minused)
                1）首先确定新的table的大小，这个大小一定要大于传入参数minused。dictresize从8开始，以指数方式增加大小，直到超过了minused为止
                2）若获得的新table大小为8，则不需要在堆上分配空间，直接使用ma_smalltable即可；否则，则需要在堆上分配空间
                3）对新的table初始化，并调整原来PyDictObject对象中用于维护table使用情况的变量
                4）对原来table中的非unused态entry进行处理。对于active态entry，要将其插入到新的table中；对于dummy态的entry，则丢弃
                5）若之前旧的table指向了一片系统堆中当内存空间，那还需要释放这片内存空间，防止内存泄露

删除（PyDict_DelItem）：
1. 计算hash值
2. 搜索相应的entry。若搜索失败，即entry不存在，返回-1
3. 删除entry所维护的元素，将entry从active态变换为dummy态，同时调整PyDictObject对象中维护table使用情况的变量

PyDictObject对象缓冲池(Python 2.7.10)：
#ifndef PyDict_MAXFREELIST
        #define PyDict_MAXFREELIST 80
#endif
static PyDictObject *free_list[PyDict_MAXFREELIST];
static int numfree = 0;

初始阶段，缓冲池内什么都没有，直到第一个PyDictObject被销毁时（dict_dealloc），这个缓冲池才开始接纳被缓冲的PyDictObject对象

static void dict_dealloc(register PyDictObject *mp)
1. 调整dict中对象的引用计数
2. 释放从系统堆中申请的内存空间
3. 若缓冲池未满，则将被销毁的PyDictObject对象放入缓冲池中；若缓冲池已满，则直接销毁

在创建新的PyDictObject对象时，若在缓冲池中有可以使用的对象，则直接从缓冲池中取出使用，而不需要再重新创建

Hack PyDictObject