Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Is there any way to refer to another array in qsort's compare function?

Reply
Thread Tools

Is there any way to refer to another array in qsort's compare function?

 
 
Stone
Guest
Posts: n/a
 
      12-29-2011
Here's the problem.

I wrote a function 'int my_compare(const void *, const void *);' and
passed it to qsort() of stdlib.h, in order to sort an array named
*ptr* which contains indices of another array *data*. By that I
intended to sort elements of *ptr* (i.e. ptr[i]) using data[ptr[i]] as
the key value.

However, the *data* array was defined as static in main(), and seemed
not easy to access in my_compare(). Is there any way to achieve this?

Thanks&Regards.

Stone.
 
Reply With Quote
 
 
 
 
Dr Nick
Guest
Posts: n/a
 
      12-29-2011
Stone <(E-Mail Removed)> writes:

> Here's the problem.
>
> I wrote a function 'int my_compare(const void *, const void *);' and
> passed it to qsort() of stdlib.h, in order to sort an array named
> *ptr* which contains indices of another array *data*. By that I
> intended to sort elements of *ptr* (i.e. ptr[i]) using data[ptr[i]] as
> the key value.
>
> However, the *data* array was defined as static in main(), and seemed
> not easy to access in my_compare(). Is there any way to achieve this?


Not that I know of. It's a design flaw in the standard library IMO -
any function that takes a user provided function and calls it in this
way should take an extra, void *, parameter that it passes to the called
function. After all, it can always be NULL. In this case, it could
carry a pointer to your "data" array.

There are non-standard versions of qsort (usually called qsort_r or
qsort_s) that do this, but whether you have access to one, and how
concerned you are about portability will feature in your decision on
whether to this or whether to make your array global (or to have a
global pointer to it - suitably named and identified).

Anyone know if this is going to appear in standard C (and if not, why
not?; it seems a clear flaw to me).
--
Online waterways route planner | http://canalplan.eu
Plan trips, see photos, check facilities | http://canalplan.org.uk
 
Reply With Quote
 
 
 
 
Ben Bacarisse
Guest
Posts: n/a
 
      12-29-2011
Stone <(E-Mail Removed)> writes:

> Here's the problem.
>
> I wrote a function 'int my_compare(const void *, const void *);' and
> passed it to qsort() of stdlib.h, in order to sort an array named
> *ptr* which contains indices of another array *data*. By that I
> intended to sort elements of *ptr* (i.e. ptr[i]) using data[ptr[i]] as
> the key value.
>
> However, the *data* array was defined as static in main(), and seemed
> not easy to access in my_compare(). Is there any way to achieve this?


You can either move the array so that it is defined at file scope
(i.e. outside main) or you can arrange for there to be a file-scope
pointer to it:

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

int *aux_sort_ptr;

int my_compare(const void *p1, const void *p2)
{
const int *ip1 = p1, *ip2 = p2;
return aux_sort_ptr[*ip1] - aux_sort_ptr[*ip2];
}

int main(void)
{
static int data[] = { 3, 1, 2 };
int idx[] = { 1, 2, 3 };
aux_sort_ptr = data;
qsort(idx, sizeof idx/sizeof *idx, sizeof *idx, my_compare);
for (int i = 0; i < sizeof idx/sizeof *idx; i++)
printf("idx[%d] = %d, data[%d] = %d\n",
i, idx[i], idx[i], data[idx[i]]);
}

This is ugly (and problematic in threaded code), but there's no elegant
way round it using standard C. Many systems have other sort functions
whose comparison function can be handed another void * (see Dr Nick's
reply) but I don't think and have become common enough to though of as
"almost standard".

--
Ben.
 
Reply With Quote
 
88888 Dihedral
Guest
Posts: n/a
 
      12-29-2011
Ben Bacarisse於 2011年12月29日星期四UTC+8下午7時58分14 寫道:
> Stone <(E-Mail Removed)> writes:
>
> > Here's the problem.
> >
> > I wrote a function 'int my_compare(const void *, const void *);' and
> > passed it to qsort() of stdlib.h, in order to sort an array named
> > *ptr* which contains indices of another array *data*. By that I
> > intended to sort elements of *ptr* (i.e. ptr[i]) using data[ptr[i]] as
> > the key value.
> >
> > However, the *data* array was defined as static in main(), and seemed
> > not easy to access in my_compare(). Is there any way to achieve this?

>
> You can either move the array so that it is defined at file scope
> (i.e. outside main) or you can arrange for there to be a file-scope
> pointer to it:
>
> #include <stdlib.h>
> #include <stdio.h>
>
> int *aux_sort_ptr;
>
> int my_compare(const void *p1, const void *p2)
> {
> const int *ip1 = p1, *ip2 = p2;
> return aux_sort_ptr[*ip1] - aux_sort_ptr[*ip2];
> }
>
> int main(void)
> {
> static int data[] = { 3, 1, 2 };
> int idx[] = { 1, 2, 3 };
> aux_sort_ptr = data;
> qsort(idx, sizeof idx/sizeof *idx, sizeof *idx, my_compare);
> for (int i = 0; i < sizeof idx/sizeof *idx; i++)
> printf("idx[%d] = %d, data[%d] = %d\n",
> i, idx[i], idx[i], data[idx[i]]);
> }
>
> This is ugly (and problematic in threaded code), but there's no elegant
> way round it using standard C. Many systems have other sort functions
> whose comparison function can be handed another void * (see Dr Nick's
> reply) but I don't think and have become common enough to though of as
> "almost standard".
>
> --
> Ben.


This method uses more memory. Do you think that just
overloading the comparison function by OOP can make it not choking at all?

 
Reply With Quote
 
Dr Nick
Guest
Posts: n/a
 
      12-29-2011
88888 Dihedral <(E-Mail Removed)> writes:

> Ben Bacarisse於 2011年12月29日星期四UTC+8下午7時58分14 寫道:
>> Stone <(E-Mail Removed)> writes:
>>
>> > Here's the problem.
>> >
>> > I wrote a function 'int my_compare(const void *, const void *);' and
>> > passed it to qsort() of stdlib.h, in order to sort an array named
>> > *ptr* which contains indices of another array *data*. By that I
>> > intended to sort elements of *ptr* (i.e. ptr[i]) using data[ptr[i]] as
>> > the key value.
>> >
>> > However, the *data* array was defined as static in main(), and seemed
>> > not easy to access in my_compare(). Is there any way to achieve this?

>>
>> You can either move the array so that it is defined at file scope
>> (i.e. outside main) or you can arrange for there to be a file-scope
>> pointer to it:
>>
>> #include <stdlib.h>
>> #include <stdio.h>
>>
>> int *aux_sort_ptr;
>>
>> int my_compare(const void *p1, const void *p2)
>> {
>> const int *ip1 = p1, *ip2 = p2;
>> return aux_sort_ptr[*ip1] - aux_sort_ptr[*ip2];
>> }
>>
>> int main(void)
>> {
>> static int data[] = { 3, 1, 2 };
>> int idx[] = { 1, 2, 3 };
>> aux_sort_ptr = data;
>> qsort(idx, sizeof idx/sizeof *idx, sizeof *idx, my_compare);
>> for (int i = 0; i < sizeof idx/sizeof *idx; i++)
>> printf("idx[%d] = %d, data[%d] = %d\n",
>> i, idx[i], idx[i], data[idx[i]]);
>> }
>>
>> This is ugly (and problematic in threaded code), but there's no elegant
>> way round it using standard C. Many systems have other sort functions
>> whose comparison function can be handed another void * (see Dr Nick's
>> reply) but I don't think and have become common enough to though of as
>> "almost standard".

>
> This method uses more memory.


One pointer's worth.

> Do you think that just
> overloading the comparison function by OOP can make it not choking at all?


Why do you say that "Do you think that just overloading the comparison
function by OOP can make it not choking at all?"

To Stone: No-one has a clue what 88888 Dihedral is on about. Many of us
suspect him to be a poor attempt to pass the Turing test. Whatever he
is, don't worry about his comments.
--
Online waterways route planner | http://canalplan.eu
Plan trips, see photos, check facilities | http://canalplan.org.uk
 
Reply With Quote
 
88888 Dihedral
Guest
Posts: n/a
 
      12-29-2011
Dr Nick於 2011年12月29日星期四UTC+8下午8時37分26 寫道:
> 88888 Dihedral <(E-Mail Removed)> writes:
>
> > Ben Bacarisse於 2011年12月29日星期四UTC+8下午7時58分14 寫道:
> >> Stone <(E-Mail Removed)> writes:
> >>
> >> > Here's the problem.
> >> >
> >> > I wrote a function 'int my_compare(const void *, const void *);' and
> >> > passed it to qsort() of stdlib.h, in order to sort an array named
> >> > *ptr* which contains indices of another array *data*. By that I
> >> > intended to sort elements of *ptr* (i.e. ptr[i]) using data[ptr[i]] as
> >> > the key value.
> >> >
> >> > However, the *data* array was defined as static in main(), and seemed
> >> > not easy to access in my_compare(). Is there any way to achieve this?
> >>
> >> You can either move the array so that it is defined at file scope
> >> (i.e. outside main) or you can arrange for there to be a file-scope
> >> pointer to it:
> >>
> >> #include <stdlib.h>
> >> #include <stdio.h>
> >>
> >> int *aux_sort_ptr;
> >>
> >> int my_compare(const void *p1, const void *p2)
> >> {
> >> const int *ip1 = p1, *ip2 = p2;
> >> return aux_sort_ptr[*ip1] - aux_sort_ptr[*ip2];
> >> }
> >>
> >> int main(void)
> >> {
> >> static int data[] = { 3, 1, 2 };
> >> int idx[] = { 1, 2, 3 };
> >> aux_sort_ptr = data;
> >> qsort(idx, sizeof idx/sizeof *idx, sizeof *idx, my_compare);
> >> for (int i = 0; i < sizeof idx/sizeof *idx; i++)
> >> printf("idx[%d] = %d, data[%d] = %d\n",
> >> i, idx[i], idx[i], data[idx[i]]);
> >> }
> >>
> >> This is ugly (and problematic in threaded code), but there's no elegant
> >> way round it using standard C. Many systems have other sort functions
> >> whose comparison function can be handed another void * (see Dr Nick's
> >> reply) but I don't think and have become common enough to though of as
> >> "almost standard".

> >
> > This method uses more memory.

>
> One pointer's worth.
>
> > Do you think that just
> > overloading the comparison function by OOP can make it not choking at all?

>
> Why do you say that "Do you think that just overloading the comparison
> function by OOP can make it not choking at all?"
>
> To Stone: No-one has a clue what 88888 Dihedral is on about. Many of us
> suspect him to be a poor attempt to pass the Turing test. Whatever he
> is, don't worry about his comments.
> --
> Online waterways route planner | http://canalplan.eu
> Plan trips, see photos, check facilities | http://canalplan.org.uk


Just feed a segment of repeated integers, say, 3,4,5,6,3,4, 5, 6
3,4,5, 6.... for several thousands then the program you posted will choke at the segment.



 
Reply With Quote
 
Dr Nick
Guest
Posts: n/a
 
      12-29-2011
88888 Dihedral <(E-Mail Removed)> writes:

> Dr Nick於 2011年12月29日星期四UTC+8下午8時37分26 寫道:
>> 88888 Dihedral <(E-Mail Removed)> writes:
>>
>> > Ben Bacarisse於 2011年12月29日星期四UTC+8下午7時58分14 寫道:
>> >> Stone <(E-Mail Removed)> writes:
>> >>
>> >> > Here's the problem.
>> >> >
>> >> > I wrote a function 'int my_compare(const void *, const void *);' and
>> >> > passed it to qsort() of stdlib.h, in order to sort an array named
>> >> > *ptr* which contains indices of another array *data*. By that I
>> >> > intended to sort elements of *ptr* (i.e. ptr[i]) using data[ptr[i]] as
>> >> > the key value.
>> >> >
>> >> > However, the *data* array was defined as static in main(), and seemed
>> >> > not easy to access in my_compare(). Is there any way to achieve this?
>> >>
>> >> You can either move the array so that it is defined at file scope
>> >> (i.e. outside main) or you can arrange for there to be a file-scope
>> >> pointer to it:
>> >>
>> >> #include <stdlib.h>
>> >> #include <stdio.h>
>> >>
>> >> int *aux_sort_ptr;
>> >>
>> >> int my_compare(const void *p1, const void *p2)
>> >> {
>> >> const int *ip1 = p1, *ip2 = p2;
>> >> return aux_sort_ptr[*ip1] - aux_sort_ptr[*ip2];
>> >> }
>> >>
>> >> int main(void)
>> >> {
>> >> static int data[] = { 3, 1, 2 };
>> >> int idx[] = { 1, 2, 3 };
>> >> aux_sort_ptr = data;
>> >> qsort(idx, sizeof idx/sizeof *idx, sizeof *idx, my_compare);
>> >> for (int i = 0; i < sizeof idx/sizeof *idx; i++)
>> >> printf("idx[%d] = %d, data[%d] = %d\n",
>> >> i, idx[i], idx[i], data[idx[i]]);
>> >> }
>> >>
>> >> This is ugly (and problematic in threaded code), but there's no elegant
>> >> way round it using standard C. Many systems have other sort functions
>> >> whose comparison function can be handed another void * (see Dr Nick's
>> >> reply) but I don't think and have become common enough to though of as
>> >> "almost standard".
>> >
>> > This method uses more memory.

>>
>> One pointer's worth.
>>
>> > Do you think that just
>> > overloading the comparison function by OOP can make it not choking at all?

>>
>> Why do you say that "Do you think that just overloading the comparison
>> function by OOP can make it not choking at all?"
>>
>> To Stone: No-one has a clue what 88888 Dihedral is on about. Many of us
>> suspect him to be a poor attempt to pass the Turing test. Whatever he
>> is, don't worry about his comments.

>
> Just feed a segment of repeated integers, say, 3,4,5,6,3,4, 5, 6
> 3,4,5, 6.... for several thousands then the program you posted will choke at the segment.


See what I mean? It's complete gibberish without any context,
understanding of code or relevance to the question.

a) I didn't post any program
b) The only way this differs from what the OP described but didn't post
is that aux_pointer has been added.
c) Changing the comparison function will have no effect on the memory
used
d) Do you ever answer questions or just spray out this stuff?

Sorry to the rest of you for this, I'm not yet killfiling him as I worry
that he'll confuse people asking for help. I'm also trying to diagnose
what's going on.
--
Online waterways route planner | http://canalplan.eu
Plan trips, see photos, check facilities | http://canalplan.org.uk
 
Reply With Quote
 
Ben Bacarisse
Guest
Posts: n/a
 
      12-29-2011
Bull in a China Blue Shop <(E-Mail Removed)> writes:

> In article <(E-Mail Removed)>,
> Stone <(E-Mail Removed)> wrote:
>
>> Here's the problem.
>>
>> I wrote a function 'int my_compare(const void *, const void *);' and
>> passed it to qsort() of stdlib.h, in order to sort an array named
>> *ptr* which contains indices of another array *data*. By that I
>> intended to sort elements of *ptr* (i.e. ptr[i]) using data[ptr[i]] as
>> the key value.
>>
>> However, the *data* array was defined as static in main(), and seemed
>> not easy to access in my_compare(). Is there any way to achieve this?

>
> MacOSX has qsort_r which passes a context pointer to qsort_r which, in turn,
> passes it to the compare. I don't know if other implementations have this.


It's in most modern versions of the GNU C library (apparently since
version 2. but it's not documented yet. I think qsort_r is probably
close to being reliably available on *nix type systems but I don't know
about Windows C libraries.

For the record, here's the same program I posted but using qsort_r:

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

int my_compare(const void *p1, const void *p2, void *cp)
{
const int *ip1 = p1, *ip2 = p2, *aux_sort_ptr = cp;
return aux_sort_ptr[*ip1] - aux_sort_ptr[*ip2];
}

int main(void)
{
static int data[] = { 3, 1, 2 };
int idx[] = { 1, 2, 3 };
qsort_r(idx, sizeof idx/sizeof *idx, sizeof *idx, my_compare, data);
for (int i = 0; i < sizeof idx/sizeof *idx; i++)
printf("idx[%d] = %d, data[%d] = %d\n",
i, idx[i], idx[i], data[idx[i]]);
}

(compile, on modern Linux at least, with -std=c99 -D_GNU_SOURCE)

--
Ben.
 
Reply With Quote
 
Ben Bacarisse
Guest
Posts: n/a
 
      12-29-2011
Ben Bacarisse <(E-Mail Removed)> writes:

> Bull in a China Blue Shop <(E-Mail Removed)> writes:

<snip>
>> MacOSX has qsort_r which passes a context pointer to qsort_r which, in turn,
>> passes it to the compare. I don't know if other implementations have this.

>
> It's in most modern versions of the GNU C library (apparently since
> version 2. but it's not documented yet.


Argh! I decided to write the missing man page and in so doing I found
the following mess:

The GNU version has prototype

void qsort_r(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *, void *),
void *data);

I.e. the data pointer is last and gets passed as the third argument to
the comparison function.

The BSD version is

void qsort_r(void *base, size_t nmemb, size_t size, void *data,
int (*compar)(void *, const void *, const void *));

with the data pointer as the fourth argument which gets passed as the
first argument to the comparison function.

Microsoft decided to do this:

void qsort_s(void *base, size_t nmemb, size_t size,
int (*compare)(void *, const void *, const void *),
void *data);

using the argument order of the GNU version and the comparison function
of the BSD version.

Annex K of the new C standard defines an option set of library extension
based on Microsoft's supposedly "safer" functions. Here we find (edited
for consistency):

errno_t qsort_s(void *base, rsize_t nmemb, rsize_t size,
int (*compar)(const void *, const void *, void *),
void *data);

which follows the GNU version except for the name and the return type!
I don't know why the online documentation for Microsoft systems does not
used this version.

> I think qsort_r is probably
> close to being reliably available on *nix type systems but I don't know
> about Windows C libraries.


So, no. There is no widely available qsort function that takes a data
pointer. If the documentation is right, you can't even use the
quasi-standard qsort_s with Microsoft's C library.

It's a shame that we are left with this mess. Annex K is optional, and
is an all-or-nothing set of extensions (I may have misunderstood that)
so qsort_s is likely to languish alongside all the other _s functions.
qsort_r is functionally better that qsort -- the change is not a
mythical safety advantage.

<snip>
--
Ben.
 
Reply With Quote
 
James Kuyper
Guest
Posts: n/a
 
      12-29-2011
On 12/29/2011 03:27 AM, Stone wrote:
> Here's the problem.
>
> I wrote a function 'int my_compare(const void *, const void *);' and
> passed it to qsort() of stdlib.h, in order to sort an array named
> *ptr* which contains indices of another array *data*. By that I
> intended to sort elements of *ptr* (i.e. ptr[i]) using data[ptr[i]] as
> the key value.
>
> However, the *data* array was defined as static in main(), and seemed
> not easy to access in my_compare(). Is there any way to achieve this?


One alternative is to redefine ptr to contain pointers, rather than
indices, so instead of using data[ptr[i]] you use *ptr[i].
 
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
is there a way to refer to public properties in other user controls Web Search Store ASP .Net Web Controls 11 04-23-2008 07:00 PM
is there a way to refer to public properties in other user controls Web Search Store ASP .Net Web Services 11 04-23-2008 07:00 PM
is there a way to refer to public properties in other user controls Web Search Store ASP .Net 11 04-23-2008 07:00 PM
501 PIX "deny any any" "allow any any" Any Anybody? Networking Student Cisco 4 11-16-2006 10:40 PM
is there a quick way to compare the results from two arrays and note the diffences? windandwaves HTML 1 03-24-2005 09:49 PM



Advertisments