Highly efficient string reversal code

[dominantubergeek]

Hello, I'm a highly experienced expert C programmer and I've written
this code to reverse a string in place. I think you could all learn
something from it!

int reverse(char* reverseme){
int retval=-1;
if(retval!=NULL ){
int len=strlen(retv al){
if(len>0){
int half=len>>1;
for(;retval<hal f;retval++){
reverseme[retval]^=reverseme[len-(retval+1)];
reverseme[len-(retval+1)]=reverseme[retval];
reverseme[retval]^=reverseme[len-(retval+1)];
}
}
}
return retval;
}

-Phil/CERisE

[Lew Pitcher]

My contribution to the cause

char *reverse(char *str)
{
char *start, *end, temp;

for (end=str;*end;+ +end);
--end; /* A */

for (start=str; start < end; ++start, --end) /* B */
{
temp = *start;
*start = *end;
*end = temp;
}
return str;
}

NB: For the degenerate case of a zero-length string, the computation of the
end character ( /* A */ ) produces a pointer that, *if dereferenced* would
encounter UB because it points out-of-bounds to the intended array.
*However*, the reversal loop ( /* B */ ) tests the value of this pointer
(without dereferencing it), and will discontinue the loop immediately
(again, without dereferencing the pointer).

--
Lew Pitcher

Master Codewright & JOAT-in-training | Registered Linux User #112576
http://pitcher.digitalfreehold.ca/ | GPG public key available by request
---------- Slackware - Because I know what I'm doing. ------

[Bartc]

"oksid" <ok***@bluewin. chwrote in message
news:be******** *************** ****@news.hispe ed.ch...

Bartc wrote:

>>
"Ben Bacarisse" <be********@bsb .me.ukwrote in message
news:87******* *****@bsb.me.uk ...

>>"Malcolm McLean" <re*******@btin ternet.comwrite s:

"Ben Bacarisse" <be********@bsb .me.ukwrote in message
void reverse(char *str)
{
char temp;
int start = 0;
int end = strlen(str) - 1;
while(start < end)
{
temp = str[start];
str[start] = str[end];
str[end] = temp;
start++;
end--;
}
}

Of course strlen() returns a size_t. So we'll replace those ints with
size_t's. What horrible thing have I now done to this function?

I don't get your point. You know the above is wrong and that
switching to size_ t does not make it right, so what are you driving
at?

What's wrong about it? It works fine, provided str points to a valid
string.

If "str" points to an empty string "strlen()" will return 0...
"end" will be equal to -1 or 0xFFFFFFFF

So? In that case start<end will be false, and the loop isn't executed.

Unless you're saying int can be unsigned? That would be news to me.

How can anyone write any sort of portable, reliable code when you don't even
know whether 'int' is signed or unsigned.

--
Bartc

[Ben Bacarisse]

"Bartc" <[e-mail] rites:

"Ben Bacarisse" <be********@bsb .me.ukwrote in message
news:87******** ****@bsb.me.uk. ..

>"Malcolm McLean" <re*******@btin ternet.comwrite s:

<snip>

>>void reverse(char *str)
{
char temp;
int start = 0;
int end = strlen(str) - 1;
while(start < end)
{
temp = str[start];
str[start] = str[end];
str[end] = temp;
start++;
end--;
}
}

Of course strlen() returns a size_t. So we'll replace those ints with
size_t's. What horrible thing have I now done to this function?

I don't get your point. You know the above is wrong and that
switching to size_ t does not make it right, so what are you driving
at?

What's wrong about it? It works fine, provided str points to a valid string.

There are two cases. If all of the values of size_t (the result of
strlen) can be represented in an int (not likely, but possible) then
the code works. If not, then strlen("") - 1 is a large positive
number that is out of range for an int, and the conversion to int is
implementation defined (which may include raising a signal).

--
Ben.

[Ben Bacarisse]

Lew Pitcher <lp******@teksa vvy.comwrites:

My contribution to the cause

char *reverse(char *str)
{
char *start, *end, temp;

for (end=str;*end;+ +end);
--end; /* A */

for (start=str; start < end; ++start, --end) /* B */
{
temp = *start;
*start = *end;
*end = temp;
}
return str;
}

NB: For the degenerate case of a zero-length string, the computation of the
end character ( /* A */ ) produces a pointer that, *if dereferenced* would
encounter UB because it points out-of-bounds to the intended array.

You need to say why you dispute the claim that 6.5.6 paragraph 8 says
the result is undefined behaviour:

"... If both the pointer operand and the result point to elements
of the same array object, or one past the last element of the array
object, the evaluation shall not produce an overflow; otherwise, the
behavior is undefined."

*However*, the reversal loop ( /* B */ ) tests the value of this pointer
(without dereferencing it), and will discontinue the loop immediately
(again, without dereferencing the pointer).

And then you'd have to say why the < operation is defined when most
people read 6.5.8 paragraph 5 as saying that it is not.

--
Ben.

[Richard Heathfield]

Lew Pitcher said:

My contribution to the cause

char *reverse(char *str)
{
char *start, *end, temp;

for (end=str;*end;+ +end);
--end; /* A */

<snip>

NB: For the degenerate case of a zero-length string, the computation of
the end character ( /* A */ ) produces a pointer that, *if dereferenced*
would encounter UB because it points out-of-bounds to the intended array.

If you fall off the beginning of an array, dereferencing is not required -
just doing it is UB.

--
Richard Heathfield <http://www.cpax.org.uk >
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

[Richard]

Lew Pitcher <lp******@teksa vvy.comwrites:

My contribution to the cause

char *reverse(char *str)
{
char *start, *end, temp;

for (end=str;*end;+ +end);
--end; /* A */

Did you not read the thread section where this is UDB in the case of
zero length strings? A surprise to me too I must admit. And thats even
before you use the illegal value in the comparison below.

>
for (start=str; start < end; ++start, --end) /* B */
{
temp = *start;
*start = *end;
*end = temp;
}
return str;
}

NB: For the degenerate case of a zero-length string, the computation of the
end character ( /* A */ ) produces a pointer that, *if dereferenced* would
encounter UB because it points out-of-bounds to the intended array.
*However*, the reversal loop ( /* B */ ) tests the value of this pointer
(without dereferencing it), and will discontinue the loop immediately
(again, without dereferencing the pointer).

--

[brix99luftballons]

do************* *@ymail.com ha scritto:

Hello, I'm a highly experienced expert C programmer and I've written
this code to reverse a string in place. I think you could all learn
something from it!

int reverse(char* reverseme){
int retval=-1;
if(retval!=NULL ){
int len=strlen(retv al){
if(len>0){
int half=len>>1;
for(;retval<hal f;retval++){
reverseme[retval]^=reverseme[len-(retval+1)];
reverseme[len-(retval+1)]=reverseme[retval];
reverseme[retval]^=reverseme[len-(retval+1)];
}
}
}
return retval;
}

-Phil/CERisE

Just another little variation :

void reverse(char* pStart)
{
char* pEnd;
int len;

if((NULL==pStar t) || (1 >= (len=(strlen(pS tart)))))
return;

pEnd= pStart+len;
do{
char t;

pEnd--;
t = *pStart;
*pStart++ = *pEnd;
*pEnd = t;
}while(pStart < pEnd);
}

B.

[brix99luftballons]

Of course, that works, not like Your mental-disturbed code ;-)
B.

[Lew Pitcher]

On September 24, 2008 09:49, in comp.lang.c, Ben Bacarisse
(be********@bsb .me.uk) wrote:

Lew Pitcher <lp******@teksa vvy.comwrites:

>My contribution to the cause

char *reverse(char *str)
{
char *start, *end, temp;

for (end=str;*end;+ +end);
--end; /* A */

for (start=str; start < end; ++start, --end) /* B */
{
temp = *start;
*start = *end;
*end = temp;
}
return str;
}

NB: For the degenerate case of a zero-length string, the computation of
the end character ( /* A */ ) produces a pointer that, *if dereferenced*
would encounter UB because it points out-of-bounds to the intended array.

You need to say why you dispute the claim that 6.5.6 paragraph 8 says
the result is undefined behaviour:

"... If both the pointer operand and the result point to elements
of the same array object, or one past the last element of the array
object, the evaluation shall not produce an overflow; otherwise, the
behavior is undefined."

>*However*, the reversal loop ( /* B */ ) tests the value of this pointer
(without dereferencing it), and will discontinue the loop immediately
(again, without dereferencing the pointer).

And then you'd have to say why the < operation is defined when most
people read 6.5.8 paragraph 5 as saying that it is not.

Oops. My bad. You are right, of course.

So, I'll try again - how about this variation?

char *reverse(char str[])
{
long int start, end;
char temp;

for (end=0;str[end];++end);
--end;

for (start=0; start < end; ++start, --end)
{
temp = str[start];
str[start] = str[end];
str[end] = temp;
}
return &str[0];
}
--
Lew Pitcher

Master Codewright & JOAT-in-training | Registered Linux User #112576
http://pitcher.digitalfreehold.ca/ | GPG public key available by request
---------- Slackware - Because I know what I'm doing. ------

[Flash Gordon]

Lew Pitcher wrote, On 24/09/08 18:28:

On September 24, 2008 09:49, in comp.lang.c, Ben Bacarisse
(be********@bsb .me.uk) wrote:

>Lew Pitcher <lp******@teksa vvy.comwrites:

>>My contribution to the cause

char *reverse(char *str)
{
char *start, *end, temp;

for (end=str;*end;+ +end);
--end; /* A */

for (start=str; start < end; ++start, --end) /* B */
{
temp = *start;
*start = *end;
*end = temp;
}
return str;
}

NB: For the degenerate case of a zero-length string, the computation of
the end character ( /* A */ ) produces a pointer that, *if dereferenced*
would encounter UB because it points out-of-bounds to the intended array.

You need to say why you dispute the claim that 6.5.6 paragraph 8 says
the result is undefined behaviour:

"... If both the pointer operand and the result point to elements
of the same array object, or one past the last element of the array
object, the evaluation shall not produce an overflow; otherwise, the
behavior is undefined."

>>*However*, the reversal loop ( /* B */ ) tests the value of this pointer
(without dereferencing it), and will discontinue the loop immediately
(again, without dereferencing the pointer).

And then you'd have to say why the < operation is defined when most
people read 6.5.8 paragraph 5 as saying that it is not.

Oops. My bad. You are right, of course.

So, I'll try again - how about this variation?

char *reverse(char str[])
{
long int start, end;
char temp;

for (end=0;str[end];++end);

A problem is the string is longer than can be represented by a long int ;-)

--end;

for (start=0; start < end; ++start, --end)
{
temp = str[start];
str[start] = str[end];
str[end] = temp;
}
return &str[0];

Why not "return str"?

}

char *reverse(char *str)
{
if (str && *str) {
char *end;
char *start;
/* subtract safe as already caught 0 length */
for (start = str, end = strchr(str,0) - 1;
end start;
start++, end--) {
char temp = *start;
*start = *end;
*end = temp;
}
}
return str;
}

I think the only limits on this would be the limits on the C
implementation and, of course, needing the pointer passed to be a valid
pointer to the first[1] character modifiable string.

[1] Well, the first character of the sub-string you want reversed, you
could leave the start of a string unreversed by passing a pointer to a
later character in the string.
--
Flash Gordon
If spamming me sent it to sm**@spam.cause way.com
If emailing me use my reply-to address
See the comp.lang.c Wiki hosted by me at http://clc-wiki.net/