String Reverse Question

[Keith Thompson]

"Keith Thompson" <[email protected]> a écrit dans le message de
[snipped]

On the other hand, if we want to allow for the possibility that the
declaration of p could be changed so it points to something bigger
than one byte (perhaps a wchar_t), we'd want to use:

p = malloc(len * (sizeof *p + 1));

to allocate one additional object rather than one additional byte.

I guess you meant p = malloc( (len+1)*sizeof*p ); to allocate one
additional object.

D'oh! Yes, you're right; sorry about that.

 

[Joe Wright]

Joe Wright a écrit :



Just some questions about this code:

1) What happens if s is a null pointer? Is strlen(s) supposed to work?
2) If e value is (s - 1), isn't the comparison (b < e) an undefined
behaviour, as e is no more pointing to an object or one element past
that object?

Right you are, dammit. strlen() could kill us, passed a NULL
pointer. Your second point is more interesting. Assuming strlen(s)
is 0, e == (s - 1) as you say, but I don't see it as an error.
First, we don't know (and can't tell) that *s is the first element
of an object. Second, 'while (b < e)' does not dereference e, it
simply examines it.

How about this..

char *revstr(char *s) {
char t, *b = s, *e;
if (s) {
e = s + strlen(s) -1;
while (b < e) t = *b, *b++ = *e, *e-- = t;
}
return s;
}

 

[CBFalconer]

It depends on your own requirements : would you like the user of
your functions take care about null pointers and memory handling
or not ? As Christopher said, most of standard functions of
<string.h> need to pay careful attention with null pointers. I
think it's fine to code in the same way as well I think it's
fine to prevent any memory access violation. If it were for
business, I would implement my functions according to the given
requirements. For my personal stuff, I always handle null pointers.

Finally, I missed to propose you my implementation of string
reversing, here it is :

.... snip <code> ....

As long as we are bandying about implementations, here's mine. I
avoid allocating memory within it, and the trap of returning a
pointer to the reversed string.

/* ======================================= */
/* reverse string in place. Return length */
size_t revstring(char *string)
{
char *last, temp;
size_t lgh;

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

 

[Rakesh]

Oh - Ooops !!

Sorry about the C++ style comments . I use Google's group interface
for posting mine as i find it much more comfortable than receiving
them on my HDD !!

 

[Rakesh]

char * strrev (const char *s)
{
char * p;
int i, j;
j = strlen(s)
if (p = calloc(1, j+1))

Just a bit curious here - Is it ok to allocate locally here, and
return it. Would that not lead to memory leaks.

 

[Ben Pfaff]

Just a bit curious here - Is it ok to allocate locally here, and
return it. Would that not lead to memory leaks.

It's surprising that you're asking that question, because your
original version also did memory allocation, although it was
written in C++ and used the `new' operator. I think you should
probably reassess what you think you know about memory allocation
in C and C++.

 

[pete]

What happens if s is indeterminate ?
What happens if s points to an object
which doesn't contain a null character ?
Why would you pass a null pointer to a string reversal function ?
What do null pointers have to do with strings ?

Right you are, dammit. strlen() could kill us, passed a NULL
pointer. Your second point is more interesting. Assuming strlen(s)
is 0, e == (s - 1) as you say, but I don't see it as an error.
First, we don't know (and can't tell) that *s is the first element
of an object.

You're saying that you think that a string reversal function
should be able to handle a NULL argument,
but not an argument which points to the lowest byte of an object ?

Second, 'while (b < e)' does not dereference e, it
simply examines it.

Merely calculating (s - 1) is sufficient for undefined behavior
if s points to the lowest byte of an object.

 

[Old Wolf]

p = new char[len + 1];

This (new) is C++. Don't post it here. ITYM

p=malloc( len*sizeof(*p)+1 );

p = malloc( (len + 1) * sizeof *p);

Of course, if sizeof *p == 1 as it does here, then these expressions
are the same, but the point of "sizeof *p" is to be able to avoid problems
related to what the type of "p" is.

 

[Irrwahn Grausewitz]

:

.... snip <code> ....

As long as we are bandying about implementations, here's mine.

<code snipped>

And yet another in-place string reversal function; like Chuck's
version it expects a valid string, but it avoids the explicit
check for a zero-length string:

char *igStrrev( char *str )
{
char chtmp;
char *forth = str;
char *back = str + strlen( str );

while ( forth < back )
{
chtmp = *forth;
*forth++ = *--back;
*back = chtmp;
}
return str;
}

Regards

 

[Richard Delorme]

pete a écrit :

What happens if s is indeterminate ?
What happens if s points to an object
which doesn't contain a null character ?
Why would you pass a null pointer to a string reversal function ?
> What do null pointers have to do with strings ?

The function receives a pointer to char. I also notice that the above
function cannot portably deal with literal strings but contains a test
to see if s is a null pointer. So the above code as to do with null
pointer, but not necessarily with strings. I don't mean that a reversal
function is supposed to work on any broken input, but I think the code
should be consistent. The problem is that the 'if (s)' test comes after
a call to strlen(), so it is useless, as strlen() exhibits undefined
behaviour (e.g. on my implemetation, it crashes) when receiving a null
pointer. So the 'if (s)' test is either misplaced or useless.

 

[Richard Delorme]

Joe Wright a écrit :

Right you are, dammit. strlen() could kill us, passed a NULL pointer.
Your second point is more interesting. Assuming strlen(s) is 0, e == (s
- 1) as you say, but I don't see it as an error. First, we don't know
(and can't tell) that *s is the first element of an object. Second,
'while (b < e)' does not dereference e, it simply examines it.

The part of the standard dealing with comparison operator says that both
b and e should point to the same object or one element past that object,
otherwise the behaviour is undefined.

How about this..

char *revstr(char *s) {
char t, *b = s, *e;
if (s) {
e = s + strlen(s) -1;
while (b < e) t = *b, *b++ = *e, *e-- = t;

I would prefer:
e = s + strlen(s);
while (b < e--) t = *b, *b++ = *e, *e = t;

 

[Irrwahn Grausewitz]

The part of the standard dealing with comparison operator says that both
b and e should point to the same object or one element past that object,
otherwise the behaviour is undefined.

Joe Wright a écrit : Correct.


I would prefer:
e = s + strlen(s);
while (b < e--) t = *b, *b++ = *e, *e = t;

^^^
This version shows exactly the problem of calculating an invalid
pointer value when passing an empty string. Try this:

e = s + strlen(s);
while (b < e) t = *b, *b++ = *--e, *e = t;

Regards

 

[Irrwahn Grausewitz]

^^^
This version shows exactly the problem of calculating an invalid
pointer value when passing an empty string.

Unless you want to keep the if(s) part, maybe I misread; if so, sorry.

Regards

 

[pete]

pete a écrit :

The function receives a pointer to char. I also notice that the above
function cannot portably deal with literal strings but contains a test
to see if s is a null pointer. So the above code as to do with null
pointer, but not necessarily with strings.
I don't mean that a reversal
function is supposed to work on any broken input, but I think the code
should be consistent.
The problem is that the 'if (s)' test comes after
a call to strlen(), so it is useless, as strlen() exhibits undefined
behaviour (e.g. on my implemetation, it crashes) when receiving a null
pointer. So the 'if (s)' test is either misplaced or useless.

#include <string.h>

char *revstr(char *s)
{
if (s != NULL && *s != '\0') {
char *p, *q, swap;

q = p = s;
q += strlen(q);
while (--q > p) {
swap = *q;
*q = *p;
*p++ = swap;
}
}
return s;
}

 

[Irrwahn Grausewitz]

Unless you want to keep the if(s) part, maybe I misread; if so, sorry.

Forget about the last comment. Sunday sillyness.

Regards

 

[pete]

<code snipped>

And yet another in-place string reversal function; like Chuck's
version it expects a valid string, but it avoids the explicit
check for a zero-length string:

But it does an unnecessary swap of the middle byte with itself
in odd length strings.

 

[Irrwahn Grausewitz]

But it does an unnecessary swap of the middle byte with itself
in odd length strings.

Exactly like Chuck's version. Mine just saves an unnecessary
additional check, as I said.

Regards

 

[Richard Delorme]

Irrwahn Grausewitz a écrit :

Correct.

I disagree. If s is an empty string, e is an invalid pointer and it is
used in the following comparison.

^^^
This version shows exactly the problem of calculating an invalid
pointer value when passing an empty string. Try this:

An invalid pointer is computed, but it is not used, so I do not think
there is any problem.

e = s + strlen(s);
while (b < e) t = *b, *b++ = *--e, *e = t;

This code is fine too.

 

[Al Bowers]

Irrwahn Grausewitz a écrit :



I disagree. If s is an empty string, e is an invalid pointer and it is
used in the following comparison.



An invalid pointer is computed, but it is not used, so I do not think
there is any problem.

I see a problem.
<Standard>
J.2 Undefined Behavior
.....
— Addition or subtraction of a pointer into, or just beyond,
an array object and an integer type produces a result that
does not point into, or just beyond, the same array
object (6.5.6).
</Standard>

Since the argument s typically points to the beginning of an
array of characters that contain a string, then, assuming the
argument is an empty string and e == s, once you decrement e
you have undefined behavior.

 

[Irrwahn Grausewitz]

Irrwahn Grausewitz a écrit :

I disagree. If s is an empty string, e is an invalid pointer and it is
used in the following comparison.

Dread, as I already said in another post: Sunday silliness.... :-/

An invalid pointer is computed, but it is not used, so I do not think
there is any problem.

Sorry, no, you invoke undefined behaviour by *computing* the invalid
value (Cf. ISO/IEC 9899:1999 6.5.6p8).

This code is fine too.

It's the only one of the three version, that does not invoke undefined
behaviour when fed with an empty string.

Regards