Why subtraction is used to compare in nginx_rbtree.c?

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

for ( ;; ) {

    /*
     * 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;

    if (*p == sentinel) {
        break;
    }

    temp = *p;
}

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 :slight_smile:

[…]

        ? &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 D.
http://nginx.org/

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

| Privacy Policy | Terms of Service | Remote Ruby Jobs