21.2 字符串函数

在日常编写字符串处理逻辑时，很容易写出两类看似正常、实则暗藏严重性能或安全隐患的代码。例如，在循环中不断使用 strcat 往目标缓冲区后追加单词，当追加到八千个单词时，底层累计搬运和扫描的内存量竟然达到了一亿六千万个字节；而如果换一种思路，在追加过程中始终在局部记录当前缓冲区的写入末尾指针，完成同样的拼接任务总共只需要扫描并写入约四万个字节。另一个极其典型的误区发生在复制场景：开发者为了防范缓冲区溢出，习惯性地调用 strncpy(dst, src, sizeof dst) 执行所谓的「安全截断拷贝」，当 8 字节的目标缓冲区遭遇 11 字节的超长源字符串时，后续如果直接调用 printf("%s") 打印，控制台末尾往往会莫名其妙地多出一段来自相邻内存区域的乱码。

这两处典型故障的根源，并不在于外部循环或打印语句本身，而在于使用者未能透彻理解这两个基础函数的标准化契约：strcat 每执行一次都会从头重新扫描目标字符串以寻找末尾的零字节，其运行开销与目标串已有的累计长度严格成正比；而 strncpy 在源字符串长度不小于给定限制 count 时，规范明确规定不会在目标末尾追加终止空字符。

在本节中，我们将严格依据 C 语言标准，亲手实现 <string.h> 中与区域设置（locale）无关的十二个核心字符串处理函数，并将它们整合到 src/mdr_string.c 中。在编码与推演的过程中，我们将深入审视三项至关重要的接口本质：哪些物理字节被界定为字符串的有效组成部分、标准库函数的返回值究竟做出了哪些承诺与妥协、以及为什么某些带有深厚历史印记的接口会维持当前的设计形态。

1. 表示与比较规则

在标准 C 语言的设计中，字符串的定义是极其朴素的：它是一段以空字符（null character，即数值为 0 的字节 '\0'）显式结尾的连续字节序列。由于该数据结构并不在内存头部维护长度字段，因此绝大多数操作都依赖顺序扫描：strlen 统计的是终止空字符之前的有效字节个数；strcmp 会顺着指针逐字节比对，直到发现第一个不相等的字节或遇到零字节时停下；而 strchr 则将终止空字符本身也视为可供检索的目标内容。这一整套处理模式都建立在一个根本前置假设之上——调用方传入的内存指针必须指向一个合法以零结尾的缓冲区。若调用方不慎传入了一块未初始化的裸数组或缺失零字节的缓冲区，便构成了前置条件违约，标准库函数出于运行效率考量不会在运行时展开边界验证，程序随即落入未定义行为。

对于涉及字符大小比对的逻辑，我们在 21.1 节实现 mdr_strcmp 时已经确立了一条核心准则：所有输入字符指针必须首先转换为 const unsigned char * 之后再展开逐字节比对：

int mdr_strcmp(const char *lhs, const char *rhs) {
    const unsigned char *p1 = (const unsigned char *)lhs;
    const unsigned char *p2 = (const unsigned char *)rhs;

    MDR_ASSERT(lhs != NULL);
    MDR_ASSERT(rhs != NULL);
    while (*p1 != '\0' && *p1 == *p2) {
        p1++;
        p2++;
    }
    return (int)*p1 - (int)*p2;
}

之所以必须显式转换为无符号字符指针，是因为 C 标准允许各编译器实现自行决定 char 类型是否带有符号。在 char 默认为有符号整型的硬件平台上，数值如 0x80 的扩展字符会被解释为负数；若直接将负数与字符常量 'a'（ASCII 值为 97）进行比较，得出的序关系将与裸字节数值的高低完全相反。将其强制转换为 unsigned char 后，每个字节的取值范围被严格规整在 0 到 255 的整数空间内，从而确保字典序比对在任何体系结构上都保持确定且可移植。

在所有字符串拷贝与拼接函数中，目标指针与源指针均被冠以 restrict 限定符：这在类型契约层面明示了两块内存区域在物理上严禁重叠。restrict 赋予了编译器优化器充分的信任假设，即对目标缓冲区的写入绝不会干扰源串的数据读取，编译器可以放心地重排相关内存读写指令；一旦调用方打破契约传入了重叠地址，执行结果便完全无法保证。若业务场景确实需要支持自重叠内存的搬移，必须转而调用 21.3 节实现的 mdr_memmove。

对于返回字符指针的检索函数，C 语言历史上存在一处为人熟知的类型安全包袱。在 C17 以及更早期的标准中，原型声明如下：

char *strchr(const char *s, int ch);

传入的实参是指向只读常量的 const char *，但函数的返回值类型却被声明为了可读写的裸指针 char *。这种声明机制打破了类型系统的只读保护，使得调用方可以轻易借助返回的指针去就地覆写一个可能驻留在只读数据段的字面量对象，且编译器在前端检查阶段完全无法拦截。直到 C23 标准，WG14 才利用宏与泛型机制将 strchr、strrchr 以及 strstr 等改造为了类型泛型接口：当调用方传入常量指针时返回常量指针，传入可变指针时返回可变指针。为了在工程实践中最大化兼顾与经典 C11/C17 代码库的二进制兼容性，本章的 mdr_ 函数依然沿用经典的 C17 声明形式；后续如果需要利用 C11 的 _Generic 宏实现等价的类型安全守卫，其技术细节在泛型选择中已有系统拆解。宿主运行库是否已经适配了 C23 的泛型版本，完全取决于平台更新节奏，不能随意预设。

十二个函数的规格要点与实现要点：

函数	规格要点	实现要点
`mdr_strcpy`	复制含终止空字符；返回 `dest`	赋值结果参与条件判断，一次读写一个字节
`mdr_strncpy`	最多写 `count` 个字节；源短则补零，源不短则无终止符	两个循环：先复制，再补零
`mdr_strcat`	追加并覆盖原终止符；返回 `dest`	先 `mdr_strlen` 定位末尾，再复制
`mdr_strncat`	最多追加 `count` 个字符，总是补终止符	空间要求是 `strlen(dest) + count + 1`
`mdr_strncmp`	最多比较 `count` 个字节	越界前遇到终止符也要停
`mdr_strchr`	查首次出现，终止空字符也查	循环条件写成「非空且不等」
`mdr_strrchr`	查最后一次出现	一次扫描，记住最后命中的位置
`mdr_strspn`	最大前缀，字符都在 `accept` 中	256 项查找表
`mdr_strcspn`	最大前缀，字符都不在 `reject` 中	同一张表，条件取反
`mdr_strpbrk`	首个出现在集合中的字符	用 `mdr_strcspn` 定位
`mdr_strstr`	子串首次出现；空 `needle` 返回 `haystack`	用 `mdr_strchr` 找首字节，再比其余
`mdr_strtok`	按分隔符切分，改写输入，进度保存在静态对象	`mdr_strspn` 跳过分隔符，`mdr_strcspn` 找字段尾

2. 复制与连接

mdr_strcpy 的循环把赋值和判断合成一步：

char *mdr_strcpy(char *restrict dest, const char *restrict src) {
    char *d = dest;

    MDR_ASSERT(dest != NULL);
    MDR_ASSERT(src != NULL);
    while ((*d = *src) != '\0') {
        d++;
        src++;
    }
    return dest;
}

赋值表达式 *d = *src 的求值结果就是刚刚写入到目标地址的那个字符数值。通过将其与 '\0' 直接进行比对，循环能够在成功拷贝完终止空字符的那一瞬间优雅地退出。按照标准定义，函数原样返回起始指针 dest，以便支持链式调用或作为其他嵌套函数的实参。

在实现字符串拼接函数 mdr_strcat 时，一种直观的做法是先调用 mdr_strlen 探测目标串的末尾位置，再将源串的内容顺次复制过去：

char *mdr_strcat(char *restrict dest, const char *restrict src) {
    char *d;

    MDR_ASSERT(dest != NULL);
    MDR_ASSERT(src != NULL);
    d = dest + mdr_strlen(dest);
    mdr_strcpy(d, src);
    return dest;
}

然而，这种符合接口约定的直观实现却潜藏着巨大的渐进性能代价：每一次执行追加操作，函数都必须从 dest 的第一个字符开始无功地向后遍历，直到重新确认原有的终止符。如果连续追加 $n$ 个单词，底层需要扫描的字节数将依次累加为 $0 + 5 + 10 + \dots$ ，算法的时间复杂度不可避免地退化为 $O (n^{2})$ 。下面这段对比测试程序生动量化了这两种策略在内存吞吐量上的鸿沟，每次追加的固定模式为 5 个字符的 "word "：

#include <stdio.h>

static unsigned long scanned;
static unsigned long copied;

/* 与 strcat 相同：每次都从开头找末尾 */
static char *append_head(char *dest, const char *word) {
    char *d = dest;

    while (*d != '\0') {
        d++;
        scanned++;
    }
    while ((*d = *word) != '\0') {
        d++;
        word++;
        copied++;
    }
    return dest;
}

/* 返回新的末尾位置，下一次从这里继续追加 */
static char *append_tail(char *tail, const char *word) {
    while ((*tail = *word) != '\0') {
        tail++;
        word++;
        copied++;
    }
    return tail;
}

int main(void) {
    static char buf[200000];

    printf("%8s %14s %14s\n", "words", "strcat", "tail");
    for (unsigned long n = 1000; n <= 8000; n *= 2) {
        unsigned long head_bytes;
        unsigned long tail_bytes;
        char *tail = buf;

        buf[0] = '\0';
        scanned = 0;
        copied = 0;
        for (unsigned long i = 0; i < n; i++) {
            append_head(buf, "word ");
        }
        head_bytes = scanned + copied;

        buf[0] = '\0';
        scanned = 0;
        copied = 0;
        tail = buf;
        for (unsigned long i = 0; i < n; i++) {
            tail = append_tail(tail, "word ");
        }
        tail_bytes = scanned + copied;
        printf("%8lu %14lu %14lu\n", n, head_bytes, tail_bytes);
    }
    return 0;
}

两次追加的词数每翻一倍，第一列访问的字节数变成四倍，第二列只翻一倍：

zsh - tailcat

text

$ gcc -std=c17 -Wall -Wextra -O2 -o tailcat tailcat.c
$ ./tailcat
   words         strcat           tail
    1000        2502500           5000
    2000       10005000          10000
    4000        40010000          20000
    8000       160020000          40000

只要在拼接过程中持续将「末尾写入位置」维护在手边，算法的开销就能被牢牢控制在与最终文本总长度严格成正比的 $O (n)$ 级别。在 POSIX 标准中，操作系统运行时为此提供了一个经典的实用接口 stpcpy：与普通 strcpy 返回目标头部不同，stpcpy 专门返回指向目标缓冲区中新写入的终止空字符的指针，其返回值可以直接无缝充当下一次追加的起始地址。虽然 stpcpy 并未被纳入 C17 标准库的核心规范，但我们在 21.5 节会亲手实现对应的 mdr_stpcpy 版本。在日常业务编码中，即使手头缺少现成的标准库扩展，读者也可以仿照上述示例，封装一个返回末尾写入指针的轻量追加函数。

接下来是本节中最容易引发安全缺陷与认知误区的接口——mdr_strncpy。如果仔细审视其规格，可以发现其后置条件实际上分裂为了两条截然不同的执行分支：

char *mdr_strncpy(char *restrict dest, const char *restrict src, size_t count) {
    size_t i = 0;

    MDR_ASSERT(dest != NULL);
    MDR_ASSERT(src != NULL);
    for (; i < count && src[i] != '\0'; i++) {
        dest[i] = src[i];
    }
    for (; i < count; i++) {
        dest[i] = '\0';
    }
    return dest;
}

在内部实现中，代码被明确划分为两个先后衔接的循环：第一个循环负责将源串字符依次搬运到目标缓冲区，直至源串遇到空字符或已经写满 count 个限制；而第二个循环则负责将目标缓冲区后续尚未填充的剩余空间全部强行用零字节灌满。这两个截然不同的分支逻辑导向了性质完全相反的输出状态：

当源字符串的实际有效长度严格小于 count 时：目标缓冲区能够完整收录源串的全部文本，且后续的全部空余空间都会被追加补齐为 \0 直至满 count 字节，此时目标缓冲区构成一个合法的以空字符结尾的 C 字符串。
当源字符串的实际有效长度大于或等于 count 时：目标缓冲区的前 count 个物理字节虽然精确对应源串的前 count 个字符，但末尾绝不会自动追加任何终止空字符，此时输出仅仅是一段定长裸字符数组，根本不再构成合法的 C 字符串！

把目标缓冲区先填满 #（0x23），再按字节打印，两种情况一目了然：

#include "mdr_string.h"
#include <stdio.h>
#include <string.h>

static void dump(const char *label, const unsigned char *p, size_t n) {
    printf("%-22s", label);
    for (size_t i = 0; i < n; i++) {
        printf(" %02X", p[i]);
    }
    printf("\n");
}

int main(void) {
    unsigned char buf[8];

    memset(buf, '#', sizeof buf);
    mdr_strncpy((char *)buf, "ab", sizeof buf);
    dump("src \"ab\" (2):", buf, sizeof buf);

    memset(buf, '#', sizeof buf);
    mdr_strncpy((char *)buf, "abcdefgh", sizeof buf);
    dump("src \"abcdefgh\" (8):", buf, sizeof buf);

    memset(buf, '#', sizeof buf);
    mdr_strncpy((char *)buf, "abcdefghij", sizeof buf);
    dump("src \"abcdefghij\" (10):", buf, sizeof buf);
    return 0;
}

zsh - nc

text

$ gcc -std=c17 -Wall -Wextra -Iinclude -o nc nc.c src/mdr_string.c
$ ./nc
src "ab" (2):          61 62 00 00 00 00 00 00
src "abcdefgh" (8):    61 62 63 64 65 66 67 68
src "abcdefghij" (10): 61 62 63 64 65 66 67 68

第一行是字符串，后两行不是：八个字节里一个零都没有，紧跟着的字节是缓冲区外面的东西。

strncpy 的后置条件有两种情形

strncpy(dest, src, count) 最多写 count 个字节。src 作为字符串短于 count 时，复制完后继续补空字符直到写满 count 个字节，结果是字符串；src 不短于 count 时，dest 的前 count 个字节等于 src 的前 count 个字节，不带终止空字符，结果不是字符串。函数的返回值始终是 dest。

理解了这套后置条件，就能彻底想通许多历史遗留代码中离奇 Bug 的成因。不少程序员看到 strncpy 名字中带有一个 n，便先入为主地认定它代表「带有长度上限的安全拷贝，且自动保证结果以空字符结尾」。然而，该函数最初被设计出来并非为了通用安全复制，其后置条件仅仅做到了「绝不向目标缓冲区写入超过 count 个物理字节」；至于末尾到底有没有终止符，完全取决于源串的长度。以下结构体字段写入代码展示了当字段长度恰好被用满时，目标内存如何沦落为缺少终止符的危险状态：

#include "mdr_string.h"
#include <stdio.h>
#include <string.h>

struct record {
    char name[8];
    char note[8];
};

int main(void) {
    struct record r;

    /* 两个字段预先填满 '#'，再用 strncpy 写入 */
    memset(&r, '#', sizeof r);
    mdr_strncpy(r.name, "Christopher", sizeof r.name);
    mdr_strncpy(r.note, "ok", sizeof r.note);
    printf("name = [%s]\n", r.name);
    printf("note = [%s]\n", r.note);
    printf("sizeof r = %lu\n", (unsigned long)sizeof r);
    return 0;
}

"Christopher" 有 11 个字母，8 字节装不下，前 8 个字节写进去之后就没有然后了：

zsh - struct_nc

text

$ gcc -std=c17 -Wall -Wextra -Iinclude -o struct_nc struct_nc.c src/mdr_string.c
$ ./struct_nc
name = [Christopok]
note = [ok]
sizeof r = 16

在控制台输出中，name 字段打印出来的结果是异常的 Christopok：其物理内存中的前 8 个字节确实是截断的 Christop，但在其紧邻的高地址方向，正好排列着结构体中的下一个成员 note（内容为 ok\0）。由于 name 的 8 个字节内根本没有用于终止扫描的 \0，printf 接收到 %s 格式控制符后，只能盲目地顺着内存指针一直向后读下去，直至偶然遇到 note 内部的零字节为止。这种输出在表象上似乎只是「末尾多了几个字符」，但其底层本质是一起严重的内存越界读漏洞。

如果希望在复制超长文本时自动截断并始终保证以零结尾，盲目调大缓冲区容量或增加 strncpy 的调用层数并没有触及根本，而是应当改用契约语义明确保证零结尾的替代接口。例如标准库中的 snprintf 总是会在缓冲区末尾保留一位写入终止空字符，唯一的代价是在遭遇截断时会舍弃超出容量的内容：

❌ 用 strncpy 做安全复制

char name[8];

/* 源比目标长时没有终止空字符 */
strncpy(name, src, sizeof name);
printf("%s\n", name);

✅ 用 snprintf 限制长度

char name[8];

/* 总是有终止空字符，超长部分被截掉 */
snprintf(name, sizeof name, "%s", src);
printf("%s\n", name);

同样的源和目标，两个函数写出的字节：

#include <stdio.h>
#include <string.h>

static void dump(const char *label, const unsigned char *p, size_t n) {
    printf("%-12s", label);
    for (size_t i = 0; i < n; i++) {
        printf(" %02X", p[i]);
    }
    printf("\n");
}

int main(int argc, char *argv[]) {
    const char *name = argc > 1 ? argv[1] : "";
    char dst[8];

    memset(dst, '#', sizeof dst);
    strncpy(dst, name, sizeof dst);
    dump("strncpy:", (const unsigned char *)dst, sizeof dst);

    memset(dst, '#', sizeof dst);
    snprintf(dst, sizeof dst, "%s", name);
    dump("snprintf:", (const unsigned char *)dst, sizeof dst);
    printf("snprintf 的结果: [%s]\n", dst);
    return 0;
}

zsh - snp

text

$ gcc -std=c17 -Wall -Wextra -o snp snp.c
$ ./snp Christopher
strncpy:     43 68 72 69 73 74 6F 70
snprintf:    43 68 72 69 73 74 6F 00
snprintf 的结果: [Christo]

snprintf 把第 8 个字节留给了终止空字符，代价是少复制一个字符，打印出来是 Christo。需要知道是否发生截断时，看它的返回值：返回值是「假如空间足够，本来会写多少个字符」，大于等于 sizeof 就说明被截断了。

因此，在日常代码编写中，切忌把 strncpy 当作所谓「防御溢出的安全拷贝工具」来使用：它在源数据过长时不提供零结尾，在源数据较短时又会极其低效地把剩余空间全部机械刷零，这两项特质几乎完全背离了常规 C 字符串的处理直觉。在真实的工业软件中，strncpy 唯一的合理栖身之所是早期 Unix 目录项或老旧网络协议中那种「允许字段被字符填满且不要求末尾零字节」的定长记录场景。对于常规的动态 C 字符串截断复制，优先选择 snprintf，或者使用 21.5 节实现的 mdr_strlcpy。

与此形成鲜明对照的是拼接接口 mdr_strncat，它的规格给出了明确的零结尾保证：

char *mdr_strncat(char *restrict dest, const char *restrict src, size_t count) {
    char *d;

    MDR_ASSERT(dest != NULL);
    MDR_ASSERT(src != NULL);
    d = dest + mdr_strlen(dest);
    while (count > 0 && *src != '\0') {
        *d = *src;
        d++;
        src++;
        count--;
    }
    *d = '\0';
    return dest;
}

在后置条件中，目标缓冲区的最终内容由 dest 原有的有效字符串、至多 count 个源串字符、以及一个强制追加的终止空字符共同组成。因此，调用方必须确保目标缓冲区拥有至少 strlen(dest) + count + 1 个字节的可写物理内存。在实际编码中，由于少计算这 + 1 个字节而引发的单字节缓冲区溢出（Off-by-one 漏洞）屡见不鲜，追加的最后一个 \0 恰好落在了合法缓冲区之外的一字节地址上。

3. 比较

mdr_strncmp 在 mdr_strcmp 的基础上加一个计数：

int mdr_strncmp(const char *lhs, const char *rhs, size_t count) {
    const unsigned char *p1 = (const unsigned char *)lhs;
    const unsigned char *p2 = (const unsigned char *)rhs;

    MDR_ASSERT(lhs != NULL);
    MDR_ASSERT(rhs != NULL);
    while (count > 0 && *p1 != '\0' && *p1 == *p2) {
        p1++;
        p2++;
        count--;
    }
    if (count == 0) {
        return 0;
    }
    return (int)*p1 - (int)*p2;
}

当 count 逐步递减至 0 时，说明在指定的比对窗口内两个字符串对应的前缀完全一致，函数返回 0。而在内部 while 循环中，*p1 != '\0' 这个判空条件具有绝对的防御意义：当传入的 count 上限大于两个字符串的实际有效长度时，若省略对终止空字符的探测，指针就会盲目越过字符串末尾并继续向后扫描未定义内存。

关于比较函数的返回值，初学者极易产生一种误解，以为两个字符串不相等时函数一定会返回固定的 -1 或 1。然而在 ISO C 规范中，标准仅仅对返回值的正负符号给出了严格契约：当 lhs 字典序小于 rhs 时返回负数，相等时返回 0，大于时返回正数；至于具体的数值大小，标准完全留给运行库自由实现。因此，同一组字符串输入在不同操作系统或不同 C 运行时环境下，往往会吐出截然不同的具体整数。下面的测试程序直接调用宿主标准库，打印三个经典比对函数面对同一组输入时的实际输出：

#include <stdio.h>
#include <string.h>

int main(int argc, char *argv[]) {
    const char *a = argc > 1 ? argv[1] : "apple";
    const char *b = argc > 2 ? argv[2] : "apricot";

    printf("strcmp   = %d\n", strcmp(a, b));
    printf("strncmp5 = %d\n", strncmp(a, b, 5));
    printf("memcmp5  = %d\n", memcmp(a, b, 5));
    return 0;
}

实参取自 argv，不写成字符串字面量。这样 GCC 无法在编译期把结果折叠为常数，调用才会实际落到库函数内部。

zsh - sign_rt

text

$ ./sign_rt                    # Windows，MinGW-w64 GCC 13.2 + UCRT
strcmp   = -1
strncmp5 = -1
memcmp5  = -1

zsh - sign_rt

text

$ ./sign_rt                    # Debian 13，GCC 14.2 + glibc 2.41
strcmp   = -2
strncmp5 = -2
memcmp5  = -2

在上述终端输出中，Windows 平台上的 UCRT 统一返回规整的 -1，而 Linux 下的 glibc 则直接返回两字符在底层 ASCII 码上的数值差值（'p' 的 ASCII 码是 112，'r' 的 ASCII 码是 114，两者相减恰好为 -2）。我们手写的 mdr_strncmp 直接返回 (int)*p1 - (int)*p2，因此其数值表现与 glibc 完全一致。这一实验给我们的测试编写敲响了警钟：在单元测试断言中，必须严格断言 mdr_strcmp(a, b) < 0，而绝不能硬编码 == -1，否则测试套件的跨平台可移植性将瞬间被打破。

4. 查找单个字符

在实现单个字符的检索函数 mdr_strchr 时，必须特别关注终止空字符的特殊处理地位：

char *mdr_strchr(const char *s, int ch) {
    char c = (char)ch;

    MDR_ASSERT(s != NULL);
    while (*s != '\0' && *s != c) {
        s++;
    }
    if (*s == c) {
        return (char *)s;
    }
    return NULL;
}

形参列表中的待查字符被声明为 int ch，这完全是为了契合 C 语言历史标准中字符常量提升的规约；而在函数体内部，必须将其强制转换回目标字符类型 char 参与比对。在扫描循环中，跳出循环的条件有两个：其一是当前指针指向了终止空字符 \0，其二是当前字符碰巧命中了目标 c。在退出循环之后，代码必须再次通过 if (*s == c) 进行复核，只有这样才能正确响应 mdr_strchr(s, '\0') 这一极端边界调用。在规格中，「终止空字符也在查找范围内」这一显式保证正是指此行为：当调用方要求查找零字符时，函数必须精准返回指向字符串结尾处那个 \0 字节自身的指针，唯有当目标字符在整个串中完全未出现时，才允许返回 NULL。

在查找最后一次出现的接口 mdr_strrchr 中，指针必须自前向后完整遍历整个字符串，并沿途记录下最后一次命中目标的物理地址：

char *mdr_strrchr(const char *s, int ch) {
    const char *last = NULL;
    char c = (char)ch;

    MDR_ASSERT(s != NULL);
    do {
        if (*s == c) {
            last = s;
        }
    } while (*s++ != '\0');
    return (char *)last;
}

这里巧妙地采用了 do … while 循环结构，从而确保即便输入是一个空串 ""，末尾的终止空字符也能顺理成章地进入循环体内部参与一次判断；而条件判断表达式中的自增操作 *s++ != '\0' 会在每次比对完成后自动将指针向前推进一格。初始时将指针 last 显式初始化为 NULL，能够同时干净利落地覆盖「检索目标在串中未出现」以及「传入的是空串且待查字符非零」这两种未命中情形。

两个函数对 "banana" 的结果：

#include "mdr_string.h"
#include <stdio.h>

static int offset_of(const char *base, const char *p) {
    return p != NULL ? (int)(p - base) : -1;
}

int main(void) {
    const char text[] = "banana";

    printf("strchr(text, 'a')     偏移 %d\n", offset_of(text, mdr_strchr(text, 'a')));
    printf("strchr(text, 'n')     偏移 %d\n", offset_of(text, mdr_strchr(text, 'n')));
    printf("strchr(text, 终止符)   偏移 %d\n", offset_of(text, mdr_strchr(text, 0)));
    printf("strrchr(text, 'a')    偏移 %d\n", offset_of(text, mdr_strrchr(text, 'a')));
    printf("strrchr(text, 终止符)  偏移 %d\n", offset_of(text, mdr_strrchr(text, 0)));
    printf("strrchr(text, 'z')    偏移 %d\n", offset_of(text, mdr_strrchr(text, 'z')));
    return 0;
}

zsh - chr

text

$ gcc -std=c17 -Wall -Wextra -Iinclude -o chr chr.c src/mdr_string.c
$ ./chr
strchr(text, 'a')     偏移 1
strchr(text, 'n')     偏移 2
strchr(text, 终止符)   偏移 6
strrchr(text, 'a')    偏移 5
strrchr(text, 终止符)  偏移 6
strrchr(text, 'z')    偏移 -1

返回值是 char *，实参是 const char *，中间必须做一次强制转换。这是 C17 接口本身遗留的历史妥协，调用方自己清楚 s 指向的究竟是不是可写对象，标准库原型在此处无法提供静态类型保护。

单选题目内容

返回 NULL

返回指向终止空字符的指针

返回指向 s 开头的指针

行为未定义

正确答案是 B。终止空字符算字符串的一部分，查找它一定能命中，返回的指针指向那个字节。只有目标字符不在字符串里时才返回 NULL。

5. 字符集合

在文本解析与词法提取中，经常需要依据某个字符集合来确定字段边界。标准库为此提供了一对对称函数：mdr_strspn 返回待查字符串 s 开头由指定白名单集合 accept 中字符组成的最长连续前缀长度；而 mdr_strcspn 则恰好相反，返回不包含黑名单集合 reject 中任何字符的最长前缀长度。

最为直观的初学者写法，是对待测串中的每一个字符，都顺次遍历一遍集合字符串。然而这种朴素双重循环的时间代价是 $O (n \times m)$ （其中 $n$ 为源串长度， $m$ 为字符集大小），在长文本解析中极易形成性能瓶颈。

由于单字节字符的取值范围被严格限定在 0 到 255 之间，我们可以引入一张包含 256 项的布尔查找表作为集合缓存：首先线性扫描一遍集合串，将出现的字符所对应的表项置为 true；随后在主扫描过程中，对每个字符的成员判定便能以 $O (1)$ 的开销通过直接查表完成，从而将整体算法的渐进复杂度大幅削减到线性的 $O (n + m)$ ：

size_t mdr_strspn(const char *s, const char *accept) {
    bool in_set[256] = {false};
    size_t n = 0;

    MDR_ASSERT(s != NULL);
    MDR_ASSERT(accept != NULL);
    while (*accept != '\0') {
        in_set[(unsigned char)*accept] = true;
    }
    while (s[n] != '\0' && in_set[(unsigned char)s[n]]) {
        n++;
    }
    return n;
}

在利用字符值作为数组下标时，必须强制转换为 unsigned char。在 char 带有符号位的编译环境下，一旦遇到大于等于 0x80 的扩展字符（如 UTF-8 编码的多字节片段），若不加转换直接取下标，会在内存中计算出负数偏移，直接导致对栈帧前序内存的越界非法写入。

两种实现的比较次数用一个计数器量出来：

#include <stdbool.h>
#include <stdio.h>
#include <string.h>

static unsigned long compares;

/* 朴素版：对每个字符在 accept 里从头找一遍 */
static size_t naive_strspn(const char *s, const char *accept) {
    size_t n = 0;

    while (s[n] != '\0') {
        const char *a = accept;
        bool found = false;

        while (*a != '\0') {
            compares++;
            if (*a == s[n]) {
                found = true;
                break;
            }
            a++;
        }
        if (!found) {
            break;
        }
        n++;
    }
    return n;
}

/* 查找表版：先把 accept 摊成 256 项表，再线性扫描 */
static size_t table_strspn(const char *s, const char *accept) {
    bool in_set[256] = {false};
    size_t n = 0;

    while (*accept != '\0') {
        in_set[(unsigned char)*accept] = true;
        accept++;
    }
    while (s[n] != '\0') {
        compares++;
        if (!in_set[(unsigned char)s[n]]) {
            break;
        }
        n++;
    }
    return n;
}

int main(void) {
    static char text[1u << 20];
    const char *accept = "0123456789abcdefghijklmnopqrstuvwxyz";

    memset(text, 'z', sizeof text - 1u);

    compares = 0;
    size_t n1 = naive_strspn(text, accept);
    unsigned long c1 = compares;

    compares = 0;
    size_t n2 = table_strspn(text, accept);
    unsigned long c2 = compares;

    printf("输入 %lu 个字符，集合 %lu 个字符，命中集合最后一个字符\n",
           (unsigned long)strlen(text), (unsigned long)strlen(accept));
    printf("朴素版：%lu 次比较\n", c1);
    printf("查找表版：%lu 次比较\n", c2);
    printf("结果：%lu 与 %lu\n", (unsigned long)n1, (unsigned long)n2);
    return 0;
}

zsh - spn_count

text

$ gcc -std=c17 -Wall -Wextra -O2 -o spn_count spn_count.c
$ ./spn_count
输入 1048575 个字符，集合 36 个字符，命中集合最后一个字符
朴素版：37748700 次比较
查找表版：1048575 次比较
结果：1048575 与 1048575

朴素版比较了 3774 万次，查找表版 105 万次，后者约为前者的三十六分之一，正好等于集合大小。前缀长度两边一致。

❌ 嵌套循环

size_t strspn_naive(const char *s, const char *accept) {
    size_t n = 0;

    while (s[n] != '\0') {
        const char *a = accept;
        bool found = false;

        while (*a != '\0') {
            if (*a == s[n]) {
                found = true;
                break;
            }
            a++;
        }
        if (!found) {
            break;
        }
        n++;
    }
    return n;
}

✅ 256 项查找表

size_t strspn_table(const char *s, const char *accept) {
    bool in_set[256] = {false};
    size_t n = 0;

    while (*accept != '\0') {
        in_set[(unsigned char)*accept] = true;
        accept++;
    }
    while (s[n] != '\0' && in_set[(unsigned char)s[n]]) {
        n++;
    }
    return n;
}

如果追求极致的空间压缩，查找表还可以进一步紧凑化：由于每个表项只需要表示存在与否的二值状态，我们可以用 1 个二进制位代替 1 个 bool 字节，256 个状态恰好可以浓缩进 32 个字节（256 位）的位图（bitmap）中：

static size_t bitmap_strspn(const char *s, const char *accept) {
    unsigned char bitmap[32] = {0};
    size_t n = 0;

    while (*accept != '\0') {
        unsigned char c = (unsigned char)*accept;

        bitmap[c / 8] |= (unsigned char)(1u << (c % 8));
        accept++;
    }
    while (s[n] != '\0') {
        unsigned char c = (unsigned char)s[n];

        if ((bitmap[c / 8] & (1u << (c % 8))) == 0) {
            break;
        }
        n++;
    }
    return n;
}

在工业级实现中，musl libc 的 strspn 正是采用了这种位图思路，将 256 位状态压缩进一组按机器字对齐的整数数组中，以极小的栈空间达成零动态分配的高效检索。而在本章的 mdr_strspn 教学实现中，我们选择保留直观的 bool in_set[256] 数组形式，逻辑清晰直白，256 字节的局部数组在现代 CPU 的 L1 缓存与函数栈帧中占用也微乎其微。

实现黑名单前缀统计函数 mdr_strcspn 时，算法骨架与上述代码几乎完全一致，唯一的差异仅在于主扫描循环的布尔判定取反：

size_t mdr_strcspn(const char *s, const char *reject) {
    bool in_set[256] = {false};
    size_t n = 0;

    MDR_ASSERT(s != NULL);
    MDR_ASSERT(reject != NULL);
    while (*reject != '\0') {
        in_set[(unsigned char)*reject] = true;
        reject++;
    }
    while (s[n] != '\0' && !in_set[(unsigned char)s[n]]) {
        n++;
    }
    return n;
}

最后，定位字符集合中任意字符首度出现的接口 mdr_strpbrk 甚至无需编写独立的扫描循环。根据数学定义，它所要寻找的「第一个出现在目标集合中的字符地址」，其在字符串中的物理偏移量恰好等于 mdr_strcspn 终止时的下标位置：

char *mdr_strpbrk(const char *s, const char *breakset) {
    size_t n = mdr_strcspn(s, breakset);

    if (s[n] == '\0') {
        return NULL;
    }
    return (char *)(s + n);
}

mdr_strcspn 只有在成功撞见集合中字符、或者扫描到达串尾 \0 时才会停止。因此，只要检查 s[n] 是否为空字符，便能立即分辨是未命中还是成功定位。通过一张查找表的预处理思想，我们以极度凝练的代码一并解决了四个集合类接口的高效实现。

多选题目内容

把集合摊成 256 项查找表，每步只查一次

把 accept 里的字符排序后二分查找

用 32 字节位图记录每个字节值是否出现

每次调用时先计算 accept 的长度，遇到相同长度直接返回

正确答案是 A、C。查找表和位图都是把「集合成员判断」从扫描变成一次取下标，预处理一次之后每步 O(1)。B 不对：二分查找每步是 O(log m)，效率提升有限，还需要预先排序，甚至会破坏调用方传入的只读 accept。D 与集合内容无关，判断不出任何字符是否属于集合。

6. 子串查找

mdr_strstr 用 mdr_strchr 找 needle 的第一个字节，找到之后比较剩下的部分：

char *mdr_strstr(const char *haystack, const char *needle) {
    size_t nlen = mdr_strlen(needle);
    const char *p = haystack;

    MDR_ASSERT(haystack != NULL);
    MDR_ASSERT(needle != NULL);
    if (nlen == 0) {
        return (char *)haystack;
    }
    while ((p = mdr_strchr(p, needle[0])) != NULL) {
        if (mdr_strncmp(p, needle, nlen) == 0) {
            return (char *)p;
        }
        p++;
    }
    return NULL;
}

当 needle 为空字符串 "" 时，函数直接原样返回母串起始指针 haystack，这一特殊后置条件在 ISO C 规范中有明确的白纸黑字约束，严禁返回 NULL。在随后的主循环中，我们将 needle[0] 作为实参传给 mdr_strchr，利用单字符查找快速跳转到每一个潜在候选位置。需要注意的是，模式串的首字符可能包含大于等于 0x80 的扩展编码，这也解释了为何 mdr_strchr 的形参必须按 int 规范传递并在内部安全转换。

这种由外层字符跳转与内层子串比对构成的朴素匹配算法，在遭遇特定病态输入时其最坏时间代价会退化到 $O (n \times m)$ 。例如将长为 $n$ 的母串设定为连续的字符 'a'，将长为 $m$ 的子串设定为前 $m - 1$ 个字符为 'a' 且最后一个字符为 'b'；在此类场景下，算法在母串的每一个物理起点都必须比对到子串的最末尾才会判定失败。上述基准测试直观呈现了这一退化趋势：

#include <stdio.h>
#include <string.h>

/* 与 mdr_strstr 相同的朴素算法，只加了比较计数 */
static unsigned long compares;

static const char *counted_strstr(const char *haystack, const char *needle) {
    size_t nlen = strlen(needle);
    const char *p = haystack;

    if (nlen == 0) {
        return haystack;
    }
    while ((p = strchr(p, needle[0])) != NULL) {
        size_t i = 0;

        while (i < nlen) {
            compares++;
            if (p[i] != needle[i]) {
                break;
            }
            i++;
        }
        if (i == nlen) {
            return p;
        }
        p++;
    }
    return NULL;
}

int main(void) {
    static char haystack[4097];
    static char needle[4097];

    printf("%6s %12s\n", "n", "comparisons");
    for (size_t n = 128; n <= 2048; n *= 2) {
        memset(haystack, 'a', n);
        haystack[n] = '\0';
        memset(needle, 'a', n);
        needle[n - 1] = 'b';
        needle[n] = '\0';

        compares = 0;
        const char *hit = counted_strstr(haystack, needle);
        printf("%6lu %12lu  %s\n", (unsigned long)n, compares,
               hit != NULL ? "found" : "not found");
    }
    return 0;
}

zsh - strstr_cost

text

$ gcc -std=c17 -Wall -Wextra -O2 -o strstr_cost strstr_cost.c
$ ./strstr_cost
     n  comparisons
   128         8383  not found
   256        33151  not found
   512       131839  not found
  1024       525823  not found
  2048      2100223  not found

每当测试规模翻倍时，字符比对的累计次数大约呈四倍增长。在工业级标准库中，glibc 在面对长模式串时会自动切换至具备线性时间上界的 Two-Way 算法；关于 KMP、Boyer-Moore 等线性字符串检索算法的理论推演与实现细节，我们会在字符串匹配一章中系统展开。在当前的模块中，mdr_strstr 选择遵循标准的朴素定义，核心目的在于精准落实规格，而非盲目复刻生产级库的高级算法优化。

7. 分词：strtok

作为 C 标准库中最富争议的遗留接口之一，mdr_strtok 承担着依据分隔符集合 delim 将源串切分为若干 Token 词元的任务。在技术契约上，它背负着两处深具破坏性的历史设计包袱：

具有就地破坏性：在切分过程中，源串内部各个词元之间的分隔符会被函数就地覆写为终止空字符 \0。
进度状态被固化在模块级的静态存储期对象中：调用方首次进入时传入待切分的字符串指针，而在后续提取剩余词元时必须传入 NULL，函数完全依赖内部隐藏的静态指针来维系上下文状态。

char *mdr_strtok(char *restrict str, const char *restrict delim) {
    static char *next;
    char *start;
    char *end;

    MDR_ASSERT(delim != NULL);
    if (str != NULL) {
        next = str;
    }
    if (next == NULL) {
        return NULL;
    }
    start = next + mdr_strspn(next, delim);
    if (*start == '\0') {
        next = NULL;
        return NULL;
    }
    end = start + mdr_strcspn(start, delim);
    if (*end != '\0') {
        *end = '\0';
        next = end + 1;
    } else {
        next = NULL;
    }
    return start;
}

在内部实现中，mdr_strspn 负责向前跳过词元开头的连续分隔符，而 mdr_strcspn 则用于快速界定当前词元的边界末尾。如果词元尾部遭遇了分隔符，代码将其就地替换为 \0 并将静态指针 next 推进到其后一字节，为下一次调用做好准备；若尾部已经到达原本的零结尾，说明当前已是整串的最后一个词元，函数将内部状态 next 重置为 NULL。由于前导的连续分隔符会被统一跨越，类似 "a,,b" 的输入只会依次产出 "a" 与 "b" 两个有效切片，中间的空词元会被静默丢弃。这种对空字段的处理策略与 BSD 体系中的 strsep 形成了鲜明对比，我们在 21.5 节会深入讨论。

将解析上下文强行绑定在函数内部的静态对象中，是 strtok 最受诟病的架构缺陷。一旦业务逻辑试图在同一个调用栈或并发线程中同时对两个字符串进行嵌套切分，内层调用就会粗暴地摧毁外层调用遗留的上下文。下面这段模拟按行切分日志、再对每行内容按逗号展开二级切分的测试，直观揭示了这种上下文破坏带来的灾难：

#include "mdr_string.h"
#include <stdio.h>
#include <string.h>

int main(void) {
    const char text[] = "red,green,blue\ncyan,magenta,yellow";
    char copy[sizeof text];
    char *line;
    unsigned long lines = 0;
    unsigned long fields = 0;

    memcpy(copy, text, sizeof text);
    printf("按行切分，再对每一行按逗号切分：\n");
    for (line = mdr_strtok(copy, "\n"); line != NULL;
         line = mdr_strtok(NULL, "\n")) {
        char *field;

        lines++;
        printf("  行 %lu: %s\n", lines, line);
        for (field = mdr_strtok(line, ","); field != NULL;
             field = mdr_strtok(NULL, ",")) {
            fields++;
            printf("    字段: %s\n", field);
        }
    }
    printf("共 %lu 行、%lu 个字段（期望 2 行、6 个字段）\n", lines, fields);
    return 0;
}

两行文本，每行三个字段，期望六行输出。实际只有一行：

zsh - tok

text

$ gcc -std=c17 -Wall -Wextra -Iinclude -o tok tok.c src/mdr_string.c
$ ./tok
按行切分，再对每一行按逗号切分：
  行 1: red,green,blue
    字段: red
    字段: green
    字段: blue
共 1 行、3 个字段（期望 2 行、6 个字段）

在这段测试中，我们原本预期切分出 2 行、共 6 个字段。然而终端输出显示程序仅打印了第 1 行的内容便戛然而止。追踪执行时序可以清晰还原其因果链：外层循环首次切出第一行文本后，内层的循环随即将 line 传入了 mdr_strtok(line, ",")，这瞬间将隐藏在函数内部的静态指针覆写为了第一行内部的偏移；当内层切分完三个逗号字段后，内部静态指针已经停留在第一行末尾；外层循环试图通过 mdr_strtok(NULL, "\n") 提取第二行时，函数在已经被打碎的第一行末尾继续扫描，立刻识别为结束，整个切分流程提前夭折，第二行文本甚至从未获得过被解析的机会！

标准库自身的 strtok 完全共享这套古老机制，直接替换为 <string.h> 得到的结果如出一辙。这种固化在接口签名中的缺陷无法通过调整外部调用次序来弥补，唯一的救赎之道是将切分进度的所有权彻底交还给调用方自己管理：例如 POSIX 标准定义的 strtok_r 接口增加了一个由调用方持有的 saveptr 显式指针，而 strsep 则直接就地更新调用方传入的二级指针。在 21.5 节中，我们将亲手实现这两个现代替代方案，并基于它们彻底解决上述嵌套切分问题。

strtok 的进度存在静态对象里

strtok 在内部用一块静态存储保存下一次从哪里继续，第一次调用传入字符串，之后传空指针。静态存储只有一份，因此同一个程序里不能同时进行两路分词：内层对另一个字符串的调用会覆盖外层的进度。它还会改写输入，把分隔符换成终止空字符。需要同时切分或者保持输入不变时，用把进度放在调用方提供的对象里的版本。

新代码里能用 strtok_r 就别用 strtok，多写一个参数换来可嵌套、可并发；只有一行命令式的简单切分，用 strtok 省事。

8. 测试

当完成上述十二个字符串函数的实现后，tests/test_string.c 中的自动化断言累计增加到了 103 项。测试代码按接口职责划分为若干个文件作用域的 static 测试函数，由 main 入口依次调度执行，最终调用 return check_report("test_string"); 输出汇总报告。

在这些测试套件中，有三类极具方法论价值的测试设计值得单独展开剖析：

第一类是与宿主标准库的差分比对测试。其核心思想是构建一组极具代表性的输入用例，分别喂给我们手写的 mdr_ 版本以及系统自带的 <string.h> 实现，比对两者的输出行为：

/* 与标准库对照：同一组输入分别交给 mdr_ 版本和 <string.h>，比较结果 */
struct find_case {
    const char *haystack;
    const char *needle;
};

static void test_against_libc(void) {
    static const struct find_case spans[] = {
        {"", ""},
        {"abc", ""},
        {"", "abc"},
        {"aabb", "ab"},
        {"12345abc", "0123456789"},
        {"12345abc", "abc"},
        {"hello world", " "},
    };
    static const struct find_case finds[] = {
        {"the cat sat on the mat", "cat"},
        {"the cat sat on the mat", "the"},
        {"the cat sat on the mat", "the m"},
        {"the cat sat on the mat", ""},
        {"the cat sat on the mat", "dog"},
        {"abc", "abcd"},
        {"aaaaab", "aab"},
    };

    for (size_t i = 0; i < sizeof spans / sizeof spans[0]; i++) {
        const char *h = spans[i].haystack;
        const char *n = spans[i].needle;

        CHECK_EQ_SIZE(mdr_strspn(h, n), strspn(h, n));
        CHECK_EQ_SIZE(mdr_strcspn(h, n), strcspn(h, n));
        CHECK(offset_or_neg(h, mdr_strpbrk(h, n)) ==
              offset_or_neg(h, strpbrk(h, n)));
    }
    for (size_t i = 0; i < sizeof finds / sizeof finds[0]; i++) {
        const char *h = finds[i].haystack;
        const char *n = finds[i].needle;

        CHECK(offset_or_neg(h, mdr_strstr(h, n)) == offset_or_neg(h, strstr(h, n)));
    }
}

在用例设计上，spans 数组覆盖了针对集合检索的全部边界，而 finds 数组则专门针对 mdr_strstr 的子串定位逻辑展开检验；其中像 {"", ""} 以及 {"abc", ""} 这样的极值用例，专门用于防范空串检索引发的未定义行为。

需要特别说明的是，在验证结果时，我们比对的是目标字符相对于 haystack 起始地址的物理偏移量，而不是直接比较两个裸指针。这是因为两套函数分别基于独立的数据对象展开运算，返回的指针必定指向不同的物理内存地址，直接用 == 比对指针毫无意义；辅助函数 offset_or_neg 将未命中时的 NULL 统一映射为数值 -1，使得命中位置与失配状态均能被纳入统一的数值断言中。

第二类是全缓冲区哨兵破坏检查。在测试内存与文本复制逻辑时，既要确认目标区域是否正确写入了期望的字符串，更必须严密监视有效写入窗口之外的物理内存是否遭到非法篡改。以 test_strncpy 为例，我们在调用前先将整个 8 字节缓冲区用特定标记字符 '#' 填满，执行截断拷贝之后，逐字节核对第 count 个字节之后的内容是否保持原样未动：

static void test_strncpy(void) {
    char buf[8];

    memset(buf, '#', sizeof buf);
    CHECK(mdr_strncpy(buf, "ab", 4u) == buf);
    CHECK_EQ_SIZE((unsigned char)buf[0], 'a');
    CHECK_EQ_SIZE((unsigned char)buf[1], 'b');
    CHECK_EQ_SIZE((unsigned char)buf[2], 0u);
    CHECK_EQ_SIZE((unsigned char)buf[3], 0u);
    CHECK_EQ_SIZE((unsigned char)buf[4], '#');

    memset(buf, '#', sizeof buf);
    CHECK(mdr_strncpy(buf, "abcdefgh", 4u) == buf);
    CHECK(memcmp(buf, "abcd", 4u) == 0);
    CHECK_EQ_SIZE((unsigned char)buf[4], '#');
}

第三类是表驱动测试（Table-Driven Testing）。在字符检索类接口中，存在大量形如「在给定文本中查找字符 X，期望返回偏移 Y」的参数组合。如果为每个用例都复制粘贴一遍断言宏，会导致测试源码冗长且难以维护；将其结构化提炼为数据驱动的结构体数组，能够大幅精简测试代码，后续新增边界用例时也只需要在静态表中追加一行配置：

struct chr_case {
    int ch;
    int first;
    int last;
};

static void test_strchr(void) {
    static const struct chr_case cases[] = {
        {'b', 0, 0},
        {'a', 1, 5},
        {'n', 2, 4},
        {'z', -1, -1},
    };
    const char text[] = "banana";

    for (size_t i = 0; i < sizeof cases / sizeof cases[0]; i++) {
        CHECK(offset_or_neg(text, mdr_strchr(text, cases[i].ch)) == cases[i].first);
        CHECK(offset_or_neg(text, mdr_strrchr(text, cases[i].ch)) == cases[i].last);
    }

    /* 终止空字符也在查找范围内：strchr 返回指向它的指针 */
    CHECK(mdr_strchr(text, 0) == text + 6);
    CHECK(mdr_strrchr(text, 0) == text + 6);
}

在表项定义中，用 -1 标识查找失败，offset_or_neg 负责将空指针转换为 -1，整个驱动循环的核心逻辑仅需一行断言。当需要扩充测试覆盖时，只需向静态表中追加测试数据行，完全无需触动底层的校验流程。

在完成代码编写后，执行全量构建与单元测试：

zsh - cmake

text

$ cmake --build build
$ ctest --test-dir build -R "^test_string$" --output-on-failure
Test project /home/minsecrus/tutorial/work/p065/mdr/build
    Start 7: test_string
1/1 Test #7: test_string ......................   Passed    0.00 sec

100% tests passed, 0 tests failed out of 1

直接运行测试程序，看每个套件的检查数：

zsh - test_string

text

$ ./build/test_string
test_string: 103 checks, 0 failed

控制台打印的 103 checks 记录了当前测试套件涵盖的全部断言数量，其中 15 个来自 21.1 节搭设的基础框架，其余 88 个则密集分布在本节十二个新增函数的边界测试中。在 Windows 平台的 MinGW-w64 GCC 环境下重新构建，测试用例同样全数绿灯；两套平台虽然在比较函数的具体数值上存在细微分歧，但由于我们的测试断言严格基于正负符号约束，因此套件在不同平台上展现出了稳健的一致性。

在工程验证中，同样需要检验测试套件本身的敏感度：即当代码发生真实回归时，测试必须能够准确报警。如果我们故意将某个断言的期望值篡改，重新执行 CTest，框架会立即输出 tests/test_string.c:行号: 实际表达式 is 实际值, expected 期望值，这一详尽的诊断格式在第 11 章中已有过演示。

在随后的 21.7 节中，我们将把这种比对思想进一步升华并体系化：通过保护页（Guard Page）机制严查单字节越界写、利用十六进制 HexDump 转储失败现场、并结合伪随机输入生成与用例自动缩小算法，构建起一套工业级的差分测试体系。

9. 习题

9.1 巩固

#22121

⚡1⏳2

三段代码都从同一个 8 字节缓冲区开始，memset 先把整个缓冲区填成 '#'（0x23），执行完以后逐字节打印。

unsigned char buf[8];

memset(buf, '#', sizeof buf);
mdr_strncpy((char *)buf, "abc", 4);

memset(buf, '#', sizeof buf);
mdr_strncpy((char *)buf, "abcdef", 4);

memset(buf, '#', sizeof buf);
mdr_strcpy((char *)buf, "ab");
mdr_strncat((char *)buf, "cdef", 2);

(1) 写出每段执行后 8 个字节的十六进制。

(2) 指出哪一段的结果不是字符串，并说明它违反了哪个函数的哪条后置条件。

(3) 第三段里 mdr_strncat 一共写了几个字节，缓冲区里还剩几个 '#'？如果 count 写成 5 而不是 2，结果又是什么？

#22122

⚡2⏳2

不运行程序，写出下面五行各自的输出：mdr_ 开头的三行要求给出具体数值（按正文的实现，返回的是两个字节值之差），memcmp 一行只要求写出符号并说明标准对数值的规定。

char a[3] = {'a', 0, 'b'};
char c[3] = {'a', 0, 'c'};

printf("%d\n", mdr_strncmp(a, c, 3));
printf("%d\n", mdr_strncmp("ab", "abc", 2));
printf("%d\n", mdr_strncmp("ab", "abc", 3));
printf("%d\n", memcmp(a, c, 3));
printf("%d\n", mdr_strcmp("\x80", "a") < 0);

最后一行用 0x80 开头，是为了检验实现有没有按 unsigned char 比较。要求答案里写清两点：mdr_strncmp 在 count 用完之前还会因为什么停下；memcmp 与它的停止条件差在哪里。

#22123

⚡2⏳3

写一个带容量的追加函数，接口如下：

/* 成功时把 src 接到 dst 末尾，返回指向新终止空字符的指针；
 * 空间不够（需要 strlen(dst) + strlen(src) + 1 个字节）时返回 NULL，dst 不变；
 * cap 为 0 时也返回 NULL。 */
char *mdr_append(char *dst, size_t cap, const char *src);

验收：

char buf[16];

strcpy(buf, "ab");
printf("%ld\n", (long)(mdr_append(buf, 6, "cde") - buf));   /* 5 */
printf("%s %lu\n", buf, (unsigned long)strlen(buf));         /* abcde 5 */

strcpy(buf, "ab");
printf("%p\n", (void *)mdr_append(buf, 5, "cde"));           /* 空指针 */
printf("%s\n", buf);                                         /* ab */

用 (long) 与 %ld 打印指针差和长度，避免 %td、%zu 在部分 MinGW 构建里被格式检查误报。

另做两件事：

用 char small[8]; memset(small, '#', sizeof small); 作缓冲区，追加到刚好填满，检查 cap 之后的字节仍是 '#'。
连续追加 "aa"、"bb"、"cc"，每次都用上一次返回的指针。用一个全局计数器在 mdr_append 里累计写入的字节数，打印三次追加的总数；再用每次都从 dst 开头找末尾的 mdr_strcat 做同样的事，对照两个总数，说明省在哪里。

#22124

⚡2⏳3

同一个逗号分隔的行，用两种切法处理。

(1) 用 mdr_strtok 写 size_t split_strtok(char *line, char *fields[], size_t max)，分隔符为 ','。对 "red,,blue" 输出几个字段、分别是什么？

(2) 用 mdr_strspn 与 mdr_strcspn 写 size_t split_keep_empty(char *line, char *fields[], size_t max)，保留空字段（可以把分隔符就地改成 '\0'，也可以只在输出里记下偏移和长度，两种都可以）。对 "red,,blue"、",,x,,"、"" 各输出什么？

(3) 两个版本的差别来自 mdr_strtok 规格里的哪一句话？如果调用方希望输入不被改写，split_keep_empty 该改成什么输出形式？

9.2 编程

#22125

⚡3⏳3

下面这段代码把记录的两个定长字段都填成 '#' 之后写入内容：

struct record {
    char name[8];
    char note[8];
};

static void set_name(struct record *r, const char *src) {
    mdr_strncpy(r->name, src, sizeof r->name);
}

int main(void) {
    struct record r;

    memset(&r, '#', sizeof r);
    set_name(&r, "Christopher");
    mdr_strncpy(r->note, "ok", sizeof r.note);
    printf("name = [%s]\n", r.name);
    printf("note = [%s]\n", r.note);
    return 0;
}

输出是 name = [Christopok]，note 却正常。

(1) 解释 name 为什么一路读到了 note，note 为什么没有同样的问题。

(2) 按固定宽度字段的规格重写：

/* 源短于 cap 时复制并补零到 cap 个字节；源不短于 cap 时复制前 cap 个字节，不写终止空字符。 */
static void set_field(char *dst, size_t cap, const char *src);

用它重跑上面的 main，要求 name 的 8 个字节是 43 68 72 69 73 74 6F 70，note 的 8 个字节是 6F 6B 00 00 00 00 00 00。

(3) 打印时不能依赖终止符。写 static void print_field(const char *p, size_t cap)，用 mdr_strnlen 与 %.*s 打印，要求输出 [Christop][ok]，且对没有终止符的字段也不读到字段之外。

#22126

⚡3⏳2

(1) [2.2] 用 mdr_strstr 写两个函数：count_nonoverlap 每次跳过整个 needle，count_overlap 每次只前进一个字节。对 "aaaa" 找 "aa"、"abababa" 找 "aba"、"abc" 找 "zzz" 分别给出两个结果。needle 为空串时两个函数都返回 0。

(2) [2.2] 用 mdr_strrchr 写 base_name 与 extension：base_name 返回最后一个 '/' 之后的文件名，extension 返回最后一个 '.' 之后的扩展名，最后一个 '/' 之后的点才算是扩展名分隔符。对 /usr/lib、/usr/lib/、file.txt、a/b.c/d 各给出两个结果。

(3) [3.2] 说明这两个函数为什么都依赖「终止空字符也在查找范围内」这一条。如果实现改成遇到终止符就停，extension("file") 与 base_name("/usr/lib") 会分别错在哪里？

#22127

⚡3⏳4

只允许使用 mdr_strspn 与 mdr_strcspn，不许调用 mdr_strtok、mdr_strstr，写：

/* 找到第 index 个单词（以空格或制表符分隔），*off 为它在 line 中的偏移，*len 为长度。
 * 找到返回 1，越界返回 0。不修改 line。 */
int word_at(const char *line, size_t index, size_t *off, size_t *len);

/* 单词个数。 */
size_t count_words(const char *line);

验收（空白包括行首、行尾以及连续多个）：

text

"  alpha\tbeta gamma "   word 0 (2,5)  word 1 (8,4)  word 2 (13,5)  word 3 不存在  count 3
"\t"                     没有单词      count 0
"one"                    word 0 (0,3)  count 1

要求 word_at 只扫描一次到目标位置，不先统计总数、不复制字符串。再说明这段代码在 line 为空指针时会发生什么，为什么规格里要把「line 指向以空字符结尾的字符串」写成前置条件。

#22128

⚡4⏳4

实现 BMH（Boyer-Moore-Horspool）子串查找：

/* 为 needle 建 256 项后缀表：表中每个字节记录「该字节在 needle 最后一位之前
 * 最后一次出现位置到末尾的距离」，没有出现过的字节记为 needle 的长度。
 * 比较从 needle 的最后一个字节开始，失配时按窗口末尾那个字节查表移动。 */
char *mdr_strstr_bmh(const char *haystack, const char *needle);

要求与 mdr_strstr 在下面这组用例上结果一致（比较相对偏移）：{"the cat sat on the mat", "cat"}、{"the cat sat on the mat", "the m"}、{"aaaaab", "aab"}、{"banana", "ana"}、{"abc", ""}。

再统计两种算法在同一个 4096 字节 haystack（全部是 'a'）上的字节比较次数。「朴素版」指正文 mdr_strstr 的写法：先用 mdr_strchr 找 needle[0]，再用 mdr_strncmp 比其余字节；计数只统计 mdr_strncmp 中实际发生的字节比较，mdr_strchr 的扫描不计。

needle 为 31 个 'a' 加一个 'b'。
needle 为 'b' 加 31 个 'a'。

两种 needle 各给出朴素版和 BMH 的数字，并解释两种情况下胜负为什么相反。第二组数说明 BMH 的最坏代价与什么有关，为什么需要 KMP 或 Two-Way 才能保证线性。

9.3 综合与挑战

#22129

⚡5⏳4

mdr_strtok 把进度放在静态对象里，两层切分会互相覆盖。设计一个把进度放在调用方手里的最小接口：

struct slice {
    const char *ptr;
    size_t len;
};

struct scanner {
    const char *p;
    const char *end;
    /* 需要时在这里补成员，例如记录「刚跳过一个分隔符、末尾还欠一个空字段」 */
};

/* 取下一个字段：以 sep 分隔，不修改输入，字段本身可以含除 sep 以外的任意字节。
 * 返回 1 表示取到一个字段，0 表示没有更多。 */
int next_field(struct scanner *sc, char sep, struct slice *out);

约定：相邻分隔符之间产生空字段，末尾分隔符之后还有一个空字段，输入为空时得到 0 个字段。例如 "a;;b;" 得到 a、空、b、空共 4 个字段，"a,b" 得到 2 个。这些约定要能同时成立，scanner 的成员可能不够用。

要求：

用它重跑正文第 7 节的两层切分（"red,green,blue\ncyan,magenta,yellow"），输出 2 行、6 个字段。用 %.*s 打印切片，scanner 需要同时支持 ',' 与 '\n' 两种分隔符。
对 "a;;b;" 得到 4 个字段，第 2 个与第 4 个为空；对 "" 得到 0 个。
写一段说明，列出它与 mdr_strtok 的三点差别（输入是否被改写、状态存在哪里、能否嵌套或并发），并解释为什么「不改写输入」意味着切片必须带长度。
把同样的两层切分改用 mdr_strtok 写一遍，确认只得到 1 行 3 个字段，并指出第二次外层调用拿到的进度是怎么被内层改掉的。

10. 参考资料

cppreference，Null-terminated byte strings（strcpy、strncpy、strcat、strncat、strncmp、strchr、strrchr、strspn、strcspn、strpbrk、strstr、strtok 各页）：https://en.cppreference.com/w/c/string/byte
musl libc，src/string：https://git.musl-libc.org/cgit/musl/tree/src/string
musl libc，strspn.c：https://git.musl-libc.org/cgit/musl/tree/src/string/strspn.c
musl libc，strstr.c：https://git.musl-libc.org/cgit/musl/tree/src/string/strstr.c
Joel Spolsky，Back to Basics：https://www.joelonsoftware.com/2001/12/11/back-to-basics/
Brian W. Kernighan、Dennis M. Ritchie，The C Programming Language，第 2 版，第 5 章，Prentice Hall，ISBN 978-0-13-110362-7。
ISO/IEC 9899:2024 工作草案 N3220，7.26 节 <string.h>：https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3220.pdf

3.10 求值

4.3 选择语句

5.5 跳转语句

10.2 结构体

14.3 程序支持

15.1 声明

16.2 对象表示

18.2 标准库中的宏

21.2 字符串函数 ​

1. 表示与比较规则 ​

2. 复制与连接 ​

strncpy 的后置条件有两种情形

3. 比较 ​

4. 查找单个字符 ​

5. 字符集合 ​

6. 子串查找 ​

7. 分词：strtok ​

strtok 的进度存在静态对象里

8. 测试 ​

9. 习题 ​

9.1 巩固 ​

9.2 编程 ​

9.3 综合与挑战 ​

10. 参考资料 ​

21.2 字符串函数

1. 表示与比较规则

2. 复制与连接

3. 比较

4. 查找单个字符

5. 字符集合

6. 子串查找

7. 分词：strtok

8. 测试

9. 习题

9.1 巩固

9.2 编程

9.3 综合与挑战

10. 参考资料