
就目前而言,在编程领域中,C语言的运用非常之多,它兼顾了高级语言的汇编语言的优点,相较于其它编程语言具有较大优势。 在所有标准C语言<string.h>头文件中声明的字符串处理函数中,最常用的是那些用来复制和连接字符串的函数。这两组函数都将字符从一个对象复制到另一个对象,并且都返回它们的第一个参数:指向目标对象的起始指针。这种返回值的方式是导致函数效率低下的一个原因,而这正是本文要探讨的主题。本文中展示的示例代码仅仅用于说明目的。它们可能包含细微的错误,不应该被视为最佳代码实践。 01标准解决方案 为了执行这个连接操作,除了同时发生的相应地在d上的传递之外,一次在s1的传递和一次在s2上的传递是必须要执行的操作,但是上面的调用在s1上进行了两次传递。让我们把这些调用分成两个语句。 char *d1 = strcpy (d, s1); // pass 1 over s1 strcat (d1, s2); // pass 2 over the copy of s1 in d 因为strcpy返回其第一个参数d的值,所以d1的值与d相同。为简单起见,在后面的示例中我们将使用d,而不是将返回值存储在d1中并使用它。在strcat调用中,我们遍历刚刚复制到d1的字符串以确定最后一个字符的位置,这个成本和第一个字符串s1的长度是线性关系。这个成本乘以每个要连接的字符串。因而最终整个连接操作的成本相当于连接数和所以字符串长度的乘积,趋于一种二次方的关系。这种低效率是如此的臭名昭著,以至于为自己赢得了一个名字:画师施莱米尔算法。(另见http://www.open-std.org/jtc1/sc2 ... 2349.htm#sad-string)必须指出的是,除了效率低下之外,strcat和strcpy还因其缓冲区溢出的问题而臭名昭著,因为它们都对复制字符的数量不做任何限制。 02克服局限性的尝试 d[dsize - 1] = '\0'; // remember to nul-terminate size_t n = strlen (d); // pass 2 over copy of s1 in d strncat (d, s2, dsize - n - 1); // pass 3 over copy of s1 in d注意,与对strncat的调用不同,当s1的长度大于d的大小时,上面对strncpy的调用不会将NUL('\0')结束符追加到d上。它是一个常见的想当然的错误。此外,当s1短于dsize-1时,strncpy函数将所有剩余的字符填满为NUL('\0'),这也被视为一种浪费的,因为随后对strncat的调用将覆盖掉它们。为了避免一些冗余,程序员有时会选择先计算字符串长度,然后使用memcpy,如下所示。这种方法仍然效率不高,而且更容易出错,并且代码难以阅读和维护。size_t s1len = strlen (s1); // pass 1 over s1 if (dsize <= s1len) s1len = dsize - 1; // no need to nul-terminate memcpy (d, s1, s1len); // pass 2 over s1 size_t s2len = strlen (s2); // pass 1 over s2 if (dsize - s1len <= s2len) s2len = dsize - s1len - 1; memcpy (d + s1len, s2, s2len); // pass 2, over s2 d[s1len + s1len] = '\0'; // nul-terminate result 03使用sprintf和snprintf进行连接 04POSIX的stpcpy和stpncpy函数 const char* stpncpy (char* restrict, const char* restrict, size_t); 特别是,在不考虑缓冲区溢出的情况下,可以像下面这样调用stpcpy来连接字符串: stpcpy (stpcpy (d, s1), s2); 然而,当字符串副本必须以目标大小为边界时,等效地使用stpncpy并不会消除将第一个NUL字符之后的剩余目标位置清零并直到边界指定的最大字符位置的开销。char *ret = stpncpy (d, dsize, s1); // zeroes out d beyond the end of s1 dsize -= (ret - d); stpncpy (d, dsize, s2); // again zeroes out d beyond the end 所以,这个函数仍然效率低下,因为对它的每次调用都会将目标中剩余的空间以及复制的字符串的末尾的空间清零。因此,这个操作的复杂性仍然是二次方的。效率低下的严重程度随着目标的大小成比例地增加,而与被连接的字符串的长度成反比增加。 05OpenBSD的strlcpy和strlcat函数 size_t strlcat (char* restrict, const char* restrict, size_t); strncpy和strlcpy函数之间的主要区别在于返回值:前者返回指向目标的指针,后者则返回复制的字符数。另一个区别是strlcpy函数总是在目标中只存储一个NUL结束符。要连接s1和s2,可以按以下方式使用strlcpy函数: size_t n = strlcpy (d, s1, dsize); dsize -= n; d += n; strlcpy (d, s2, dsize); 这使得strlcpy在使用性和简单性方面都可以与snprintf相提并论(当然snprintf的开销虽然恒定,但要大得多)。 除了OpenBSD以外,strlcpy和strlcat函数在其他系统上也可用,包括Solaris和Linux(在BSD兼容库中)。但是由于这些系统不是由POSIX指定的,所以这两个函数在那些系统中并不总是存在。 06POSIX的memccpy函数 这个函数结合了memcpy、memchr的特性以及上面讨论的API的最佳方面的特性。
为了避免缓冲区溢出的风险,需要为每个调用确定适当的大小限制并作为参数提供。因此,像在snprintf(d, dsize, "%s%s", s1, s2)函数中那样限制目标大小的连接调用,可以像下面这样计算目标大小:char *p = memccpy (d, s1, '\0', dsize); dsize -= (p - d - 1); memccpy (p - 1, s2, '\0', dsize); 07选择一个解决方案
{ void *pc = memchr (src, c, n); void *ret; if (pc) { n = (char*)pc - (char*)src + 1; ret = (char*)dst + n; } else ret = 0; memcpy (dst, src, n); return ret; } 这个函数的一个更优化的实现可能如下。 void* memccpy (void* restrict dst, const void* restrict src, int c, size_t n) { const char *s = src; for (char *ret = dst; n; ++ret, ++s, --n) { *ret = *s; if ((unsigned char)*ret == (unsigned char)c) return ret + 1; } return 0; } 借助于memccpy的性能优化,编译器将能够把对snprintf (d, dsize, "%s", s)函数的简单调用转换为对memccpy(d, s, '\0', dsize)的最佳有效调用。通过以代码大小换取速度,激进的优化器甚至可以将符合下列条件的snprintf函数调用(其格式字符串由多个%s指令组成,这些指令中间穿插有普通字符,如%s/%s)转换成一系列的此类memccpy函数调用:如下所示 char *p = memccpy (d, s1, '\0', dsize); if (p) { --p; p = memccpy (p, "/", '\0', dsize - (p - d)); if (p) { --p; p = memccpy (p, s2, '\0', dsize - (p - d)); } } if (!p) d[dsize - 1] = '\0'; 082019年4月WG14会议后的更新 |