Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #27522 > unrolled thread

How to apply qsort() with a parameter?

Back to article view | Back to comp.lang.c

Contents

  How to apply qsort() with a parameter? rouben@shadow.(none) (Rouben Rostamian) - 2012-10-22 17:51 +0000
    Re: How to apply qsort() with a parameter? ImpalerCore <jadill33@gmail.com> - 2012-10-22 11:18 -0700
      Re: How to apply qsort() with a parameter? ImpalerCore <jadill33@gmail.com> - 2012-10-22 11:26 -0700
      Re: How to apply qsort() with a parameter? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-10-22 20:27 +0100
    Re: How to apply qsort() with a parameter? tom st denis <tom@iahu.ca> - 2012-10-22 11:38 -0700
    Re: How to apply qsort() with a parameter? Eric Sosman <esosman@comcast-dot-net.invalid> - 2012-10-22 14:41 -0400
      Re: How to apply qsort() with a parameter? Eric Sosman <esosman@comcast-dot-net.invalid> - 2012-10-22 14:59 -0400
        Re: How to apply qsort() with a parameter? tom st denis <tom@iahu.ca> - 2012-10-22 13:25 -0700
          Re: How to apply qsort() with a parameter? Eric Sosman <esosman@comcast-dot-net.invalid> - 2012-10-22 16:54 -0400
            Re: How to apply qsort() with a parameter? Robert Wessel <robertwessel2@yahoo.com> - 2012-10-22 23:25 -0500
              Re: How to apply qsort() with a parameter? James Kuyper <jameskuyper@verizon.net> - 2012-10-23 07:42 -0400
              Re: How to apply qsort() with a parameter? Eric Sosman <esosman@comcast-dot-net.invalid> - 2012-10-23 08:14 -0400
            Re: How to apply qsort() with a parameter? tom st denis <tom@iahu.ca> - 2012-10-23 07:05 -0700
              Re: How to apply qsort() with a parameter? Eric Sosman <esosman@comcast-dot-net.invalid> - 2012-10-23 10:13 -0400
      Re: How to apply qsort() with a parameter? "Scott Fluhrer" <sfluhrer@ix.netcom.com> - 2012-10-23 10:28 -0400
        Re: How to apply qsort() with a parameter? Eric Sosman <esosman@comcast-dot-net.invalid> - 2012-10-23 10:56 -0400
    Re: How to apply qsort() with a parameter? Öö Tiib <ootiib@hot.ee> - 2012-10-22 15:30 -0700
    Re: How to apply qsort() with a parameter? rouben@shady.(none) (Rouben Rostamian) - 2012-10-23 03:52 +0000
      Re: How to apply qsort() with a parameter? Keith Thompson <kst-u@mib.org> - 2012-10-22 22:46 -0700
        Re: How to apply qsort() with a parameter? pete <pfiland@mindspring.com> - 2012-10-23 16:03 -0400
      Re: How to apply qsort() with a parameter? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2012-10-23 06:43 -0700

Page 1 of 2  [1] 2  Next page →

#27522 — How to apply qsort() with a parameter?

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?

-- 
Rouben Rostamian

[toc] | [next] | [standalone]

#27524

On Oct 22, 1:51 pm, rouben@shadow.(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);
>
> }
>
> 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?

The best method is to reparameterize the qsort function with a
comparison that takes an external parameter.

void qsort_ext( void* base,
                size_t num,
                size_t size,
                int (*cmp_ext_fn)( const void*, const void*, void* ),
                void* ext_data );

Then you write your modified comparison function in this fashion.

int compar(const void *aa, const void *bb, void *nn)
{
  int a = *(const int *)aa;
  int b = *(const int *)bb;
  int n = *(int *)n;
  return abs(a - n) < abs(b - n);
}

If you have the source of a 'qsort' you want to use, you can create
'qsort_ext' by simply adding the external parameter to the comparison
function pointer call.

Best regards,
John D.

[toc] | [prev] | [next] | [standalone]

#27525

On Oct 22, 2:18 pm, ImpalerCore <jadil...@gmail.com> wrote:
> int compar(const void *aa, const void *bb, void *nn)
> {
>   int a = *(const int *)aa;
>   int b = *(const int *)bb;
>   int n = *(int *)n;
>   return abs(a - n) < abs(b - n);
> }

The comparison should probably be 'abs(a - n) - abs(b - n)', not '<'
which is a boolean expression.

Best regards,
John D.

[toc] | [prev] | [next] | [standalone]

#27533

ImpalerCore <jadill33@gmail.com> writes:

> On Oct 22, 1:51 pm, rouben@shadow.(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);
>>
>> }
>>
>> 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?
>
> The best method is to reparameterize the qsort function with a
> comparison that takes an external parameter.
>
> void qsort_ext( void* base,
>                 size_t num,
>                 size_t size,
>                 int (*cmp_ext_fn)( const void*, const void*, void* ),
>                 void* ext_data );
>
> Then you write your modified comparison function in this fashion.
>
> int compar(const void *aa, const void *bb, void *nn)
> {
>   int a = *(const int *)aa;
>   int b = *(const int *)bb;
>   int n = *(int *)n;
>   return abs(a - n) < abs(b - n);
> }
>
> If you have the source of a 'qsort' you want to use, you can create
> 'qsort_ext' by simply adding the external parameter to the comparison
> function pointer call.

Many C libraries already have such a thing.  GNU libc has qsort_r and
Microsoft champions qsort_s -- to the extent that it's in C11.  The BSD
C library also has qsort_r but with a different argument order (for both
qsort_r and the comparison function).  I'll bet there are others.

A mess of #ifdefs can probably render such code reasonably portable, but
maybe the OP wants the code to work in only one of these environments.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#27526

On Oct 22, 1:51 pm, rouben@shadow.(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);
>
> }
>
> 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?

The most portable way is to normalize your input first based on what
you are measuring the distance from then perform your sort.

Tom

[toc] | [prev] | [next] | [standalone]

#27528

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.

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

     No, nothing clever.  You could write multiple comparators,
each hard-wiring a different `n' value:

	int compar10(const void *aa, const void *bb) {
	    ... use n=10 ...
	}

	int compar20(const void *aa, const void *bb) {
	    ... use n=20 ...
	}

     Or, you could subtract n from all the array elements,
use the equivalent of compar0(), and then add n back again.
(Sounds wasteful, but it only adds O(N) time to an operation
that's probably O(N log N) already.)

     Neither alternative strikes me as "clever."  You either
live with the qsort() interface or write your own sort.

-- 
Eric Sosman
esosman@comcast-dot-net.invalid

[toc] | [prev] | [next] | [standalone]

#27531

On 10/22/2012 2:41 PM, Eric Sosman wrote:
> On 10/22/2012 1:51 PM, none Rouben Rostamian wrote:
>> How does one apply qsort() if the comparison criterion
>> depends on a parameter?

     A further observation: Don't go overboard in parameterizing
your comparators.  A comparator may be called a large number of
times during a sort, so it's "in the inner loop" and should be
kept short and swift.  A comparator that examines parameters
P1,P2,P3,... in addition to the items it's comparing starts to
stray from the "short and swift" ideal.

     A particular abuse that always seems to crop up is trying
to use one comparator to sort on multiple keys:

	struct s {
	    int k1;
	    char *k2;
	    double k3;
	};

	int which_key;

	int compare(const void *aa, const void *bb) {
	    const struct s *a = aa;
	    const struct s *b = bb;
	    switch (which_key) {
	    case 1:
	        return (a->k1 > b->k1) - (a->k1 < b->k1);
	    case 2:
	        return strcmp(a->k2, b->k2);
	    case 3:
	        return (a->k3 > b->k3) - (a->k3 < b->k3);
	    default:
	        assert(false);
	    }
	}

	...
	which_key = 2;
	qsort(array, count, sizeof array[0], compare);

     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.

-- 
Eric Sosman
esosman@comcast-dot-net.invalid

[toc] | [prev] | [next] | [standalone]

#27536

On Oct 22, 2:59 pm, Eric Sosman <esos...@comcast-dot-net.invalid>
wrote:
> On 10/22/2012 2:41 PM, Eric Sosman wrote:
>
> > On 10/22/2012 1:51 PM, none Rouben Rostamian wrote:
> >> How does one apply qsort() if the comparison criterion
> >> depends on a parameter?
>
>      A further observation: Don't go overboard in parameterizing
> your comparators.  A comparator may be called a large number of
> times during a sort, so it's "in the inner loop" and should be
> kept short and swift.  A comparator that examines parameters
> P1,P2,P3,... in addition to the items it's comparing starts to
> stray from the "short and swift" ideal.
>
>      A particular abuse that always seems to crop up is trying
> to use one comparator to sort on multiple keys:
>
>         struct s {
>             int k1;
>             char *k2;
>             double k3;
>         };
>
>         int which_key;
>
>         int compare(const void *aa, const void *bb) {
>             const struct s *a = aa;
>             const struct s *b = bb;
>             switch (which_key) {
>             case 1:
>                 return (a->k1 > b->k1) - (a->k1 < b->k1);
>             case 2:
>                 return strcmp(a->k2, b->k2);
>             case 3:
>                 return (a->k3 > b->k3) - (a->k3 < b->k3);
>             default:
>                 assert(false);
>             }
>         }
>
>         ...
>         which_key = 2;
>         qsort(array, count, sizeof array[0], compare);
>
>      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.

Tom

[toc] | [prev] | [next] | [standalone]

#27537

On 10/22/2012 4:25 PM, tom st denis wrote:
> On Oct 22, 2:59 pm, Eric Sosman <esos...@comcast-dot-net.invalid>
> 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.

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

     In any event, the code I showed was an illustration of
what I consider an inferior pattern; the suggested alternative
could in fact be thread-safe.

-- 
Eric Sosman
esosman@comcast-dot-net.invalid

[toc] | [prev] | [next] | [standalone]

#27560

On Mon, 22 Oct 2012 16:54:25 -0400, Eric Sosman
<esosman@comcast-dot-net.invalid> wrote:

>On 10/22/2012 4:25 PM, tom st denis wrote:
>> On Oct 22, 2:59 pm, Eric Sosman <esos...@comcast-dot-net.invalid>
>> 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.


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.

[toc] | [prev] | [next] | [standalone]

#27566

On 10/23/2012 12:25 AM, Robert Wessel wrote:
> On Mon, 22 Oct 2012 16:54:25 -0400, Eric Sosman
> <esosman@comcast-dot-net.invalid> 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

[toc] | [prev] | [next] | [standalone]

#27567

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
esosman@comcast-dot-net.invalid

[toc] | [prev] | [next] | [standalone]

#27573

On Oct 22, 4:54 pm, Eric Sosman <esos...@comcast-dot-net.invalid>
wrote:
> On 10/22/2012 4:25 PM, tom st denis wrote:
>
> > On Oct 22, 2:59 pm, Eric Sosman <esos...@comcast-dot-net.invalid>
> > 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

[toc] | [prev] | [next] | [standalone]

#27575

On 10/23/2012 10:05 AM, tom st denis wrote:
> On Oct 22, 4:54 pm, Eric Sosman <esos...@comcast-dot-net.invalid>
> wrote:
>> On 10/22/2012 4:25 PM, tom st denis wrote:
>>
>>> On Oct 22, 2:59 pm, Eric Sosman <esos...@comcast-dot-net.invalid>
>>> 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
esosman@comcast-dot-net.invalid

[toc] | [prev] | [next] | [standalone]

#27576

"Eric Sosman" <esosman@comcast-dot-net.invalid> wrote in message 
news:k6441n$oa7$1@dont-email.me...
> 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.

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.

-- 
poncho

[toc] | [prev] | [next] | [standalone]

#27579

On 10/23/2012 10:28 AM, Scott Fluhrer wrote:
> "Eric Sosman" <esosman@comcast-dot-net.invalid> wrote in message
> news:k6441n$oa7$1@dont-email.me...
>> 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
esosman@comcast-dot-net.invalid

[toc] | [prev] | [next] | [standalone]

#27543

On Monday, 22 October 2012 20:51:55 UTC+3, none  wrote:
> How does one apply qsort() if the comparison criterion 
> depends on a parameter?

Others have already replied that most platforms offer qsort variants
with additional parameter. 

Also think over why you need to sort with dynamic criteria.
Maybe you only need to find few items with highest order before
your criteria changes again? 
On that case building an heap 
http://en.wikipedia.org/wiki/Heap_(data_structure)
can be more efficient solution. 

[toc] | [prev] | [next] | [standalone]

#27558

In article <k6413q$l7u$1@news.albasani.net>,
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

[toc] | [prev] | [next] | [standalone]

#27563

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) kst-u@mib.org  <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"

[toc] | [prev] | [next] | [standalone]

#27602

Keith Thompson wrote:
> 
> 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.

qsortR,
1   is usable in the same way that qsort_r is
2   is small
3   and has subquadratic worst case behavior.

I could easily come up with a faster
but larger function of the same type, 
if anyone wants to see one.

Here's qsortR:

#include <stddef.h>

void 
qsortR(void *base, size_t nmemb, size_t size, void *thunk, 
       int (*compar)(void *, const void *, const void *))
{
    size_t bytes, h, t;
    unsigned char *array, *after, *i, *j, *k;
    unsigned char *p1, *p2, *end, swap;

    if (nmemb > 1) {
        array = base;
        after = nmemb * size + array;
        nmemb /= 4; 
        h = nmemb + 1;  
        for (t = 1; nmemb != 0; nmemb /= 4) {
            t *= 2;
        }
        do {
            bytes = h * size;
            i = bytes + array;
            do {
                j = i - bytes;
                if (compar(thunk, j, i) > 0) {
                    k = i;
                    do {
                        p1  = j;
                        p2  = k;
                        end = p2 + size;
                        do {
                            swap  = *p1;
                            *p1++ = *p2;
                            *p2++ = swap;
                        } while (p2 != end);
                        if (bytes + array > j) {
                            break;
                        }
                        k = j;
                        j -= bytes;
                    } while (compar(thunk, j, k) > 0);
                }
                i += size;
            } while (i != after);
            t /= 2;
            h = t * t - t * 3 / 2 + 1;
        } while (t != 0);
    }
}

-- 
pete

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.c

csiph-web