当前位置: 首页 >> 程序设计 >> strstr 两个实现的对比

strstr 两个实现的对比

作者：来源：lgfang.cublog.cn 发表时间：2007-03-20 浏览次数：字号：大 中 小

Created: Fang lungang 03-12-2007 Modified: Fang lungang 03-12-2007 21:17>

今天看到 strstr() 的两个实现。两相对比，感觉真是有意思。

实现一

http://lynx.isc.org/lynx2.8.5/lynx2-8-5/src/strstr.c

这个程序的风格、算法、技巧都中规中矩，简洁、明了，感觉就是典型的 C 程序。和下一个程序相比，我绝对更喜欢这个。

/* Written by Philippe De Muyter <phdm@macqel.be>.  */
char *
  strstr (buf, sub)
     register char *buf;
     register char *sub;
{
    register char *bp;
    register char *sp;

    if (!*sub)
      return buf;
    while (*buf)
    {
        bp = buf;
        sp = sub;
        do {
            if (!*sp)
              return buf;
        } while (*bp++ == *sp++);
        buf += 1;
    }
    return 0;
}

实现二

glibc 的源码（glibc-2.5/string/strstr.c）

这个程序我就没看，估计看也看不懂。虽说作者号称效率高，但搞得也太复杂、难懂了吧。

/*
 * My personal strstr() implementation that beats most other algorithms.
 * Until someone tells me otherwise, I assume that this is the
 * fastest implementation of strstr() in C.
 * I deliberately chose not to comment it.  You should have at least
 * as much fun trying to understand it, as I had to write it :-).
 *
 * Stephen R. van den Berg, berg@pool.informatik.rwth-aachen.de */

typedef unsigned chartype;

char *
strstr (phaystack, pneedle)
     const char *phaystack;
     const char *pneedle;
{
  const unsigned char *haystack, *needle;
  chartype b;
  const unsigned char *rneedle;

  haystack = (const unsigned char *) phaystack;

  if ((b = *(needle = (const unsigned char *) pneedle)))
    {
      chartype c;
      haystack--;       /* possible ANSI violation */

      {
    chartype a;
    do
      if (!(a = *++haystack))
        goto ret0;
    while (a != b);
      }

      if (!(c = *++needle))
    goto foundneedle;
      ++needle;
      goto jin;

      for (;;)
    {
      {
        chartype a;
        if (0)
        jin:{
        if ((a = *++haystack) == c)
          goto crest;
          }
        else
          a = *++haystack;
        do
          {
        for (; a != b; a = *++haystack)
          {
            if (!a)
              goto ret0;
            if ((a = *++haystack) == b)
              break;
            if (!a)
              goto ret0;
          }
          }
        while ((a = *++haystack) != c);
      }
    crest:
      {
        chartype a;
        {
          const unsigned char *rhaystack;
          if (*(rhaystack = haystack-- + 1) == (a = *(rneedle = needle)))
        do
          {
            if (!a)
              goto foundneedle;
            if (*++rhaystack != (a = *++needle))
              break;
            if (!a)
              goto foundneedle;
          }
        while (*++rhaystack == (a = *++needle));
          needle = rneedle; /* took the register-poor aproach */
        }
        if (!a)
          break;
      }
    }
    }
foundneedle:
  return (char *) haystack;
ret0:
  return 0;
}