[Guy Harris <guy@xxxxxxxxxxxx>]

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.