Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

1. 字符串操作函数

程序按功能划分可分为数值运算、符号处理和 I/O 操作三类，符号处理程序占相当大的比例，符号处理程序无处不在，编译器、浏览器、Office 套件等程序的主要功能都是符号处理。无论多复杂的符号处理都是由各种基本的字符串操作组成的，本节介绍如何用 C 语言的库函数做字符串初始化、取长度、拷贝、连接、比较、搜索等基本操作。

1.1. 初始化字符串

#include <string.h>

void *memset(void *s, int c, size_t n);
返回值：s 指向哪，返回的指针就指向哪

memset 函数把s 所指的内存地址开始的n 个字节都填充为c 的值。通常c 的值为 0，把一块内存区清零。例如定义char buf[10]; ，如果它是全局变量或静态变量，则自动初始化为 0（位于.bss 段），如果它是函数的局部变量，则初值不确定，可以用memset(buf, 0, 10) 清零，由malloc 分配的内存初值也是不确定的，也可以用memset 清零。

1.2. 取字符串的长度

#include <string.h>

size_t strlen(const char *s);
返回值：字符串的长度

strlen 函数返回s 所指的字符串的长度。该函数从s 所指的第一个字符开始找'\0' 字符，一旦找到就返回，返回的长度不包括'\0' 字符在内。例如定义char buf[] = "hello"; ，则strlen(buf) 的值是 5，但要注意，如果定义char buf[5] = "hello"; ，则调用strlen(buf) 是危险的，会造成数组访问越界。

1.3. 拷贝字符串

在第 1 节 “本章的预备知识”中介绍了 strcpy 和 strncpy 函数，拷贝以 '\0' 结尾的字符串， strncpy 还带一个参数指定最多拷贝多少个字节，此外， strncpy 并不保证缓冲区以 '\0' 结尾。现在介绍 memcpy 和 memmove 函数。

#include <string.h>

void *memcpy(void *dest, const void *src, size_t n);
void *memmove(void *dest, const void *src, size_t n);
返回值：dest 指向哪，返回的指针就指向哪

memcpy 函数从src 所指的内存地址拷贝n 个字节到dest 所指的内存地址，和strncpy 不同，memcpy 并不是遇到'\0' 就结束，而是一定会拷贝完n 个字节。这里的命名规律是，以str 开头的函数处理以'\0' 结尾的字符串，而以mem 开头的函数则不关心'\0' 字符，或者说这些函数并不把参数当字符串看待，因此参数的指针类型是void * 而非char * 。

memmove 也是从src 所指的内存地址拷贝n 个字节到dest 所指的内存地址，虽然叫 move 但其实也是拷贝而非移动。但是和memcpy 有一点不同，memcpy 的两个参数src 和dest 所指的内存区间如果重叠则无法保证正确拷贝，而memmove 却可以正确拷贝。假设定义了一个数组char buf[20] = "hello world\n"; ，如果想把其中的字符串往后移动一个字节（变成"hhello world\n" ），调用memcpy(buf + 1, buf, 13) 是无法保证正确拷贝的：

例 25.1. 错误的 memcpy 调用

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

int main(void)
{
	char buf[20] = "hello world\n";
	memcpy(buf + 1, buf, 13);
	printf(buf);
	return 0;
}

在我的机器上运行的结果是 hhhllooworrd 。如果把代码中的 memcpy 改成 memmove 则可以保证正确拷贝。 memmove 可以这样实现：

void *memmove(void *dest, const void *src, size_t n)
{
	char temp[n];
	int i;
	char *d = dest;
	const char *s = src;

	for (i = 0; i < n; i++)
		temp[i] = s[i];
	for (i = 0; i < n; i++)
		d[i] = temp[i];

	return dest;
}

借助于一个临时缓冲区 temp ，即使 src 和 dest 所指的内存区间有重叠也能正确拷贝。思考一下，如果不借助于临时缓冲区能不能正确处理重叠内存区间的拷贝？

用 memcpy 如果得到的结果是 hhhhhhhhhhhhhh 倒不奇怪，可为什么会得到 hhhllooworrd 这个奇怪的结果呢？根据这个结果猜测的一种可能的实现是：

void *memcpy(void *dest, const void *src, size_t n)
{
	char *d = dest;
	const char *s = src;
	int *di;
	const int *si;
	int r = n % 4;
	while (r--)
		*d++ = *s++;
	di = (int *)d;
	si = (const int *)s;
	n /= 4;
	while (n--)
		*di++ = *si++;

	return dest;
}

在 32 位的 x86 平台上，每次拷贝 1 个字节需要一条指令，每次拷贝 4 个字节也只需要一条指令， memcpy 函数的实现尽可能 4 个字节 4 个字节地拷贝，因而得到上述结果。

C99 的 restrict 关键字

我们来看一个跟 memcpy / memmove 类似的问题。下面的函数将两个数组中对应的元素相加，结果保存在第三个数组中。

void vector_add(const double *x, const double *y, double *result)
{
	int i;
	for (i = 0; i < 64; ++i)
		result[i] = x[i] + y[i];
}

如果这个函数要在多处理器的计算机上执行，编译器可以做这样的优化：把这一个循环拆成两个循环，一个处理器计算 i 值从 0 到 31 的循环，另一个处理器计算 i 值从 32 到 63 的循环，这样两个处理器可以同时工作，使计算时间缩短一半。但是这样的编译优化能保证得出正确结果吗？假如 result 和 x 所指的内存区间是重叠的， result[0] 其实是 x[1] ， result[i] 其实是 x[i+1] ，这两个处理器就不能各干各的事情了，因为第二个处理器的工作依赖于第一个处理器的最终计算结果，这种情况下编译优化的结果是错的。这样看来编译器是不敢随便做优化了，那么多处理器提供的并行性就无法利用，岂不可惜？为此，C99 引入 restrict 关键字，如果程序员把上面的函数声明为 void vector_add(const double *restrict x, const double *restrict y, double *restrict result) ，就是告诉编译器可以放心地对这个函数做优化，程序员自己会保证这些指针所指的内存区间互不重叠。

由于 restrict 是 C99 引入的新关键字，目前 Linux 的 Man Page 还没有更新，所以都没有 restrict 关键字，本书的函数原型都取自 Man Page，所以也都没有 restrict 关键字。但在 C99 标准中库函数的原型都在必要的地方加了 restrict 关键字，在 C99 中 memcpy 的原型是 void *memcpy(void * restrict s1, const void * restrict s2, size_t n); ，就是告诉调用者，这个函数的实现可能会做些优化，编译器也可能会做些优化，传进来的指针不允许指向重叠的内存区间，否则结果可能是错的，而 memmove 的原型是 void *memmove(void *s1, const void *s2, size_t n); ，没有 restrict 关键字，说明传给这个函数的指针允许指向重叠的内存区间。在 restrict 关键字出现之前都是用自然语言描述哪些函数的参数不允许指向重叠的内存区间，例如在 C89 标准的库函数一章开头提到，本章描述的所有函数，除非特别说明，都不应该接收两个指针参数指向重叠的内存区间，例如调用 sprintf 时传进来的格式化字符串和结果字符串的首地址相同，诸如此类的调用都是非法的。本书也遵循这一惯例，除非像 memmove 这样特别说明之外，都表示“不允许”。

关于 restrict 关键字更详细的解释可以参考[BeganFORTRAN]。

字符串的拷贝也可以用 strdup(3) 函数，这个函数不属于 C 标准库，是 POSIX 标准中定义的，POSIX 标准定义了 UNIX 系统的各种接口，包含 C 标准库的所有函数和很多其它的系统函数，在第 2 节 “C 标准 I/O 库函数与 Unbuffered I/O 函数”将详细介绍 POSIX 标准。

#include <string.h>

char *strdup(const char *s);
返回值：指向新分配的字符串

这个函数调用 malloc 动态分配内存，把字符串 s 拷贝到新分配的内存中然后返回。用这个函数省去了事先为新字符串分配内存的麻烦，但是用完之后要记得调用 free 释放新字符串的内存。

1.4. 连接字符串

#include <string.h>

char *strcat(char *dest, const char *src);
char *strncat(char *dest, const char *src, size_t n);
返回值：dest 指向哪，返回的指针就指向哪

strcat 把src 所指的字符串连接到dest 所指的字符串后面，例如：

char d[10] = "foo";
char s[10] = "bar";
strcat(d, s);
printf("%s %s\n", d, s);

调用 strcat 函数后，缓冲区 s 的内容没变，缓冲区 d 中保存着字符串 "foobar" ，注意原来 "foo" 后面的 '\0' 被连接上来的字符串 "bar" 覆盖掉了， "bar" 后面的 '\0' 仍保留。

strcat 和strcpy 有同样的问题，调用者必须确保dest 缓冲区足够大，否则会导致缓冲区溢出错误。strncat 函数通过参数n 指定一个长度，就可以避免缓冲区溢出错误。注意这个参数n 的含义和strncpy 的参数n 不同，它并不是缓冲区dest 的长度，而是表示最多从src 缓冲区中取n 个字符（不包括结尾的'\0' ）连接到dest 后面。如果src 中前n 个字符没有出现'\0' ，则取前n 个字符再加一个'\0' 连接到dest 后面，所以strncat 总是保证dest 缓冲区以'\0' 结尾，这一点又和strncpy 不同，strncpy 并不保证dest 缓冲区以'\0' 结尾。所以，提供给strncat 函数的dest 缓冲区的大小至少应该是strlen(dest)+n+1 个字节，才能保证不溢出。

1.5. 比较字符串

#include <string.h>

int memcmp(const void *s1, const void *s2, size_t n);
int strcmp(const char *s1, const char *s2);
int strncmp(const char *s1, const char *s2, size_t n);
返回值：负值表示 s1 小于 s2，0 表示 s1 等于 s2，正值表示 s1 大于 s2

memcmp 从前到后逐个比较缓冲区s1 和s2 的前n 个字节（不管里面有没有'\0' ），如果s1 和s2 的前n 个字节全都一样就返回 0，如果遇到不一样的字节，s1 的字节比s2 小就返回负值，s1 的字节比s2 大就返回正值。

strcmp 把s1 和s2 当字符串比较，在其中一个字符串中遇到'\0' 时结束，按照上面的比较准则，"ABC" 比"abc" 小，"ABCD" 比"ABC" 大，"123A9" 比"123B2" 小。

strncmp 的比较结束条件是：要么在其中一个字符串中遇到'\0' 结束（类似于strcmp ），要么比较完n 个字符结束（类似于memcmp ）。例如，strncmp("ABCD", "ABC", 3) 的返回值是 0，strncmp("ABCD", "ABC", 4) 的返回值是正值。

#include <strings.h>

int strcasecmp(const char *s1, const char *s2);
int strncasecmp(const char *s1, const char *s2, size_t n);
返回值：负值表示 s1 小于 s2，0 表示 s1 等于 s2，正值表示 s1 大于 s2

这两个函数和 strcmp / strncmp 类似，但在比较过程中忽略大小写，大写字母 A 和小写字母 a 认为是相等的。这两个函数不属于 C 标准库，是 POSIX 标准中定义的。

1.6. 搜索字符串

#include <string.h>

char *strchr(const char *s, int c);
char *strrchr(const char *s, int c);
返回值：如果找到字符 c，返回字符串 s 中指向字符 c 的指针，如果找不到就返回 NULL

strchr 在字符串s 中从前到后查找字符c ，找到字符c 第一次出现的位置时就返回，返回值指向这个位置，如果找不到字符c 就返回NULL 。strrchr 和strchr 类似，但是从右向左找字符c ，找到字符c 第一次出现的位置就返回，函数名中间多了一个字母 r 可以理解为 Right-to-left。

#include <string.h>

char *strstr(const char *haystack, const char *needle);
返回值：如果找到子串，返回值指向子串的开头，如果找不到就返回 NULL

strstr 在一个长字符串中从前到后找一个子串（Substring），找到子串第一次出现的位置就返回，返回值指向子串的开头，如果找不到就返回 NULL。这两个参数名很形象，在干草堆haystack 中找一根针needle ，按中文的说法叫大海捞针，显然haystack 是长字符串，needle 是要找的子串。

搜索子串有一个显而易见的算法，可以用两层的循环，外层循环把 haystack 中的每一个字符的位置依次假定为子串的开头，内层循环从这个位置开始逐个比较 haystack 和 needle 的每个字符是否相同。想想这个算法最多需要做多少次比较？其实有比这个算法高效得多的算法，有兴趣的读者可以参考[算法导论]。

1.7. 分割字符串

很多文件格式或协议格式中会规定一些分隔符或者叫界定符（Delimiter），例如 /etc/passwd 文件中保存着系统的帐号信息：

$ cat /etc/passwd
root:x:0:0:root:/root:/bin/bash
daemon:x:1:1:daemon:/usr/sbin:/bin/sh
bin:x:2:2:bin:/bin:/bin/sh
...

每条记录占一行，也就是说记录之间的分隔符是换行符，每条记录又由若干个字段组成，这些字段包括用户名、密码、用户 id、组 id、个人信息、主目录、登录 Shell，字段之间的分隔符是:号。解析这样的字符串需要根据分隔符把字符串分割成几段，C 标准库提供的 strtok 函数可以很方便地完成分割字符串的操作。tok 是 Token 的缩写，分割出来的每一段字符串称为一个 Token。

#include <string.h>

char *strtok(char *str, const char *delim);
char *strtok_r(char *str, const char *delim, char **saveptr);
返回值：返回指向下一个 Token 的指针，如果没有下一个 Token 了就返回 NULL

参数 str 是待分割的字符串， delim 是分隔符，可以指定一个或多个分隔符， strtok 遇到其中任何一个分隔符就会分割字符串。看下面的例子。

例 25.2. strtok

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

int main(void)
{
	char str[] = "root:x::0:root:/root:/bin/bash:";
	char *token;

	token = strtok(str, ":");
	printf("%s\n", token);
	while ( (token = strtok(NULL, ":")) != NULL)
		printf("%s\n", token);

	return 0;
}

$ ./a.out
root
x
0
root
/root
/bin/bash

结合这个例子， strtok 的行为可以这样理解：冒号是分隔符，把 "root:x::0:root:/root:/bin/bash:" 这个字符串分隔成 "root" 、 "x" 、 "" 、 "0" 、 "root" 、 "/root" 、 "/bin/bash" 、 "" 等几个 Token，但空字符串的 Token 被忽略。第一次调用要把字符串首地址传给 strtok 的第一个参数，以后每次调用第一个参数只要传 NULL 就可以了， strtok 函数自己会记住上次处理到字符串的什么位置（显然这是通过 strtok 函数中的一个静态指针变量记住的）。

用 gdb 跟踪这个程序，会发现 str 字符串被 strtok 不断修改，每次调用 strtok 把 str 中的一个分隔符改成 '\0' ，分割出一个小字符串，并返回这个小字符串的首地址。

(gdb) start
Breakpoint 1 at 0x8048415: file main.c, line 5.
Starting program: /home/akaedu/a.out
main () at main.c:5
5	{
(gdb) n
6		char str[] = "root:x::0:root:/root:/bin/bash:";
(gdb)
9		token = strtok(str, ":");
(gdb) display str
1: str = "root:x::0:root:/root:/bin/bash:"
(gdb) n
10		printf("%s\n", token);
1: str = "root\000x::0:root:/root:/bin/bash:"
(gdb)
root
11		while ( (token = strtok(NULL, ":")) != NULL)
1: str = "root\000x::0:root:/root:/bin/bash:"
(gdb)
12			printf("%s\n", token);
1: str = "root\000x\000:0:root:/root:/bin/bash:"
(gdb)
x
11		while ( (token = strtok(NULL, ":")) != NULL)
1: str = "root\000x\000:0:root:/root:/bin/bash:"

刚才提到在 strtok 函数中应该有一个静态指针变量记住上次处理到字符串中的什么位置，所以不需要每次调用时都把字符串中的当前处理位置传给 strtok ，但是在函数中使用静态变量是不好的，以后会讲到这样的函数是不可重入的。 strtok_r 函数则不存在这个问题，它的内部没有静态变量，调用者需要自己分配一个指针变量来维护字符串中的当前处理位置，每次调用时把这个指针变量的地址传给 strtok_r 的第三个参数，告诉 strtok_r 从哪里开始处理， strtok_r 返回时再把新的处理位置写回到这个指针变量中（这是一个 Value-result 参数）。 strtok_r 末尾的 r 就表示可重入（Reentrant），这个函数不属于 C 标准库，是在 POSIX 标准中定义的。关于 strtok_r 的用法 Man Page 上有一个很好的例子：

例 25.3. strtok_r

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

int main(int argc, char *argv[])
{
	char *str1, *str2, *token, *subtoken;
	char *saveptr1, *saveptr2;
	int j;

	if (argc != 4) {
		fprintf(stderr, "Usage: %s string delim subdelim\n",
			argv[0]);
		exit(EXIT_FAILURE);
	}

	for (j = 1, str1 = argv[1]; ; j++, str1 = NULL) {
		token = strtok_r(str1, argv[2], &saveptr1);
		if (token == NULL)
			break;
		printf("%d: %s\n", j, token);

		for (str2 = token; ; str2 = NULL) {
			subtoken = strtok_r(str2, argv[3], &saveptr2);
			if (subtoken == NULL)
				break;
			printf(" --> %s\n", subtoken);
		}
	}

	exit(EXIT_SUCCESS);
}

$ ./a.out 'a/bbb///cc;xxx:yyy:' ':;' '/'
1: a/bbb///cc
 --> a
 --> bbb
 --> cc
2: xxx
 --> xxx
3: yyy
 --> yyy

a/bbb///cc;xxx:yyy: 这个字符串有两级分隔符，一级分隔符是:号或;号，把这个字符串分割成a/bbb///cc 、xxx 、yyy 三个子串，二级分隔符是/，只有第一个子串中有二级分隔符，它被进一步分割成a 、bbb 、cc 三个子串。由于strtok_r 不使用静态变量，而是要求调用者自己保存字符串的当前处理位置，所以这个例子可以在按一级分隔符分割整个字符串的过程中穿插着用二级分隔符分割其中的每个子串。建议读者用gdb 的display 命令跟踪argv[1] 、saveptr1 和saveptr2 ，以理解strtok_r 函数的工作方式。

Man Page 的BUGS部分指出了用 strtok 和 strtok_r 函数需要注意的问题：

  • 这两个函数要改写字符串以达到分割的效果

  • 这两个函数不能用于常量字符串，因为试图改写 .rodata 段会产生段错误

  • 在做了分割之后，字符串中的分隔符就被 '\0' 覆盖了

  • strtok 函数使用了静态变量，它不是线程安全的，必要时应该用可重入的strtok_r 函数，以后再详细介绍“可重入”和“线程安全”这两个概念

习题

1、出于练习的目的， strtok 和 strtok_r 函数非常值得自己动手实现一遍，在这个过程中不仅可以更深刻地理解这两个函数的工作原理，也为以后理解“可重入”和“线程安全”这两个重要概念打下基础。

2、解析 URL 中的路径和查询字符串。动态网页的 URL 末尾通常带有查询，例如：

http://www.google.cn/search?complete=1&hl=zh-CN&ie=GB2312&q=linux&meta=
http://www.baidu.com/s?wd=linux&cl=3

比如上面第一个例子， http://www.google.cn/search 是路径部分，?号后面的 complete=1&hl=zh-CN&ie=GB2312&q=linux&meta= 是查询字符串，由五个“key=value”形式的键值对（Key-value Pair）组成，以&隔开，有些键对应的值可能是空字符串，比如这个例子中的键 meta 。

现在要求实现一个函数，传入一个带查询字符串的 URL，首先检查输入格式的合法性，然后对 URL 进行切分，将路径部分和各键值对分别传出，请仔细设计函数接口以便传出这些字符串。如果函数中有动态分配内存的操作，还要另外实现一个释放内存的函数。完成之后，为自己设计的函数写一个 Man Page。