后记：“解构 K&R C” 已死
最后更新于：2022-04-01 23:29:47
# “解构 K&R C” 已死
> 原文：[Deconstructing K&RC Is Dead](http://c.learncodethehardway.org/book/krcritique.html)
> 译者：[飞龙](https://github.com/wizardforcel)
我彻底失败了。我放弃了多年以来尝试理清C语言如何编写的想法，因为它的发明是有缺陷的。起初，我的书中有一章叫做“解构 K&R C”。这一章的目的是告诉人们永远不要假设它们的代码是正确的，或者对于任何人的代码，不管它有多出名，也不能避免缺陷。这看起来似乎并不是革命性的想法，并且对我来说它只是分析代码缺陷和编写更好更可靠代码的一部分。
多年以来，我在写这本书的这一块时收到重挫，并且收到了比任何其它事情更多的批评和侮辱。不仅如此，而且书中这部分的批评以这些话而结束，“你是对的，但是你认为他们的代码很烂这件事是错的。”我不能理解，有一群被认为很聪明的人，他们的大脑中充满理性，却坚持“我可以是错的，但是同时也可以是对的”的观点。我不得不与这些学究在C IRC channels、邮件列表、评论上斗争，这包括每一个它们提出一些怪异的、迂腐的刻薄意见的情况，需要我对我的文章进行更多的逻辑性修改来说服他们。
有趣的一点是，在我写这部分之前，我收到了本书许多正面的评论。当时本书还在写作中，所以我觉得确实需要改进。我甚至设置了一些奖金让人们帮助改进。但可悲的是，一旦他们被自己的英雄蒙蔽，所崇拜的基调就发生了翻天覆地的变化。我变得十分令人讨厌，只不过是尝试教人们如何安全使用一个极易出错的垃圾语言，比如C语言。这是我很擅长的东西。
这些批评者向我承认，他们不写C代码也不教授它，他们只是死记硬背标准库来“帮助”其它人，这对我来说并不重要。我以一个开放的心态试图解决问题，甚至设置奖金给那些有助于修复它的人，这也不重要。这可以使更多的人爱上C语言，并且使其它人入门编程，这更不重要。重要的是我“侮辱”了他们的英雄，这意味着我所说的话永远地完蛋了，没有人会再次相信我。
坦率地说，这是编程文化极为的黑暗、丑陋、邪恶的一面。他们整天在说，“我与你们同在”，但是如果你不屈服于大师们海量的学识，以及乞求他们准许你质疑他们所信奉的东西，你突然就会变成敌人。程序员费尽心机地把自己放在权力的宝座上，来要求别人赞许他们高超的记忆能力，或者对一些微不足道的琐事的熟知，并且会尽全力消灭那些胆敢质疑的人。
这非常恶心，我对此也没什么能做的。我对老程序员无能为力。但他们注定会失败。它们通过标准化记忆所积累的学识，也会在咸鱼的下一次翻身中蒸发掉。它们对考虑如何事物的运作方式，以及如何改进它们，或者将它们的手艺传授给他人毫无兴趣，除非这里面涉及到大量的阿谀奉承并让他们觉得很爽。老程序员总会完蛋的。
他们向现在的年轻程序员施压，我对此并不能做任何事情。我不能阻止无能程序员的诽谤，他们甚至根本不像专业的C程序员那样。然而，我宁愿使本书有助于那些想要学习C语言以及如何编写可靠的软件的人，而不是和那些思维闭锁的保守派做斗争。它们贪图安逸的行为给人一种感觉，就是他们知道更多迂腐的、可怜的小话题，就比如未定义行为。
因此，我删除了书中的K&R C部分，并且找到了新的主题。我打算重写这本书，但是并不知道如何去做。我犹如在地狱中，因为我自己非常执着于我觉得很重要的一些事情，但我不知道如何推进。我现在算是明白了这是错的，因为它阻碍我将一些与C不相关的重要技巧教给许多新的程序员，包括编程规范、代码分析、缺陷和安全漏洞的检测，以及学习其它编程语言的方法。
现在我明白了，我将为这本书制作一些课程，关于编写最安全的C代码，以及将C语言代码打破为一种学习C和编程规范的方式。我会卑微地说我的书只是一个桥梁，所有人应该去读K&R C来迎合这些学究，并且在这些黄金法则的脚下顶礼膜拜。我要澄清我的C版本限制于一个固定的目的之中，因为这让我的代码更安全。我一定会提到所有迂腐的东西，比如每个书呆子式的，关于20世纪60年代的PDP-11电脑上空指针的要求。
之后，我会告诉人们不要再去写别的C程序。这不会很明显，完全不会，但我的目标是将人们从C带到能更好地编程的其它语言中。Go、Rust或者Swift，是我能想到的能处理C语言主要任务新型语言，所以我推荐人们学习它们。我会告诉他们，他们的技能在于发现缺陷，并且对C代码的严格分析将会对所有语言都有巨大的好处，以及使其它语言更易于学习。
但是C呢？C已经死了，它是为想要争论A.6.2章第四段的指针未定义行为的老程序员准备的。谢天谢地，我打算去学习Go（或者Rust，或者Swift，或者其它任何东西）了。
';
练习47：一个快速的URL路由
最后更新于：2022-04-01 23:29:44
# 练习47：一个快速的URL路由
> 原文：[Exercise 47: A Fast URL Router](http://c.learncodethehardway.org/book/ex47.html)
> 译者：[飞龙](https://github.com/wizardforcel)
我现在打算向你展示使用`TSTree`来创建服务器中的快速URL路由。它适用于应用中的简单的URL匹配，而不是在许多Web应用框架中的更复杂（一些情况下也不必要）的路由发现功能。
我打算编程一个小型命令行工具和路由交互，他叫做`urlor`，读取简单的路由文件，之后提示用户输入要检索的URL。
```c
#include
#include
TSTree *add_route_data(TSTree *routes, bstring line)
{
struct bstrList *data = bsplit(line, ' ');
check(data->qty == 2, "Line '%s' does not have 2 columns",
bdata(line));
routes = TSTree_insert(routes,
bdata(data->entry[0]), blength(data->entry[0]),
bstrcpy(data->entry[1]));
bstrListDestroy(data);
return routes;
error:
return NULL;
}
TSTree *load_routes(const char *file)
{
TSTree *routes = NULL;
bstring line = NULL;
FILE *routes_map = NULL;
routes_map = fopen(file, "r");
check(routes_map != NULL, "Failed to open routes: %s", file);
while((line = bgets((bNgetc)fgetc, routes_map, '\n')) != NULL) {
check(btrimws(line) == BSTR_OK, "Failed to trim line.");
routes = add_route_data(routes, line);
check(routes != NULL, "Failed to add route.");
bdestroy(line);
}
fclose(routes_map);
return routes;
error:
if(routes_map) fclose(routes_map);
if(line) bdestroy(line);
return NULL;
}
bstring match_url(TSTree *routes, bstring url)
{
bstring route = TSTree_search(routes, bdata(url), blength(url));
if(route == NULL) {
printf("No exact match found, trying prefix.\n");
route = TSTree_search_prefix(routes, bdata(url), blength(url));
}
return route;
}
bstring read_line(const char *prompt)
{
printf("%s", prompt);
bstring result = bgets((bNgetc)fgetc, stdin, '\n');
check_debug(result != NULL, "stdin closed.");
check(btrimws(result) == BSTR_OK, "Failed to trim.");
return result;
error:
return NULL;
}
void bdestroy_cb(void *value, void *ignored)
{
(void)ignored;
bdestroy((bstring)value);
}
void destroy_routes(TSTree *routes)
{
TSTree_traverse(routes, bdestroy_cb, NULL);
TSTree_destroy(routes);
}
int main(int argc, char *argv[])
{
bstring url = NULL;
bstring route = NULL;
check(argc == 2, "USAGE: urlor ");
TSTree *routes = load_routes(argv[1]);
check(routes != NULL, "Your route file has an error.");
while(1) {
url = read_line("URL> ");
check_debug(url != NULL, "goodbye.");
route = match_url(routes, url);
if(route) {
printf("MATCH: %s == %s\n", bdata(url), bdata(route));
} else {
printf("FAIL: %s\n", bdata(url));
}
bdestroy(url);
}
destroy_routes(routes);
return 0;
error:
destroy_routes(routes);
return 1;
}
```
之后我创建了一个简单的文件，含有一些用于交互的伪造的路由：
```
/ MainApp /hello Hello /hello/ Hello /signup Signup /logout Logout /album/ Album
```
## 你会看到什么
一旦你使`urlor`工作，并且创建了路由文件，你可以尝试这样：
```sh
$ ./bin/urlor urls.txt
URL> /
MATCH: / == MainApp
URL> /hello
MATCH: /hello == Hello
URL> /hello/zed
No exact match found, trying prefix.
MATCH: /hello/zed == Hello
URL> /album
No exact match found, trying prefix.
MATCH: /album == Album
URL> /album/12345
No exact match found, trying prefix.
MATCH: /album/12345 == Album
URL> asdfasfdasfd
No exact match found, trying prefix.
FAIL: asdfasfdasfd
URL> /asdfasdfasf
No exact match found, trying prefix.
MATCH: /asdfasdfasf == MainApp
URL>
$
```
你可以看到路由系统首先尝试精确匹配，之后如果找不到的话则会尝试前缀匹配。这主要是尝试这二者的不同。根据你的URL的语义，你可能想要之中精确匹配，始终前缀匹配，或者执行二者并选出“最好”的那个。
## 如何改进
URL非常古怪。因为人们想让它们神奇地处理它们的web应用所具有的，所有疯狂的事情，即使不是很合逻辑。在这个对如何将`TSTree`用作路由的简单演示中，它具有一些人们不想要的缺陷。比如，它会把`/al`匹配到`Album`，它是人们通常不想要的。它们想要`/album/*`匹配到`Album`以及`/al`匹配到404错误。
这并不难以实现，因为你可以修改前缀算法来以你想要的任何方式匹配。如果你修改了匹配算法，来寻找所有匹配的前缀，之后选出“最好”的那个，你就可以轻易做到它。这种情况下，`/al`回匹配`MainApp`或者`Album`。获得这些结果之后，就可以执行一些逻辑来决定哪个“最好”。
另一件你能在真正的路由系统里做的事情，就是使用`TSTree`来寻找所有可能的匹配，但是这些匹配是需要检查的一些模式串。在许多web应用中，有一个正则表达式的列表，用于和每个请求的URL进行匹配。匹配所有这些正则表达式非常花时间，所以你可以使用`TSTree`来通过它们的前缀寻找所有可能的结果。于是你就可以缩小模式串的范围，更快速地做尝试。
使用这种方式，你的URL会精确匹配，因为你实际上运行了正则表达式，它们匹配起来更快，因为你通过可能的前缀来查找它们。
这种算法也可用于所有需要用户可视化的灵活路由机制。域名、IP地址、包注册器和目录，文件或者URL。
## 附加题
+ 创建一个实际的引擎，使用`Handler`结构储存应用，而不是仅仅储存应用的字符串。这个结构储存它所绑定的URL，名称和任何需要构建实际路由系统的东西。
+ 将URL映射到`.so`文件而不是任意的名字，并且使用`dlopen`系统动态加载处理器，并执行它们所包含的回调。将这些回调放进你的`Handler`结构体中，之后你就用C编写了动态回调处理器系统的全部。
';
练习46：三叉搜索树
最后更新于：2022-04-01 23:29:42
# 练习46：三叉搜索树
> 原文：[Exercise 46: Ternary Search Tree](http://c.learncodethehardway.org/book/ex46.html)
> 译者：[飞龙](https://github.com/wizardforcel)
我打算向你介绍的最后一种数据结构就是三叉搜索树（`TSTree`），它和`BSTree`很像，除了它有三个分支，`low`、`equal`和`high`。它的用法和`BStree`以及`Hashmap`基本相同，用于储存键值对的数据，但是它通过键中的独立字符来控制。这使得`TSTree`具有一些`BStree`和`Hashmap`不具备的功能。
`TSTree`的工作方式是，每个键都是字符串，根据字符串中字符的等性，通过构建或者遍历一棵树来进行插入。首先由根节点开始，观察每个节点的字符，如果小于、等于或大于则去往相应的方向。你可以参考这个头文件：
```c
#ifndef _lcthw_TSTree_h
#define _lctwh_TSTree_h
#include
#include
typedef struct TSTree {
char splitchar;
struct TSTree *low;
struct TSTree *equal;
struct TSTree *high;
void *value;
} TSTree;
void *TSTree_search(TSTree *root, const char *key, size_t len);
void *TSTree_search_prefix(TSTree *root, const char *key, size_t len);
typedef void (*TSTree_traverse_cb)(void *value, void *data);
TSTree *TSTree_insert(TSTree *node, const char *key, size_t len, void *value);
void TSTree_traverse(TSTree *node, TSTree_traverse_cb cb, void *data);
void TSTree_destroy(TSTree *root);
#endif
```
`TSTree`拥有下列成员：
splitchar
树中该节点的字符。
low
小于`splitchar`的分支。
equal
等于`splitchar`的分支。
high
大于`splitchar`的分支。
value
这个节点上符合当前`splitchar`的值的集合。
你可以看到这个实现中含有下列操作：
search
为特定`key`寻找值的典型操作。
search_prefix
寻找第一个以`key`为前缀的值，这是你不能轻易使用`BSTree` 或 `Hashmap` 完成的操作。
insert
将`key`根据每个字符拆分，并把它插入到树中。
traverse
遍历整颗树，使你能够收集或分析所包含的所有键和值。
唯一缺少的操作就是`TSTree_delete`，这是因为它是一个开销很大的操作，比`BSTree_delete`大得多。当我使用`TSTree`结构时，我将它们视为常量数据，我打算遍历许多次，但是永远不会移除任何东西。它们对于这样的操作会很快，但是不适于需要快速插入或删除的情况。为此我会使用`Hashmap`因为它优于`BSTree`和`TSTree`。
`TSTree`的实现非常简单，但是第一次可能难以理解。我会在你读完之后拆分它。
```c
#include
#include
#include
#include
#include
static inline TSTree *TSTree_insert_base(TSTree *root, TSTree *node,
const char *key, size_t len, void *value)
{
if(node == NULL) {
node = (TSTree *) calloc(1, sizeof(TSTree));
if(root == NULL) {
root = node;
}
node->splitchar = *key;
}
if(*key < node->splitchar) {
node->low = TSTree_insert_base(root, node->low, key, len, value);
} else if(*key == node->splitchar) {
if(len > 1) {
node->equal = TSTree_insert_base(root, node->equal, key+1, len - 1, value);
} else {
assert(node->value == NULL && "Duplicate insert into tst.");
node->value = value;
}
} else {
node->high = TSTree_insert_base(root, node->high, key, len, value);
}
return node;
}
TSTree *TSTree_insert(TSTree *node, const char *key, size_t len, void *value)
{
return TSTree_insert_base(node, node, key, len, value);
}
void *TSTree_search(TSTree *root, const char *key, size_t len)
{
TSTree *node = root;
size_t i = 0;
while(i < len && node) {
if(key[i] < node->splitchar) {
node = node->low;
} else if(key[i] == node->splitchar) {
i++;
if(i < len) node = node->equal;
} else {
node = node->high;
}
}
if(node) {
return node->value;
} else {
return NULL;
}
}
void *TSTree_search_prefix(TSTree *root, const char *key, size_t len)
{
if(len == 0) return NULL;
TSTree *node = root;
TSTree *last = NULL;
size_t i = 0;
while(i < len && node) {
if(key[i] < node->splitchar) {
node = node->low;
} else if(key[i] == node->splitchar) {
i++;
if(i < len) {
if(node->value) last = node;
node = node->equal;
}
} else {
node = node->high;
}
}
node = node ? node : last;
// traverse until we find the first value in the equal chain
// this is then the first node with this prefix
while(node && !node->value) {
node = node->equal;
}
return node ? node->value : NULL;
}
void TSTree_traverse(TSTree *node, TSTree_traverse_cb cb, void *data)
{
if(!node) return;
if(node->low) TSTree_traverse(node->low, cb, data);
if(node->equal) {
TSTree_traverse(node->equal, cb, data);
}
if(node->high) TSTree_traverse(node->high, cb, data);
if(node->value) cb(node->value, data);
}
void TSTree_destroy(TSTree *node)
{
if(node == NULL) return;
if(node->low) TSTree_destroy(node->low);
if(node->equal) {
TSTree_destroy(node->equal);
}
if(node->high) TSTree_destroy(node->high);
free(node);
}
```
对于`TSTree_insert`，我使用了相同模式的递归结构，其中我创建了一个小型函数，它调用真正的递归函数。我对此并不做任何检查，但是你应该为之添加通常的防御性编程策略。要记住的一件事，就是它使用了一些不同的设计，这里并没有单独的`TSTree_create`函数，如果你将`node`传入为`NULL`，它会新建一个，然后返回最终的值。
这意味着我需要为你分解`TSTree_insert_base`，使你理解插入操作。
tstree.c:10-18
像我提到的那样，如果函数接收到`NULL`，我需要创建节点，并且将`*key`（当前字符）赋值给它。这用于当我插入键时来构建树。
tstree.c:20-21
当`*key`小于`splitchar`时，选择`low`分支。
tstree.c:22
如果`splitchar`相等，我就要进一步确定等性。这会在我刚刚创建这个节点时发生，所以这里我会构建这棵树。
tstree.c:23-24
仍然有字符串需要处理，所以向下递归`equal`分支，并且移动到下一个`*key`字符。
tstree.c:26-27
这是最后一个字符的情况，所以我将值设置好。我编写了一个`assert`来避免重复。
tstree.c:29-30
最后的情况是`*key`大于`splitchar`，所以我需要向下递归`high`分支。
这个数据结构的`key`实际上带有一些特性，我只会在`splitchar`相等时递增所要分析的字符。其它两种情况我只会继续遍历整个树，直到碰到了相等的字符，我才会递归处理下一个字符。这一操作使它对于找不到键的情况是非常快的。我可以传入一个不存在的键，简单地遍历一些`high`和`low`节点，直到我碰到了末尾并且知道这个键不存在。我并不需要处理键的每个字符，或者树的每个节点。
一旦你理解了这些，之后来分析`TSTree_search`如何工作：
tstree.c:46
我并不需要递归处理整棵树，只需要使用`while`循环和当前的`node`节点。
tstree.c:47-48
如果当前字符小于节点中的`splitchar`，则选择`low`分支。
tstree.c:49-51
如果相等，自增`i`并且选择`equal`分支，只要不是最后一个字符。这就是`if(i < len)`所做的，使我不会越过最后的`value`。
tstree.c:52-53
否则我会选择`high`分支，由于当前字符更大。
tstree.c:57-61
循环结束后如果`node`不为空，那么返回它的`value`，否则返回`NULL`。
这并不难以理解，并且你可以看到`TSTree_search_prefix`函数用了几乎相同的算法。唯一的不同就是我并不试着寻找精确的匹配，而是可找到的最长前缀。我在相等时跟踪`last`节点来实现它，并且在搜索循环结束之后，遍历这个节点直到发现`value`。
观察`TSTree_search_prefix`，你就会开始明白`TSTree`相对`BSTree` 和 `Hashmap`在查找操作上的另一个优点。给定一个长度为X的键，你可以在X步内找到任何键，但是也可以在X步加上额外的N步内找到第一个前缀，取决于匹配的键有多长。如果树中最长的键是十个字符，那么你就可以在10步之内找到任意的前缀。更重要的是，你可以通过对键的每个字符只比较一次来实现。
相比之下，使用`BSTree`执行相同操作，你需要在`BSTree`的每一个可能匹配的节点中检查两个字符串是否有共同的前缀。这对于寻找键，或者检查键是否存在（`TSTree_search`）是相同的。你需要将每个字符与`BSTree`中的大多数字符对比，来确认是否匹配。
`Hashamp`对于寻找前缀更加糟糕，因为你不能够仅仅计算前缀的哈希值。你基本上不能高效在`Hashmap`中实现它，除非数据类似URL可以被解析。即使这样你还是需要遍历`Hashmap`的所有节点。
> 译者注：二叉树和三叉树在搜索时都是走其中的一支，但由于二叉树中每个节点储存字符串，而三叉树储存的是字符。所以三叉树的整个搜索过程相当于一次字符串比较，而二叉树的每个节点都需要一次字符串比较。三叉树堆叠储存字符串使搜索起来更方便。
> 至于哈希表，由于字符串整体和前缀计算出来的哈希值差别很大，所以按前缀搜索时，哈希的优势完全失效，所以只能改为暴力搜索，效果比二叉树还要差。
最后的两个函数应该易于分析，因为它们是典型的遍历和销毁操作，你已经在其它数据结构中看到过了。
最后，我编写了简单的单元测试，来确保我所做的全部东西正确。
```c
#include "minunit.h"
#include
#include
#include
#include
TSTree *node = NULL;
char *valueA = "VALUEA";
char *valueB = "VALUEB";
char *value2 = "VALUE2";
char *value4 = "VALUE4";
char *reverse = "VALUER";
int traverse_count = 0;
struct tagbstring test1 = bsStatic("TEST");
struct tagbstring test2 = bsStatic("TEST2");
struct tagbstring test3 = bsStatic("TSET");
struct tagbstring test4 = bsStatic("T");
char *test_insert()
{
node = TSTree_insert(node, bdata(&test1), blength(&test1), valueA);
mu_assert(node != NULL, "Failed to insert into tst.");
node = TSTree_insert(node, bdata(&test2), blength(&test2), value2);
mu_assert(node != NULL, "Failed to insert into tst with second name.");
node = TSTree_insert(node, bdata(&test3), blength(&test3), reverse);
mu_assert(node != NULL, "Failed to insert into tst with reverse name.");
node = TSTree_insert(node, bdata(&test4), blength(&test4), value4);
mu_assert(node != NULL, "Failed to insert into tst with second name.");
return NULL;
}
char *test_search_exact()
{
// tst returns the last one inserted
void *res = TSTree_search(node, bdata(&test1), blength(&test1));
mu_assert(res == valueA, "Got the wrong value back, should get A not B.");
// tst does not find if not exact
res = TSTree_search(node, "TESTNO", strlen("TESTNO"));
mu_assert(res == NULL, "Should not find anything.");
return NULL;
}
char *test_search_prefix()
{
void *res = TSTree_search_prefix(node, bdata(&test1), blength(&test1));
debug("result: %p, expected: %p", res, valueA);
mu_assert(res == valueA, "Got wrong valueA by prefix.");
res = TSTree_search_prefix(node, bdata(&test1), 1);
debug("result: %p, expected: %p", res, valueA);
mu_assert(res == value4, "Got wrong value4 for prefix of 1.");
res = TSTree_search_prefix(node, "TE", strlen("TE"));
mu_assert(res != NULL, "Should find for short prefix.");
res = TSTree_search_prefix(node, "TE--", strlen("TE--"));
mu_assert(res != NULL, "Should find for partial prefix.");
return NULL;
}
void TSTree_traverse_test_cb(void *value, void *data)
{
assert(value != NULL && "Should not get NULL value.");
assert(data == valueA && "Expecting valueA as the data.");
traverse_count++;
}
char *test_traverse()
{
traverse_count = 0;
TSTree_traverse(node, TSTree_traverse_test_cb, valueA);
debug("traverse count is: %d", traverse_count);
mu_assert(traverse_count == 4, "Didn't find 4 keys.");
return NULL;
}
char *test_destroy()
{
TSTree_destroy(node);
return NULL;
}
char * all_tests() {
mu_suite_start();
mu_run_test(test_insert);
mu_run_test(test_search_exact);
mu_run_test(test_search_prefix);
mu_run_test(test_traverse);
mu_run_test(test_destroy);
return NULL;
}
RUN_TESTS(all_tests);
```
## 优点和缺点
`TSTree`可以用于实现一些其它实用的事情：
+ 除了寻找前缀，你可以反转插入的所有键，之后通过后缀来寻找。我使用它来寻找主机名称，因为我想要找到`*.learncodethehardway.com`，所以如果我反向来寻找，会更快匹配到它们。
+ 你可以执行“模糊”搜索，其中你可以收集所有与键的大多数字符相似的节点，或者使用其它算法用于搜索近似的匹配。
+ 你可以寻找所有中间带有特定部分的键。
我已经谈论了`TSTree`能做的一些事情，但是它们并不总是最好的数据结构。`TSTree`的缺点在于：
+ 像我提到过的那样，删除操作非常麻烦。它们适用于需要快速检索并且从不移除的操作。如果你需要删除，可以简单地将`value`置空，之后当树过大时周期性重构它。
+ 与`BSTree`和`Hashmap`相比，它在相同的键上使用了大量的空间。它对于键中的每个字符都使用了完整的节点。它对于短的键效果更好，但如果你在`TSTree`中放入一大堆东西，它会变得很大。
+ 它们也不适合处理非常长的键，然而“长”是主观的词，所以应当像通常一样先进行测试。如果你尝试储存一万个字符的键，那么应当使用`Hashmap`。
## 如何改进
像通常一样，浏览代码，使用防御性的先决条件、断言，并且检查每个函数来改进。下面是一些其他的改进方案，但是你并不需要全部实现它们：
+ 你可以使用`DArray`来允许重复的`value`值。
+ 因为我提到删除非常困难，但是你可以通过将值设为`NULL`来模拟，使值能够高效被删除。
+ 目前还不能获取到所有匹配指定前缀的值，我会让你在附加题中实现它。
+ 有一些其他得更复杂的算法会比它要好。查询前缀数组、前缀树和基数树的资料。
## 附加题
+ 实现`TSTree_collect`返回`DArray`包含所有匹配指定前缀的键。
+ 实现`TSTree_search_suffix`和`TSTree_insert_suffix`，实现后缀搜索和插入。
+ 使用`valgrind`来查看与`BSTree` 和 `Hashmap`相比，这个结构使用了多少内存来储存数据。
';
练习45：一个简单的TCP/IP客户端
最后更新于：2022-04-01 23:29:40
# 练习45：一个简单的TCP/IP客户端
> 原文：[Exercise 45: A Simple TCP/IP Client](http://c.learncodethehardway.org/book/ex45.html)
> 译者：[飞龙](https://github.com/wizardforcel)
我打算使用`RingBuffer`来创建一个非常简单的小型网络测试工具，叫做`netclient`。为此我需要向`Makefile`添加一些工具，来处理`bin/`目录下的小程序。
## 扩展Makefile
首先，为程序添加一些变量，就像单元测试的`TESTS`和`TEST_SRC`变量：
```Makefile
PROGRAMS_SRC=$(wildcard bin/*.c)
PROGRAMS=$(patsubst %.c,%,$(PROGRAMS_SRC))
```
之后你可能想要添加`PROGRAMS`到所有目标中：
```makefile
all: $(TARGET) $(SO_TARGET) tests $(PROGRAMS)
```
之后在`clean`目标中向`rm`那一行添加`PROGRAMS`：
```makefile
rm -rf build $(OBJECTS) $(TESTS) $(PROGRAMS)
```
最后你还需要在最后添加一个目标来构建它们：
```makefile
$(PROGRAMS): CFLAGS += $(TARGET)
```
做了这些修改你就能够将`.c`文件扔到`bin`中，并且编译它们以及为其链接库文件，就像测试那样。
## netclient 代码
netclient的代码是这样的：
```c
#undef NDEBUG
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
struct tagbstring NL = bsStatic("\n");
struct tagbstring CRLF = bsStatic("\r\n");
int nonblock(int fd) {
int flags = fcntl(fd, F_GETFL, 0);
check(flags >= 0, "Invalid flags on nonblock.");
int rc = fcntl(fd, F_SETFL, flags | O_NONBLOCK);
check(rc == 0, "Can't set nonblocking.");
return 0;
error:
return -1;
}
int client_connect(char *host, char *port)
{
int rc = 0;
struct addrinfo *addr = NULL;
rc = getaddrinfo(host, port, NULL, &addr);
check(rc == 0, "Failed to lookup %s:%s", host, port);
int sock = socket(AF_INET, SOCK_STREAM, 0);
check(sock >= 0, "Cannot create a socket.");
rc = connect(sock, addr->ai_addr, addr->ai_addrlen);
check(rc == 0, "Connect failed.");
rc = nonblock(sock);
check(rc == 0, "Can't set nonblocking.");
freeaddrinfo(addr);
return sock;
error:
freeaddrinfo(addr);
return -1;
}
int read_some(RingBuffer *buffer, int fd, int is_socket)
{
int rc = 0;
if(RingBuffer_available_data(buffer) == 0) {
buffer->start = buffer->end = 0;
}
if(is_socket) {
rc = recv(fd, RingBuffer_starts_at(buffer), RingBuffer_available_space(buffer), 0);
} else {
rc = read(fd, RingBuffer_starts_at(buffer), RingBuffer_available_space(buffer));
}
check(rc >= 0, "Failed to read from fd: %d", fd);
RingBuffer_commit_write(buffer, rc);
return rc;
error:
return -1;
}
int write_some(RingBuffer *buffer, int fd, int is_socket)
{
int rc = 0;
bstring data = RingBuffer_get_all(buffer);
check(data != NULL, "Failed to get from the buffer.");
check(bfindreplace(data, &NL, &CRLF, 0) == BSTR_OK, "Failed to replace NL.");
if(is_socket) {
rc = send(fd, bdata(data), blength(data), 0);
} else {
rc = write(fd, bdata(data), blength(data));
}
check(rc == blength(data), "Failed to write everything to fd: %d.", fd);
bdestroy(data);
return rc;
error:
return -1;
}
int main(int argc, char *argv[])
{
fd_set allreads;
fd_set readmask;
int socket = 0;
int rc = 0;
RingBuffer *in_rb = RingBuffer_create(1024 * 10);
RingBuffer *sock_rb = RingBuffer_create(1024 * 10);
check(argc == 3, "USAGE: netclient host port");
socket = client_connect(argv[1], argv[2]);
check(socket >= 0, "connect to %s:%s failed.", argv[1], argv[2]);
FD_ZERO(&allreads);
FD_SET(socket, &allreads);
FD_SET(0, &allreads);
while(1) {
readmask = allreads;
rc = select(socket + 1, &readmask, NULL, NULL, NULL);
check(rc >= 0, "select failed.");
if(FD_ISSET(0, &readmask)) {
rc = read_some(in_rb, 0, 0);
check_debug(rc != -1, "Failed to read from stdin.");
}
if(FD_ISSET(socket, &readmask)) {
rc = read_some(sock_rb, socket, 0);
check_debug(rc != -1, "Failed to read from socket.");
}
while(!RingBuffer_empty(sock_rb)) {
rc = write_some(sock_rb, 1, 0);
check_debug(rc != -1, "Failed to write to stdout.");
}
while(!RingBuffer_empty(in_rb)) {
rc = write_some(in_rb, socket, 1);
check_debug(rc != -1, "Failed to write to socket.");
}
}
return 0;
error:
return -1;
}
```
代码中使用了`select`来处理`stdin`（文件描述符0）和用于和服务器交互的`socket`中的事件。它使用了`RingBuffer`来储存和复制数据，并且你可以认为`read_some`和`write_some`函数都是`RingBuffer`中相似函数的原型。
在这一小段代码中，可能有一些你并不知道的网络函数。当你碰到不知道的函数时，在手册页上查询它来确保你理解了它。这一小段代码可能需要让你研究用于小型服务器编程的所有C语言API。
## 你会看到什么
如果你完成了所有构建，测试的最快方式就是看看你能否从learncodethehardway.org上得到一个特殊的文件：
```sh
$
$ ./bin/netclient learncodethehardway.org 80
GET /ex45.txt HTTP/1.1
Host: learncodethehardway.org
HTTP/1.1 200 OK
Date: Fri, 27 Apr 2012 00:41:25 GMT
Content-Type: text/plain
Content-Length: 41
Last-Modified: Fri, 27 Apr 2012 00:42:11 GMT
ETag: 4f99eb63-29
Server: Mongrel2/1.7.5
Learn C The Hard Way, Exercise 45 works.
^C
$
```
这里我所做的事情是键入创建`/ex45.txt`的HTTP请求所需的语法，在`Host:`请求航之后，按下ENTER键来输入空行。接着我获取相应，包括响应头和内容。最后我按下CTRL-C来退出。
## 如何使它崩溃
这段代码肯定含有bug，但是当前在本书的草稿中，我会继续完成它。与此同时，尝试分析代码，并且用其它服务器来击溃它。一种叫做`netcat`的工具可以用于建立这种服务器。另一种方法就是使用`Python`或`Ruby`之类的语言创建一个简单的“垃圾服务器”，来产生垃圾数据，随机关闭连接，或者其它异常行为。
如果你找到了bug，在评论中报告它们，我会修复它。
## 附加题
+ 像我提到的那样，这里面有一些你不知道的函数，去查询他们。实际上，即使你知道它们也要查询。
+ 在`valgrind`下运行它来寻找错误。
+ 为函数添加各种防御性编程检查，来改进它们。
+ 使用`getopt`函数，运行用户提供选项来防止将`\n`转换为`\r\n`。这仅仅用于需要处理行尾的协议例如HTTP。有时你可能不想执行转换，所以要给用户一个选择。
';
练习44：环形缓冲区
最后更新于：2022-04-01 23:29:38
# 练习44：环形缓冲区
> 原文：[Exercise 44: Ring Buffer](http://c.learncodethehardway.org/book/ex44.html)
> 译者：[飞龙](https://github.com/wizardforcel)
环形缓冲区在处理异步IO时非常实用。它们可以在一端接收随机长度和区间的数据，在另一端以相同长度和区间提供密致的数据块。它们是`Queue`数据结构的变体，但是它针对于字节块而不是一系列指针。这个练习中我打算向你展示`RingBuffer`的代码，并且之后你需要对它执行完整的单元测试。
```c
#ifndef _lcthw_RingBuffer_h
#define _lcthw_RingBuffer_h
#include
typedef struct {
char *buffer;
int length;
int start;
int end;
} RingBuffer;
RingBuffer *RingBuffer_create(int length);
void RingBuffer_destroy(RingBuffer *buffer);
int RingBuffer_read(RingBuffer *buffer, char *target, int amount);
int RingBuffer_write(RingBuffer *buffer, char *data, int length);
int RingBuffer_empty(RingBuffer *buffer);
int RingBuffer_full(RingBuffer *buffer);
int RingBuffer_available_data(RingBuffer *buffer);
int RingBuffer_available_space(RingBuffer *buffer);
bstring RingBuffer_gets(RingBuffer *buffer, int amount);
#define RingBuffer_available_data(B) (((B)->end + 1) % (B)->length - (B)->start - 1)
#define RingBuffer_available_space(B) ((B)->length - (B)->end - 1)
#define RingBuffer_full(B) (RingBuffer_available_data((B)) - (B)->length == 0)
#define RingBuffer_empty(B) (RingBuffer_available_data((B)) == 0)
#define RingBuffer_puts(B, D) RingBuffer_write((B), bdata((D)), blength((D)))
#define RingBuffer_get_all(B) RingBuffer_gets((B), RingBuffer_available_data((B)))
#define RingBuffer_starts_at(B) ((B)->buffer + (B)->start)
#define RingBuffer_ends_at(B) ((B)->buffer + (B)->end)
#define RingBuffer_commit_read(B, A) ((B)->start = ((B)->start + (A)) % (B)->length)
#define RingBuffer_commit_write(B, A) ((B)->end = ((B)->end + (A)) % (B)->length)
#endif
```
观察这个数据结构，你会看到它含有`buffer`、`start` 和 `end`。`RingBuffer`的所做的事情只是在`buffer`中移动`start`和`end`，所以当数据到达缓冲区末尾时还可以继续“循环”。这样就会给人一种在固定空间内无限读取的“幻觉”。接下来我创建了一些宏来基于它执行各种计算。
下面是它的实现，它是对工作原理更好的解释：
```c
#undef NDEBUG
#include
#include
#include
#include
#include
#include
RingBuffer *RingBuffer_create(int length)
{
RingBuffer *buffer = calloc(1, sizeof(RingBuffer));
buffer->length = length + 1;
buffer->start = 0;
buffer->end = 0;
buffer->buffer = calloc(buffer->length, 1);
return buffer;
}
void RingBuffer_destroy(RingBuffer *buffer)
{
if(buffer) {
free(buffer->buffer);
free(buffer);
}
}
int RingBuffer_write(RingBuffer *buffer, char *data, int length)
{
if(RingBuffer_available_data(buffer) == 0) {
buffer->start = buffer->end = 0;
}
check(length <= RingBuffer_available_space(buffer),
"Not enough space: %d request, %d available",
RingBuffer_available_data(buffer), length);
void *result = memcpy(RingBuffer_ends_at(buffer), data, length);
check(result != NULL, "Failed to write data into buffer.");
RingBuffer_commit_write(buffer, length);
return length;
error:
return -1;
}
int RingBuffer_read(RingBuffer *buffer, char *target, int amount)
{
check_debug(amount <= RingBuffer_available_data(buffer),
"Not enough in the buffer: has %d, needs %d",
RingBuffer_available_data(buffer), amount);
void *result = memcpy(target, RingBuffer_starts_at(buffer), amount);
check(result != NULL, "Failed to write buffer into data.");
RingBuffer_commit_read(buffer, amount);
if(buffer->end == buffer->start) {
buffer->start = buffer->end = 0;
}
return amount;
error:
return -1;
}
bstring RingBuffer_gets(RingBuffer *buffer, int amount)
{
check(amount > 0, "Need more than 0 for gets, you gave: %d ", amount);
check_debug(amount <= RingBuffer_available_data(buffer),
"Not enough in the buffer.");
bstring result = blk2bstr(RingBuffer_starts_at(buffer), amount);
check(result != NULL, "Failed to create gets result.");
check(blength(result) == amount, "Wrong result length.");
RingBuffer_commit_read(buffer, amount);
assert(RingBuffer_available_data(buffer) >= 0 && "Error in read commit.");
return result;
error:
return NULL;
}
```
这些就是一个基本的`RingBuffer`实现的全部了。你可以从中读取和写入数据，获得它的大小和容量。也有一些缓冲区使用OS中的技巧来创建虚拟的无限存储，但它们不可移植。
由于我的`RingBuffer`处理读取和写入内存块，我要保证任何`end == start`出现的时候我都要将它们重置为0，使它们从退回缓冲区头部。在维基百科上的版本中，它并不可以写入数据块，所以只能移动`end`和`start`来转圈。为了更好地处理数据块，你需要在数据为空时移动到内部缓冲区的开头。
## 单元测试
对于你的单元测试，你需要测试尽可能多的情况。最简单的方法就是预构造不同的`RingBuffer`结构，之后手动检查函数和算数是否有效。例如，你可以构造`end`在缓冲区末尾的右边，而`start`在缓冲区范围内的`RingBuffer`，来看看它是否执行成功。
## 你会看到什么
下面是我的`ringbuffer_tests`运行结果：
```sh
$ ./tests/ringbuffer_tests
DEBUG tests/ringbuffer_tests.c:60: ----- RUNNING: ./tests/ringbuffer_tests
----
RUNNING: ./tests/ringbuffer_tests
DEBUG tests/ringbuffer_tests.c:53:
----- test_create
DEBUG tests/ringbuffer_tests.c:54:
----- test_read_write
DEBUG tests/ringbuffer_tests.c:55:
----- test_destroy
ALL TESTS PASSED
Tests run: 3
$
```
你应该测试至少三次来确保所有基本操作有效，并且看看在我完成之前你能测试到额外的多少东西。
## 如何改进
像往常一样，你应该为这个练习做防御性编程检查。我希望你这样做，是因为` liblcthw`的代码基本上没有做我教给你的防御型编程检查。我将它们留给你，便于你熟悉使用这些额外的检查来改进代码。
例如，这个环形缓冲区并没有过多检查每次访问是否实际上都在缓冲区内。
如果你阅读[环形缓冲区的维基百科页面](http://en.wikipedia.org/wiki/Ring_buffer)，你会看到“优化的POSIX实现”，它使用POSIX特定的调用来创建一块无限的区域。研究并且在附加题中尝试实现它。
## 附加题
+ 创建`RingBuffer`的替代版本，使用POSIX的技巧并为其执行单元测试。
+ 为二者添加一个性能对比测试，通过带有随机数据和随机读写操作的模糊测试来比较两个版本。确保你你对每个版本进行了相同的操作，便于你在操作之间比较二者。
+ 使用`callgrind` 和 `cachegrind`比较二者的性能。
';
练习43：一个简单的统计引擎
最后更新于：2022-04-01 23:29:35
# 练习43：一个简单的统计引擎
> 原文：[Exercise 43: A Simple Statistics Engine](http://c.learncodethehardway.org/book/ex43.html)
> 译者：[飞龙](https://github.com/wizardforcel)
这是一个简单的算法，我将其用于“联机”（不储存任何样本）收集概要统计。我在任何需要执行一些统计，比如均值、标准差和求和中使用它，但是其中我并不会储存所需的全部样本。我只需要储存计算出的结果，它们仅仅含有5个数值。
## 计算标准差和均值
首先你需要一系列样本。它可以使任何事情，比如完成一个任务所需的时间，某人访问某个东西的次数，或者甚至是网站的评分。是什么并不重要，只要你能得到一些数字，并且你想要知道它们的下列概要统计值：
`sum`
对所有数字求和。
`sumsq`（平方和）
对所有数字求平方和。
`count(n)`
求出样本数量。
`min`
求出样本最小值。
`max`
求出样本最大值。
`mean`
求出样本的均值。它类似于但又不是中位数，但可作为中位数的估计。
`stddev`
使用`$sqrt(sumsq - (sum * mean) / (n - 1) )`来计算标准差，其中`sqrt`为`math.h`头文件中的平方根。
我将会使用R来验证这些计算，因为我知道R能够计算正确。
```r
> s <- runif(n=10, max=10)
> s
[1] 6.1061334 9.6783204 1.2747090 8.2395131 0.3333483 6.9755066 1.0626275
[8] 7.6587523 4.9382973 9.5788115
> summary(s)
Min. 1st Qu. Median Mean 3rd Qu. Max.
0.3333 2.1910 6.5410 5.5850 8.0940 9.6780
> sd(s)
[1] 3.547868
> sum(s)
[1] 55.84602
> sum(s * s)
[1] 425.1641
> sum(s) * mean(s)
[1] 311.8778
> sum(s * s) - sum(s) * mean(s)
[1] 113.2863
> (sum(s * s) - sum(s) * mean(s)) / (length(s) - 1)
[1] 12.58737
> sqrt((sum(s * s) - sum(s) * mean(s)) / (length(s) - 1))
[1] 3.547868
>
```
你并不需要懂得R，只需要看着我拆分代码来解释如何检查这些运算：
lines 1-4
我使用`runit`函数来获得“随机形式”的数字分布，之后将它们打印出来。我会在接下来的单元测试中用到它。
lines 5-7
这个就是概要，便于你看到R如何计算它们。
lines 8-9
这是使用`sd`函数计算的`stddev`。
lines 10-11
现在我开始手动进行这一计算，首先计算`sum`。
lines 12-13
`stddev`公式中的下一部分是`sumsq`，我可以通过`sum(s * s)`来得到，它告诉R将整个`s`列表乘以其自身，之后计算它们的`sum`。R的可以在整个数据结构上做运算，就像这样。
lines 14-15
观察那个公式，我之后需要`sum`乘上`mean`，所以我执行了`sum(s) * mean(s)`。
lines 16-17
我接着将`sumsq`参与运算，得到`sum(s * s) - sum(s) * mean(s)`。
lines 18-19
还需要除以`n - 1`，所以我执行了`(sum(s * s) - sum(s) * mean(s)) / (length(s) - 1)`。
lines 20-21
随后，我使用`sqrt`算出平方根，并得到3.547868，它符合R通过`sd`的运算结果。
## 实现
这就是计算`stddev`的方法，现在我可以编写一些简单的代码来实现这一计算。
```c
#ifndef lcthw_stats_h
#define lctwh_stats_h
typedef struct Stats {
double sum;
double sumsq;
unsigned long n;
double min;
double max;
} Stats;
Stats *Stats_recreate(double sum, double sumsq, unsigned long n, double min, double max);
Stats *Stats_create();
double Stats_mean(Stats *st);
double Stats_stddev(Stats *st);
void Stats_sample(Stats *st, double s);
void Stats_dump(Stats *st);
#endif
```
这里你可以看到我将所需的统计量放入一个struct，并且创建了用于处理样本和获得数值的函数。实现它只是转换数字的一个练习：
```c
#include
#include
#include
#include
Stats *Stats_recreate(double sum, double sumsq, unsigned long n, double min, double max)
{
Stats *st = malloc(sizeof(Stats));
check_mem(st);
st->sum = sum;
st->sumsq = sumsq;
st->n = n;
st->min = min;
st->max = max;
return st;
error:
return NULL;
}
Stats *Stats_create()
{
return Stats_recreate(0.0, 0.0, 0L, 0.0, 0.0);
}
double Stats_mean(Stats *st)
{
return st->sum / st->n;
}
double Stats_stddev(Stats *st)
{
return sqrt( (st->sumsq - ( st->sum * st->sum / st->n)) / (st->n - 1) );
}
void Stats_sample(Stats *st, double s)
{
st->sum += s;
st->sumsq += s * s;
if(st->n == 0) {
st->min = s;
st->max = s;
} else {
if(st->min > s) st->min = s;
if(st->max < s) st->max = s;
}
st->n += 1;
}
void Stats_dump(Stats *st)
{
fprintf(stderr, "sum: %f, sumsq: %f, n: %ld, min: %f, max: %f, mean: %f, stddev: %f",
st->sum, st->sumsq, st->n, st->min, st->max,
Stats_mean(st), Stats_stddev(st));
}
```
下面是` stats.c`中每个函数的作用：
Stats_recreate
我希望从一些数据中加载这些数据，这和函数让我重新创建`Stats`结构体。
Stats_create
只是以全0的值调用`Stats_recreate`。
Stats_mean
使用`sum`和`n`计算均值。
Stats_stddev
实现我之前的公式，唯一的不同就是我使用`t->sum / st->n`来计算均值，而不是调用`Stats_mean`。
Stats_sample
它用于在`Stats`结构体中储存数值。当你向它提供数值时，它看到`n`是0，并且相应地设置`min`和`max`。之后的每次调用都会使`sum`、`sumsq`和`n`增加，并且计算出这一新的样本的`min`和`max`值。
Stats_dump
简单的调试函数，用于转储统计量，便于你看到它们。
我需要干的最后一件事，就是确保这些运算正确。我打算使用我的样本，以及来自于R会话中的计算结果创建单元测试，来确保我会得到正确的结果。
```c
#include "minunit.h"
#include
#include
const int NUM_SAMPLES = 10;
double samples[] = {
6.1061334, 9.6783204, 1.2747090, 8.2395131, 0.3333483,
6.9755066, 1.0626275, 7.6587523, 4.9382973, 9.5788115
};
Stats expect = {
.sumsq = 425.1641,
.sum = 55.84602,
.min = 0.333,
.max = 9.678,
.n = 10,
};
double expect_mean = 5.584602;
double expect_stddev = 3.547868;
#define EQ(X,Y,N) (round((X) * pow(10, N)) == round((Y) * pow(10, N)))
char *test_operations()
{
int i = 0;
Stats *st = Stats_create();
mu_assert(st != NULL, "Failed to create stats.");
for(i = 0; i < NUM_SAMPLES; i++) {
Stats_sample(st, samples[i]);
}
Stats_dump(st);
mu_assert(EQ(st->sumsq, expect.sumsq, 3), "sumsq not valid");
mu_assert(EQ(st->sum, expect.sum, 3), "sum not valid");
mu_assert(EQ(st->min, expect.min, 3), "min not valid");
mu_assert(EQ(st->max, expect.max, 3), "max not valid");
mu_assert(EQ(st->n, expect.n, 3), "max not valid");
mu_assert(EQ(expect_mean, Stats_mean(st), 3), "mean not valid");
mu_assert(EQ(expect_stddev, Stats_stddev(st), 3), "stddev not valid");
return NULL;
}
char *test_recreate()
{
Stats *st = Stats_recreate(expect.sum, expect.sumsq, expect.n, expect.min, expect.max);
mu_assert(st->sum == expect.sum, "sum not equal");
mu_assert(st->sumsq == expect.sumsq, "sumsq not equal");
mu_assert(st->n == expect.n, "n not equal");
mu_assert(st->min == expect.min, "min not equal");
mu_assert(st->max == expect.max, "max not equal");
mu_assert(EQ(expect_mean, Stats_mean(st), 3), "mean not valid");
mu_assert(EQ(expect_stddev, Stats_stddev(st), 3), "stddev not valid");
return NULL;
}
char *all_tests()
{
mu_suite_start();
mu_run_test(test_operations);
mu_run_test(test_recreate);
return NULL;
}
RUN_TESTS(all_tests);
```
这个单元测试中没什么新东西，除了`EQ`宏。我比较懒，并且不想查询比较两个`double`值的标准方法，所以我使用了这个宏。`double`的问题是等性不是完全相等，因为我使用了两个不同的系统，并带有不同的四舍五入的位数。解决方案就是判断两个数“乘以10的X次方是否相等”。
我使用`EQ`来计算数字的10的幂，之后使用`round`函数来获得证书。这是个简单的方法来四舍五入N位小数，并以整数比较结果。我确定有数以亿计的其它方法能做相同的事情，但是现在我就用这种。
预期结果储存在`Stats` `struct`中，之后我只是确保我得到的数值接近R给我的数值。
## 如何使用
你可以使用标准差和均值来决定一个新的样本是否是“有趣”的，或者你可以使用它们计算统计量的统计量。前者对于人们来说更容易理解，所以我用登录的例子来做个简短的解释。
假设你在跟踪人们花费多长时间在一台服务器上，并且你打算用统计来分析它。每次有人登录进来，你都对它们在这里的时长保持跟踪，之后调用`Stats_sample`函数。我会寻找停留“过长”时间的人，以及“过短”的人。
比起设定特殊的级别，我更倾向于将一个人的停留时间与`mean (plus or minus) 2 * stddev`这个范围进行比较。我计算出`mean`和`2 * stddev`，并且如果它们在这个范围之外，我就认为是“有趣”的。由于我使用了联机算法来维护这些统计量，所以它非常快，并且我可以使软件标记在这个范围外的用户。
这不仅仅用于找出行为异常的用户，更有助于标记一些潜在的问题，你可以查看它们来观察发生了什么。它基于所有用户的行为来计算，这也避免了你任意挑出一个数值而并不基于实际情况的问题。
你可以从中学到的通用规则是，`mean (plus or minus) 2 * stddev`是90%的值预期所属的范围预测值，任何在它之外的值都是有趣的。
第二种利用这些统计量的方式就是继续将其用于其它的`Stats`计算。基本上像通常一样使用`Stats_sample`，但是之后在`min`、`max`、`n`、`mean`和`stddev`上执行`Stats_sample`。这会提供二级的度量，并且让你对比样本的样本。
被搞晕了吗？我会以上面的例子基础，并且假设你拥有100台服务器，每台都运行一个应用。你已经在每个应用服务器上跟踪了用户的登录时长，但是你想要比较所有的这100和应用，并且标记它们当中任何登录时间过长的用户。最简单的方式就是每次有人登录进来时，计算新的登录统计量，之后将`Stats structs`的元素添加到第二个`Stats`中。
你最后应该会得到一些统计量，它们可以这样命名：
均值的均值
这是一个`Stats struct`，它向你提供所有服务器的均值的`mean`和`stddev`。你可以用全局视角来观察任何在此之外的用户或服务器。
标准差的均值
另一个`Stats struct`，计算这些服务器的分布的统计量。你之后可以分析每个服务器并且观察是否它们中的任何服务器具有异常分散的分布，通过将它们的`stddev`和这个`mean of stddevs`统计量进行对比。
你可以计算出全部统计量，但是这两个是最有用的。如果你打算监视服务器上的移除登录时间，你可以这样做：
+ 用户John登录并登出服务器A。获取服务器A的统计量，并更新它们。
+ 获取`mean of means`统计量，计算出A的均值并且将其加入样本。我叫它`m_of_m`。
+ 获取`mean of stddev`统计量，将A的标准差添加到样本中。我叫它` m_of_s`。
+ 如果A的`mean`在`m_of_m.mean + 2 * m_of_m.stddev`范围外，标记它可能存在问题。
+ 如果A的`stddev`在`m_of_s.mean + 2 * m_of_s.stddev`范围外，标记它可能存在行为异常。
+ 最后，如果John的登录时长在A的范围之外，或A的`m_of_m`范围之外，标记为有趣的。
通过计算“均值的均值”，或者“标准差的均值”，你可以以最小的执行和储存总量，有效地跟踪许多度量。
## 附加题
+ 将`Stats_stddev` 和 `Stats_mean`转换为`static inline`函数，放到`stats.h`文件中，而不是`stats.c`文件。
+ 使用这份代码来编写`string_algos_test.c`的性能测试。使它为可选的，并且运行基准测试作为一系列样本，之后报告结果。
+ 编写它的另一个语言的版本。确保这个版本基于我的数据正确执行。
+ 编写一个小型程序，它能从文件读取所有数字，并执行这些统计。
+ 使程序接收一个数据表，其中第一行是表头，剩下的行含有任意数量空格分隔的数值。你的程序应该按照表头中的名称，打印出每一列的统计值。
';
练习42：栈和队列
最后更新于：2022-04-01 23:29:33
# 练习42：栈和队列
> 原文：[Exercise 42: Stacks and Queues](http://c.learncodethehardway.org/book/ex42.html)
> 译者：[飞龙](https://github.com/wizardforcel)
到现在为止，你已经知道了大多数用于构建其它数据结构的数据结构。如果你拥有一些`List`、`DArray`、`Hashmap` 和 `Tree`，你就能用他们构造出大多数其它的任何结构。你碰到的其它任何结构要么可以用它们实现，要么是它们的变体。如果不是的话，它可能是外来的数据结构，你可能不需要它。
`Stack`和`Queue`是非常简单的数据结构，它们是`List`的变体。它们是`List`的弱化或者转换形式，因为你只需要在`List`的一端放置元素。对于`Stack`，你只能能够在一段压入和弹出元素。而对于`Queue`，你只能够在开头压入元素，并在末尾弹出（或者反过来）。
我能够只通过C预处理器和两个头文件来实现这两个数据结构。我的头文件只有21行的长度，并且实现了所有`Stack`和`Queue`的操作，不带有任何神奇的定义。
我将会向你展示单元测试，你需要实现头文件来让它们正常工作。你不能创建`stack.c` 或 `queue.c`实现文件来通过测试，只能使用`stack.h` 和 `queue.h`来使测试运行。
```c
#include "minunit.h"
#include
#include
static Stack *stack = NULL;
char *tests[] = {"test1 data", "test2 data", "test3 data"};
#define NUM_TESTS 3
char *test_create()
{
stack = Stack_create();
mu_assert(stack != NULL, "Failed to create stack.");
return NULL;
}
char *test_destroy()
{
mu_assert(stack != NULL, "Failed to make stack #2");
Stack_destroy(stack);
return NULL;
}
char *test_push_pop()
{
int i = 0;
for(i = 0; i < NUM_TESTS; i++) {
Stack_push(stack, tests[i]);
mu_assert(Stack_peek(stack) == tests[i], "Wrong next value.");
}
mu_assert(Stack_count(stack) == NUM_TESTS, "Wrong count on push.");
STACK_FOREACH(stack, cur) {
debug("VAL: %s", (char *)cur->value);
}
for(i = NUM_TESTS - 1; i >= 0; i--) {
char *val = Stack_pop(stack);
mu_assert(val == tests[i], "Wrong value on pop.");
}
mu_assert(Stack_count(stack) == 0, "Wrong count after pop.");
return NULL;
}
char *all_tests() {
mu_suite_start();
mu_run_test(test_create);
mu_run_test(test_push_pop);
mu_run_test(test_destroy);
return NULL;
}
RUN_TESTS(all_tests);
```
之后是`queue_tests.c`，几乎以相同的方式来使用`Queue`：
```c
#include "minunit.h"
#include
#include
static Queue *queue = NULL;
char *tests[] = {"test1 data", "test2 data", "test3 data"};
#define NUM_TESTS 3
char *test_create()
{
queue = Queue_create();
mu_assert(queue != NULL, "Failed to create queue.");
return NULL;
}
char *test_destroy()
{
mu_assert(queue != NULL, "Failed to make queue #2");
Queue_destroy(queue);
return NULL;
}
char *test_send_recv()
{
int i = 0;
for(i = 0; i < NUM_TESTS; i++) {
Queue_send(queue, tests[i]);
mu_assert(Queue_peek(queue) == tests[0], "Wrong next value.");
}
mu_assert(Queue_count(queue) == NUM_TESTS, "Wrong count on send.");
QUEUE_FOREACH(queue, cur) {
debug("VAL: %s", (char *)cur->value);
}
for(i = 0; i < NUM_TESTS; i++) {
char *val = Queue_recv(queue);
mu_assert(val == tests[i], "Wrong value on recv.");
}
mu_assert(Queue_count(queue) == 0, "Wrong count after recv.");
return NULL;
}
char *all_tests() {
mu_suite_start();
mu_run_test(test_create);
mu_run_test(test_send_recv);
mu_run_test(test_destroy);
return NULL;
}
RUN_TESTS(all_tests);
```
你应该在不修改测试文件的条件下，使单元测试能够运行，并且它应该能够通过`valgrind`而没有任何内存错误。下面是当我直接运行`stack_tests`时它的样子：
```sh
$ ./tests/stack_tests
DEBUG tests/stack_tests.c:60: ----- RUNNING: ./tests/stack_tests
----
RUNNING: ./tests/stack_tests
DEBUG tests/stack_tests.c:53:
----- test_create
DEBUG tests/stack_tests.c:54:
----- test_push_pop
DEBUG tests/stack_tests.c:37: VAL: test3 data
DEBUG tests/stack_tests.c:37: VAL: test2 data
DEBUG tests/stack_tests.c:37: VAL: test1 data
DEBUG tests/stack_tests.c:55:
----- test_destroy
ALL TESTS PASSED
Tests run: 3
$
```
`queue_test`的输出基本一样，所以我在这里就不展示了。
## 如何改进
你可以做到的唯一真正的改进，就是把所用的`List`换成`DArray`。`Queue`数据结构难以用`DArray`实现，因为它要同时处理两端的节点。
完全在头文件中来实现它们的缺点，是你并不能够轻易地对它做性能调优。你需要使用这种技巧，建立一种以特定的方式使用`List`的“协议”。做性能调优时，如果你优化了`List`，这两种数据结构都会有所改进。
## 附加题
+ 使用`DArray`代替`List`实现`Stack`，并保持单元测试不变。这意味着你需要创建你自己的`STACK_FOREACH`。
';
练习41：将 Cachegrind 和 Callgrind 用于性能调优
最后更新于：2022-04-01 23:29:31
# 练习41：将 Cachegrind 和 Callgrind 用于性能调优
> 原文：[Exercise 41: Using Cachegrind And Callgrind For Performance Tuning](http://c.learncodethehardway.org/book/ex41.html)
> 译者：[飞龙](https://github.com/wizardforcel)
这个练习中，我打算上一节速成课，内容是使用`Valgrind`的两个工具`callgrind`和`cachegrind`。这两个工具会分析你程序的执行，并且告诉你哪一部分运行缓慢。这些结果非常精确，因为`Valgrind`的工作方式有助于你解决一些问题，比如执行过多的代码行，热点，内容访问问题，甚至是CPU的缓存未命中。
为了做这个练习，我打算使用`bstree_tests`单元测试，你之前用于寻找能提升算法的地方。你需要确保你这些程序的版本没有任何`valgrind`错误，并且和我的代码非常相似，因为我会使用我的代码的转储来谈论`cachegrind`和`callgrind`如何工作。
## 运行 Callgrind
为了运行Callgrind，你需要向`valgrind`传入`--tool=callgrind`选项，之后它会产生`callgrind.out.PID`文件（其中PID为所运行程序的进程PID）。一旦你这样运行了，你就可以使用一个叫做`callgrind_annotate`的工具分析`callgrind.out`文件，它会告诉你哪个函数运行中使用了最多的指令。下面是个例子，我在`bstree_tests`上运行了`callgrind`，之后得到了这个信息：
```sh
$ valgrind --dsymutil=yes --tool=callgrind tests/bstree_tests
...
$ callgrind_annotate callgrind.out.1232
--------------------------------------------------------------------------------
Profile data file 'callgrind.out.1232' (creator: callgrind-3.7.0.SVN)
--------------------------------------------------------------------------------
I1 cache:
D1 cache:
LL cache:
Timerange: Basic block 0 - 1098689
Trigger: Program termination
Profiled target: tests/bstree_tests (PID 1232, part 1)
Events recorded: Ir
Events shown: Ir
Event sort order: Ir
Thresholds: 99
Include dirs:
User annotated:
Auto-annotation: off
--------------------------------------------------------------------------------
Ir
--------------------------------------------------------------------------------
4,605,808 PROGRAM TOTALS
--------------------------------------------------------------------------------
Ir file:function
--------------------------------------------------------------------------------
670,486 src/lcthw/bstrlib.c:bstrcmp [tests/bstree_tests]
194,377 src/lcthw/bstree.c:BSTree_get [tests/bstree_tests]
65,580 src/lcthw/bstree.c:default_compare [tests/bstree_tests]
16,338 src/lcthw/bstree.c:BSTree_delete [tests/bstree_tests]
13,000 src/lcthw/bstrlib.c:bformat [tests/bstree_tests]
11,000 src/lcthw/bstrlib.c:bfromcstralloc [tests/bstree_tests]
7,774 src/lcthw/bstree.c:BSTree_set [tests/bstree_tests]
5,800 src/lcthw/bstrlib.c:bdestroy [tests/bstree_tests]
2,323 src/lcthw/bstree.c:BSTreeNode_create [tests/bstree_tests]
1,183 /private/tmp/pkg-build/coregrind//vg_preloaded.c:vg_cleanup_env [/usr/local/lib/valgrind/vgpreload_core-amd64-darwin.so]
$
```
我已经移除了单元测试和`valgrind`输出，因为它们对这个练习没有用。你应该看到了`callgrind_anotate`输出，它向你展示了每个函数所运行的指令数量（`valgrind`中叫做`Ir`），由高到低排序。你通常可以忽略头文件的数据，直接跳到函数列表。
> 注
> 如果你获取到一堆“???:Image”的行，并且它们不是你程序中的东西，那么你读到的是OS的垃圾。只需要在末尾添加`| grep -v "???"`来过滤掉它们。
我现在可以对这个输出做个简短的分解，来找出下一步观察什么：
+ 每一行都列出了`Ir`序号和执行它们的`file:function `。`Ir`是指令数量，并且如果它越少就越快。这里有些复杂，但是首先要着眼于`Ir`。
+ 解决这个程序的方式是观察最上面的函数，之后看看你首先可以改进哪一个。这里，我可以改进`bstrcmp`或者`BStree_get`。可能以`BStree_get`开始更容易些。
+ 这些函数的一部分由单元测试调用，所以我可以忽略它们。类似`bformat`，`bfromcstralloc`和 `bdestroy`就是这样的函数。
+ 我也可以找到我可以简单地避免调用的函数。例如，或许我可以假设`BSTree`仅仅处理`bstring`键，之后我可以不使用回调系统，并且完全移除`default_compare`。
到目前为止，我只知道我打算改进`BSTree_get`，并且不是因为`BSTree_get`执行慢。这是分析的第二阶段。
## Callgrind 注解源文件
下一步我使用`callgrind_annotate`输出`bstree.c`文件，并且使用所带有的`Ir`对每一行做注解。你可以通过运行下面的命令来得到注解后的源文件：
```sh
$ callgrind_annotate callgrind.out.1232 src/lcthw/bstree.c
...
```
你的输出会是这个源文件的一个较大的转储，但是我会将它们剪切成包含`BSTree_get`和`BSTree_getnode`的部分：
```
--------------------------------------------------------------------------------
-- User-annotated source: src/lcthw/bstree.c
--------------------------------------------------------------------------------
Ir
2,453 static inline BSTreeNode *BSTree_getnode(BSTree *map, BSTreeNode *node, void *key)
. {
61,853 int cmp = map->compare(node->key, key);
663,908 => src/lcthw/bstree.c:default_compare (14850x)
.
14,850 if(cmp == 0) {
. return node;
24,794 } else if(cmp < 0) {
30,623 if(node->left) {
. return BSTree_getnode(map, node->left, key);
. } else {
. return NULL;
. }
. } else {
13,146 if(node->right) {
. return BSTree_getnode(map, node->right, key);
. } else {
. return NULL;
. }
. }
. }
.
. void *BSTree_get(BSTree *map, void *key)
4,912 {
24,557 if(map->root == NULL) {
14,736 return NULL;
. } else {
. BSTreeNode *node = BSTree_getnode(map, map->root, key);
2,453 return node == NULL ? NULL : node->data;
. }
. }
```
每一行都显示它的`Ir`（指令）数量，或者一个点（`.`）来表示它并不重要。我所要找的就是一些热点，或者带有巨大数值的`Ir`的行，它能够被优化掉。这里，第十行的输出表明，`BSTree_getnode`开销非常大的原因是它调用了`default_comapre`，它又调用了`bstrcmp`。我已经知道了`bstrcmp`是性能最差的函数，所以如果我想要改进`BSTree_getnode`的速度，我应该首先解决掉它。
之后我以相同方式查看`bstrcmp`：
```
98,370 int bstrcmp (const_bstring b0, const_bstring b1) {
. int i, v, n;
.
196,740 if (b0 == NULL || b1 == NULL || b0->data == NULL || b1->data == NULL ||
32,790 b0->slen < 0 || b1->slen < 0) return SHRT_MIN;
65,580 n = b0->slen; if (n > b1->slen) n = b1->slen;
89,449 if (b0->slen == b1->slen && (b0->data == b1->data || b0->slen == 0))
. return BSTR_OK;
.
23,915 for (i = 0; i < n; i ++) {
163,642 v = ((char) b0->data[i]) - ((char) b1->data[i]);
. if (v != 0) return v;
. if (b0->data[i] == (unsigned char) '\0') return BSTR_OK;
. }
.
. if (b0->slen > n) return 1;
. if (b1->slen > n) return -1;
. return BSTR_OK;
. }
```
输出中让我预料之外的事情就是`bstrcmp`最糟糕的一行并不是我想象中的字符比较。对于内存访问，顶部的防御性`if`语句将所有可能的无效变量都检查了一遍。与第十七行比较字符的语句相比，这个`if`语句进行了多于两倍的内存访问。如果我要优化`bstcmp`，我会完全把它去掉，或者在其它一些地方来执行它。
另一种选择是将这个检查改为`assert`，它只在开发时的运行中存在，之后在发布时把它去掉。我没有足够的证明来表明这行代码不适于这个数据结构，所以我可以证明移除它是可行的。
然而，我并不想弱化这个函数的防御性，来得到一些性能。在真实的性能优化环境，我会简单地把它放到列表中，之后挖掘程序中能得到的其它收益。
## 调优之道
> 我们应该忽略微小的效率，对于97%的情况：过早优化是万恶之源。
> -- 高德纳
在我看来，这个引述似乎忽略了一个关于性能调优的重点。在高德纳的话中，当你做性能调优时，如果你过早去做它，可能会导致各种问题。根据他的话，优化应该执行于“稍晚的某个时间”，或者这只是我的猜测。谁知道呢。
我打算澄清这个引述并不是完全错误，而是忽略了某些东西，并且我打算给出我的引述。你可以引用我的这段话：
> 使用证据来寻找最大的优化并花费最少的精力。
> -- 泽德 A. 肖
你什么时候优化并不重要，但是你需要弄清楚你的优化是否真正能改进软件，以及需要投入多少精力来实现它。通过证据你就可以找到代码中的位置，用一点点精力就能取得最大的提升。通常这些地方都是一些愚蠢的决定，就像`bstrcmp`试图检查任何东西不为`NULL`一样。
在某个特定时间点上，代码中需要调优的地方只剩下极其微小的优化，比如重新组织`if`语句，或者类似达夫设备这样的特殊循环。这时候，你应该停止优化，因为这是一个好机会，你可以通过重新设计软件并且避免这些事情来获得更多收益。
这是一些只想做优化的程序员没有看到的事情。许多时候，把一件事情做快的最好方法就是寻找避免它们的办法。在上面的分析中，我不打算优化`bstrcmp`，我会寻找一个不使用它的方法。也许我可以使用一种哈希算法来执行可排序的哈希计算而不是始终使用`bstrcmp`。也许我可以通过首先尝试第一个字符，如果它们不匹配就没必要调用`bstrcmp`。
如果在此之后你根本不能重新设计，那么就开始寻找微小的优化，但是要始终确保它们能够提升速度。要记住目标是使用最少的精力尽可能得到最大的效果。
## 使用 KCachegrind
这个练习最后一部分就是向你介绍一个叫做[KCachegrind](http://kcachegrind.sourceforge.net/html/Home.html)的神奇的GUI工具，用于分析`callgrind` 和 `cachegrind`的输出。我使用Linux或BSD电脑上工作时几乎都会使用它，并且我实际上为了使用`KCachegrind`而切换到Linux来编写代码。
教会你如何使用是这个练习之外的内容，你需要在这个练习之后自己学习如何用它。输出几乎是相同的，除了`KCachegrind`可以让你做这些：
+ 图形化地浏览源码和执行次数，并使用各种排序来搜索可优化的东西。
+ 分析不同的图表，来可视化地观察什么占据了大多数时间，以及它调用了什么。
+ 查看真实的汇编机器码输出，使你能够看到实际的指令，给你更多的线索。
+ 可视化地显示源码中的循环和分支的跳跃方式，便于你更容易地找到优化代码的方法。
你应该在获取、安装和玩转`KCachegrind`上花一些时间。
## 附加题
+ 阅读[ callgrind 手册页](http://valgrind.org/docs/manual/cl-manual.html)并且尝试一些高级选项。
+ 阅读[ cachegrind 手册页](http://valgrind.org/docs/manual/cg-manual.html)并且也尝试一些高级选项。
+ 在所有单元测试上使用`callgrind` 和 `cachegrind`，看看你能否找到可优化的地方。你找到一些预料之外的事情了吗？如果没有，你可能观察地不够仔细。
+ 使用 KCachegrind 并且观察它和我这里的输出有什么不同。
+ 现在使用这些工具来完成练习40的附加题和改进部分。
';
练习40：二叉搜索树
最后更新于：2022-04-01 23:29:28
# 练习40：二叉搜索树
> 原文：[Exercise 40: Binary Search Trees](http://c.learncodethehardway.org/book/ex40.html)
> 译者：[飞龙](https://github.com/wizardforcel)
二叉树是最简单的树形数据结构，虽然它在许多语言中被哈希表取代，但仍旧对于一些应用很实用。二叉树的各种变体可用于一些非常实用东西，比如数据库的索引、搜索算法结构、以及图像处理。
我把我的二叉树叫做`BSTree`，描述它的最佳方法就是它是另一种`Hashmap`形式的键值对储存容器。它们的差异在于，哈希表为键计算哈希值来寻找位置，而二叉树将键与树中的节点进行对比，之后深入树中找到储存它的最佳位置，基于它与其它节点的关系。
在我真正解释它的工作原理之前，让我向你展示`bstree.h`头文件，便于你看到数据结构，之后我会用它来解释如何构建。
```c
#ifndef _lcthw_BSTree_h
#define _lcthw_BSTree_h
typedef int (*BSTree_compare)(void *a, void *b);
typedef struct BSTreeNode {
void *key;
void *data;
struct BSTreeNode *left;
struct BSTreeNode *right;
struct BSTreeNode *parent;
} BSTreeNode;
typedef struct BSTree {
int count;
BSTree_compare compare;
BSTreeNode *root;
} BSTree;
typedef int (*BSTree_traverse_cb)(BSTreeNode *node);
BSTree *BSTree_create(BSTree_compare compare);
void BSTree_destroy(BSTree *map);
int BSTree_set(BSTree *map, void *key, void *data);
void *BSTree_get(BSTree *map, void *key);
int BSTree_traverse(BSTree *map, BSTree_traverse_cb traverse_cb);
void *BSTree_delete(BSTree *map, void *key);
#endif
```
这遵循了我之前用过的相同模式，我创建了一个基容器叫做`BSTree`，它含有叫做`BSTreeNode`的节点，组成实际内容。厌倦了吗？是的，这种结构也没有什么高明之处。
最重要的部分是，`BSTreeNode`如何配置，以及它如何用于进行每个操作：设置、获取和删除。我会首先讲解`get`，因为它是最简单的操作，并且我会在数据结构上手动操作：
+ 我获得你要找的键，并且用根节点开始遍历，首先我将你的键与这个节点的键进行对比。
+ 如果你的键小于`node.key`，我使用`left`指针来详细遍历。
+ 如果你的键大于`node.key`，我使用`right`指针来详细遍历。
+ 重复第二步和第三部，知道我找到了匹配`node.key`的节点，或者我遍历到了没有左子树或右子树的节点。这种情况我会返回`node.data`，其它情况会返回`NULL`。
这就是`get`的全部操作，现在是`set`，它几乎执行相同的操作，除了你在寻找防止新节点的位置。
+ 如果`BSTree.root`为空，就算是执行完成了。它就是第一个节点。
+ 之后我会将你的键与`node.key`进行比对，从根节点开始。
+ 如果你的键小于或等于`node.key`，我会遍历左子树，否则是右子树。
+ 重复第三步，直到我到达了没有左子树或右子树的节点，但是这是我需要选择的方向。
+ 我选择了这个方向（左或者右）来放置新的节点，并且将这个新节点的父节点设为我来时的上一个节点。当我删除它时，我会使用它的父节点。
这也解释了它如何工作。如果寻找一个节点涉及到按照键的对比来遍历左子树或右子树，那么设置一个节点涉及到相同的事情，直到我找到了一个位置，可以在其左子树或右子树上放置新的节点。
花一些时间在纸上画出一些树并且遍历一些节点来进行查找或设置，你就可以理解它如何工作。之后你要准备好来看一看实现，我在其中解释了删除操作。删除一个节点非常麻烦，因此它最适合逐行的代码分解。
```c
#include
#include
#include
#include
static int default_compare(void *a, void *b)
{
return bstrcmp((bstring)a, (bstring)b);
}
BSTree *BSTree_create(BSTree_compare compare)
{
BSTree *map = calloc(1, sizeof(BSTree));
check_mem(map);
map->compare = compare == NULL ? default_compare : compare;
return map;
error:
if(map) {
BSTree_destroy(map);
}
return NULL;
}
static int BSTree_destroy_cb(BSTreeNode *node)
{
free(node);
return 0;
}
void BSTree_destroy(BSTree *map)
{
if(map) {
BSTree_traverse(map, BSTree_destroy_cb);
free(map);
}
}
static inline BSTreeNode *BSTreeNode_create(BSTreeNode *parent, void *key, void *data)
{
BSTreeNode *node = calloc(1, sizeof(BSTreeNode));
check_mem(node);
node->key = key;
node->data = data;
node->parent = parent;
return node;
error:
return NULL;
}
static inline void BSTree_setnode(BSTree *map, BSTreeNode *node, void *key, void *data)
{
int cmp = map->compare(node->key, key);
if(cmp <= 0) {
if(node->left) {
BSTree_setnode(map, node->left, key, data);
} else {
node->left = BSTreeNode_create(node, key, data);
}
} else {
if(node->right) {
BSTree_setnode(map, node->right, key, data);
} else {
node->right = BSTreeNode_create(node, key, data);
}
}
}
int BSTree_set(BSTree *map, void *key, void *data)
{
if(map->root == NULL) {
// first so just make it and get out
map->root = BSTreeNode_create(NULL, key, data);
check_mem(map->root);
} else {
BSTree_setnode(map, map->root, key, data);
}
return 0;
error:
return -1;
}
static inline BSTreeNode *BSTree_getnode(BSTree *map, BSTreeNode *node, void *key)
{
int cmp = map->compare(node->key, key);
if(cmp == 0) {
return node;
} else if(cmp < 0) {
if(node->left) {
return BSTree_getnode(map, node->left, key);
} else {
return NULL;
}
} else {
if(node->right) {
return BSTree_getnode(map, node->right, key);
} else {
return NULL;
}
}
}
void *BSTree_get(BSTree *map, void *key)
{
if(map->root == NULL) {
return NULL;
} else {
BSTreeNode *node = BSTree_getnode(map, map->root, key);
return node == NULL ? NULL : node->data;
}
}
static inline int BSTree_traverse_nodes(BSTreeNode *node, BSTree_traverse_cb traverse_cb)
{
int rc = 0;
if(node->left) {
rc = BSTree_traverse_nodes(node->left, traverse_cb);
if(rc != 0) return rc;
}
if(node->right) {
rc = BSTree_traverse_nodes(node->right, traverse_cb);
if(rc != 0) return rc;
}
return traverse_cb(node);
}
int BSTree_traverse(BSTree *map, BSTree_traverse_cb traverse_cb)
{
if(map->root) {
return BSTree_traverse_nodes(map->root, traverse_cb);
}
return 0;
}
static inline BSTreeNode *BSTree_find_min(BSTreeNode *node)
{
while(node->left) {
node = node->left;
}
return node;
}
static inline void BSTree_replace_node_in_parent(BSTree *map, BSTreeNode *node, BSTreeNode *new_value)
{
if(node->parent) {
if(node == node->parent->left) {
node->parent->left = new_value;
} else {
node->parent->right = new_value;
}
} else {
// this is the root so gotta change it
map->root = new_value;
}
if(new_value) {
new_value->parent = node->parent;
}
}
static inline void BSTree_swap(BSTreeNode *a, BSTreeNode *b)
{
void *temp = NULL;
temp = b->key; b->key = a->key; a->key = temp;
temp = b->data; b->data = a->data; a->data = temp;
}
static inline BSTreeNode *BSTree_node_delete(BSTree *map, BSTreeNode *node, void *key)
{
int cmp = map->compare(node->key, key);
if(cmp < 0) {
if(node->left) {
return BSTree_node_delete(map, node->left, key);
} else {
// not found
return NULL;
}
} else if(cmp > 0) {
if(node->right) {
return BSTree_node_delete(map, node->right, key);
} else {
// not found
return NULL;
}
} else {
if(node->left && node->right) {
// swap this node for the smallest node that is bigger than us
BSTreeNode *successor = BSTree_find_min(node->right);
BSTree_swap(successor, node);
// this leaves the old successor with possibly a right child
// so replace it with that right child
BSTree_replace_node_in_parent(map, successor, successor->right);
// finally it's swapped, so return successor instead of node
return successor;
} else if(node->left) {
BSTree_replace_node_in_parent(map, node, node->left);
} else if(node->right) {
BSTree_replace_node_in_parent(map, node, node->right);
} else {
BSTree_replace_node_in_parent(map, node, NULL);
}
return node;
}
}
void *BSTree_delete(BSTree *map, void *key)
{
void *data = NULL;
if(map->root) {
BSTreeNode *node = BSTree_node_delete(map, map->root, key);
if(node) {
data = node->data;
free(node);
}
}
return data;
}
```
在讲解`BSTree_delete`如何工作之前，我打算解释一下我用于执行递归函数的模式。你会发现许多树形数据结构都易于使用递归来编写，而写成单个函数的形式相当困难。一部分原因在于你需要为第一次操作建立一些初始的数据，之后在数据结构中递归，这难以写成一个函数。
解决办法就是使用两个函数。一个函数“建立”数据结构和首次递归的条件使第二层函数能够执行真正的逻辑。首先看一看`BSTree_get`来理解我所说的。
+ 我设置了初始条件来处理递归，如果`map->NULL`是`NULL`，那么就返回`NULL`并且不需要递归。
+ 之后我执行了真正的递归调用，它就是`BSTree_getnode`。我设置了根节点的初始条件、`key`和`map`。
+ 之后在`BSTree_getnode`中，我执行了真正的递归逻辑，我将是用`map->compare(node->key, key)`来进行键的比对，并且根据结果遍历左子树或右子树，或者相等。
+ 由于这个函数时“自相似”的，并且不用处理任何初始条件（因为`BSTree_get`处理了），我就可以使它非常简单。当它完成时会返回给调用者，最后把结构返回给`BSTree_get`。
+ 最后，在结果不为`NULL`的情况下，`BSTree_get`处理获得的`node.data`元素。
这种构造递归算法的方法，与我构造递归数据结构的方法一致。我创建了一个起始的“基函数”，它处理初始条件和一些边界情况，之后它调用了一个简洁的递归函数来执行任务。与之相比，我在`BStree`中创建了“基结构”，它持有递归的`BSTreeNode`结构，每个节点都引用树中的其它节点。使用这种模式让我更容易处理递归并保持简洁。
接下来，浏览`BSTree_set` 和 `BSTree_setnode`，来观察相同的模式。我使用`BSTree_set`来确保初始条件和便捷情况。常见的边界情况就是树中没有根节点，于是我需要创建一个函数来初始化它们。
这个模式适用于几乎任何递归的算法。我按照这种模式来编写它们：
+ 理解初始变量，它们如何改变，以及递归每一步的终止条件。
+ 编写调用自身的递归函数，带有参数作为终止条件和初始变量。
+ 编程一个启动函数来设置算法的初始条件，并且处理边界情况，之后调用递归函数。
+ 最后，启动函数返回最后的结果，并且如果递归函数不能处理最终的边界情况可能还要做调整。
这引导了我完成`BSTree_delete`和`BSTree_node_delete`。首先你可以看一下`BSTree_delete`和它的启动函数，它获取结果节点的数据，并且释放找到的节点。在`BSTree_node_delete`中事情就变得复杂了，因为要在树中任意位置删除一个节点，我需要将子节点翻转上来。我会逐行拆分这个函数：
bstree.c:190
我执行比较函数来找出应该选择的方向。
bstree.c:192-198
这是“小于”的分支，我应该移到左子树。这里左子树并不存在并且返回了`NULL`来表示“未找到”。这处理了一些不在`BSTree`中元素的删除操作。
bstree.c:199-205
和上面相同，但是是对于树的右侧分支。这就像其它函数一样只是在树中向下遍历，并且在不存在时返回`NULL`。
bstree.c:206
这里是发现目标节点的地方，因为键是相等的（`compare`返回了0）。
bstree.c:207
这个节点同时具有`left`和`right`分支，所以它深深嵌入在树中。
bstree.c:209
要移除这个节点，我首先要找到大于这个节点的最小节点，这里我在右子树上调用了`BSTree_find_min`。
bstree.c:210
一旦我获得了这个几点，我将它的`key`和`data`与当前节点互换。这样就高效地将当前节点移动到树的最底端，并且不同通过它的指针来调整节点。
bstree.c:214
现在`successor`是一个无效的分支，储存了当前节点的值。然而它可能还带有右子树，也就是说我必须做一个旋转使它的右节点上来代替它。
bstree.c:217
到此为止，`successor`已经从树中移出了，它的值被当前节点的值代替，它的任何子树都合并进了它的父节点。我可以像`node`一样返回它。
bstree.c:218
这个分支中，我了解到这个节点没有右子树只有左子树，所以我可以简单地用左节点来替代它。
bstree.c:219
我再次使用`BSTree_replace_node_in_parent`来执行替换，把左节点旋转上去。
bstree.c:220
这是只有右子树而没有左子树的情况，所以需要将右节点旋转上去。
bstree.c:221
再次使用相同的函数，这次是针对右节点。
bstree.c:222
最后，对于我发现的节点只剩下一种情况，就是它没有任何子树（没有做子树也没有右子树）。这种情况，我只需要使用相同函数以`NULL`来执行替换。
bstree.c:210
在此之后，我已经将当前节点从书中移除，并且以某个合适的子节点的元素来替换。我只需要把它返回给调用者，使它能够被释放或管理。
这个操作非常复杂，实话说，在一些树形数据结构中，我并不需要执行删除，而是把它当做软件中的常亮数据。如果我需要做繁杂的插入和删除工作，我会使用`Hashmap`。
最后，你可以查看它的单元测试以及测试方法：
```c
#include "minunit.h"
#include
#include
#include
#include
#include
BSTree *map = NULL;
static int traverse_called = 0;
struct tagbstring test1 = bsStatic("test data 1");
struct tagbstring test2 = bsStatic("test data 2");
struct tagbstring test3 = bsStatic("xest data 3");
struct tagbstring expect1 = bsStatic("THE VALUE 1");
struct tagbstring expect2 = bsStatic("THE VALUE 2");
struct tagbstring expect3 = bsStatic("THE VALUE 3");
static int traverse_good_cb(BSTreeNode *node)
{
debug("KEY: %s", bdata((bstring)node->key));
traverse_called++;
return 0;
}
static int traverse_fail_cb(BSTreeNode *node)
{
debug("KEY: %s", bdata((bstring)node->key));
traverse_called++;
if(traverse_called == 2) {
return 1;
} else {
return 0;
}
}
char *test_create()
{
map = BSTree_create(NULL);
mu_assert(map != NULL, "Failed to create map.");
return NULL;
}
char *test_destroy()
{
BSTree_destroy(map);
return NULL;
}
char *test_get_set()
{
int rc = BSTree_set(map, &test1, &expect1);
mu_assert(rc == 0, "Failed to set &test1");
bstring result = BSTree_get(map, &test1);
mu_assert(result == &expect1, "Wrong value for test1.");
rc = BSTree_set(map, &test2, &expect2);
mu_assert(rc == 0, "Failed to set test2");
result = BSTree_get(map, &test2);
mu_assert(result == &expect2, "Wrong value for test2.");
rc = BSTree_set(map, &test3, &expect3);
mu_assert(rc == 0, "Failed to set test3");
result = BSTree_get(map, &test3);
mu_assert(result == &expect3, "Wrong value for test3.");
return NULL;
}
char *test_traverse()
{
int rc = BSTree_traverse(map, traverse_good_cb);
mu_assert(rc == 0, "Failed to traverse.");
mu_assert(traverse_called == 3, "Wrong count traverse.");
traverse_called = 0;
rc = BSTree_traverse(map, traverse_fail_cb);
mu_assert(rc == 1, "Failed to traverse.");
mu_assert(traverse_called == 2, "Wrong count traverse for fail.");
return NULL;
}
char *test_delete()
{
bstring deleted = (bstring)BSTree_delete(map, &test1);
mu_assert(deleted != NULL, "Got NULL on delete.");
mu_assert(deleted == &expect1, "Should get test1");
bstring result = BSTree_get(map, &test1);
mu_assert(result == NULL, "Should delete.");
deleted = (bstring)BSTree_delete(map, &test1);
mu_assert(deleted == NULL, "Should get NULL on delete");
deleted = (bstring)BSTree_delete(map, &test2);
mu_assert(deleted != NULL, "Got NULL on delete.");
mu_assert(deleted == &expect2, "Should get test2");
result = BSTree_get(map, &test2);
mu_assert(result == NULL, "Should delete.");
deleted = (bstring)BSTree_delete(map, &test3);
mu_assert(deleted != NULL, "Got NULL on delete.");
mu_assert(deleted == &expect3, "Should get test3");
result = BSTree_get(map, &test3);
mu_assert(result == NULL, "Should delete.");
// test deleting non-existent stuff
deleted = (bstring)BSTree_delete(map, &test3);
mu_assert(deleted == NULL, "Should get NULL");
return NULL;
}
char *test_fuzzing()
{
BSTree *store = BSTree_create(NULL);
int i = 0;
int j = 0;
bstring numbers[100] = {NULL};
bstring data[100] = {NULL};
srand((unsigned int)time(NULL));
for(i = 0; i < 100; i++) {
int num = rand();
numbers[i] = bformat("%d", num);
data[i] = bformat("data %d", num);
BSTree_set(store, numbers[i], data[i]);
}
for(i = 0; i < 100; i++) {
bstring value = BSTree_delete(store, numbers[i]);
mu_assert(value == data[i], "Failed to delete the right number.");
mu_assert(BSTree_delete(store, numbers[i]) == NULL, "Should get nothing.");
for(j = i+1; j < 99 - i; j++) {
bstring value = BSTree_get(store, numbers[j]);
mu_assert(value == data[j], "Failed to get the right number.");
}
bdestroy(value);
bdestroy(numbers[i]);
}
BSTree_destroy(store);
return NULL;
}
char *all_tests()
{
mu_suite_start();
mu_run_test(test_create);
mu_run_test(test_get_set);
mu_run_test(test_traverse);
mu_run_test(test_delete);
mu_run_test(test_destroy);
mu_run_test(test_fuzzing);
return NULL;
}
RUN_TESTS(all_tests);
```
我要重点讲解`test_fuzzing`函数，它是针对复杂数据结构的一种有趣的测试技巧。创建一些键来覆盖`BSTree_node_delete`的所有分支相当困难，而且有可能我会错过一些边界情况。更好的方法就是创建一个“模糊测试”的函数来执行所有操作，并尽可能以一种可怕且随机的方式执行它们。这里我插入了一系列随机字符串的键，之后我删除了它们并试着在删除之后获取它们的值。
这种测试可以避免只测试到你知道能正常工作的部分，这意味着你不会遗漏不知道的事情。通过想你的数据结构插入一些随机的垃圾数据，你可以碰到意料之外的事情，并检测出任何bug。
## 如何改进
不要完成下列任何习题，因为在下个练习中我会使用这里的单元测试，来教你使用一些性能调优的技巧。在你完成练习41之后，你需要返回来完成这些习题。
+ 像之前一样，你应该执行所有防御性编程检查，并且为不应发生的情况添加`assert`。例如，你不应该在递归函数中获取到`NULL`，为此添加断言。
+ 遍历函数按照左子树、右子树和当前节点的顺组进行遍历。你可以创建相反顺序的遍历函数。
+ 每个节点上都会执行完整的字符串比较，但是我可以使用`Hashmap`的哈希函数来提升速度。我可以计算键的哈希值，在`BSTreeNode`中储存它。之后在每个创建的函数中，我可以实现计算出键的哈希值，然后在递归中向下传递。我可以使用哈希来很快地比较每个节点，就像`Hashmap`那样。
## 附加题
同样，现在先不要完成它们，直到完成练习41，那时你就可以使用`Valgrind`的性能调优技巧来完成它们了。
+ 有一种不使用递归的替代的方法，也可以操作这个数据结构。维基百科上介绍了不使用递归来完成相同事情的替代方法。这样做会更好还是更糟？
+ 查询你能找到的所有不同的树的相关资料。比如AVL树、红黑树、以及一些非树形结构例如跳转表。
';
练习39：字符串算法
最后更新于：2022-04-01 23:29:26
# 练习39：字符串算法
> 原文：[Exercise 39: String Algorithms](http://c.learncodethehardway.org/book/ex39.html)
> 译者：[飞龙](https://github.com/wizardforcel)
这个练习中，我会向你展示可能是最快的字符串搜索算法之一，并且将它与`bstrlib.c`中现有的`binstr`比较。`binstr`的文档说它仅仅使用了“暴力搜索”的字符串算法来寻找第一个实例。我所实现的函数使用Boyer-Moore-Horspool（BMH）算法，如果你分析理论时间的话，一般认为它会更快。你也会看到，如果我的实现没有任何缺陷，BMH的实际时间会比`binstr`简单的暴力搜索更糟。
这个练习的要点并不是真正解释算法本身，因为你可以直接去[Boyer-Moore-Horspool 的维基百科页面](http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore%E2%80%93Horspool_algorithm)去阅读它。这个算法的要点就是它会计算出“跳跃字符列表”作为第一步操作，之后它使用这个列表来快速扫描整个字符串。它应当比暴力搜索更快，所以让我们在文件里写出代码来看看吧。
首先，创建头文件：
```c
#ifndef string_algos_h
#define string_algos_h
#include
#include
typedef struct StringScanner {
bstring in;
const unsigned char *haystack;
ssize_t hlen;
const unsigned char *needle;
ssize_t nlen;
size_t skip_chars[UCHAR_MAX + 1];
} StringScanner;
int String_find(bstring in, bstring what);
StringScanner *StringScanner_create(bstring in);
int StringScanner_scan(StringScanner *scan, bstring tofind);
void StringScanner_destroy(StringScanner *scan);
#endif
```
为了观察“跳跃字符列表”的效果，我打算创建这个算法的两种版本：
String_find
只是在一个字符串中，寻找另一个字符串的首个实例，以一个动作执行整个算法。
StringScanner_scan
使用`StringScanner`状态结构，将跳跃列表的构建和实际的查找操作分开。这让我能看到什么影响了性能。这个模型有另一个优点，就是我可以在一个字符串中逐步搜索，并且快速地找到所有实例。
一旦你完成了头文件，下面就是实现了：
```c
#include
#include
static inline void String_setup_skip_chars(
size_t *skip_chars,
const unsigned char *needle, ssize_t nlen)
{
size_t i = 0;
size_t last = nlen - 1;
for(i = 0; i < UCHAR_MAX + 1; i++) {
skip_chars[i] = nlen;
}
for (i = 0; i < last; i++) {
skip_chars[needle[i]] = last - i;
}
}
static inline const unsigned char *String_base_search(
const unsigned char *haystack, ssize_t hlen,
const unsigned char *needle, ssize_t nlen,
size_t *skip_chars)
{
size_t i = 0;
size_t last = nlen - 1;
assert(haystack != NULL && "Given bad haystack to search.");
assert(needle != NULL && "Given bad needle to search for.");
check(nlen > 0, "nlen can't be <= 0");
check(hlen > 0, "hlen can't be <= 0");
while (hlen >= nlen)
{
for (i = last; haystack[i] == needle[i]; i--) {
if (i == 0) {
return haystack;
}
}
hlen -= skip_chars[haystack[last]];
haystack += skip_chars[haystack[last]];
}
error: // fallthrough
return NULL;
}
int String_find(bstring in, bstring what)
{
const unsigned char *found = NULL;
const unsigned char *haystack = (const unsigned char *)bdata(in);
ssize_t hlen = blength(in);
const unsigned char *needle = (const unsigned char *)bdata(what);
ssize_t nlen = blength(what);
size_t skip_chars[UCHAR_MAX + 1] = {0};
String_setup_skip_chars(skip_chars, needle, nlen);
found = String_base_search(haystack, hlen, needle, nlen, skip_chars);
return found != NULL ? found - haystack : -1;
}
StringScanner *StringScanner_create(bstring in)
{
StringScanner *scan = calloc(1, sizeof(StringScanner));
check_mem(scan);
scan->in = in;
scan->haystack = (const unsigned char *)bdata(in);
scan->hlen = blength(in);
assert(scan != NULL && "fuck");
return scan;
error:
free(scan);
return NULL;
}
static inline void StringScanner_set_needle(StringScanner *scan, bstring tofind)
{
scan->needle = (const unsigned char *)bdata(tofind);
scan->nlen = blength(tofind);
String_setup_skip_chars(scan->skip_chars, scan->needle, scan->nlen);
}
static inline void StringScanner_reset(StringScanner *scan)
{
scan->haystack = (const unsigned char *)bdata(scan->in);
scan->hlen = blength(scan->in);
}
int StringScanner_scan(StringScanner *scan, bstring tofind)
{
const unsigned char *found = NULL;
ssize_t found_at = 0;
if(scan->hlen <= 0) {
StringScanner_reset(scan);
return -1;
}
if((const unsigned char *)bdata(tofind) != scan->needle) {
StringScanner_set_needle(scan, tofind);
}
found = String_base_search(
scan->haystack, scan->hlen,
scan->needle, scan->nlen,
scan->skip_chars);
if(found) {
found_at = found - (const unsigned char *)bdata(scan->in);
scan->haystack = found + scan->nlen;
scan->hlen -= found_at - scan->nlen;
} else {
// done, reset the setup
StringScanner_reset(scan);
found_at = -1;
}
return found_at;
}
void StringScanner_destroy(StringScanner *scan)
{
if(scan) {
free(scan);
}
}
```
整个算法都在两个`static inline`的函数中，叫做`String_setup_skip_chars` 和 `String_base_search`。它们在别的函数中使用，用于实现我想要的的搜索形式。研究这两个函数，并且与维基百科的描述对比，你就可以知道它的工作原理。
之后`String_find`使用这两个函数来寻找并返回所发现的位置。它非常简单并且我使用它来查看“跳跃字符列表”的构建如何影响到真实性能。要注意，你或许可以使它更快，但是我要教给你在你实现算法之后如何验证理论速度。
`StringScanner_scan`函数随后按照“创建、扫描、销毁”的常用模式，并且用于在一个字符串中逐步搜索另一个字符串。当我向你展示单元测试的时候，你会看到它如何使用。
最后，我编写了单元测试来确保算法有效，之后在它的注释部分，我为三个搜索函数运行了简单的性能测试：
```c
#include "minunit.h"
#include
#include
#include
struct tagbstring IN_STR = bsStatic("I have ALPHA beta ALPHA and oranges ALPHA");
struct tagbstring ALPHA = bsStatic("ALPHA");
const int TEST_TIME = 1;
char *test_find_and_scan()
{
StringScanner *scan = StringScanner_create(&IN_STR);
mu_assert(scan != NULL, "Failed to make the scanner.");
int find_i = String_find(&IN_STR, &ALPHA);
mu_assert(find_i > 0, "Failed to find 'ALPHA' in test string.");
int scan_i = StringScanner_scan(scan, &ALPHA);
mu_assert(scan_i > 0, "Failed to find 'ALPHA' with scan.");
mu_assert(scan_i == find_i, "find and scan don't match");
scan_i = StringScanner_scan(scan, &ALPHA);
mu_assert(scan_i > find_i, "should find another ALPHA after the first");
scan_i = StringScanner_scan(scan, &ALPHA);
mu_assert(scan_i > find_i, "should find another ALPHA after the first");
mu_assert(StringScanner_scan(scan, &ALPHA) == -1, "shouldn't find it");
StringScanner_destroy(scan);
return NULL;
}
char *test_binstr_performance()
{
int i = 0;
int found_at = 0;
unsigned long find_count = 0;
time_t elapsed = 0;
time_t start = time(NULL);
do {
for(i = 0; i < 1000; i++) {
found_at = binstr(&IN_STR, 0, &ALPHA);
mu_assert(found_at != BSTR_ERR, "Failed to find!");
find_count++;
}
elapsed = time(NULL) - start;
} while(elapsed <= TEST_TIME);
debug("BINSTR COUNT: %lu, END TIME: %d, OPS: %f",
find_count, (int)elapsed, (double)find_count / elapsed);
return NULL;
}
char *test_find_performance()
{
int i = 0;
int found_at = 0;
unsigned long find_count = 0;
time_t elapsed = 0;
time_t start = time(NULL);
do {
for(i = 0; i < 1000; i++) {
found_at = String_find(&IN_STR, &ALPHA);
find_count++;
}
elapsed = time(NULL) - start;
} while(elapsed <= TEST_TIME);
debug("FIND COUNT: %lu, END TIME: %d, OPS: %f",
find_count, (int)elapsed, (double)find_count / elapsed);
return NULL;
}
char *test_scan_performance()
{
int i = 0;
int found_at = 0;
unsigned long find_count = 0;
time_t elapsed = 0;
StringScanner *scan = StringScanner_create(&IN_STR);
time_t start = time(NULL);
do {
for(i = 0; i < 1000; i++) {
found_at = 0;
do {
found_at = StringScanner_scan(scan, &ALPHA);
find_count++;
} while(found_at != -1);
}
elapsed = time(NULL) - start;
} while(elapsed <= TEST_TIME);
debug("SCAN COUNT: %lu, END TIME: %d, OPS: %f",
find_count, (int)elapsed, (double)find_count / elapsed);
StringScanner_destroy(scan);
return NULL;
}
char *all_tests()
{
mu_suite_start();
mu_run_test(test_find_and_scan);
// this is an idiom for commenting out sections of code
#if 0
mu_run_test(test_scan_performance);
mu_run_test(test_find_performance);
mu_run_test(test_binstr_performance);
#endif
return NULL;
}
RUN_TESTS(all_tests);
```
我把它们写在`#if 0`中间，它是使用C预处理器来注释一段代码的方法。像这样输入，并且把它和`#endif`移除，你就可以运行性能测试。当你继续这本书时，需要简单地把它们再次注释，以防它们浪费你的开发时间。
这个单元测试没有什么神奇之处，它只是在尊换种调用每个不同的函数，循环需要持续足够长的时间来得到一个几秒的样本。第一个测试（`test_find_and_scan`）只是确保我所编写的代码正常工作，因为测试无效的代码没有意义。之后，下面的三个函数使用三个函数中的每一个来执行大量的搜索。
需要注意的一个技巧是，我在`start`中存储了起始时间，之后一直循环到至少过了`TEST_TIME`秒。这确保了我能或得到足够好的样本用于比较三者。我之后会使用不同的`TEST_TIME`设置来运行测试，并且分析结果。
## 你会看到什么
当我在我的笔记本上运行测试时，我得到的数据是这样的：
```sh
$ ./tests/string_algos_tests
DEBUG tests/string_algos_tests.c:124: ----- RUNNING: ./tests/string_algos_tests
----
RUNNING: ./tests/string_algos_tests
DEBUG tests/string_algos_tests.c:116:
----- test_find_and_scan
DEBUG tests/string_algos_tests.c:117:
----- test_scan_performance
DEBUG tests/string_algos_tests.c:105: SCAN COUNT: 110272000, END TIME: 2, OPS: 55136000.000000
DEBUG tests/string_algos_tests.c:118:
----- test_find_performance
DEBUG tests/string_algos_tests.c:76: FIND COUNT: 12710000, END TIME: 2, OPS: 6355000.000000
DEBUG tests/string_algos_tests.c:119:
----- test_binstr_performance
DEBUG tests/string_algos_tests.c:54: BINSTR COUNT: 72736000, END TIME: 2, OPS: 36368000.000000
ALL TESTS PASSED
Tests run: 4
$
```
我看到了它，觉得每轮运行应该超过两秒。并且，我打算多次运行它，并且像之前一样使用R来验证。下面是我获得的10个样例，每个基本上是10秒：
```r
scan find binstr
71195200 6353700 37110200
75098000 6358400 37420800
74910000 6351300 37263600
74859600 6586100 37133200
73345600 6365200 37549700
74754400 6358000 37162400
75343600 6630400 37075000
73804800 6439900 36858700
74995200 6384300 36811700
74781200 6449500 37383000
```
我在shell的一点点帮助下获取数据，之后编辑输出：
```shell
$ for i in 1 2 3 4 5 6 7 8 9 10; do echo "RUN --- $i" >> times.log; ./tests/string_algos_tests 2>&1 | grep COUNT >> times.log ; done
$ less times.log
$ vim times.log
```
现在你可以看到`scan`系统要优于另外两个，但是我会在R中打开它并且验证结果：
```rebol
> times <- read.table("times.log", header=T)
> summary(times)
scan find binstr
Min. :71195200 Min. :6351300 Min. :36811700
1st Qu.:74042200 1st Qu.:6358100 1st Qu.:37083800
Median :74820400 Median :6374750 Median :37147800
Mean :74308760 Mean :6427680 Mean :37176830
3rd Qu.:74973900 3rd Qu.:6447100 3rd Qu.:37353150
Max. :75343600 Max. :6630400 Max. :37549700
>
```
为了理解我为什么要生成这份概要统计，我必须对你解释一些统计学概念。我在这些数字中寻找的东西能够简单地告诉我，“这三个函数（`scan`、`find`、`binstr`）实际上不同吗？”我知道每次我运行测试函数的时候，我都会得到有些不同的数值，并且那些数值始终处理一个固定的范围。你可以看到两个四分位数反映了这一点。
我首先会去看均值，并且我会观察每个样例的均值是否不同于其它的。我可以清楚地看到`scan`优于`binstr`，同时后者优于`find`。然而问题来了，如果我只使用均值，就可以出现每个样例的范围会重叠的可能性。
如果均值不同，但是两个四分位点重叠会怎么用？这种情况下我只能说有这种可能性，并且如果我再次运行测试，均值就可能不同了。很可能出现的范围上的重叠是，我的两个样例（以及两个函数）并非实际上不同。任何我看到的差异都是随机产生的结果。
统计学拥有大量工具来解决这一问题，但是在我们的例子中我可以仅仅观察两个四分位值，以及所有样例的均值。如果均值不同，并且四分位值不可能重叠，就可以说它们完全不同。
在我的三个样例中，我可以说`scan`、`find`和`binstr`都是不同的，范围上没有重叠，并且（最重要的是）我可以相信数据。
## 分析结果
从结果中可以看出`String_find`比其它两个更慢。实际上，我认为慢的原因是我实现的方式有些问题。然而当我将它与`StringScanner_scan`比较时，我发现正是构造跳跃列表的那一部分最消耗时间。并且它的功能比`scan`要少，因为它仅仅找到了第一个位置，而`scan`找到了全部。
我也可以发现`scan`以很大优势优于`binstr`。同时我可以说`scan`的功能比其他两个要多，速度也更快。
下面是这个分析的一些注解：
+ 我可能将实现或测试弄乱了。现在我打算研究所有实现BMH的可能方式来改进它。我也会确保我所做的事情正确。
+ 如果你修改了测试运行的时间，你会得到不同的结果。这就是我没有考虑的”热身“环节。
+ `test_scan_performance`单元测试和其它两个并不相同，但是它比其它测试做得更多（并且也是按照时间和操作数量计算的），所以他可能是合理的。
+ 我只通过在一个字符串内搜索另一个来执行测试。我应该使所查找的字符串随机化，来移除它们的位置和长度，作为干扰因素。
+ `binstr`的实现可能比“暴力搜索”要好。（所以应该自己编写暴力搜索作为对照。）
+ 我可能以不幸的顺序来执行这些函数，并且随机化首先运行的测试可能会得到更好的结果。
可以从中学到的是，你需要确保知己的性能，即使你“正确”实现了一个算法。在这里BMH算法应该优于`binstr`算法，但是一个简单的测试证明了它是错误。如果我没有这些测试，我可能就使用了一个劣等的算法实现而不自知。参照这些度量，我可以开始调优我的实现，或者只是抛弃它并寻找新的算法。
## 附加题
+ 看看你能不能使`Scan_find`更快。为什么我的实现这么慢？
+ 尝试一些不同的搜索时长，看看你是否能得到不同的数值。当你改变`scan`的测试时间时，时间的长度会有什么影响？对于这些结果你能得出什么结论？
+ 修改单元测试，使它最开始执行每个函数一小段时间，来消除任何“热身”缓解。这样会修改所运行时长的依赖性吗？每秒可能出现多少次操作？
+ 使单元测试中的所查找字符串随机化，之后测量你的得到的性能。一种实现它的方式就是使用`bstrlib.h`中的`bsplit`函数在空格处分割`IN_STR`。之后使用你得到的`strList`结构访问它返回的每个字符串。这也教给你如何使用`bstrList`操作进行字符串处理。
+ 尝试一些不同顺序的测试，看看能否得到不同的结果。
';
练习38：哈希算法
最后更新于：2022-04-01 23:29:24
# 练习38：哈希算法
> 原文：[Exercise 38: Hashmap Algorithms](http://c.learncodethehardway.org/book/ex38.html)
> 译者：[飞龙](https://github.com/wizardforcel)
你需要在这个练习中实现下面这三个哈希函数：
FNV-1a
以创造者Glenn Fowler、Phong Vo 和 Landon Curt Noll的名字命名。这个算法产生合理的数值并且相当快。
Adler-32
以Mark Adler命名。一个比较糟糕的算法，但是由来已久并且适于学习。
DJB Hash
由Dan J. Bernstein (DJB)发明的哈希算法，但是难以找到这个算法的讨论。它非常快，但是结果不是很好。
你应该看到我使用了Jenkins hash作为`Hashmap`数据结构的默认哈希函数，所以这个练习的重点会放在这三个新的函数上。它们的代码通常来说不多，并且没有任何优化。像往常一样我会放慢速度来让你理解。
头文件非常简单，所以我以它开始：
```c
#ifndef hashmap_algos_h
#define hashmap_algos_h
#include
uint32_t Hashmap_fnv1a_hash(void *data);
uint32_t Hashmap_adler32_hash(void *data);
uint32_t Hashmap_djb_hash(void *data);
#endif
```
我只是声明了三个函数，我会在`hashmap_algos.c`文件中实现它们：
```c
#include
#include
// settings taken from
// http://www.isthe.com/chongo/tech/comp/fnv/index.html#FNV-param
const uint32_t FNV_PRIME = 16777619;
const uint32_t FNV_OFFSET_BASIS = 2166136261;
uint32_t Hashmap_fnv1a_hash(void *data)
{
bstring s = (bstring)data;
uint32_t hash = FNV_OFFSET_BASIS;
int i = 0;
for(i = 0; i < blength(s); i++) {
hash ^= bchare(s, i, 0);
hash *= FNV_PRIME;
}
return hash;
}
const int MOD_ADLER = 65521;
uint32_t Hashmap_adler32_hash(void *data)
{
bstring s = (bstring)data;
uint32_t a = 1, b = 0;
int i = 0;
for (i = 0; i < blength(s); i++)
{
a = (a + bchare(s, i, 0)) % MOD_ADLER;
b = (b + a) % MOD_ADLER;
}
return (b << 16) | a;
}
uint32_t Hashmap_djb_hash(void *data)
{
bstring s = (bstring)data;
uint32_t hash = 5381;
int i = 0;
for(i = 0; i < blength(s); i++) {
hash = ((hash << 5) + hash) + bchare(s, i, 0); /* hash * 33 + c */
}
return hash;
}
```
这个文件中有三个哈希函数。你应该注意到我默认使用`bstring`作为键，并且使用了`bchare`函数从字符串获取字符，然而如果字符超出了字符串的长度会返回0。
这些算法中每个都可以在网上搜索到，所以你需要搜索它们并阅读相关内容。同时我主要使用维基百科上的结果，之后参照了其它来源。
接着我为每个算法编写了单元测试，同时也测试了它们在多个桶中的分布情况。
```c
#include
#include
#include
#include
#include "minunit.h"
struct tagbstring test1 = bsStatic("test data 1");
struct tagbstring test2 = bsStatic("test data 2");
struct tagbstring test3 = bsStatic("xest data 3");
char *test_fnv1a()
{
uint32_t hash = Hashmap_fnv1a_hash(&test1);
mu_assert(hash != 0, "Bad hash.");
hash = Hashmap_fnv1a_hash(&test2);
mu_assert(hash != 0, "Bad hash.");
hash = Hashmap_fnv1a_hash(&test3);
mu_assert(hash != 0, "Bad hash.");
return NULL;
}
char *test_adler32()
{
uint32_t hash = Hashmap_adler32_hash(&test1);
mu_assert(hash != 0, "Bad hash.");
hash = Hashmap_adler32_hash(&test2);
mu_assert(hash != 0, "Bad hash.");
hash = Hashmap_adler32_hash(&test3);
mu_assert(hash != 0, "Bad hash.");
return NULL;
}
char *test_djb()
{
uint32_t hash = Hashmap_djb_hash(&test1);
mu_assert(hash != 0, "Bad hash.");
hash = Hashmap_djb_hash(&test2);
mu_assert(hash != 0, "Bad hash.");
hash = Hashmap_djb_hash(&test3);
mu_assert(hash != 0, "Bad hash.");
return NULL;
}
#define BUCKETS 100
#define BUFFER_LEN 20
#define NUM_KEYS BUCKETS * 1000
enum { ALGO_FNV1A, ALGO_ADLER32, ALGO_DJB};
int gen_keys(DArray *keys, int num_keys)
{
int i = 0;
FILE *urand = fopen("/dev/urandom", "r");
check(urand != NULL, "Failed to open /dev/urandom");
struct bStream *stream = bsopen((bNread)fread, urand);
check(stream != NULL, "Failed to open /dev/urandom");
bstring key = bfromcstr("");
int rc = 0;
// FNV1a histogram
for(i = 0; i < num_keys; i++) {
rc = bsread(key, stream, BUFFER_LEN);
check(rc >= 0, "Failed to read from /dev/urandom.");
DArray_push(keys, bstrcpy(key));
}
bsclose(stream);
fclose(urand);
return 0;
error:
return -1;
}
void destroy_keys(DArray *keys)
{
int i = 0;
for(i = 0; i < NUM_KEYS; i++) {
bdestroy(DArray_get(keys, i));
}
DArray_destroy(keys);
}
void fill_distribution(int *stats, DArray *keys, Hashmap_hash hash_func)
{
int i = 0;
uint32_t hash = 0;
for(i = 0; i < DArray_count(keys); i++) {
hash = hash_func(DArray_get(keys, i));
stats[hash % BUCKETS] += 1;
}
}
char *test_distribution()
{
int i = 0;
int stats[3][BUCKETS] = {{0}};
DArray *keys = DArray_create(0, NUM_KEYS);
mu_assert(gen_keys(keys, NUM_KEYS) == 0, "Failed to generate random keys.");
fill_distribution(stats[ALGO_FNV1A], keys, Hashmap_fnv1a_hash);
fill_distribution(stats[ALGO_ADLER32], keys, Hashmap_adler32_hash);
fill_distribution(stats[ALGO_DJB], keys, Hashmap_djb_hash);
fprintf(stderr, "FNV\tA32\tDJB\n");
for(i = 0; i < BUCKETS; i++) {
fprintf(stderr, "%d\t%d\t%d\n",
stats[ALGO_FNV1A][i],
stats[ALGO_ADLER32][i],
stats[ALGO_DJB][i]);
}
destroy_keys(keys);
return NULL;
}
char *all_tests()
{
mu_suite_start();
mu_run_test(test_fnv1a);
mu_run_test(test_adler32);
mu_run_test(test_djb);
mu_run_test(test_distribution);
return NULL;
}
RUN_TESTS(all_tests);
```
我在代码中将`BUCKETS`的值设置得非常高，因为我的电脑足够快。如果你将它和`NUM_KEYS`调低，就会比较慢了。这个测试运行之后，对于每个哈希函数，通过使用R语言做统计分析，可以观察键的分布情况。
我实现它的方式是使用`gen_keys`函数生成键的大型列表。这些键从`/dev/urandom`设备中获得，它们是一些随机的字节。之后我使用了这些键来调用`fill_distribution`，填充了`stats `数组，这些键计算哈希值后会被放入理论上的一些桶中。所有这类函数会遍历所有键，计算哈希，之后执行类似`Hashmap`所做的事情来寻找正确的桶。
最后我只是简单打印出一个三列的表格，包含每个桶的最终数量，展示了每个桶中随机储存了多少个键。之后可以观察这些数值，来判断这些哈希函数是否合理对键进行分配。
## 你会看到什么
教授R是这本书范围之外的内容，但是如果你想试试它，可以访问[r-project.org](http://www.r-project.org/)。
下面是一个简略的shell会话，向你展示了我如何运行`1tests/hashmap_algos_test`来获取`test_distribution`产生的表（这里没有展示），之后使用R来观察统计结果：
```sh
$ tests/hashmap_algos_tests
# copy-paste the table it prints out
$ vim hash.txt
$ R
> hash <- read.table("hash.txt", header=T)
> summary(hash)
FNV A32 DJB
Min. : 945 Min. : 908.0 Min. : 927
1st Qu.: 980 1st Qu.: 980.8 1st Qu.: 979
Median : 998 Median :1000.0 Median : 998
Mean :1000 Mean :1000.0 Mean :1000
3rd Qu.:1016 3rd Qu.:1019.2 3rd Qu.:1021
Max. :1072 Max. :1075.0 Max. :1082
```
首先我只是运行测试，它会在屏幕上打印表格。之后我将它复制粘贴到下来并使用`vim hash.txt`来储存数据。如果你观察数据，它会带有显示这三个算法的`FNV A32 DJB`表头。
接着，我运行R来使用`read.table`命令加载数据集。它是个非常智能的函数，适用于这种tab分隔的数据，我只要告诉它`header=T`，它就知道数据集中带有表头。
最后，我家在了数据并且可以使用`summary`来打印出它每行的统计结果。这里你可以看到每个函数处理随机数据实际上都没有问题。我会解释每个行的意义：
Min.
它是列出数据的最小值。FNV似乎在这方面是最优的，因为它有最大的结果，也就是说它的下界最严格。
1st Qu.
数据的第一个四分位点。
Median
如果你对它们排序，这个数值就是最重点的那个数。中位数比起均值来讲更有用一些。
Mean
均值对大多数人意味着“平均”，它是数据的总数比数量。如果你观察它们，所有均值都是1000，这非常棒。如果你将它去中位数对比，你会发现，这三个中位数都很接近均值。这就意味着这些数据都没有“偏向”一端，所以均值是可信的。
3rd Qu.
数据后四分之一的起始点，代表了尾部的数值。
Max.
这是数据中的最大值，代表了它们的上界。
观察这些数据，你会发现这些哈希算法似乎都适用于随机的键，并且均值与我设置的`NUM_KEYS`匹配。我所要找的就是如果我为每个桶中生成了1000个键，那么平均每个桶中就应该有100个键。如果哈希函数工作不正常，你会发现统计结果中均值不是1000，并且第一个和第三个四分位点非常高。一个好的哈希算法应该使平均值为1000，并且具有严格的范围。
同时，你应该明白即使在这个单元测试的不同运行之间，你的数据的大多数应该和我不同。
## 如何使它崩溃
这个练习的最后，我打算向你介绍使它崩溃的方法。我需要让你变写你能编写的最烂的哈希函数，并且我会使用数据来证明它确实很烂。你可以使用R来进行统计，就像我上面一样，但也可能你知道其他可以使用的工具来进行相同的统计操作。
这里的目标是让一个哈希函数，它表面看起来是正常的，但实际运行就得到一个糟糕的均值，并且分布广泛。这意味着你不能只让你返回1，而是需要返回一些看似正常的数值，但是分布广泛并且都填充到相同的桶中。
如果你对这四个函数之一做了一些小修改来完成任务，我会给你额外的分数。
这个练习的目的是，想像一下一些“友好”的程序员见到你并且打算改进你的哈希函数，但是实际上只是留了个把你的`Hashmap`搞砸的后门。
## 附加题
+ 将`hashmap.c`中的`default_hash`换成`hashmap_algos.c`中的算法之一，并且再次通过所有测试。
+ 向`hashmap_algos_tests.c`添加`default_hash`，并将它与其它三个哈希函数比较。
+ 寻找一些更多的哈希函数并添加进来，你永远都不可能找到太多的哈希函数！
';
练习37：哈希表
最后更新于：2022-04-01 23:29:21
# 练习37：哈希表
> 原文：[Exercise 37: Hashmaps](http://c.learncodethehardway.org/book/ex37.html)
> 译者：[飞龙](https://github.com/wizardforcel)
哈希表（`HashMap`、`HashTable`以及`Dictionary`）广泛用于许多动态编程语言来储存键值对的数据。哈希表通过在键上执行“哈希”运算产生整数，之后使用它来寻找相应的桶来获取或储存值。它是非常快速的使用数据结构，因为它适用于任何数据并且易于实现。
下面是哈希表（也叫作字典）的一个使用示例：
```c
fruit_weights = {'Apples': 10, 'Oranges': 100, 'Grapes': 1.0}
for key, value in fruit_weights.items():
print key, "=", value
```
几乎所有现代语言都具备这种特性，所以许多人写完代码都不知道它实际上如何工作。通过在C中创建`Hashmap`数据结构，我会向你展示它的工作原理。我会从头文件开始，来谈论整个数据结构。
```c
#ifndef _lcthw_Hashmap_h
#define _lcthw_Hashmap_h
#include
#include
#define DEFAULT_NUMBER_OF_BUCKETS 100
typedef int (*Hashmap_compare)(void *a, void *b);
typedef uint32_t (*Hashmap_hash)(void *key);
typedef struct Hashmap {
DArray *buckets;
Hashmap_compare compare;
Hashmap_hash hash;
} Hashmap;
typedef struct HashmapNode {
void *key;
void *data;
uint32_t hash;
} HashmapNode;
typedef int (*Hashmap_traverse_cb)(HashmapNode *node);
Hashmap *Hashmap_create(Hashmap_compare compare, Hashmap_hash);
void Hashmap_destroy(Hashmap *map);
int Hashmap_set(Hashmap *map, void *key, void *data);
void *Hashmap_get(Hashmap *map, void *key);
int Hashmap_traverse(Hashmap *map, Hashmap_traverse_cb traverse_cb);
void *Hashmap_delete(Hashmap *map, void *key);
#endif
```
这个结构就是`Hashmap`，含有许多`HashmapNode`节点。观察`Hashmap`你会看到它类似这样：
`DArray *buckets`
一个动态数组，设置为100个桶的固定大小。每个桶会含有一个`DArray`，来实际存档`HashmapNode`对。
`Hashmap_compare compare`
这是一个比较函数，被`Hashmap`用于实际用过键寻找元素。它应该和其它的比较函数类似，并且默认设置为`bstrcmp`来比较字符串。
`Hashmap_hash`
这是哈希函数，它用于接收键，处理它的内容，之后产生一个`uint32_t`索引数值。之后你会看到默认的实现。
这些告诉了你数据如何存储，但是用作`buckets`的`DArray`还没有创建。要记住它具有二层结构；
+ 第一层有100个桶，数据基于它们的哈希值储存在桶中。
+ 每个桶都是一个`DArray`，其中含有`HashmapNode`，添加时只是简单地附加到末尾。
`HashMapNode`由下面三个元素组成：
`void *key`
键值对的键。
`void *value`
键值对的值。
`uint32_t hash`
计算出的哈希值，它用于使查找该节点更加迅速，只要判断键是否相等。
有文件的剩余部分没有新的东西，所以我现在可以向你展示`hashmap.c`的实现了：
```c
#undef NDEBUG
#include
#include
#include
#include
static int default_compare(void *a, void *b)
{
return bstrcmp((bstring)a, (bstring)b);
}
/**
* Simple Bob Jenkins's hash algorithm taken from the
* wikipedia description.
*/
static uint32_t default_hash(void *a)
{
size_t len = blength((bstring)a);
char *key = bdata((bstring)a);
uint32_t hash = 0;
uint32_t i = 0;
for(hash = i = 0; i < len; ++i)
{
hash += key[i];
hash += (hash << 10);
hash ^= (hash >> 6);
}
hash += (hash << 3);
hash ^= (hash >> 11);
hash += (hash << 15);
return hash;
}
Hashmap *Hashmap_create(Hashmap_compare compare, Hashmap_hash hash)
{
Hashmap *map = calloc(1, sizeof(Hashmap));
check_mem(map);
map->compare = compare == NULL ? default_compare : compare;
map->hash = hash == NULL ? default_hash : hash;
map->buckets = DArray_create(sizeof(DArray *), DEFAULT_NUMBER_OF_BUCKETS);
map->buckets->end = map->buckets->max; // fake out expanding it
check_mem(map->buckets);
return map;
error:
if(map) {
Hashmap_destroy(map);
}
return NULL;
}
void Hashmap_destroy(Hashmap *map)
{
int i = 0;
int j = 0;
if(map) {
if(map->buckets) {
for(i = 0; i < DArray_count(map->buckets); i++) {
DArray *bucket = DArray_get(map->buckets, i);
if(bucket) {
for(j = 0; j < DArray_count(bucket); j++) {
free(DArray_get(bucket, j));
}
DArray_destroy(bucket);
}
}
DArray_destroy(map->buckets);
}
free(map);
}
}
static inline HashmapNode *Hashmap_node_create(int hash, void *key, void *data)
{
HashmapNode *node = calloc(1, sizeof(HashmapNode));
check_mem(node);
node->key = key;
node->data = data;
node->hash = hash;
return node;
error:
return NULL;
}
static inline DArray *Hashmap_find_bucket(Hashmap *map, void *key,
int create, uint32_t *hash_out)
{
uint32_t hash = map->hash(key);
int bucket_n = hash % DEFAULT_NUMBER_OF_BUCKETS;
check(bucket_n >= 0, "Invalid bucket found: %d", bucket_n);
*hash_out = hash; // store it for the return so the caller can use it
DArray *bucket = DArray_get(map->buckets, bucket_n);
if(!bucket && create) {
// new bucket, set it up
bucket = DArray_create(sizeof(void *), DEFAULT_NUMBER_OF_BUCKETS);
check_mem(bucket);
DArray_set(map->buckets, bucket_n, bucket);
}
return bucket;
error:
return NULL;
}
int Hashmap_set(Hashmap *map, void *key, void *data)
{
uint32_t hash = 0;
DArray *bucket = Hashmap_find_bucket(map, key, 1, &hash);
check(bucket, "Error can't create bucket.");
HashmapNode *node = Hashmap_node_create(hash, key, data);
check_mem(node);
DArray_push(bucket, node);
return 0;
error:
return -1;
}
static inline int Hashmap_get_node(Hashmap *map, uint32_t hash, DArray *bucket, void *key)
{
int i = 0;
for(i = 0; i < DArray_end(bucket); i++) {
debug("TRY: %d", i);
HashmapNode *node = DArray_get(bucket, i);
if(node->hash == hash && map->compare(node->key, key) == 0) {
return i;
}
}
return -1;
}
void *Hashmap_get(Hashmap *map, void *key)
{
uint32_t hash = 0;
DArray *bucket = Hashmap_find_bucket(map, key, 0, &hash);
if(!bucket) return NULL;
int i = Hashmap_get_node(map, hash, bucket, key);
if(i == -1) return NULL;
HashmapNode *node = DArray_get(bucket, i);
check(node != NULL, "Failed to get node from bucket when it should exist.");
return node->data;
error: // fallthrough
return NULL;
}
int Hashmap_traverse(Hashmap *map, Hashmap_traverse_cb traverse_cb)
{
int i = 0;
int j = 0;
int rc = 0;
for(i = 0; i < DArray_count(map->buckets); i++) {
DArray *bucket = DArray_get(map->buckets, i);
if(bucket) {
for(j = 0; j < DArray_count(bucket); j++) {
HashmapNode *node = DArray_get(bucket, j);
rc = traverse_cb(node);
if(rc != 0) return rc;
}
}
}
return 0;
}
void *Hashmap_delete(Hashmap *map, void *key)
{
uint32_t hash = 0;
DArray *bucket = Hashmap_find_bucket(map, key, 0, &hash);
if(!bucket) return NULL;
int i = Hashmap_get_node(map, hash, bucket, key);
if(i == -1) return NULL;
HashmapNode *node = DArray_get(bucket, i);
void *data = node->data;
free(node);
HashmapNode *ending = DArray_pop(bucket);
if(ending != node) {
// alright looks like it's not the last one, swap it
DArray_set(bucket, i, ending);
}
return data;
}
```
这个实现中并没有什么复杂的东西，但是`default_hash`和`Hashmap_find_bucket`需要一些解释。当你使用`Hashmap_create`时，你可以传入任何定制的比较和哈希函数。但是如果你没有则会使用`default_compare`和`default_hash`函数。
需要观察的第一件事，是`default_hash`的行为。这是一个简单的哈希函数，叫做“Jenkins hash”，以Bob Jenkins的名字命名。我从[维基百科](http://en.wikipedia.org/wiki/Jenkins_hash_function)上获得了这个算法。它仅仅遍历键（`bstring`）的每个字节来计算哈希，以便得出`uint32_t`的结果。它使用一些加法和异或运算来实现。
哈希函数有很多中，它们具有不同的特性，然而一旦你选择了一种，就需要一种方法来使用它找到正确的桶。`Hashmap_find_bucket`像这样实现它：
+ 首先调用` map->hash(key)`来获得键的哈希值。
+ 之后使用`hash % DEFAULT_NUMBER_OF_BUCKETS`，这样无论哈希值有多大，都能找到匹配的桶。
+ 找到桶之后，它是个`DArray`，可能还没有创建，这取决与`create`变量的内容。
+ 一旦找到了正确的`DArray`桶，就会将它返回，并且`hash_out`变量用于向调用者提供所找到的哈希值。
其它函数都使用`Hashmap_find_bucket`来完成工作：
+ 设置键值对涉及到找到正确的桶，之后创建`HashmapNode`，将它添加到桶中。
+ 获取键值涉及到找到正确的桶，之后找到匹配`hash`和`key`的`HashmapNode`。
+ 删除元素也需要找到正确的桶，找到所需的节点，之后通过与末尾的节点交换位置来删除。
你需要学习的唯一一个其他函数是`Hashmap_travers`，它仅仅遍历每个桶，对于任何含有值的桶，在每个值上调用`traverse_cb`。这就是扫描整个`Hashmap`的办法。
## 单元测试
最后你需要编写单元测试，对于所有这些操作：
```c
#include "minunit.h"
#include
#include
#include
Hashmap *map = NULL;
static int traverse_called = 0;
struct tagbstring test1 = bsStatic("test data 1");
struct tagbstring test2 = bsStatic("test data 2");
struct tagbstring test3 = bsStatic("xest data 3");
struct tagbstring expect1 = bsStatic("THE VALUE 1");
struct tagbstring expect2 = bsStatic("THE VALUE 2");
struct tagbstring expect3 = bsStatic("THE VALUE 3");
static int traverse_good_cb(HashmapNode *node)
{
debug("KEY: %s", bdata((bstring)node->key));
traverse_called++;
return 0;
}
static int traverse_fail_cb(HashmapNode *node)
{
debug("KEY: %s", bdata((bstring)node->key));
traverse_called++;
if(traverse_called == 2) {
return 1;
} else {
return 0;
}
}
char *test_create()
{
map = Hashmap_create(NULL, NULL);
mu_assert(map != NULL, "Failed to create map.");
return NULL;
}
char *test_destroy()
{
Hashmap_destroy(map);
return NULL;
}
char *test_get_set()
{
int rc = Hashmap_set(map, &test1, &expect1);
mu_assert(rc == 0, "Failed to set &test1");
bstring result = Hashmap_get(map, &test1);
mu_assert(result == &expect1, "Wrong value for test1.");
rc = Hashmap_set(map, &test2, &expect2);
mu_assert(rc == 0, "Failed to set test2");
result = Hashmap_get(map, &test2);
mu_assert(result == &expect2, "Wrong value for test2.");
rc = Hashmap_set(map, &test3, &expect3);
mu_assert(rc == 0, "Failed to set test3");
result = Hashmap_get(map, &test3);
mu_assert(result == &expect3, "Wrong value for test3.");
return NULL;
}
char *test_traverse()
{
int rc = Hashmap_traverse(map, traverse_good_cb);
mu_assert(rc == 0, "Failed to traverse.");
mu_assert(traverse_called == 3, "Wrong count traverse.");
traverse_called = 0;
rc = Hashmap_traverse(map, traverse_fail_cb);
mu_assert(rc == 1, "Failed to traverse.");
mu_assert(traverse_called == 2, "Wrong count traverse for fail.");
return NULL;
}
char *test_delete()
{
bstring deleted = (bstring)Hashmap_delete(map, &test1);
mu_assert(deleted != NULL, "Got NULL on delete.");
mu_assert(deleted == &expect1, "Should get test1");
bstring result = Hashmap_get(map, &test1);
mu_assert(result == NULL, "Should delete.");
deleted = (bstring)Hashmap_delete(map, &test2);
mu_assert(deleted != NULL, "Got NULL on delete.");
mu_assert(deleted == &expect2, "Should get test2");
result = Hashmap_get(map, &test2);
mu_assert(result == NULL, "Should delete.");
deleted = (bstring)Hashmap_delete(map, &test3);
mu_assert(deleted != NULL, "Got NULL on delete.");
mu_assert(deleted == &expect3, "Should get test3");
result = Hashmap_get(map, &test3);
mu_assert(result == NULL, "Should delete.");
return NULL;
}
char *all_tests()
{
mu_suite_start();
mu_run_test(test_create);
mu_run_test(test_get_set);
mu_run_test(test_traverse);
mu_run_test(test_delete);
mu_run_test(test_destroy);
return NULL;
}
RUN_TESTS(all_tests);
```
需要学习的唯一一件事情就是我在单元测试的顶端使用了`bstring`的特性来创建静态字符串用于测试。我使用`tagbstring`和`bsStatic`在7~13行创建他们。
## 如何改进
这是一个非常简单的`Hashmap`实现，就像书中的大多数其他数据结构那样。我的目标不是让你以非常快的速度来掌握数据结构。通常这些讨论起来非常复杂，并且会让你偏离真正的基础和实用的数据结构。我的目标是提供一个易于理解的起始点，然后再改进或理解它们如何实现。
对于这和练习，下面是你能够用于改进这个实现的方法：
+ 你可以对每个桶进行排序，使它们有序。这会增加你的插入时间，但是减少寻找时间，因为你可以使用二分搜索来寻找每个节点。到现在为止它遍历桶中的所有节点来寻找元素。
+ 你可以动态设定桶的数量，或者让调用者指定每个`Hashmap`中的该值。
+ 你可以使用更好的`default_hash`函数，有许多这样的函数。
+ 这个实现以及几乎所有实现都有将一些特定的键存到一个桶中的风险。这会使你的程序运行速度变慢，因为它使`Hashmap`的处理过程变成了处理单个的`DArray`。如果你对桶中的数组排序会有帮助，但是你可以仅仅使用更好的哈希函数来避免，并且对于真正的偏执狂，你可以添加一个随机的盐，让键不可预测。
+ 你可以删掉不歪有任何节点的桶来节约空间，或者将空的桶当如缓存中，便于节约创建和销毁它们的开销。
+ 现在为止它可以添加已存在的元素，编写一个替代的实现，使它只能够添加不存在的元素。
像往常一样，你需要浏览每个函数，并且使之健壮。`Hashmap`也可以使用一些调试设置，来执行不变量检查。
## 附加题
+ 研究你最喜欢的编程语言的`Hashmap`实现，了解它们具有什么特性。
+ 找到`Hashmap`的主要缺点，以及如何避免它们。例如，它们不做特定的修改就不能保存顺序，并且当你基于键的一部分来查找元素时，它们就不能生效。
+ 编写单元测试来展示将键都填充到`Hashmap`的一个桶中所带来的缺陷，之后测试这样如何影响性能。一个实现它的好方法，就是把桶的数量减少到一个愚蠢的数值，比如1。
';
练习36：更安全的字符串
最后更新于：2022-04-01 23:29:19
# 练习36：更安全的字符串
> 原文：[Exercise 36: Safer Strings](http://c.learncodethehardway.org/book/ex36.html)
> 译者：[飞龙](https://github.com/wizardforcel)
我已经在练习26中，构建`devpkg`的时候介绍了[Better String](http://bstring.sourceforge.net/)库。这个练习让你从现在开始熟悉`bstring`库，并且明白C风格字符串为什么十分糟糕。之后你需要修改`liblcthw`的代码来使用`bstring`。
## 为什么C风格字符串十分糟糕
当人们谈论C的问题时，“字符串”的概念永远是首要缺陷之一。你已经用过它们，并且我也谈论过它们的种种缺陷，但是对为什么C字符串拥有缺陷，以及为什么一直是这样没有明确的解释。我会试着现在做出解释，部分原因是C风格字符串经过数十年的使用，有足够的证据表明它们是个非常糟糕的东西。
对于给定的任何C风格字符串，都不可能验证它是否有效。
+ 以`'\0'`结尾的C字符串是有效的。
+ 任何处理无效C字符串的循环都是无限的（或者造成缓冲区溢出）。
+ C字符串没有确定的长度，所以检查它们的唯一方法就是遍历它来观察循环是否正确终止。
+ 所以，不通过有限的循环就不可能验证C字符串。
这个逻辑非常简单。你不能编写一个循环来验证C字符串是否有效，因为无效的字符串导致循环永远不会停止。就是这样，唯一的解决方案就是包含大小。一旦你知道了大小，你可以避免无限循环问题。如果你观察练习27中我向你展示的两个函数：
> 译者注：检验C风格字符串是否有效等价于“停机问题”，这是一个非常著名的不可解问题。
```c
void copy(char to[], char from[])
{
int i = 0;
// while loop will not end if from isn't '\0' terminated
while((to[i] = from[i]) != '\0') {
++i;
}
}
int safercopy(int from_len, char *from, int to_len, char *to)
{
int i = 0;
int max = from_len > to_len - 1 ? to_len - 1 : from_len;
// to_len must have at least 1 byte
if(from_len < 0 || to_len <= 0) return -1;
for(i = 0; i < max; i++) {
to[i] = from[i];
}
to[to_len - 1] = '\0';
return i;
}
```
想象你想要向`copy`函数添加检查来确保`from`字符串有效。你该怎么做呢？你编写了一个循环来检查字符串是否已`'\0'`结尾。哦，等一下，如果字符串不以`'\0'`结尾，那它怎么让循环停下？不可能停下，所以无解。
无论你怎么做，你都不能在不知道字符串长度的情况下检查C字符串的有效性，这里`safercopy`包含了程度。这个函数没有相同的问题，因为他的循环一定会中止，即使你传入了错误的大小，大小也是有限的。
> 译者注：但是问题来了，对于一个C字符串，你怎么获取其大小？你需要在这个函数之前调用`strlen`，又是一个无限循环问题。
于是，`bstring`库所做的事情就是创建一个结构体，它总是包含字符串长度。由于这个长度对于`bstring`来说总是可访问的，它上面的所有操作都会更安全。循环是有限的，内容也是有效的，并且这个主要的缺陷也不存在了。BString库也带有大量所需的字串操作，比如分割、格式化、搜索，并且大多数都会正确并安全地执行。
`bstring`中也可能有缺陷，但是经过这么长时间，可能性已经很低了。`glibc`中也有缺陷，所以你让程序员怎么做才好呢？
## 使用 bstrlib
有很多改进后的字符串库，但是我最喜欢`bstrlib`，因为它只有一个程序集，并且具有大多数所需的字符串功能。你已经在使用它了，所以这个练习中你需要从[Better String](http://bstring.sourceforge.net/)获取两个文件，`bstrlib.c`和`bstrlib.h`。
下面是我在`liblcthw`项目目录里所做的事情：
```sh
$ mkdir bstrlib
$ cd bstrlib/
$ unzip ~/Downloads/bstrlib-05122010.zip
Archive: /Users/zedshaw/Downloads/bstrlib-05122010.zip
...
$ ls
bsafe.c bstraux.c bstrlib.h bstrwrap.h license.txt test.cpp
bsafe.h bstraux.h bstrlib.txt cpptest.cpp porting.txt testaux.c
bstest.c bstrlib.c bstrwrap.cpp gpl.txt security.txt
$ mv bstrlib.h bstrlib.c ../src/lcthw/
$ cd ../
$ rm -rf bstrlib
# make the edits
$ vim src/lcthw/bstrlib.c
$ make clean all
...
$
```
在第14行你可以看到，我编辑了`bstrlib.c`文件，来将它移动到新的位置，并且修复OSX上的bug。下面是差异：
```diff
25c25
< #include "bstrlib.h"
---
> #include
2759c2759
< #ifdef __GNUC__
---
> #if defined(__GNUC__) && !defined(__APPLE__)
```
我把包含修改为``，然后修复2759行`ifdef`的问题。
## 学习使用该库
这个练习很短，只是让你准备好剩余的练习，它们会用到这个库。接下来两个联系中，我会使用`bstrlib.c`来创建Hashmap`数据结构。
你现在应该阅读头文件和实现，之后编写`tests/bstr_tests.c`来测试下列函数，来熟悉这个库：
`bfromcstr`
从C风格字符串中创建一个`bstring`。
`blk2bstr`
与上面相同，但是可以提供缓冲区长度。
`bstrcpy`
复制`bstring`。
`bassign`
将一个`bstring`赋值为另一个。
`bassigncstr`
将`bsting`的内容设置为C字符串的内容。
`bassignblk`
将`bsting`的内容设置为C字符串的内容，但是可以提供长度。
`bdestroy`
销毁`bstring`。
`bconcat`
在一个`bstring`末尾连接另一个。
`bstricmp`
比较两个`bstring`，返回值与`strcmp`相同。
`biseq`
检查两个`bstring`是否相等。
`binstr`
判断一个`bstring`是否被包含于另一个。
`bfindreplace`
在一个`bstring`中寻找另一个，并且将其替换为别的。
`bsplit`
将`bstring`分割为`bstrList`。
`bformat`
执行字符串格式化，十分便利。
`blength`
获取`bstring`的长度。
`bdata`
获取`bstring`的数据。
`bchar`
获得`bstring`中的字符。
你的测试应该覆盖到所有这些操作，以及你从头文件中发现的更多有趣的东西。在`valgrind`下运行测试，确保内存使用正确。
';
练习35：排序和搜索
最后更新于：2022-04-01 23:29:17
# 练习35：排序和搜索
> 原文：[Exercise 35: Sorting And Searching](http://c.learncodethehardway.org/book/ex35.html)
> 译者：[飞龙](https://github.com/wizardforcel)
这个练习中我打算涉及到四个排序算法和一个搜索算法。排序算法是快速排序、堆排序、归并排序和基数排序。之后在你完成基数排序之后，我打算想你展示二分搜索。
然而，我是一个懒人，大多数C标准库都实现了堆排序、快速排序和归并排序算法，你可以直接使用它们：
```c
#include
#include
int DArray_qsort(DArray *array, DArray_compare cmp)
{
qsort(array->contents, DArray_count(array), sizeof(void *), cmp);
return 0;
}
int DArray_heapsort(DArray *array, DArray_compare cmp)
{
return heapsort(array->contents, DArray_count(array), sizeof(void *), cmp);
}
int DArray_mergesort(DArray *array, DArray_compare cmp)
{
return mergesort(array->contents, DArray_count(array), sizeof(void *), cmp);
}
```
这就是`darray_algos.c`文件的整个实现，它在大多数现代Unix系统上都能运行。它们的每一个都使用`DArray_compare`对`contents`中储存的无类型指针进行排序。我也要向你展示这个头文件：
```c
#ifndef darray_algos_h
#define darray_algos_h
#include
typedef int (*DArray_compare)(const void *a, const void *b);
int DArray_qsort(DArray *array, DArray_compare cmp);
int DArray_heapsort(DArray *array, DArray_compare cmp);
int DArray_mergesort(DArray *array, DArray_compare cmp);
#endif
```
大小几乎一样，你也应该能预料到。接下来你可以了解单元测试中这三个函数如何使用：
```c
#include "minunit.h"
#include
int testcmp(char **a, char **b)
{
return strcmp(*a, *b);
}
DArray *create_words()
{
DArray *result = DArray_create(0, 5);
char *words[] = {"asdfasfd", "werwar", "13234", "asdfasfd", "oioj"};
int i = 0;
for(i = 0; i < 5; i++) {
DArray_push(result, words[i]);
}
return result;
}
int is_sorted(DArray *array)
{
int i = 0;
for(i = 0; i < DArray_count(array) - 1; i++) {
if(strcmp(DArray_get(array, i), DArray_get(array, i+1)) > 0) {
return 0;
}
}
return 1;
}
char *run_sort_test(int (*func)(DArray *, DArray_compare), const char *name)
{
DArray *words = create_words();
mu_assert(!is_sorted(words), "Words should start not sorted.");
debug("--- Testing %s sorting algorithm", name);
int rc = func(words, (DArray_compare)testcmp);
mu_assert(rc == 0, "sort failed");
mu_assert(is_sorted(words), "didn't sort it");
DArray_destroy(words);
return NULL;
}
char *test_qsort()
{
return run_sort_test(DArray_qsort, "qsort");
}
char *test_heapsort()
{
return run_sort_test(DArray_heapsort, "heapsort");
}
char *test_mergesort()
{
return run_sort_test(DArray_mergesort, "mergesort");
}
char * all_tests()
{
mu_suite_start();
mu_run_test(test_qsort);
mu_run_test(test_heapsort);
mu_run_test(test_mergesort);
return NULL;
}
RUN_TESTS(all_tests);
```
你需要注意的事情是第四行`testcmp`的定义，它困扰了我一整天。你必须使用`char **`而不是`char *`，因为`qsort`会向你提供指向`content`数组中指针的指针。原因是`qsort`会打扫数组，使用你的比较函数来处理数组中每个元素的指针。因为我在`contents`中存储指针，所以你需要使用指针的指针。
有了这些之后，你只需要实现三个困难的搜索算法，每个大约20行。你应该在这里停下来，不过这本书的一部分就是学习这些算法的原理，附加题会涉及到实现这些算法。
## 基数排序和二分搜索
既然你打算自己实现快速排序、堆排序和归并排序，我打算向你展示一个流行的算法叫做基数排序。它的实用性很小，只能用于整数数组，并且看上去像魔法一样。这里我打算常见一个特殊的数据结构，叫做`RadixMap`，用于将一个整数映射为另一个。
下面是为新算法创建的头文件，其中也含有数据结构：
```c
#ifndef _radixmap_h
#include
typedef union RMElement {
uint64_t raw;
struct {
uint32_t key;
uint32_t value;
} data;
} RMElement;
typedef struct RadixMap {
size_t max;
size_t end;
uint32_t counter;
RMElement *contents;
RMElement *temp;
} RadixMap;
RadixMap *RadixMap_create(size_t max);
void RadixMap_destroy(RadixMap *map);
void RadixMap_sort(RadixMap *map);
RMElement *RadixMap_find(RadixMap *map, uint32_t key);
int RadixMap_add(RadixMap *map, uint32_t key, uint32_t value);
int RadixMap_delete(RadixMap *map, RMElement *el);
#endif
```
你看到了其中有许多和`Dynamic Array`或`List`数据结构相同的操作，不同就在于我只处理固定32位大小的`uint32_t`正忽视。我也会想你介绍C语言的一个新概念，叫做`union`。
## C联合体
联合体是使用不同方式引用内存中同一块区域的方法。它们的工作方式，就像你把它定义为`sturct`，然而，每个元素共享同一片内存区域。你可以认为，联合体是内存中的一幅画，所有颜色不同的元素都重叠在它上面。
它可以用于节约内存，或在不同格式之间转换内存块。它的第一个用途就是实现“可变类型”，你可以创建一个带有类型“标签”的结构体，之后在其中创建含有多种类型的联合体。用于在内存的不同格式之间转换时，只需要定义两个结构体，访问正确的那个类型。
首先让我向你展示如何使用C联合体构造可变类型：
```c
#include
typedef enum {
TYPE_INT,
TYPE_FLOAT,
TYPE_STRING,
} VariantType;
struct Variant {
VariantType type;
union {
int as_integer;
float as_float;
char *as_string;
} data;
};
typedef struct Variant Variant;
void Variant_print(Variant *var)
{
switch(var->type) {
case TYPE_INT:
printf("INT: %d\n", var->data.as_integer);
break;
case TYPE_FLOAT:
printf("FLOAT: %f\n", var->data.as_float);
break;
case TYPE_STRING:
printf("STRING: %s\n", var->data.as_string);
break;
default:
printf("UNKNOWN TYPE: %d", var->type);
}
}
int main(int argc, char *argv[])
{
Variant a_int = {.type = TYPE_INT, .data.as_integer = 100};
Variant a_float = {.type = TYPE_FLOAT, .data.as_float = 100.34};
Variant a_string = {.type = TYPE_STRING, .data.as_string = "YO DUDE!"};
Variant_print(&a_int);
Variant_print(&a_float);
Variant_print(&a_string);
// here's how you access them
a_int.data.as_integer = 200;
a_float.data.as_float = 2.345;
a_string.data.as_string = "Hi there.";
Variant_print(&a_int);
Variant_print(&a_float);
Variant_print(&a_string);
return 0;
}
```
你可以在许多动态语言实现中发现它。对于为语言中所有基本类型，代码中首先定义了一些带有变迁的可变类型，之后通常给你所创建的类型打上`object`标签。这样的好处就是`Variant`通常只需要`VariantType type`标签的空间，加上联合体最大成员的空间，因为C将`Variant.data`的每个元素堆起来，它们是重叠的，只保证有足够的空间放下最大的元素。
`radixmap.h`文件中我创建了`RMElement`联合体，用于在类型之间转换内存块。这里，我希望存储`uint64_t`定长整数用于排序目录，但是我也希望使用两个`uint32_t`用于表示数据的`key`和`value`对。通过使用联合体我就能够使用所需的两种不同方法来访问内存。
## 实现
接下来是实际的`RadixMap`对于这些操作的实现：
```c
/*
* Based on code by Andre Reinald then heavily modified by Zed A. Shaw.
*/
#include
#include
#include
#include
#include
RadixMap *RadixMap_create(size_t max)
{
RadixMap *map = calloc(sizeof(RadixMap), 1);
check_mem(map);
map->contents = calloc(sizeof(RMElement), max + 1);
check_mem(map->contents);
map->temp = calloc(sizeof(RMElement), max + 1);
check_mem(map->temp);
map->max = max;
map->end = 0;
return map;
error:
return NULL;
}
void RadixMap_destroy(RadixMap *map)
{
if(map) {
free(map->contents);
free(map->temp);
free(map);
}
}
#define ByteOf(x,y) (((uint8_t *)x)[(y)])
static inline void radix_sort(short offset, uint64_t max, uint64_t *source, uint64_t *dest)
{
uint64_t count[256] = {0};
uint64_t *cp = NULL;
uint64_t *sp = NULL;
uint64_t *end = NULL;
uint64_t s = 0;
uint64_t c = 0;
// count occurences of every byte value
for (sp = source, end = source + max; sp < end; sp++) {
count[ByteOf(sp, offset)]++;
}
// transform count into index by summing elements and storing into same array
for (s = 0, cp = count, end = count + 256; cp < end; cp++) {
c = *cp;
*cp = s;
s += c;
}
// fill dest with the right values in the right place
for (sp = source, end = source + max; sp < end; sp++) {
cp = count + ByteOf(sp, offset);
dest[*cp] = *sp;
++(*cp);
}
}
void RadixMap_sort(RadixMap *map)
{
uint64_t *source = &map->contents[0].raw;
uint64_t *temp = &map->temp[0].raw;
radix_sort(0, map->end, source, temp);
radix_sort(1, map->end, temp, source);
radix_sort(2, map->end, source, temp);
radix_sort(3, map->end, temp, source);
}
RMElement *RadixMap_find(RadixMap *map, uint32_t to_find)
{
int low = 0;
int high = map->end - 1;
RMElement *data = map->contents;
while (low <= high) {
int middle = low + (high - low)/2;
uint32_t key = data[middle].data.key;
if (to_find < key) {
high = middle - 1;
} else if (to_find > key) {
low = middle + 1;
} else {
return &data[middle];
}
}
return NULL;
}
int RadixMap_add(RadixMap *map, uint32_t key, uint32_t value)
{
check(key < UINT32_MAX, "Key can't be equal to UINT32_MAX.");
RMElement element = {.data = {.key = key, .value = value}};
check(map->end + 1 < map->max, "RadixMap is full.");
map->contents[map->end++] = element;
RadixMap_sort(map);
return 0;
error:
return -1;
}
int RadixMap_delete(RadixMap *map, RMElement *el)
{
check(map->end > 0, "There is nothing to delete.");
check(el != NULL, "Can't delete a NULL element.");
el->data.key = UINT32_MAX;
if(map->end > 1) {
// don't bother resorting a map of 1 length
RadixMap_sort(map);
}
map->end--;
return 0;
error:
return -1;
}
```
像往常一样键入它并使它通过单元测试，之后我会解释它。尤其要注意`radix_sort`函数，我实现它的方法非常特别。
```c
#include "minunit.h"
#include
#include
static int make_random(RadixMap *map)
{
size_t i = 0;
for (i = 0; i < map->max - 1; i++) {
uint32_t key = (uint32_t)(rand() | (rand() << 16));
check(RadixMap_add(map, key, i) == 0, "Failed to add key %u.", key);
}
return i;
error:
return 0;
}
static int check_order(RadixMap *map)
{
RMElement d1, d2;
unsigned int i = 0;
// only signal errors if any (should not be)
for (i = 0; map->end > 0 && i < map->end-1; i++) {
d1 = map->contents[i];
d2 = map->contents[i+1];
if(d1.data.key > d2.data.key) {
debug("FAIL:i=%u, key: %u, value: %u, equals max? %d\n", i, d1.data.key, d1.data.value,
d2.data.key == UINT32_MAX);
return 0;
}
}
return 1;
}
static int test_search(RadixMap *map)
{
unsigned i = 0;
RMElement *d = NULL;
RMElement *found = NULL;
for(i = map->end / 2; i < map->end; i++) {
d = &map->contents[i];
found = RadixMap_find(map, d->data.key);
check(found != NULL, "Didn't find %u at %u.", d->data.key, i);
check(found->data.key == d->data.key, "Got the wrong result: %p:%u looking for %u at %u",
found, found->data.key, d->data.key, i);
}
return 1;
error:
return 0;
}
// test for big number of elements
static char *test_operations()
{
size_t N = 200;
RadixMap *map = RadixMap_create(N);
mu_assert(map != NULL, "Failed to make the map.");
mu_assert(make_random(map), "Didn't make a random fake radix map.");
RadixMap_sort(map);
mu_assert(check_order(map), "Failed to properly sort the RadixMap.");
mu_assert(test_search(map), "Failed the search test.");
mu_assert(check_order(map), "RadixMap didn't stay sorted after search.");
while(map->end > 0) {
RMElement *el = RadixMap_find(map, map->contents[map->end / 2].data.key);
mu_assert(el != NULL, "Should get a result.");
size_t old_end = map->end;
mu_assert(RadixMap_delete(map, el) == 0, "Didn't delete it.");
mu_assert(old_end - 1 == map->end, "Wrong size after delete.");
// test that the end is now the old value, but uint32 max so it trails off
mu_assert(check_order(map), "RadixMap didn't stay sorted after delete.");
}
RadixMap_destroy(map);
return NULL;
}
char *all_tests()
{
mu_suite_start();
srand(time(NULL));
mu_run_test(test_operations);
return NULL;
}
RUN_TESTS(all_tests);
```
我不应该向你解释关于测试的过多东西，它只是模拟将随机正是放入`RadixMap`，确保你可以可靠地将其取出。也不是非常有趣。
在`radixmap.c`中的大多数操作都易于理解，如果你阅读代码的话。下面是每个基本函数作用及其工作原理的描述：
RadixMap_create
像往常一样，我分配了结构体所需的内存，结构体在`radixmap.h`中定义。当后面涉及到`radix_sort`时我会使用`temp`和`contents`。
RadixMap_destroy
同样，销毁我所创建的东西。
radix_sort
这个数据结构的灵魂，我会在下一节中解释其作用。
RadixMap_sort
它使用了`radix_sort`函数来实际对`contents`进行排序。
RadixMap_find
使用二分搜索算法来寻找提供的`key`，我之后会解释它的原理。
RadixMap_add
使用`RadixMap_sort`函数，它会在末尾添加`key`和`value`，然后简单地重新排序使一切元素都有序。一旦排序完，`RadixMap_find`会正确工作，因为它是二分搜索。
RadixMap_delete
工作方式类似`RadixMap_add`，除了“删除”结构中的元素，通过将它们的值设为无符号的32为整数的最大值，也就是`UINT32_MAX`。这意味着你不能使用这个值作为合法的键，但是它是元素删除变得容易。简单设置它之后排序，它会被移动到末尾，这就算删除了。
学习我所描述的代码，接下来还剩`RadixMap_sort`，`radix_sort`和`RadixMap_find`需要了解。
## RadixMap_find 和二分搜索
我首先以二分搜索如何实现开始。二分搜索是一种简单算法，大多数人都可以直观地理解。实际上，你可以取一叠游戏卡片（或带有数字的卡片）来手动操作。下面是该函数的工作方式，也是二分搜索的原理：
+ 基于数组大小设置上界和下界。
+ 获取上下界之间的中间元素。
+ 如果键小于这个元素的值，就一定在它前面，所以上界设置为中间元素。
+ 如果键大于这个元素的值，就一定在它后面，所以下界设置为中间元素。
+ 继续循环直到上界和下界越过了彼此。如果退出了循环则没有找到。
你实际上所做的事情是，通过挑选中间的值来比较，猜出`key`可能的位置。由于数据是有序的，你知道`key`一定会在它前面或者后面，这样就能把搜索区域分成两半。之后你继续搜索知道找到他，或者越过了边界并穷尽了搜索空间。
## RadixMap_sort 和 radix_sort
如果你事先手动模拟基数排序，它就很易于理解。这个算法利用了一个现象，数字都以十进制字符的序列来表示，按照“不重要”到“重要”的顺序排列。之后它通过十进制字符来选取数字并且将它们储存在桶中，当它处理完所有字符时，数字就排好序了。一开始它看上去像是魔法，浏览代码也的确如此，但是你要尝试手动执行它。
为了解释这个算法，需要先写下一组三位的十进制数，以随机的顺序，假设就是223、912、275、100、633、120 和 380。
+ 按照它们的个位，将数字放入桶中：`[380, 100, 120], [912], [633, 223], [275]`。
+ 现在遍历每个桶中的数字，接着按十位排序：`[100], [912], [120, 223], [633], [275], [380]`。
+ 现在每个桶都包含了按照个位和十位排序后的数字。接着我需要按照这个顺序遍历，并把它们放入最后百位的桶中：`[100, 120], [223, 275], [380], [633], [912]`。
+ 到现在为止，每个数字都按照百位、十位和个位排序，并且如果我按照顺序遍历每个桶，我会得到最终排序的结果：`100, 120, 223, 275, 380, 633, 912`。
确保你多次重复了这个过程，便于你理解它如何工作。这实在是一种机智的算法，并且最重要的是它对于任何大小的数字都有效。所以你可以用它来排序比较大的数字，因为你一次只是处理一位。
在我的环境下，“字符”是独立的8位字节，所以我需要256个桶来储存这些数字按照字节的分布结果。我需要一种方法来储存它，并且不需要花费太多的空间。如果你查看`radix_sort`，首先我会构建`count`直方图，便于我了解对于给定的`offset`，每个字节的频率。
一旦我知道了每一种字节的数量（共有256种），我就可以将目标数组用于存储这些值的分布。比如，如果0x00的数量为10个，我就可以将它们放在目标数组的前10个位置中。这可以让我索引到它们在目标数组中的位置，这就是`radix_sort`中的第二个`for`循环。
最后，当我知道它们在目标数组中储存在哪里，我只是遍历`source`数组对于当前`offset`的所有字节，并且将数值按顺序放入它们的位置中。`ByteOf`宏的使用有助于保持代码整洁，因为它需要一些指针的黑魔法，但是最后当`for`循环结束之后，所有整数都会按照它们的字节放入桶中。
我在`RadixMap_sort`中对这些64位的整数按照它们的前32位进行排序，这非常有意思。还记得我是如何将键和值放入`RMElement`类型的联合体了吗？这意味着如果要按照键来对这个数组排序，我只需要对每个整数前4个字节（32位/8位每字节）进行排序。
如果你观察`RadixMap_sort`，你会看到我获取了`contents`和`temp`的便利指针，用于源数组和目标数组，之后我四次调用`radix_sort`。每次调用我将源数组和目标数组替换为下一字节的情况。当我完成时，`radix_sort`就完成了任务，并且`contents`中也有了最后的结果。
## 如何改进
这个实现有个很大的缺点，就是它遍历了整个数组四次。它执行地很快，但是如果你通过需要排序的数值大小来限制排序的总量，会更好一些。
有两个方法可以用于改进这个实现：
+ 使用二分搜索来寻找新元素的最小位置，只对这个位置到微末之间进行排序。你需要找到它，将新元素放到末尾，之后对它们之间进行排序。大多数情况下这会显著地缩减排序范围。
+ 跟踪当前所使用的最大的键，之后只对足够的位数进行排序，来处理这个键。你也可以跟踪最小的数值，之后只对范围中必要的字节进行排序。为了这样做，你需要关心CPU的整数存储顺序（大小端序）。
## 附加题
+ 实现快速排序、堆排序和归并排序，并且提供一个`#define`让其他人在二者（标准库和你的实现）当中进行选择，或者创建另一套不同名称的函数。使用我教给你的技巧，阅读维基百科的算法页面，之后参照伪代码来实现它。
+ 对比你的实现和标准库实现的性能。
+ 使用这些排序函数创建`DArray_sort_add`，它可以向`DArray`添加元素，但是随后对数组排序。
+ 编写`DArray_find`，使用`RadixMap_find`中的二分搜索算法和`DArray_compare`，来在有序的`DArray`中寻找元素。
';
练习34：动态数组
最后更新于：2022-04-01 23:29:15
# 练习34：动态数组
> 原文：[Exercise 34: Dynamic Array](http://c.learncodethehardway.org/book/ex34.html)
> 译者：[飞龙](https://github.com/wizardforcel)
动态数组是自增长的数组，它与链表有很多相同的特性。它通常占据更少的空间，跑得更快，还有一些其它的优势属性。这个练习会涉及到它的一些缺点，比如从开头移除元素会很慢，并给出解决方案（只从末尾移除）。
动态数组简单地实现为`void **`指针的数组，它是预分配内存的，并且指向数据。在链表中你创建了完整的结构体来储存`void *value`指针，但是动态数组中你只需要一个储存它们的单个数组。也就是说，你并不需要创建任何其它的指针储存上一个或下一个元素。它们可以直接索引。
我会给你头文件作为起始，你需要为实现打下它们：
```c
#ifndef _DArray_h
#define _DArray_h
#include
#include
#include
typedef struct DArray {
int end;
int max;
size_t element_size;
size_t expand_rate;
void **contents;
} DArray;
DArray *DArray_create(size_t element_size, size_t initial_max);
void DArray_destroy(DArray *array);
void DArray_clear(DArray *array);
int DArray_expand(DArray *array);
int DArray_contract(DArray *array);
int DArray_push(DArray *array, void *el);
void *DArray_pop(DArray *array);
void DArray_clear_destroy(DArray *array);
#define DArray_last(A) ((A)->contents[(A)->end - 1])
#define DArray_first(A) ((A)->contents[0])
#define DArray_end(A) ((A)->end)
#define DArray_count(A) DArray_end(A)
#define DArray_max(A) ((A)->max)
#define DEFAULT_EXPAND_RATE 300
static inline void DArray_set(DArray *array, int i, void *el)
{
check(i < array->max, "darray attempt to set past max");
if(i > array->end) array->end = i;
array->contents[i] = el;
error:
return;
}
static inline void *DArray_get(DArray *array, int i)
{
check(i < array->max, "darray attempt to get past max");
return array->contents[i];
error:
return NULL;
}
static inline void *DArray_remove(DArray *array, int i)
{
void *el = array->contents[i];
array->contents[i] = NULL;
return el;
}
static inline void *DArray_new(DArray *array)
{
check(array->element_size > 0, "Can't use DArray_new on 0 size darrays.");
return calloc(1, array->element_size);
error:
return NULL;
}
#define DArray_free(E) free((E))
#endif
```
这个头文件向你展示了`static inline`的新技巧，它就类似`#define`宏的工作方式，但是它们更清楚，并且易于编写。如果你需要创建一块代码作为宏，并且不需要代码生成，可以使用`static inline`函数。
为链表生成`for`循环的`LIST_FOREACH`不可能写为`static inline`函数，因为它需要生成循环的内部代码块。实现它的唯一方式是灰调函数，但是这不够块，并且难以使用。
之后我会修改代码，并且让你创建`DArray`的单元测试。
```c
#include "minunit.h"
#include
static DArray *array = NULL;
static int *val1 = NULL;
static int *val2 = NULL;
char *test_create()
{
array = DArray_create(sizeof(int), 100);
mu_assert(array != NULL, "DArray_create failed.");
mu_assert(array->contents != NULL, "contents are wrong in darray");
mu_assert(array->end == 0, "end isn't at the right spot");
mu_assert(array->element_size == sizeof(int), "element size is wrong.");
mu_assert(array->max == 100, "wrong max length on initial size");
return NULL;
}
char *test_destroy()
{
DArray_destroy(array);
return NULL;
}
char *test_new()
{
val1 = DArray_new(array);
mu_assert(val1 != NULL, "failed to make a new element");
val2 = DArray_new(array);
mu_assert(val2 != NULL, "failed to make a new element");
return NULL;
}
char *test_set()
{
DArray_set(array, 0, val1);
DArray_set(array, 1, val2);
return NULL;
}
char *test_get()
{
mu_assert(DArray_get(array, 0) == val1, "Wrong first value.");
mu_assert(DArray_get(array, 1) == val2, "Wrong second value.");
return NULL;
}
char *test_remove()
{
int *val_check = DArray_remove(array, 0);
mu_assert(val_check != NULL, "Should not get NULL.");
mu_assert(*val_check == *val1, "Should get the first value.");
mu_assert(DArray_get(array, 0) == NULL, "Should be gone.");
DArray_free(val_check);
val_check = DArray_remove(array, 1);
mu_assert(val_check != NULL, "Should not get NULL.");
mu_assert(*val_check == *val2, "Should get the first value.");
mu_assert(DArray_get(array, 1) == NULL, "Should be gone.");
DArray_free(val_check);
return NULL;
}
char *test_expand_contract()
{
int old_max = array->max;
DArray_expand(array);
mu_assert((unsigned int)array->max == old_max + array->expand_rate, "Wrong size after expand.");
DArray_contract(array);
mu_assert((unsigned int)array->max == array->expand_rate + 1, "Should stay at the expand_rate at least.");
DArray_contract(array);
mu_assert((unsigned int)array->max == array->expand_rate + 1, "Should stay at the expand_rate at least.");
return NULL;
}
char *test_push_pop()
{
int i = 0;
for(i = 0; i < 1000; i++) {
int *val = DArray_new(array);
*val = i * 333;
DArray_push(array, val);
}
mu_assert(array->max == 1201, "Wrong max size.");
for(i = 999; i >= 0; i--) {
int *val = DArray_pop(array);
mu_assert(val != NULL, "Shouldn't get a NULL.");
mu_assert(*val == i * 333, "Wrong value.");
DArray_free(val);
}
return NULL;
}
char * all_tests() {
mu_suite_start();
mu_run_test(test_create);
mu_run_test(test_new);
mu_run_test(test_set);
mu_run_test(test_get);
mu_run_test(test_remove);
mu_run_test(test_expand_contract);
mu_run_test(test_push_pop);
mu_run_test(test_destroy);
return NULL;
}
RUN_TESTS(all_tests);
```
这向你展示了所有操作都如何使用，它会使`DArray`的实现变得容易：
```c
#include
#include
DArray *DArray_create(size_t element_size, size_t initial_max)
{
DArray *array = malloc(sizeof(DArray));
check_mem(array);
array->max = initial_max;
check(array->max > 0, "You must set an initial_max > 0.");
array->contents = calloc(initial_max, sizeof(void *));
check_mem(array->contents);
array->end = 0;
array->element_size = element_size;
array->expand_rate = DEFAULT_EXPAND_RATE;
return array;
error:
if(array) free(array);
return NULL;
}
void DArray_clear(DArray *array)
{
int i = 0;
if(array->element_size > 0) {
for(i = 0; i < array->max; i++) {
if(array->contents[i] != NULL) {
free(array->contents[i]);
}
}
}
}
static inline int DArray_resize(DArray *array, size_t newsize)
{
array->max = newsize;
check(array->max > 0, "The newsize must be > 0.");
void *contents = realloc(array->contents, array->max * sizeof(void *));
// check contents and assume realloc doesn't harm the original on error
check_mem(contents);
array->contents = contents;
return 0;
error:
return -1;
}
int DArray_expand(DArray *array)
{
size_t old_max = array->max;
check(DArray_resize(array, array->max + array->expand_rate) == 0,
"Failed to expand array to new size: %d",
array->max + (int)array->expand_rate);
memset(array->contents + old_max, 0, array->expand_rate + 1);
return 0;
error:
return -1;
}
int DArray_contract(DArray *array)
{
int new_size = array->end < (int)array->expand_rate ? (int)array->expand_rate : array->end;
return DArray_resize(array, new_size + 1);
}
void DArray_destroy(DArray *array)
{
if(array) {
if(array->contents) free(array->contents);
free(array);
}
}
void DArray_clear_destroy(DArray *array)
{
DArray_clear(array);
DArray_destroy(array);
}
int DArray_push(DArray *array, void *el)
{
array->contents[array->end] = el;
array->end++;
if(DArray_end(array) >= DArray_max(array)) {
return DArray_expand(array);
} else {
return 0;
}
}
void *DArray_pop(DArray *array)
{
check(array->end - 1 >= 0, "Attempt to pop from empty array.");
void *el = DArray_remove(array, array->end - 1);
array->end--;
if(DArray_end(array) > (int)array->expand_rate && DArray_end(array) % array->expand_rate) {
DArray_contract(array);
}
return el;
error:
return NULL;
}
```
这占你展示了另一种处理复杂代码的方法，观察头文件并阅读单元测试，而不是一头扎进`.c`实现中。这种“具体的抽象”让你理解代码如何一起工作，并且更容易记住。
## 优点和缺点
`DArray`在你需要这些操作时占优势。
+ 迭代。你可以仅仅使用基本的`for`循环，使用`DArray_count`和`DArray_get`来完成任务。不需要任何特殊的宏。并且由于不处理指针，它非常快。
+ 索引。你可以使用`DArray_get`和`DArray_set`来随机访问任何元素，但是`List`上你就必须经过第N个元素来访问第N+1个元素。
+ 销毁。你只需要以两个操作销毁结构体和`content`。但是`List`需要一些列的`free`调用同时遍历每个元素。
+ 克隆。你只需要复制结构体和`content`，用两步复制整个结构。`List`需要遍历所有元素并且复制每个`ListNode`和值。
+ 排序。你已经见过了，如果你需要对数据排序，`List`非常麻烦。`DArray`上可以实现所有高效的排序算法，因为你可以随机访问任何元素。
+ 大量数据。如果你需要储存大量数据，`DArray`由于基于`content`，比起相同数量的`ListNode`占用更少空间而占优。
然而`List`在这些操作上占优势。
+ 在开头插入和移除元素。`DArray`需要特殊的优化来高效地完成它，并且通常还需要一些复制操作。
+ 分割和连接。`List`只需要复制一些指针就能完成，但是`DArray`需要复制涉及到的所有数组。
+ 少量数据。如果你只需要存储几个元素，通常使用`List`所需的空间要少于`DArray`，因为`DArray`需要考虑到日后的添加而扩展背后的空间，但是`List`只需要元素所需的空间。
考虑到这些，我更倾向使用`DArray`来完成其它人使用`List`所做的大部分事情。对于任何需要少量节点并且在两端插入删除的，我会使用`List`。我会想你展示两个相似的数据结构，叫做`Stack`和`Queue`，它们也很重要。
## 如何改进
像往常一样，浏览每个函数和操作，并且执行防御性编程检查，以及添加先决条件、不变量等任何可以使实现更健壮的东西。
## 附加题
+ 改进单元测试来覆盖耕作操作，并使用`for`循环来测试迭代。
+ 研究`DArray`上如何实现冒泡排序和归并排序，但是不要马上实现它们。我会在下一张实现`DArray`的算法，之后你可以完成它。
+ 为一些常用的操作编写一些性能测试，并与`List`中的相同操作比较。你已经做过很多次了，但是这次需要编写重复执行所涉及操作的单元测试，之后在主运行器中计时。
+ 观察`DArray_expand`如何使用固定增长（`size + 300`）来实现。通常动态数组都以倍数增长（`size * 2`）的方式实现，但是我发现它会花费无用的内存并且没有真正取得性能收益。测试我的断言，并且看看什么情况下需要倍数增长而不是固定增长。
';
练习33：链表算法
最后更新于：2022-04-01 23:29:12
# 练习33：链表算法
> 原文：[Exercise 33: Linked List Algorithms](http://c.learncodethehardway.org/book/ex33.html)
> 译者：[飞龙](https://github.com/wizardforcel)
我将想你介绍涉及到排序的两个算法，你可以用它们操作链表。我首先要警告你，如果你打算对数据排序，不要使用链表，它们对于排序十分麻烦，并且有更好的数据结构作为替代。我向你介绍这两种算法只是因为它们难以在链表上完成，并且让你思考如何高效操作它们。
为了编写这本书，我打算将算法放在两个不同的文件中，`list_algos.h`和`list_algos.c`，之后在`list_algos_test.c`中编写测试。现在你要按照我的结构，因为它足以把事情做好，但是如果你使用其它的库要记住这并不是通用的结构。
这个练习中我打算给你一些额外的挑战，并且希望你不要作弊。我打算先给你单元测试，并且让你打下来。之后让你基于它们在维基百科中的描述，尝试实现这个两个算法，之后看看你的代码是否和我的类似。
## 冒泡排序和归并排序
互联网的强大之处，就是我可以仅仅给你[冒泡排序](http://en.wikipedia.org/wiki/Bubble_sort)和[归并排序](http://en.wikipedia.org/wiki/Merge_sort)的链接，来让你学习它们。是的，这省了我很多字。现在我要告诉你如何使用它们的伪代码来实现它们。你可以像这样来实现算法：
+ 阅读描述，并且观察任何可视化的图表。
+ 使用方框和线条在纸上画出算法，或者使用一些带有数字的卡片（比如扑克牌），尝试手动执行算法。这会向你形象地展示算法的执行过程。
+ 在`list_algos.c`文案总创建函数的主干，并且创建`list_algos.h`文件，之后创建测试代码。
+ 编写第一个测试并且编译所有东西。
+ 回到维基百科页面，复制粘贴伪代码到你创建的函数中（不是C代码）。
+ 将伪代码翻译成良好的C代码，就像我教你的那样，使用你的单元测试来保证它有效。
+ 为边界情况补充一些测试，例如空链表，排序号的链表，以及其它。
+ 对下一个算法重复这些过程并测试。
我只是告诉你理解大多数算法的秘密，直到你碰到一些更加麻烦的算法。这里你只是按照维基百科来实现冒泡排序和归并排序，它们是一个好的起始。
## 单元测试
下面是你应该通过的单元测试：
```c
#include "minunit.h"
#include
#include
#include
char *values[] = {"XXXX", "1234", "abcd", "xjvef", "NDSS"};
#define NUM_VALUES 5
List *create_words()
{
int i = 0;
List *words = List_create();
for(i = 0; i < NUM_VALUES; i++) {
List_push(words, values[i]);
}
return words;
}
int is_sorted(List *words)
{
LIST_FOREACH(words, first, next, cur) {
if(cur->next && strcmp(cur->value, cur->next->value) > 0) {
debug("%s %s", (char *)cur->value, (char *)cur->next->value);
return 0;
}
}
return 1;
}
char *test_bubble_sort()
{
List *words = create_words();
// should work on a list that needs sorting
int rc = List_bubble_sort(words, (List_compare)strcmp);
mu_assert(rc == 0, "Bubble sort failed.");
mu_assert(is_sorted(words), "Words are not sorted after bubble sort.");
// should work on an already sorted list
rc = List_bubble_sort(words, (List_compare)strcmp);
mu_assert(rc == 0, "Bubble sort of already sorted failed.");
mu_assert(is_sorted(words), "Words should be sort if already bubble sorted.");
List_destroy(words);
// should work on an empty list
words = List_create(words);
rc = List_bubble_sort(words, (List_compare)strcmp);
mu_assert(rc == 0, "Bubble sort failed on empty list.");
mu_assert(is_sorted(words), "Words should be sorted if empty.");
List_destroy(words);
return NULL;
}
char *test_merge_sort()
{
List *words = create_words();
// should work on a list that needs sorting
List *res = List_merge_sort(words, (List_compare)strcmp);
mu_assert(is_sorted(res), "Words are not sorted after merge sort.");
List *res2 = List_merge_sort(res, (List_compare)strcmp);
mu_assert(is_sorted(res), "Should still be sorted after merge sort.");
List_destroy(res2);
List_destroy(res);
List_destroy(words);
return NULL;
}
char *all_tests()
{
mu_suite_start();
mu_run_test(test_bubble_sort);
mu_run_test(test_merge_sort);
return NULL;
}
RUN_TESTS(all_tests);
```
建议你从冒泡排序开始，使它正确，之后再测试归并。我所做的就是编写函数原型和主干，让这三个文件能够编译，但不能通过测试。之后你将实现填充进入之后才能够工作。
## 实现
你作弊了吗？之后的练习中，我只会给你单元测试，并且让自己实现它。对于你来说，不看这段代码知道你自己实现它是一种很好的练习。下面是`list_algos.c`和`list_algos.h`的代码：
```c
#ifndef lcthw_List_algos_h
#define lcthw_List_algos_h
#include
typedef int (*List_compare)(const void *a, const void *b);
int List_bubble_sort(List *list, List_compare cmp);
List *List_merge_sort(List *list, List_compare cmp);
#endif
```
```c
#include
#include
inline void ListNode_swap(ListNode *a, ListNode *b)
{
void *temp = a->value;
a->value = b->value;
b->value = temp;
}
int List_bubble_sort(List *list, List_compare cmp)
{
int sorted = 1;
if(List_count(list) <= 1) {
return 0; // already sorted
}
do {
sorted = 1;
LIST_FOREACH(list, first, next, cur) {
if(cur->next) {
if(cmp(cur->value, cur->next->value) > 0) {
ListNode_swap(cur, cur->next);
sorted = 0;
}
}
}
} while(!sorted);
return 0;
}
inline List *List_merge(List *left, List *right, List_compare cmp)
{
List *result = List_create();
void *val = NULL;
while(List_count(left) > 0 || List_count(right) > 0) {
if(List_count(left) > 0 && List_count(right) > 0) {
if(cmp(List_first(left), List_first(right)) <= 0) {
val = List_shift(left);
} else {
val = List_shift(right);
}
List_push(result, val);
} else if(List_count(left) > 0) {
val = List_shift(left);
List_push(result, val);
} else if(List_count(right) > 0) {
val = List_shift(right);
List_push(result, val);
}
}
return result;
}
List *List_merge_sort(List *list, List_compare cmp)
{
if(List_count(list) <= 1) {
return list;
}
List *left = List_create();
List *right = List_create();
int middle = List_count(list) / 2;
LIST_FOREACH(list, first, next, cur) {
if(middle > 0) {
List_push(left, cur->value);
} else {
List_push(right, cur->value);
}
middle--;
}
List *sort_left = List_merge_sort(left, cmp);
List *sort_right = List_merge_sort(right, cmp);
if(sort_left != left) List_destroy(left);
if(sort_right != right) List_destroy(right);
return List_merge(sort_left, sort_right, cmp);
}
```
冒泡排序并不难以理解，虽然它非常慢。归并排序更为复杂，实话讲如果我想要牺牲可读性的话，我会花一点时间来优化代码。
归并排序有另一种“自底向上”的实现方式，但是它太难了，我就没有选择它。就像我刚才说的那样，在链表上编写排序算法没有什么意思。你可以把时间都花在使它更快，它比起其他可排序的数据结构会相当版。链表的本质决定了如果你需要对数据进行排序，你就不要使用它们（尤其是单向的）。
## 你会看到什么
如果一切都正常工作，你会看到这些：
```sh
$ make clean all
rm -rf build src/lcthw/list.o src/lcthw/list_algos.o tests/list_algos_tests tests/list_tests
rm -f tests/tests.log
find . -name "*.gc*" -exec rm {} \;
rm -rf `find . -name "*.dSYM" -print`
cc -g -O2 -Wall -Wextra -Isrc -rdynamic -DNDEBUG -fPIC -c -o src/lcthw/list.o src/lcthw/list.c
cc -g -O2 -Wall -Wextra -Isrc -rdynamic -DNDEBUG -fPIC -c -o src/lcthw/list_algos.o src/lcthw/list_algos.c
ar rcs build/liblcthw.a src/lcthw/list.o src/lcthw/list_algos.o
ranlib build/liblcthw.a
cc -shared -o build/liblcthw.so src/lcthw/list.o src/lcthw/list_algos.o
cc -g -O2 -Wall -Wextra -Isrc -rdynamic -DNDEBUG build/liblcthw.a tests/list_algos_tests.c -o tests/list_algos_tests
cc -g -O2 -Wall -Wextra -Isrc -rdynamic -DNDEBUG build/liblcthw.a tests/list_tests.c -o tests/list_tests
sh ./tests/runtests.sh
Running unit tests:
----
RUNNING: ./tests/list_algos_tests
ALL TESTS PASSED
Tests run: 2
tests/list_algos_tests PASS
----
RUNNING: ./tests/list_tests
ALL TESTS PASSED
Tests run: 6
tests/list_tests PASS
$
```
这个练习之后我就不会向你展示这样的输出了，除非有必要向你展示它的工作原理。你应该能知道我运行了测试，并且通过了所有测试。
## 如何改进
退回去查看算法描述，有一些方法可用于改进这些实现，其中一些是很显然的：
+ 归并排序做了大量的链表复制和创建操作，寻找减少它们的办法。
+ 归并排序的维基百科描述提到了一些优化，实现它们。
+ 你能使用`List_split`和`List_join`（如果你实现了的话）来改进归并排序嘛？
+ 浏览所有防御性编程原则，检查并提升这一实现的健壮性，避免`NULL`指针，并且创建一个可选的调试级别的不变量，在排序后实现`is_sorted`的功能。
## 附加题
+ 创建单元测试来比较这两个算法的性能。你需要`man 3 time`来查询基本的时间函数，并且需要运行足够的迭代次数，至少以几秒钟作为样本。
+ 改变需要排序的链表中的数据总量，看看耗时如何变化。
+ 寻找方法来创建不同长度的随机链表，并且测量需要多少时间，之后将它可视化并与算法的描述对比。
+ 尝试解释为什么对链表排序十分麻烦。
+ 实现`List_insert_sorted`（有序链表），它使用`List_compare`，接收一个值，将其插入到正确的位置，使链表有序。它与创建链表后再进行排序相比怎么样？
+ 尝试实现维基百科上“自底向上”的归并排序。上面的代码已经是C写的了，所以很容易重新创建，但是要试着理解它的工作原理，并与这里的低效版本对比。
';
练习32：双向链表
最后更新于：2022-04-01 23:29:10
# 练习32：双向链表
> 原文：[Exercise 32: Double Linked Lists](http://c.learncodethehardway.org/book/ex32.html)
> 译者：[飞龙](https://github.com/wizardforcel)
这本书的目的是教给你计算机实际上如何工作，这也包括多种数据结构和算法函数。计算机自己其实并没有太大用处。为了让它们做一些有用的事情，你需要构建数据，之后在这些结构上组织处理。其它编程语言带有实现所有这些结构的库，或者带有直接的语法来创建它们。C需要你手动实现所有数据结构，这使它成为最“完美”的语言，让你知道它们的工作原理。
我的目标是交给你这些数据结构，以及相关算法的知识，来帮助你完成下面这三件事：
+ 理解Python、Ruby或JavaScript的`data = {"name": "Zed"}`到底做了什么。
+ 使用数据结构来解决问题，使你成为更好的C程序员。
+ 学习数据结构和算法的核心部分，让你知道在特定条件下哪个最好。
## 数据结构是什么。
“数据结构”这个名称自己就能够解释。它是具有特性模型的数据组织方法。这一模型可能设计用于以新的方法处理数据，也可能只是用于将它们更高效地储存在磁盘上。这本书中我会遵循一些简单的模式来构建可用的数据结构：
+ 定义一个结构的主要“外部结构”。
+ 定义一个结构的内容，通常是带有链接的节点。
+ 创建函数操作它们的函数。
C中还有其它样式的数据结构，但是这个模式效果很好，并且对于你创建的大部分数据结构都适用。
## 构建库
对于这本书的剩余部分，当你完成这本书之后，你将会创建一个可用的库。这个库会包含下列元素：
+ 为每个数据结构编写的头文件`.h`。
+ 为算法编写的实现文件`.c`。
+ 用于测试它们确保有效的单元测试。
+ 从头文件自动生成的文档。
你已经实现了`c-skeleton`（项目框架目录），使用它来创建一个`liblcthw`项目：
```sh
$ cp -r c-skeleton liblcthw
$ cd liblcthw/
$ ls
LICENSE Makefile README.md bin build src tests
$ vim Makefile
$ ls src/
dbg.h libex29.c libex29.o
$ mkdir src/lcthw
$ mv src/dbg.h src/lcthw
$ vim tests/minunit.h
$ rm src/libex29.* tests/libex29*
$ make clean
rm -rf build tests/libex29_tests
rm -f tests/tests.log
find . -name "*.gc*" -exec rm {} \;
rm -rf `find . -name "*.dSYM" -print`
$ ls tests/
minunit.h runtests.sh
$
```
这个会话中我执行了下列事情：
+ 复制了`c-skeleton`。
+ 编辑Makefile，将`libYOUR_LIBRARY.a`改为`liblcthw.a`作为新的`TARGET`。
+ 创建`src/lcthw`目录，我们会在里面放入代码。
+ 移动`src/dbg.h`文件到新的目录中。
+ 编辑` tests/minunit.h`，使它使用所包含的`#include `。
+ 移除`libex29.*`中我们不需要的源文件和测试文件。
+ 清理所有遗留的东西。
执行完之后你就准备好开始构建库了，我打算构建第一个数据结构是双向链表。
## 双向链表
我们将要向`liblcthw`添加的第一个数据结构是双向链表。这是你能够构建的最简单的数据结构，并且它拥有针对特定操作的实用属性。单向链表通过指向下一个或上一个元素的节点来工作。“双向”链表持有全部这两个指针，而“单向”链表只持有下一个元素的指针。
由于每个节点都有下一个和上一个元素的指针，并且你可以跟踪联保的第一个和最后的元素，你就可以快速地执行一些操作。任何涉及到插入和删除元素的操作会非常快。它对大多数人来说也易于实现。
链表的主要缺点是，遍历它涉及到处理沿途每个单个的指针。这意味着搜索、多数排序以及迭代元素会表较慢。这也意味着你不能直接跳过链表的随机一部分。如果换成数组，你就可以直接索引到它的中央，但是链表不行。也就是说如果你想要访问第十个元素，你必须经过1~9。
### 定义
正如在这个练习的介绍部分所说，整个过程的第一步，是编程一个头文件，带有正确的C结构定义。
```c
#ifndef lcthw_List_h
#define lcthw_List_h
#include
struct ListNode;
typedef struct ListNode {
struct ListNode *next;
struct ListNode *prev;
void *value;
} ListNode;
typedef struct List {
int count;
ListNode *first;
ListNode *last;
} List;
List *List_create();
void List_destroy(List *list);
void List_clear(List *list);
void List_clear_destroy(List *list);
#define List_count(A) ((A)->count)
#define List_first(A) ((A)->first != NULL ? (A)->first->value : NULL)
#define List_last(A) ((A)->last != NULL ? (A)->last->value : NULL)
void List_push(List *list, void *value);
void *List_pop(List *list);
void List_unshift(List *list, void *value);
void *List_shift(List *list);
void *List_remove(List *list, ListNode *node);
#define LIST_FOREACH(L, S, M, V) ListNode *_node = NULL;\
ListNode *V = NULL;\
for(V = _node = L->S; _node != NULL; V = _node = _node->M)
#endif
```
我所做的第一件事就是创建两个结构，`ListNode`和包含这些节点的`List`。这创建了是将在函数中使用的数据结构，以及随后定义的宏。如果你浏览这些函数，它们看起来非常简单。当我讲到实现时，我会解释他们，但我更希望你能猜出它们的作用。
这些数据结构的工作方式，就是每个`ListNode`都有三个成员。
+ 值，它是无类型的指针，存储我们想在链表中放置的东西。
+ `ListNode *next`指针，它指向另一个储存下一个元素的`ListNode `。
+ `ListNode *prev`指针，它指向另一个储存上一个元素的`ListNode `。
`List`结构只是这些`ListNode`结构的容器，它们互联链接组成链型。它跟踪链表的`count`，`first`和`last`元素。
最后，看一看`src/lcthw/list.h:37`，其中我定义了`LIST_FOREACH`宏。这是个常见的习语，你可以创建一个宏来生成迭代代码，使用者就不会弄乱了。正确使用这类执行过程来处理数据结构十分困难，所以可以编写宏来帮助使用者。当我讲到实现时，你可以看到我如何使用它。
### 实现
一旦你理解了它们之后，你很可能理解了双向链表如何工作。它只是带有两个指针的节点，指向链表中前一个和后一个元素。接下来你可以编写`src/lcthw/list.c`中的代码，来理解每个操作如何实现。
```c
#include
#include
List *List_create()
{
return calloc(1, sizeof(List));
}
void List_destroy(List *list)
{
LIST_FOREACH(list, first, next, cur) {
if(cur->prev) {
free(cur->prev);
}
}
free(list->last);
free(list);
}
void List_clear(List *list)
{
LIST_FOREACH(list, first, next, cur) {
free(cur->value);
}
}
void List_clear_destroy(List *list)
{
List_clear(list);
List_destroy(list);
}
void List_push(List *list, void *value)
{
ListNode *node = calloc(1, sizeof(ListNode));
check_mem(node);
node->value = value;
if(list->last == NULL) {
list->first = node;
list->last = node;
} else {
list->last->next = node;
node->prev = list->last;
list->last = node;
}
list->count++;
error:
return;
}
void *List_pop(List *list)
{
ListNode *node = list->last;
return node != NULL ? List_remove(list, node) : NULL;
}
void List_unshift(List *list, void *value)
{
ListNode *node = calloc(1, sizeof(ListNode));
check_mem(node);
node->value = value;
if(list->first == NULL) {
list->first = node;
list->last = node;
} else {
node->next = list->first;
list->first->prev = node;
list->first = node;
}
list->count++;
error:
return;
}
void *List_shift(List *list)
{
ListNode *node = list->first;
return node != NULL ? List_remove(list, node) : NULL;
}
void *List_remove(List *list, ListNode *node)
{
void *result = NULL;
check(list->first && list->last, "List is empty.");
check(node, "node can't be NULL");
if(node == list->first && node == list->last) {
list->first = NULL;
list->last = NULL;
} else if(node == list->first) {
list->first = node->next;
check(list->first != NULL, "Invalid list, somehow got a first that is NULL.");
list->first->prev = NULL;
} else if (node == list->last) {
list->last = node->prev;
check(list->last != NULL, "Invalid list, somehow got a next that is NULL.");
list->last->next = NULL;
} else {
ListNode *after = node->next;
ListNode *before = node->prev;
after->prev = before;
before->next = after;
}
list->count--;
result = node->value;
free(node);
error:
return result;
}
```
我实现了双向链表上的所有操作，它们不能用简单的宏来完成。比起覆盖文件中的每一行，我打算为`list.h`和`list.c`中的每个操作提供一个高阶的概览。你需要自己阅读代码。
list.h:List_count
返回链表中元素数量，它在元素添加或移除时维护。
list.h:List_first
返回链表的首个元素，但是并不移除它。
list.h:List_last
返回链表的最后一个元素，但是不移除它。
list.h:LIST_FOREACH
遍历链表中的元素。
list.c:List_create
简单地创建主要的`List`结构。
list.c:List_destroy
销毁`List`以及其中含有的所有元素。
list.c:List_clear
为释放每个节点中的值（而不是节点本身）创建的辅助函数。
list.c:List_clear_destroy
清理并销毁链表。它并不十分搞笑因为它对每个元素遍历两次。
list.c:List_push
第一个操作演示了链表的有点。它向链表尾添加新的元素，由于只是一些指针赋值，所以非常快。
list.c:List_pop
`List_push`的反向版本，它去除最后一个元素并返回它。
list.c:List_unshift
亦可以轻易对链表执行的另一件事，就是快速地向链表头部添加元素。由于找不到合适的词，这里我把它称为`unshift`。
list.c:List_shift
类似`List_pop`，但是它移除链表的首个元素并返回。
list.c:List_remove
当你执行`List_pop`或`List_shift`时，它执行实际的移除操作。在数据结构中移除数据总是看似比较困难，这个函数也不例外。它需要处理一些条件，取决于被移除的位置，在开头、在结尾、开头并且结尾，或者在中间。
这些函数大多数都没什么特别的，你应该能够轻易描述出来，并且根据代码来理解它。你应该完全专注于`List_destroy`中的`LIST_FOREACH`如何使用来理解它如何简化通常的操作。
## 测试
在你编译它们之前，需要创建测试来确保它们正确执行。
```c
#include "minunit.h"
#include
#include
static List *list = NULL;
char *test1 = "test1 data";
char *test2 = "test2 data";
char *test3 = "test3 data";
char *test_create()
{
list = List_create();
mu_assert(list != NULL, "Failed to create list.");
return NULL;
}
char *test_destroy()
{
List_clear_destroy(list);
return NULL;
}
char *test_push_pop()
{
List_push(list, test1);
mu_assert(List_last(list) == test1, "Wrong last value.");
List_push(list, test2);
mu_assert(List_last(list) == test2, "Wrong last value");
List_push(list, test3);
mu_assert(List_last(list) == test3, "Wrong last value.");
mu_assert(List_count(list) == 3, "Wrong count on push.");
char *val = List_pop(list);
mu_assert(val == test3, "Wrong value on pop.");
val = List_pop(list);
mu_assert(val == test2, "Wrong value on pop.");
val = List_pop(list);
mu_assert(val == test1, "Wrong value on pop.");
mu_assert(List_count(list) == 0, "Wrong count after pop.");
return NULL;
}
char *test_unshift()
{
List_unshift(list, test1);
mu_assert(List_first(list) == test1, "Wrong first value.");
List_unshift(list, test2);
mu_assert(List_first(list) == test2, "Wrong first value");
List_unshift(list, test3);
mu_assert(List_first(list) == test3, "Wrong last value.");
mu_assert(List_count(list) == 3, "Wrong count on unshift.");
return NULL;
}
char *test_remove()
{
// we only need to test the middle remove case since push/shift
// already tests the other cases
char *val = List_remove(list, list->first->next);
mu_assert(val == test2, "Wrong removed element.");
mu_assert(List_count(list) == 2, "Wrong count after remove.");
mu_assert(List_first(list) == test3, "Wrong first after remove.");
mu_assert(List_last(list) == test1, "Wrong last after remove.");
return NULL;
}
char *test_shift()
{
mu_assert(List_count(list) != 0, "Wrong count before shift.");
char *val = List_shift(list);
mu_assert(val == test3, "Wrong value on shift.");
val = List_shift(list);
mu_assert(val == test1, "Wrong value on shift.");
mu_assert(List_count(list) == 0, "Wrong count after shift.");
return NULL;
}
char *all_tests() {
mu_suite_start();
mu_run_test(test_create);
mu_run_test(test_push_pop);
mu_run_test(test_unshift);
mu_run_test(test_remove);
mu_run_test(test_shift);
mu_run_test(test_destroy);
return NULL;
}
RUN_TESTS(all_tests);
```
它简单地遍历了每个操作，并且确保它们有效。我在测试中做了简化，对于整个程序我只创建了一个`List *list`，这解决了为每个测试构建一个`List`的麻烦，但它同时意味着一些测试会受到之前测试的影响。这里我试着是每个测试不改变链表，或实际使用上一个测试的结果。
## 你会看到什么
如果你正确完成了每件事，当你执行构建并且运行单元测试是，你会看到：
```sh
$ make
cc -g -O2 -Wall -Wextra -Isrc -rdynamic -DNDEBUG -fPIC -c -o src/lcthw/list.o src/lcthw/list.c
ar rcs build/liblcthw.a src/lcthw/list.o
ranlib build/liblcthw.a
cc -shared -o build/liblcthw.so src/lcthw/list.o
cc -g -O2 -Wall -Wextra -Isrc -rdynamic -DNDEBUG build/liblcthw.a tests/list_tests.c -o tests/list_tests
sh ./tests/runtests.sh
Running unit tests:
----
RUNNING: ./tests/list_tests
ALL TESTS PASSED
Tests run: 6
tests/list_tests PASS
$
```
确保6个测试运行完毕，以及构建时没有警告或错误，并且成功构建了`build/liblcthw.a`和`build/liblcthw.so`文件。
## 如何改进
我打算告诉你如何改进代码，而不是使它崩溃。
+ 你可以使用`LIST_FOREACH`并在循环中调用`free`来使`List_clear_destroy`更高效。
+ 你可以为一些先决条件添加断言，使其部结构`NULL`值作为`List *list`的参数。
+ 你可以添加不变了，来检查列表的内容始终正确，例如`count`永远不会`< 0`，如果`count > 0`，`first`不为`NULL`。
+ 你可以向头文件添加文档，在每个结构、函数和宏之前添加描述其作用的注释。
这些改进执行了防御性编程实践，并且“加固”了代码来避免错误或使用不当。马上去做这些事情，之后找到尽可能多的办法来改进代码。
## 附加题
+ 研究双向和单向链表，以及什么情况下其中一种优于另一种。
+ 研究双向链表的限制。例如，虽然它们对于插入和删除元素很高效，但是对于变量元素比较慢。
+ 还缺少什么你能想到的操作？比如复制、连接、分割等等。实现这些操作，并且为它们编写单元测试。
';
练习31：代码调试
最后更新于：2022-04-01 23:29:08
# 练习31：代码调试
> 原文：[Exercise 31: Debugging Code](http://c.learncodethehardway.org/book/ex31.html)
> 译者：[飞龙](https://github.com/wizardforcel)
我已经教给你一些关于我的强大的调试宏的技巧，并且你已经开始用它们了。当我调试代码时，我使用`debug()`宏，分析发生了什么以及跟踪问题。在这个练习中我打算教给你一些使用gdb的技巧，用于监视一个不会退出的简单程序。你会学到如何使用gdb附加到运行中的进程，并挂起它来观察发生了什么。在此之后我会给你一些用于gdb的小提示和小技巧。
## 调试输出、GDB或Valgrind
我主要按照一种“科学方法”的方式来调试，我会提出可能的所有原因，之后排除它们或证明它们导致了缺陷。许多程序员拥有的问题是它们对解决bug的恐慌和急躁使他们觉得这种方法会“拖慢”他们。它们并没有注意到，它们已经失败了，并且在收集无用的信息。我发现日志（调试输出）会强迫我科学地解决bug，并且在更多情况下易于收集信息。
此外，使用调试输出来作为我的首要调试工具的理由如下：
+ 你可以使用变量的调试输出，来看到程序执行的整个轨迹，它让你跟踪变量是如何产生错误的。使用gdb的话，你必须为每个变量放置查看和调试语句，并且难以获得执行的实际轨迹。
+ 调试输出存在于代码中，当你需要它们是你可以重新编译使它们回来。使用gdb的话，你每次调试都需要重新配置相同的信息。
+ 当服务器工作不正常时，它的调试日志功能易于打开，并且在它运行中可以监视日志来查看哪里不对。系统管理员知道如何处理日志，他们不知道如何使用gdb。
+ 打印信息更加容易。调试器通常由于它奇特的UI和前后矛盾显得难用且古怪。`debug("Yo, dis right? %d", my_stuff);`就没有那么麻烦。
+ 编写调试输出来发现缺陷，强迫你实际分析代码，并且使用科学方法。你可以认为它是，“我假设这里的代码是错误的”，你可以运行它来验证你的假设，如果这里没有错误那么你可以移动到其它地方。这看起来需要更长时间，但是实际上更快，因为你经历了“鉴别诊断”的过程，并排除所有可能的原因，直到你找到它。
+ 调试输入更适于和单元测试一起运行。你可以实际上总是编译调试语句，单元测试时可以随时查看日志。如果你用gdb，你需要在gdb中重复运行单元测试，并跟踪他来查看发生了什么。
+ 使用Valgrind可以得到和调试输出等价的内存相关的错误，所以你并不需要使用类似gdb的东西来寻找缺陷。
尽管所有原因显示我更倾向于`debug`而不是`gdb`，我还是在少数情况下回用到`gdb`，并且我认为你应该选择有助于你完成工作的工具。有时，你只能够连接到一个崩溃的程序并且四处转悠。或者，你得到了一个会崩溃的服务器，你只能够获得一些核心文件来一探究竟。这些货少数其它情况中，gdb是很好的办法。你最好准备尽可能多的工具来解决问题。
接下来我会通过对比gdb、调试输出和Valgrind来详细分析，像这样：
+ Valgrind用于捕获所有内存错误。如果Valgrind中含有错误或Valgrind会严重拖慢程序，我会使用gdb。
+ 调试输出用于诊断或修复有关逻辑或使用上的缺陷。在你使用Valgrind之前，这些共计90%的缺陷。
+ 使用gdb解决剩下的“谜之bug”，或如要收集信息的紧急情况。如果Valgrind不起作用，并且我不能打印出所需信息，我就会使用gdb开始四处搜索。这里我仅仅使用gdb来收集信息。一旦我弄清发生了什么，我会回来编程单元测试来引发缺陷，之后编程打印语句来查找原因。
## 调试策略
这一过程适用于你打算使用任何调试技巧，无论是Valgrind、调试输出，或者使用调试器。我打算以使用`gdb`的形式来描述他，因为似乎人们在使用调试器是会跳过它。但是应当对每个bug使用它，直到你只需要在非常困难的bug上用到。
+ 创建一个小型文本文件叫做`notes.txt`，并且将它用作记录想法、bug和问题的“实验记录”。
+ 在你使用`gdb`之前，写下你打算修复的bug，以及可能的产生原因。
+ 对于每个原因，写下你所认为的，问题来源的函数或文件，或者仅仅写下你不知道。
+ 现在启动`gdb`并且使用`file:function`挑选最可能的因素，之后在那里设置断点。
+ 使用`gdb`运行程序，并且确认它是否是真正原因。查明它的最好方式就是看看你是否可以使用`set`命令，简单修复问题或者重现错误。
+ 如果它不是真正原因，则在`notes.txt`中标记它不是，以及理由。移到下一个可能的原因，并且使最易于调试的，之后记录你收集到的信息。
这里你并没有注意到，它是最基本的科学方法。你写下一些假设，之后调试来证明或证伪它们。这让你洞察到更多可能的因素，最终使你找到他。这个过程有助于你避免重复步入同一个可能的因素，即使你发现它们并不可能。
你也可以使用调试输出来执行这个过程。唯一的不同就是你实际在源码中编写假设来推测问题所在，而不是`notes.txt`中。某种程度上，调试输出强制你科学地解决bug，因为你需要将假写为打印语句。
## 使用 GDB
我将在这个练习中调试下面这个程序，它只有一个不会正常终止的`while`循环。我在里面放置了一个`usleep`调用，使它循环起来更加有趣。
```c
#include
int main(int argc, char *argv[])
{
int i = 0;
while(i < 100) {
usleep(3000);
}
return 0;
}
```
像往常一样编译，并且在`gdb`下启动它，例如：`gdb ./ex31`。
一旦它运行之后，我打算让你使用这些`gdb`命令和它交互，并且观察它们的作用以及如何使用它们。
help COMMAND
获得`COMMAND`的简单帮助。
break file.c:(line|function)
在你希望暂停之星的地方设置断点。你可以提供行号或者函数名称，来在文件中的那个地方暂停。
run ARGS
运行程序，使用`ARGS`作为命令行参数。
cont
继续执行程序，直到断点或错误。
step
单步执行代码，但是会进入函数内部。使用它来跟踪函数内部，来观察它做了什么。
next
就像是`step`，但是他会运行函数并步过它们。
backtrace (or bt)
执行“跟踪回溯”，它会转储函数到当前执行点的执行轨迹。对于查明如何执行到这里非常有用，因为它也打印出传给每个函数的参数。它和Valgrind报告内存错误的方式很接近。
set var X = Y
将变量`X`设置为`Y`。
print X
打印出`X`的值，你通常可以使用C的语法来访问指针的值或者结构体的内容。
ENTER
重复上一条命令。
quit
退出`gdb`。
这些都是我使用`gdb`时的主要命令。你现在的任务是玩转它们和`ex31`，你会对它的输出更加熟悉。
一旦你熟悉了`gdb`之后，你会希望多加使用它。尝试在更复杂的程序，例如`devpkg`上使用它，来观察你是否能够改函数的执行或分析出程序在做什么。
## 附加到进程
`gdb`最实用的功能就是附加到运行中的程序，并且就地调试它的能力。当你拥有一个崩溃的服务器或GUI程序，你通常不需要像之前那样在`gdb`下运行它。而是可以直接启动它，希望它不要马上崩溃，之后附加到它并设置断点。练习的这一部分中我会向你展示怎么做。
当你退出`gdb`之后，如果你停止了`ex31`我希望你重启它，之后开启另一个中断窗口以便于启动`gdb`并附加。进程附加就是你让`gdb`连接到已经运行的程序，以便于你实时监测它。它会挂起程序来让你单步执行，当你执行完之后程序会像往常一样恢复运行。
下面是一段会话，我对`ex31`做了上述事情，单步执行它，之后修改`while`循环并使它退出。
```sh
$ ps ax | grep ex31
10026 s000 S+ 0:00.11 ./ex31
10036 s001 R+ 0:00.00 grep ex31
$ gdb ./ex31 10026
GNU gdb 6.3.50-20050815 (Apple version gdb-1705) (Fri Jul 1 10:50:06 UTC 2011)
Copyright 2004 Free Software Foundation, Inc.
GDB is free software, covered by the GNU General Public License, and you are
welcome to change it and/or distribute copies of it under certain conditions.
Type "show copying" to see the conditions.
There is absolutely no warranty for GDB. Type "show warranty" for details.
This GDB was configured as "x86_64-apple-darwin"...Reading symbols for shared libraries .. done
/Users/zedshaw/projects/books/learn-c-the-hard-way/code/10026: No such file or directory
Attaching to program: `/Users/zedshaw/projects/books/learn-c-the-hard-way/code/ex31', process 10026.
Reading symbols for shared libraries + done
Reading symbols for shared libraries ++........................ done
Reading symbols for shared libraries + done
0x00007fff862c9e42 in __semwait_signal ()
(gdb) break 8
Breakpoint 1 at 0x107babf14: file ex31.c, line 8.
(gdb) break ex31.c:11
Breakpoint 2 at 0x107babf1c: file ex31.c, line 12.
(gdb) cont
Continuing.
Breakpoint 1, main (argc=1, argv=0x7fff677aabd8) at ex31.c:8
8 while(i < 100) {
(gdb) p i
$1 = 0
(gdb) cont
Continuing.
Breakpoint 1, main (argc=1, argv=0x7fff677aabd8) at ex31.c:8
8 while(i < 100) {
(gdb) p i
$2 = 0
(gdb) list
3
4 int main(int argc, char *argv[])
5 {
6 int i = 0;
7
8 while(i < 100) {
9 usleep(3000);
10 }
11
12 return 0;
(gdb) set var i = 200
(gdb) p i
$3 = 200
(gdb) next
Breakpoint 2, main (argc=1, argv=0x7fff677aabd8) at ex31.c:12
12 return 0;
(gdb) cont
Continuing.
Program exited normally.
(gdb) quit
$
```
> 注
> 在OSX上你可能会看到输入root密码的GUI输入框，并且即使你输入了密码还是会得到来自`gdb`的“Unable to access task for process-id XXX: (os/kern) failure.”的错误。这种情况下，你需要停止`gdb`和`ex31`程序，并重新启动程序使它工作，只要你成功输入了root密码。
我会遍历整个会话，并且解释我做了什么：
gdb:1
使用`ps`来寻找我想要附加的`ex31`的进程ID。
gdb:5
我使用`gdb ./ex31 PID`来附加到进程，其中`PID`替换为我所拥有的进程ID。
gdb:6-19
`gdb`打印出了一堆关于协议的信息，接着它读取了所有东西。
gdb:21
程序被附加，并且在当前执行点上停止。所以现在我在文件中的第8行使用`break`设置了断点。我假设我这么做的时候，已经在这个我想中断的文件中了。
gdb:24
执行`break`的更好方式，是提供`file.c line`的格式，便于你确保定位到了正确的地方。我在这个`break`中这样做。
gdb:27
我使用`cont`来继续运行，直到我命中了断点。
gdb:30-31
我已到达断点，于是`gdb`打印出我需要了解的变量（`argc`和`argv`），以及停下来的位置，之后打印出断点的行号。
gdb:33-34
我使用`print`的缩写`p`来打印出`i`变量的值，它是0。
gdb:36
继续运行来查看`i`是否改变。
gdb:42
再次打印出`i`，显然它没有变化。
gdb:45-55
使用`list`来查看代码是什么，之后我意识到它不可能退出，因为我没有自增`i`。
gdb:57
确认我的假设是正确的，即`i`需要使用`set`命令来修改为`i = 200`。这是`gdb`最优秀的特性之一，让你“修改”程序来让你快速知道你是否正确。
gdb:59
打印`i`来确保它已改变。
gdb:62
使用`next`来移到下一段代码，并且我发现命中了`ex31.c:12`的断点，所以这意味着`while`循环已退出。我的假设正确，我需要修改`i`。
gdb:67
使用`cont`来继续运行，程序像往常一样退出。
gdb:71
最后我使用`quit`来退出`gdb`。
## GDB 技巧
下面是你可以用于GDB的一些小技巧：
gdb --args
通常`gdb`获得你提供的变量并假设它们用于它自己。使用`--args`来向程序传递它们。
thread apply all bt
转储所有线程的执行轨迹，非常有用。
gdb --batch --ex r --ex bt --ex q --args
运行程序，当它崩溃时你会得到执行轨迹。
?
如果你有其它技巧，在评论中写下它吧。
## 附加题
+ 找到一个图形化的调试器，将它与原始的`gdb`相比。它们在本地调试程序时非常有用，但是对于在服务器上调试没有任何意义。
+ 你可以开启OS上的“核心转储”，当程序崩溃时你会得到一个核心文件。这个核心文件就像是对程序的解剖，便于你了解崩溃时发生了什么，以及由什么原因导致。修改`ex31.c`使它在几个迭代之后崩溃，之后尝试得到它的核心转储并分析。
';
练习30：自动化测试
最后更新于：2022-04-01 23:29:06
# 练习30：自动化测试
> 原文：[Exercise 30: Automated Testing](http://c.learncodethehardway.org/book/ex30.html)
> 译者：[飞龙](https://github.com/wizardforcel)
自动化测试经常用于例如Python和Ruby的其它语言，但是很少用于C。一部分原因是自动化加载和测试C的代码片段具有较高的难度。这一章中，我们会创建一个非常小型的测试“框架”，并且使用你的框架目录构建测试用例的示例。
我接下来打算使用，并且你会包含进框架目录的框架，叫做“minunit”，它以[Jera Design](http://www.jera.com/techinfo/jtns/jtn002.html)所编写的一小段代码作为开始，之后我扩展了它，就像这样：
```c
#undef NDEBUG
#ifndef _minunit_h
#define _minunit_h
#include
#include
#include
#define mu_suite_start() char *message = NULL
#define mu_assert(test, message) if (!(test)) { log_err(message); return message; }
#define mu_run_test(test) debug("\n-----%s", " " #test); \
message = test(); tests_run++; if (message) return message;
#define RUN_TESTS(name) int main(int argc, char *argv[]) {\
argc = 1; \
debug("----- RUNNING: %s", argv[0]);\
printf("----\nRUNNING: %s\n", argv[0]);\
char *result = name();\
if (result != 0) {\
printf("FAILED: %s\n", result);\
}\
else {\
printf("ALL TESTS PASSED\n");\
}\
printf("Tests run: %d\n", tests_run);\
exit(result != 0);\
}
int tests_run;
#endif
```
原始的内容所剩不多了，现在我使用`dbg.h`宏，并且在模板测试运行器的末尾创建了大量的宏。在这小段代码中我们创建了整套函数单元测试系统，一旦它结合上shell脚本来运行测试，你可以将其用于你的C代码。
## 完成测试框架
为了基础这个练习，你应该让你的`src/libex29.c`正常工作，并且完成练习29的附加题，是`ex29.c`加载程序并合理运行。练习29中我这事了一个附加题来使它像单元测试一样工作，但是现在我打算重新想你展示如何使用`minunit.h`来做这件事。
首先我们需要创建一个简单的空单元测试，命名为`tests/libex29_tests.c`，在里面输入：
```c
#include "minunit.h"
char *test_dlopen()
{
return NULL;
}
char *test_functions()
{
return NULL;
}
char *test_failures()
{
return NULL;
}
char *test_dlclose()
{
return NULL;
}
char *all_tests() {
mu_suite_start();
mu_run_test(test_dlopen);
mu_run_test(test_functions);
mu_run_test(test_failures);
mu_run_test(test_dlclose);
return NULL;
}
RUN_TESTS(all_tests);
```
这份代码展示了`tests/minunit.h`中的`RUN_TESTS`宏，以及如何使用其他的测试运行器宏。我没有编写实际的测试函数，所以你只能看到单元测试的结构。我首先会分解这个文件：
libex29_tests.c:1
包含`minunit.h`框架。
libex29_tests.c:3-7
第一个测试。测试函数具有固定的结构，它们不带任何参数并且返回`char *`，成功时为`NULL`。这非常重要，因为其他宏用于向测试运行器返回错误信息。
libex29_tests.c:9-25
与第一个测试相似的更多测试。
libex29_tests.c:27
控制其他测试的运行器函数。它和其它测试用例格式一致，但是使用额外的东西来配置。
libex29_tests.c:28
为`mu_suite_start`测试设置一些通用的东西。
libex29_tests.c:30
这就是使用`mu_run_test`返回结果的地方。
libex29_tests.c:35
在你运行所有测试之后，你应该返回`NULL`，就像普通的测试函数一样。
libex29_tests.c:38
最后需要使用`RUN_TESTS`宏来启动`main`函数，让它运行`all_tests`启动器。
这就是用于运行测试所有代码了，现在你需要尝试使它运行在项目框架中。下面是我的执行结果：
```shell
not printable
```
我首先执行`make clean`，之后我运行了构建，它将模板改造为`libYOUR_LIBRARY.a`和`libYOUR_LIBRARY.so`文件。要记住你需要在练习29的附加题中完成它。但如果你没有完成的话，下面是我所使用的`Makefile`的文件差异：
```diff
diff --git a/code/c-skeleton/Makefile b/code/c-skeleton/Makefile
index 135d538..21b92bf 100644
--- a/code/c-skeleton/Makefile
+++ b/code/c-skeleton/Makefile
@@ -9,9 +9,10 @@ TEST_SRC=$(wildcard tests/*_tests.c)
TESTS=$(patsubst %.c,%,$(TEST_SRC))
TARGET=build/libYOUR_LIBRARY.a
+SO_TARGET=$(patsubst %.a,%.so,$(TARGET))
# The Target Build
-all: $(TARGET) tests
+all: $(TARGET) $(SO_TARGET) tests
dev: CFLAGS=-g -Wall -Isrc -Wall -Wextra $(OPTFLAGS)
dev: all
@@ -21,6 +22,9 @@ $(TARGET): build $(OBJECTS)
ar rcs $@ $(OBJECTS)
ranlib $@
+$(SO_TARGET): $(TARGET) $(OBJECTS)
+ $(CC) -shared -o $@ $(OBJECTS)
+
build:
@mkdir -p build
@mkdir -p bin
```
完成这些改变后，你现在应该能够构建任何东西，并且你可以最后补完剩余的单元测试函数：
```c
#include "minunit.h"
#include
typedef int (*lib_function)(const char *data);
char *lib_file = "build/libYOUR_LIBRARY.so";
void *lib = NULL;
int check_function(const char *func_to_run, const char *data, int expected)
{
lib_function func = dlsym(lib, func_to_run);
check(func != NULL, "Did not find %s function in the library %s: %s", func_to_run, lib_file, dlerror());
int rc = func(data);
check(rc == expected, "Function %s return %d for data: %s", func_to_run, rc, data);
return 1;
error:
return 0;
}
char *test_dlopen()
{
lib = dlopen(lib_file, RTLD_NOW);
mu_assert(lib != NULL, "Failed to open the library to test.");
return NULL;
}
char *test_functions()
{
mu_assert(check_function("print_a_message", "Hello", 0), "print_a_message failed.");
mu_assert(check_function("uppercase", "Hello", 0), "uppercase failed.");
mu_assert(check_function("lowercase", "Hello", 0), "lowercase failed.");
return NULL;
}
char *test_failures()
{
mu_assert(check_function("fail_on_purpose", "Hello", 1), "fail_on_purpose should fail.");
return NULL;
}
char *test_dlclose()
{
int rc = dlclose(lib);
mu_assert(rc == 0, "Failed to close lib.");
return NULL;
}
char *all_tests() {
mu_suite_start();
mu_run_test(test_dlopen);
mu_run_test(test_functions);
mu_run_test(test_failures);
mu_run_test(test_dlclose);
return NULL;
}
RUN_TESTS(all_tests);
```
我希望你可以弄清楚它都干了什么，因为这里没有什么新的东西，除了`check_function`函数。这是一个通用的模式，其中我需要重复执行一段代码，然后通过为之创建宏或函数来使它自动化。这里我打算运行`.so`中所加载的函数，所以我创建了一个小型函数来完成它。
## 附加题
+ 这段代码能起作用，但是可能有点乱。清理框架目录，是它包含所有这些文件，但是移除任何和练习29有关的代码。你应该能够复制这个目录并且无需很多编辑操作就能开始新的项目。
+ 研究`runtests.sh`，并且查询有关`bash`语法的资料，来弄懂它的作用。你能够编写这个脚本的C版本吗？
';
练习29：库和链接
最后更新于：2022-04-01 23:29:02
# 练习29：库和链接
> 原文：[Exercise 29: Libraries And Linking](http://c.learncodethehardway.org/book/ex29.html)
> 译者：[飞龙](https://github.com/wizardforcel)
C语言编程的核心能力之一就是链接OS所提供的库。链接是一种为你的程序天机额外特性的方法，这些特性有其它人在系统中创建并打包。你已经使用了一些自动包含的标准库，但是我打算对哭的不同类型和它们的作用做个解释。
首先，库在每个语言中都没有良好的设计。我不知道为什么，但是似乎语言的设计者都将链接视为不是特别重要的东西。它们通常令人混乱，难以使用，不能正确进行版本控制，并以不同的方式链接到各种地方。
C没有什么不同，但是C中的库和链接是Unix操作系统的组件，并且可执行的格式在一些年前就设计好了。学习C如何链接库有助于理解OS如何工作，以及它如何运行你的程序。
C中的库有两种基本类型：
静态
你可以使用`ar`和`ranlib`来构建它，就像上个练习中的`libYOUR_LIBRARY.a`那样（Windows下后缀为`.lib`）。这种库可以当做一系列`.o`对象文件和函数的容器，以及当你构建程序时，可以当做是一个大型的`.o`文件。
动态
它们通常以`.so`（Linux）或`.dll`（Windows）结尾。在OSX中，差不多有一百万种后缀，取决于版本和编写它的人。严格来讲，OSX中的`.dylib`，`.bundle`和`framework`与前面这个三个没什么不同。这些文件都被构建好并且放置到指定的地方。当你运行程序时，OS会动态加载这些文件并且“凭空”链接到你的程序中。
我倾向于对于小型或中性项目使用静态的库，因为它们易于使用，并且工作在在更多操作系统上。我也喜欢将所有代码当如静态库中，之后链接它来执行单元测试，或者链接到所需的程序中。
动态库适用于大型系统，其中空间十分有限，或者大量程序都使用相同的功能。这种情况下不应该为每个程序的共同特性静态链接所有代码，而是应该将它放到动态库中，这样它仅仅会为所有程序加载一份。
在上一个练习中，我讲解了如何构建静态库（`.a`），我会在本书的剩余部分用到它。这个练习中我打算向你展示如何构建一个简单的`.so`库，并且如何使用Unix系统的`dlopen`动态加载它。我会手动执行它，以便你可以理解每件实际发生的事情。之后，附加题这部分会使用c项目框架来创建它。
## 动态加载动态库
我创建了两个源文件里完成它。一个用于侯建`libex29.so`库，另一个是个叫做`ex29`的程序，它可以加载这个库并运行其中的程序、
```c
#include
#include
#include "dbg.h"
int print_a_message(const char *msg)
{
printf("A STRING: %s\n", msg);
return 0;
}
int uppercase(const char *msg)
{
int i = 0;
// BUG: \0 termination problems
for(i = 0; msg[i] != '\0'; i++) {
printf("%c", toupper(msg[i]));
}
printf("\n");
return 0;
}
int lowercase(const char *msg)
{
int i = 0;
// BUG: \0 termination problems
for(i = 0; msg[i] != '\0'; i++) {
printf("%c", tolower(msg[i]));
}
printf("\n");
return 0;
}
int fail_on_purpose(const char *msg)
{
return 1;
}
```
这里面没什么神奇之处。其中故意留了一些bug，看你是否注意到了。你会在随后修复它们。
我们打算使用`dlopen`，`dlsym`，和`dlclose`函数来处理上面的函数。
```c
#include
#include "dbg.h"
#include
typedef int (*lib_function)(const char *data);
int main(int argc, char *argv[])
{
int rc = 0;
check(argc == 4, "USAGE: ex29 libex29.so function data");
char *lib_file = argv[1];
char *func_to_run = argv[2];
char *data = argv[3];
void *lib = dlopen(lib_file, RTLD_NOW);
check(lib != NULL, "Failed to open the library %s: %s", lib_file, dlerror());
lib_function func = dlsym(lib, func_to_run);
check(func != NULL, "Did not find %s function in the library %s: %s", func_to_run, lib_file, dlerror());
rc = func(data);
check(rc == 0, "Function %s return %d for data: %s", func_to_run, rc, data);
rc = dlclose(lib);
check(rc == 0, "Failed to close %s", lib_file);
return 0;
error:
return 1;
}
```
我现在会拆分这个程序，便于你理解这一小段代码其中的原理。
ex29.c:5
我在随后使用这个函数指针定义，来调用库中的函数。这没什么新东西，确保你理解了它的作用。
ex29.c:17
在为一个小型程序做必要的初始化后，我使用了`dlopen`函数来加载由`lib_file`表示的库。这个函数返回一个句柄，我们随后会用到它，就像来打开文件那样。
ex29.c:18
如果出现错误，我执行了通常的检查并退出，但是要注意最后我使用了`dlerror`来查明发生了什么错误。
ex29.c:20
我使用了`dlsym`来获取`lib`中的函数，通过它的字面名称`func_to_run`。它是最强大的部分，因为我动态获取了一个函数指针，基于我从命令行`argv`获得的字符串。
ex29.c:23
接着我调用`func`函数，获得返回值并检查。
ex29.c:26
最后，我像关闭文件那样关闭了库。通常你需要在程序的整个运行时保持它们打开，所以关闭操作并不非常实用，我只是在这里演示它。
> 译者注：由于能够使用系统调用加载，动态库可以被多种语言的程序调用，而静态库只能被C及兼容C的程序调用。
## 你会看到什么
既然你已经知道这些文件做什么了，下面是我的shell会话，用于构建`libex29.so`和`ex29`并随后运行它。下面的代码中你可以学到如何手动构建：
```shell
# compile the lib file and make the .so
# you may need -fPIC here on some platforms. add that if you get an error
$ cc -c libex29.c -o libex29.o
$ cc -shared -o libex29.so libex29.o
# make the loader program
$ cc -Wall -g -DNDEBUG ex29.c -ldl -o ex29
# try it out with some things that work
$ ex29 ./libex29.so print_a_message "hello there"
-bash: ex29: command not found
$ ./ex29 ./libex29.so print_a_message "hello there"
A STRING: hello there
$ ./ex29 ./libex29.so uppercase "hello there"
HELLO THERE
$ ./ex29 ./libex29.so lowercase "HELLO tHeRe"
hello there
$ ./ex29 ./libex29.so fail_on_purpose "i fail"
[ERROR] (ex29.c:23: errno: None) Function fail_on_purpose return 1 for data: i fail
# try to give it bad args
$ ./ex29 ./libex29.so fail_on_purpose
[ERROR] (ex29.c:11: errno: None) USAGE: ex29 libex29.so function data
# try calling a function that is not there
$ ./ex29 ./libex29.so adfasfasdf asdfadff
[ERROR] (ex29.c:20: errno: None) Did not find adfasfasdf
function in the library libex29.so: dlsym(0x1076009b0, adfasfasdf): symbol not found
# try loading a .so that is not there
$ ./ex29 ./libex.so adfasfasdf asdfadfas
[ERROR] (ex29.c:17: errno: No such file or directory) Failed to open
the library libex.so: dlopen(libex.so, 2): image not found
$
```
需要注意，你可能需要在不同OS、不同OS的不同版本，以及不同OS的不同版本的不同编译器上执行构建，则需要修改构建共享库的方式。如果我构建`libex29.so`的方式在你的平台上不起作用，请告诉我，我会为其它平台添加一些注解。
> 译者注：到处编写、到处调试、到处编译、到处发布。--vczh
> 注
> 有时候你会通常运行`cc -Wall -g -DNDEBUG -ldl ex29.c -o ex29`，并且认为它能够正常工作，但是没有。在一些平台上，参数的顺序会影响到它是否生效，这也没什么理由。在Debian或者Ubuntu中你需要执行`cc -Wall -g -DNDEBUG ex29.c -ldl -o ex29`。它是唯一的方式，所以虽然我在这里使用了OSX，但是以后如果你链接动态库的时候它找不到某个函数，要试着自己解决问题。
> 这里面比较麻烦的事情是，实际平台的不同会影响到命令参数的顺序。将`-ldl`放到某个位置没有理由与其它位置不同。他只是一个选项，还需要了解这些简直是太气人了。
## 如何使它崩溃
打开`lbex29.so`，并且使用能够处理二进制的编辑器编辑它。修改一些字节，然后关闭。看看你是否能使用`dlopen`函数来打开它，即使你修改了它。
## 附加题
+ 你注意到我在`libex29.c`中写的不良代码了吗？我使用了一个`for`循环来检查`'\0'`的结尾，修改它们使这些函数总是接收字符串长度，并在函数内部使用。
+ 使用项目框架目录，并且为这个练习创建新的项目。将`libex29.c`放入`src/`目录，修改`Makefile`使它能够构建`build/libex29.so`。
+ 将`ex29.c`改为`tests/ex29_tests.c`，使它做为单元测试执行。使它能够正常工作，意思是你需要修改它让它加载`build/libex29.so`文件，并且运行上面我手写的测试。
+ 阅读`man dlopen`文档，并且查询所有有关函数。尝试`dlopen`的其它选项，比如`RTLD_NOW`。
';