Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > How to apply qsort() with a parameter?

Reply
Thread Tools

How to apply qsort() with a parameter?

 
 
none
Guest
Posts: n/a
 
      10-23-2012
In article <k6413q$l7u$(E-Mail Removed)>,
none) (Rouben Rostamian <rouben@shadow.> wrote:
>How does one apply qsort() if the comparison criterion
>depends on a parameter?
>
>Specifically, suppose I wish to sort an array of int,
>according to distance from a prescribed value `n':
>
>int compar(const void *aa, const void *bb)
>{
> int a = *(int *)aa;
> int b = *(int *)bb;
> return abs(a - n) < abs(b - n);
>}
>
>One way to make this work, is to declare n as a global
>(file scope) variable. Is there a clever way to do this
>without bringing in a global variable?


Thank you everyone for your suggestions and comments.
I knew about GNU's qsort_r() with its extra parameter.
It does exactly what I need. The reason I asked the
question here is that I was holding out hope that
there may be a way of doing something similar in
standard C. From the responses it appears that it is
not possible.

Thanks you again.

--
Rouben Rostamian
 
Reply With Quote
 
 
 
 
Keith Thompson
Guest
Posts: n/a
 
      10-23-2012
rouben@shady.(none) (Rouben Rostamian) writes:
[...]
> Thank you everyone for your suggestions and comments.
> I knew about GNU's qsort_r() with its extra parameter.
> It does exactly what I need. The reason I asked the
> question here is that I was holding out hope that
> there may be a way of doing something similar in
> standard C. From the responses it appears that it is
> not possible.


If qsort_r() isn't already written in standard C, I'm sure it could be.

--
Keith Thompson (The_Other_Keith) http://www.velocityreviews.com/forums/(E-Mail Removed) <http://www.ghoti.net/~kst>
Will write code for food.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
 
Reply With Quote
 
 
 
 
James Kuyper
Guest
Posts: n/a
 
      10-23-2012
On 10/23/2012 12:25 AM, Robert Wessel wrote:
> On Mon, 22 Oct 2012 16:54:25 -0400, Eric Sosman
> <(E-Mail Removed)> wrote:

....
>> Since qsort() itself need not be thread-safe (it need not
>> even be re-entrant within just one thread), the thread-safety
>> of a comparator scarcely matters. A thread-safe comparator
>> could be called by qsort() in one thread while another called
>> it via bsearch(), but that's a bit of a stretch.

>
>
> How is qsort not thread safe or non-reentrant? With the obvious, and
> uninteresting, exception of an attempt to simultaneously sort a single
> array more than once.


He didn't say that qsort() is not thread-safe, or non-reentrant. He said
that qsort() is not required to be thread-safe or reentrant. It's
probably both - there's no obvious reason to make it otherwise - but
he's correct that it's not required to be either.
--
James Kuyper
 
Reply With Quote
 
Eric Sosman
Guest
Posts: n/a
 
      10-23-2012
On 10/23/2012 12:25 AM, Robert Wessel wrote:
>[...]
>> Since qsort() itself need not be thread-safe (it need not
>> even be re-entrant within just one thread), the thread-safety
>> of a comparator scarcely matters. A thread-safe comparator
>> could be called by qsort() in one thread while another called
>> it via bsearch(), but that's a bit of a stretch.

>
> How is qsort not thread safe or non-reentrant? With the obvious, and
> uninteresting, exception of an attempt to simultaneously sort a single
> array more than once.


7.1.4p4: "The functions in the standard library are not
guaranteed to be reentrant and may modify objects with static
or thread storage duration."

Even so, it turns out I was wrong, at least in part. The
quoted language appears in both C99 (except for "or thread") and
C11, but C11 adds two further paragraphs p6,p7 describing some
thread-safety constraints on implementations of the library.
"Upon further review," I now believe

In C11, qsort() is thread-safe.

In C99, qsort() is thread-UNsafe (sort of obvious, since
C99 has no notion of threads).

In both C99 and C11, qsort() is non-reentrant. Two C11
threads can use qsort() simultaneously, but it's still
an error to call qsort() from qsort()'s comparator, or
to call it from a handler for a signal that might be
raised during a qsort().

--
Eric Sosman
(E-Mail Removed)d
 
Reply With Quote
 
Malcolm McLean
Guest
Posts: n/a
 
      10-23-2012
On Tuesday, October 23, 2012 4:52:28 AM UTC+1, none wrote:
> In article <k6413q$l7u$(E-Mail Removed)>,
>
> Thank you everyone for your suggestions and comments.
> I knew about GNU's qsort_r() with its extra parameter.
> It does exactly what I need. The reason I asked the
> question here is that I was holding out hope that
> there may be a way of doing something similar in
> standard C. From the responses it appears that it is
> not possible.
>

No, it's a design fault with qsort(). Functions that take a fucntion pointer
should also take an arbitrary void * which they pass back as a parameter.
But qsort() was very early, before this was realised.
 
Reply With Quote
 
tom st denis
Guest
Posts: n/a
 
      10-23-2012
On Oct 22, 4:54*pm, Eric Sosman <(E-Mail Removed)>
wrote:
> On 10/22/2012 4:25 PM, tom st denis wrote:
>
> > On Oct 22, 2:59 pm, Eric Sosman <(E-Mail Removed)>
> > wrote:
> >>[...]
> >> * * * This setup repeats the switch decision -- which is "just
> >> overhead" -- for every comparison, and there may be a lot of
> >> them. *It would almost surely be better to have three short
> >> comparators than one omnibus comparator.

>
> > But that code is not thread safe and it's not really any simpler than
> > just calling qsort with a variable as the compare callback that is
> > determined locally on the stack.

>
> * * *Since qsort() itself need not be thread-safe (it need not
> even be re-entrant within just one thread), the thread-safety
> of a comparator scarcely matters. *A thread-safe comparator
> could be called by qsort() in one thread while another called
> it via bsearch(), but that's a bit of a stretch.


It's generally a bad idea to write thread unsafe code on purpose
unless you have a reason.

> * * *My personal parser recognizes all the words in your second
> and third lines, but is unable to make sense of them.


I was saying in the function where you call qsort() you could resolve
there which key to sort on and then call the appropriate comparator
function. Instead of having one compare function you'd have n and
they'd all compare a different key.

Tom
 
Reply With Quote
 
Eric Sosman
Guest
Posts: n/a
 
      10-23-2012
On 10/23/2012 10:05 AM, tom st denis wrote:
> On Oct 22, 4:54 pm, Eric Sosman <(E-Mail Removed)>
> wrote:
>> On 10/22/2012 4:25 PM, tom st denis wrote:
>>
>>> On Oct 22, 2:59 pm, Eric Sosman <(E-Mail Removed)>
>>> wrote:
>>>> [...]
>>>> This setup repeats the switch decision -- which is "just
>>>> overhead" -- for every comparison, and there may be a lot of
>>>> them. It would almost surely be better to have three short
>>>> comparators than one omnibus comparator.

>>
>>> But that code is not thread safe and it's not really any simpler than
>>> just calling qsort with a variable as the compare callback that is
>>> determined locally on the stack.

>>
>> Since qsort() itself need not be thread-safe (it need not
>> even be re-entrant within just one thread), the thread-safety
>> of a comparator scarcely matters. A thread-safe comparator
>> could be called by qsort() in one thread while another called
>> it via bsearch(), but that's a bit of a stretch.

>
> It's generally a bad idea to write thread unsafe code on purpose
> unless you have a reason.
>
>> My personal parser recognizes all the words in your second
>> and third lines, but is unable to make sense of them.

>
> I was saying in the function where you call qsort() you could resolve
> there which key to sort on and then call the appropriate comparator
> function. Instead of having one compare function you'd have n and
> they'd all compare a different key.


Ah! Okay, we're in violent agreement. That's exactly
what I meant by suggesting "It would almost surely be better
to have three short comparators than one omnibus comparator."

--
Eric Sosman
(E-Mail Removed)d
 
Reply With Quote
 
Eric Sosman
Guest
Posts: n/a
 
      10-23-2012
On 10/23/2012 10:28 AM, Scott Fluhrer wrote:
> "Eric Sosman" <(E-Mail Removed)> wrote in message
> news:k6441n$oa7$(E-Mail Removed)...
>> On 10/22/2012 1:51 PM, none Rouben Rostamian wrote:
>>> How does one apply qsort() if the comparison criterion
>>> depends on a parameter?
>>>
>>> Specifically, suppose I wish to sort an array of int,
>>> according to distance from a prescribed value `n':
>>>
>>> int compar(const void *aa, const void *bb)
>>> {
>>> int a = *(int *)aa;
>>> int b = *(int *)bb;
>>> return abs(a - n) < abs(b - n);

>>
>> Aside: This can't be right, as it doesn't define
>> a total ordering.
>>

>
> I believe this point could use some expansion. What Eric was refering to
> was the fact that a qsort implementation expects a comparison function that
> returns negative if the first element should appear earlier than the second
> element, positive if the second element should appear earlier, and 0 if you
> don't care. In particular, if compare(a, b) returns positive, compare(b, a)
> must return negative.


Exactly. Also, if compare(a,b) and compare(a,c) both return
zero, then compare(b,c) must return zero. It's easy to see that
the function as shown doesn't satisfy this. (Consider n=0 for
simplicity, then compare(10,1) and compare(10,5) both return zero,
but compare(1,5) returns one.)

> If the above isn't true, well, I don't know if there is any requirement on
> what qsort is allowed to do. The most obvious thing it could do in this
> case is not sort the array as you expect (for example, given the array [1000
> 1] and N=0, it may leave the array undisturbed). Other misbehaviors (such
> as infinite looping, or returning an array which is not a permutation of the
> original, or simply crashing) are less likely, but are still conceivable.


As far as I can see, the behavior is undefined. The "shall
be consistent" requirement is in 7.22.5, which is not part of a
constraint. 4p2 tells us that violating a non-constraint "shall"
yields undefined behavior.

As to outcomes, both crashes and infinite loops seem likely
possibilities to me. For example, a qsort() using the Quicksort
algorithm with Sedgewick's median-of-three heuristic may well
walk off one end or the other of the array if the comparator
misbehaves and fails to stop it. Even if this doesn't loop or
crash, it might exchange some array elements with bytes outside
the array limits.

That's another reason to keep comparators simple: It's
easier to verify their correctness.

--
Eric Sosman
(E-Mail Removed)d
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: How include a large array? Edward A. Falk C Programming 1 04-04-2013 08:07 PM
Wireless Only Desktop - Network Starts too late and AD Computer Policies Don't Apply Kenny Wireless Networking 3 11-08-2005 10:53 PM
How to apply xml commentig code salvatore.difazio@gmail.com ASP .Net 3 09-30-2005 06:22 AM
[Vb.net question] how to apply online update function into program (the effect just like Norton system work live update) chan ASP .Net 1 03-04-2004 02:58 PM
[XSLT] could not apply "apply-templates" Stefan Siegl XML 1 07-18-2003 09:43 AM



Advertisments