Re: [Qemu-devel] [PATCH RFC 4/4] range: Replace internal representation of Range

[Markus Armbruster <armbru@redhat.com>]

Eric Blake <eblake@redhat.com> writes:

> On 06/15/2016 02:41 PM, Markus Armbruster wrote:
>> Range represents a range as follows.  Member @start is the inclusive
>> lower bound, member @end is the exclusive upper bound.  Zero @end is
>> special: if @start is also zero, the range is empty, else @end is to
>> be interpreted as 2^64.  No other empty ranges may occur.
>> 
>> The range [0,2^64-1] cannot be represented.  If you try to create it
>> with range_set_bounds1(), you get the empty range instead.  If you try
>> to create it with range_set_bounds() or range_extend(), assertions
>> fail.  Before range_set_bounds() existed, the open-coded creation
>> usually got you the empty range instead.  Open deathtrap.
>> 
>> Moreover, the code dealing with the janus-faced @end is too clever by
>> half.
>> 
>> Dumb this down to a more pedestrian representation: members @lob and
>> @upb are inclusive lower and upper bounds.  The empty range is encoded
>> as @lob = 1, @upb = 0.
>
> And since all users now go through accessors, we've freed ourselves to
> change the underlying representation.
>
>> 
>> Signed-off-by: Markus Armbruster <armbru@redhat.com>
>> ---
>>  include/qemu/range.h | 55 +++++++++++++++++++++++++---------------------------
>>  util/range.c         | 13 +++----------
>>  2 files changed, 29 insertions(+), 39 deletions(-)
>
> Not only does it have more power, it takes fewer lines of code!

That's the kind of change I like best :)

>>  /* Compound literal encoding the empty range */
>> -#define range_empty ((Range){ .begin = 0, .end = 0 })
>> +#define range_empty ((Range){ .lob = 1, .upb = 0 })
>
> well, one particular representation of the empty range, but the comment
> is fine as-is.

The only ways to create empty ranges are range_make_empty() and
range_set_bounds1().  Both use macro range_empty below the hood.

Before this patch, there is only one empty range: { .begin=0, .end=0 }.
range_empty is this one empty range:
    #define range_empty ((Range){ .begin = 0, .end = 0 })

range_invariant() enforces it:

    assert((!range->begin && !range->end) /* empty */
           || range->begin <= range->end - 1); /* non-empty */

range_is_empty() relies on it:

    return !range->begin && !range->end;

With this patch, the code treats any range with begin > end as empty.
range_invariant():

    assert(range->lob <= range->upb || range->lob == range->upb + 1);

range_is_empty():

    return range->lob > range->upb;

Nevertheless, you can still create only one:
    #define range_empty ((Range){ .lob = 1, .upb = 0 })

I could tighten range_invariant().  Doesn't feel worthwhile to me.

> Reviewed-by: Eric Blake <eblake@redhat.com>

Thanks!