Highly efficient string reversal code

[CBFalconer]

Re: Highly efficient string reversal code

Ben Bacarisse wrote:

Richard<rgrdev@ gmail.comwrites :
>
<snip>
>

>Much nicer IMO:
>>
>#include <string.h>
>>
>char * my_strrev(char *s){
> char t;
> char *e = s+strlen(s)-1;
> while(e>s){
> t = *s;
> *s++ = *e;
> *e-- = t;
> }
>}
>>
>I'm sure it breaks some sort of ISO magic,

>
Not "magic" but it has undefined behaviour on empty strings.

It also has the fatal error (to me) of returning a char*. This
encourages the silly mistake of trying to print a string and its
reverse with:

printf("%s & %s\n", s, strrev(s));

In fact it is even worse than that - it fails to return the
declared object. My version returns strlen, which it needs to
evaluate to find the end of the string, and thus avoids the caller
needing to call it again. Also note that my code returns a NULL if
the passed string is NULL, and correctly handles strings of length
0 and 1.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home .att.net>
Try the download section.

[CBFalconer]

Re: Highly efficient string reversal code

Ben Bacarisse wrote:

CBFalconer <cbfalconer@yah oo.comwrites:
>
<snip code>
>

>This is so horrible and faulty that I have to attach the
>following. Don't forget to #include <strings.h>.

>
I'd include <string.hinstea d. I haven't seen strings.h for
decades.

A point. A palpable point. Thanks.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home .att.net>
Try the download section.

[lovecreatesbea...@gmail.com]

Re: Highly efficient string reversal code

On Sep 23, 7:22 am, pete <pfil...@mindsp ring.comwrote:

Richard wrote:

#include <string.h>

>

char * my_strrev(char *s){
     char t;
     char *e = s+strlen(s)-1;
     while(e>s){
        t    = *s;
        *s++ = *e;
        *e-- = t;
     }
}

>

I'm sure it breaks some sort of ISO magic, but it seems more concise and
readable to me.  No I didnt test it, but I guess the idea should be self
evident.

>
It's undefined when attempting to reverse a zero length string.

How to reverse a zero length string for it has only a single NULL
terminating character : ) The reverse function quits if this is the
case.

[lovecreatesbea...@gmail.com]

Re: Highly efficient string reversal code

On Sep 23, 9:28 am, "lovecreatesbea ...@gmail.com"
<lovecreatesbea ...@gmail.comwr ote:

On Sep 23, 7:22 am, pete <pfil...@mindsp ring.comwrote:
>
>
>
>
>

Richard wrote:

#include <string.h>

>

char * my_strrev(char *s){
     char t;
     char *e = s+strlen(s)-1;
     while(e>s){
        t    = *s;
        *s++ = *e;
        *e-- = t;
     }
}

>

I'm sure it breaks some sort of ISO magic, but it seems more concise and
readable to me.  No I didnt test it, but I guess the idea should beself
evident.

>

It's undefined when attempting to reverse a zero length string.

>
How to reverse a zero length string for it has only a single NULL
terminating character : ) The reverse function quits if this is the
case.

My version

char *reverse(char *p)
{
char *p1, *p2, ch;

for (p1 = p; *(p1 + 1); p1++) ;
for (p2 = p; p2 < p1; p2++, p1--)
ch = *p2, *p2 = *p1, *p1 = ch;
return p;
}

[Ben Bacarisse]

Re: Highly efficient string reversal code

CBFalconer <cbfalconer@yah oo.comwrites:

Ben Bacarisse wrote:

>Richard<rgrdev @gmail.comwrite s:
>>
><snip>
>>

>>Much nicer IMO:
>>>
>>#include <string.h>
>>>
>>char * my_strrev(char *s){
>> char t;
>> char *e = s+strlen(s)-1;
>> while(e>s){
>> t = *s;
>> *s++ = *e;
>> *e-- = t;
>> }
>>}
>>>
>>I'm sure it breaks some sort of ISO magic,

>>
>Not "magic" but it has undefined behaviour on empty strings.

>
It also has the fatal error (to me) of returning a char*.

The fatal error is that is does *not* return a char * :-)

--
Ben.

[Ben Bacarisse]

Re: Highly efficient string reversal code

"lovecreatesbea ...@gmail.com" <lovecreatesbea uty@gmail.comwr ites:

On Sep 23, 9:28 am, "lovecreatesbea ...@gmail.com"
<lovecreatesbea ...@gmail.comwr ote:

>On Sep 23, 7:22 am, pete <pfil...@mindsp ring.comwrote:
>>

Richard wrote:
#include <string.h>

>>

char * my_strrev(char *s){
     char t;
     char *e = s+strlen(s)-1;
     while(e>s){
        t    = *s;
        *s++ = *e;
        *e-- = t;
     }
}

>>

I'm sure it breaks some sort of ISO magic, but it seems more concise and
readable to me.  No I didnt test it, but I guess the idea should be self
evident.

>>

It's undefined when attempting to reverse a zero length string.

>>
>How to reverse a zero length string for it has only a single NULL
>terminating character : ) The reverse function quits if this is the
>case.

Yes, but that is not the problem.

My version
>
char *reverse(char *p)
{
char *p1, *p2, ch;
>
for (p1 = p; *(p1 + 1); p1++) ;

If p points to an empty string this, too, is probably UB. It may not
be -- one would have to see the call, but you should not even risk
this. A call like: char test[10]; test[0] = 0; reverse(test); is bad
news!

for (p2 = p; p2 < p1; p2++, p1--)
ch = *p2, *p2 = *p1, *p1 = ch;
return p;
}

--
Ben.

[Richard]

Re: Highly efficient string reversal code

Ben Bacarisse <ben.usenet@bsb .me.ukwrites:

CBFalconer <cbfalconer@yah oo.comwrites:
>

>Ben Bacarisse wrote:

>>Richard<rgrde v@gmail.comwrit es:
>>>
>><snip>
>>>
>>>Much nicer IMO:
>>>>
>>>#include <string.h>
>>>>
>>>char * my_strrev(char *s){
>>> char t;
>>> char *e = s+strlen(s)-1;
>>> while(e>s){
>>> t = *s;
>>> *s++ = *e;
>>> *e-- = t;
>>> }
>>>}
>>>>
>>>I'm sure it breaks some sort of ISO magic,
>>>
>>Not "magic" but it has undefined behaviour on empty strings.

>>
>It also has the fatal error (to me) of returning a char*.

>
The fatal error is that is does *not* return a char * :-)

Please notice the name of the function before we get too carried away
here ...

And of course, me not returning anything ... :-; Another cut and paste
mistake .... No more me posting code untested (with the caveat included)
to "get the idea".

[Richard]

Re: Highly efficient string reversal code

pete <pfiland@mindsp ring.comwrites:

Richard wrote:

>Richard<rgrdev @gmail.comwrite s:
>>

>>pete <pfiland@mindsp ring.comwrites:
>>>
>>>Richard wrote:
>>>>
>>>>char * my_strrev(char *s){
>>>> char t;
>>>> char *e = s+strlen(s);
>>>> while(e-->s){
>>>>Is that now defined? or, after a 14 hour day, am I talking rubbish here?
>>>>>
>>>>Can e not be decremented to a value "smaller" than s?
>>>That operation would be undefined.
>>>>
>>>An object pointer can have only 4 different kinds of values:
>>>1 Address of an object
>>>2 One more than the address of an object
>>>3 null pointer value
>>>4 indeterminate value
>>So whats an indeterminate value in this case?
>>>
>>Since the "--" is done after the compare is this still "undefined
>>behaviour"?

>
Yes.
>

>or to make my question more clear - does this mean the entire program is
>"undefined" ?

>
Yes.

OK, I learnt something there. I have been too lazy with certain aspects
(and I'm not referring to the silly zero length error there) of my C
coding and I never, ever considered a line like

while(p-- s)


to have UDB risks. Probably one of the problems from associating C too
much with being a low level language designed to produce efficient code
tied to the underlying CPU HW and never really giving too much of a hoot
about platform independence.

To get me started on the path of righteousness can you point out where I
should learn/read that in the n1256.txt? As, frankly, I find the
standard document quite daunting and confusing.

[CBFalconer]

Re: Highly efficient string reversal code

"lovecreatesbea ...@gmail.com" wrote:

pete <pfil...@mindsp ring.comwrote:
>

.... snip ...

>

>It's undefined when attempting to reverse a zero length string.

>
How to reverse a zero length string for it has only a single
NULL terminating character : ) The reverse function quits if
this is the case.

Not mine, which was posted earlier. It also considers a NULL
passed in as indicating an empty string, and returns 0 (for input
length).

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home .att.net>
Try the download section.

[CBFalconer]

Re: Highly efficient string reversal code

"lovecreatesbea ...@gmail.com" wrote:

>

.... snip ...

>
My version
>
char *reverse(char *p) {
char *p1, *p2, ch;
>
for (p1 = p; *(p1 + 1); p1++) ;
for (p2 = p; p2 < p1; p2++, p1--)
ch = *p2, *p2 = *p1, *p1 = ch;
return p;
}

Much better. It still doesn't handle a NULL input, and has the
error of returning the string pointer rather than the string
length. Which is only an error in optimization, not coding.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home .att.net>
Try the download section.

[CBFalconer]

Re: Highly efficient string reversal code

Ben Bacarisse wrote:

"lovecreatesbea ...@gmail.com" <lovecreatesbea uty@gmail.comwr ites:
>

.... snip ...

>

>My version
>>
>char *reverse(char *p) {
> char *p1, *p2, ch;
>>
> for (p1 = p; *(p1 + 1); p1++) ;

>
If p points to an empty string this, too, is probably UB. It may
not be -- one would have to see the call, but you should not even
risk this. A call like: char test[10]; test[0] = 0; reverse(test);
is bad news!

I think that is OK. The above for does nothing except set p1 == p.

>

> for (p2 = p; p2 < p1; p2++, p1--)
> ch = *p2, *p2 = *p1, *p1 = ch;
> return p;
>}

and this one does nothing because p2 is not < p1. Both are at p.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home .att.net>
Try the download section.

[Peter Nilsson]

Re: Highly efficient string reversal code

Richard<rgr...@ gmail.comwrote:

>>An object pointer can have only 4 different kinds of
>>values:
>>1    Address of an object
>>2    One more than the address of an object
>>3    null pointer value
>>4    indeterminate value

5 Address of a function

OK, I learnt something there. I have been too lazy with
certain aspects (and I'm not referring to the silly zero
length error there) of my C coding and I never, ever
considered a line like
>
while(p-- s)
>
to have UDB risks. ...
<snip>
To get me started on the path of righteousness can
you point out where I should learn/read that in the
n1256.txt? As, frankly, I find the standard document
quite daunting and confusing.

Your path to righteousness begins with not slagging off
people who are prepared to do what you can't or won't.

That said, look at 6.5.6 (additive operators),
specifically p8.

"...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."

--
Peter

[arnuld]

Re: Highly efficient string reversal code

On Mon, 22 Sep 2008 18:22:25 -0400, CBFalconer wrote:

This is so horrible and faulty that I have to attach the
following. Don't forget to #include <strings.h>. Note that it
returns strlen.
>
/* =============== ======== */
/* reverse string in place */
size_t revstring(char *stg)
{
char *last, temp;
size_t lgh;
>
lgh = strlen(stg);
if (lgh 1) {
last = stg + lgh; /* points to '\0' */
while (last-- stg) {
temp = *stg; *stg++ = *last; *last = temp;
}
}
return lgh;
} /* revstring */

I have edited it a little bit to get pointer to pointer as function
argument and combined it with my get_single_word program and it works
little strange though. Also, your function is much easier to read IMHO:


#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>


enum { WORD_SIZE = 28 };
enum { GSW_OK, GSW_ENOMEM, GSW_ENORESIZE } ;


int get_single_word ( char** );
size_t revstring( char** );


int main(void)
{
char *word;

while( (GSW_OK == get_single_word (&word)) && (*word) )
{
revstring( &word );
printf("Reverse d: [ %s ]\n", word);
}

return 0;
}



/* reverse string in place */
size_t revstring(char **stg)
{
char *last, temp;
size_t lgh;

lgh = strlen(*stg);
if (lgh 1) {
last = *stg + lgh; /* points to '\0' */
while (last-- *stg)
{
temp = **stg;
**stg++ = *last;
*last = temp;
}
}
return lgh;
}



int get_single_word ( char** ppc )
{
unsigned ele_num;
int ch;
size_t word_length, word_length_int erval;
char* word_begin;
char* new_mem;

ele_num = 0;

word_length = WORD_SIZE;
word_length_int erval = 2;



*ppc = malloc(word_len gth * sizeof(**ppc));
word_begin = *ppc;


if( NULL == ppc )
{
return GSW_ENOMEM;

}


while( (EOF != (ch = getchar())) && isspace(ch) )
{
continue; /* trailing whitespace */
}


if( EOF != ch )
{
*word_begin++ = ch;
ele_num = 1;
}


while( (EOF != (ch = getchar())) && (! isspace(ch)) )
{
if( (word_length - 1) == ele_num++ )
{
new_mem = realloc( *ppc, (word_length_in terval * word_length * sizeof **ppc) );
*ppc = new_mem;

if( new_mem )
{
word_begin = new_mem + (word_begin - *ppc);
word_length *= word_length_int erval;
*ppc = new_mem;
}
else
{
*word_begin = '\0';
return GSW_ENORESIZE;
}
}

*word_begin++ = ch;
}


*word_begin = '\0';

return GSW_OK;
}

=============== ==== OUTPUT =============== ======
[arnuld@dune ztest]$ gcc -ansi -pedantic -Wall -Wextra reverse-string.c
[arnuld@dune ztest]$ ./a.out
Ben
Reversed: [ neB ]
CBFalconer
Reversed: [ rBFalconeC ]
comp.kang.c++
Reversed: [ +omp.kang.c+c ]
[arnuld@dune ztest]$



--

https://www.lispmachine.wordpress.com

my email is @ the above blog.
Google Groups is Blocked. Reason: Excessive Spamming

[Richard]

Re: Highly efficient string reversal code

Peter Nilsson <airia@acay.com .auwrites:

Richard<rgr...@ gmail.comwrote:

>>>An object pointer can have only 4 different kinds of
>>>values:
>>>1    Address of an object
>>>2    One more than the address of an object
>>>3    null pointer value
>>>4    indeterminate value

>
5 Address of a function
>

>OK, I learnt something there. I have been too lazy with
>certain aspects (and I'm not referring to the silly zero
>length error there) of my C coding and I never, ever
>considered a line like
>>
>while(p-- s)
>>
>to have UDB risks. ...
><snip>
>To get me started on the path of righteousness can
>you point out where I should learn/read that in the
>n1256.txt? As, frankly, I find the standard document
>quite daunting and confusing.

>
Your path to righteousness begins with not slagging off
people who are prepared to do what you can't or won't.

Hold on - I still dont hold with the other version from cbf. Frankly any
prodding he gets is his own fault - he spends 90% of his posts doing
much the same. And I dont slag off correct code either. I do however
slag off ridiculous bullying and silly preening with such claims as "I
dont need a debugger and neither do you" or "your debugger uses numbers
for pointers? Really"? etc etc etc . It makes this group a very tense
and strange place to be at times.

Anyway I appreciate the link.

>
That said, look at 6.5.6 (additive operators),
specifically p8.
>
"...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."

Now back to "undefined" .

And my code.

>while(p-- s)

Where does "undefined" in any shape or form indicate that there will be
knock on effects outside of the value of the variable in question
considering it is not used anymore? And if that variable is not used
anymore does it really matter? Its like using (or not using rather) an
uninitialised pointer.

Yes, I know "undefined" can mean "anything", but lets stay real here for
a moment. Possibly "undefined" is "defined" to mean "undefined for that
variable in question".

Or?

[Keith Thompson]

Re: Highly efficient string reversal code

Richard<rgrdev@ gmail.comwrites :
[...]

Now back to "undefined" .
>
And my code.
>

>>while(p-- s)

>
Where does "undefined" in any shape or form indicate that there will be
knock on effects outside of the value of the variable in question
considering it is not used anymore? And if that variable is not used
anymore does it really matter? Its like using (or not using rather) an
uninitialised pointer.
>
Yes, I know "undefined" can mean "anything", but lets stay real here for
a moment. Possibly "undefined" is "defined" to mean "undefined for that
variable in question".
>
Or?

No, "undefined behavior" means exactly that:

behavior, upon use of a nonportable or erroneous program construct
or of erroneous data, for which this International Standard
imposes no requirements

NOTE Possible undefined behavior ranges from ignoring the
situation completely with unpredictable results, to behaving
during translation or program execution in a documented manner
characteristic of the environment (with or without the issuance of
a diagnostic message), to terminating a translation or execution
(with the issuance of a diagnostic message).

In the case of constructing a pointer just before the beginning of an
object, it will very often be harmless. But suppose an implementation
uses segmented memory, and the object just happens to be start at the
very beginning of a segment. And suppose the machine has special
instructions that operate on addresses, and that trap if you attempt
to construct a pointer outside the segment you started from (which
would be quite useful for catching errors). The point is that the
standard is specifically designed to allow such an implementation.

I feel safe in assuming that decrementing a pointer won't actually
make demons fly out of my nose. And if it did, I would complain
bitterly to the the implementer for making the implementation behave
in such a rude manner. But among my many complaints, I would not be
able to claim that the implementation fails to conform to the C
standard.

--
Keith Thompson (The_Other_Keit h) kst-u@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"