By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
448,538 Members | 875 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 448,538 IT Pros & Developers. It's quick & easy.

qsort

P: n/a
I'm trying to figure out qsort(). I haven't seen any practical examples,
only synopsis. In the code below, the array is not sorted. Can someone
give me some help?

#include <stdio.h>
#include <stdlib.h>
int compare(const void* a, const void* b);

int main(void)
{
int idx;
int array[] = {243, 12, 99, 106, 122, 77, 242};

qsort(array, 7, 4, &compare);
for(idx=0; idx<7; ++idx)
printf("%d\t", array[idx]);
printf("\n");

return 0;
}

int compare(const void* a, const void* b)
{
if(a < b) return -1;
if(a == b) return 0;
if(a > b) return 1;
}
Nov 14 '05 #1
Share this Question
Share on Google+
32 Replies


P: n/a
John Smith wrote:
I'm trying to figure out qsort(). I haven't seen any practical examples,
only synopsis. In the code below, the array is not sorted. Can someone
give me some help?

#include <stdio.h>
#include <stdlib.h>
int compare(const void* a, const void* b);

int main(void)
{
int idx;
int array[] = {243, 12, 99, 106, 122, 77, 242};

qsort(array, 7, 4, &compare);
The `&' is harmless, but unnecessary. The `4' may
be true for your C implementation, but is not universal:
each C implementation chooses its own "best" size for
`int', and different implementations choose differently.
For portability, write `sizeof array[0]' instead.
for(idx=0; idx<7; ++idx)
printf("%d\t", array[idx]);
printf("\n");

return 0;
}

int compare(const void* a, const void* b)
{
if(a < b) return -1;
if(a == b) return 0;
if(a > b) return 1;
}


Here's your difficulty. The comparison function's
arguments are not two array elements, but pointers to
two array elements. You are comparing the pointers, but
you want to compare the pointed-to objects. Here is one
way to do it:

int compare(const void *a, const void *b) {
int u = *(const int*)a;
int v = *(const int*)b;
if (u < v) ...

--
Er*********@sun.com

Nov 14 '05 #2

P: n/a
Quoth John Smith on or about 2004-11-17:
if(a < b) return -1;
if(a == b) return 0;
if(a > b) return 1;


First of all, shouldn't these be dereferenced?
Nov 14 '05 #3

P: n/a
John Smith wrote:
I'm trying to figure out qsort(). I haven't seen any practical examples,
only synopsis. In the code below, the array is not sorted. Can someone
give me some help?

#include <stdio.h>
#include <stdlib.h>
int compare(const void* a, const void* b);

int main(void)
{
int idx;
int array[] = {243, 12, 99, 106, 122, 77, 242};

qsort(array, 7, 4, &compare);
for(idx=0; idx<7; ++idx)
printf("%d\t", array[idx]);
printf("\n");

return 0;
}

int compare(const void* a, const void* b)
{
if(a < b) return -1;
if(a == b) return 0;
if(a > b) return 1;
}


Inside your 'compare' implementation you are comparing pointers instead
of comparing the values pointed by those pointers. You are supposed to
do the latter, not the former. For example, you can do it as follows

int compare(const void* a, const void* b)
{
int ia = *(const int*) a;
int ib = *(const int*) b;
return (ia > ib) - (ia < ib);
}

Also, it makes more sense to form arguments of 'qsort' by using
'sizeof', instead of specifying concrete values explicitly

qsort(array, sizeof array / sizeof *array, sizeof *array, &compare);

--
Best regards,
Andrey Tarasevich
Nov 14 '05 #4

P: n/a
John Smith wrote:

I'm trying to figure out qsort(). I haven't seen any practical examples,
only synopsis. In the code below, the array is not sorted. Can someone
give me some help?

#include <stdio.h>
#include <stdlib.h>
int compare(const void* a, const void* b);

int main(void)
{
int idx;
int array[] = {243, 12, 99, 106, 122, 77, 242};

qsort(array, 7, 4, &compare);
for(idx=0; idx<7; ++idx)
printf("%d\t", array[idx]);
printf("\n");

return 0;
}

int compare(const void* a, const void* b)
{
if(a < b) return -1;
if(a == b) return 0;
if(a > b) return 1;
}


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

#define NELM (sizeof array / sizeof *array)

int compare(const void* a, const void* b);

int main(void)
{
int idx;
int array[] = {243, 12, 99, 106, 122, 77, 242};

qsort(array, NELM, sizeof *array, compare);
for (idx = 0; idx < NELM; ++idx) {
printf("%d\t", array[idx]);
}
putchar('\n');
return 0;
}

int compare(const void* a, const void* b)
{
const int aa = *(int*)a;
const int bb = *(int*)b;

return bb > aa ? -1 : aa > bb;
}

--
pete
Nov 14 '05 #5

P: n/a
pete wrote:
[snip] int compare(const void* a, const void* b)
{
const int aa = *(int*)a; should be:
const int aa = *(const int *)a; const int bb = *(int*)b;

return bb > aa ? -1 : aa > bb; return aa - bb;

would be the usual idiom. }

Nov 14 '05 #6

P: n/a
Robert Harris wrote:

pete wrote:
[snip]

int compare(const void* a, const void* b)
{
const int aa = *(int*)a;

should be:
const int aa = *(const int *)a;


It makes no difference.
You wind up with const int aa, either way.
const int bb = *(int*)b;

return bb > aa ? -1 : aa > bb;

return aa - bb;

would be the usual idiom.


(aa - bb) is entirely unacceptable
as a generic compar function expression.
If aa equals INT_MAX and bb equals -1,
then you have undefined behavior.
}


--
pete
Nov 14 '05 #7

P: n/a
"John Smith" <JS****@mail.net> wrote in message
news:5qNmd.252445$%k.66766@pd7tw2no...
I'm trying to figure out qsort(). I haven't seen any practical examples,
only synopsis. In the code below, the array is not sorted. Can someone
give me some help? int compare(const void* a, const void* b)
{
if(a < b) return -1;
if(a == b) return 0;
if(a > b) return 1;
}


The compare function is incorrect.
Other replies have given correct alternatives.
Here is my question :

What is the semantics of comparing void* for anything but equality ?
It is non standard to subtract void pointers (but a dubious gcc extension)
What about comparison ? Is it also an extension or is it defined in the
standard ?

Chqrlie.
Nov 14 '05 #8

P: n/a
Charlie Gordon wrote:
"John Smith" <JS****@mail.net> wrote in message
news:5qNmd.252445$%k.66766@pd7tw2no...

int compare(const void* a, const void* b)
{
if(a < b) return -1;
if(a == b) return 0;
if(a > b) return 1;
}


The compare function is incorrect.
Other replies have given correct alternatives.
Here is my question :

What is the semantics of comparing void* for anything but equality ?
It is non standard to subtract void pointers (but a dubious gcc extension)
What about comparison ? Is it also an extension or is it defined in the
standard ?


The comparison is well-defined (as I learned to my
surprise not long ago) under the usual condition that
the two pointers point to or just after the same array.
qsort() guarantees this (although bsearch() obviously
does not), so the comparison is valid.

However, the fact that the comparison is valid doesn't
imply that it's usable by qsort()! The compare() function
must define a consistent ordering, even while qsort() is
busy rearranging the array. If the compare() function's
result changes as the items are shuffled about, the ordering
is inconsistent and qsort()'s behavior is undefined.

Various people have run afoul of this by trying to
compare the pointers to equal elements in an attempt to
achieve a stable sort, e.g.

int compare(const void *p, const void *q) {
int a = *(const int*)p;
int b = *(const int*)q;

if (a < b) return -1;
if (a > b) return +1;

/* Equal elements; try for stability */
if (p < q) return -1;
if (p > q) return +1;
return 0; /* stupid qsort()! */
}

is wrong, R-O-N-G, wrong. The outcome of comparing two
equal integers would depend on their relative locations
in the array, and these locations can change as qsort()
does its work.

--
Er*********@sun.com

Nov 14 '05 #9

P: n/a
Robert Harris wrote:
...
int compare(const void* a, const void* b)
{
const int aa = *(int*)a;

should be:
const int aa = *(const int *)a;
const int bb = *(int*)b;

return bb > aa ? -1 : aa > bb;

return aa - bb;

would be the usual idiom.


The usual idiom would be

return (aa > bb) - (aa < bb);

A mere 'aa - bb' can produce signed overflow, which makes it entirely
useless.

--
Best regards,
Andrey Tarasevich

Nov 14 '05 #10

P: n/a
On Thu, 18 Nov 2004 12:18:56 +0000, pete wrote:
Robert Harris wrote:

pete wrote:
> [snip]

> int compare(const void* a, const void* b)
> {
> const int aa = *(int*)a;

should be:
const int aa = *(const int *)a;


It makes no difference.
You wind up with const int aa, either way.


True the int* cast is correct, but not casting away const
is better style. Reasonable compiler often will
issue a warning about that or can be made to, and it is
a good warning to turn on.

Lawrence

Nov 14 '05 #11

P: n/a
On Thu, 18 Nov 2004 10:58:06 -0500, Eric Sosman wrote:

....
The comparison is well-defined (as I learned to my
surprise not long ago) under the usual condition that
the two pointers point to or just after the same array.
qsort() guarantees this


I don't see anything in the description of qsort() that guarantees this.
It would be quite reasonable for an implementation for qsort() to copy an
element of the array into a local temporary and compare against that. This
is a natural thing to do in some sorting algorithms.

Lawrence
Nov 14 '05 #12

P: n/a
Lawrence Kirby wrote:
On Thu, 18 Nov 2004 10:58:06 -0500, Eric Sosman wrote:

...

The comparison is well-defined (as I learned to my
surprise not long ago) under the usual condition that
the two pointers point to or just after the same array.
qsort() guarantees this

I don't see anything in the description of qsort() that guarantees this.


The C89 wording isn't clear, but C99 makes it explicit:

7.20.5 Searching and sorting utilities
/2/ The implementation shall ensure that [...] both
arguments (when called from qsort), are pointers to
elements of the array. [...]

--
Er*********@sun.com

Nov 14 '05 #13

P: n/a
On Thu, 18 Nov 2004 13:29:38 -0500, Eric Sosman wrote:
Lawrence Kirby wrote:


....
I don't see anything in the description of qsort() that guarantees this.


The C89 wording isn't clear, but C99 makes it explicit:

7.20.5 Searching and sorting utilities
/2/ The implementation shall ensure that [...] both
arguments (when called from qsort), are pointers to
elements of the array. [...]


OK, it is required in C99. Very strange though, it potentially reduces the
efficiency of the implementation for no obvious benefit.

Lawrence

Nov 14 '05 #14

P: n/a
Lawrence Kirby wrote:

On Thu, 18 Nov 2004 13:29:38 -0500, Eric Sosman wrote:
Lawrence Kirby wrote:


...
I don't see anything in the description of qsort()
that guarantees this.


The C89 wording isn't clear, but C99 makes it explicit:

7.20.5 Searching and sorting utilities
/2/ The implementation shall ensure that [...] both
arguments (when called from qsort), are pointers to
elements of the array. [...]


OK, it is required in C99.
Very strange though, it potentially reduces the
efficiency of the implementation for no obvious benefit.


I must be misunderstanding what you're saying.
I don't see how you can write a compar function without knowing
that the arguments are pointers to array elements.

Is this the same thing as what you're talking about?
My C89 last draft has:

4.10.5.2 The qsort function
The contents of the array are sorted in ascending order according
to a comparison function pointed to by compar , which is called with
two arguments that point to the objects being compared.

--
pete
Nov 14 '05 #15

P: n/a


pete wrote:
Lawrence Kirby wrote:
On Thu, 18 Nov 2004 13:29:38 -0500, Eric Sosman wrote:

Lawrence Kirby wrote:
...

I don't see anything in the description of qsort()
that guarantees this.

The C89 wording isn't clear, but C99 makes it explicit:

7.20.5 Searching and sorting utilities
/2/ The implementation shall ensure that [...] both
arguments (when called from qsort), are pointers to
elements of the array. [...]


OK, it is required in C99.
Very strange though, it potentially reduces the
efficiency of the implementation for no obvious benefit.


Umh, I cannot think of a situation where you cannot make do
with pointers to array elements -- the information is hidden
behind void *, so I fail to see the restriction.

One possible benefit could be that for keys giving the same
value, you want to keep the order in which the respective
objects (and thus the pointers) were stored.
This could of course be done by extending the key but maybe
is not possible in a straightforward way. If we are looking
at the same array, the pointers can be compared whereas this
is not possible if we memcpy() one of the objects.
I must be misunderstanding what you're saying.
I don't see how you can write a compar function without knowing
that the arguments are pointers to array elements.

Is this the same thing as what you're talking about?
My C89 last draft has:

4.10.5.2 The qsort function
The contents of the array are sorted in ascending order according
to a comparison function pointed to by compar , which is called with
two arguments that point to the objects being compared.


The thing is that in C89, I could memcpy() one array element and
pass a pointer to it to the function pointed to by compar, whereas
in the C99 version this is forbidden.
Cheers
Michael
--
E-Mail: Mine is a gmx dot de address.

Nov 14 '05 #16

P: n/a
Michael Mair wrote:

pete wrote:
Lawrence Kirby wrote:
On Thu, 18 Nov 2004 13:29:38 -0500, Eric Sosman wrote:
Lawrence Kirby wrote:

...
>I don't see anything in the description of qsort()
>that guarantees this.

The C89 wording isn't clear, but C99 makes it explicit:

7.20.5 Searching and sorting utilities
/2/ The implementation shall ensure that [...] both
arguments (when called from qsort), are pointers to
elements of the array. [...]

OK, it is required in C99.
Very strange though, it potentially reduces the
efficiency of the implementation for no obvious benefit.


Umh, I cannot think of a situation where you cannot make do
with pointers to array elements -- the information is hidden
behind void *, so I fail to see the restriction.

One possible benefit could be that for keys giving the same
value, you want to keep the order in which the respective
objects (and thus the pointers) were stored.
This could of course be done by extending the key but maybe
is not possible in a straightforward way. If we are looking
at the same array, the pointers can be compared whereas this
is not possible if we memcpy() one of the objects.
I must be misunderstanding what you're saying.
I don't see how you can write a compar function without knowing
that the arguments are pointers to array elements.

Is this the same thing as what you're talking about?
My C89 last draft has:

4.10.5.2 The qsort function
The contents of the array are sorted in ascending order according
to a comparison function pointed to by compar , which is called with
two arguments that point to the objects being compared.


The thing is that in C89, I could memcpy() one array element and
pass a pointer to it to the function pointed to by compar, whereas
in the C99 version this is forbidden.


Thank you.

--
pete
Nov 14 '05 #17

P: n/a
On Fri, 19 Nov 2004 14:22:07 +0100, Michael Mair wrote:


pete wrote:
Lawrence Kirby wrote:
On Thu, 18 Nov 2004 13:29:38 -0500, Eric Sosman wrote:
Lawrence Kirby wrote:

...
>I don't see anything in the description of qsort()
>that guarantees this.

The C89 wording isn't clear, but C99 makes it explicit:

7.20.5 Searching and sorting utilities
/2/ The implementation shall ensure that [...] both
arguments (when called from qsort), are pointers to
elements of the array. [...]

OK, it is required in C99.
Very strange though, it potentially reduces the
efficiency of the implementation for no obvious benefit.
Umh, I cannot think of a situation where you cannot make do
with pointers to array elements -- the information is hidden
behind void *, so I fail to see the restriction.
A simple example is an insertion sort. A basic implementation
compares adjacent elements. If they are out of order it swaps them and
moves on. Essentially one element moves along the array until it is in its
correct place. An optimisation of this is to copy that element to a
temporary variable and compare that against array elements, move them when
out of order and finally write your temporary back to the free slot in the
array when you find the right position. Esssentially you can optimise a
lot of swap operations into moves. With the requirements of C99 the
element must stay in the array for the purposes of comparison so this
optimisation is no longer possible. You can "make do" but what is the
benefit of potentially cripping the efficiency of the qsort()
implementation?
One possible benefit could be that for keys giving the same
value, you want to keep the order in which the respective
objects (and thus the pointers) were stored.
This could of course be done by extending the key but maybe
is not possible in a straightforward way. If we are looking
at the same array, the pointers can be compared whereas this
is not possible if we memcpy() one of the objects.


Comparing addresses does *not* make a sort stable, because during the sort
process the position of elements varies and not necessarily in a
consistent way (think for example of the partitioning process that
Quicksort uses).

Indeed ANY test of relative addresses that can affect the result of the
comparison function will guarantee that the function no longer generates a
consistent ordering relation. So there is no value in supporting relative
pointer comparisons.
I must be misunderstanding what you're saying.
I don't see how you can write a compar function without knowing
that the arguments are pointers to array elements.
When comparing 2 elements all you need is access to the values of those
elements, whether they are part of the same array or not is not useful or
relevant information.
Is this the same thing as what you're talking about?
My C89 last draft has:

4.10.5.2 The qsort function
The contents of the array are sorted in ascending order according
to a comparison function pointed to by compar , which is called with
two arguments that point to the objects being compared.


The thing is that in C89, I could memcpy() one array element and
pass a pointer to it to the function pointed to by compar, whereas
in the C99 version this is forbidden.


Yes, that's the problem, C99 appears to have invented a pointless and
counterproductive restriction.

Lawrence

Nov 14 '05 #18

P: n/a


Lawrence Kirby wrote:
On Fri, 19 Nov 2004 14:22:07 +0100, Michael Mair wrote:

pete wrote:
Lawrence Kirby wrote:

On Thu, 18 Nov 2004 13:29:38 -0500, Eric Sosman wrote:

>Lawrence Kirby wrote:

>>I don't see anything in the description of qsort()
>>that guarantees this.
>
> The C89 wording isn't clear, but C99 makes it explicit:
>
> 7.20.5 Searching and sorting utilities
> /2/ The implementation shall ensure that [...] both
> arguments (when called from qsort), are pointers to
> elements of the array. [...]

OK, it is required in C99.
Very strange though, it potentially reduces the
efficiency of the implementation for no obvious benefit.


Umh, I cannot think of a situation where you cannot make do
with pointers to array elements -- the information is hidden
behind void *, so I fail to see the restriction.


A simple example is an insertion sort. A basic implementation
compares adjacent elements. If they are out of order it swaps them and
moves on. Essentially one element moves along the array until it is in its
correct place. An optimisation of this is to copy that element to a
temporary variable and compare that against array elements, move them when
out of order and finally write your temporary back to the free slot in the
array when you find the right position. Esssentially you can optimise a
lot of swap operations into moves. With the requirements of C99 the
element must stay in the array for the purposes of comparison so this
optimisation is no longer possible. You can "make do" but what is the
benefit of potentially cripping the efficiency of the qsort()
implementation?


Okay, so we essentially have to switch from a few memcpy()s to
one memmove(). For small partitions left by a quicksort or a
"nearly" sorted array, we probably will lose something.
I guess Shell sort would be even more pathological as you cannot
use one memmove but would have to first find out where everything
goes and then loop again to do the memcpy()s.

Thank you for explaining.

One possible benefit could be that for keys giving the same
value, you want to keep the order in which the respective
objects (and thus the pointers) were stored.
This could of course be done by extending the key but maybe
is not possible in a straightforward way. If we are looking
at the same array, the pointers can be compared whereas this
is not possible if we memcpy() one of the objects.


Comparing addresses does *not* make a sort stable, because during the sort
process the position of elements varies and not necessarily in a
consistent way (think for example of the partitioning process that
Quicksort uses).

Indeed ANY test of relative addresses that can affect the result of the
comparison function will guarantee that the function no longer generates a
consistent ordering relation. So there is no value in supporting relative
pointer comparisons.


Er, perhaps I am slow on the uptake but IMO a quicksort _can_ keep
the previous relative order when partitioning. If I've time today, I
will try it out.
However, the requirements from the standard are probably not strong
enough for that to portably work.

Apart from that, I do _not_ want to say that it is a good
idea to bring in relative position as sorting criteria. But this
is the only "benefit" I could think of.

Did the standard people give any rationale as to why they changed
the wording? Otherwise this might be a good question for c.s.c.
Cheers
Michael
--
E-Mail: Mine is a gmx dot de address.

Nov 14 '05 #19

P: n/a
Michael Mair wrote:

Lawrence Kirby wrote:
On Fri, 19 Nov 2004 14:22:07 +0100, Michael Mair wrote:

pete wrote:

Lawrence Kirby wrote:

>On Thu, 18 Nov 2004 13:29:38 -0500, Eric Sosman wrote:
>
>>Lawrence Kirby wrote:
>
>>>I don't see anything in the description of qsort()
>>>that guarantees this.
>>
>> The C89 wording isn't clear, but C99 makes it explicit:
>>
>> 7.20.5 Searching and sorting utilities
>> /2/ The implementation shall ensure that [...] both
>> arguments (when called from qsort), are pointers to
>> elements of the array. [...]
>
>OK, it is required in C99.
>Very strange though, it potentially reduces the
>efficiency of the implementation for no obvious benefit.

Umh, I cannot think of a situation where you cannot make do
with pointers to array elements -- the information is hidden
behind void *, so I fail to see the restriction.
A simple example is an insertion sort. A basic implementation
compares adjacent elements. If they are out of order it swaps
them and moves on. Essentially one element moves along
the array until it is in its correct place.
An optimisation of this is to copy that element to a
temporary variable and compare that against array elements,
move them when out of order and finally write your temporary
back to the free slot in the
array when you find the right position.
Esssentially you can optimise a lot of swap operations into moves.
With the requirements of C99 the
element must stay in the array for the purposes of comparison
so this optimisation is no longer possible.
You can "make do" but what is the
benefit of potentially cripping the efficiency of the qsort()
implementation?


Okay, so we essentially have to switch from a few memcpy()s to
one memmove(). For small partitions left by a quicksort or a
"nearly" sorted array, we probably will lose something.
I guess Shell sort would be even more pathological as you cannot
use one memmove but would have to first find out where everything
goes and then loop again to do the memcpy()s.


Shell sort with a temp variable
doesn't need any relooping that I'm aware of.

e_type is a user defined nonarray type.
GT is a user defined "greater than" macro.
If e_type were to be an array, then all of the e_type
assignments would have to be replaced with memcpy calls.

void s3sort(e_type *array, size_t nmemb)
{
e_type temp, *i, *j, *k, *after;

after = array + nmemb;
if (nmemb > (size_t)-1 / 3) {
nmemb = (size_t)-1 / 3;
}
do {
for (i = array + nmemb; i != after; ++i) {
j = i - nmemb;
if (GT(j, i)) {
k = i;
temp = *k;
do {
*k = *j;
k = j;
if (nmemb + array > j) {
break;
}
j -= nmemb;
} while (GT(j, &temp));
*k = temp;
}
}
nmemb = nmemb != 2 ? 3 * nmemb / 7 : 1;
} while (nmemb != 0);
}

The references to memcpy and memmove
suggest that you're talking about writing qsort in C.
qsort can't depend on malloc (and friends) to provide the temp object,
because malloc may fail with valid arguments, while qsort may not.
That means that if qsort is going to use a temp variable,
it must have an alternative way if malloc fails.
Automatic variables are unsuitable for temp types larger than char,
because their alignment requirements may be less than their size,
while array elements of the same size may need to be aligned
at their full size.
One possible benefit could be that for keys giving the same
value, you want to keep the order in which the respective
objects (and thus the pointers) were stored.
This could of course be done by extending the key but maybe
is not possible in a straightforward way. If we are looking
at the same array, the pointers can be compared whereas this
is not possible if we memcpy() one of the objects.

Er, perhaps I am slow on the uptake but IMO a quicksort _can_ keep
the previous relative order when partitioning. If I've time today, I
will try it out.


Any array sorting algorithm that compares and swaps
nonadjacent elements, like quicksort does,
is going to have a very hard time being made stable,
if stable sorting is what you're talking about.

--
pete
Nov 14 '05 #20

P: n/a
Lawrence Kirby wrote:

pete wrote:

Umh, I cannot think of a situation where you cannot make do
with pointers to array elements -- the information is hidden
behind void *, so I fail to see the restriction.
A simple example is an insertion sort. A basic implementation
compares adjacent elements. If they are out of order it swaps them and
moves on. Essentially one element moves along the array until it is in its
correct place. An optimisation of this is to copy that element to a
temporary variable and compare that against array elements, move them when
out of order and finally write your temporary back to the free slot in the
array when you find the right position. Esssentially you can optimise a
lot of swap operations into moves. With the requirements of C99 the
element must stay in the array for the purposes of comparison so this
optimisation is no longer possible. You can "make do" but what is the
benefit of potentially cripping the efficiency of the qsort()
implementation?


Leave the "moving" item in place in the array until you
discover its destination, then swap it with its neigbors in
one operation. One of Jon Bentley's "Programming Pearls"
columns shows a neat way of doing this, or you could use
memcpy-memmove-memcpy via a temporary area (note that the
restriction applies only when the comparison function is
called; the use of non-array memory is permitted at other
times during the sort).

There's another consideration: How would qsort() acquire
sufficient temporary memory to hold a copy of an item of
arbitrary size? malloc() is unattractive because it can
fail but qsort() cannot. qsort() could, of course, be a
wrapper around two implementations, one for use when malloc()
succeeds and a fall-back to cope with failure -- but that
seems unattractive, since the dynamic memory doesn't seem to
add much to the overall efficiency.
[...]
Yes, that's the problem, C99 appears to have invented a pointless and
counterproductive restriction.


The restriction doesn't seem counter-productive, but I
admit I don't see much point in it. A comparison function
might, perhaps, modify the pointed-to elements (in a way
that doesn't affect the computed result, of course, and after
casting away the `const'-ness), and such modifications would
be problematic if two versions of "the same" element could
co-exist simultaneously. But why would a comparison function
want to do such a thing? I remain baffled.

--
Er*********@sun.com

Nov 14 '05 #21

P: n/a


pete wrote:
Michael Mair wrote:
Lawrence Kirby wrote:
On Fri, 19 Nov 2004 14:22:07 +0100, Michael Mair wrote:

pete wrote:
>Lawrence Kirby wrote:
>
>
>>On Thu, 18 Nov 2004 13:29:38 -0500, Eric Sosman wrote:
>>
>>
>>>Lawrence Kirby wrote:
>>
>>>>I don't see anything in the description of qsort()
>>>>that guarantees this.
>>>
>>> The C89 wording isn't clear, but C99 makes it explicit:
>>>
>>> 7.20.5 Searching and sorting utilities
>>> /2/ The implementation shall ensure that [...] both
>>> arguments (when called from qsort), are pointers to
>>> elements of the array. [...]
>>
>>OK, it is required in C99.
>>Very strange though, it potentially reduces the
>>efficiency of the implementation for no obvious benefit.

Umh, I cannot think of a situation where you cannot make do
with pointers to array elements -- the information is hidden
behind void *, so I fail to see the restriction.

A simple example is an insertion sort. A basic implementation
compares adjacent elements. If they are out of order it swaps
them and moves on. Essentially one element moves along
the array until it is in its correct place.
An optimisation of this is to copy that element to a
temporary variable and compare that against array elements,
move them when out of order and finally write your temporary
back to the free slot in the
array when you find the right position.
Esssentially you can optimise a lot of swap operations into moves.
With the requirements of C99 the
element must stay in the array for the purposes of comparison
so this optimisation is no longer possible.
You can "make do" but what is the
benefit of potentially cripping the efficiency of the qsort()
implementation?
Okay, so we essentially have to switch from a few memcpy()s to
one memmove(). For small partitions left by a quicksort or a
"nearly" sorted array, we probably will lose something.
I guess Shell sort would be even more pathological as you cannot
use one memmove but would have to first find out where everything
goes and then loop again to do the memcpy()s.

Shell sort with a temp variable
doesn't need any relooping that I'm aware of.


We are still in the setting that you *must* *not*
use the temporary variable for comparing -- this is
the whole point. If we may use it, of course no relooping
is necessary. But the requirement that both arguments
passed to compar are pointers to objects residing _inside_
the array (which is what we are talking about) effectively
makes it impossible to avoid swapping the "equidistant"
non-adjacent elements if not by some type of relooping.

Example: We look at the N-distant subsets and are looking
for the right position of some element X within its
remainder class. We compare X with the elements with
index index(X)-i*N. If we use a temporary variable
and have to copy an element to a position with higher
index, we have to copy the temporary object into the
"free slot" in order to be able to compare again.
With insertion sort, we have N==1. So, we can just
find out where exactly X goes, copy it to temp, memmove()
the elements in between one element size "up" and
insert X which should be cheaper than doing 2*(number of
elements to move) memcpy()s.
Alternatively, with the information available, we could
just replace the memmove() by (number of elements to move)+1
memcpy()s. In the non-contiguous setting of Shell sort (N>1),
This is exactly what I would do. The relooping probably is
cheaper than the additional memcpy() calls.

e_type is a user defined nonarray type.
GT is a user defined "greater than" macro.
If e_type were to be an array, then all of the e_type
assignments would have to be replaced with memcpy calls.

void s3sort(e_type *array, size_t nmemb)
{
e_type temp, *i, *j, *k, *after;

after = array + nmemb;
if (nmemb > (size_t)-1 / 3) {
nmemb = (size_t)-1 / 3;
}
do {
for (i = array + nmemb; i != after; ++i) {
j = i - nmemb;
if (GT(j, i)) {
k = i;
temp = *k;
do {
*k = *j;
k = j;
if (nmemb + array > j) {
break;
}
j -= nmemb;
} while (GT(j, &temp)); ^^^^^^^^^^^^
Here goes your approach. *k = temp;
}
}
nmemb = nmemb != 2 ? 3 * nmemb / 7 : 1;
} while (nmemb != 0);
}
I hope I made the problem clearer now.

The references to memcpy and memmove
suggest that you're talking about writing qsort in C.
qsort can't depend on malloc (and friends) to provide the temp object,
because malloc may fail with valid arguments, while qsort may not.
That means that if qsort is going to use a temp variable,
it must have an alternative way if malloc fails.
Automatic variables are unsuitable for temp types larger than char,
because their alignment requirements may be less than their size,
while array elements of the same size may need to be aligned
at their full size.


This is a problem I silently excluded and would rather see
as separate.

One possible benefit could be that for keys giving the same
value, you want to keep the order in which the respective
objects (and thus the pointers) were stored.
This could of course be done by extending the key but maybe
is not possible in a straightforward way. If we are looking
at the same array, the pointers can be compared whereas this
is not possible if we memcpy() one of the objects.

Er, perhaps I am slow on the uptake but IMO a quicksort _can_ keep
the previous relative order when partitioning. If I've time today, I
will try it out.


Any array sorting algorithm that compares and swaps
nonadjacent elements, like quicksort does,
is going to have a very hard time being made stable,
if stable sorting is what you're talking about.


Yep, that is what I was talking about -- I was unaware of
the term "stable sorting", so I only now found out that this
is what I wanted to say...
Cheers
Michael
--
E-Mail: Mine is a gmx dot de address.

Nov 14 '05 #22

P: n/a


Eric Sosman wrote:
Lawrence Kirby wrote:
pete wrote:

Umh, I cannot think of a situation where you cannot make do
with pointers to array elements -- the information is hidden
behind void *, so I fail to see the restriction.
A simple example is an insertion sort. A basic implementation
compares adjacent elements. If they are out of order it swaps them and
moves on. Essentially one element moves along the array until it is in its
correct place. An optimisation of this is to copy that element to a
temporary variable and compare that against array elements, move them when
out of order and finally write your temporary back to the free slot in the
array when you find the right position. Esssentially you can optimise a
lot of swap operations into moves. With the requirements of C99 the
element must stay in the array for the purposes of comparison so this
optimisation is no longer possible. You can "make do" but what is the
benefit of potentially cripping the efficiency of the qsort()
implementation?

Leave the "moving" item in place in the array until you
discover its destination, then swap it with its neigbors in
one operation. One of Jon Bentley's "Programming Pearls"
columns shows a neat way of doing this, or you could use
memcpy-memmove-memcpy via a temporary area (note that the
restriction applies only when the comparison function is
called; the use of non-array memory is permitted at other
times during the sort).


Do you remember which column? I did not want to go through all
the material of the 2nd Edition as it is on the web and could
not find the specific one googling.

There's another consideration: How would qsort() acquire
sufficient temporary memory to hold a copy of an item of
arbitrary size? malloc() is unattractive because it can
fail but qsort() cannot. qsort() could, of course, be a
wrapper around two implementations, one for use when malloc()
succeeds and a fall-back to cope with failure -- but that
seems unattractive, since the dynamic memory doesn't seem to
add much to the overall efficiency.


How would you do that in a portable way? My first thought
was bytewise XORing for swapping two elements but this
usually is the worst way to do it...
However, without having any kind of dynamic memory allocation
the only other thing is having a (medium-sized) fixed temp-array and
memcpy()ing and memmove()ing junks of at most the size of that
array. Sounds unattractive, too.

[...]
Yes, that's the problem, C99 appears to have invented a pointless and
counterproductive restriction.


The restriction doesn't seem counter-productive, but I
admit I don't see much point in it. A comparison function
might, perhaps, modify the pointed-to elements (in a way
that doesn't affect the computed result, of course, and after
casting away the `const'-ness), and such modifications would
be problematic if two versions of "the same" element could
co-exist simultaneously. But why would a comparison function
want to do such a thing? I remain baffled.


Perhaps a pet algorithm of someone. As I wondered aloud
elsewhere: Does anyone know a reason for this?

I think the example of an underlying Shell sort shows that you
would have to change qsort() implementation to one with more
cost -- which is really unnecessary.
Cheers
Michael
--
E-Mail: Mine is a gmx dot de address.

Nov 14 '05 #23

P: n/a
Michael Mair wrote:

Eric Sosman wrote:

Leave the "moving" item in place in the array until you
discover its destination, then swap it with its neigbors in
one operation. One of Jon Bentley's "Programming Pearls"
columns shows a neat way of doing this, or you could use
memcpy-memmove-memcpy via a temporary area (note that the
restriction applies only when the comparison function is
called; the use of non-array memory is permitted at other
times during the sort).


Do you remember which column? I did not want to go through all
the material of the 2nd Edition as it is on the web and could
not find the specific one googling.


I don't recall the column, but I do recall the method.
The challenge is to exchange two adjacent regions of an
array, when the two regions may not be the same size:

abcRSTUVWXYZ -> RSTUVWXYZabc

In the insertion-sort context, "abc" has been determined
to belong just after its neighbors "RSTUVWXYZ," and the
challenge is to get it there. With a temporary area big
enough for "abc" this is simple: memcpy() "abc" to the
temporary, slide the rest leftward with memmove(), and
them memcpy() the temporary to the right-hand end. You
could even make do with a smaller temporary area by using
multiple "rotations:"

abcRSTUVWXYZ -> bcRSTUVWXYZa
-> cRSTUVWXYZab
-> RSTUVWXYZabc

This is unattractive, though, because it copies all the
data multiple times.

Bentley tells the sad tale of many programmers who
tried to make the exchange efficiently but using only a
fixed amount of temporary space. The efforts, he said,
were discouraging: horribly complex code with a tendency
to fall over and die when confronted by edge cases.

Look what happens, though, if you reverse the array
in place, byte-for-byte (or element-for-element):

abcRSTUVWXYZ -> ZYXWVUTSRcba

The two segments are now in the proper positions, but
each segment has been reversed. Correct this by
reversing each segment individually:

ZYXWVUTSRcba -> RSTUVWXYZcba
^^^^^^^^^ ^^^^^^^^^

RSTUVWXYZcba -> RSTUVWXYZabc
^^^ ^^^

.... and the job is complete.

"But what about efficiency? Surely there's a better
way than moving every byte twice!" Bentley thinks not,
based on observation of the complicated but "efficient"
codes. Compilers can easily unroll and otherwise optimize
the simple loop of an in-place reversal, but the more
complicated codes didn't lend themselves to optimization:
too many decisions, too many branches, and so on. Not
only was the "inefficient" method easy to write and easy
to verify, but it actually turned out to be faster than
the (often bug-ridden) "efficient" methods.

If sufficient temporary space is available, I think
the memcpy/memmove/memcpy method is probably best. But
if you've only got a fixed amount of extra space and it
isn't quite big enough, the three-rotation method has
much to recommend it.

--
Er*********@sun.com

Nov 14 '05 #24

P: n/a
Eric Sosman wrote:
Michael Mair wrote:
Eric Sosman wrote:

Leave the "moving" item in place in the array until you
discover its destination, then swap it with its neigbors in
one operation. One of Jon Bentley's "Programming Pearls"
columns shows a neat way of doing this, or you could use
memcpy-memmove-memcpy via a temporary area (note that the
restriction applies only when the comparison function is
called; the use of non-array memory is permitted at other
times during the sort).


Do you remember which column? I did not want to go through all
the material of the 2nd Edition as it is on the web and could
not find the specific one googling.

I don't recall the column, but I do recall the method.
The challenge is to exchange two adjacent regions of an
array, when the two regions may not be the same size:

abcRSTUVWXYZ -> RSTUVWXYZabc

In the insertion-sort context, "abc" has been determined
to belong just after its neighbors "RSTUVWXYZ," and the
challenge is to get it there. With a temporary area big
enough for "abc" this is simple: memcpy() "abc" to the
temporary, slide the rest leftward with memmove(), and
them memcpy() the temporary to the right-hand end. You
could even make do with a smaller temporary area by using
multiple "rotations:"

abcRSTUVWXYZ -> bcRSTUVWXYZa
-> cRSTUVWXYZab
-> RSTUVWXYZabc

This is unattractive, though, because it copies all the
data multiple times.

Bentley tells the sad tale of many programmers who
tried to make the exchange efficiently but using only a
fixed amount of temporary space. The efforts, he said,
were discouraging: horribly complex code with a tendency
to fall over and die when confronted by edge cases.

Look what happens, though, if you reverse the array
in place, byte-for-byte (or element-for-element):

abcRSTUVWXYZ -> ZYXWVUTSRcba

The two segments are now in the proper positions, but
each segment has been reversed. Correct this by
reversing each segment individually:

ZYXWVUTSRcba -> RSTUVWXYZcba
^^^^^^^^^ ^^^^^^^^^

RSTUVWXYZcba -> RSTUVWXYZabc
^^^ ^^^

... and the job is complete.

"But what about efficiency? Surely there's a better
way than moving every byte twice!" Bentley thinks not,
based on observation of the complicated but "efficient"
codes. Compilers can easily unroll and otherwise optimize
the simple loop of an in-place reversal, but the more
complicated codes didn't lend themselves to optimization:
too many decisions, too many branches, and so on. Not
only was the "inefficient" method easy to write and easy
to verify, but it actually turned out to be faster than
the (often bug-ridden) "efficient" methods.

If sufficient temporary space is available, I think
the memcpy/memmove/memcpy method is probably best. But
if you've only got a fixed amount of extra space and it
isn't quite big enough, the three-rotation method has
much to recommend it.


Thank you :-)))

-Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.
Nov 14 '05 #25

P: n/a
> > [...]
Yes, that's the problem, C99 appears to have invented a pointless and
counterproductive restriction.


The restriction doesn't seem counter-productive, but I
admit I don't see much point in it. A comparison function
might, perhaps, modify the pointed-to elements (in a way
that doesn't affect the computed result, of course, and after
casting away the `const'-ness), and such modifications would
be problematic if two versions of "the same" element could
co-exist simultaneously. But why would a comparison function
want to do such a thing? I remain baffled.


Such a function could do this for statistical purposes.
Another possibility is that the comparison could require acquiring external
resources to which a handle may need to be stored in the object.
Some other cacheing mechanism might entail modifying the compared objects...
Modifying the objects during the comparison violates the prototype for the
comparison function where the parameters are defined as const void *, so this
was probably not the intent of the standard, thus not the reason for the
restriction.
I am more inclined to assume that specific alignment constraints unknown to
qsort(), and not necessarily matched by malloc(), make it a good reason to
enforce that the objects always be array elements at comparison time.

Chqrlie.
Nov 14 '05 #26

P: n/a
On Fri, 19 Nov 2004 16:13:08 +0000, pete wrote:

....
The references to memcpy and memmove
suggest that you're talking about writing qsort in C.
qsort can't depend on malloc (and friends) to provide the temp object,
Certainly it can.
because malloc may fail with valid arguments, while qsort may not.
That means that if qsort is going to use a temp variable,
it must have an alternative way if malloc fails.
That's one solution to the problem.

But consider that failing due to lack of resources could in principle
happen to ANY standard library function, or indeed any user-defined
function. If the C standard forbade such failure the language would be to
all intents and purposes unimplementable.

qsort() doesn't have a way to flag a failure to complete the sort to the
caller, so in such circumstances it can't return. It CAN cause the program
execution to terminate abnormally, e.g. by calling abort(). This isn't
really any different to a program "crashing" at any point due to lack of
stack space (on relevant stack based implementations).
Automatic variables are unsuitable for temp types larger than char,
because their alignment requirements may be less than their size,
while array elements of the same size may need to be aligned
at their full size.


However qsort() is part of the implementation so it can be written with
knowledge of implementation alignment characteristics, in the same way
that malloc() can. Of course allocation failure is a possibility here
too.

Lawrence
Nov 14 '05 #27

P: n/a
Lawrence Kirby wrote:

On Fri, 19 Nov 2004 16:13:08 +0000, pete wrote:

...
The references to memcpy and memmove
suggest that you're talking about writing qsort in C.
qsort can't depend on malloc (and friends)
to provide the temp object,
Certainly it can.
because malloc may fail with valid arguments, while qsort may not.
That means that if qsort is going to use a temp variable,
it must have an alternative way if malloc fails.


That's one solution to the problem.

But consider that failing due to lack of resources could in principle
happen to ANY standard library function, or indeed any user-defined
function.
If the C standard forbade such failure the language would be to
all intents and purposes unimplementable.


If an implementation cannot translate and execute a program
like the one described in N869 5.2.4.1, [#1],
then it is not a conforming implementation.
qsort() doesn't have a way to flag a failure to complete
the sort to the
caller, so in such circumstances it can't return.
It CAN cause the program
execution to terminate abnormally, e.g. by calling abort().


You just made that up. There's nothing in the standard which suggests
that qsort can call abort when qsort is called with valid arguments.

--
pete
Nov 14 '05 #28

P: n/a
On Wed, 01 Dec 2004 14:00:27 +0000, pete wrote:
Lawrence Kirby wrote:

On Fri, 19 Nov 2004 16:13:08 +0000, pete wrote:

...
> The references to memcpy and memmove
> suggest that you're talking about writing qsort in C.
> qsort can't depend on malloc (and friends)
> to provide the temp object,


Certainly it can.
> because malloc may fail with valid arguments, while qsort may not.
> That means that if qsort is going to use a temp variable,
> it must have an alternative way if malloc fails.


That's one solution to the problem.

But consider that failing due to lack of resources could in principle
happen to ANY standard library function, or indeed any user-defined
function.
If the C standard forbade such failure the language would be to
all intents and purposes unimplementable.


If an implementation cannot translate and execute a program
like the one described in N869 5.2.4.1, [#1],
then it is not a conforming implementation.


But it is up to the implementation to choose the program. It will clearly
choose a program that it can translate and execute. This does not require
it to be able to translate and execute successfully any other program. The
compiler could be written to recognise this program specifically and just
generate code to produce the correct output. Indeed the program could be
designed to produce no output.
qsort() doesn't have a way to flag a failure to complete the sort to
the
caller, so in such circumstances it can't return. It CAN cause the
program
execution to terminate abnormally, e.g. by calling abort().


You just made that up. There's nothing in the standard which suggests
that qsort can call abort when qsort is called with valid arguments.


I'll try to be clearer. Any program (except the one designated containing
examples of the translation limits) can fail in execution at any point
without creating a conformance issue for the implementation. If qsort() is
part of the implementation and if it decides it can't complete the
operation, it is at perfect liberty to cause the execution of the program
to fail. I suggested calling abort() as a means to achieve this. If you
don't like that it isn't a problem, it will just have to use some
"internal" mechanism, e.g. it could do the equivalent of causing a stack
overflow (or whatever makes sense on the implementation).

Lawrence


Nov 14 '05 #29

P: n/a
Lawrence Kirby wrote:

On Wed, 01 Dec 2004 14:00:27 +0000, pete wrote:
Lawrence Kirby wrote:

On Fri, 19 Nov 2004 16:13:08 +0000, pete wrote:

...

> The references to memcpy and memmove
> suggest that you're talking about writing qsort in C.
> qsort can't depend on malloc (and friends)
> to provide the temp object,

Certainly it can.

> because malloc may fail with valid arguments,
> while qsort may not.
> That means that if qsort is going to use a temp variable,
> it must have an alternative way if malloc fails.

That's one solution to the problem.

But consider that failing due to lack of resources
could in principle
happen to ANY standard library function, or indeed any user-defined
function.
If the C standard forbade such failure the language would be to
all intents and purposes unimplementable.


If an implementation cannot translate and execute a program
like the one described in N869 5.2.4.1, [#1],
then it is not a conforming implementation.


But it is up to the implementation to choose the program.
It will clearly choose a program that it can translate and execute.
This does not require it to be able to translate and execute
successfully any other program. The compiler could be written to
recognise this program specifically and just
generate code to produce the correct output.
Indeed the program could be designed to produce no output.


It has nothing to do with choosing.
Anything that can't translate and execute a C program,
isn't a C implementation. It's as simple as that.

--
pete
Nov 14 '05 #30

P: n/a
pete <pf*****@mindspring.com> writes:
Lawrence Kirby wrote:

[...]
But it is up to the implementation to choose the program.
It will clearly choose a program that it can translate and execute.
This does not require it to be able to translate and execute
successfully any other program. The compiler could be written to
recognise this program specifically and just
generate code to produce the correct output.
Indeed the program could be designed to produce no output.


It has nothing to do with choosing.
Anything that can't translate and execute a C program,
isn't a C implementation. It's as simple as that.


No, it's not as simple as that.

The following is a C program. On a system with infinite available
memory, it will never terminate. No real system can execute it
(unless it optimizes away the recursive calls).

static void recurse(void)
{
char data[1024];
recurse();
recurse();
}

int main(void)
{
recurse();
}

This is an extreme case, but all implementations have capacity
limitations.

--
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.
Nov 14 '05 #31

P: n/a
> The following is a C program. On a system with infinite available
memory, it will never terminate. No real system can execute it
(unless it optimizes away the recursive calls).

static void recurse(void)
{
char data[1024];
recurse();
recurse();
}

int main(void)
{
recurse();
}
Well, a clever C compiler might just compile this as a single infinite
loop, but I wouldn't count on it. This piece of code will confuse a lot
of them as to optimizing.
This is an extreme case, but all implementations have capacity
limitations.


This is an infinite recursion.

Therefore, it goes beyond the scope of any programming language except
maybe a formal Turing machine. In the real world, infinite recursion
makes no sense. Can we really speak of capacity limitations? Yes and no.
What is infinite capacity, to begin with? What kind of problem would an
infinite recursion be able to solve? And lastly, does infinity really
exist? Is our universe finite or infinite?

Are we going too far? ;-)
Nov 14 '05 #32

P: n/a
Guillaume <"grsNOSPAM at NOTTHATmail dot com"> writes:
The following is a C program. On a system with infinite available
memory, it will never terminate. No real system can execute it
(unless it optimizes away the recursive calls).
static void recurse(void)
{
char data[1024];
recurse();
recurse();
}
int main(void)
{
recurse();
}


Well, a clever C compiler might just compile this as a single infinite
loop, but I wouldn't count on it. This piece of code will confuse a lot
of them as to optimizing.


Which is what I meant by "unless it optimizes away the recursive
calls". (I should have referred to transforming them into an infinite
loop; my wording implied eliminating them altogether, which is of
course invalid.)
This is an extreme case, but all implementations have capacity
limitations.


This is an infinite recursion.

Therefore, it goes beyond the scope of any programming language except
maybe a formal Turing machine. In the real world, infinite recursion
makes no sense. Can we really speak of capacity limitations? Yes and no.

[snip]

I agree with your last statement, except for the "and no" part.

All implementations have capacity limitations, some more stringent
than others. If a program has, for example, allocated *almost* all
the memory available to it, a call to qsort() (or to any function) may
fail due to a lack of memory. Since qsort() in particular is likely
to be recursive, it's entirely possible for the initial call to
qsort() to succeed, but for the program to run out of memory while
qsort() is running. There's no mechanism for qsort() to report this
(or any other failure) to the caller; aborting the program is probably
the most reasonable response.

The standard provides a mechanism to report running out of heap
(malloc() returning a null pointer), but not to report running out of
stack. (The standard doesn't use the terms "heap" and "stack", but
you get the idea.)

The standard also allows an implementation to be very sloppy about
documenting its capacity limitations. Since the amount of memory
available to a program can vary randomly depending on the current
state of the system, that's probably unavoidable.

--
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.
Nov 14 '05 #33

This discussion thread is closed

Replies have been disabled for this discussion.