brain teasers

[Army1987]

Have you tried to compile this?


Or this?

No... whoops...

 

[Flash Gordon]

Richard Bos wrote, On 05/04/07 12:29:

It was new to all of us, once. Those of us who understand programming
quickly learnt that such schoolboy tricks are not worth looking for.

Should I be proud of never having invented the XOR trick? In fact, I
can't remember ever doing anything similar. The only times I've ever
(that I can remember) looked for clever tricks it was because I already
knew I had performance problems to solve and had already reached the
point where I was programming in assembler.

I have, on the other hand, been clever in selecting algorithms and
clever in the way I have designed things

 

[Martin Ambuhl]

a = a+b
b = a-b;
a = a-b;

A swap should not raise the specter of overflow or underflow. Yours is
not an answer. Further, the question was about swapping variables, not
numbers. Your "answer" is obviously nonsense for non-arithmetic types.

 

[Daniel Rudy]

At about the time of 4/5/2007 4:10 AM, Army1987 stated the following:

if (sizeof *a != sizeof *b) {

I think you mean sizeof(*a) and sizeof(*b), but does that construct even
work for a void *?


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

 

[Ian Collins]

At about the time of 4/5/2007 4:10 AM, Army1987 stated the following:


I think you mean sizeof(*a) and sizeof(*b), but does that construct even
work for a void *?

No, you can't take the sizeof void.

 

[Daniel Rudy]

At about the time of 4/5/2007 12:20 AM, Ian Collins stated the following:

To the OP:

#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?

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);
}

I just came up with one even better....

int swap(void *a, void *b, size_t size)
{
void *ptr;

ptr = malloc(size);
if (ptr == NULL) return(-1);
memcpy(ptr, a, size);
memcpy(a, b, size);
memcpy(b, ptr, size);
free(ptr);
return(0);
}

That will swap *ANY* 2 data types of the same type, structs included.


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

 

[Ian Collins]

At about the time of 4/5/2007 12:20 AM, Ian Collins stated the following:

To the OP:

#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?

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);
}

I just came up with one even better....

Define better!

int swap(void *a, void *b, size_t size)
{
void *ptr;

ptr = malloc(size);
if (ptr == NULL) return(-1);
memcpy(ptr, a, size);
memcpy(a, b, size);
memcpy(b, ptr, size);
free(ptr);
return(0);

return isn't a function. Why not make the function void?

}

That will swap *ANY* 2 data types of the same type, structs included.

As would mine.

 

[Daniel Rudy]

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

At about the time of 4/5/2007 12:20 AM, Ian Collins stated the following:

Daniel Rudy wrote:

To the OP:

#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?
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);
}

I just came up with one even better....

Define better!

int swap(void *a, void *b, size_t size)
{
void *ptr;

ptr = malloc(size);
if (ptr == NULL) return(-1);
memcpy(ptr, a, size);
memcpy(a, b, size);
memcpy(b, ptr, size);
free(ptr);
return(0);

return isn't a function. Why not make the function void?

It needs to return an error indicator to the caller if malloc fails?

As would mine.

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

 

[Richard Heathfield]

Daniel Rudy said:

At about the time of 4/5/2007 4:10 AM, Army1987 stated the following:

I think you mean sizeof(*a) and sizeof(*b)
(Why(?))

, but does that construct
even work for a void *?

No.

 

[Richard Heathfield]

Daniel Rudy said:

I just came up with one even better....

int swap(void *a, void *b, size_t size)
{
void *ptr;

ptr = malloc(size);
if (ptr == NULL) return(-1);
memcpy(ptr, a, size);
memcpy(a, b, size);
memcpy(b, ptr, size);
free(ptr);
return(0);
}

That will swap *ANY* 2 data types of the same type, structs included.

Well, it might. Or it might not.

This is a classic case of a situation where malloc can fail and yet you
can recover and perform your task properly, albeit in a slightly
clumsier way than would be possible with the successful malloc call. To
return an error is a mistake, I think.

 

[Dave Vandervies]

viv342 said:


Pointlessly.

Temps are cheap, and the resulting code will be quicker and easier to
read than a hack. And, in any case, the hack for which you are
stretching only works for particular kinds of variable under particular
conditions.

Alternatively, write the code in a way that makes sense and use an
optimizing compiler:
--------
dave@goofy:~/clc (0) $ cat swap.c
void swap(int *a,int *b)
{
int t=*a;
*a=*b;
*b=t;
}
dave@goofy:~/clc (0) $ gcc -W -Wall -ansi -pedantic -O -S swap.c
dave@goofy:~/clc (0) $ cat swap.s
[Some framing removed, this is the generated code for the actual function
in its entirety]
swap:
pushl %ebp
movl %esp, %ebp
pushl %ebx
movl 8(%ebp), %edx
movl 12(%ebp), %ecx
movl (%edx), %ebx
movl (%ecx), %eax
movl %eax, (%edx)
movl %ebx, (%ecx)
movl (%esp), %ebx
leave
ret
--------

Two loads, two stores, no third variable.


dave

 

[Ian Collins]

Temps are cheap, and the resulting code will be quicker and easier to
read than a hack. And, in any case, the hack for which you are
stretching only works for particular kinds of variable under particular
conditions.

Alternatively, write the code in a way that makes sense and use an
optimizing compiler:
--------
dave@goofy:~/clc (0) $ cat swap.c
void swap(int *a,int *b)
{
int t=*a;
*a=*b;
*b=t;
}
dave@goofy:~/clc (0) $ gcc -W -Wall -ansi -pedantic -O -S swap.c
dave@goofy:~/clc (0) $ cat swap.s
[Some framing removed, this is the generated code for the actual function
in its entirety]
swap:
pushl %ebp
movl %esp, %ebp
pushl %ebx
movl 8(%ebp), %edx
movl 12(%ebp), %ecx
movl (%edx), %ebx
movl (%ecx), %eax
movl %eax, (%edx)
movl %ebx, (%ecx)
movl (%esp), %ebx
leave
ret

Also interesting is what Sun cc does with main if I add:

int main( void )
{
int a = 42;
int b = 32;

swap( &a, &b );

printf( "%d %d\n", a, b );
}

The generated code is:

main:
subl $16,%esp
push $42
push $32
push $.L21
call printf
addl $28,%esp
ret

!

 

[user923005]

To the OP:

#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?

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);

}

Certainly, the most elegant C version (due to C99 semantics). But all
of these solutions are a good study to show the beauty and elegance of
the C++ template.
Not only are there no function calls, but it looks more natural
{considering template <class Etype>}:
Etype Tmp = a;
b = c;
c = b;
b = Tmp;
I guess that in things like sorting (or other generic routines where
you do not know the size of what you are going to exchange) this will
make a significant difference in performance.

IMO-YMMV.

 

[user923005]

Daniel Rudy said:







Well, it might. Or it might not.

This is a classic case of a situation where malloc can fail and yet you
can recover and perform your task properly, albeit in a slightly
clumsier way than would be possible with the successful malloc call. To
return an error is a mistake, I think.

I agree. The place to handle the problem is in the exchange function
itself. Can you imagine the tedium of handling:
err = swap(&a,&b);
if (err)
{
/* Now what?...*/
}
in every place in the code in which an exchange is to take place?
Now if (for some reason) the error cannot be handled (e.g. a bad input
address) then it might be logical to return an error. But percolating
this type of error up the call stack is a stomach turning notion.

 

[user923005]

Now, in defense of C, there is a fairly elegant exchange that can be
implemented in terms of evil function macros, as illustrated nicely
here:

/*
* Modifications from vanilla NetBSD source:
* Add do ... while() macro fix
* Remove __inline, _DIAGASSERTs, __P
* Remove ill-considered "swap_cnt" switch to insertion sort,
* in favor of a simple check for presorted input.
*
* $PostgreSQL: pgsql/src/port/qsort.c,v 1.8.2.1 2006/03/21 19:49:19
tgl Exp $
*/

/* $NetBSD: qsort.c,v 1.13 2003/08/07 16:43:42 agc Exp $ */

/*-
* Copyright (c) 1992, 1993
* The Regents of the University of California. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above
copyright
* notice, this list of conditions and the following disclaimer in
the
* documentation and/or other materials provided with the
distribution.
* 3. Neither the name of the University nor the names of its
contributors
* may be used to endorse or promote products derived from this
software
* without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS''
AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE
LIABLE
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
GOODS
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY
OF
* SUCH DAMAGE.
*/

int ISORT_THRESHOLD = 7;
int MULTI_MEDIAN_EST = 7;

#include "c.h"


static char *med3(char *, char *, char *,
int (*) (const void *, const void *));
static void swapfunc(char *, char *, size_t, int);

#define min(a, b) ((a) < (b) ? (a) : (b))

/*
* Qsort routine based on J. L. Bentley and M. D. McIlroy,
* "Engineering a sort function",
* Software--Practice and Experience 23 (1993) 1249-1265.
* We have modified their original by adding a check for already-
sorted input,
* which seems to be a win per discussions on pgsql-hackers around
2006-03-21.
*/
#define swapcode(TYPE, parmi, parmj, n) \
do { \
size_t i = (n) / sizeof (TYPE); \
TYPE *pi = (TYPE *)(void *)(parmi); \
TYPE *pj = (TYPE *)(void *)(parmj); \
do { \
TYPE t = *pi; \
*pi++ = *pj; \
*pj++ = t; \
} while (--i > 0); \
} while (0)

#define SWAPINIT(a, es) swaptype = ((char *)(a) - (char *)0) %
sizeof(long) || \
(es) % sizeof(long) ? 2 : (es) == sizeof(long)? 0 : 1;

static void
swapfunc(a, b, n, swaptype)
char *a,
*b;
size_t n;
int swaptype;
{
if (swaptype <= 1)
swapcode(long, a, b, n);
else
swapcode(char, a, b, n);
}

#define swap(a, b) \
if (swaptype == 0) { \
long t = *(long *)(void *)(a); \
*(long *)(void *)(a) = *(long *)(void *)(b); \
*(long *)(void *)(b) = t; \
} else \
swapfunc(a, b, es, swaptype)

#define vecswap(a, b, n) if ((n) > 0) swapfunc((a), (b), (size_t)(n),
swaptype)

static char *
med3(a, b, c, cmp)
char *a,
*b,
*c;
int (*cmp) (const void *, const void *);
{
return cmp(a, b) < 0 ?
(cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a))
: (cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c));
}

void
qsort(a, n, es, cmp)
void *a;
size_t n,
es;
int (*cmp) (const void *, const void *);
{
char *pa,
*pb,
*pc,
*pd,
*pl,
*pm,
*pn;
int d,
r,
swaptype,
presorted;

loop:SWAPINIT(a, es);
if (n < 7)
{
for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0;
pl -= es)
swap(pl, pl - es);
return;
}
presorted = 1;
for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
{
if (cmp(pm - es, pm) > 0)
{
presorted = 0;
break;
}
}
if (presorted)
return;
pm = (char *) a + (n / 2) * es;
if (n > 7)
{
pl = (char *) a;
pn = (char *) a + (n - 1) * es;
if (n > 40)
{
d = (n / 8) * es;
pl = med3(pl, pl + d, pl + 2 * d, cmp);
pm = med3(pm - d, pm, pm + d, cmp);
pn = med3(pn - 2 * d, pn - d, pn, cmp);
}
pm = med3(pl, pm, pn, cmp);
}
swap(a, pm);
pa = pb = (char *) a + es;
pc = pd = (char *) a + (n - 1) * es;
for (;
{
while (pb <= pc && (r = cmp(pb, a)) <= 0)
{
if (r == 0)
{
swap(pa, pb);
pa += es;
}
pb += es;
}
while (pb <= pc && (r = cmp(pc, a)) >= 0)
{
if (r == 0)
{
swap(pc, pd);
pd -= es;
}
pc -= es;
}
if (pb > pc)
break;
swap(pb, pc);
pb += es;
pc -= es;
}
pn = (char *) a + n * es;
r = min(pa - (char *) a, pb - pa);
vecswap(a, pb - r, r);
r = min(pd - pc, pn - pd - es);
vecswap(pb, pn - r, r);
if ((r = pb - pa) > es)
qsort(a, r / es, es, cmp);
if ((r = pd - pc) > es)
{
/* Iterate rather than recurse to save stack space */
a = pn - r;
n = r / es;
goto loop;
}
/* qsort(pn - r, r / es, es, cmp);*/
}

 

[Coos Haak]

Op Thu, 05 Apr 2007 22:08:12 GMT schreef Daniel Rudy:

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

It needs to return an error indicator to the caller if malloc fails?

Perhaps, but you haven't answered why do you think return is a function?!

 

[Coos Haak]

Op Thu, 5 Apr 2007 22:19:45 +0000 (UTC) schreef Dave Vandervies:

viv342 said:


Pointlessly.

Temps are cheap, and the resulting code will be quicker and easier to
read than a hack. And, in any case, the hack for which you are
stretching only works for particular kinds of variable under particular
conditions.

Alternatively, write the code in a way that makes sense and use an
optimizing compiler:
--------
dave@goofy:~/clc (0) $ cat swap.c
void swap(int *a,int *b)
{
int t=*a;
*a=*b;
*b=t;
}
dave@goofy:~/clc (0) $ gcc -W -Wall -ansi -pedantic -O -S swap.c
dave@goofy:~/clc (0) $ cat swap.s
[Some framing removed, this is the generated code for the actual function
in its entirety]
swap:
pushl %ebp
movl %esp, %ebp
pushl %ebx
movl 8(%ebp), %edx
movl 12(%ebp), %ecx
movl (%edx), %ebx
movl (%ecx), %eax
movl %eax, (%edx)
movl %ebx, (%ecx)
movl (%esp), %ebx
leave
ret

But you use THREE registers! ebx is used as a temporary storage here.
In short, three variables.

 

[Keith Thompson]

At about the time of 4/5/2007 4:10 AM, Army1987 stated the following:

I think you mean sizeof(*a) and sizeof(*b), but does that construct even
work for a void *?

The parentheses are unnecessary. Remember, the syntax for the sizeof
operator is
sizeof unary-expression
or
sizeof( type-name )

But since a and b are both of type void* the expression violates a
constraint.

<OT>gcc, as an extension, treats sizeof (void) as 1. I don't know
whether it will accept the above code; it might still choke on the
attempt to dereference something of type void*.</OT>

 

[Keith Thompson]

Op Thu, 05 Apr 2007 22:08:12 GMT schreef Daniel Rudy:

Perhaps, but you haven't answered why do you think return is a function?!

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.

 

[Keith Thompson]

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);

}

Please don't quote signatures.

Certainly, the most elegant C version (due to C99 semantics).

[...]

For certain values of "elegant".

If there isn't enough space to allocate the temporary buffer, this
version invokes undefined behavior. In an alternative version using
malloc(), you can catch an allocation error and fall back to an
alternative technique.