Sorting a Dynamic Array of Pointers

Discussion in 'C Programming' started by jehugaleahsa@gmail.com, Feb 19, 2010.

  1. Guest

    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
     
    , Feb 19, 2010
    #1
    1. Advertising

  2. On Thu, 18 Feb 2010 19:18:30 -0800 (PST), ""
    <> 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
     
    Barry Schwarz, Feb 19, 2010
    #2
    1. Advertising

  3. On Feb 18, 10:28 pm, Barry Schwarz <> wrote:
    > On Thu, 18 Feb 2010 19:18:30 -0800 (PST), ""
    >
    >
    >
    >
    >
    > <> 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.
     
    Jehu Galeahsa, Feb 19, 2010
    #3
  4. On Feb 19, 4:21 am, pete <> wrote:
    > 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 -
     
    Jehu Galeahsa, Feb 19, 2010
    #4
  5. #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;
    }
     
    Jehu Galeahsa, Feb 19, 2010
    #5
  6. On Fri, 19 Feb 2010 15:25:30 -0800 (PST), Jehu Galeahsa
    <> wrote:

    >On Feb 18, 10:28 pm, Barry Schwarz <> wrote:
    >> On Thu, 18 Feb 2010 19:18:30 -0800 (PST), ""
    >>
    >>
    >>
    >>
    >>
    >> <> 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
     
    Barry Schwarz, Feb 20, 2010
    #6
  7. On Fri, 19 Feb 2010 15:43:11 -0800 (PST), Jehu Galeahsa
    <> wrote:

    >On Feb 19, 4:21 am, pete <> wrote:
    >> 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
     
    Barry Schwarz, Feb 20, 2010
    #7
  8. Alan Curry Guest

    In article <>,
    Jehu Galeahsa <> 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
     
    Alan Curry, Feb 20, 2010
    #8
  9. On Feb 19, 8:01 pm, (Alan Curry) wrote:
    > In article <..com>,
    > Jehu Galeahsa  <> 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.
     
    Jehu Galeahsa, Feb 20, 2010
    #9
  10. On Feb 19, 6:35 pm, Barry Schwarz <> wrote:
    > On Fri, 19 Feb 2010 15:25:30 -0800 (PST), Jehu Galeahsa
    >
    >
    >
    >
    >
    > <> wrote:
    > >On Feb 18, 10:28 pm, Barry Schwarz <> wrote:
    > >> On Thu, 18 Feb 2010 19:18:30 -0800 (PST), ""

    >
    > >> <> 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 -
     
    Jehu Galeahsa, Feb 20, 2010
    #10
  11. Alan Curry Guest

    In article <>,
    Jehu Galeahsa <> wrote:
    |
    |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.

    You can provide a macro for turning the comparison function's parameters
    into the pointers you want the application layer to see. Documentation can
    say that the only allowable operation on the comparison function's parameters
    is BlessArrayElement(), defined as

    #define BlessArrayElement(v) (*(void *const *)v)

    So it would be used like this:

    int cmpfunc(const void *v1, const void *v2)
    {
    struct person *p1 = BlessArrayElement(v1);
    struct person *p2 = BlessArrayElement(v2);
    ...
    }

    which gives you the freedom to try other approaches later, without changing
    the upper-level interface, by just changing BlessArrayElement to a noop once
    you've fixed the lower layers.

    --
    Alan Curry
     
    Alan Curry, Feb 20, 2010
    #11
  12. #ifndef ARRAY_LIST_H
    #define ARRAY_LIST_H

    #include <stdlib.h>

    /*
    Represents a dynamically-growing, random-access collection.
    */
    typedef struct array_list_
    {
    int count;
    int capacity;
    void ** elements;
    } array_list;

    /*
    Initializes an array_list.
    */
    void array_list_init(array_list * lst, size_t type_size, int reserve)
    {
    lst->count = 0;
    lst->capacity = reserve;
    lst->elements = (void **)calloc(reserve, type_size);
    }

    /*
    Destroys an array_list.
    */
    void array_list_destroy(array_list * lst)
    {
    int index;
    for (index = 0; index != lst->count; ++index)
    {
    free(lst->elements[index]);
    }
    free(lst->elements);
    }

    /*
    Removes all of the items from the array_list.
    */
    void array_list_clear(array_list * lst)
    {
    int index;
    for (index = 0; index != lst->count; ++index)
    {
    free(lst->elements[index]);
    }
    lst->count = 0;
    }

    /*
    Gets the number of items in the list.
    */
    int array_list_get_count(array_list * lst)
    {
    return lst->count;
    }

    /*
    Gets the maximum number of items that can be added before more memory
    is allocated.
    */
    int array_list_get_capacity(array_list * lst)
    {
    return lst->capacity;
    }

    /*
    Gets the item at the given index.
    */
    void * array_list_get_item(array_list * lst, int index)
    {
    return lst->elements[index];
    }

    /*
    Replaces the item at the given index with the given value. The
    replaced
    value is returned.
    */
    void array_list_set_item(array_list * lst, int index, void * value)
    {
    void * replaced = lst->elements[index];
    lst->elements[index] = value;
    free(replaced);
    }

    /*
    Inserts the given value at the given index.
    */
    void array_list_insert(array_list * lst, int index, void * value)
    {
    int position;
    if (lst->count == lst->capacity)
    {
    void ** temp;
    lst->capacity = lst->capacity == 0 ? 4 : lst->capacity * 2;
    temp = (void **)calloc(lst->capacity, sizeof(void *));
    for (position = 0; position != index; ++position)
    {
    temp[position] = lst->elements[position];
    }
    free(lst->elements);
    lst->elements = temp;
    }
    for (position = lst->count; position != index; --position)
    {
    lst->elements[position] = lst->elements[position - 1];
    }
    lst->elements[index] = value;
    ++lst->count;
    }

    /*
    Adds the given value to the end of the array_list.
    */
    void array_list_add(array_list * lst, void * value)
    {
    if (lst->count == lst->capacity)
    {
    lst->capacity = lst->capacity == 0 ? 4 : lst->capacity * 2;
    lst->elements = (void **)realloc(lst->elements, lst->capacity *
    sizeof(void *));
    }
    lst->elements[lst->count] = value;
    ++lst->count;
    }

    /*
    Removes the item at the given index, but does free it. The
    item is returned.
    */
    void * array_list_detach(array_list * lst, int index)
    {
    void * detached = lst->elements[index];
    for (; index < lst->count - 1; ++index)
    {
    lst->elements[index] = lst->elements[index + 1];
    }
    --lst->count;
    return detached;
    }

    /*
    Removes the item at the given index.
    */
    void array_list_remove_at(array_list * lst, int index)
    {
    void * removed = array_list_detach(lst, index);
    free(removed);
    }

    /*
    Removes the last item in the array_list.
    */
    void array_list_remove_last(array_list * lst)
    {
    --lst->count;
    free(lst->elements[lst->count]);
    }

    /*
    Shrinks the capacity of the array_list to the count.
    */
    void array_list_trim(array_list * lst)
    {
    lst->capacity = lst->count;
    lst->elements = (void **)realloc(lst->elements, lst->count *
    sizeof(void *));
    }

    typedef void (*array_list_action)(void * item);

    /*
    Applies the given operation to every item in the list.
    */
    void array_list_for_each(array_list * lst, array_list_action action)
    {
    int index;
    for (index = 0; index != lst->count; ++index)
    {
    action(lst->elements[index]);
    }
    }

    typedef int (*array_list_predicate)(void const* value);

    /*
    Finds the first occurrence of a value such that the comparison returns
    non-zero.
    If the value is not found, -1 is returned.
    */
    int array_list_find(array_list const* lst, array_list_predicate
    predicate)
    {
    int index;
    for (index = 0; index != lst->count; ++index)
    {
    if (predicate(lst->elements[index]))
    {
    return index;
    }
    }
    return -1;
    }

    /*
    Finds the last occurrence of a value such that the comparison returns
    non-zero.
    If the value is not found, -1 is returned.
    */
    int array_list_find_last(array_list * lst, array_list_predicate
    predicate)
    {
    int index;
    for (index = lst->count - 1; index >= 0; --index)
    {
    if (predicate(lst->elements[index]))
    {
    return index;
    }
    }
    return -1;
    }

    #endif // ARRAY_LIST_H
     
    Jehu Galeahsa, Feb 21, 2010
    #12
  13. On Sun, 21 Feb 2010 10:25:16 -0800 (PST), Jehu Galeahsa
    <> wrote:

    >#ifndef ARRAY_LIST_H
    >#define ARRAY_LIST_H
    >
    >#include <stdlib.h>
    >
    >/*
    >Represents a dynamically-growing, random-access collection.
    >*/
    >typedef struct array_list_
    >{
    > int count;
    > int capacity;
    > void ** elements;
    >} array_list;
    >
    >/*
    >Initializes an array_list.
    >*/
    >void array_list_init(array_list * lst, size_t type_size, int reserve)
    >{
    > lst->count = 0;
    > lst->capacity = reserve;
    > lst->elements = (void **)calloc(reserve, type_size);


    The cast is unnecessary in C. Using calloc to initialize an array of
    pointers to all-bits-zero is perfectly legal but not necessarily
    portable. There is no guarantee that the bit representation of null
    pointer has this bit representation. When asking for help, it pays to
    let as many people as possible do so. In this case, using malloc and
    a loop to set each array element to NULL is cheap insurance.

    >}
    >
    >/*
    >Destroys an array_list.
    >*/
    >void array_list_destroy(array_list * lst)
    >{
    > int index;
    > for (index = 0; index != lst->count; ++index)
    > {
    > free(lst->elements[index]);
    > }
    > free(lst->elements);


    Don't you want to set capacity to zero here?

    >}
    >
    >/*
    >Removes all of the items from the array_list.
    >*/
    >void array_list_clear(array_list * lst)
    >{
    > int index;
    > for (index = 0; index != lst->count; ++index)
    > {
    > free(lst->elements[index]);


    Since you don't free elements itself in this case, it would make sense
    to also set elements[index] to NULL. At the very least, it would
    insure that your _destroy function above would not attempt to evaluate
    an indeterminate value.

    > }
    > lst->count = 0;
    >}
    >
    >/*
    >Gets the number of items in the list.
    >*/
    >int array_list_get_count(array_list * lst)
    >{
    > return lst->count;
    >}
    >
    >/*
    >Gets the maximum number of items that can be added before more memory
    >is allocated.


    Memory has already been allocated. When you exceed capacity, you need
    to allocate (realloc) more. Misleading comments can really hurt when
    you go back to the program after a long hiatus.

    >*/
    >int array_list_get_capacity(array_list * lst)
    >{
    > return lst->capacity;
    >}
    >
    >/*
    >Gets the item at the given index.
    >*/
    >void * array_list_get_item(array_list * lst, int index)
    >{
    > return lst->elements[index];
    >}
    >
    >/*
    >Replaces the item at the given index with the given value. The
    >replaced
    >value is returned.


    The function never returns anything. Did you mean the previously
    allocated memory is given back to the system?

    >*/
    >void array_list_set_item(array_list * lst, int index, void * value)
    >{
    > void * replaced = lst->elements[index];
    > lst->elements[index] = value;
    > free(replaced);
    >}
    >
    >/*
    >Inserts the given value at the given index.
    >*/
    >void array_list_insert(array_list * lst, int index, void * value)
    >{
    > int position;
    > if (lst->count == lst->capacity)
    > {
    > void ** temp;
    > lst->capacity = lst->capacity == 0 ? 4 : lst->capacity * 2;


    Don't you need to check capacity against count before deciding an
    expansion is necessary. Does your code ever set capacity to 0?

    > temp = (void **)calloc(lst->capacity, sizeof(void *));


    Is there some reason you are not willing to use realloc and let it do
    all the hard work for you?

    > for (position = 0; position != index; ++position)
    > {
    > temp[position] = lst->elements[position];
    > }
    > free(lst->elements);
    > lst->elements = temp;
    > }
    > for (position = lst->count; position != index; --position)


    What happens if index is greater than count (insert at end of list)?
    You may want to use position>index here.

    > {
    > lst->elements[position] = lst->elements[position - 1];
    > }
    > lst->elements[index] = value;
    > ++lst->count;
    >}
    >
    >/*
    >Adds the given value to the end of the array_list.
    >*/
    >void array_list_add(array_list * lst, void * value)
    >{
    > if (lst->count == lst->capacity)
    > {
    > lst->capacity = lst->capacity == 0 ? 4 : lst->capacity * 2;
    > lst->elements = (void **)realloc(lst->elements, lst->capacity *
    >sizeof(void *));
    > }
    > lst->elements[lst->count] = value;
    > ++lst->count;
    >}
    >
    >/*
    >Removes the item at the given index, but does free it. The


    Did you intend to say "does not"?

    >item is returned.
    >*/
    >void * array_list_detach(array_list * lst, int index)
    >{
    > void * detached = lst->elements[index];
    > for (; index < lst->count - 1; ++index)
    > {
    > lst->elements[index] = lst->elements[index + 1];
    > }
    > --lst->count;
    > return detached;
    >}
    >
    >/*
    >Removes the item at the given index.
    >*/
    >void array_list_remove_at(array_list * lst, int index)
    >{
    > void * removed = array_list_detach(lst, index);
    > free(removed);
    >}
    >
    >/*
    >Removes the last item in the array_list.


    Just my opinion but forcing the user of these functions to distinguish
    between first, last, and intermediate elements is wrong. The user
    should issue a generic remove request with the desired index and the
    service functions should make any distinctions necessary.

    >*/
    >void array_list_remove_last(array_list * lst)
    >{
    > --lst->count;
    > free(lst->elements[lst->count]);
    >}
    >
    >/*
    >Shrinks the capacity of the array_list to the count.
    >*/
    >void array_list_trim(array_list * lst)
    >{
    > lst->capacity = lst->count;
    > lst->elements = (void **)realloc(lst->elements, lst->count *
    >sizeof(void *));


    Are you always guaranteed that only the first count elements contain
    "active" pointers? If not, this causes memory leaks.

    >}
    >
    >typedef void (*array_list_action)(void * item);
    >
    >/*
    >Applies the given operation to every item in the list.
    >*/
    >void array_list_for_each(array_list * lst, array_list_action action)
    >{
    > int index;
    > for (index = 0; index != lst->count; ++index)
    > {
    > action(lst->elements[index]);
    > }
    >}
    >
    >typedef int (*array_list_predicate)(void const* value);
    >
    >/*
    >Finds the first occurrence of a value such that the comparison returns
    >non-zero.
    >If the value is not found, -1 is returned.
    >*/
    >int array_list_find(array_list const* lst, array_list_predicate
    >predicate)
    >{
    > int index;
    > for (index = 0; index != lst->count; ++index)
    > {
    > if (predicate(lst->elements[index]))
    > {
    > return index;
    > }
    > }
    > return -1;
    >}
    >
    >/*
    >Finds the last occurrence of a value such that the comparison returns
    >non-zero.
    >If the value is not found, -1 is returned.
    >*/
    >int array_list_find_last(array_list * lst, array_list_predicate
    >predicate)
    >{
    > int index;
    > for (index = lst->count - 1; index >= 0; --index)
    > {
    > if (predicate(lst->elements[index]))
    > {
    > return index;
    > }
    > }
    > return -1;
    >}
    >
    >#endif // ARRAY_LIST_H


    Is there some reason you intend to #include this source in multiple
    translation units rather than compile it once and let the linker
    include the various functions as appropriate?

    --
    Remove del for email
     
    Barry Schwarz, Feb 21, 2010
    #13
  14. On Feb 21, 12:51 pm, Barry Schwarz <> wrote:
    > On Sun, 21 Feb 2010 10:25:16 -0800 (PST), Jehu Galeahsa
    >
    >
    >
    >
    >
    > <> wrote:
    > >#ifndef ARRAY_LIST_H
    > >#define ARRAY_LIST_H

    >
    > >#include <stdlib.h>

    >
    > >/*
    > >Represents a dynamically-growing, random-access collection.
    > >*/
    > >typedef struct array_list_
    > >{
    > >    int count;
    > >    int capacity;
    > >    void ** elements;
    > >} array_list;

    >
    > >/*
    > >Initializes an array_list.
    > >*/
    > >void array_list_init(array_list * lst, size_t type_size, int reserve)
    > >{
    > >    lst->count = 0;
    > >    lst->capacity = reserve;
    > >    lst->elements = (void **)calloc(reserve, type_size);

    >
    > The cast is unnecessary in C.  Using calloc to initialize an array of
    > pointers to all-bits-zero is perfectly legal but not necessarily
    > portable.  There is no guarantee that the bit representation of null
    > pointer has this bit representation.  When asking for help, it pays to
    > let as many people as possible do so.  In this case, using malloc and
    > a loop to set each array element to NULL is cheap insurance.


    I could see where malloc would be more efficient. I am not actually
    concerned what the pointer value is if it is greater than count.
    Bogus, random data is fine with me.

    >
    > >}

    >
    > >/*
    > >Destroys an array_list.
    > >*/
    > >void array_list_destroy(array_list * lst)
    > >{
    > >    int index;
    > >    for (index = 0; index != lst->count; ++index)
    > >    {
    > >            free(lst->elements[index]);
    > >    }
    > >    free(lst->elements);

    >
    > Don't you want to set capacity to zero here?


    No. I do want users using my array list after it is destroyed. If they
    want to reuse the same array_list, they MUST call init after destroy.

    >
    > >}

    >
    > >/*
    > >Removes all of the items from the array_list.
    > >*/
    > >void array_list_clear(array_list * lst)
    > >{
    > >    int index;
    > >    for (index = 0; index != lst->count; ++index)
    > >    {
    > >            free(lst->elements[index]);

    >
    > Since you don't free elements itself in this case, it would make sense
    > to also set elements[index] to NULL.  At the very least, it would
    > insure that your _destroy function above would not attempt to evaluate
    > an indeterminate value.


    The count field is responsible for managing what is destroyed. Since
    count is set back to zero, destroy will not try to double free.

    >
    > >    }
    > >    lst->count = 0;
    > >}

    >
    > >/*
    > >Gets the number of items in the list.
    > >*/
    > >int array_list_get_count(array_list * lst)
    > >{
    > >    return lst->count;
    > >}

    >
    > >/*
    > >Gets the maximum number of items that can be added before more memory
    > >is allocated.

    >
    > Memory has already been allocated.  When you exceed capacity, you need
    > to allocate (realloc) more.  Misleading comments can really hurt when
    > you go back to the program after a long hiatus.


    I don't understand your problem with my comment above.

    >
    >
    >
    >
    >
    > >*/
    > >int array_list_get_capacity(array_list * lst)
    > >{
    > >    return lst->capacity;
    > >}

    >
    > >/*
    > >Gets the item at the given index.
    > >*/
    > >void * array_list_get_item(array_list * lst, int index)
    > >{
    > >    return lst->elements[index];
    > >}

    >
    > >/*
    > >Replaces the item at the given index with the given value. The
    > >replaced
    > >value is returned.

    >
    > The function never returns anything.  Did you mean the previously
    > allocated memory is given back to the system?


    That is correct. I need to fix my comment.

    >
    >
    >
    >
    >
    > >*/
    > >void array_list_set_item(array_list * lst, int index, void * value)
    > >{
    > >    void * replaced = lst->elements[index];
    > >    lst->elements[index] = value;
    > >    free(replaced);
    > >}

    >
    > >/*
    > >Inserts the given value at the given index.
    > >*/
    > >void array_list_insert(array_list * lst, int index, void * value)
    > >{
    > >    int position;
    > >    if (lst->count == lst->capacity)
    > >    {
    > >            void ** temp;
    > >            lst->capacity = lst->capacity == 0 ? 4 : lst->capacity * 2;

    >
    > Don't you need to check capacity against count before deciding an
    > expansion is necessary.  Does your code ever set capacity to 0?


    I check if count == capacity. When calling init, the capacity can be
    set to 0.

    >
    > >            temp = (void **)calloc(lst->capacity, sizeof(void *));

    >
    > Is there some reason you are not willing to use realloc and let it do
    > all the hard work for you?


    The reason is that realloc will copy all my values to the new memory.
    I can avoid unnecessary copying if I use malloc. If I insert in the
    middle of a huge array_list, this might make a difference in
    performance. Of course, I am using calloc, so my point is moot. I will
    change to malloc; thanks for pointing that out.

    >
    > >            for (position = 0; position != index; ++position)
    > >            {
    > >                    temp[position] = lst->elements[position];
    > >            }
    > >            free(lst->elements);
    > >            lst->elements = temp;
    > >    }
    > >    for (position = lst->count; position != index; --position)

    >
    > What happens if index is greater than count (insert at end of list)?
    > You may want to use position>index here.


    I am ignoring argument checking for now. You might have noticed that I
    am doing no error checking either.

    >
    >
    >
    >
    >
    > >    {
    > >            lst->elements[position] = lst->elements[position - 1];
    > >    }
    > >    lst->elements[index] = value;
    > >    ++lst->count;
    > >}

    >
    > >/*
    > >Adds the given value to the end of the array_list.
    > >*/
    > >void array_list_add(array_list * lst, void * value)
    > >{
    > >    if (lst->count == lst->capacity)
    > >    {
    > >            lst->capacity = lst->capacity == 0 ? 4 : lst->capacity * 2;
    > >            lst->elements = (void **)realloc(lst->elements, lst->capacity *
    > >sizeof(void *));
    > >    }
    > >    lst->elements[lst->count] = value;
    > >    ++lst->count;
    > >}

    >
    > >/*
    > >Removes the item at the given index, but does free it. The

    >
    > Did you intend to say "does not"?


    Yup. I need to fix my comments.

    >
    >
    >
    >
    >
    > >item is returned.
    > >*/
    > >void * array_list_detach(array_list * lst, int index)
    > >{
    > >    void * detached = lst->elements[index];
    > >    for (; index < lst->count - 1; ++index)
    > >    {
    > >            lst->elements[index] = lst->elements[index + 1];
    > >    }
    > >    --lst->count;
    > >    return detached;
    > >}

    >
    > >/*
    > >Removes the item at the given index.
    > >*/
    > >void array_list_remove_at(array_list * lst, int index)
    > >{
    > >    void * removed = array_list_detach(lst, index);
    > >    free(removed);
    > >}

    >
    > >/*
    > >Removes the last item in the array_list.

    >
    > Just my opinion but forcing the user of these functions to distinguish
    > between first, last, and intermediate elements is wrong.  The user
    > should issue a generic remove request with the desired index and the
    > service functions should make any distinctions necessary.


    Probably. I know I would expect the same performance if I called
    remove_last and remove_at(count).

    >
    > >*/
    > >void array_list_remove_last(array_list * lst)
    > >{
    > >    --lst->count;
    > >    free(lst->elements[lst->count]);
    > >}

    >
    > >/*
    > >Shrinks the capacity of the array_list to the count.
    > >*/
    > >void array_list_trim(array_list * lst)
    > >{
    > >    lst->capacity = lst->count;
    > >    lst->elements = (void **)realloc(lst->elements, lst->count *
    > >sizeof(void *));

    >
    > Are you always guaranteed that only the first count elements contain
    > "active" pointers?  If not, this causes memory leaks.


    I am saying that is the case. If someone directly accesses my
    elements, they are corrupting my data structure. If they only use my
    functions to manipulate the data structure, they are a-okay.

    >
    >
    >
    >
    >
    > >}

    >
    > >typedef void (*array_list_action)(void * item);

    >
    > >/*
    > >Applies the given operation to every item in the list.
    > >*/
    > >void array_list_for_each(array_list * lst, array_list_action action)
    > >{
    > >    int index;
    > >    for (index = 0; index != lst->count; ++index)
    > >    {
    > >            action(lst->elements[index]);
    > >    }
    > >}

    >
    > >typedef int (*array_list_predicate)(void const* value);

    >
    > >/*
    > >Finds the first occurrence of a value such that the comparison returns
    > >non-zero.
    > >If the value is not found, -1 is returned.
    > >*/
    > >int array_list_find(array_list const* lst, array_list_predicate
    > >predicate)
    > >{
    > >    int index;
    > >    for (index = 0; index != lst->count; ++index)
    > >    {
    > >            if (predicate(lst->elements[index]))
    > >            {
    > >                    return index;
    > >            }
    > >    }
    > >    return -1;
    > >}

    >
    > >/*
    > >Finds the last occurrence of a value such that the comparison returns
    > >non-zero.
    > >If the value is not found, -1 is returned.
    > >*/
    > >int array_list_find_last(array_list * lst, array_list_predicate
    > >predicate)
    > >{
    > >    int index;
    > >    for (index = lst->count - 1; index >= 0; --index)
    > >    {
    > >            if (predicate(lst->elements[index]))
    > >            {
    > >                    return index;
    > >            }
    > >    }
    > >    return -1;
    > >}

    >
    > >#endif // ARRAY_LIST_H

    >
    > Is there some reason you intend to #include this source in multiple
    > translation units rather than compile it once and let the linker
    > include the various functions as appropriate?


    You mean, why don't I have a .c file? Because I am just experimenting
    for now.

    >
    > --
    > Remove del for email- Hide quoted text -
    >
    > - Show quoted text -- Hide quoted text -
    >
    > - Show quoted text -- Hide quoted text -
    >
    > - Show quoted text -- Hide quoted text -
    >
    > - Show quoted text -- Hide quoted text -
    >
    > - Show quoted text -- Hide quoted text -
    >
    > - Show quoted text -
     
    Jehu Galeahsa, Feb 21, 2010
    #14
  15. "" <> wrote:
    > ..., 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 generally try to avoid the casts...

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

    #define countof(x) ((size_t) (sizeof (x)/sizeof *(x)))
    #define pp_cmp(a, b) (((b) < (a)) - ((a) < (b)))

    typedef struct person
    {
    const char *name;
    int beauty;
    } person;

    int by_age(const void *lv, const void *rv)
    {
    const void * const *lpv = lv;
    const void * const *rpv = rv;
    const person *lp = *lpv;
    const person *rp = *rpv;
    return strcmp(lp->name, rp->name);
    }

    int by_beauty(const void *lv, const void *rv)
    {
    const void * const *lpv = lv;
    const void * const *rpv = rv;
    const person *lp = *lpv;
    const person *rp = *rpv;
    return pp_cmp(lp->beauty, rp->beauty);
    }

    person peter = { "Peter", 38 };
    person bob = { "Bob", 42 };
    person alice = { "Alice", 24 };

    int main(void)
    {
    size_t i;
    void *a[] = { &peter, &bob, &alice };

    puts("By name (lexical):");
    qsort(a, countof(a), sizeof *a, by_age);
    for (i = 0; i < countof(a); i++)
    {
    const person *p = a;
    printf("%s: %d\n", p->name, p->beauty);
    }

    puts("\nBy beauty (relative):");
    qsort(a, countof(a), sizeof *a, by_beauty);
    for (i = 0; i < countof(a); i++)
    {
    const person *p = a;
    printf("%s: %d\n", p->name, p->beauty);
    }

    return 0;
    }

    --
    Peter
     
    Peter Nilsson, Feb 22, 2010
    #15
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Peter B. Steiger

    Can a static array contain a dynamic array of pointers?

    Peter B. Steiger, Apr 19, 2004, in forum: C Programming
    Replies:
    8
    Views:
    2,120
    Dave Thompson
    Apr 26, 2004
  2. Replies:
    2
    Views:
    579
    Victor Bazarov
    May 20, 2006
  3. Sean
    Replies:
    2
    Views:
    653
    loufoque
    Sep 24, 2006
  4. Piotrek

    pointers and array of pointers

    Piotrek, Apr 2, 2007, in forum: C Programming
    Replies:
    8
    Views:
    340
    Chris Torek
    Apr 6, 2007
  5. cerr

    pointers, pointers, pointers...

    cerr, Apr 7, 2011, in forum: C Programming
    Replies:
    12
    Views:
    710
Loading...

Share This Page