1e18a033bSKonstantin Ananyev
2e18a033bSKonstantin Ananyev/*
3e18a033bSKonstantin Ananyev * Copyright (C) Igor Sysoev
4e18a033bSKonstantin Ananyev * Copyright (C) Nginx, Inc.
5e18a033bSKonstantin Ananyev */
6e18a033bSKonstantin Ananyev
7e18a033bSKonstantin Ananyev
8e18a033bSKonstantin Ananyev#include <ngx_config.h>
9e18a033bSKonstantin Ananyev#include <ngx_core.h>
10e18a033bSKonstantin Ananyev
11e18a033bSKonstantin Ananyev
12e18a033bSKonstantin Ananyevstatic ngx_radix_node_t *ngx_radix_alloc(ngx_radix_tree_t *tree);
13e18a033bSKonstantin Ananyev
14e18a033bSKonstantin Ananyev
15e18a033bSKonstantin Ananyevngx_radix_tree_t *
16e18a033bSKonstantin Ananyevngx_radix_tree_create(ngx_pool_t *pool, ngx_int_t preallocate)
17e18a033bSKonstantin Ananyev{
18e18a033bSKonstantin Ananyev    uint32_t           key, mask, inc;
19e18a033bSKonstantin Ananyev    ngx_radix_tree_t  *tree;
20e18a033bSKonstantin Ananyev
21e18a033bSKonstantin Ananyev    tree = ngx_palloc(pool, sizeof(ngx_radix_tree_t));
22e18a033bSKonstantin Ananyev    if (tree == NULL) {
23e18a033bSKonstantin Ananyev        return NULL;
24e18a033bSKonstantin Ananyev    }
25e18a033bSKonstantin Ananyev
26e18a033bSKonstantin Ananyev    tree->pool = pool;
27e18a033bSKonstantin Ananyev    tree->free = NULL;
28e18a033bSKonstantin Ananyev    tree->start = NULL;
29e18a033bSKonstantin Ananyev    tree->size = 0;
30e18a033bSKonstantin Ananyev
31e18a033bSKonstantin Ananyev    tree->root = ngx_radix_alloc(tree);
32e18a033bSKonstantin Ananyev    if (tree->root == NULL) {
33e18a033bSKonstantin Ananyev        return NULL;
34e18a033bSKonstantin Ananyev    }
35e18a033bSKonstantin Ananyev
36e18a033bSKonstantin Ananyev    tree->root->right = NULL;
37e18a033bSKonstantin Ananyev    tree->root->left = NULL;
38e18a033bSKonstantin Ananyev    tree->root->parent = NULL;
39e18a033bSKonstantin Ananyev    tree->root->value = NGX_RADIX_NO_VALUE;
40e18a033bSKonstantin Ananyev
41e18a033bSKonstantin Ananyev    if (preallocate == 0) {
42e18a033bSKonstantin Ananyev        return tree;
43e18a033bSKonstantin Ananyev    }
44e18a033bSKonstantin Ananyev
45e18a033bSKonstantin Ananyev    /*
46e18a033bSKonstantin Ananyev     * Preallocation of first nodes : 0, 1, 00, 01, 10, 11, 000, 001, etc.
47e18a033bSKonstantin Ananyev     * increases TLB hits even if for first lookup iterations.
48e18a033bSKonstantin Ananyev     * On 32-bit platforms the 7 preallocated bits takes continuous 4K,
49e18a033bSKonstantin Ananyev     * 8 - 8K, 9 - 16K, etc.  On 64-bit platforms the 6 preallocated bits
50e18a033bSKonstantin Ananyev     * takes continuous 4K, 7 - 8K, 8 - 16K, etc.  There is no sense to
51e18a033bSKonstantin Ananyev     * to preallocate more than one page, because further preallocation
52e18a033bSKonstantin Ananyev     * distributes the only bit per page.  Instead, a random insertion
53e18a033bSKonstantin Ananyev     * may distribute several bits per page.
54e18a033bSKonstantin Ananyev     *
55e18a033bSKonstantin Ananyev     * Thus, by default we preallocate maximum
56e18a033bSKonstantin Ananyev     *     6 bits on amd64 (64-bit platform and 4K pages)
57e18a033bSKonstantin Ananyev     *     7 bits on i386 (32-bit platform and 4K pages)
58e18a033bSKonstantin Ananyev     *     7 bits on sparc64 in 64-bit mode (8K pages)
59e18a033bSKonstantin Ananyev     *     8 bits on sparc64 in 32-bit mode (8K pages)
60e18a033bSKonstantin Ananyev     */
61e18a033bSKonstantin Ananyev
62e18a033bSKonstantin Ananyev    if (preallocate == -1) {
63e18a033bSKonstantin Ananyev        switch (ngx_pagesize / sizeof(ngx_radix_node_t)) {
64e18a033bSKonstantin Ananyev
65e18a033bSKonstantin Ananyev        /* amd64 */
66e18a033bSKonstantin Ananyev        case 128:
67e18a033bSKonstantin Ananyev            preallocate = 6;
68e18a033bSKonstantin Ananyev            break;
69e18a033bSKonstantin Ananyev
70e18a033bSKonstantin Ananyev        /* i386, sparc64 */
71e18a033bSKonstantin Ananyev        case 256:
72e18a033bSKonstantin Ananyev            preallocate = 7;
73e18a033bSKonstantin Ananyev            break;
74e18a033bSKonstantin Ananyev
75e18a033bSKonstantin Ananyev        /* sparc64 in 32-bit mode */
76e18a033bSKonstantin Ananyev        default:
77e18a033bSKonstantin Ananyev            preallocate = 8;
78e18a033bSKonstantin Ananyev        }
79e18a033bSKonstantin Ananyev    }
80e18a033bSKonstantin Ananyev
81e18a033bSKonstantin Ananyev    mask = 0;
82e18a033bSKonstantin Ananyev    inc = 0x80000000;
83e18a033bSKonstantin Ananyev
84e18a033bSKonstantin Ananyev    while (preallocate--) {
85e18a033bSKonstantin Ananyev
86e18a033bSKonstantin Ananyev        key = 0;
87e18a033bSKonstantin Ananyev        mask >>= 1;
88e18a033bSKonstantin Ananyev        mask |= 0x80000000;
89e18a033bSKonstantin Ananyev
90e18a033bSKonstantin Ananyev        do {
91e18a033bSKonstantin Ananyev            if (ngx_radix32tree_insert(tree, key, mask, NGX_RADIX_NO_VALUE)
92e18a033bSKonstantin Ananyev                != NGX_OK)
93e18a033bSKonstantin Ananyev            {
94e18a033bSKonstantin Ananyev                return NULL;
95e18a033bSKonstantin Ananyev            }
96e18a033bSKonstantin Ananyev
97e18a033bSKonstantin Ananyev            key += inc;
98e18a033bSKonstantin Ananyev
99e18a033bSKonstantin Ananyev        } while (key);
100e18a033bSKonstantin Ananyev
101e18a033bSKonstantin Ananyev        inc >>= 1;
102e18a033bSKonstantin Ananyev    }
103e18a033bSKonstantin Ananyev
104e18a033bSKonstantin Ananyev    return tree;
105e18a033bSKonstantin Ananyev}
106e18a033bSKonstantin Ananyev
107e18a033bSKonstantin Ananyev
108e18a033bSKonstantin Ananyevngx_int_t
109e18a033bSKonstantin Ananyevngx_radix32tree_insert(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask,
110e18a033bSKonstantin Ananyev    uintptr_t value)
111e18a033bSKonstantin Ananyev{
112e18a033bSKonstantin Ananyev    uint32_t           bit;
113e18a033bSKonstantin Ananyev    ngx_radix_node_t  *node, *next;
114e18a033bSKonstantin Ananyev
115e18a033bSKonstantin Ananyev    bit = 0x80000000;
116e18a033bSKonstantin Ananyev
117e18a033bSKonstantin Ananyev    node = tree->root;
118e18a033bSKonstantin Ananyev    next = tree->root;
119e18a033bSKonstantin Ananyev
120e18a033bSKonstantin Ananyev    while (bit & mask) {
121e18a033bSKonstantin Ananyev        if (key & bit) {
122e18a033bSKonstantin Ananyev            next = node->right;
123e18a033bSKonstantin Ananyev
124e18a033bSKonstantin Ananyev        } else {
125e18a033bSKonstantin Ananyev            next = node->left;
126e18a033bSKonstantin Ananyev        }
127e18a033bSKonstantin Ananyev
128e18a033bSKonstantin Ananyev        if (next == NULL) {
129e18a033bSKonstantin Ananyev            break;
130e18a033bSKonstantin Ananyev        }
131e18a033bSKonstantin Ananyev
132e18a033bSKonstantin Ananyev        bit >>= 1;
133e18a033bSKonstantin Ananyev        node = next;
134e18a033bSKonstantin Ananyev    }
135e18a033bSKonstantin Ananyev
136e18a033bSKonstantin Ananyev    if (next) {
137e18a033bSKonstantin Ananyev        if (node->value != NGX_RADIX_NO_VALUE) {
138e18a033bSKonstantin Ananyev            return NGX_BUSY;
139e18a033bSKonstantin Ananyev        }
140e18a033bSKonstantin Ananyev
141e18a033bSKonstantin Ananyev        node->value = value;
142e18a033bSKonstantin Ananyev        return NGX_OK;
143e18a033bSKonstantin Ananyev    }
144e18a033bSKonstantin Ananyev
145e18a033bSKonstantin Ananyev    while (bit & mask) {
146e18a033bSKonstantin Ananyev        next = ngx_radix_alloc(tree);
147e18a033bSKonstantin Ananyev        if (next == NULL) {
148e18a033bSKonstantin Ananyev            return NGX_ERROR;
149e18a033bSKonstantin Ananyev        }
150e18a033bSKonstantin Ananyev
151e18a033bSKonstantin Ananyev        next->right = NULL;
152e18a033bSKonstantin Ananyev        next->left = NULL;
153e18a033bSKonstantin Ananyev        next->parent = node;
154e18a033bSKonstantin Ananyev        next->value = NGX_RADIX_NO_VALUE;
155e18a033bSKonstantin Ananyev
156e18a033bSKonstantin Ananyev        if (key & bit) {
157e18a033bSKonstantin Ananyev            node->right = next;
158e18a033bSKonstantin Ananyev
159e18a033bSKonstantin Ananyev        } else {
160e18a033bSKonstantin Ananyev            node->left = next;
161e18a033bSKonstantin Ananyev        }
162e18a033bSKonstantin Ananyev
163e18a033bSKonstantin Ananyev        bit >>= 1;
164e18a033bSKonstantin Ananyev        node = next;
165e18a033bSKonstantin Ananyev    }
166e18a033bSKonstantin Ananyev
167e18a033bSKonstantin Ananyev    node->value = value;
168e18a033bSKonstantin Ananyev
169e18a033bSKonstantin Ananyev    return NGX_OK;
170e18a033bSKonstantin Ananyev}
171e18a033bSKonstantin Ananyev
172e18a033bSKonstantin Ananyev
173e18a033bSKonstantin Ananyevngx_int_t
174e18a033bSKonstantin Ananyevngx_radix32tree_delete(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask)
175e18a033bSKonstantin Ananyev{
176e18a033bSKonstantin Ananyev    uint32_t           bit;
177e18a033bSKonstantin Ananyev    ngx_radix_node_t  *node;
178e18a033bSKonstantin Ananyev
179e18a033bSKonstantin Ananyev    bit = 0x80000000;
180e18a033bSKonstantin Ananyev    node = tree->root;
181e18a033bSKonstantin Ananyev
182e18a033bSKonstantin Ananyev    while (node && (bit & mask)) {
183e18a033bSKonstantin Ananyev        if (key & bit) {
184e18a033bSKonstantin Ananyev            node = node->right;
185e18a033bSKonstantin Ananyev
186e18a033bSKonstantin Ananyev        } else {
187e18a033bSKonstantin Ananyev            node = node->left;
188e18a033bSKonstantin Ananyev        }
189e18a033bSKonstantin Ananyev
190e18a033bSKonstantin Ananyev        bit >>= 1;
191e18a033bSKonstantin Ananyev    }
192e18a033bSKonstantin Ananyev
193e18a033bSKonstantin Ananyev    if (node == NULL) {
194e18a033bSKonstantin Ananyev        return NGX_ERROR;
195e18a033bSKonstantin Ananyev    }
196e18a033bSKonstantin Ananyev
197e18a033bSKonstantin Ananyev    if (node->right || node->left) {
198e18a033bSKonstantin Ananyev        if (node->value != NGX_RADIX_NO_VALUE) {
199e18a033bSKonstantin Ananyev            node->value = NGX_RADIX_NO_VALUE;
200e18a033bSKonstantin Ananyev            return NGX_OK;
201e18a033bSKonstantin Ananyev        }
202e18a033bSKonstantin Ananyev
203e18a033bSKonstantin Ananyev        return NGX_ERROR;
204e18a033bSKonstantin Ananyev    }
205e18a033bSKonstantin Ananyev
206e18a033bSKonstantin Ananyev    for ( ;; ) {
207e18a033bSKonstantin Ananyev        if (node->parent->right == node) {
208e18a033bSKonstantin Ananyev            node->parent->right = NULL;
209e18a033bSKonstantin Ananyev
210e18a033bSKonstantin Ananyev        } else {
211e18a033bSKonstantin Ananyev            node->parent->left = NULL;
212e18a033bSKonstantin Ananyev        }
213e18a033bSKonstantin Ananyev
214e18a033bSKonstantin Ananyev        node->right = tree->free;
215e18a033bSKonstantin Ananyev        tree->free = node;
216e18a033bSKonstantin Ananyev
217e18a033bSKonstantin Ananyev        node = node->parent;
218e18a033bSKonstantin Ananyev
219e18a033bSKonstantin Ananyev        if (node->right || node->left) {
220e18a033bSKonstantin Ananyev            break;
221e18a033bSKonstantin Ananyev        }
222e18a033bSKonstantin Ananyev
223e18a033bSKonstantin Ananyev        if (node->value != NGX_RADIX_NO_VALUE) {
224e18a033bSKonstantin Ananyev            break;
225e18a033bSKonstantin Ananyev        }
226e18a033bSKonstantin Ananyev
227e18a033bSKonstantin Ananyev        if (node->parent == NULL) {
228e18a033bSKonstantin Ananyev            break;
229e18a033bSKonstantin Ananyev        }
230e18a033bSKonstantin Ananyev    }
231e18a033bSKonstantin Ananyev
232e18a033bSKonstantin Ananyev    return NGX_OK;
233e18a033bSKonstantin Ananyev}
234e18a033bSKonstantin Ananyev
235e18a033bSKonstantin Ananyev
236e18a033bSKonstantin Ananyevuintptr_t
237e18a033bSKonstantin Ananyevngx_radix32tree_find(ngx_radix_tree_t *tree, uint32_t key)
238e18a033bSKonstantin Ananyev{
239e18a033bSKonstantin Ananyev    uint32_t           bit;
240e18a033bSKonstantin Ananyev    uintptr_t          value;
241e18a033bSKonstantin Ananyev    ngx_radix_node_t  *node;
242e18a033bSKonstantin Ananyev
243e18a033bSKonstantin Ananyev    bit = 0x80000000;
244e18a033bSKonstantin Ananyev    value = NGX_RADIX_NO_VALUE;
245e18a033bSKonstantin Ananyev    node = tree->root;
246e18a033bSKonstantin Ananyev
247e18a033bSKonstantin Ananyev    while (node) {
248e18a033bSKonstantin Ananyev        if (node->value != NGX_RADIX_NO_VALUE) {
249e18a033bSKonstantin Ananyev            value = node->value;
250e18a033bSKonstantin Ananyev        }
251e18a033bSKonstantin Ananyev
252e18a033bSKonstantin Ananyev        if (key & bit) {
253e18a033bSKonstantin Ananyev            node = node->right;
254e18a033bSKonstantin Ananyev
255e18a033bSKonstantin Ananyev        } else {
256e18a033bSKonstantin Ananyev            node = node->left;
257e18a033bSKonstantin Ananyev        }
258e18a033bSKonstantin Ananyev
259e18a033bSKonstantin Ananyev        bit >>= 1;
260e18a033bSKonstantin Ananyev    }
261e18a033bSKonstantin Ananyev
262e18a033bSKonstantin Ananyev    return value;
263e18a033bSKonstantin Ananyev}
264e18a033bSKonstantin Ananyev
265e18a033bSKonstantin Ananyev
266e18a033bSKonstantin Ananyev#if (NGX_HAVE_INET6)
267e18a033bSKonstantin Ananyev
268e18a033bSKonstantin Ananyevngx_int_t
269e18a033bSKonstantin Ananyevngx_radix128tree_insert(ngx_radix_tree_t *tree, u_char *key, u_char *mask,
270e18a033bSKonstantin Ananyev    uintptr_t value)
271e18a033bSKonstantin Ananyev{
272e18a033bSKonstantin Ananyev    u_char             bit;
273e18a033bSKonstantin Ananyev    ngx_uint_t         i;
274e18a033bSKonstantin Ananyev    ngx_radix_node_t  *node, *next;
275e18a033bSKonstantin Ananyev
276e18a033bSKonstantin Ananyev    i = 0;
277e18a033bSKonstantin Ananyev    bit = 0x80;
278e18a033bSKonstantin Ananyev
279e18a033bSKonstantin Ananyev    node = tree->root;
280e18a033bSKonstantin Ananyev    next = tree->root;
281e18a033bSKonstantin Ananyev
282e18a033bSKonstantin Ananyev    while (bit & mask[i]) {
283e18a033bSKonstantin Ananyev        if (key[i] & bit) {
284e18a033bSKonstantin Ananyev            next = node->right;
285e18a033bSKonstantin Ananyev
286e18a033bSKonstantin Ananyev        } else {
287e18a033bSKonstantin Ananyev            next = node->left;
288e18a033bSKonstantin Ananyev        }
289e18a033bSKonstantin Ananyev
290e18a033bSKonstantin Ananyev        if (next == NULL) {
291e18a033bSKonstantin Ananyev            break;
292e18a033bSKonstantin Ananyev        }
293e18a033bSKonstantin Ananyev
294e18a033bSKonstantin Ananyev        bit >>= 1;
295e18a033bSKonstantin Ananyev        node = next;
296e18a033bSKonstantin Ananyev
297e18a033bSKonstantin Ananyev        if (bit == 0) {
298e18a033bSKonstantin Ananyev            if (++i == 16) {
299e18a033bSKonstantin Ananyev                break;
300e18a033bSKonstantin Ananyev            }
301e18a033bSKonstantin Ananyev
302e18a033bSKonstantin Ananyev            bit = 0x80;
303e18a033bSKonstantin Ananyev        }
304e18a033bSKonstantin Ananyev    }
305e18a033bSKonstantin Ananyev
306e18a033bSKonstantin Ananyev    if (next) {
307e18a033bSKonstantin Ananyev        if (node->value != NGX_RADIX_NO_VALUE) {
308e18a033bSKonstantin Ananyev            return NGX_BUSY;
309e18a033bSKonstantin Ananyev        }
310e18a033bSKonstantin Ananyev
311e18a033bSKonstantin Ananyev        node->value = value;
312e18a033bSKonstantin Ananyev        return NGX_OK;
313e18a033bSKonstantin Ananyev    }
314e18a033bSKonstantin Ananyev
315e18a033bSKonstantin Ananyev    while (bit & mask[i]) {
316e18a033bSKonstantin Ananyev        next = ngx_radix_alloc(tree);
317e18a033bSKonstantin Ananyev        if (next == NULL) {
318e18a033bSKonstantin Ananyev            return NGX_ERROR;
319e18a033bSKonstantin Ananyev        }
320e18a033bSKonstantin Ananyev
321e18a033bSKonstantin Ananyev        next->right = NULL;
322e18a033bSKonstantin Ananyev        next->left = NULL;
323e18a033bSKonstantin Ananyev        next->parent = node;
324e18a033bSKonstantin Ananyev        next->value = NGX_RADIX_NO_VALUE;
325e18a033bSKonstantin Ananyev
326e18a033bSKonstantin Ananyev        if (key[i] & bit) {
327e18a033bSKonstantin Ananyev            node->right = next;
328e18a033bSKonstantin Ananyev
329e18a033bSKonstantin Ananyev        } else {
330e18a033bSKonstantin Ananyev            node->left = next;
331e18a033bSKonstantin Ananyev        }
332e18a033bSKonstantin Ananyev
333e18a033bSKonstantin Ananyev        bit >>= 1;
334e18a033bSKonstantin Ananyev        node = next;
335e18a033bSKonstantin Ananyev
336e18a033bSKonstantin Ananyev        if (bit == 0) {
337e18a033bSKonstantin Ananyev            if (++i == 16) {
338e18a033bSKonstantin Ananyev                break;
339e18a033bSKonstantin Ananyev            }
340e18a033bSKonstantin Ananyev
341e18a033bSKonstantin Ananyev            bit = 0x80;
342e18a033bSKonstantin Ananyev        }
343e18a033bSKonstantin Ananyev    }
344e18a033bSKonstantin Ananyev
345e18a033bSKonstantin Ananyev    node->value = value;
346e18a033bSKonstantin Ananyev
347e18a033bSKonstantin Ananyev    return NGX_OK;
348e18a033bSKonstantin Ananyev}
349e18a033bSKonstantin Ananyev
350e18a033bSKonstantin Ananyev
351e18a033bSKonstantin Ananyevngx_int_t
352e18a033bSKonstantin Ananyevngx_radix128tree_delete(ngx_radix_tree_t *tree, u_char *key, u_char *mask)
353e18a033bSKonstantin Ananyev{
354e18a033bSKonstantin Ananyev    u_char             bit;
355e18a033bSKonstantin Ananyev    ngx_uint_t         i;
356e18a033bSKonstantin Ananyev    ngx_radix_node_t  *node;
357e18a033bSKonstantin Ananyev
358e18a033bSKonstantin Ananyev    i = 0;
359e18a033bSKonstantin Ananyev    bit = 0x80;
360e18a033bSKonstantin Ananyev    node = tree->root;
361e18a033bSKonstantin Ananyev
362e18a033bSKonstantin Ananyev    while (node && (bit & mask[i])) {
363e18a033bSKonstantin Ananyev        if (key[i] & bit) {
364e18a033bSKonstantin Ananyev            node = node->right;
365e18a033bSKonstantin Ananyev
366e18a033bSKonstantin Ananyev        } else {
367e18a033bSKonstantin Ananyev            node = node->left;
368e18a033bSKonstantin Ananyev        }
369e18a033bSKonstantin Ananyev
370e18a033bSKonstantin Ananyev        bit >>= 1;
371e18a033bSKonstantin Ananyev
372e18a033bSKonstantin Ananyev        if (bit == 0) {
373e18a033bSKonstantin Ananyev            if (++i == 16) {
374e18a033bSKonstantin Ananyev                break;
375e18a033bSKonstantin Ananyev            }
376e18a033bSKonstantin Ananyev
377e18a033bSKonstantin Ananyev            bit = 0x80;
378e18a033bSKonstantin Ananyev        }
379e18a033bSKonstantin Ananyev    }
380e18a033bSKonstantin Ananyev
381e18a033bSKonstantin Ananyev    if (node == NULL) {
382e18a033bSKonstantin Ananyev        return NGX_ERROR;
383e18a033bSKonstantin Ananyev    }
384e18a033bSKonstantin Ananyev
385e18a033bSKonstantin Ananyev    if (node->right || node->left) {
386e18a033bSKonstantin Ananyev        if (node->value != NGX_RADIX_NO_VALUE) {
387e18a033bSKonstantin Ananyev            node->value = NGX_RADIX_NO_VALUE;
388e18a033bSKonstantin Ananyev            return NGX_OK;
389e18a033bSKonstantin Ananyev        }
390e18a033bSKonstantin Ananyev
391e18a033bSKonstantin Ananyev        return NGX_ERROR;
392e18a033bSKonstantin Ananyev    }
393e18a033bSKonstantin Ananyev
394e18a033bSKonstantin Ananyev    for ( ;; ) {
395e18a033bSKonstantin Ananyev        if (node->parent->right == node) {
396e18a033bSKonstantin Ananyev            node->parent->right = NULL;
397e18a033bSKonstantin Ananyev
398e18a033bSKonstantin Ananyev        } else {
399e18a033bSKonstantin Ananyev            node->parent->left = NULL;
400e18a033bSKonstantin Ananyev        }
401e18a033bSKonstantin Ananyev
402e18a033bSKonstantin Ananyev        node->right = tree->free;
403e18a033bSKonstantin Ananyev        tree->free = node;
404e18a033bSKonstantin Ananyev
405e18a033bSKonstantin Ananyev        node = node->parent;
406e18a033bSKonstantin Ananyev
407e18a033bSKonstantin Ananyev        if (node->right || node->left) {
408e18a033bSKonstantin Ananyev            break;
409e18a033bSKonstantin Ananyev        }
410e18a033bSKonstantin Ananyev
411e18a033bSKonstantin Ananyev        if (node->value != NGX_RADIX_NO_VALUE) {
412e18a033bSKonstantin Ananyev            break;
413e18a033bSKonstantin Ananyev        }
414e18a033bSKonstantin Ananyev
415e18a033bSKonstantin Ananyev        if (node->parent == NULL) {
416e18a033bSKonstantin Ananyev            break;
417e18a033bSKonstantin Ananyev        }
418e18a033bSKonstantin Ananyev    }
419e18a033bSKonstantin Ananyev
420e18a033bSKonstantin Ananyev    return NGX_OK;
421e18a033bSKonstantin Ananyev}
422e18a033bSKonstantin Ananyev