Title: Student Code Critique Competition

Having read them for a couple of years, I thought it was about time I had a go at one of these code critiques, so here goes...

The first task is obviously to find out why this code seg faults. A segmentation fault occurs when the processor is asked to read or write to memory that doesn't exist or write to memory marked as read-only. Strictly speaking, the first case is actually a bus-error, but many systems merge these two classes of faults into one.

In this code the reason is pretty obvious in that the test harness is calling reverse() with a constant string: constants are often held in read-only memory, and reversing a section of read-only memory is probably going to be quite hard. Some compilers automagically copy constant strings into writable memory when passed to functions expecting non-constant arguments (such as reverse()) however this is very much a compiler dependant feature (Not one I have ever come across, and it would worry me if I did. Francis). I believe that most compilers will have a switch to enable a warning when such code is compiled, but many will ship with it turned off.

The first task, therefore, is to re-write the test harness to operate with a writable chunk of memory. It is also worth considering the possible ways in which reverse() might fail: what happens if it's passed a NULL pointer, an empty string, a string with an odd number of characters and so on. Testing for the correct handling of a NULL pointer is tricky since reverse() doesn't return any value, so the best we can do is call reverse(NULL) and see whether it seg.faults.

Whenever I write functions like reverse(), I always include a complete test harness inside "#ifdef TEST/#endif". Needless to say, functions like reverse() exist in their own compilation unit (roughly a .c file). For reverse(), my test harness would look a little bit like this (modified to reduce the number of lines):

#ifdef TEST
#include <stdio.h>
int main(void) {
  bool failed = false;
  struct{
    char original[10];
    char const * result;
  } tests[] = {
      { "",        ""},
      { "a",       "a"},
      { "ab",      "ba"},
      { "abc" ,    "cba"},
      { "abcd",    "dcba"}
    };
  for(int test = 0; test < 
    sizeof(tests)/sizeof(tests[0]); ++test) {
    printf("Reversing \"%s\"\n",
         tests[test].original);
    printf("expecting \"%s\"\n",
         tests[test].result);
    reverse(tests[test].original);
    printf("      got \"%s\"\t",
         tests[test].original);
    if(strcmp(tests[test].original,
         tests[test].result) == 0) {
      puts(" Pass.\n");
    } else {
      puts(" Failed!\n");
      failed = true;
    }
  }
  if(failed) puts("\n\nSome tests failed.\n");
  else   puts("\nAll tests passed.\n");
// Test for handling of NULL
  puts("testing NULL pointer handling.\n");
  reverse(NULL);
  puts("Well,  it didn't seg-fault!.\n");
  return 0;
}
#endif

Note that I can add new tests very easily just by extending the test array - a little trickery using sizeof() means I don't even have to update a "number of tests" variable. There is a slight issue with the fixed size of ten characters for the original string that I could get around, but it doesn't seem worth it for a test harness.

Notice also that every variable is initialised as soon as it is declared - this is a nice feature of the new version of C which I have used in the for-loop. Sadly I can't use it in reality as I don't have a C99-compliant compiler, however as the original code uses exactly this technique inside reverse() I guess the student must be richer than my employer! (or uses a C++ compiler. Francis)

While writing the new test harness I started to think about the function signature for reverse():

void reverse(char * str)

I don't like this for two reasons - first, "reverse" sounds like a more general-purpose array reversal function than a specific string-reversal function. Second, the formal parameter name of "str" is reserved by the C-standard, as is every other name beginning str. Next, the formal parameter is a non-constant pointer, but as a general rule I like to make pointer parameters constant so that I have some confidence in their value. If I need to change the pointer, I can always copy it to a local variable inside my function, and being a constant pointer doesn't mean I can't write to whatever it actually points to. Finally, void functions miss out on the important trick shown by many of the standard library functions of returning their calling parameter (e.g. strcat()). This makes the function much easier to use in some cases, for example inside the parameter list of a call to another function like sprintf(). I'd therefore change the function signature to be more like:

char * my_strrev(char * const ptr)

Moving on to the actual code of reverse(), it looks like the code is going to be very inefficient: just a cursory look showed that strlen() would be called at least once for every character in the original string, yet reversing a string doesn't alter its length, so why not call strlen() once and hold the result in a (constant) variable?

Looking further, there are a lot of array subscripting operations, and my experience with embedded systems has taught me the hard way that array subscripting is a very slow operation best reserved for when you need to access elements of an array in a random order. As reverse() only needs to access characters sequentially we would be far better off to use pointers directly, and given the original specification ("reverse a string in place with the use of pointers") which sounds suspiciously like a homework assignment, reverse() probably isn't what the lecturer wanted as pointers are only used to pass two characters into swap().

Obviously we need to access the string from both ends, so two pointers moving in opposite directions along the string are the easiest way to proceed. Initialising the first pointer is easy - it's the formal parameter to the function, but the second pointer will need to be "walked" along the string to find the end. As each character is copied, the pointers are moved closer together by one character each, and the whole string has been reversed when the second pointer reaches or passes the first.

The next thing I spotted was that a helper function called swap() is used to actually exchange two characters in the string. In C99 this could be marked as an inline function, or in C89 it could be implemented as a macro. I have to be honest and say that I probably wouldn't do either in this case: I'd probably but the exchanging directly into my_strrev().

The final thing to hit me was that reverse() doesn't just reverse the string - it also prints it out. I'm going to assume this is debugging added to find out why the original was seg.faulting, however I would have preferred to see this sort of code enclosed in some way to make it obvious, for example a call to debug_printf() or wrapped in "#ifdef DEBUG/#endif".

So what does my_strrev() look like after all these changes?

char * my_strrev(char * const ptr) {
  char * beg = ptr;
  char * end = ptr;
// Handle a NULL pointer gracefully...
  if(ptr == NULL) return NULL;
// Walk the end pointer up to the nul character
  while(*end != '\0') ++end;
// end now points to the nul - step back by one
  --end;
// Now reverse the string until the pointers 
// cross over
  while(beg < end) {
// Swap two characters and move the pointers
    char tmp = *beg;
    *beg++ = *end;
    *end-- = tmp;
  }
  return ptr;
}

You can see that I've actually walked the end pointer one character too far and have had to back it up again. There are a whole host of other ways I could have achieved the same result by adding +1 and -1 all over the code, however I feel this is the most obvious. I've also used post-increment on both of the pointers: normally I'd actually write this as two separate stages (swapping the characters and then moving the pointers) however I know that the number of lines of code needs to be kept down for printing in C-Vu and this code is still pretty readable, especially as the comment highlights the pointers moving.

Fixing the original seg.fault was quite easy. [well implicitly you did, but being picky, you did not do so explicitly. Francis] Doing a code-review of the rest of the functions shows that a lot can be changed, but how much better is the new code? That depends on how you define "better". One metric might be how fast the code is, and fortunately I have access to some really powerful code profiling tools. I ran the same tests on both my_strrev() and reverse(). reverse() took an average of 1.64us, of which only 0.34us was in reverse() itself, the rest being in swap() and strlen(). my_strrev() took an average of 0.43us with no function calls. So was it worth it? Possibly. If my_strrev() is only used once or twice inside a huge application, a saving of 1.21us simply isn't worth the effort. However, if my_strrev() is used in the middle of a tight loop called a hundred thousand times per second in a real-time critical system, saving 121us might make the different between your code being fast enough and crashing. As I spend most of my time in the latter environment, it's probably worth it for me. As the original code was probably a homework assignment, the time saving really isn't worth it. Perhaps this goes to prove the old adage regarding optimisation:

Rule 1 (for all programmers): Don't do it.

Rule 2 (for experts only): Don't do it yet.

There are two issues that need to be addressed in this code; what is 'C' and the use of constant data.

  char word[] ="cheese";
  reverse(word);

  const char word[] ="cheese";  
  reverse(word); /* word is of type const
                 char* */

  const char word[] ="cheese";
  reverse((char*)word);

for(;;){
  char *a = &(str[i]);
  char *b = &(str[len-i-1]);

#include <string.h>
#include <stdio.h>
static void swap(char *a, char *b){
  char tmp;
  tmp = *a;
  *a = *b;
  *b = tmp;
}
void reverse(char *str){
  char *a=0, *b=0;
  size_t i, len=strlen(str);
  for(i=0; i<len/2; i++){
    a = &(str[i]);
    b = &(str[len-i-1]);
    printf("swapping %c %c...\n", *a, *b);
    swap(a,b);
    printf("the reversed string is: %s\n", str);
  }
}
int main(){
  char word[] = "cheese";
  reverse(word);
/* reverse(word) may be replaced by strrev(word) */
  return 0;
}

The problem with this code was quite easy to spot for a seasoned C programmer; most would get the compiler to spot it for them by enabling warnings (in gcc's case -Wwrite-strings). The problem is that the author is trying to apply reverse() to a string literal, while the implementation treats literals as const and has write-protected the memory it's stored in.

The moral is that the first thing to do when learning to use a new compiler is find out how to enable as many warnings as possible. I really think compilers should enable all warnings by default and let advanced programmers disable them if necessary (for legacy code etc), instead of the other way round.

An easy fix is to use strdup() to create a writable copy of the string. However, strdup() is not strictly standard, and not always provided. Luckily it's very easy to implement, so I've written an implementation called str_dup(). Most names beginning with "str" are reserved by and for the standard, but that only applies to those where the "str" is followed by another lower-case letter.

I want to keep reverse()'s implementation of altering the input string, as I'll discuss later, so I'll put the call to str_dup() in main() for now. So the implementation of main() becomes:

reverse(str_dup("cheese"));

The code now compiles without the warning about a discarded qualifier, and more importantly runs and produces the expected result instead of seg-faulting. However, as we've been sensible and enabled other warnings as well, we see that printf() needs declaring, main's declaration is wrong, and it needs a return value. We should also be tidy and free the temporary string we've created. So we add some includes (stdio.h for printf(), stdlib.h for free() and the malloc() in our strdup implementation) to the top of the source file, and main() becomes:

int main(void){
  char *str = str_dup("cheese");
  reverse(str);
  free(str);
  return 0;
}

I recently embarrassed myself on a newsgroup about the definition of main: if you're not using arguments, I learnt the correct declaration is int main(void) rather than int main(). [But only in C. Francis]

I don't see a need to change swap(); there are a number of changes I'd like to make to reverse() though. I'll keep the implementation that it alters the string it's passed, because there'll often be times when this is the desired behaviour for performance reasons, rather than creating a new string. But it's common practice to return a copy of the pointer to the string in such cases, for convenience and to enable tail-call optimisations. The name reverse() is fine, because it's obvious by the argument type that it's a string we're reversing. The name "str" for the argument is fine, not being followed by a lower-case letter.

To make reverse() more versatile, we don't want it to print the result, nor the messages for debugging swap if we want to use it for real. The best thing to do with the final printf is move it into main(). For now the debugging messages can be sent to stderr instead of stdout; then they can be easily be suppressed or redirected to a file independently of the output we really want.

Working down the reverse() function, a and b are declared earlier than necessary, so we can move that inside the loop and combine the declarations with assignments. We could do without the variables altogether and use expressions, but with the debugging statement it's more convenient to keep them, and even if we remove the debugging, the use of temporary variables won't cause any run-time overhead with a modern compiler. I prefer the syntax of pointer arithmetic to logically dereferencing with [], then taking the address again, so I've changed that in the assignment statements too.

I've moved the declaration of i outside the loop, because I've got into the habit of trying to make my code portable, and ANSI C is still much more widely supported than C99. It should also be size_t instead of a simple int. There's a strong case for using strlen() in each instance that the length of a string is needed, but I've decided to call it just once and store the result in a variable here. This is because we're not changing the length of the string, but as we are changing the content, the compiler might decide it isn't safe to optimise it away to one call, and performance would suffer, especially as it's used twice each time round the loop.

Finally, as we wanted to use reverse() on, effectively, a const string, it would be useful to provide an alternative version of the function that operates on and returns a copy. I'll call this version reverse_copy(); it's a very simple forwarding function, so if I were still using C99 it would be a candidate for inlining. Now all that remains is to alter main() to use reverse_copy() instead of strdup() and reverse().

At the risk of going on too long for such a short piece of code, there is one more thing that can be done. So far we've stuck to a single source file for this example. The functions are all potentially useful though, so it would be a good idea to put them in a separate file from main so that it can be built into a useful library for use in other programs in future. With this in mind, I'll go back on what I said before about keeping the function names and give them all a prefix of str_ to indicate they're user-supplied code to supplement the standard library's string operations. It's good practice to decide on a prefix for each source file in a large program and use it religiously on every function name and non-local variable: it aids debugging and reduces the chance of name clashes.

Here is the code. Where a function has a comment next to its header declaration I've saved space by not providing a similar comment in the source file:

#ifndef STR_EXTRA_H
#define STR_EXTRA_H
/* Used instead of strdup() in case the latter isn't provided by the platform */
char *str_dup(const char *);
/* Swaps the characters pointed to by a and b */
void str_swap(char *a, char *b);
/* Reverses str and returns a copy of the pointer (not a copy of the string) */
char *str_reverse(char *str);
/* Returns a reversed copy of str, which may be free()'d */
char *str_reverse_copy(const char *str);
#endif /* STR_EXTRA_H */

/* str_extra.c */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char *str_dup(const char *str){
  char *ret = malloc(strlen(str) + 1);
  strcpy(ret, str);
  return ret;
}
void str_swap(char *a, char *b){
  char tmp;
  tmp = *a;
  *a = *b;
  *b = tmp;
}
char *str_reverse(char *str){
  size_t i;
  const size_t len = strlen(str);
  for(i = 0; i < len/2; ++i)  {
  char *a = str + i;
  char *b = str + len - i - 1;
  fprintf(stderr, "swapping %c & %c...\n", *a, *b);
  swap(a, b);
  }
  return str;
}
char *str_reverse_copy(const char *str){
  return reverse(str_dup(str));
}
/* End of str_extra.c */
/* main.c */
#include <stdio.h>
#include <stdlib.h>
#include "str_extra.h"
int main(void){
  char *str = reverse_copy("cheese");
  printf("the reversed string is: %s\n", str);
  free(str);
  return 0;
}
/* End of main.c */