On Mar 26, 2013, at 5:40 AM, Bill Meier <wmeier@xxxxxxxxxxx> wrote:
I'm curious why you added the following test in the recent value_string.c patch
if (first_value > vs_p[i].value) {
g_warning("Extended value string %s forced to fall back to linear search: entry %u, value %u < first entry, value %u",
vse->_vs_name, i, vs_p[i].value, first_value);
type = VS_SEARCH;
break;
}
I don't think it's adding that test - unless I missed something, the change was from
if ((type == VS_BIN_TREE) && (A || B)) {
type = VS_SEARCH;
complain;
break;
}
to
if (type == VS_BIN_TREE) {
if (A) {
complain about A;
type = VS_SEARCH;
break;
}
if (B) {
complain about B;
type = VS_SEARCH;
break;
}
}
B is first_value > vs_p[i].value, so it was being tested for before my change. I didn't add a test, I just split one so that the warning message would report whether A or B was the failure case.
Do you feel that the "special case" described in the comments (see extract below) should be dis-allowed (maybe because it's a bit of a hack) ?
If so, ISTR there are some value string arrays which will need to be re-ordered.
Bill
/* Note: The value_string 'value' is *unsigned*.
*
* Special case:
* { -3, -2, -1, 0, 1, 2 } will be treated as "ascending ordered"
(altho not really such)
* thus allowing as a 'direct' search.
Unless I'm missing something, if that's the special case to which you're referring, then
vs_p[i].value != (i + first_value)
will not be true in any case - the array is
{ 0xFFFFFFFD, 0xFFFFFFFE, 0xFFFFFFFF, 0, 1, 2 }
and, given that it's 32-bit unsigned arithmetic (arithmetic mod 2^32-1), that test will always be false, so the loop will never fall back to VS_BIN_TREE, and the test that was changed will never happen.
* Note:
* { -3, -2, 0, 1, 2 } and { -3, -2, -1, 0, 2 } will both be
considered as "out-of-order with gaps"
* thus requiring a 'linear' search.
That's
{ 0xFFFFFFFD, 0xFFFFFFFE, 0, 1, 2 }
and
vs_p[i].value != (i + first_value)
will fail for i = 2, as (0xFFFFFFFD + 2) = 0xFFFFFFFF, which is != 0.
So it'll fall back to VS_BIN_TREE; first_value is 0xFFFFFFFD, which is > 0, so it'll fall back again to VS_SEARCH, but that'd happen in either version of the code.
* { 0, 1, 2, -3, -2 } and { 0, 2, -3, -2, -1 } will be considered
"ascending ordered with gaps"
* thus allowing a 'binary' search.
The first of those is
{ 0, 1, 2, 0xFFFFFFFD, 0xFFFFFFFE }
and that'll fail the
vs_p[i].value != (i + first_value)
test for i = 3, and fall back to VS_BIN_TREE, but it won't fail either of the tests done for VS_BIN_TREE, in either version of the code.
The second of those is
{ 0, 2, 0xFFFFFFFD, 0xFFFFFFFE, 0xFFFFFFFF }
and the same applies, except that it'll fall back to VS_BIN_TREE for i = 2.
