Design decision

[jacob navia]

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

 

[Ben Bacarisse]

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.

 

[Ian Pilcher]

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.

 

[jacob navia]

Le 21/01/11 19:28, Ian Pilcher a écrit :

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.

 

[Keith Thompson]

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.

 

[Ian Pilcher]

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

Correct.