473,322 Members | 1,345 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,322 software developers and data experts.

brain teasers

how can two variables be swapped without using a third variable?

Apr 4 '07 #1
95 4203

viv342 wrote:
how can two variables be swapped without using a third variable?
Lookup what the bitwise XOR operator does. But the compiler is likely
to use a temporary anyway, and it's nearly always more readable also.

Apr 4 '07 #2
On 4 Apr, 11:42, "viv342" <viv...@gmail.comwrote:
how can two variables be swapped without using a third variable?
Do your own homework, kid.

Hint: It took no more than ten seconds to find it from the Wikipedia
home page.

Apr 4 '07 #3
viv342 wrote:
how can two variables be swapped without using a third variable?
You didn't check the FAQ before posting this trite question, did you?
Nor did you check the archives, did you?
When you go back to the idiot that thinks the stupid XOR trick is neat,
ask him what he does with non-integer variables. And ask him how he
knows the compiler doesn't generate a hidden third variable even when he
uses the stupid XOR trick with integer type variables. And if he gives
you a one-line answer, it is sure to violate constraints even on integer
variables. Learn some real programming and leave the crap to people who
place bar bets for drinks.
Apr 4 '07 #4
a = a^b;
b = a^b;
a = a^b;

Apr 4 '07 #5
ro********@gmail.com wrote:
a = a^b;
b = a^b;
a = a^b;
Please quote the relevant portions of the message to which you're
replying, since on Usenet itself, as opposed to Google Groups,
previous articles may not always be available or easily accessible.
It's also good practise to make a post contextually self-contained.

Apr 4 '07 #6
ro********@gmail.com wrote:
a = a^b;
b = a^b;
a = a^b;
So you know the stupid XOR trick. So what? Don't perpetuate this.
Just because every class of beginners has someone who thinks this is
cool doesn't mean that it is worth bothering with. And you neither
answered the question about what happens with non-integer variables nor
demonstrated why you think the compiler doesn't generate a hidden third
variable. If your trick doesn't work with non-integers (it doesn't),
then the original question has not been answered. If the compiler might
generate a hidden third variable, then the original question has not
been answered.

Apr 4 '07 #7

"Martin Ambuhl" <ma*****@earthlink.netwrote in message
news:57*************@mid.individual.net...
viv342 wrote:
>how can two variables be swapped without using a third variable?

You didn't check the FAQ before posting this trite question, did you? Nor
did you check the archives, did you?
When you go back to the idiot that thinks the stupid XOR trick is neat,
ask him what he does with non-integer variables. And ask him how he knows
the compiler doesn't generate a hidden third variable even when he uses
the stupid XOR trick with integer type variables. And if he gives you a
one-line answer, it is sure to violate constraints even on integer
variables. Learn some real programming and leave the crap to people who
place bar bets for drinks.
Quess who missed his Easter bonus at work.
The XOR trick was new to me once.

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

Apr 4 '07 #8
On Wed, 4 Apr 2007 21:39:10 +0100, "Malcolm McLean"
<re*******@btinternet.comwrote:
>
"Martin Ambuhl" <ma*****@earthlink.netwrote in message
news:57*************@mid.individual.net...
>viv342 wrote:
>>how can two variables be swapped without using a third variable?

You didn't check the FAQ before posting this trite question, did you? Nor
did you check the archives, did you?
When you go back to the idiot that thinks the stupid XOR trick is neat,
ask him what he does with non-integer variables. And ask him how he knows
the compiler doesn't generate a hidden third variable even when he uses
the stupid XOR trick with integer type variables. And if he gives you a
one-line answer, it is sure to violate constraints even on integer
variables. Learn some real programming and leave the crap to people who
place bar bets for drinks.
Quess who missed his Easter bonus at work.
The XOR trick was new to me once.
Me too. In fact, I invented it, and thought I was quite clever until I
found out how many other people had invented it <g>.

My application was different, though - implementing a byte-addressing
method for the assembler of a machine which only addressed 16 bits. A
temporary would have been undesirable, because we had to support
re-entrant code.

--
Al Balmer
Sun City, AZ
Apr 4 '07 #9
"viv342" <vi****@gmail.comwrites:
how can two variables be swapped without using a third variable?
The same way you pound a nail without using a hammer. You don't.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Apr 4 '07 #10
viv342 said:
how can two variables be swapped without using a third variable?
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.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.
Apr 5 '07 #11
At about the time of 4/4/2007 11:43 AM, Martin Ambuhl stated the following:
ro********@gmail.com wrote:
>a = a^b;
b = a^b;
a = a^b;

So you know the stupid XOR trick. So what? Don't perpetuate this.
Just because every class of beginners has someone who thinks this is
cool doesn't mean that it is worth bothering with. And you neither
answered the question about what happens with non-integer variables nor
demonstrated why you think the compiler doesn't generate a hidden third
variable. If your trick doesn't work with non-integers (it doesn't),
then the original question has not been answered. If the compiler might
generate a hidden third variable, then the original question has not
been answered.
I agree. I didn't even know what the XOR trick was before this.
Looking at that code, I can't tell what it is or what it does without
getting a pencil and some paper and working it out manually.

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? That's a universal swap function that will
work with *ANY* datatype in any configuration (as far as I know) up to
32 bytes in size (int, long, float, double, char, signed, unsigned,
struct, etc...). Hell, this will work as is on any machine no matter
what the endian is (big, little, pdp, etc...). In fact, just changing
the MAXSWAP define, you can swap data of ANY size, and it's portable.

To use it?

int a, b;
....
swap(&a, &b, sizeof(int));

--or--

double x, y;
....
swap(&x, &y, sizeof(double));
It's that simple.

(Of course I probably made a simple mistake that the regulars are going
to jump all over me about.) :-)

--
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
Apr 5 '07 #12
Daniel Rudy said:

<snip>
#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.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.
Apr 5 '07 #13
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);
}

--
Ian Collins.
Apr 5 '07 #14
a = a+b
b = a-b;
a = a-b;
Apr 5 '07 #15
"Vishesh" <vi***************@yahoo.co.inha scritto nel messaggio
news:11**********************@e65g2000hsc.googlegr oups.com...
>a = a+b
You meant a = a+b;
By the way, what if a = 30000, b = 30001, INT_MAX = 32767?
b = a-b;
a = a-b;

Apr 5 '07 #16

"Ian Collins" <ia******@hotmail.comha scritto nel messaggio
news:57*************@mid.individual.net...
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) {
fputs("Attempt to swap variables of incompatible types", stderr);
return 1;
}
temp = malloc(sizeof *a);
if (temp == NULL) {
perror("Unable to allocate memory");
return -1;
}
memcpy(temp, a, sizeof *a);
memcpy(a, b, sizeof *a);
memcpy(b, temp, sizeof *a);
free(temp);
retun 0;
}

Apr 5 '07 #17
Army1987 wrote:
"Ian Collins" <ia******@hotmail.comha scritto nel messaggio
news:57*************@mid.individual.net...
>>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?

--
Ian Collins.
Apr 5 '07 #18
"Vishesh" <vi***************@yahoo.co.inwrote:
a = a+b
b = a-b;
a = a-b;
Too stupid to bother with.

HTH; HAND; no, I don't want fries with that.

Richard
Apr 5 '07 #19
"Malcolm McLean" <re*******@btinternet.comwrote:
"Martin Ambuhl" <ma*****@earthlink.netwrote in message
news:57*************@mid.individual.net...
viv342 wrote:
how can two variables be swapped without using a third variable?
You didn't check the FAQ before posting this trite question, did you? Nor
did you check the archives, did you?
When you go back to the idiot that thinks the stupid XOR trick is neat,
ask him what he does with non-integer variables. And ask him how he knows
the compiler doesn't generate a hidden third variable even when he uses
the stupid XOR trick with integer type variables. And if he gives you a
one-line answer, it is sure to violate constraints even on integer
variables. Learn some real programming and leave the crap to people who
place bar bets for drinks.
Quess who missed his Easter bonus at work.
TINEB.
The XOR trick was new to me once.
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.

Richard
Apr 5 '07 #20
"Ian Collins" <ia******@hotmail.comha scritto nel messaggio
news:57**************@mid.individual.net...
>int swap (void *a, void *b)
{
void *temp;
if (sizeof *a != sizeof *b) {

Have you tried to compile this?
> retun 0;

Or this?
No... whoops...
Apr 5 '07 #21
Vishesh wrote:
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.
Apr 5 '07 #22
Richard Bos wrote, On 05/04/07 12:29:
"Malcolm McLean" <re*******@btinternet.comwrote:
<snip discussion of xor variable swap trick NOT suggested by anyone quoted>
>The XOR trick was new to me once.

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 :-)
--
Flash Gordon
Apr 5 '07 #23
At about the time of 4/5/2007 4:10 AM, Army1987 stated the following:
"Ian Collins" <ia******@hotmail.comha scritto nel messaggio
news:57*************@mid.individual.net...
>Or even in modern C:
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
Apr 5 '07 #24
Daniel Rudy wrote:
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 *?
No, you can't take the sizeof void.

--
Ian Collins.
Apr 5 '07 #25
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....

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
Apr 5 '07 #26
Daniel Rudy wrote:
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?
}

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

--
Ian Collins.
Apr 5 '07 #27
Daniel Rudy said:
At about the time of 4/5/2007 4:10 AM, Army1987 stated the following:
>"Ian Collins" <ia******@hotmail.comha scritto nel messaggio
news:57*************@mid.individual.net...
>>Or even in modern C:
if (sizeof *a != sizeof *b) {

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

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.
Apr 5 '07 #28
At about the time of 4/5/2007 2:05 PM, Ian Collins stated the following:
Daniel Rudy wrote:
>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?
>
>}

That will swap *ANY* 2 data types of the same type, structs included.
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
Apr 5 '07 #29
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.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.
Apr 5 '07 #30
In article <I9*********************@bt.com>,
Richard Heathfield <rj*@see.sig.invalidwrote:
>viv342 said:
>how can two variables be swapped without using a third variable?

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

--
Dave Vandervies dj******@csclub.uwaterloo.ca
Oh! My programming language has become a mammal! Is that what makes
the problems so hairy?
--Chris Dollin in comp.lang.c
Apr 5 '07 #31
Dave Vandervies wrote:
In article <I9*********************@bt.com>,
Richard Heathfield <rj*@see.sig.invalidwrote:
>>
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.
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

!
--
Ian Collins.
Apr 5 '07 #32
On Apr 5, 12:20 am, Ian Collins <ian-n...@hotmail.comwrote:
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);

}

--
Ian Collins.
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.
Apr 5 '07 #33
On Apr 5, 3:13 pm, Richard Heathfield <r...@see.sig.invalidwrote:
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.
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.
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999http://www.cpax.org.uk
email: rjh at the above domain, - www.

Apr 5 '07 #34
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);*/
}
Apr 5 '07 #35
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:
>Daniel Rudy wrote:
<snip>
>> 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?
Perhaps, but you haven't answered why do you think return is a function?!
--
Coos
Apr 5 '07 #36
Op Thu, 5 Apr 2007 22:19:45 +0000 (UTC) schreef Dave Vandervies:
In article <I9*********************@bt.com>,
Richard Heathfield <rj*@see.sig.invalidwrote:
>>viv342 said:
>>how can two variables be swapped without using a third variable?

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.
But you use THREE registers! ebx is used as a temporary storage here.
In short, three variables.
--
Coos
Apr 5 '07 #37
Daniel Rudy <sp******@spamthis.netwrites:
At about the time of 4/5/2007 4:10 AM, Army1987 stated the following:
>"Ian Collins" <ia******@hotmail.comha scritto nel messaggio
news:57*************@mid.individual.net...
>>Or even in modern C:
if (sizeof *a != sizeof *b) {

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 (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Apr 6 '07 #38
Coos Haak <ch*****@hccnet.nlwrites:
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:
>>Daniel Rudy wrote:
<snip>
>>> 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?

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 (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Apr 6 '07 #39
"user923005" <dc*****@connx.comwrites:
On Apr 5, 12:20 am, Ian Collins <ian-n...@hotmail.comwrote:
[...]
>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.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Apr 6 '07 #40
On Apr 5, 5:19 pm, Keith Thompson <k...@mib.orgwrote:
"user923005" <dcor...@connx.comwrites:
On Apr 5, 12:20 am, Ian Collins <ian-n...@hotmail.comwrote:
[...]
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.
If someone uses malloc() in an exchange function, they need to be
slapped[0], unless you are exchanging 5 GB x-ray images or some other
absurdity [in which case you would probably use a customized exchange
function just for that purpose].

Having an exchange function fail because not enough auto memory is
available is not more probable than having the C program fail in some
other function because not enough automatic storage is available.
Hence, if the technique is dangerous here, then C programs are
dangerous in general. The dreadful, dreary slowness of malloc() makes
this notion so unpalatable that the core dump is almost pleasant[1] by
contrast.

[0] I can't figure out what I did with my poleaxe machine, so a slap
will have to do.
[1] But if Nudds flys (flies?) out of my left nostril {rather than a
core dump}, I will have to concede the issue.

Apr 6 '07 #41
"user923005" <dc*****@connx.comwrites:
On Apr 5, 5:19 pm, Keith Thompson <k...@mib.orgwrote:
>"user923005" <dcor...@connx.comwrites:
On Apr 5, 12:20 am, Ian Collins <ian-n...@hotmail.comwrote:
[...]
>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);
>}
[...]
>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.

If someone uses malloc() in an exchange function, they need to be
slapped[0], unless you are exchanging 5 GB x-ray images or some other
absurdity [in which case you would probably use a customized exchange
function just for that purpose].

Having an exchange function fail because not enough auto memory is
available is not more probable than having the C program fail in some
other function because not enough automatic storage is available.
Hence, if the technique is dangerous here, then C programs are
dangerous in general. The dreadful, dreary slowness of malloc() makes
this notion so unpalatable that the core dump is almost pleasant[1] by
contrast.
Using a VLA and risking undefined behavior if you run out of memory
(you could be swapping very large objects) isn't what I'd call
elegant. You could, I suppose, restrict the size of the objects beng
swapped.

If you want to use a temporary that's the full size of the objects
being swapped, malloc() is the only safe way to go. If malloc() isn't
acceptable, just swap one byte at a time.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Apr 6 '07 #42
On Apr 5, 6:44 pm, Keith Thompson <k...@mib.orgwrote:
"user923005" <dcor...@connx.comwrites:
On Apr 5, 5:19 pm, Keith Thompson <k...@mib.orgwrote:
"user923005" <dcor...@connx.comwrites:
On Apr 5, 12:20 am, Ian Collins <ian-n...@hotmail.comwrote:
[...]
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);
}
[...]
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.
If someone uses malloc() in an exchange function, they need to be
slapped[0], unless you are exchanging 5 GB x-ray images or some other
absurdity [in which case you would probably use a customized exchange
function just for that purpose].
Having an exchange function fail because not enough auto memory is
available is not more probable than having the C program fail in some
other function because not enough automatic storage is available.
Hence, if the technique is dangerous here, then C programs are
dangerous in general. The dreadful, dreary slowness of malloc() makes
this notion so unpalatable that the core dump is almost pleasant[1] by
contrast.

Using a VLA and risking undefined behavior if you run out of memory
(you could be swapping very large objects) isn't what I'd call
elegant. You could, I suppose, restrict the size of the objects beng
swapped.
Using a VLA is no more dangerous than using an object of the same size
as the VLA.
If we are using the function generically, that indicates that
somewhere in the program we are eventually going to refer to actual
objects to feed to our exchange function. How do we tend to use
exchange functions? Often (for instance) to sort things in a vector
or to reform a heap or to reorder a tree or something of that nature.
An exchange function is mathematically useless, unless there is some
kind of order implied. Ordering implies a collection of objects (e.g.
if there are only two of them, then actually exchanging them is a
waste of time). If the addition of a single temporary to automatic
memory is unsafe, then the program itself is unsafe. Certainly, we
are going to be manipulating collections of these things elsewhere in
the program.
If you want to use a temporary that's the full size of the objects
being swapped, malloc() is the only safe way to go. If malloc() isn't
acceptable, just swap one byte at a time.
Or do something clever like the Bentley / McIlroy sort I posted (which
tends to be a lot faster than swapping one byte at a time).

On the other hand, perhaps it really means that the C++ template is
even more superior than I ever imagined.

The reason I am kicking up such a fuss on this subject is that this
(exchange/compare sorts of operations) is the kind of thing that will
have a severe impact on performance (even on a vector in the ideal
case of selection sort which minimizes exchanges we will still have
exchanges proportional at least to N). Writing a bad exchange
function (and I consider an exchange function that calls malloc() and
free() a very, very bad one) will definitely have a very severe effect
on overall performance.

Apr 6 '07 #43
On Apr 5, 8:06 pm, "user923005" <dcor...@connx.comwrote:
On Apr 5, 6:44 pm, Keith Thompson <k...@mib.orgwrote:
"user923005" <dcor...@connx.comwrites:
On Apr 5, 5:19 pm, Keith Thompson <k...@mib.orgwrote:
>"user923005" <dcor...@connx.comwrites:
On Apr 5, 12:20 am, Ian Collins <ian-n...@hotmail.comwrote:
>[...]
>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);
>}
[...]
>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.
If someone uses malloc() in an exchange function, they need to be
slapped[0], unless you are exchanging 5 GB x-ray images or some other
absurdity [in which case you would probably use a customized exchange
function just for that purpose].
Having an exchange function fail because not enough auto memory is
available is not more probable than having the C program fail in some
other function because not enough automatic storage is available.
Hence, if the technique is dangerous here, then C programs are
dangerous in general. The dreadful, dreary slowness of malloc() makes
this notion so unpalatable that the core dump is almost pleasant[1] by
contrast.
Using a VLA and risking undefined behavior if you run out of memory
(you could be swapping very large objects) isn't what I'd call
elegant. You could, I suppose, restrict the size of the objects beng
swapped.

Using a VLA is no more dangerous than using an object of the same size
as the VLA.
If we are using the function generically, that indicates that
somewhere in the program we are eventually going to refer to actual
objects to feed to our exchange function. How do we tend to use
exchange functions? Often (for instance) to sort things in a vector
or to reform a heap or to reorder a tree or something of that nature.
An exchange function is mathematically useless, unless there is some
kind of order implied. Ordering implies a collection of objects (e.g.
if there are only two of them, then actually exchanging them is a
waste of time). If the addition of a single temporary to automatic
memory is unsafe, then the program itself is unsafe. Certainly, we
are going to be manipulating collections of these things elsewhere in
the program.
If you want to use a temporary that's the full size of the objects
being swapped, malloc() is the only safe way to go. If malloc() isn't
acceptable, just swap one byte at a time.

Or do something clever like the Bentley / McIlroy sort I posted (which
tends to be a lot faster than swapping one byte at a time).

On the other hand, perhaps it really means that the C++ template is
even more superior than I ever imagined.

The reason I am kicking up such a fuss on this subject is that this
(exchange/compare sorts of operations) is the kind of thing that will
have a severe impact on performance (even on a vector in the ideal
case of selection sort which minimizes exchanges we will still have
exchanges proportional at least to N). Writing a bad exchange
function (and I consider an exchange function that calls malloc() and
free() a very, very bad one) will definitely have a very severe effect
on overall performance.
Having thought about this a bit, I think the superiority of the C++
template just got a huge hole shot in its foot, unless we make the
exchange a class member that stores a temporary, or unless we pass the
temporary in as a parameter. After all, the template exchange method
(if the temp is not part of the class) is going to do a new/delete
when we create the temp to perform the exchange. This notion is of
such dramatic importance that I feel a burning need to do a code
review of a few hundred thousand lines (obviously, I can't do this in
a day!).

Apr 6 '07 #44
user923005 wrote:
>
Having thought about this a bit, I think the superiority of the C++
template just got a huge hole shot in its foot, unless we make the
exchange a class member that stores a temporary, or unless we pass the
temporary in as a parameter. After all, the template exchange method
(if the temp is not part of the class) is going to do a new/delete
when we create the temp to perform the exchange.
OK, I've kept out of this so far, but that assumption is wrong. The
temporary is just another automatic variable. Thus the C++ template
solution suffers the same potential stack exhaustion problems as my VLA
suggestion. On the other hand, not having to pass things via void*
gives the compiler a better shot at optimising the copies.

The same applies to sorting in general, this is one area where C++
(through aggressive optimisation) can outperform C where templates
rather than void* are used to provide a generic solution.

--
Ian Collins.
Apr 6 '07 #45
On Apr 5, 8:48 pm, Ian Collins <ian-n...@hotmail.comwrote:
user923005 wrote:
Having thought about this a bit, I think the superiority of the C++
template just got a huge hole shot in its foot, unless we make the
exchange a class member that stores a temporary, or unless we pass the
temporary in as a parameter. After all, the template exchange method
(if the temp is not part of the class) is going to do a new/delete
when we create the temp to perform the exchange.

OK, I've kept out of this so far, but that assumption is wrong. The
temporary is just another automatic variable. Thus the C++ template
solution suffers the same potential stack exhaustion problems as my VLA
suggestion.
When you create a temporary, it will call the constructor. Typically,
the constructor will call new. You are right in the case of
fundamental types like integers and doubles.
On the other hand, not having to pass things via void*
gives the compiler a better shot at optimising the copies.

The same applies to sorting in general, this is one area where C++
(through aggressive optimisation) can outperform C where templates
rather than void* are used to provide a generic solution.
It turns out I am full of crap anyway. I was going on old, old
profile runs where malloc()/free() were time pigs of the worst kind.
I just did a benchmark and my old profiles simply do not hold up:

dcorbit@DCORBIT64 /c/tmp
$ gcc -W -Wall -ansi -pedantic -DUNIT_TEST threesorts.c
threesorts.c: In function 'autoswap':
threesorts.c:18: warning: ISO C90 forbids variable-size array 'temp'

dcorbit@DCORBIT64 /c/tmp
$ ./a
auto heap sort took 28.407000 seconds
heap heap sort took 29.392000 seconds
etype heap sort took 27.595000 seconds

dcorbit@DCORBIT64 /c/tmp

$ cat threesorts.c
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

typedef double Etype;

void etypeswap(Etype *a, Etype *b)
{
Etype temp;
temp = *a;
*a = *b;
*b = temp;
}

void autoswap(void *a, void *b, size_t size)
{
char temp[size];
memcpy(temp, a, size);
memcpy(a, b, size);
memcpy(b, temp, size);
}

void heapswap(void *a, void *b, size_t size)
{
char *temp = malloc(size);
assert(temp);
if (temp) {
memcpy(temp, a, size);
memcpy(a, b, size);
memcpy(b, temp, size);
free(temp);
} else {
printf("Memory allocation error in %s:%s at %u\n", __FILE__,
__FUNCTION__, (unsigned) __LINE__);
}
}

/* This version of heapsort is adapted from:
*
* Data Structures and Algorithm Analysis in C (Second Edition) by
Mark Allen
* Weiss Addison-Wesley, 1997 ISBN: 0-201-49840-5 Page 228.
*
* It is simple and interesting, but quick-sort is better than heap-
sort. */

#define LeftChild( i ) ( 2 * ( i ) + 1 )
int GT(Etype a, Etype b)
{
return (a b);
}
int LT(Etype a, Etype b)
{
return (a < b);
}
void perc_down(Etype A[], size_t i, size_t N)
{
size_t Child;
Etype Tmp;

for (Tmp = A[i]; LeftChild(i) < N; i = Child) {
Child = LeftChild(i);
if (Child != N - 1 && GT(A[Child + 1], A[Child]))
Child++;
if (LT(Tmp, A[Child]))
A[i] = A[Child];
else
break;
}
A[i] = Tmp;
}

void autoheapsort(Etype A[], size_t N)
{
int i;

for (i = N / 2; i >= 0; i--)
/* BuildHeap */
perc_down(A, i, N);
for (i = N - 1; i 0; i--) {
autoswap(&A[0], &A[i], sizeof(Etype));
/* DeleteMax */
perc_down(A, 0, i);
}
}

void heapheapsort(Etype A[], size_t N)
{
long i;

for (i = N / 2; i >= 0; i--)
/* BuildHeap */
perc_down(A, i, N);
for (i = N - 1; i 0; i--) {
heapswap(&A[0], &A[i], sizeof(Etype));
/* DeleteMax */
perc_down(A, 0, i);
}
}

void etypeheapsort(Etype A[], size_t N)
{
long i;

for (i = N / 2; i >= 0; i--)
/* BuildHeap */
perc_down(A, i, N);
for (i = N - 1; i 0; i--) {
etypeswap(&A[0], &A[i]);
/* DeleteMax */
perc_down(A, 0, i);
}
}

#ifdef UNIT_TEST

#include <time.h>
#include <math.h>
Etype array[10000000];
Etype tarray[10000000];
Etype t2array[10000000];

int main(void)
{
size_t index;
clock_t start,
end;
size_t array_dim = sizeof array / sizeof array[0];
/* Fill array with random numbers */
for (index = 0; index < array_dim; index++) {
array[index] = rand() / (fabs((double) rand()) + 1);
}
/* Make copies of random numbers */
memcpy(tarray, array, sizeof array);
memcpy(t2array, array, sizeof array);
start = clock();
autoheapsort(array, array_dim);
end = clock();
printf("auto heap sort took %f seconds\n", (end - start) * 1.0 /
CLOCKS_PER_SEC);
start = clock();
heapheapsort(tarray, array_dim);
end = clock();
printf("heap heap sort took %f seconds\n", (end - start) * 1.0 /
CLOCKS_PER_SEC);
start = clock();
etypeheapsort(t2array, array_dim);
end = clock();
printf("etype heap sort took %f seconds\n", (end - start) * 1.0 /
CLOCKS_PER_SEC);
return 0;
}
#endif

dcorbit@DCORBIT64 /c/tmp

Thinking it might be optimization level, I tried again:
dcorbit@DCORBIT64 /c/tmp
$ gcc -W -Wall -ansi -pedantic -DUNIT_TEST -O3 threesorts.c
threesorts.c: In function 'autoswap':
threesorts.c:18: warning: ISO C90 forbids variable-size array 'temp'

dcorbit@DCORBIT64 /c/tmp
$ ./a
auto heap sort took 17.547000 seconds
heap heap sort took 17.267000 seconds
etype heap sort took 15.641000 seconds

dcorbit@DCORBIT64 /c/tmp

I guess that .984 is hardly a dramatic speedup (1.6%) and even the
native type still used 0.89 of the time which is only (11%) better.

Apr 6 '07 #46
user923005 wrote:
On Apr 5, 8:48 pm, Ian Collins <ian-n...@hotmail.comwrote:
>>user923005 wrote:
>>>Having thought about this a bit, I think the superiority of the C++
template just got a huge hole shot in its foot, unless we make the
exchange a class member that stores a temporary, or unless we pass the
temporary in as a parameter. After all, the template exchange method
(if the temp is not part of the class) is going to do a new/delete
when we create the temp to perform the exchange.

OK, I've kept out of this so far, but that assumption is wrong. The
temporary is just another automatic variable. Thus the C++ template
solution suffers the same potential stack exhaustion problems as my VLA
suggestion.

When you create a temporary, it will call the constructor. Typically,
the constructor will call new. You are right in the case of
fundamental types like integers and doubles.
No, it will not.

<OT>Constructors don't call new, new calls constructors.</OT>

--
Ian Collins.
Apr 6 '07 #47
On Apr 5, 8:58 pm, "user923005" <dcor...@connx.comwrote:
By changing autoswap to this:
void autoswap(void *a, void *b, size_t size)
{
char temp[sizeof(Etype)];
memcpy(temp, a, size);
memcpy(a, b, size);
memcpy(b, temp, size);
}

So that only C90 is needed (though you have to recompile for every
Etype you want to use) I got this:

dcorbit@DCORBIT64 /c/tmp
$ gcc -W -Wall -ansi -pedantic -DUNIT_TEST -O3 threesorts.c

dcorbit@DCORBIT64 /c/tmp
$ ./a
auto heap sort took 14.719000 seconds
heap heap sort took 15.845000 seconds
etype heap sort took 14.407000 seconds

dcorbit@DCORBIT64 /c/tmp
$

Also, using MS VC++ I got this:
C:\tmp>cl /DUNIT_TEST /W4 /Ox threesorts.c
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 14.00.50727.42
for
Copyright (C) Microsoft Corporation. All rights reserved.

threesorts.c
Microsoft (R) Incremental Linker Version 8.00.50727.42
Copyright (C) Microsoft Corporation. All rights reserved.

/out:threesorts.exe
threesorts.obj

C:\tmp>threesorts
auto heap sort took 15.532000 seconds
heap heap sort took 16.814000 seconds
etype heap sort took 15.438000 seconds

Apr 6 '07 #48
On Apr 5, 9:05 pm, Ian Collins <ian-n...@hotmail.comwrote:
user923005 wrote:
On Apr 5, 8:48 pm, Ian Collins <ian-n...@hotmail.comwrote:
>user923005 wrote:
>>Having thought about this a bit, I think the superiority of the C++
template just got a huge hole shot in its foot, unless we make the
exchange a class member that stores a temporary, or unless we pass the
temporary in as a parameter. After all, the template exchange method
(if the temp is not part of the class) is going to do a new/delete
when we create the temp to perform the exchange.
>OK, I've kept out of this so far, but that assumption is wrong. The
temporary is just another automatic variable. Thus the C++ template
solution suffers the same potential stack exhaustion problems as my VLA
suggestion.
When you create a temporary, it will call the constructor. Typically,
the constructor will call new. You are right in the case of
fundamental types like integers and doubles.

No, it will not.

<OT>Constructors don't call new, new calls constructors.</OT>
<OT>
Are you saying that using the new operator in constructors and the
delete operator in destructors is unusual?
It's not.
</OT>

Apr 6 '07 #49
user923005 wrote:
On Apr 5, 9:05 pm, Ian Collins <ian-n...@hotmail.comwrote:
>>user923005 wrote:
>>>On Apr 5, 8:48 pm, Ian Collins <ian-n...@hotmail.comwrote:
>>>>user923005 wrote:
>>>>>Having thought about this a bit, I think the superiority of the C++
>template just got a huge hole shot in its foot, unless we make the
>exchange a class member that stores a temporary, or unless we pass the
>temporary in as a parameter. After all, the template exchange method
>(if the temp is not part of the class) is going to do a new/delete
>when we create the temp to perform the exchange.
>>>>OK, I've kept out of this so far, but that assumption is wrong. The
temporary is just another automatic variable. Thus the C++ template
solution suffers the same potential stack exhaustion problems as my VLA
suggestion.
>>>When you create a temporary, it will call the constructor. Typically,
the constructor will call new. You are right in the case of
fundamental types like integers and doubles.

No, it will not.

<OT>Constructors don't call new, new calls constructors.</OT>

<OT>
Are you saying that using the new operator in constructors and the
delete operator in destructors is unusual?
It's not.
You're implying the object to be swapped are something other than valid
C types.
</OT>
If the the objects being swapped require complex initialisation (C or
C++), you probably wouldn't be swapping then, you'd more likely swap
pointers.

--
Ian Collins.
Apr 6 '07 #50

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

2
by: brendan | last post by:
here's a brain teaser for someone with more skills or at least more lateral thinking capability than me - done my nut over this one... have written a list manager in PHP which a) posts out new...
7
by: robert | last post by:
running 8.1.7 server, 8.1.6 client. i *thought* inner join should not return nulls, but not only that, but i get way more rows than i'm expecting. assume: order table: order_number
7
by: Mark A | last post by:
If server 01 running HADR in the primary role crashes, and the DBA does a HADR takeover by force on the 02 server to switch roles, then the 02 server is now the primary. What happens when the...
3
by: Joachim Klassen | last post by:
Hi all, if I accidentally use a TAKEOVER command with BY FORCE clause while primary and standby are in peer state I'll end up with two primary's (at least with FP10 and Windows). Is this works ...
16
by: Ludwig | last post by:
Hi, I'm looking for C# brain teasers (or VB.NET): a little piece of code that does something special, or where a little error is. Does anyone has some of these, or links to sites? Thanks!
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.