strtok和strtok_r

1.strtok()函数的用法

函数原型：char *strtok(char *s, const char *delim);
Function：分解字符串为一组字符串。s为要分解的字符串，delim为分隔符字符串。
Description：strtok()用来将字符串分割成一个个片段。参数s指向欲分割的字符串，参数delim则为分割字符串，当strtok()在参数s的字符串中发现到参数delim的分割字符时则会将该字符改为字符。在第一次调用时，strtok()必需给予参数s字符串，往后的调用则将参数s设置成NULL。每次调用成功则返回被分割出片段的指针。

（1）如果stork函数的第一个参数不是NULL，函数将找到的字符串的第一个标记。同时保存它在字符串中的位置

（2）如果strtok函数的第一个参数是NULL，函数就在同一个字符串中从这个被保存的位置开始向前面一样查找下一个标记。

下面是一个使用实例：

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int main(int argc, char * argv[])
 5 {
 6     //时间格式 2010/08/11 10:38:22
 7     char strEventTime[] = "2010/08/11 10:38:22";
 8     char *token = NULL;
 9     
10      token = strtok(strEventTime, "/");
11     char *year = token;
12     if (token != NULL)
13     {
14         token = strtok(NULL, "/");
15     }
16     char *month = token;
17     if (token != NULL)
18     {
19         token = strtok(NULL, " ");
20     }
21     char *day = token;
22     if (token != NULL)
23     {
24         token = strtok(NULL, ":");
25     }
26     char *hour = token;
27     if (token != NULL)
28     {
29         token = strtok(NULL, ":");
30     }
31     char *minute = token;
32 
33     if (token != NULL)
34     {
35         token = strtok(NULL, ":");
36     }
37     char *second = token;
38 
39     printf("%s %s %s %s %s %s %s
", year, month, day, hour, minute, second);
40     return 0;
41 }

/*　　
* strtok是一个线程不安全的函数，因为它使用了静态分配的空间来存储被分割的字符串位置 　　
* 线程安全的函数叫strtok_r　　
* 运用strtok来判断ip或者mac的时候务必要先用其他的方法判断'.'或':'的个数，
* 因为用strtok截断的话，比如："192..168.0...8..."这个字符串，strtok只会截取四次，中间的...无论多少都会被当作一个key
*/

2.strtok()函数的实现

（1）NetBSD实现：

1: char*  strtok_r(char* string_org,const char* demial,char** last)
   2: {
   3: const char* spanp; //span表示分隔，p表示指针
   4: char c, sc; //c表示char字符，sc表示 span char
   5: char* tok;  //token表示分隔的段
   6:  
   7: //当开始结尾都为NULL的时候，说明没有字符被查找，所以返回NULL
   8: if (string_org == NULL  && (string_org = *last) == NULL)
   9:     {
  10:     return (NULL);
  11:     }
  12:  
  13: //由goto组成的循环是在扫描字符串的时候，当遇到所需要匹配的字符时，略过这个字符。        
  14: cont:
  15: c = *string_org++;
  16:     
  17: for (spanp = demial; (sc = *spanp++) != 0; )
  18:     {
  19:     if (c == sc)
  20:         {
  21:         goto cont;
  22:         }
  23:     }
  24:  
  25: //下一个字符为0，则表示到达了搜索结果，把last置为NULL，并返回NULL            
  26: if (c == 0)
  27:     {
  28:     *last = NULL;
  29:     return (NULL);
  30:     }
  31:  
  32: //把原始的字符串指针回退。            
  33: tok = string_org -1;
  34:  
  35: //开始扫描字符串中是否含有要匹配的字符，之后把这个匹配字符之前的部分返回。
  36: //这看似是个无限循环，但当源字符串和匹配字符串都走到结尾时，也就是string_org和sc都为NULL时，最外层循环最后会走到return(tok)结束循环。
  37: for (;;)
  38:     {
  39:     c = *string_org++;
  40:     spanp = demial;
  41:     
  42:     do 
  43:         {
  44:         if ((sc = *spanp++) == c) 
  45:             {
  46:             if (c == 0)
  47:                 {
  48:                 string_org = NULL;
  49:                 }
  50:             else
  51:                 {
  52:                 string_org[-1] = 0;
  53:                 }
  54:             *last = string_org;
  55:             return (tok);
  56:             }
  57:         } while (sc != 0);
  58:     }
  59:     
  60: }

（2）在NetBSD中strtok的实现：

   1: //把last设置为一个静态局部变量来保存余下内容的地址。
   2: char *
   3: strtok(char *s, const char *delim)
   4:     {
   5:     static char *lasts;
   6:  
   7:     return strtok_r(s, delim, &lasts);
   8:     }

（3）微软的实现：

   1: char*  strtok_r(char* string_org,const char* demial)
   2: {
   3: static unsigned char* last; //保存分隔后剩余的部分
   4: unsigned char* str;         //返回的字符串
   5: const unsigned char* ctrl = (const unsigned char*)demial;//分隔字符
   6:  
   7: //把分隔字符放到一个索引表中。定义32是因为ASCII字符表最多是0~255个，也是说用最大的255右移3位，也就是除以8一定会是32中的一个数。
   8: unsigned char map[32]; 
   9: int count;
  10:  
  11: //把map全部清为0，之后相与的操作，与0的都为0
  12: for (count =0; count <32; count++)
  13:     {
  14:     map[count] = 0;
  15:     }
  16:  
  17: //把匹配字符放入表中
  18: //放入的算法是把匹配字符右移3位，相当于除以8，的数值 并上(加上)
  19: //匹配字符与7，得到低3位，得出的结果，是把1左移的位数。最大左移位数是7，也就是所表示的最大值是128,    
  20: do 
  21:     {
  22:     map[*ctrl >> 3] |= (1 << (*ctrl & 7));
  23:     } while (*ctrl++);
  24:     
  25: //原始字符串是否为空，如果为空表示第二次获取剩余字符的分隔部分。    
  26: if (string_org)
  27:     {
  28:     str = (unsigned char*)string_org;
  29:     } 
  30: else
  31:     {
  32:     str = last;
  33:     }
  34:  
  35: //在表中查找是否有匹配的字符，如果有略过    
  36: while ((map[*str >> 3] & (1 << (*str & 7)))  && *str)
  37:     {
  38:     str++;
  39:     }
  40:  
  41: //重置需要扫描的字符串    
  42: string_org = (char*)str;
  43:  
  44: //开始扫描
  45: for (;*str; str++)
  46:     {
  47:     if ( map[*str >> 3] & (1 << (*str & 7)))
  48:         {
  49:         *str++ = '';//当找到时，把匹配字符填为0，并且把str指向下一位。
  50:         break; //退出循环             
  51:         }
  52:             
  53:     }
  54:     
  55: last =str; // 把剩余字符串的指针保存到静态变量last中。
  56:     
  57: if (string_org == (char*)str)
  58:     {
  59:     return NULL; //没有找到，也就是没有移动指针的位置，返回NULL
  60:     }
  61: else
  62:     {
  63:     return string_org; //找到了，返回之前字符串的头指针
  64:     }
  65: }

（4）对比：

　　1.NetBSD的方法是节约了空间，牺牲了时间(它的时间复杂度为N2)
　　2.而微软的方法是节约了时间(它的时间复杂度为N)，牺牲了空间(开了一个32个8位的空间）

3.strtok()自己的理解和注释：

　　自己在NetBSD的基础上加了一些帮助理解的注释：

 1 #ifndef STRTOK_H
 2 #define STRTOK_H
 3 
 4 
 5 #include <stdio.h>
 6 
 7 // NetBSD:
 8 char *cat_strtok_r(char *src, const char *delim, char **last) {
 9     const char *spanp; // span表示分割，p表示指针
10     char c, sc; // c表示char字符(保存src中的字符)，sc表示span char（保存delim的字符）
11     char *tok;  // 表示分隔的段
12 
13     // 当开始、结尾都为NULL时，说明没有字符查找
14     if (NULL == src && NULL == (src = *last))
15         return NULL;
16 
17     // 由goto组成的循环是在扫描字符串的时候，当遇到所需要匹配的字符时，略过这个字符
18 cont:
19     c = *src++;
20 
21     for (spanp = delim; (sc = *spanp++) != 0; ) {
22         if (c == sc)
23             goto cont; // cat：这里的意思应该是：src字符串头部匹配delim的部分都忽略掉，因为分割了也没意义，匹配部分前面已经没有其他字符了
24     }
25 
26     // 下一个字符为0，则表示到达了搜索结果，把last置为NULL，并返回NULL
27     // cat：其实就是到达src的尾部，也就意味着delim和src是相等的，就无从分割了
28     if (0 == c) {
29         *last = NULL;
30         return NULL;
31     }
32 
33     // 把原始的字符串指针回退
34     tok = src - 1; // cat：因为c = *src++;最后一步就是不匹配还是会执行++操作
35 
36     // 开始扫描字符串中是否含有压迫匹配的字符，之后把该匹配字符之前的部分返回
37     // 当源字符串和匹配字符串当走到结尾时，即src和sc都为NULL时，最外层循环最后会return(tok)结束循环
38     for ( ; ; ) {
39         c = *src++;
40         spanp = delim;
41         do {
42             if ((sc = *spanp++) == c) {
43                 if (0 == c)
44                     src = NULL;
45                 else
46                     src[-1] = 0; 
47                     // 比如src为"12:34",匹配字符为":"。当匹配到":"时，src++导致src指向了"3"，所以需要减1，把匹配到的位置(即把src中的":")设为''
48                     //*(src - 1) = 0;// 等价于这行代码
49 
50                 *last = src;
51 
52                 return tok;
53             }
54         } while (sc != 0);
55     }
56 }
57 
58 // 把last设置为一个静态局部变量来保存余下内容的地址
59 char *cat_strtok(char *src, const char *delim) {
60     static char *lasts;
61     return cat_strtok_r(src, delim, &lasts);
62 }
63 
64 #endif

测试代码：

 1 #include "strtok.h"
 2 
 3 
 4 void test_strtok();
 5 
 6 int main() {
 7 
 8     test_strtok();
 9 
10     return 0;
11 }
12 
13 void test_strtok() {
14     //char *src = "111:222:333:444";
15     char *src = "123:456";
16     char *ret = cat_strtok(src, ":");
17 
18     printf("%s
%s
", ret, src);
19 }

　　然后我们会发现程序运行到src[-1] = 0;这一步的时候出错。为什么呢？

　　先看C语言中内存分布情况（更多请查阅《C语言char[]和char*比较》http://www.cnblogs.com/lingshaohu/p/3956239.html ）：

char s[]="abc";   //栈
char *p2;         //栈
char *p3="123456";   //123456在常量区，p3在栈上。

　　也就是说，char *src = "123:456"; "123:456"是一个常量！常量不能修改，而我们src[-1] = 0;尝试修改它，所以报错！

　　因此，改成这样就可以了：

void test_strtok() {
    //char *src = "111:222:333:444";
    //char *src = "123:456";
    char src[] = "123:456";
    char *ret = cat_strtok(src, ":");

    printf("%s
%s
", ret, src);
}

ref：

http://www.cnblogs.com/aduck/articles/2245364.html

http://www.cppblog.com/yinquan/archive/2009/06/01/86411.html