On Thu, 11 Nov 2021 at 22:24, Zebediah Figura zfigura@codeweavers.com wrote:
On 11/11/21 3:18 AM, Giovanni Mascellani wrote:
On 10/11/21 17:33, Zebediah Figura (she/her) wrote:
Er, sorry, I should have said intptr_t. I mean to return intptr_t from the rbtree compare callback, and then all you need is
return (intptr_t)key - (intptr_t) variable->var;Would that really work? For one thing, signed overflow is undefined behavior in C (except possibly very recent versions which we're definitely not using). It doesn't seem we're using -fwrapv, does it?
Even assuming two's complement semantics, this doesn't seem to give an order: for example, 0 > (INT_MIN + 1), because 0 - (INT_MIN + 1) = INT_MAX > 0 and INT_MAX > 0, because INT_MAX - 0 = INT_MAX > 0, but (INT_MIN + 1) - INT_MAX = 2 > 0, therefore you'd have (INT_MIN + 1) > INT_MAX. Therefore the relationship is not transitive, which I am pretty sure the red-black tree implementation won't like.
Am I missing something?
Actually I think you're right, but I didn't realize because I've seen that idiom used elsewhere. Specifically, compare_register_range() and compare_descriptor_range() in libs/vkd3d/state.c are definitely broken, and we have a few other comparison functions which are only not broken by virtue of implicit bounds.
Unless we're both missing something...
I think all three of you are right. :) I think I somehow managed to convince myself that it's safe, while clearly it isn't in all cases. Unfortunately, between vkd3d and wined3d I've managed to introduce quite a few instances of this. My suggested replacement would be to introduce a helper like this:
static int vkd3d_compare_uint32(uint32_t x, uint32_t y) { return (x > y) - (x < y); }
and then use that helper in the places where we currently have the subtraction.