Home My Page Projects Code Snippets Project Openings DPWS Core
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files Mediawiki

[#396] da_is_included questionable

Date:
2013-04-02 18:44
Priority:
3
State:
Open
Submitted by:
Raymond Dubler (remozis)
Assigned to:
Stéphane ROUGES (srouges)
Target Fix Version:
Unassigned
Product:
none
Operating System:
none
Component:
none
Version:
none
Severity:
trivial
Resolution:
Fixed
Hardware:
none
URL:
Summary:
da_is_included questionable

Detailed description
da_is_included has a return value of DC_TRUE "if a is included in b", else DC_FALSE. If you assume that this means every value of set A has to be present in set B, then the current implementation of da_is_included does not work. A workaround for da_is_included that adheres to the above statement could look as follows:

DC_BOOL da_is_included(dyn_array_t *a, dyn_array_t *b, da_cmp_cbk compare)
{
int i, j;
if (a == NULL || a->nb == 0)
return DC_TRUE;
if (b == NULL || b->nb == 0)
return DC_FALSE;
for (i = 0; i < a->nb; i++)
{
int present = 0;
for (j = 0; j < b->nb ; j++ ) {
if ( 0 == compare(GET_ENTRY(a, i), GET_ENTRY(b, j)) ) {
present = 1;
break;
}
}
if (0 == present)
return DC_FALSE;
}
return DC_TRUE;
}

Is my understanding of "is included" correct?

-Remo-
Message  ↓
Date: 2013-04-08 13:05
Sender: Stéphane ROUGES

Fixed in trunk.

Date: 2013-04-08 12:46
Sender: Stéphane ROUGES

Sorry, you were right...
The trick is that that da_is_included() was made a reusable tool used especially for discovery but the semantics of the comparator should be in fact a boolean in case of equality (this is what is still expecting the code using it). I'm going to create a new callback type with the right semantics.
I did not check carefully enough what you said because neither our tests, neither our users did detect any problem of this kind in discovery.
Thank you,
Stéphane

Date: 2013-04-05 19:00
Sender: Raymond Dubler

To shed some more light on this, consider the following:
I assume compare works like strcmp; if the values are not the same you get a 0> or <0 back, and if they match you get a 0 back.
In the inner loop when compare returns 0 (due to match), that gets negated and turns into a 1, which keeps the loop running.

Date: 2013-04-05 18:08
Sender: Raymond Dubler

I tested the loop with a disjoint set and still got true back, which made me suspicious.  The problem is that the inner loop breaks on the 1st occurence of a non true element, but will only return false if it made it to the end of the inner loop.

Date: 2013-04-04 08:44
Sender: Stéphane ROUGES

Hi,

I think your understanding of the function is OK but I don't see how your code is different ? For me, you do the same as the original does, except that you use an intermediate variable that we spare. You exit the inner loop when the "a" element is found and set "present" while we exit when found and check we exhausted the "b" set because the bound was reached to detect failure of inclusion.
Did you get to inspect this code because you faced a misbehavior of the software ?
BR,

Stéphane

Field Old Value Date By
assigned_tonone2013-04-08 13:05srouges
SeverityNone2013-04-08 13:05srouges
ResolutionAccepted As Bug2013-04-08 13:05srouges
ResolutionWorks For Me2013-04-08 12:46srouges
ResolutionNone2013-04-04 08:44srouges