Why subtraction is used to compare in nginx_rbtree.c?

[Maxim Dounin]

Hello!

On Tue, Mar 24, 2015 at 03:39:23PM +0800, 张奕普 wrote:

> When I study the rbtree of nginx I can't understand the comments. Can
> someone give me a concrete example?Thanks :)

[...]

>         /*
>          * Timer values
>          * 1) are spread in small range, usually several minutes,
>          * 2) and overflow each 49 days, if milliseconds are stored in 32 bits.
>          * The comparison takes into account that overflow.
>          */
> 
>         /*  node->key < temp->key */
> 
>         p = ((ngx_rbtree_key_int_t) (node->key - temp->key) < 0)
>             ? &temp->left : &temp->right;

Consider (assuming 32-bit keys):

    node->key = 4294967295
    temp->key = 0

The 0 value is bigger, because it's (4294967295 + 1).  And that's 
what the code checks.  The

    (ngx_rbtree_key_int_t) (node->key - temp->key)

evaluates to

    (ngx_rbtree_key_int_t) (4294967295 - 0)

and becomes negative after casting to signed (note: this 
conversion result is actually implementation-defined, but this is 
how it works in practice).

-- 
Maxim Dounin
http://nginx.org/