Design decision

Discussion in 'C Programming' started by jacob navia, Jan 21, 2011.

  1. jacob navia

    jacob navia Guest

    I am introducing a new container into the container library: Treemap.

    This one features a scapegoat tree, and NEEDS a comparison function to
    be able to build the tree.

    Normally, comparison functions takes two arguments, for instance the
    argument to the qsort() function.

    Within the context of the container library, I propose to use
    comparison functions that can take a third argument, where you
    can pass a context to the function without having to use global
    variables.

    Now, maintaining this third argument has been quite a pain, since
    it implies (ofcourse) that in all my calls to qsort() I would
    need a special qsort, augmented with extra arguments.

    Now in my tree function, I have:

    int Add(TreeMap *tree, void *data, void *ExtraArgs);

    where "ExtraArgs" are the extra arguments to pass to the
    comparison function.

    My problem is that in all sequential containers I have

    int Add(Container *someContainer, void *data);

    and it would be real NICE if I could keep that function with
    the same syntax.

    To solve this problem, I added a void * in the TreeMap
    structure to contain the extra arguments for the comparison function
    in case you need them. So, you would do:

    TreeMap *tree;
    void *Context;

    // initialize tree and Context

    SetComparisonContext(tree,Context);
    Add(tree,data);
    SetComparisonContext(tree,NULL);

    So, you would pass the extra arguments in the tree itself.

    Problem is, I am not sure of the implications of this stuff in
    a multi-threaded environment. I would have to lock the tree to
    modifications between the call to the first SetComparisonContext
    and the second. Since the tree must be locked anyway for the
    add this doesn't look very catastrophic anyway, but now the
    "Add" function must NOT try to lock again the tree since it is
    already locked. This means that the locking primitives must
    notice if the tree is locked by the SAME thread and ignore the
    lock.

    All this quickly goes beyond the feeble capacities of my
    small brain :)

    Hence this message and a question:

    Better modify the syntax of the functions than getting into the
    multi-threading hair splitting?

    What do you think?

    Thanks in advance for any help.

    jacob
    jacob navia, Jan 21, 2011
    #1
    1. Advertising

  2. jacob navia <> writes:

    > I am introducing a new container into the container library: Treemap.
    >
    > This one features a scapegoat tree, and NEEDS a comparison function to
    > be able to build the tree.
    >
    > Normally, comparison functions takes two arguments, for instance the
    > argument to the qsort() function.
    >
    > Within the context of the container library, I propose to use
    > comparison functions that can take a third argument, where you
    > can pass a context to the function without having to use global
    > variables.
    >
    > Now, maintaining this third argument has been quite a pain, since
    > it implies (ofcourse) that in all my calls to qsort() I would
    > need a special qsort, augmented with extra arguments.
    >
    > Now in my tree function, I have:
    >
    > int Add(TreeMap *tree, void *data, void *ExtraArgs);
    >
    > where "ExtraArgs" are the extra arguments to pass to the
    > comparison function.
    >
    > My problem is that in all sequential containers I have
    >
    > int Add(Container *someContainer, void *data);
    >
    > and it would be real NICE if I could keep that function with
    > the same syntax.
    >
    > To solve this problem, I added a void * in the TreeMap
    > structure to contain the extra arguments for the comparison function
    > in case you need them. So, you would do:
    >
    > TreeMap *tree;
    > void *Context;
    >
    > // initialize tree and Context
    >
    > SetComparisonContext(tree,Context);
    > Add(tree,data);
    > SetComparisonContext(tree,NULL);
    >
    > So, you would pass the extra arguments in the tree itself.
    >
    > Problem is, I am not sure of the implications of this stuff in
    > a multi-threaded environment. I would have to lock the tree to
    > modifications between the call to the first SetComparisonContext
    > and the second. Since the tree must be locked anyway for the
    > add this doesn't look very catastrophic anyway, but now the
    > "Add" function must NOT try to lock again the tree since it is
    > already locked. This means that the locking primitives must
    > notice if the tree is locked by the SAME thread and ignore the
    > lock.


    But then you have all sorts of problems. If the main thread calls

    SetComparisonContext(tree,Context);

    the tree will be locked and no other threads could do anything with it.

    > All this quickly goes beyond the feeble capacities of my
    > small brain :)
    >
    > Hence this message and a question:
    >
    > Better modify the syntax of the functions than getting into the
    > multi-threading hair splitting?
    >
    > What do you think?


    I'd change Add. You could make the prototype

    int Add(Container *someContainer, void *data, ...);

    so as to leave existing code unchanged.

    --
    Ben.
    Ben Bacarisse, Jan 21, 2011
    #2
    1. Advertising

  3. jacob navia

    Ian Pilcher Guest

    On 01/21/2011 11:09 AM, jacob navia wrote:
    > Within the context of the container library, I propose to use
    > comparison functions that can take a third argument, where you
    > can pass a context to the function without having to use global
    > variables.


    What is the use case for passing additional context to the comparison
    function?

    If the additional context is going to affect the result of the
    comparison, then you have to ensure that all uses of the comparison
    function by a given container always have the same additional context,
    in which case it should be set when the container is created and not
    changed.

    If you don't do this, your comparison function isn't going to be stable,
    and it's hard to see how your tree is going to work at all.

    --
    ========================================================================
    Ian Pilcher
    ========================================================================
    Ian Pilcher, Jan 21, 2011
    #3
  4. jacob navia

    jacob navia Guest

    Le 21/01/11 19:28, Ian Pilcher a écrit :
    > On 01/21/2011 11:09 AM, jacob navia wrote:
    >> Within the context of the container library, I propose to use
    >> comparison functions that can take a third argument, where you
    >> can pass a context to the function without having to use global
    >> variables.

    >
    > What is the use case for passing additional context to the comparison
    > function?
    >
    > If the additional context is going to affect the result of the
    > comparison, then you have to ensure that all uses of the comparison
    > function by a given container always have the same additional context,
    > in which case it should be set when the container is created and not
    > changed.
    >
    > If you don't do this, your comparison function isn't going to be stable,
    > and it's hard to see how your tree is going to work at all.
    >


    Wow, I guess you are 200% right. I did not think about that. The
    comparison function MUST be stable. If not everything breaks down
    as you point out.

    Thanks for your message.
    jacob navia, Jan 21, 2011
    #4
  5. Ian Pilcher <> writes:
    > On 01/21/2011 11:09 AM, jacob navia wrote:
    >> Within the context of the container library, I propose to use
    >> comparison functions that can take a third argument, where you
    >> can pass a context to the function without having to use global
    >> variables.

    >
    > What is the use case for passing additional context to the comparison
    > function?
    >
    > If the additional context is going to affect the result of the
    > comparison, then you have to ensure that all uses of the comparison
    > function by a given container always have the same additional context,
    > in which case it should be set when the container is created and not
    > changed.
    >
    > If you don't do this, your comparison function isn't going to be stable,
    > and it's hard to see how your tree is going to work at all.


    A minor quibble: I think you probably mean consistent rather than
    stable.

    A "stable" sorting algorithm is one that maintains the original
    order for items with matching keys. Quicksort, for example, is
    not stable (at least not without some tweaks). (Note: I write
    "Quicksort", not qsort(); C's qsort() may or may not be stable.)

    A consistent comparison (I'm not sure if that's the usual term)
    is one that always yields the same result for any given values;
    if it reports X < Y one time, and X == Y another time, then it's
    inconsistent, and trying to use it for sorting can Cause Bad Things
    To Happen (see, for example, C99 7.20.5p4).

    I mention this because "stable" has a consistent meaning when
    referring to sorting algorithms. For jacob's purposes, I suspect
    that a non-stable sort would be acceptable, as long as the comparison
    function is consistent.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
    Keith Thompson, Jan 21, 2011
    #5
  6. jacob navia

    Ian Pilcher Guest

    On 01/21/2011 01:51 PM, Keith Thompson wrote:
    >> If you don't do this, your comparison function isn't going to be stable,
    >> and it's hard to see how your tree is going to work at all.

    >
    > A minor quibble: I think you probably mean consistent rather than
    > stable.


    Correct.

    --
    ========================================================================
    Ian Pilcher
    ========================================================================
    Ian Pilcher, Jan 21, 2011
    #6
    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. tubby

    Help with design decision

    tubby, Dec 2, 2005, in forum: ASP .Net
    Replies:
    1
    Views:
    323
    cbDevelopment
    Dec 4, 2005
  2. Marcus Reiter

    [JSP] Help with Design decision

    Marcus Reiter, Dec 29, 2004, in forum: Java
    Replies:
    1
    Views:
    393
    Ryan Stewart
    Dec 30, 2004
  3. Jeff Marder

    Feedback on a design decision?

    Jeff Marder, Oct 5, 2006, in forum: Java
    Replies:
    15
    Views:
    535
    Christopher Benson-Manica
    Oct 9, 2006
  4. __PPS__

    Class design decision

    __PPS__, Dec 7, 2006, in forum: C++
    Replies:
    5
    Views:
    315
  5. pek
    Replies:
    15
    Views:
    544
Loading...

Share This Page