Thursday, August 07, 2003

The old standby

I'm filling out a programming quiz and run into that old standby, reverse the words of a string in place in linear time. I've done this one at the whiteboard too many times so I did a quick Google search: lots of references to the problem but no reusable code*. So, I write my own. To save some other person the trouble, I'm posting it here. Also, I'm hoping to get mail from someone pointing out how I could do it better. Good advice is a precious commodity.

* I am a big advocate of code reuse. I can't stand to see cut&paste coding and NIH (not invented here) syndrome drives me nuts.

#include <ctype.h>

/*
 * In C++ just use std::swap.  This macro uses the XOR hack to avoid
 * the stack and a temporary.
 */
#define SWAP(a,b) \ 
  do { (*a) ^= (*b); (*b) ^= (*a); (*a) ^= (*b); } while (0)

/* 
 * Although wordrev could be written using strtok(3), many
 * implementation of strtok run in quadratic time with respect to the
 * token string and strtok only expresses membership in the token
 * class rather than non-membership.  I contrast, most implementations
 * optimize isspace(3) very well usually using a table-driven macro
 * for contant time performance even avoiding the function call cost.
 *
 * If wordrev proves to be a hotspot, then unroll the loop:
 *
 *   switch (b - a) {
 *   case 0: case 1: break;
 *   case 2: SWAP(a[0], a[1]); break;
 *   case 3: SWAP(a[0], a[2]); break;
 *   case 4: SWAP(a[0], a[3]); SWAP(a[1], a[2]); break;
 *   case 5: SWAP(a[0], a[4]); SWAP(a[1], a[3]); break;
 *   default: // use the loop below
 *   }
 *
 * I prefer not to unroll it unless a profiler indicates that it
 * matters and that the unrolling makes a difference.
 */

int
wordrev (char* s, int len)
{
  char* m; /* word boundary marker */

  if (! s) return 0; /* protect against a null pointer */
  if (len < 0) return 0; /* nonsense argument */

  m = s;

  for (;;) {
    const char* X = s + len; /* end of search space */
    char* a, *b; /* pointers for reversing word */

    while (m < X && *m && isspace(*m))
      ++m; /* advance m to start of next word */

    a = m; /* word start */

    while (m < X && *m && ! isspace(*m))
      ++m; /* advance m to next word break */

    if (m == a)
      break; // EOS

    b = m - 1; /* word finish, skipping the space */

    for ( ; a < b; a++, --b)
      SWAP(a, b);
  }

  return m - s;
}

No comments: