[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Qemu-devel] [PATCH RFC 4/4] range: Replace internal representation
From: |
Markus Armbruster |
Subject: |
Re: [Qemu-devel] [PATCH RFC 4/4] range: Replace internal representation of Range |
Date: |
Thu, 16 Jun 2016 10:04:58 +0200 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/24.5 (gnu/linux) |
Eric Blake <address@hidden> 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 <address@hidden>
>> ---
>> 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 <address@hidden>
Thanks!