static ngx_int_t
ngx_http_limit_req_lookup(ngx_http_limit_req_conf_t *lrcf, ngx_uint_t hash,
    u_char *data, size_t len, ngx_http_limit_req_node_t **lrp)
{
    ngx_int_t                   rc, excess;
    ngx_time_t                 *tp;
    ngx_msec_t                  now;
    ngx_msec_int_t              ms;
    ngx_rbtree_node_t          *node, *sentinel;
    ngx_http_limit_req_ctx_t   *ctx;
    ngx_http_limit_req_node_t  *lr;

    ctx = lrcf->shm_zone->data;

    node = ctx->sh->rbtree.root;
    sentinel = ctx->sh->rbtree.sentinel;

    while (node != sentinel) {

        if (hash < node->key) {
            node = node->left;
            continue;
        }

        if (hash > node->key) {
            node = node->right;
            continue;
        }

        /* hash == node->key */

        do {
            lr = (ngx_http_limit_req_node_t *) &node->color;

            rc = ngx_memn2cmp(data, lr->data, len, (size_t) lr->len);

            if (rc == 0) {

                tp = ngx_timeofday();

                now = (ngx_msec_t) (tp->sec * 1000 + tp->msec);
                ms = (ngx_msec_int_t) (now - lr->last);

                excess = lr->excess - ctx->rate * ngx_abs(ms) / 1000 + 1000;

                if (excess < 0) {
                    excess = 0;
                }

                if ((ngx_uint_t) excess > lrcf->burst) {
                    *lrp = lr;
                    return NGX_BUSY;
                }

                lr->excess = excess;
                lr->last = now;

                *lrp = lr;

                if (excess) {
                    return NGX_AGAIN;
                }

                return NGX_OK;
            }

            node = (rc < 0) ? node->left : node->right;

        } while (node != sentinel && hash == node->key);

        break;
    }

    *lrp = NULL;

    return NGX_DECLINED;
}