面向指针编程（一）
面向对象编程，面向设计模式编程（亦即设计模式），面向接口编程，面向模板编程（亦即泛型编程），面向函数编程（亦即函数式编程），面向多核时代的并行编程，面向大数据的机器学习编程……这么多年，大家要面向的东西已经够多了，然而我看到的现象是，很多编程语言让大家面向 xxx 的同时在竭力回避指针。我可不想面向这么多东西，所以我只好加入指针的黑暗势力。我要不自量力的来写一篇《面向指针编程》作为投名状，借以表示我与软件世界的光明势力的彻底决裂。
这个世界上，提供指针的编程语言很少，这样的语言有汇编语言、C/C++ 以及 Pascal 等。Pascal 我没学过。汇编语言过于黑暗，我现在功力还不足以驾驭它。C++，我觉得它简直是黑暗势力中的败类——它试图挣脱指针，走向光明，结果却出了一堆幺蛾子。所以我还是俗套的选 C 语言来阐述指针的黑暗力量。
阅读本文之前，请读三遍无名师说的话：当尊者 Ritchie 发明 C 时，他将程序员放到缓冲溢出、堆损坏和烂指针 bug 的地狱中惩罚。然后自我安慰一下，如果地狱未能使我屈服，那么我会比地狱更黑暗更强大。
指针是什么？
内存是以字节为单位的一个很大但是又经常不够用的空间。指针是内存中 x 个连续的字节中存储的数据——在 32 位的机器上，x 的值为 4；在 64 位机器上，x 值为 8。为了叙述的简便，本文只在 64 位的机器上谈论指针。
指针是一种数据，这没什么稀奇的。从机器的角度来看，程序的一切是存放在数组中的数据。只有那些自作多情的程序猿才会像亚里士多德一样自作多情的认为程序是由对象 + 方法或者许多函数复合而成的。事实上，从最远离机器的 Lisp 语言的角度来看，程序的一切也都是数据，存放在表中的数据。如果忽视程序本身就是数据这个客观事实，程序猿们很容易就走上了形而上学的道路，然后他们会度过漫长的、罪恶的、痛苦的中世纪，膜拜着一个又一个神棍，当然期间也出现了几位圣·奥古斯丁。
那么，指针中存储着什么数据？内存地址。
内存是以字节为单位的空间，其中每个字节都伴随着一个地址，这个地址机器赋予的，并不是我们的程序编制的。你可以将整个内存空间想象成一栋大楼，将字节想象为大楼中每个房间，将每个字节的地址想象为房间的门牌号，于是指针中存储的数据就类似于门牌号。
如果你从未学过 C 语言，读到此处可能会问，我们为什么要在内存中存储内存地址？不知你是否住过宾馆。在正规的宾馆里，每个房间的门后都会贴着逃生路线图，图中『存储』了该宾馆与你的房间同一楼层内的全部房间的门牌号以及它们的布局。如果你住酒店时从来也不看逃生路线图，那么从现在开始，入住酒店后第一件事就是认真的看一下它，关键时刻它能救你一命。在内存中存储内存地址，虽然不是救你性命的，但是可以藉此构造与宾馆逃生路线图相似的抽象事物——内存数据的抽象与复合。
有兴趣可以加群一起交流，群号在我主页之中有介绍
内存空间的有名与无名
现在来看两行 C 代码：
int foo = 10;
int *bar = &foo;
foo 是什么？foo 表示一个内存地址。foo 前面的 int 是数据类型修饰，它表示 foo 是内存中 4 个连续字节的首字节地址（ 64 位机器上，int 类型的数据长度为 4 个字节）。C 编译器总是会根据某个内存地址相应的类型来确定以该内存地址起始的一段连续字节中所存储的数据的逻辑意义。因此，当我们用 int 类型来修饰 foo，编译器就会认为以 foo 开始的连续 4 个字节中存储的数据是一个整型数据。在上述代码中，这个整型数据是 10，我们通过赋值运算符 = 将这个整型数保存到内存中以 foo 地址开始的连续 4 个字节中。
从此刻开始，要记住一个事实，那就是 C 语言中所有的变量名，本质上都是内存地址。之所以不直接使用内存地址，而是使用一些有意义的名字，这就类似于没人愿意用你的身份证号来称呼你，大家更愿意用你的姓名来称呼你。
由于 C 语言认为数据的长度是由其类型确定的。例如，int 类型的数据长度是 4 个字节，char 类型的数据长度是是 1 个字节，用户自定义的 struct 类型的数据长度则是根据实际情况而待定。在这种情况下，所有表示内存地址的名字，它们实质上表示的是内存中各种类型数据存储空间的起始地址——专业一点，就是基地址。凡是用名字来表示基地址的内存空间，我们就将其称为有名的内存空间。
再来看 bar 是什么？bar 是内存地址的名字，由于 bar 前面有个 * 号，这表示我们打算在以 bar 为基地址的连续 8 个字节中存储一个内存地址（别忘了，我们是在 64 位机器上，指针数据的长度是 8 个字节）——foo 所表示的那个地址，亦即 &foo。在这里， & 是取值符，它会对 foo 说，你甭给我耍花样了，老实交代你的身份证号！在* 之前还有 int，这意味着在以 bar 为基地址的连续 8 个字节中存储的那个内存地址是某个用于存储整型数据的内存空间的基地址。
由于 bar 是某个内存空间的基地址，而这个内存空间中存储的是一个内存地址，所以 bar 就是所谓的指针。在这里，我们可以认为 bar 是对某块以 foo 为基地址的内存空间的『引用』，也就是在一个房间号为 bar 的房间里存储了房间号 foo。按照 C 语言教材里常用的说法，可将 int *bar = &foo 这件事描述为『指针 bar 指向了整型变量 foo』，然而事实上内存里哪有什么针，哪有什么指向？一切都是内存空间的引用。在上面的例子里，我们是用 foo 来直接引用某个内存空间，然后又使用 bar 来间接引用某个内存空间。
在上面的例子里，bar 引用的是一个有名的内存空间。那么有没有无名的内存空间呢？看下面的代码：
int *bar = malloc(sizeof(int));
malloc(sizeof(int)) 就是一个无名的内存空间，因为它是一个表达式，而这个表达式描述的是一系列行为，行为需要借助动词来描述，而无法用名词来描述。比如『我在写文章』，这种行为无法只使用名词来描述，必须借助动词。任何会终止的行为都可表示为一系列的状态的变化，也就是说任何会终止的行为都会产生一个结果，而这个结果可以用名词来描述。例如 malloc(sizeof(int)) 这个行为就是可终止的，它的结果是它在内存所开辟 4 个字节的空间的基地址，这个基地址是没有名字的，所以它就是个无名的基地址，因此它对应的内存空间就是无名的内存空间。在上例中，我们将这个无名的内存空间的基地址保存到了一个有名的内存空间——以 bar 为基地址的内存空间。
C 语言的创始人—— Dennis Ritchie 与 Brian Kernighan 将带名字的存储空间称为对象（Object）——并非『面向对象编程』中的对象，然后将指代这个对象的表达式称为左值（lvalue）。也就是说，在 C 语言中，上例中的 foo 与 bar 都是左值，因为它们总是能够出现在赋值符号的左侧。
看下面的代码：
int foo = 10;
int *bar = &foo;
printf("%d", *bar);
第三行的 printf 语句中的 *bar 也是一个左值，因为它指代了一个有名字的存储空间，这个存储空间的名字就叫做 *bar。这个存储空间其实就是以 foo 为基地址的存储空间。在表达式 *bar 中， * 号的作用是解引用，就是将以 bar 为基地址的内存空间中存储的内存地址取出来，然后去访问这个内存地址对应的内存空间。由于 *bar 的类型是 int，所以程序自身就可以知道要访问的是以 *bar 为基地址的 4 个字节，因此它可以准确无误的将整型数据 10 取出来并交给 printf 来显示。
指针最黑暗之处在于，当你拿到了一块内存空间的基地址之后，你可以借助这个基地址随意访问内存中的任何区域！也就是说，你可以从通过指针获得内存空间的入口，然后你可以让你的程序在内存中随便逛，随便破坏，然后你的程序可能就崩溃了。你的程序如果隐含缓冲区溢出漏洞，它甚至可被其他程序控制着去执行一些对你的系统非常不利的代码，这就是所谓的缓冲区溢出攻击。C 语言不提供任何缓冲区保护机制，能否有效保护缓冲区，主要取决于你的 C 编程技艺。
现在我们写 C 程序时，基本上不需要担心自己的程序会遭遇缓冲区溢出攻击。因为只有那些被广泛使用的 C 程序才有这种风险；如果很不幸，你写的 C 程序真的被很多人使用了，那也不需要太担心。《深入理解计算机系统》在 3.12 节『存储器的越界引用和缓冲区溢出』中告诉我们，现代操作系统对程序运行时所需要的栈空间是随机生成的，导致攻击者很难获得栈空间中的某个确定地址，至少在 Linux 系统中是这样子。C 语言编译器提供了栈破坏检测——至少在 GCC 中是这样，其原理就是程序的栈空间放置了一只『金丝雀』，程序在运行中一旦发现有袭击『金丝雀』的可耻代码，它就会异常终止。处理器层面也对可执行代码所在的内存区域进行了限定，这样攻击者很难再向程序的栈空间插入攻击系统的可执行代码了。
栈与堆
如果我说 C 语言是一种部分支持垃圾内存回收的语言……你可能会认为我脑子坏掉了。事实上，C 语言中的所有的局部变量包括指针超出作用域时，它们所占据的存储空间都会被『回收』。这算不算内存垃圾回收？
从 C 程序的角度来看，内存并非一个以字节为单位的一个很大但是又经常不够用的空间，不是一个，而是两个。其中一个空间叫栈，另一个空间叫堆。可被 C 程序『回收』存储空间是栈空间。也就是说，在一个函数中，所有的局部变量所占据的存储空间属于栈空间。可能再说的学术一点，就是绝大多数左值都在栈空间（有人在很遥远的地方指出，全局变量是左值，但它不在栈空间，它与程序同寿，与进程齐光）。
当一个函数运行结束，它所占据的栈空间就不再属于它了，而是将会被一个新的待运行的函数占据。所以，从本质上说，C 程序对栈空间的回收都不屑一顾，因为它根本不回收，而是旧的数据会被新的数据覆盖。
堆空间，我们在程序里无法直接访问，只能借助指针。因为堆空间的内存地址可被指针引用。例如，当使用 malloc 分配空间时，所分配空间的基地址总是保存在一个位于栈空间的指针中的。
栈空间通常远远小于堆空间，即便如此也几乎不会出现某个函数会耗尽栈空间的现象。如果这种现象出现了，那只能证明造出这种现象的程序猿应该继续学习 C 语言了。栈空间被耗尽，往往是因为有些程序本来是写成递归，但可能是代码写错了，导致递而不归；还有一种可能是递归层次太深，这时可以想办法在堆空间中模拟一个栈来解决。还有一种情况就是在函数中定义了很大的数组，导致栈空间放不下……这种情况总是可以靠分配堆空间来解决。
数据的抽象
当你具备了一些 C 编程基础，并且能够理解上文中的内容，那么你就可以对各种类型的数据进行抽象了。
我们为什么要对数据进行抽象？《计算机程序的构造和解释》的第 2 章的导言部分给出了很好的答案，即：许多程序在设计时就是为了模拟复杂的现象，因为它们就常常需要构造出一些运算对象，为了能够模拟真实世界中的现象的各个方面，需要将运算对象表示为一些组件的复合结构。
下面来对自行车链的任意一个链节进行模拟：
struct chain_node {
struct chain_node *prev;
struct chain_node *next;
void *shape;
};
然后我们可以造出 3 个链节，然后可以造出世界上最短的车链：
struct chain_node a, b, c;
a.next = &b;
b.prev = &a;
b.next = &c;
c.prev = &b;
c.next = &a;
a.prev = &c;
如果再多造一些链节，就可以得到周长大一些的车链，也能够制造出各种形状的多边形，但是最好是借助无名的内存空间。下面的代码可以创建一条具有 1000 个链节的链条：
struct chain_node *head = malloc(sizeof(struct chain_node));
struct chain_node *tail = head;
for (int i = 0; i next = new_tail;
new_tail->prev = tail;
tail = new_tail;
}
tail->next = head;
head->prev = tail;
如果我们将前面那个示例中的 a，b, c 视为三角形的三个顶点，那么我们所创造的三个链节构成的链条就变成了一个三角形。同理，上述所创建的 1000 个链节的链条就变成了一个 1000 条边首尾相接的多边形。如果学过拓扑学，那么自然可以发现任何与圆环同胚的结构都可以基于 struct chai_node 这种数据结构模拟出来，而我们所仰仗的东西仅仅是将三个指针封装到一个结构体中。
事实上，struct chain_node 中的第三个指针 void *shape 还没被用到。这是一个 void * 类型的指针，是喜欢用 C 代码玩各种抽象的程序猿的最爱，因为它能引用任何类型数据所在内存空间的基地址。这就意味着 struct chain_node 可以借助 shape 指针获得强大的扩展能力。
现在，我要制造一种很简陋的链节，它的形状仅仅是一个矩形的小铁片，上面打了两个小圆孔。我将它的数据结构设计为：
struct point {
double x;
double y;
};
struct rectangle {
double width;
double height;
};
struct circle {
struct point *center;
double radius;
};
struct chain_node_shape {
struct rectangle *body;
struct circle *holes[2] ;
};
基于这些数据结构，我就可以写出一个专门用来制造矩形小铁片的函数：
struct chain_node_shape *
create_chain_node_shape(struct circle *c1,
struct circle *c2,
struct rectangle *rect)
{
struct chain_node_shape *ret = malloc(sizeof(struct chain_node_shape));
ret->body = rect;
ret->holes[0] = c1;
ret->holes[1] = c2;
return ret;
}
然后再为 create_chain_node_shape 所接受的两种参数写出相应的构造函数：
struct circle *
create_circle(struct point *center, double radius)
{
struct circle *ret = malloc(sizeof(struct circle));
ret->center = center;
ret->radius = radius;
return ret;
}
struct rectangle *
create_rectangle(double w, double h)
{
struct rectangle *ret = malloc(sizeof(struct rectangle));
ret->width = w;
ret->height = h;
return ret;
}
为了让 create_circle 更方便使用，最好再创建一个 struct point 的构造函数：
struct point *
create_point(double x, double y)
{
struct point *ret = malloc(sizeof(struct point));
ret->x = x;
ret->y = y;
return ret;
}
一切所需要的构件都已准备完毕，现在可以开始生产某种特定型号的链节了，即：
struct chain_node *
create_chain_node(void)
{
double radius = 0.5;
double left_x = 1.0;
double left_y = 1.0;
struct point *left_center = create_point(left_x, left_y);
struct circle *left_hole = create_circle(left_center, radius);
double right_x = 9.0;
double right_y = 1.0;
struct point *right_center = create_point(right_x, right_y);
struct circle *right_hole = create_circle(right_center, radius);
struct rectangle *body = create_rectangle(10.0, 2.0);
struct chain_node *ret = malloc(sizeof(struct chain_node));
ret->prev = NULL;
ret->next = NULL;
ret->shape = create_chain_node_shape(left_hole, right_hole, body);
return ret;
}
最后再将制造链条的代码略作修改：
struct chain_node *head = create_chain_node();
struct chain_node *tail = head;
for (int i = 0; i next = new_tail;
new_tail->prev = tail;
tail = new_tail;
}
tail->next = head;
head->prev = tail;
现在我们所模拟的车链与现实中的车链已经有些形似了。上述代码虽然有些冗长，下文会对其进行重构，现在先来总结一下上述代码中指针的用法。
仔细观察上述代码中我们所定义的结构体，它们的共同特征是：所有非 C 内建的数据类型都是结构体类型，当它们作为某个结构体成员类型时均被声明为指针类型。为什么要这样？如果你真的打算问这个问题，那么就请你观察一下上述的 5 个 create_xxx 函数，你会发现这些 create 函数的参数与返回值也都是结构体类型的指针。将这些现象综合起来，可以得出以下结论：
将结构体指针作为函数的参数与返回值，可以避免函数调用时发生过多的内存复制。
当一个结构体类型作为其他结构体的成员类型时，将前者声明为指针类型，可以在后者的 create 函数中避免繁琐的解引用。
void * 指针可以引用任意类型的数据存储空间的基地址。例如在 create_chain_node函数的定义中，我们将一个 struct chain_node_shape 类型的指针赋给了 void * 类型的指针 shape。
这三条结论是指针在数据抽象中的惯用手法，它不仅关系到数据结构的设计，也关系到数据结构的构造与销毁函数的设计。（上述代码为了省事，没有定义数据结构的销毁函数）。
