qsort needs one more argument

Discussion in 'C Programming' started by jacob navia, Dec 31, 2009.

  1. jacob navia

    jacob navia Guest

    Within the context of the container library, sorting needs a callback
    with more than just the two elements to be compared. The standard
    qsort function has a callback that takes only two arguments.

    This wasn't a big problem since I just adapted the code of lcc-win's
    C library to receive one more argument and the problem was gone.

    I wonder now, if my problem could be maybe more widespread than I
    think. I named the new function: "qsortEx" with the prototype:

    void qsortEx(void *base,
    size_t num,
    size_t width,
    int(*cmp) (const void *elem1,
    const void *elem2,
    void *ExtraArgs),
    void *ExtraArgs);

    The ExtraArgs aren't "const" since precisely the callbacks could modify
    it during the sort.

    All this avoids global variables, that are the only solution here.

    Has anyone of you seen a function like this?
    Is there a C library that provides this?

    Thanks in advance.

    jacob
     
    jacob navia, Dec 31, 2009
    #1
    1. Advertising

  2. jacob navia

    Nick Guest

    jacob navia <> writes:

    > Within the context of the container library, sorting needs a callback
    > with more than just the two elements to be compared. The standard
    > qsort function has a callback that takes only two arguments.
    >
    > This wasn't a big problem since I just adapted the code of lcc-win's
    > C library to receive one more argument and the problem was gone.
    >
    > I wonder now, if my problem could be maybe more widespread than I
    > think. I named the new function: "qsortEx" with the prototype:
    >
    > void qsortEx(void *base,
    > size_t num,
    > size_t width,
    > int(*cmp) (const void *elem1,
    > const void *elem2,
    > void *ExtraArgs),
    > void *ExtraArgs);
    >
    > The ExtraArgs aren't "const" since precisely the callbacks could modify
    > it during the sort.
    >
    > All this avoids global variables, that are the only solution here.
    >
    > Has anyone of you seen a function like this?
    > Is there a C library that provides this?


    One popular library that does this is expat - xml parsing. It passes a
    void pointer ("data") all over the place for you to use in whatever way
    you want.

    I bit myself with this one a while ago, and now always include that
    extra pointer - it only adds a couple of lines to the code, and making
    it NULL is painless when you don't need it.
    --
    Online waterways route planner | http://canalplan.eu
    Plan trips, see photos, check facilities | http://canalplan.org.uk
     
    Nick, Dec 31, 2009
    #2
    1. Advertising

  3. jacob navia

    jacob navia Guest

    Richard Heathfield a écrit :
    > That's why, a long time ago, I added
    > side-channel pointers into my container library. I can't do anything
    > about qsort, bsearch or *alloc/free, though.


    How did you call your qsort routine? Did it have the same interface?
     
    jacob navia, Dec 31, 2009
    #3
  4. jacob navia

    Paul N Guest

    On 31 Dec, 14:48, Richard Heathfield <> wrote:
    > jacob navia wrote:


    > > How did you call your qsort routine? Did it have the same interface?


    > Well, obviously I don't call it qsort. The interface is basically the
    > same, except for an additional void * parameter at the end, which is
    > either a pointer to side channel data or a null pointer.


    English is a funny language. "How did you call your qsort routine?"
    and "What did you call your qsort routine?" have completely different
    meanings.
     
    Paul N, Dec 31, 2009
    #4
  5. jacob navia

    Seebs Guest

    On 2009-12-31, jacob navia <> wrote:
    > All this avoids global variables, that are the only solution here.


    Not quite, they aren't.

    > Has anyone of you seen a function like this?
    > Is there a C library that provides this?


    It's a fairly common idiom for callbacks. That said, you can do
    it without a global -- through the magic of file scope.

    /* begin mycmpEx.c */

    static void *aux;

    int mycmp(struct foo *a, struct foo *b) {
    /* manipulate aux, also compare a and b */
    }

    int mycmp_aux(void *v) {
    aux = v;
    }

    /* begin use of mycmp */

    mycmp_aux(callback_value);
    qsort(blah blah, mycmp);

    /* see? */

    Basically, you can take advantage of static file scope to introduce a
    variable which you can access from your comparator, but which is not
    visble to anything else. You don't have to worry about this preventing
    inlining, because I'm pretty sure no one is inlining qsort comparators,
    and you even reduce the number of arguments being passed around.

    Christmas was saved!

    -s
    p.s.: Which isn't to say I wouldn't have preferred qsort's cmp function
    to take an aux argument.
    --
    Copyright 2009, all wrongs reversed. Peter Seebach /
    http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
    http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
     
    Seebs, Dec 31, 2009
    #5
  6. jacob navia

    Nobody Guest

    On Thu, 31 Dec 2009 11:30:29 +0100, jacob navia wrote:

    > Within the context of the container library, sorting needs a callback
    > with more than just the two elements to be compared. The standard
    > qsort function has a callback that takes only two arguments.


    > I wonder now, if my problem could be maybe more widespread than I
    > think.


    > Has anyone of you seen a function like this?
    > Is there a C library that provides this?


    Both the GNU and BSD libc provide qsort_r():

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

    The first two hits for qsort_r on Google:

    BSD http://www.ipnom.com/FreeBSD-Man-Pages/qsort_r.3.html
    GNU http://www.digipedia.pl/man/doc/view/qsort_r.3.html
     
    Nobody, Dec 31, 2009
    #6
  7. jacob navia

    jacob navia Guest

    Seebs a écrit :
    > On 2009-12-31, jacob navia <> wrote:
    >> All this avoids global variables, that are the only solution here.

    >
    > Not quite, they aren't.
    >
    >> Has anyone of you seen a function like this?
    >> Is there a C library that provides this?

    >
    > It's a fairly common idiom for callbacks. That said, you can do
    > it without a global -- through the magic of file scope.
    >
    > /* begin mycmpEx.c */
    >
    > static void *aux;
    >
    > int mycmp(struct foo *a, struct foo *b) {
    > /* manipulate aux, also compare a and b */
    > }
    >
    > int mycmp_aux(void *v) {
    > aux = v;
    > }
    >
    > /* begin use of mycmp */
    >
    > mycmp_aux(callback_value);
    > qsort(blah blah, mycmp);
    >
    > /* see? */
    >
    > Basically, you can take advantage of static file scope to introduce a
    > variable which you can access from your comparator, but which is not
    > visble to anything else. You don't have to worry about this preventing
    > inlining, because I'm pretty sure no one is inlining qsort comparators,
    > and you even reduce the number of arguments being passed around.
    >
    > Christmas was saved!
    >
    > -s
    > p.s.: Which isn't to say I wouldn't have preferred qsort's cmp function
    > to take an aux argument.


    Thanks. The problem with your solution is that in a multithreading
    environment it would be a bit messy: you would have to protect the file
    scoped variable from other threads.

    The whole multithreading stuff is not done yet, but I have it in mind
    so that later it is fairly easy to implement.
     
    jacob navia, Dec 31, 2009
    #7
  8. jacob navia

    jacob navia Guest

    Nobody a écrit :
    > On Thu, 31 Dec 2009 11:30:29 +0100, jacob navia wrote:
    >
    >> Within the context of the container library, sorting needs a callback
    >> with more than just the two elements to be compared. The standard
    >> qsort function has a callback that takes only two arguments.

    >
    >> I wonder now, if my problem could be maybe more widespread than I
    >> think.

    >
    >> Has anyone of you seen a function like this?
    >> Is there a C library that provides this?

    >
    > Both the GNU and BSD libc provide qsort_r():
    >
    > qsort_r(void *base, size_t nmemb, size_t size, void *thunk,
    > int (*compar)(void *, const void *, const void *));
    >
    > The first two hits for qsort_r on Google:
    >
    > BSD http://www.ipnom.com/FreeBSD-Man-Pages/qsort_r.3.html
    > GNU http://www.digipedia.pl/man/doc/view/qsort_r.3.html
    >
    >


    Thanks.

    Once you know about qsort_r it is easy to find of course
    :)
     
    jacob navia, Dec 31, 2009
    #8
  9. jacob navia

    Seebs Guest

    On 2009-12-31, jacob navia <> wrote:
    > Thanks. The problem with your solution is that in a multithreading
    > environment it would be a bit messy: you would have to protect the file
    > scoped variable from other threads.


    True that.

    Your next option over, which is Clearly Very Bad, is to ensure that
    every object you're comparing has a pointer to the aux object. :)

    > The whole multithreading stuff is not done yet, but I have it in mind
    > so that later it is fairly easy to implement.


    Good thinking.

    -s
    --
    Copyright 2009, all wrongs reversed. Peter Seebach /
    http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
    http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
     
    Seebs, Dec 31, 2009
    #9
    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. Carlos
    Replies:
    6
    Views:
    373
    Carlos
    Feb 16, 2005
  2. cayblood
    Replies:
    4
    Views:
    2,573
    Ivan Vecerina
    Nov 3, 2005
  3. Merciadri Luca
    Replies:
    4
    Views:
    841
  4. Steven D'Aprano
    Replies:
    0
    Views:
    133
    Steven D'Aprano
    Dec 23, 2013
  5. Replies:
    3
    Views:
    107
    Gary Herron
    Dec 23, 2013
Loading...

Share This Page