学步园

    3、字符串复制strcpy,strncpy,wcscpy,wcsncpy：将字符串src（或其前n个字符）复制到dest中，覆盖dest的内容。实现中先检查指针是否越界，计算指针dest到src的偏移，然后开始做复制操作，复制到dest的开始位置处，以覆盖dest的内容。对strncpy，也采用了每4个字符作为一组来进行复制的方法，以加快复制速度。

/* strcpy.c：strcpy函数的实现 */<br /> #include <stddef.h> /* 用到了ptrdiff_t */<br /> #include <string.h><br /> #include <memcopy.h><br /> #include <bp-checks.h> /* 定义了CHECK_BOUNDS_LOW和CHECK_BOUNDS_HIGH */<br /> #undef strcpy<br /> /* 将SRC复制到DEST中，覆盖DEST原先的内容 */<br /> char *<br /> strcpy (dest, src)<br /> char *dest;<br /> const char *src;<br /> {<br /> reg_char c;<br /> /* 检查指针src的值是否 >= low，返回原来的指针值 */<br /> char *__unbounded s = (char *__unbounded) CHECK_BOUNDS_LOW (src);<br /> /* 计算出目的地dest到s的偏移 */<br /> const ptrdiff_t off = CHECK_BOUNDS_LOW (dest) - s - 1;<br /> size_t n;<br /> do<br /> {<br /> c = *s++; /* 把src中每个字符复制到目的地，覆盖了dest中的内容 */<br /> s[off] = c;<br /> }<br /> while (c != '/0');<br /> n = s - src;<br /> (void) CHECK_BOUNDS_HIGH (src + n); /* 检查指针src+n的值是否 < high，返回原来的指针值 */<br /> (void) CHECK_BOUNDS_HIGH (dest + n);<br /> return dest;<br /> }<br /> libc_hidden_builtin_def (strcpy)

/* strncpy.c：strncpy函数的实现 */<br /> #include <string.h><br /> #include <memcopy.h><br /> #undef strncpy<br /> /* 将s2的前n个字符复制到s1中，覆盖s1原先的内容，若s2不中n个字符，<br /> 则填充null字符，直到写入n个字符 */<br /> char *<br /> strncpy (s1, s2, n)<br /> char *s1;<br /> const char *s2;<br /> size_t n;<br /> {<br /> reg_char c;<br /> char *s = s1;<br /> --s1; /* 指向首字符的前一个字符 */<br /> if (n >= 4) /* 做复制操作，每4个字符作为一组来进行复制 */<br /> {<br /> size_t n4 = n >> 2; /* 让n除以4，计算出循环次数 */<br /> for (;;) /* 每次循环都复制4个字符，总共复制了4*n4个字符 */<br /> {<br /> c = *s2++;<br /> *++s1 = c;<br /> if (c == '/0') /* s2不足n个字符时，复制完毕，退出循环 */<br /> break;<br /> c = *s2++;<br /> *++s1 = c;<br /> if (c == '/0')<br /> break;<br /> c = *s2++;<br /> *++s1 = c;<br /> if (c == '/0')<br /> break;<br /> c = *s2++;<br /> *++s1 = c;<br /> if (c == '/0')<br /> break;<br /> if (--n4 == 0)<br /> goto last_chars; /* 循环终止，要对剩下的几个字符（不超过3个）进行复制 */<br /> }<br /> n = n - (s1 - s) - 1;<br /> if (n == 0) /* 若s1恰好到达s的终止符的前一个字符处 */<br /> return s; /* 说明s与s2长度相等，均为n，复制操作恰好用s2覆盖了s，终止符没有覆盖，直接返回s */<br /> goto zero_fill; /* 否则s1没有到达s的末尾，说明s2不足n个字符，需要在s1末尾填充null字符，直到写入n个字符 */<br /> }<br /> last_chars:<br /> n &= 3; /* 求出n除以4的余数 */<br /> if (n == 0) /* 余数为0说明没有剩余的未复制的字符，直接返回s */<br /> return s;<br /> do /* 对剩下的几个字符（最多3个）进行复制 */<br /> {<br /> c = *s2++;<br /> *++s1 = c;<br /> if (--n == 0)<br /> return s;<br /> }<br /> while (c != '/0');<br /> zero_fill:<br /> do<br /> *++s1 = '/0'; /* 在s1末尾填充null字符，直到写入n个字符 */<br /> while (--n > 0);<br /> return s;<br /> }<br /> libc_hidden_builtin_def (strncpy)

    4、字符串求长strlen,wcslen：返回str中终止符'/0'之前的字符个数。这里通过把指针移到终止符处，然后计算该指针与开始处指针的差值来获取字符串的长度。为了加快移动速度，实现中把const char*型指针char_ptr转换成了unsigned long*型指针longword_ptr，这样一次就可以移动4个字节。算法关键是要辨别出longword_ptr指向的值（有4个字节）中有一个字节为0（它表示字符'/0'），这说明指针到达了终止符'/0'处，要停止移动，并转换回const char*型指针，计算指针之间的差值。

/* strlen.c：strlen函数的实现 */<br /> #include <string.h><br /> #include <stdlib.h> /* 用到abort()函数 */<br /> #undef strlen<br /> /* 返回以null终止的字符串str的长度。通过一次测试4个字节来迅速的扫描到null终止符 */<br /> size_t<br /> strlen (str)<br /> const char *str;<br /> {<br /> const char *char_ptr;<br /> const unsigned long int *longword_ptr;<br /> unsigned long int longword, magic_bits, himagic, lomagic;<br /> /* 通过一次读取一个字符来处理开头的几个字符，直到char_ptr中的值对齐到一个long型字的边界，<br /> 即直到char_ptr中的值是long的字节数（通常为4）的倍数 */<br /> for (char_ptr = str; ((unsigned long int) char_ptr<br /> & (sizeof (longword) - 1)) != 0;<br /> ++char_ptr)<br /> if (*char_ptr == '/0') /* 若到达null终止符，则直接返回长度 */<br /> return char_ptr - str;<br /> /* 所有这些说明性的注释使用4字节的long型字，但本算法同样也可以应用于8字节的long型字 */</p> <p> longword_ptr = (unsigned long int *) char_ptr;<br /> /* magic_bits的第8,16,24,31位为0，称这些位为“洞”。注意每个字节的左边有一个洞，<br /> 在最后的位置上也有一个洞。<br /> bits: 01111110 11111110 11111110 11111111<br /> 比特1确保进位能传播到后面的比特0上，比特0则提供洞，以便让进位陷进去 */<br /> magic_bits = 0x7efefeffL;<br /> himagic = 0x80808080L; /* 高位魔数，即第7,15,23,31位上为1 */<br /> lomagic = 0x01010101L; /* 低位魔数，即第0,8,16,24位上为1 */<br /> if (sizeof (longword) > 4) /* 64位的平台上 */<br /> {<br /> /* 魔数的64位版本 */<br /> /* 移位操作分两步，以避免当long为32位时出现警告 */<br /> /* 位数的第8,16,24,32,40,48,56,63位上为0 */<br /> magic_bits = ((0x7efefefeL << 16) << 16) | 0xfefefeffL;<br /> himagic = ((himagic << 16) << 16) | himagic; /* 第7,15,23,31,39,47,55,63位上为1 */<br /> lomagic = ((lomagic << 16) << 16) | lomagic; /* 第0,8,16,24,32,40,48,56位上为0 */<br /> }<br /> if (sizeof (longword) > 8) /* long类型大于8字节则终止程序 */<br /> abort ();<br /> /* 这里我们不使用传统的对每个字符都进行测试的循环，而是一次测试一个long型字。技巧性的部分<br /> 是测试当前long型字的各个字节是否为0 */<br /> for (;;)<br /> {<br /> longword = *longword_ptr++;<br /> if (<br /> #if 0<br /> /* 让longword加上魔数magic_bits */<br /> (((longword + magic_bits)<br /> /* 设置那些通过加法而未改变的位 */<br /> ^ ~longword)</p> <p> /* 只需看这些洞。如果任何的洞位都没有改变，最有可能的是有一个字节值为0 */<br /> & ~magic_bits)<br /> #else<br /> ((longword - lomagic) & himagic)<br /> #endif<br /> != 0)<br /> {<br /> /* 长整型字的哪个字节为0？如果都不为0，则是一个非预期情况，继续搜索 */<br /> const char *cp = (const char *) (longword_ptr - 1);<br /> if (cp[0] == 0)<br /> return cp - str;<br /> if (cp[1] == 0)<br /> return cp - str + 1;<br /> if (cp[2] == 0)<br /> return cp - str + 2;<br /> if (cp[3] == 0)<br /> return cp - str + 3;<br /> if (sizeof (longword) > 4) /* 如果long类型是8个字节，则还有4个字节需要判断 */<br /> {<br /> if (cp[4] == 0)<br /> return cp - str + 4;<br /> if (cp[5] == 0)<br /> return cp - str + 5;<br /> if (cp[6] == 0)<br /> return cp - str + 6;<br /> if (cp[7] == 0)<br /> return cp - str + 7;<br /> }<br /> }<br /> }<br /> }<br /> libc_hidden_builtin_def (strlen)

    解释：
    （1）先移动char_ptr，使其值对齐到长整型字的边界，即移动到使char_ptr中的值是4的倍数为止。在对齐过程中若到达了终止符处，则直接返回与开始处的指针str的差值。
    （2）对longword_ptr指针进行移动时，指针指向的值为longword。为了判断指针是否到达终止符，算法实现使用了两个魔数lomagic和himagic，lomagic各个字节的最低位为1，其余位均为0；himagic各个字节的最高位为1，其余位均为0。看表达式(longword - lomagic) & himagic，若longword中有一个字节为00000000，则减00000001时要向高字节借一位，得到11111111或11111110（当借了一位给更低的字节时），与10000000做“与”运算后变成10000000，这时表达式的结果必定不为0。可见，只有在表达式结果不等于0时，longword中才有可能有终止符。因此，在移动过程中，一旦表达式结果不等于0，只要逐一检查一下每个字节，看哪个为0，这时就到达终止符，计算指针差值并返回。若都不为0，则继续移动。
    （3）也可以只用一个魔数magic_bits来实现，即代码中用#if 0注释掉的那部分，它可以达到同样的效果。看表达式((longword + magic_bits) ^ ~longword) & ~magic_bits，最后的“与”运算会使结果的其他位清零，只留下那4个洞位，因此我们只要看longword的洞位的变化即可。若longword中有一个字节为0，则做加法后它不可能向高字节（即左侧字节）进位，左侧字节的洞位没有改变（因为magic_bits的对应洞位为0，加上0而又没有低字节的进位，因此不会改变）。做异或运算后，必定使这个洞位变成1，因此表达式的结果必定不为0。可见，这跟（2）用两个魔数实现的效果是一样的。
    5、字符搜索strchr,strrchr,wcschr,wcsrchr：在字符串s中查找字符c的第一次（或最后一次）出现，若没找到则返回NULL指针。算法实现与strlen类似，只不过在strlen是搜索到终止符'/0'为止，这里是搜索到字符c为止。

/* strchr.c：strchr函数的实现 */<br /> #include <string.h><br /> #include <memcopy.h> /* 非标准头文件，要用到reg_char类型 */<br /> #include <stdlib.h> /* 要用到abort() */<br /> #undef strchr<br /> /* 在S中查找C的第一次出现，如果没有找到，则返回NULL指针 */<br /> char *<br /> strchr (s, c_in)<br /> const char *s;<br /> int c_in;<br /> {<br /> const unsigned char *char_ptr;<br /> const unsigned long int *longword_ptr;<br /> unsigned long int longword, magic_bits, charmask;<br /> unsigned reg_char c;<br /> c = (unsigned char) c_in;<br /> /* 通过一次读取一个字符来处理开头的几个字符，直到char_ptr中的值对齐到一个long型字的边界，<br /> 即直到char_ptr中的值是long的字节数（通常为4）的倍数 */<br /> for (char_ptr = (const unsigned char *) s;<br /> ((unsigned long int) char_ptr & (sizeof (longword) - 1)) != 0;<br /> ++char_ptr)<br /> if (*char_ptr == c) /* 若到达字符c处，则直接返回其指针 */<br /> return (void *) char_ptr;<br /> else if (*char_ptr == '/0') /* 没找到c则返回NULL */<br /> return NULL;<br /> /* 所有这些说明性的注释使用4字节的long型字，但本算法同样也可以应用于8字节的long型字 */<br /> longword_ptr = (unsigned long int *) char_ptr;<br /> /* magic_bits的第8,16,24,31位为0，称这些位为“洞”。注意每个字节的左边有一个洞，<br /> 在最后的位置上也有一个洞。<br /> bits: 01111110 11111110 11111110 11111111<br /> 比特1确保进位能传播到后面的比特0上，比特0则提供洞，以便让进位陷进去 */<br /> switch (sizeof (longword))<br /> {<br /> case 4: magic_bits = 0x7efefeffL; break;<br /> case 8: magic_bits = ((0x7efefefeL << 16) << 16) | 0xfefefeffL; break;<br /> default:<br /> abort ();<br /> }<br /> /* 设置一个长整型字，其每个字节都是字符c */<br /> charmask = c | (c << 8);<br /> charmask |= charmask << 16;<br /> if (sizeof (longword) > 4)<br /> /* 移位操作分两步，以避免当long为32位时出现警告 */<br /> charmask |= (charmask << 16) << 16;<br /> if (sizeof (longword) > 8)<br /> abort (); /* long类型大于8字节则终止程序 */<br /> /* 这里我们不使用传统的对每个字符都进行测试的循环，而是一次测试一个long型字。技巧性的部分<br /> 是测试当前long型字的各个字节是否为0 */<br /> for (;;)<br /> {<br /> longword = *longword_ptr++;<br /> /* 让longword加上魔数magic_bits */<br /> if ((((longword + magic_bits)<br /> /* 设置那些通过加法而未改变的位 */<br /> ^ ~longword)<br /> /* 只需看这些洞。如果任何的洞位都没有改变，最有可能的是有一个字节值为0 */<br /> & ~magic_bits) != 0 ||<br /> /* 捕捉到值为0的字节后，测试字中是否含有字符c */<br /> ((((longword ^ charmask) + magic_bits) ^ ~(longword ^ charmask))<br /> & ~magic_bits) != 0)<br /> {<br /> /* 长整型字的哪个字节为C或0？如果都不是，则是一个非预期情况，继续搜索 */<br /> const unsigned char *cp = (const unsigned char *) (longword_ptr - 1);<br /> if (*cp == c)<br /> return (char *) cp;<br /> else if (*cp == '/0')<br /> return NULL;<br /> if (*++cp == c)<br /> return (char *) cp;<br /> else if (*cp == '/0')<br /> return NULL;<br /> if (*++cp == c)<br /> return (char *) cp;<br /> else if (*cp == '/0')<br /> return NULL;<br /> if (*++cp == c)<br /> return (char *) cp;<br /> else if (*cp == '/0')<br /> return NULL;<br /> if (sizeof (longword) > 4) /* 如果long类型是8个字节，则还有4个字节需要判断 */<br /> {<br /> if (*++cp == c)<br /> return (char *) cp;<br /> else if (*cp == '/0')<br /> return NULL;<br /> if (*++cp == c)<br /> return (char *) cp;<br /> else if (*cp == '/0')<br /> return NULL;<br /> if (*++cp == c)<br /> return (char *) cp;<br /> else if (*cp == '/0')<br /> return NULL;<br /> if (*++cp == c)<br /> return (char *) cp;<br /> else if (*cp == '/0')<br /> return NULL;<br /> }<br /> }<br /> }<br /> return NULL;<br /> }<br /> #ifdef weak_alias<br /> #undef index<br /> weak_alias (strchr, index)<br /> #endif<br /> libc_hidden_builtin_def (strchr)

/* strrchr.c：strrchr函数的实现 */<br /> #include <string.h><br /> #undef strrchr<br /> /* 在S中查找C的最后一次出现 */<br /> char *<br /> strrchr (const char *s, int c)<br /> {<br /> register const char *found, *p;<br /> c = (unsigned char) c;<br /> /* 因为strchr非常地快，我们直接使用它来实现strrchr */<br /> if (c == '/0')<br /> return strchr (s, '/0');<br /> found = NULL;<br /> while ((p = strchr (s, c)) != NULL)<br /> {<br /> found = p;<br /> s = p + 1;<br /> }<br /> return (char *) found;<br /> }<br /> #ifdef weak_alias<br /> #undef rindex<br /> weak_alias (strrchr, rindex)<br /> #endif<br /> libc_hidden_builtin_def (strrchr)

    解释：
    （1）算法中，有可能搜索到字符c，也有可能搜索到终止符（当字符串中没有c时）。对于搜索到终止符，与strlen中一样，对于搜索到字符c，要判断longword中是否有一个字节为c，看表达式(((longword ^ charmask) + magic_bits) ^ ~(longword ^ charmask)) & ~magic_bits，长整型字charmask的每个字节都是字符c。strlen的对应表达式中的longword换成了这里的longword ^ charmask，而这里的longword中有一个字节为c，恰好等价于longword ^ charmask中有一个字节为0，因此具体的分析过程是一样的。
    （2）strrchr的实现直接使用strchr。用strchr不停地向前搜索，直到搜索到最后一个c为止。
    6、子串的无顺序匹配strspn,strcspn,strpbrk,wcsspn,wcscspn,wcspbrk：strspn和strcspn在s的开头查找一个最长子串，使其所有字符都在accept中（或都不在reject中），返回这个子串的长度。strspn的实现中直接对s中开头的每个字符搜索accept，看其是否在accept中。strcspn的实现则使用了strchr来查找字符。strpbrk在s中搜索第一个出现在accept中的字符，返回其指针。

/* strspn.c：strspn函数的实现 */<br /> #include <string.h><br /> #undef strspn<br /> /* 返回S中的第一个子串长度，这个子串的所有字符都在ACCEPT中 */<br /> size_t<br /> strspn (s, accept)<br /> const char *s;<br /> const char *accept;<br /> {<br /> const char *p;<br /> const char *a;<br /> size_t count = 0;<br /> for (p = s; *p != '/0'; ++p) /* 对s开头的各个字符，搜索accept */<br /> {<br /> for (a = accept; *a != '/0'; ++a)<br /> if (*p == *a) /* 若该字符在accept中，则子串长度加1 */<br /> break;<br /> if (*a == '/0') /* 若在accept中没有找到该字符，则子串匹配结束，直接返回count */<br /> return count;<br /> else<br /> ++count;<br /> }<br /> return count;<br /> }<br /> libc_hidden_builtin_def (strspn)

/* strcspn.c：strcspn函数的实现 */<br /> #if HAVE_CONFIG_H<br /> # include <config.h><br /> #endif<br /> #if defined _LIBC || HAVE_STRING_H<br /> # include <string.h><br /> #else<br /> # include <strings.h><br /> # ifndef strchr<br /> # define strchr index<br /> # endif<br /> #endif<br /> #undef strcspn<br /> /* 返回S中的第一个子串长度，这个子串的所有字符都不在REJECT中 */<br /> size_t<br /> strcspn (s, reject)<br /> const char *s;<br /> const char *reject;<br /> {<br /> size_t count = 0;<br /> while (*s != '/0') /* 对s开头的各个字符，搜索reject */<br /> if (strchr (reject, *s++) == NULL) /* 若不在reject，则子串长度加1 */<br /> ++count;<br /> else<br /> return count;<br /> return count;<br /> }<br /> libc_hidden_builtin_def (strcspn)

/* strpbrk.c：strpbrk函数的实现 */<br /> #ifdef HAVE_CONFIG_H<br /> # include <config.h><br /> #endif<br /> #if defined _LIBC || defined HAVE_CONFIG_H<br /> # include <string.h><br /> #endif<br /> #undef strpbrk<br /> /* 在s中搜索第一个出现在accept中的字符，返回其指针 */<br /> char *<br /> strpbrk (s, accept)<br /> const char *s;<br /> const char *accept;<br /> {<br /> while (*s != '/0') /* 对s开头的各个字符，看其是否在accept中 */<br /> {<br /> const char *a = accept;<br /> while (*a != '/0')<br /> if (*a++ == *s) /* 若在accept，则返回，否则继承向前搜索 */<br /> return (char *) s;<br /> ++s;<br /> }<br /> return NULL;<br /> }<br /> libc_hidden_builtin_def (strpbrk)

    7、模式匹配及字符串解析strstr,strtok,wcsstr,wcstok：strstr(src,sub)在src中搜索子串sub，返回其第一次出现的位置。strtok(str,set)用set中的字符作为分隔符把str分解为多个标号。
    strstr的实现用了最新的二路模式匹配算法，可以达到最好的效率。由于算法比较复杂，涉及到很多内部函数，这里就不解剖了，我们平时一般使用KMP算法来进行模式匹配，这个效率也已经非常不错了。strtok实现如下：

/* strok.c：strok函数的实现 */<br /> #include <string.h><br /> static char *olds; /* 下一记号的开始处，若到达字符串末尾，则olds指向终止符'/0' */<br /> #undef strtok<br /> /* 用DELIM中的字符作为分隔符把S解析成多个记号，返回当前的记号。如果S为NULL，<br /> 则strtok从即下一记号的开始处开始解析。例如：<br /> char s[] = "-abc-=-def";<br /> x = strtok(s, "-"); // x = "abc"<br /> x = strtok(NULL, "-="); // x = "def"<br /> x = strtok(NULL, "="); // x = NULL<br /> // s = "abc/0=-def/0"<br /> */<br /> char *<br /> strtok (s, delim)<br /> char *s;<br /> const char *delim;<br /> {<br /> char *token;<br /> if (s == NULL) /* s指定为NULL，则使用olds */<br /> s = olds;<br /> /* 从s开始搜索分隔符，跳过分隔符，让s移动到记号开始处 */<br /> s += strspn (s, delim);<br /> if (*s == '/0') /* 若s到达字符串末尾，则返回NULL表示记号解析过程完毕 */<br /> {<br /> olds = s;<br /> return NULL;<br /> }<br /> /* 找到当前记号的末尾处（即下一分隔符处） */<br /> token = s; /* token指向记号的首个字符 */<br /> s = strpbrk (token, delim); /* 从token开始找到下一分隔符，让s指向它 */<br /> if (s == NULL) /* 如果到达的是字符串末尾，说明当前记号是最后一个记号 */<br /> /* 从token开始，找到终止符，并赋给olds，表示记号解析结束 */<br /> olds = __rawmemchr (token, '/0');<br /> else /* 否则s指向了下一分隔符 */<br /> {<br /> /* 把分隔符替换成'/0'，以解析出当前记号，让OLDS指向下一记号的开始处 */<br /> *s = '/0';<br /> olds = s + 1;<br /> }<br /> return token;<br /> }

    算法先用strspn函数使s路过分隔符，移到当前记号的开始处；接着让token指向当前记号开始处，s移到下一个分隔符处（通过strpbrk函数）；然后把这个分隔符替换成终止符'/0'，以解析出当前记号，olds指向下一记号的开始处。下一次解析时，若指定s为NULL，则从olds处开始新的解析。