Wireshark mailing list archives
Re: [Wireshark-commits] rev 48555: /trunk/epan/ /trunk/epan/: value_string.c
From: Bill Meier <wmeier () newsguy com>
Date: Tue, 26 Mar 2013 17:30:12 -0400
On 3/26/2013 1:29 PM, Guy Harris wrote:
On Mar 26, 2013, at 5:40 AM, Bill Meier <wmeier () 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.
Right you are ! I was too quick on the draw :( Sorry for the noise .... Bill ___________________________________________________________________________ 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-request () wireshark org?subject=unsubscribe
Current thread:
- Re: [Wireshark-commits] rev 48555: /trunk/epan/ /trunk/epan/: value_string.c Bill Meier (Mar 26)
- Re: [Wireshark-commits] rev 48555: /trunk/epan/ /trunk/epan/: value_string.c Guy Harris (Mar 26)
- Re: [Wireshark-commits] rev 48555: /trunk/epan/ /trunk/epan/: value_string.c Bill Meier (Mar 26)
- Re: [Wireshark-commits] rev 48555: /trunk/epan/ /trunk/epan/: value_string.c Guy Harris (Mar 26)