Write code to reverse a C-style string in place

Question

I know this question has been asked many times before, but I just have a few questions about my code below.

So the code below doesn't work because in my while loop I have str != end instead of str < end. Why does it have to be str < end? I'm confused because it seems like the condition str != end should work the same way, since the pointers will eventually be pointing at the same position.

My second question is why we have to do while(*end){end++;} instead of while(end){end++}. Isn't the pointer invalid when we move past the length of end anyway? What is while(end){end++} doing if it's not correct?

My last question is that in other variations of this code, I've seen a condition added to the top of this function that says if(!(*str)){return;}. Is this necessary? My code seems to handle the empty string fine without this. Also, similar to *end vs end, why do we have to do !(*str) instead of !(str)?

   void reverse(char *str){
       char *end = str;
       while(*end){
          end++;
       }
       end--;

       while(str != end){
          char tmp = *str;
          *str = *end;
          *end = tmp;
          str++; end--;
       }
    }

Answer 1

1. Why does it have to be str < end?

Consider what happens for strings with an even number of characters, e.g. "abcdef".

2. why we have to do while(*end){end++;} instead of while(end){end++}.

You're looking for the null byte terminating the string, i.e. when the pointer end points to a null byte. Using the latter version which make the loop terminate only when the pointer points to address zero.

3. I've seen a condition added to the top of this function that says if(!(*str)){return;}. Is this necessary?

NoYes! As the other answers correctly pointed out, the check avoids that --end; is executed.

Answer 2

You increment str and decrement end at the same time (str++; end--;). So it's possible for them to hop over each other and never be equal when you come to compare them.

In your current implementation, if an empty string is passed (*str==0) then you still unconditionally decrement end (end--, 5th line of function). So now it looks like str starts out larger than end which is bad news if str!=end is the conditional in your loop (I say "looks like" because, as pointed out by Cornstalks, it's actually undefined behaviour—under some circumstances the compiler might for example adjust end so that points too far ahead of str). In any event, it's even worse news as soon as you dereference end, because you're likely messing with unallocated memory.

As for your question about !(*str) : if *str==0 that means that the string is empty, whereas if str==0 that means the calling function has passed you a NULL string pointer. You should check for both eventualities—specifically, to avoid blowing up the universe, check whether the pointer is NULL first, before you attempt to dereference it.

Answer 3

I want to specifically answer the question regarding whether if(!(*str)){return;} is necessary.

Yes, it is absolutely necessary with your current code.

Without it, end-- will be executed. This means that end will be decremented outside of the valid range [str, str + strlen(str) + 1] (you can increment a pointer one-past the end of its memory block, but you can't dereference it).

Doing so is actually undefined behavior. A pointer outside if a valid memory range is undefined behavior, even if you don't dereference it.

For example, if your computer is using a segmented memory model, then your comparison (str < end) might still be true, even if you have an empty string and you decremented end (in this case, end could have wrapped around and str < end is still true).

Consider, for example, a aaaa:bbbb segmented memory model. aaaa is the segment, bbbb is the offset within the segment. If str is a pointer to 1234:0000, and you decrement it, it could be a new value 1234:ffff. Why didn't the segment decrement? Because the compiler knows you can't jump segments; a pointer can only point to data within the current segment. So when doing pointer arithmetic, it only modifies the offset (the lower two bytes) of the pointer. Now, str < end is still true, and the code will continue and wreck havoc.

Answer 4

1. The condition str != end will give you adequate results only if your string has an odd number of characters. Otherwise it is well possible that you have the following sequence:

   str 0 1 2

   end 3 2 1

   At this point, str != end is still true, although your pointers already passed the middle of the string.

2. while(end) doesn't check if the pointer is valid in the sense that it is pointing to a value you previously assigned to that memory address. It only checks if end is different from NULL.

3. This is not technically necessary, but it ensures that you exit the function immediately if the string is empty, without doing any additional work.

   Edit: As pointed out by Cornstalks, it is necessary to check this.

Answer 5

You need to have str < end because you do str++; end--;. What happens if end is exactly above str and you do str++; end--;? After that str will be exactly above end and they will differ but you don't want to continue your loop.

end is allways a pointer. It might point to some valid memory or it might point somewhere which will give you a segfault if you try to access that memory. Increasing a pointer will only make it point to a higher address. It will not become NULL just because the address is invalid. That is why you have to look at *end to find the end of your null terminated string.

With your current code it does not seem necessary to have the check if(!(*str)){return;} as empty strings are catched by the fact that str and end becomes the same. However, it might be a good idea to add if(!str){return;} to avoid getting a segfault if someone calls your function with a NULL pointer.

Answer 6

it seems like the condition str != end should work the same way, since the pointers will eventually be pointing at the same position.

That depends on whether the string has an even or an odd number of characters. In the former case, the str and end pointers will move past each other and will never be equal.

What is while(end){end++} doing if it's not correct?

This is checking whether end is NULL, and you are not setting end to NULL.