Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Sorting a Dynamic Array of Pointers

Reply
Thread Tools

Sorting a Dynamic Array of Pointers

 
 
jehugaleahsa@gmail.com
Guest
Posts: n/a
 
      02-19-2010
Hello:

I am playing around with a data structure in C. It is a dynamically
growing array of pointers. So, really, it is just a void** with a
count and capacity.

I want to provide a sorting algorithm that takes a comparison function
with the signature qsort expects.

However, qsort is sending a void** instead of a void*, so all the
comparison functions need to be written like this:

int person_comparison(void const* value1, void const* value2)
{
person *const* t1 = (person *const*)value1;
person *const* t2 = (person *const*)value2;
person *const p1 = *t1;
person *const p2 = *t2;
/* compare the two people */
}

I want to avoid forcing clients of my class to do this double
dereference. However, I have no clue how to transform what qsort sends
to the comparison. I was thinking about creating a function that would
dereference the void**'s and then call the comparison the user passed
in with the dereferenced void*'s. In C++, I would accomplish using a
functor, but I don't know how to do this in C. I'd like to avoid
writing my own quick sort.

Let me know if you need to see more code. Any help would be
appreciated.

Thanks,
Travis Parks
 
Reply With Quote
 
 
 
 
Barry Schwarz
Guest
Posts: n/a
 
      02-19-2010
On Thu, 18 Feb 2010 19:18:30 -0800 (PST), "(E-Mail Removed)"
<(E-Mail Removed)> wrote:

>Hello:
>
>I am playing around with a data structure in C. It is a dynamically
>growing array of pointers. So, really, it is just a void** with a
>count and capacity.
>
>I want to provide a sorting algorithm that takes a comparison function
>with the signature qsort expects.
>
>However, qsort is sending a void** instead of a void*, so all the
>comparison functions need to be written like this:
>
>int person_comparison(void const* value1, void const* value2)
>{
> person *const* t1 = (person *const*)value1;
> person *const* t2 = (person *const*)value2;
> person *const p1 = *t1;
> person *const p2 = *t2;
> /* compare the two people */
>}
>
>I want to avoid forcing clients of my class to do this double
>dereference. However, I have no clue how to transform what qsort sends
>to the comparison. I was thinking about creating a function that would
>dereference the void**'s and then call the comparison the user passed
>in with the dereferenced void*'s. In C++, I would accomplish using a
>functor, but I don't know how to do this in C. I'd like to avoid
>writing my own quick sort.


qsort will always send the address of two array elements, each with
type const void*. Since the elements of your array are in fact
pointers, then each address your compare function receives is of
necessity the address of a pointer to your object of interest,
conveniently represented by the ** notation. You have no choice but
to dereference this address to obtain the pointer you are really
interested in.

Now you need to figure out what type you want the result of this
dereference to be. What you have coded above defines p1 as a constant
pointer to person. While I doubt you will change the value of p1, I'm
pretty sure it is more important to insure you never change the value
of the person. What you want is a pointer to a constant person. (See
6.2.5-28 for an explanation) I guess you could combine the two into a
constant pointer to a constant person but the declaration of the
compare function is really intended to insure you never change the
objects being compared.

The cast and the dereference can be combined into a single statement,
either
const person *p1 = *(const person**)value1;
or
const person * const p1 = *(const person*const*)value1;

Furthermore, all the const qualifiers inside the casts are unnecessary
since you are allowed to add the qualification implicitly
const person *p1 = *(person**)value1;
const person * const p2 = *(person**)value2;

--
Remove del for email
 
Reply With Quote
 
 
 
 
Jehu Galeahsa
Guest
Posts: n/a
 
      02-19-2010
On Feb 18, 10:28*pm, Barry Schwarz <(E-Mail Removed)> wrote:
> On Thu, 18 Feb 2010 19:18:30 -0800 (PST), "(E-Mail Removed)"
>
>
>
>
>
> <(E-Mail Removed)> wrote:
> >Hello:

>
> >I am playing around with a data structure in C. It is a dynamically
> >growing array of pointers. So, really, it is just a void** with a
> >count and capacity.

>
> >I want to provide a sorting algorithm that takes a comparison function
> >with the signature qsort expects.

>
> >However, qsort is sending a void** instead of a void*, so all the
> >comparison functions need to be written like this:

>
> >int person_comparison(void const* value1, void const* value2)
> >{
> > * *person *const* t1 = (person *const*)value1;
> > * *person *const* t2 = (person *const*)value2;
> > * *person *const p1 = *t1;
> > * *person *const p2 = *t2;
> > * */* compare the two people */
> >}

>
> >I want to avoid forcing clients of my class to do this double
> >dereference. However, I have no clue how to transform what qsort sends
> >to the comparison. I was thinking about creating a function that would
> >dereference the void**'s and then call the comparison the user passed
> >in with the dereferenced void*'s. In C++, I would accomplish using a
> >functor, but I don't know how to do this in C. I'd like to avoid
> >writing my own quick sort.

>
> qsort will always send the address of two array elements, each with
> type const void*. *Since the elements of your array are in fact
> pointers, then each address your compare function receives is of
> necessity the address of a pointer to your object of interest,
> conveniently represented by the ** notation. *You have no choice but
> to dereference this address to obtain the pointer you are really
> interested in.
>
> Now you need to figure out what type you want the result of this
> dereference to be. *What you have coded above defines p1 as a constant
> pointer to person. *While I doubt you will change the value of p1, I'm
> pretty sure it is more important to insure you never change the value
> of the person. *What you want is a pointer to a constant person. *(See
> 6.2.5-28 for an explanation) *I guess you could combine the two into a
> constant pointer to a constant person but the declaration of the
> compare function is really intended to insure you never change the
> objects being compared.
>
> The cast and the dereference can be combined into a single statement,
> either
> * * *const person *p1 = *(const person**)value1;
> or
> * * const person * const p1 = *(const person*const*)value1;
>
> Furthermore, all the const qualifiers inside the casts are unnecessary
> since you are allowed to add the qualification implicitly
> * * const person *p1 = *(person**)value1;
> * * const person * const p2 = *(person**)value2;
>
> --
> Remove del for email- Hide quoted text -
>
> - Show quoted text -


Yeah, I figured out my const mistake last night. I also made it one
line, but thanks for the pointers. I'm rusty, let me tell ya.

So, are you telling me I can't provide a qsort-like interface without
reinventing the wheel?

In general, would you say that data structures like my class are
avoided in C?

The reason for my question: We have a huge application at work that
uses Pro*C. The big problem with it is that it is tens of thousands of
lines of code and all of the Pro*C is mixed in-line with the business
logic. There is a massive amount of code simply for converting between
VARCHARs and char*s. If the code were rewritten so that the Pro*C was
encapsulated within methods, such that the results were converted to
raw ADTs and stored in a data structure, we wouldn't have such a hard
time maintaining it. Nothing is more annoying than finding a 20 year
old bug because someone forgot to NULL-terminate a VARCHAR before
passing it to strcmp!

We are currently analyzing possible approaches to take when writing
new features and reworking old ones. We are hoping to find an easily
repeatable process. Without a data structure, we have to do all of the
processing while looping through the SQL results. You can't even
determine how many results there were without running once through. We
can't use plain-Jane arrays because we don't necessarily have an upper
limit. We want to isolate any dynamic array allocation logic to a
single set of code.

Well, just thought I would share. If we really can't provide a qsort
interface, I suppose we'll just copy our libraries and tweak it.
 
Reply With Quote
 
Jehu Galeahsa
Guest
Posts: n/a
 
      02-19-2010
On Feb 19, 4:21*am, pete <(E-Mail Removed)> wrote:
> (E-Mail Removed) wrote:
> > Hello:

>
> > I am playing around with a data structure in C. It is a dynamically
> > growing array of pointers. So, really, it is just a void** with a
> > count and capacity.

>
> Why aren't you using a (person**) instead of a (void**)?


We want to reuse the same code for all pointer types. A little casting
here and there isn't a big deal.

>
> > I want to provide a sorting algorithm that takes a comparison function
> > with the signature qsort expects.

>
> > However, qsort is sending a void** instead of a void*,

>
> I suspect that it isn't.


The signature is a const void *. But, that (const void *) is really a
const pointer to another (void *). That (void *) is really a (person
*). Since qsort sends a void * pointing to the element being sorted, I
am getting a void **, effectively. At least that's as far as I want to
wrap my mind around it.

>
>
>
>
>
> > so all the
> > comparison functions need to be written like this:

>
> > int person_comparison(void const* value1, void const* value2)
> > {
> > * *person *const* t1 = (person *const*)value1;
> > * *person *const* t2 = (person *const*)value2;
> > * *person *const p1 = *t1;
> > * *person *const p2 = *t2;
> > * */* compare the two people */
> > }

>
> > I want to avoid forcing clients of my class to do this double
> > dereference. However, I have no clue how to transform what qsort sends
> > to the comparison. I was thinking about creating a function that would
> > dereference the void**'s and then call the comparison the user passed
> > in with the dereferenced void*'s. In C++, I would accomplish using a
> > functor, but I don't know how to do this in C. I'd like to avoid
> > writing my own quick sort.

>
> > Let me know if you need to see more code. Any help would be
> > appreciated.

>
> Show me a C definition of a person.


I will paste my test file for you in a different post.

>
> --
> pete- Hide quoted text -
>
> - Show quoted text -


 
Reply With Quote
 
Jehu Galeahsa
Guest
Posts: n/a
 
      02-19-2010
#include "array_list.h"
#include <assert.h>
#include <stdio.h>

typedef struct person_
{
char * name;
int age;
} person;

person * create_person(char * name, int age)
{
person * p = (person *)malloc(sizeof(person));
p->age = age;
p->name = name;
return p;
}

char * person_get_name(person const* person)
{
return person->name;
}

int person_get_age(person const* person)
{
return person->age;
}

void print_person(void * item)
{
person * p = (person *)item;
printf("%s is %d.\n", person_get_name(p), person_get_age(p));
}

int person_comparison(void const* value1, void const* value2)
{
person const* p1 = *(person const**)value1;
person const* p2 = *(person const**)value2;
int age1 = person_get_age(p1);
int age2 = person_get_age(p2);
return age1 - age2;
}

int main(int argc, char ** argv)
{
int capacity = 10;
int index = 0;
person * last = 0;
person * replacement = 0;

array_list lst;
array_list_init(&lst, sizeof(person), capacity);
assert(array_list_get_capacity(&lst) == capacity);
assert(array_list_get_count(&lst) == 0);

printf("Printing empty list:\n");
array_list_for_each(&lst, print_person);

for (index = 0; index != 10; ++index)
{
person * p = create_person("Tom", index);
array_list_add(&lst, p);
}

printf("Printing added items:\n");
array_list_for_each(&lst, print_person);

last = create_person("Tom", index);
array_list_add(&lst, last);

printf("Printing items after adding last item:\n");
array_list_for_each(&lst, print_person);

for (index = 0; index != array_list_get_count(&lst); ++index)
{
person * p = (person *)array_list_get_item(&lst, index);
assert(person_get_age(p) == index);
}

replacement = create_person("Tom", -1);
array_list_set_item(&lst, 0, replacement);
replacement = array_list_get_item(&lst, 0);
assert(person_get_age(replacement) == -1);

printf("Printing item after replacing first item:\n");
array_list_for_each(&lst, print_person);

replacement = create_person("Tom", 2);
array_list_insert(&lst, 0, replacement);
replacement = array_list_get_item(&lst, 0);
assert(person_get_age(replacement) == 2);

printf("Printing item after inserting at the front:\n");
array_list_for_each(&lst, print_person);

replacement = create_person("Tom", 4);
array_list_insert(&lst, 3, replacement);
replacement = array_list_get_item(&lst, 3);
assert(person_get_age(replacement) == 4);

printf("Printing item after inserting at the end:\n");
array_list_for_each(&lst, print_person);

array_list_trim(&lst);
replacement = create_person("Tom", 5);
index = array_list_get_count(&lst);
array_list_insert(&lst, index, replacement);
replacement = array_list_get_item(&lst, index);
assert(person_get_age(replacement) == 5);

printf("Printing item after inserting at the end:\n");
array_list_for_each(&lst, print_person);

//array_list_sort(&lst, person_comparison);

//printf("Printing after sorting by age:\n");
//array_list_for_each(&lst, print_person);

array_list_clear(&lst);
for (index = 0; index != 1000; ++index)
{
person * p = create_person("Tom", rand());
array_list_add(&lst, p);
}
//array_list_sort(&lst, person_comparison);

//printf("Printing after sorting a large number of people by age:
\n");
//array_list_for_each(&lst, print_person);

array_list_destroy(&lst);
return 0;
}
 
Reply With Quote
 
Barry Schwarz
Guest
Posts: n/a
 
      02-20-2010
On Fri, 19 Feb 2010 15:25:30 -0800 (PST), Jehu Galeahsa
<(E-Mail Removed)> wrote:

>On Feb 18, 10:28*pm, Barry Schwarz <(E-Mail Removed)> wrote:
>> On Thu, 18 Feb 2010 19:18:30 -0800 (PST), "(E-Mail Removed)"
>>
>>
>>
>>
>>
>> <(E-Mail Removed)> wrote:
>> >Hello:

>>
>> >I am playing around with a data structure in C. It is a dynamically
>> >growing array of pointers. So, really, it is just a void** with a
>> >count and capacity.

>>
>> >I want to provide a sorting algorithm that takes a comparison function
>> >with the signature qsort expects.

>>
>> >However, qsort is sending a void** instead of a void*, so all the
>> >comparison functions need to be written like this:

>>
>> >int person_comparison(void const* value1, void const* value2)
>> >{
>> > * *person *const* t1 = (person *const*)value1;
>> > * *person *const* t2 = (person *const*)value2;
>> > * *person *const p1 = *t1;
>> > * *person *const p2 = *t2;
>> > * */* compare the two people */
>> >}

>>
>> >I want to avoid forcing clients of my class to do this double
>> >dereference. However, I have no clue how to transform what qsort sends
>> >to the comparison. I was thinking about creating a function that would
>> >dereference the void**'s and then call the comparison the user passed
>> >in with the dereferenced void*'s. In C++, I would accomplish using a
>> >functor, but I don't know how to do this in C. I'd like to avoid
>> >writing my own quick sort.

>>
>> qsort will always send the address of two array elements, each with
>> type const void*. *Since the elements of your array are in fact
>> pointers, then each address your compare function receives is of
>> necessity the address of a pointer to your object of interest,
>> conveniently represented by the ** notation. *You have no choice but
>> to dereference this address to obtain the pointer you are really
>> interested in.
>>
>> Now you need to figure out what type you want the result of this
>> dereference to be. *What you have coded above defines p1 as a constant
>> pointer to person. *While I doubt you will change the value of p1, I'm
>> pretty sure it is more important to insure you never change the value
>> of the person. *What you want is a pointer to a constant person. *(See
>> 6.2.5-28 for an explanation) *I guess you could combine the two into a
>> constant pointer to a constant person but the declaration of the
>> compare function is really intended to insure you never change the
>> objects being compared.
>>
>> The cast and the dereference can be combined into a single statement,
>> either
>> * * *const person *p1 = *(const person**)value1;
>> or
>> * * const person * const p1 = *(const person*const*)value1;
>>
>> Furthermore, all the const qualifiers inside the casts are unnecessary
>> since you are allowed to add the qualification implicitly
>> * * const person *p1 = *(person**)value1;
>> * * const person * const p2 = *(person**)value2;
>>
>> --
>> Remove del for email- Hide quoted text -
>>
>> - Show quoted text -

>
>Yeah, I figured out my const mistake last night. I also made it one
>line, but thanks for the pointers. I'm rusty, let me tell ya.
>
>So, are you telling me I can't provide a qsort-like interface without
>reinventing the wheel?


You don't need to reinvent a qsort. It is already sufficiently
general. You only need to define the appropriate compare function.

>
>In general, would you say that data structures like my class are
>avoided in C?


I have no idea. C doesn't have classes. You never showed us what the
type of person is.

snip a bunch of stuff I don't understand

>We are currently analyzing possible approaches to take when writing
>new features and reworking old ones. We are hoping to find an easily
>repeatable process. Without a data structure, we have to do all of the
>processing while looping through the SQL results. You can't even
>determine how many results there were without running once through. We
>can't use plain-Jane arrays because we don't necessarily have an upper
>limit. We want to isolate any dynamic array allocation logic to a
>single set of code.


Seems reasonable to me

>
>Well, just thought I would share. If we really can't provide a qsort
>interface, I suppose we'll just copy our libraries and tweak it.


Why do you think you can't provide the appropriate compare function?
What does it have to do with dynamic arrays?

--
Remove del for email
 
Reply With Quote
 
Barry Schwarz
Guest
Posts: n/a
 
      02-20-2010
On Fri, 19 Feb 2010 15:43:11 -0800 (PST), Jehu Galeahsa
<(E-Mail Removed)> wrote:

>On Feb 19, 4:21*am, pete <(E-Mail Removed)> wrote:
>> (E-Mail Removed) wrote:
>> > Hello:

>>
>> > I am playing around with a data structure in C. It is a dynamically
>> > growing array of pointers. So, really, it is just a void** with a
>> > count and capacity.

>>
>> Why aren't you using a (person**) instead of a (void**)?

>
>We want to reuse the same code for all pointer types. A little casting
>here and there isn't a big deal.


If any call to qsort is for something other than an array of pointers
to person, you can't use the same code.

>
>>
>> > I want to provide a sorting algorithm that takes a comparison function
>> > with the signature qsort expects.

>>
>> > However, qsort is sending a void** instead of a void*,

>>
>> I suspect that it isn't.

>
>The signature is a const void *. But, that (const void *) is really a
>const pointer to another (void *). That (void *) is really a (person
>*). Since qsort sends a void * pointing to the element being sorted, I
>am getting a void **, effectively. At least that's as far as I want to
>wrap my mind around it.


Then you are doomed to perpetual confusion. qsort always sends a
pointer to an array element with type void*. You then need to cast
this pointer to the actual type of the array element. If the array
element is a pointer to "the real something" to be sorted, then you
dereference to get the correct pointer before doing the actual
compares.


--
Remove del for email
 
Reply With Quote
 
Alan Curry
Guest
Posts: n/a
 
      02-20-2010
In article <(E-Mail Removed)>,
Jehu Galeahsa <(E-Mail Removed)> wrote:
|>
|> >I want to avoid forcing clients of my class to do this double
|> >dereference. However, I have no clue how to transform what qsort sends
|> >to the comparison. I was thinking about creating a function that would
|> >dereference the void**'s and then call the comparison the user passed
|> >in with the dereferenced void*'s. In C++, I would accomplish using a
|> >functor, but I don't know how to do this in C. I'd like to avoid
|> >writing my own quick sort.

I've had some trouble figuring out what you are asking for. But I think
I've got it now. Let me summarize:

You want to provide a sorting interface as part of an array library. The
array library implements arrays of pointers only. You want to present
the simplest possible interface for the comparison function, which is
not the qsort interface because the qsort comparison interface is more
general (it handles arrays of any kind of object, not just arrays of
pointers).

So there are at least 3 layers of code which you are trying to make as
independent as possible. Ideally, the top layer would be the only one to
know about the "person" type. The middle layer would only do memory
management for your arrays, and the low layer would be the standard C
library providing qsort.

Your call tree looks like this:

+-------------------+ +-------------------+
| Application-level | | comparison |
| code | | function |
+-------------------+ +-------------------+
| ^
==========|==========================|============ =======
v |
+-------------------+ |
| array library | |
+-------------------+ |
| |
===================|=================|============ =======
v |
+-------------------+
| qsort |
+-------------------+

See what's missing? On the way into qsort, your array library is doing
something. On the callback, it's being bypassed. What you want is to put
something in the middle layer on the right. The only way to accomplish
that with qsort is to have a comparison function inside your array
library, and pass that down to qsort instead of the application level's
comparison function. This middle-layer comparison function would then do
the (first level of) dereferencing, and call the real comparison
function.

The hard part is how the array library's sort function communicates the
real comparison function pointer to the array library's comparison
function. If qsort was properly designed, it would have a context
parameter (something passed into qsort, which gets passed back up to the
comparison function) for this purpose. But it doesn't, so you have to
use a static variable visible by both functions in the array library.

It's probably more trouble than it's worth. The alternative - which
should be looking pretty attractive by now - is to learn to live with
the extra dereference in the application-level comparison function.

--
Alan Curry
 
Reply With Quote
 
Jehu Galeahsa
Guest
Posts: n/a
 
      02-20-2010
On Feb 19, 8:01*pm, (E-Mail Removed) (Alan Curry) wrote:
> In article <(E-Mail Removed)..com>,
> Jehu Galeahsa *<(E-Mail Removed)> wrote:
> |>
> |> >I want to avoid forcing clients of my class to do this double
> |> >dereference. However, I have no clue how to transform what qsort sends
> |> >to the comparison. I was thinking about creating a function that would
> |> >dereference the void**'s and then call the comparison the user passed
> |> >in with the dereferenced void*'s. In C++, I would accomplish using a
> |> >functor, but I don't know how to do this in C. I'd like to avoid
> |> >writing my own quick sort.
>
> I've had some trouble figuring out what you are asking for. But I think
> I've got it now. Let me summarize:
>
> You want to provide a sorting interface as part of an array library. The
> array library implements arrays of pointers only. You want to present
> the simplest possible interface for the comparison function, which is
> not the qsort interface because the qsort comparison interface is more
> general (it handles arrays of any kind of object, not just arrays of
> pointers).
>
> So there are at least 3 layers of code which you are trying to make as
> independent as possible. Ideally, the top layer would be the only one to
> know about the "person" type. The middle layer would only do memory
> management for your arrays, and the low layer would be the standard C
> library providing qsort.
>
> Your call tree looks like this:
>
> +-------------------+ * * * * * * * +-------------------+
> | Application-level | * * * * * * * | * * comparison * *|
> | * * * code * * * *| * * * * * * * | * * *function * * |
> +-------------------+ * * * * * * * +-------------------+
> * * * * * | * * * * * * * * * * * * *^
> ==========|==========================|============ =======
> * * * * * v * * * * * * * * * * * * *|
> * * * * *+-------------------+ * * * |
> * * * * *| * array library * | * * * |
> * * * * *+-------------------+ * * * |
> * * * * * * * * * *| * * * * * * * * |
> ===================|=================|============ =======
> * * * * * * * * * *v * * * * * * * * |
> * * * * * * * * * +-------------------+
> * * * * * * * * * | * * * qsort * * * |
> * * * * * * * * * +-------------------+
>
> See what's missing? On the way into qsort, your array library is doing
> something. On the callback, it's being bypassed. What you want is to put
> something in the middle layer on the right. The only way to accomplish
> that with qsort is to have a comparison function inside your array
> library, and pass that down to qsort instead of the application level's
> comparison function. This middle-layer comparison function would then do
> the (first level of) dereferencing, and call the real comparison
> function.
>
> The hard part is how the array library's sort function communicates the
> real comparison function pointer to the array library's comparison
> function. If qsort was properly designed, it would have a context
> parameter (something passed into qsort, which gets passed back up to the
> comparison function) for this purpose. But it doesn't, so you have to
> use a static variable visible by both functions in the array library.
>
> It's probably more trouble than it's worth. The alternative - which
> should be looking pretty attractive by now - is to learn to live with
> the extra dereference in the application-level comparison function.
>
> --
> Alan Curry


You understood my dilemma perfectly. Thank you for taking the time.
Yes, double dereferences do seem attractive at this point. I'll just
have to be extra careful about how I explain its usage.
 
Reply With Quote
 
Jehu Galeahsa
Guest
Posts: n/a
 
      02-20-2010
On Feb 19, 6:35*pm, Barry Schwarz <(E-Mail Removed)> wrote:
> On Fri, 19 Feb 2010 15:25:30 -0800 (PST), Jehu Galeahsa
>
>
>
>
>
> <(E-Mail Removed)> wrote:
> >On Feb 18, 10:28 pm, Barry Schwarz <(E-Mail Removed)> wrote:
> >> On Thu, 18 Feb 2010 19:18:30 -0800 (PST), "(E-Mail Removed)"

>
> >> <(E-Mail Removed)> wrote:
> >> >Hello:

>
> >> >I am playing around with a data structure in C. It is a dynamically
> >> >growing array of pointers. So, really, it is just a void** with a
> >> >count and capacity.

>
> >> >I want to provide a sorting algorithm that takes a comparison function
> >> >with the signature qsort expects.

>
> >> >However, qsort is sending a void** instead of a void*, so all the
> >> >comparison functions need to be written like this:

>
> >> >int person_comparison(void const* value1, void const* value2)
> >> >{
> >> > person *const* t1 = (person *const*)value1;
> >> > person *const* t2 = (person *const*)value2;
> >> > person *const p1 = *t1;
> >> > person *const p2 = *t2;
> >> > /* compare the two people */
> >> >}

>
> >> >I want to avoid forcing clients of my class to do this double
> >> >dereference. However, I have no clue how to transform what qsort sends
> >> >to the comparison. I was thinking about creating a function that would
> >> >dereference the void**'s and then call the comparison the user passed
> >> >in with the dereferenced void*'s. In C++, I would accomplish using a
> >> >functor, but I don't know how to do this in C. I'd like to avoid
> >> >writing my own quick sort.

>
> >> qsort will always send the address of two array elements, each with
> >> type const void*. Since the elements of your array are in fact
> >> pointers, then each address your compare function receives is of
> >> necessity the address of a pointer to your object of interest,
> >> conveniently represented by the ** notation. You have no choice but
> >> to dereference this address to obtain the pointer you are really
> >> interested in.

>
> >> Now you need to figure out what type you want the result of this
> >> dereference to be. What you have coded above defines p1 as a constant
> >> pointer to person. While I doubt you will change the value of p1, I'm
> >> pretty sure it is more important to insure you never change the value
> >> of the person. What you want is a pointer to a constant person. (See
> >> 6.2.5-28 for an explanation) I guess you could combine the two into a
> >> constant pointer to a constant person but the declaration of the
> >> compare function is really intended to insure you never change the
> >> objects being compared.

>
> >> The cast and the dereference can be combined into a single statement,
> >> either
> >> const person *p1 = *(const person**)value1;
> >> or
> >> const person * const p1 = *(const person*const*)value1;

>
> >> Furthermore, all the const qualifiers inside the casts are unnecessary
> >> since you are allowed to add the qualification implicitly
> >> const person *p1 = *(person**)value1;
> >> const person * const p2 = *(person**)value2;

>
> >> --
> >> Remove del for email- Hide quoted text -

>
> >> - Show quoted text -

>
> >Yeah, I figured out my const mistake last night. I also made it one
> >line, but thanks for the pointers. I'm rusty, let me tell ya.

>
> >So, are you telling me I can't provide a qsort-like interface without
> >reinventing the wheel?

>
> You don't need to reinvent a qsort. *It is already sufficiently
> general. *You only need to define the appropriate compare function.
>
>
>
> >In general, would you say that data structures like my class are
> >avoided in C?

>
> I have no idea. *C doesn't have classes. *You never showed us what the
> type of person is.


By class, I meant the struct and the functions that worked on it.
Sorry, C++ and C# on the brain.

I sent an example that defines person. It is a typedef of struct
person_.

>
> snip a bunch of stuff I don't understand
>
> >We are currently analyzing possible approaches to take when writing
> >new features and reworking old ones. We are hoping to find an easily
> >repeatable process. Without a data structure, we have to do all of the
> >processing while looping through the SQL results. You can't even
> >determine how many results there were without running once through. We
> >can't use plain-Jane arrays because we don't necessarily have an upper
> >limit. We want to isolate any dynamic array allocation logic to a
> >single set of code.

>
> Seems reasonable to me
>
>
>
> >Well, just thought I would share. If we really can't provide a qsort
> >interface, I suppose we'll just copy our libraries and tweak it.

>
> Why do you think you can't provide the appropriate compare function?
> What does it have to do with dynamic arrays?
>
> --
> Remove del for email- Hide quoted text -
>
> - Show quoted text -

 
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
pointers, pointers, pointers... cerr C Programming 12 04-07-2011 11:17 PM
pointers and array of pointers Piotrek C Programming 8 04-06-2007 08:02 AM
Pointers, linked list, array of pointers Sean C++ 2 09-24-2006 01:35 PM
access object in array of pointers to dynamic array of class complex jccorreu@gmail.com C++ 2 05-20-2006 05:08 AM
Can a static array contain a dynamic array of pointers? Peter B. Steiger C Programming 8 04-26-2004 03:07 AM



Advertisments