第二章 —— 接口与实现
在 C 语言模块化编程中，每个模块由一个 .h 文件以及一个 .c 文件组成，在书中被称为模块的接口与实现。接口规定了模块做什么（拥有何种功能），实现提供了接口规定的功能。每个实现可能使用不同的算法和数据结构，但它们都必须合乎接口的规定。
客户程序（client）是使用模块的一段代码。客户程序导入接口，实现则导出接口。客户程序只需要看到接口即可。实际上，他们可能只有实现的目标码（即编译后的二进制程序，如使用 printf() 函数会在链接时会将库文件打包）。多个客户程序共享接口和实现，因而避免了不必要的代码重复。这种方法也有助于避免 bug，接口和实现编写并调试一次后，可以经常使用。
从章节开始处的一段话可以看出，所谓的「接口与实现」其实就是一直以来使用的模块化编程中头文件和源文件换一种说法罢了。在头文件中声明标识符（变量、函数）和类型（结构体），在源文件中编写函数的定义。而书中就以这种方式实现了常用数据结构接口。第二章介绍了「接口与实现」的定义和注意事项。
接口的设计原则
完全屏蔽实现细节
接口仅规定客户程序可能使用的那些标识符，而尽可能隐藏不相关的表示细节算法。这有助于客户程序避免依赖特定实现的具体细节。
接口应该即完全屏蔽实现细节，对于使用的接口的程序而言是完全不知道接口背后实现的任何细节，这样就没有机会让使用者依赖了。后面接着讲到这是为了去掉客户程序与接口实现之间的耦合，让他俩能够独立修改（前提当然是都要符合接口规定），而互不影响。
规范的标识符命名
在接口中，接口名称表现为每个标识符的前缀，这种约定并不优美，但 C 语言几乎没有提供其他的备选方案。所在文件作用域中的标识符，包括变量、函数、类型定义和枚举常数，都共享同一个命名空间。所有的全局结构、联合和枚举标记则共享另一个命名空间。避免这种名称碰撞（name collision）的一个方法是使用前缀，如模块名。一个大程序很容易有数千全局标识符，但通常只有几百个模块。模块名不仅提供了适当的前缀，还有助于使客户程序代码文档化。
「接口名称作为标识符前缀」算是一种约定俗成的习惯。如果查阅一些大的 C 语言源码，会经常看到代码命名「整齐划一」的景象，像 uCosII 操作系统中的 OSTaskCreate()、OSTaskDel()、OSTaskNameGet() 等函数都是属于「任务管理」这个功能模块。想起宋宝华老师说过判断程序「高内聚低耦合」简单粗暴的方法 —— 文件内标识符命名越整齐内聚越高，出现外部名称越少耦合越低。总结起来有两点好处：一是避免名称冲突，二是提高程序的可读性。
堵住（完善）语言语义漏洞
大多数编程语言的语义中都包含有漏洞，某些操作的精确含义定义得不明确或根本未定义。C 语言的语义充满了这种漏洞。设计完善的接口会塞住这些漏洞，将未定义之处定义完善，并对语言标准规定为未定义或由具体实现定义的行为给出明确的裁决。
书中举了这样一个例子：C 语言没有对除法以及模运算操作做明确定义，不同的编译器实现所得到的结果存在差异。而接口的设计者必须要有自己的明确立场，并负责统一不同具体实现所带来的差异，从而确保程序的可移植性（书中有不少这样的例子，毕竟 C 接近底层机器具体实现），避免对特定机器的依赖。
具体例子就是书中的 Arith_div 和 Arith_mod 函数， 两者分别实现求两个整数的除法和模运算，但上面提到对于除法和模运算规则 C 语言没有严格定义。
C 语言标准只是强调，如果 x/y 是可表示的，那么 (x/y)*y + x%y 必须等于 x。那么问题就来了，当一个操作数为负数时，这种语义就使得整数除法可以向零舍入，可以向负无穷大舍入。例如，如果 -13/5 的结果定义为 -2，那么标准指出，-13%5 必须等于 -13-(-13/5)5=-13-(-2)5=-3。但如果 -13/5 定义为 -3，那么 -13%15 的指必须是 -13-(-3)*5 = 2。
而书中对 Arith_div 的结果规定为「向负无穷大舍入」，所以在返回结果时通过 -13/5 == -2 表达式测试当前机器计算方式并统一处理两种可能：
if (-13/5 == -2 && x%y != 0)
return x/y -1;
else
return x/y;
抽象数据类型
数据类型的内涵
一个抽象数据类型是一个接口，它定义了一个数据类型和对该类型的值所进行的操作。一个数据类型是一个值的集合。在 C 语言中，内建的数据类型包括字符、整数、浮点数等。而结构本身也能定义新的类型，因而可用于建立更高级类型，如列表、树、查找表等。
高级类型是抽象的，因为其接口隐藏了相关的表示细节，并只规定了对该类型的合法操作。理想情况下，这些操作不会暴露类型的表示细节，因为那样可能使客户程序隐含地依赖于具体的表示。
之前也有这样的意识，数据类型除了感性上「不同类别数据」的认识之外，还存在更加深刻的内涵。书中在介绍抽象数据类型时就指出了数据类型的两个本质内容 —— 数据本身（值的集合）与对数据的操作。以基本数据类型的实型为例，它是所有带小数点数值的集合（长得像 12.32，433.23 这样的），并有一些合法操作（如加减乘除，而模运算、位运算是非法的）。而高级的数据结构也不过如此，只是用一个接口模块进行了封装。如栈类型必提供一个数值集合，和一些 Push、Pop 的操作，至于使用顺序表还是链表，怎么实现 Push 和 Pop 就是类型内部的事情了。
不透明的指针类型
书中以栈作为 ADT 的范例（栈所保存的数据为 void 指针），在接口中定义了栈类型及其五个操作：
<initial version of stack.h> ≡
#ifndef STACK_INCLUDED
#define STACK_INCLUDED
typedef struct Stack_T *Strck_T;
extern Stack_T Stack_new (void);
extern int Stack_empty(Stack_T stk);
extern void Stack_push (Stack_T stk, void *x);
extern void *Stack_pop (Stack_t stk);
extern void Stack_free (Stack_t *stk);
#endif
PS：程序中结构名 Stack_T 和 typedef 得到的类型名相同，形象地用指针表示了类型。但这并不会冲突。书中解释到：「该定义是合法的，因为结构、联合和枚举的名称（标记）占用了一个命名空间，该命名空间不同于变量、函数和类型名所用的命名空间」。
该接口透露了栈是通过指向结构的指针表示的，但并没有给出结构的任何信息。因而
Stack_T是一个不透明指针类型，客户端可以自由地操纵这种指针，但无法反引用不透明指针，即无法查看指针所指向结构的内部信息。不透明指针隐藏了表示细节，有助于捕获错误。只有
Stack_T类型值可以传递给上述的函数，试图传递另一种指针，如指向其他结构的指针，将会产生编译错误。唯一的例外是参数中的一个void指针。该参数可以传递任何类型指针。
这里提到了一个概念叫「不透明指针」，意思是使用者在接口中看到的是指向具体类型（结构）的指针，而看不到具体结构的内组成(当然这只是针对头文件来讲，严格来说只要有 C 文件还是可以看到内部实现的)。使用指针作为导出类型隐藏了内部细节，需要披露表示细节时则将结构类型定义为导出类型，关于这一点，书中举了后面 16 章 Text 接口的类型定义作为对比。
<exported types 192> ≡
typedef struct T {
int len;
const char *str;
} T;
简而言之，「透明」就是在头文件中能看到结构体的成员，而不透明恰好相反。对不透明指针导出的 ADT，客户程序不知道指针指向的到底是个什么东西（就像你从一把钥匙永远猜不到它打开的箱子里是黄金还是暖色灯泡），只能通过接口提供的函数进行操作，而不能直接访问字段（虽然在一些 IDE 中有「 ->指向运算符后提示成员名称」功能使你能直接访问它们）。
习题（完整代码见Github）
2.1 原本可使用预处理器宏和条件编译指令如 #if，来指定 Arith_div 和 Arith_mod 中如何处理除法的舍入操作。解释为什么对 -13/5 == -2 的显示测试是实现上述判断的更好的方法。
答：使用显示测试而不使用预处理条件编译符合「一份程序应对不同情况」的原则，使得编译好的程序更加灵活，而不需要针对不同的目标机器重新编译。
2.2 对于 Arith_div 和 Arith_mod 来说，仅当用于编译 airth.c 的编译器执行算术操作的方式与 Arith_div 和 Arith_mod 被调用的目标机器相同时，这两个函数中所用的 -13/5 == -2 测试才是有效的。但这个条件可能不成立，例如如果 arith.c 由运行在机器 X 上交叉编译器编译，针对机器 Y 生成代码。不使用条件编译指令，请改正 arith.c，使得交叉编译生成的代码也保证可以工作。
表示这题目也是看了半天才看懂……书中在程序中使用判断条件 -13/5 == -2 测试目标机器（即运行程序的机器）对除法的计算规则，但问题在于，C 语言的常量表达式会在编译时就会计算出结果并用结果替代，这样一来目标程序中的结果就变成常量而不会再去计算。在交叉编译（程序由不同架构的机器编译和运行）时测试表达式便会失效。所以第一反应就想到，既然常量表达式不行就用变量啊（好像也太直接了吧）……
答：常量表达式在编译时会被计算，将 arith.c 的测试表达式用变量表示：
int a = -13;
int b = 5;
<division truncates toward 0 14> ≡
a / b == -2
2.3 如同本书所有的 ADT，Stack 接口也省略了下述规格说明：「将外部的 Stack_T 传递给本接口中任何例程，都是未检查的运行时错误」。外部的 Stack_T，意味着不是由 Stack_new 产生的 Stack_T。修正 stack.c 使其可以在某些情况下检查到这种错误。例如，一种方法是向 Stack_T 结构添加一个字段，对于 Stack_new 返回的 Stack_T，该字段包含一个特有的位模式。
答：按照题目提示，向 Stack_T 结构添加一个字段 check，其合法值（即由 Stack_new 返回的 Stack_T 所指向）为 0x66，在对 Stack_T 操作的其余各函数中增加 STACK_T_IS_LEGAL 断言检查其合法性。
#include <stddef.h>
#include "assert.h"
#include "mem.h"
#include "stack.h"
#define T Stack_T
#define LEGAL 0x66
#define STACK_T_IS_LEGAL (((stk) != NULL)&&((stk->check) == LEGAL))
struct T {
int count;
struct elem {
void *x;
struct elem *link;
} *head;
unsigned char check;
};
T Stack_new(void) {
T stk;
NEW(stk);
stk->count = 0;
stk->head = NULL;
stk->check = LEGAL;
return stk;
}
int Stack_empty(T stk) {
assert(STACK_T_IS_LEGAL)
return stk-> count == 0;
}
2.4 通常有可能会检测到某些无效指针。例如，如果一个非空指针指定的地址在客户程序地址空间之外，那么该指针就是无效的，而且指针通常会受到对齐约束，例如，在某些系统上，指向 double 的指针，指向的地址必定是 8 的倍数。请设计一个特定于系统的宏 isBadPtr(p)，在 p 为无效指针时为 1，这样 assert(ptr) 之类的断言都可以替换为类似 assert(!isBadPtr(ptr)) 的断言。
答：#define isBadPtr(p) (((p) == (NULL)) || ((((unsigned int)(p)) % (sizeof(T))) != (0)))
2.5 对栈来说，有许多可行的接口。为 Stack 接口设计并实现一些备选方案。例如，一种方案是在为 Stack_new 增加一个参数，用于指定栈的最大容量。
答：向 Stack_T 结构添加一个字段 max_size 保存栈的最大容量，修改 Stack_new 和 Stack_push 方法，初始化时指定栈的最大容量并保存到 max_size 字段中，入栈时检查栈大小是否超出最大容量。
struct T {
int count;
int max_size;
struct elem {
void *x;
struct elem *link;
} *head;
unsigned char check;
};
T Stack_new(int max) {
T stk;
NEW(stk);
stk->count = 0;
stk->max_size = max;
stk->head = NULL;
stk->check = LEGAL;
return stk;
}
void Stack_push(T stk, void *x) {
struct elem *t;
assert(STACK_T_IS_LEGAL);
assert(stk->count < stk->max_size)
NEW(t);
t->x = x;
t->link = stk->head;
stk->head = t;
stk->count++;
}
