brain teasers

[Richard Heathfield]

Gunvant Patil said:

Yikes..!!! it didn't shown me any warnings when i build that binary
using -Wall.

That should be adequate proof, if proof were needed, that gcc's -Wall
does *not* mean "enable all warnings".

 

[Flash Gordon]

Daniel Rudy wrote, On 06/04/07 07:11:

At about the time of 4/5/2007 8:48 PM, Ian Collins stated the following:

Man, you guys are flat ruthless on my coding algorithms and style.

Yes, which is a good thing.

> My
original one was shot down, then my malloc one caused an argument...

People here like arguing (in the sense of debating rather than shouting
matches). It can be fun.

> In
taking everyone's suggestions into account. I have devised the
following routine:

void swap(void *a, void *b, size_t size)
{
size_t i; /* generic counter */

Please do not use tabs when posting to news groups. Sometimes they get
stripped from posts.

unsigned char tmp; /* temp */
unsigned char *d1, *d2; /* data pointers */

d1 = a;
d2 = b;

You could have done the initialising on declaration
unsigned char *d1 = a;
unsigned char *d2 = b;

for (i = 0; i < size; i++)
{
tmp = *d1;
*d1 = *d2;
*d2 = tmp;
if (i < (size - 1))
{
d1++;
d2++;
}
}
return;
}

That one doesn't use malloc, swaps 1 byte at a time, and can be used
with any datatype. It will not increment d1 and d2 beyond the size either.

You do not need to worry about that last point since C explicitly allows
it. So here is my tidied up version...
void swap(void *a, void *b, size_t size)
{
unsigned char tmp;
unsigned char *d1 = a;
unsigned char *d2 = b;

while (size > 0) {
tmp = *d1;
*d1++ = *d2;
*d2++ = tmp;
size--;
}
}

Or, to be a bit cleverer and do block copies

void swap(void *a, void *b, size_t size)
{
unsigned char tmp[64];
unsigned char *d1 = a;
unsigned char *d2 = b;

while (size >= sizeof tmp) {
memcpy(tmp, d1, sizeof tmp);
memcpy(d1, d2, sizeof tmp);
memcpy(d2, tmp, sizeof tmp);
size -= sizeof tmp;
d1 += sizeof tmp;
d2 += sizeof tmp;
}

if (size > 0) {
memcpy(tmp, d1, size);
memcpy(d1, d2, size);
memcpy(d2, tmp, size);
}
}

Or to get those benefits without calling memcpy, abuse structs:

void swapstr(void *a, void *b, size_t size)
{
struct buf {
unsigned char arr[64];
};
struct buf tmp;
struct buf *d1 = a;
struct buf *d2 = b;

while (size >= sizeof tmp) {
tmp = *d1;
*d1++ = *d2;
*d2++ = tmp;
size -= sizeof tmp;
}

while (size > 0) {
tmp = *d1;
*d1++ = *d2;
*d2++ = tmp;
size--;
}
}

Of course, which is most efficient will depend. Personally I've never
had to worry about the efficiency of swapping.

 

[Daniel Rudy]

At about the time of 4/6/2007 12:37 AM, Richard Heathfield stated the
following:

Daniel Rudy said:



Don't you think that's a good thing?

In most cases, yes. In fact, I've actually learned alot of stuff by it.
But, beyond that it's just nitpicking which gets annoying... :/

All of us have been shot down in flames a few times here in c.l.c, and
it has generally been a useful experience.
Agreed.


You'll need a header for that size_t.

True, and I'm sure that most people are aware of it.

Your indenting is broken. <g,d&rvf>

This is a matter of style. When I code using my tools, that's the
indenting that I use. When I code on the fly in the group, I generally
use tabs to indent. Look at some of my past posts in the group, even in
this thread.

I think you could profitably swap more bytes at a time than that, using
memcpy. Who told you swapping many bytes at once was a bad idea?

I think it was user923005 who said something about performance...And I
believe it was Keith T. who mentioned swapping one byte at a time.


--
Daniel Rudy

Email address has been base64 encoded to reduce spam
Decode email address using b64decode or uudecode -m

Why geeks like computers: look chat date touch grep make unzip
strip view finger mount fcsk more fcsk yes spray umount sleep

 

[zebedee]

Or even in modern C:

void swap( void *a, void *b, size_t size )
{
char temp[size];

memcpy(temp, a, size);
memcpy(a, b, size);
memcpy(b, temp, size);
}

How 'bout:
int swap (void *a, void *b)
{
void *temp;
if (sizeof *a != sizeof *b) {

Have you tried to compile this?

retun 0;

Or this?

I doubt it.

"/tmp/foo.c", line 4: error: operand of "sizeof" cannot have incomplete type
if (sizeof *a != sizeof *b) {
^
"/tmp/foo.c", line 4: error: operand of "sizeof" cannot have incomplete type
if (sizeof *a != sizeof *b) {
^
"/tmp/foo.c", line 5: error: identifier "fputs" is not defined
fputs("Attempt to swap variables of incompatible types", stderr);
^
"/tmp/foo.c", line 5: error: identifier "stderr" is not defined
fputs("Attempt to swap variables of incompatible types", stderr);
^
"/tmp/foo.c", line 8: error: identifier "malloc" is not defined
temp = malloc(sizeof *a);
^
"/tmp/foo.c", line 8: error: operand of "sizeof" cannot have incomplete type
temp = malloc(sizeof *a);
^
"/tmp/foo.c", line 9: error: identifier "NULL" is not defined
if (temp == NULL) {
^
"/tmp/foo.c", line 10: error: identifier "perror" is not defined
perror("Unable to allocate memory");
^
"/tmp/foo.c", line 13: error: identifier "memcpy" is not defined
memcpy(temp, a, sizeof *a);
^
"/tmp/foo.c", line 13: error: operand of "sizeof" cannot have incomplete
type
memcpy(temp, a, sizeof *a);
^
"/tmp/foo.c", line 14: error: identifier "memcpy" is not defined
memcpy(a, b, sizeof *a);
^
"/tmp/foo.c", line 14: error: operand of "sizeof" cannot have incomplete
type
memcpy(a, b, sizeof *a);
^
"/tmp/foo.c", line 15: error: identifier "memcpy" is not defined
memcpy(b, temp, sizeof *a);
^
"/tmp/foo.c", line 15: error: operand of "sizeof" cannot have incomplete
type
memcpy(b, temp, sizeof *a);
^
"/tmp/foo.c", line 16: error: identifier "free" is not defined
free(temp);
^
"/tmp/foo.c", line 17: error: identifier "retun" is not defined
retun 0;
^
"/tmp/foo.c", line 17: error: expected ';'
retun 0;
^
"/tmp/foo.c", line 18: warning: function "swap" should return a value
}
^

17 errors found compiling "/tmp/foo.c".

 

[zebedee]

Or even in modern C:

void swap( void *a, void *b, size_t size )
{
char temp[size];

memcpy(temp, a, size);
memcpy(a, b, size);
memcpy(b, temp, size);
}

How 'bout:
int swap (void *a, void *b)
{
void *temp;
if (sizeof *a != sizeof *b) {

Have you tried to compile this?

retun 0;

Or this?

One doubts it.

"/tmp/foo.c", line 4: error: operand of "sizeof" cannot have incomplete type
if (sizeof *a != sizeof *b) {
^
"/tmp/foo.c", line 4: error: operand of "sizeof" cannot have incomplete type
if (sizeof *a != sizeof *b) {
^
"/tmp/foo.c", line 5: error: identifier "fputs" is not defined
fputs("Attempt to swap variables of incompatible types", stderr);
^
"/tmp/foo.c", line 5: error: identifier "stderr" is not defined
fputs("Attempt to swap variables of incompatible types", stderr);
^
"/tmp/foo.c", line 8: error: identifier "malloc" is not defined
temp = malloc(sizeof *a);
^
"/tmp/foo.c", line 8: error: operand of "sizeof" cannot have incomplete type
temp = malloc(sizeof *a);
^
"/tmp/foo.c", line 9: error: identifier "NULL" is not defined
if (temp == NULL) {
^
"/tmp/foo.c", line 10: error: identifier "perror" is not defined
perror("Unable to allocate memory");
^
"/tmp/foo.c", line 13: error: identifier "memcpy" is not defined
memcpy(temp, a, sizeof *a);
^
"/tmp/foo.c", line 13: error: operand of "sizeof" cannot have incomplete
type
memcpy(temp, a, sizeof *a);
^
"/tmp/foo.c", line 14: error: identifier "memcpy" is not defined
memcpy(a, b, sizeof *a);
^
"/tmp/foo.c", line 14: error: operand of "sizeof" cannot have incomplete
type
memcpy(a, b, sizeof *a);
^
"/tmp/foo.c", line 15: error: identifier "memcpy" is not defined
memcpy(b, temp, sizeof *a);
^
"/tmp/foo.c", line 15: error: operand of "sizeof" cannot have incomplete
type
memcpy(b, temp, sizeof *a);
^
"/tmp/foo.c", line 16: error: identifier "free" is not defined
free(temp);
^
"/tmp/foo.c", line 17: error: identifier "retun" is not defined
retun 0;
^
"/tmp/foo.c", line 17: error: expected ';'
retun 0;
^
"/tmp/foo.c", line 18: warning: function "swap" should return a value
}
^

17 errors found compiling "/tmp/foo.c".

 

[Richard Heathfield]

Daniel Rudy said:

At about the time of 4/6/2007 12:37 AM, Richard Heathfield stated the
following:

This is a matter of style. When I code using my tools, that's the
indenting that I use.

You outdent the bodies of for-loops to the left margin *on purpose*?
Well, okay, if that's what you want, but, er, why?

I think it was user923005 who said something about performance...And I
believe it was Keith T. who mentioned swapping one byte at a time.

You might want to ask him why he suggested that. It sounds silly to me.

 

[Chris Torek]

Daniel Rudy said:

You outdent the bodies of for-loops to the left margin *on purpose*?
Well, okay, if that's what you want, but, er, why?

I think you left out an important sentence here (maybe you did not
realize it was important): his tools put in a tab (as in '\t')
character.

This tab came through fine on *my* usenet server, so that the
inside of the loop was more-indented. It appears that whatever
software sits between you and Daniel Rudy, however, ate the tab.
The fact that some Usenet servers (and/or other Usenet article
delivery systems) eat tabs are why I have my software run all
my postings through the "expand" program by default.

 

[Keith Thompson]

Gunvant Patil said:

That should be adequate proof, if proof were needed, that gcc's -Wall
does *not* mean "enable all warnings".

Indeed. "-pedantic" is the option you need to enable that warning.

 

[Kelsey Bjarnason]

I see no real evidence that he thinks return is a function. It's more
likely that he either thinks (incorrectly) that a return statement
requires parentheses, or (questionably) that using parentheses is good
style. There is precedent for the latter point of view; see K&R1, for
example.

Personally, I strongly prefer not to use unnecessary parentheses on a
return statement, but of course "return(0);" is perfectly legal.

A lot of people - myself included - have developed a habit of using
parentheses in return. Why? Who knows? It's common enough it shouldn't
be confusing, even if it is redundant. I don't advocate redundancy in
general, but this is one of those harmless cases where nothing is really
lost in the use of it.

 

[Keith Thompson]

Daniel Rudy said:

At about the time of 4/6/2007 12:37 AM, Richard Heathfield stated the
following: [...]

I think you could profitably swap more bytes at a time than that,
using memcpy. Who told you swapping many bytes at once was a bad
idea?

I think it was user923005 who said something about performance...And I
believe it was Keith T. who mentioned swapping one byte at a time.

You might want to ask him why he suggested that. It sounds silly to me.

I suggested swapping one byte at a time as a generic alternative to
swapping entire objects at a time, which could run out of memory if
the objects being swapped are very large. Swapping medium-sized
chunks is likely to be more efficient, but it's also more complex; you
need to allow for the possibility that the object size isn't a
multiple of the chunk size, and determining the optimal chunk size is
extremely system-specific (and may depend on the alignments of the
objects being swapped).

In practice, swapping usually involves small objects. As someone has
already pointed out in this thread, if you need to swap large objects,
you're probably better off swapping pointers. And swapping is such a
simple operation that there isn't really a need to write a generic
swap routine; it's easy enough to code it directly, which lets the
compiler take advantage of the specific type being swapped.

int x, y;
...
{
/* swap x and y */
const int old_x = x;
x = y;
y = old_x;
}

On the other hand, there's some small risk of getting it wrong if
you're not careful (I initially wrote "y = x;", but I corrected it
immediately).

 

[Default User]

Daniel Rudy said:


You outdent the bodies of for-loops to the left margin *on purpose*?
Well, okay, if that's what you want, but, er, why?

It didn't appear that way to me in Daniel's orginal posts, only in your
quotes.



Brian

 

[Richard Heathfield]

Keith Thompson said:

I suggested swapping one byte at a time as a generic alternative to
swapping entire objects at a time, which could run out of memory if
the objects being swapped are very large.

Okay, that sounds fair enough, although...

Swapping medium-sized
chunks is likely to be more efficient,
Indeed.

but it's also more complex;

Only a bit.

you need to allow for the possibility that the object size isn't a
multiple of the chunk size,

That's easy enough.

and determining the optimal chunk size is
extremely system-specific (and may depend on the alignments of the
objects being swapped).

But you don't actually need to do this, at least not if the alternative
is single-byte swapping! You can bet your best friend's mother's
cousin's accountant's shirt that pretty well any finger-in-the-air
chunk size is going to be better than 1.

In practice, swapping usually involves small objects. As someone has
already pointed out in this thread, if you need to swap large objects,
you're probably better off swapping pointers.
Aye.

And swapping is such a
simple operation that there isn't really a need to write a generic
swap routine;

Ha! Yeah, I thought that too once. But I ended up finding a need.
Either that, or I under-analysed the problem (or, just perhaps,
over-analysed it).

 

[Stephen Sprunk]

Yikes..!!! it didn't shown me any warnings when i build that binary
using -Wall.

You need to use "-ansi -pedantic -W -Wall" to get everything.

I'll leave understanding the rationale of -Wall not including all warnings
as an exercise for the reader

S

 

[Richard Heathfield]

Default User said:

It didn't appear that way to me in Daniel's orginal posts, only in
your quotes.

Oh. Tabs again, I guess. Nothing to see here, move along...

 

[Flash Gordon]

Keith Thompson wrote, On 06/04/07 19:51:

Indeed. "-pedantic" is the option you need to enable that warning.

You also need -ansi to get some of the others warnings you should want.
If you want as close as gcc comes to C99 look in the manual and also
look up the limitations.

 

[Default User]

Default User said:


Oh. Tabs again, I guess. Nothing to see here, move along...

Possibly, I suppose. The indents were pretty small though.



Brian

 

[CBFalconer]

Daniel Rudy said:

#define MAXSWAP 32 /* maximum size of variable swap */
int swap(void *a, void *b, int size)
{
char temp[MAXSWAP]; /* temp buffer */

if (size > MAXSWAP) return(-1);
memcpy(temp, a, size);
memcpy(a, b, size);
memcpy(b, temp, size);
return(0);
}

Now what's wrong with that?

Not very much. Here's a less restrictive solution:

#include <string.h>

#define MAXSWAP 32

void swap(void *va, void *vb, size_t size)
{
unsigned char *a = va;
unsigned char *b = vb;
unsigned char temp[MAXSWAP] = {0};

while(size >= MAXSWAP)
{
memcpy(temp, a, MAXSWAP);
memcpy(a, b, MAXSWAP);
memcpy(b, temp, MAXSWAP);
size -= MAXSWAP;
a += MAXSWAP;
b += MAXSWAP;
}
memcpy(temp, a, size);
memcpy(a, b, size);
memcpy(b, temp, size);
return;
}

It is possible that this could be done more elegantly (eliminating
the duplicated code). Given the time of day here, I'll leave that
as an exercise.

Being a believer in the KISS principle, I would write it as:

void swap(void *va, void *vb, size_t size) {
unsigned char *a = va;
unsigned char *b = vb;
unsigned char t;

if (va != vb)
while (size--) {
t = *a; *a++ = *b; *b++ = t;
}
}

and let the compiler optimize. I would not alter swap unless
profiling showed it to be a critical cpu eater. I might even
eliminate the va != vb test. If I kept it I would move the
initialization of a and b to after the test.

--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
<http://www.securityfocus.com/columnists/423>
<http://www.aaxnet.com/editor/edit043.html>

"A man who is right every time is not likely to do very much."
-- Francis Crick, co-discover of DNA
"There is nothing more amazing than stupidity in action."
-- Thomas Matthews

 

[CBFalconer]

.... snip ...

You need to use "-ansi -pedantic -W -Wall" to get everything.

I'll leave understanding the rationale of -Wall not including all
warnings as an exercise for the reader

I suspect it is historic. At one point -Wall enabled all. Then
more were needed. In order to not disturb old makefiles, -W was
added.

--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
<http://www.securityfocus.com/columnists/423>
<http://www.aaxnet.com/editor/edit043.html>

"A man who is right every time is not likely to do very much."
-- Francis Crick, co-discover of DNA
"There is nothing more amazing than stupidity in action."
-- Thomas Matthews

 

[Richard Heathfield]

Stephen Sprunk said:

You need to use "-ansi -pedantic -W -Wall" to get everything.

That still doesn't give you everything.

 

[Keith Thompson]

Stephen Sprunk said:

That still doesn't give you everything.

Well, that's good, because I don't know where I'd put it.