On Mar 26, 2013, at 5:40 AM, Bill Meier <wme...@newsguy.com> 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.
___________________________________________________________________________
Sent via: Wireshark-dev mailing list <wireshark-dev@wireshark.org>
Archives: http://www.wireshark.org/lists/wireshark-dev
Unsubscribe: https://wireshark.org/mailman/options/wireshark-dev
mailto:wireshark-dev-requ...@wireshark.org?subject=unsubscribe
