3 * Copyright (C) Igor Sysoev
4 * Copyright (C) Nginx, Inc.
8 #include <ngx_config.h>
12 static ngx_radix_node_t
*ngx_radix_alloc(ngx_radix_tree_t
*tree
);
16 ngx_radix_tree_create(ngx_pool_t
*pool
, ngx_int_t preallocate
)
18 uint32_t key
, mask
, inc
;
19 ngx_radix_tree_t
*tree
;
21 tree
= ngx_palloc(pool
, sizeof(ngx_radix_tree_t
));
31 tree
->root
= ngx_radix_alloc(tree
);
32 if (tree
->root
== NULL
) {
36 tree
->root
->right
= NULL
;
37 tree
->root
->left
= NULL
;
38 tree
->root
->parent
= NULL
;
39 tree
->root
->value
= NGX_RADIX_NO_VALUE
;
41 if (preallocate
== 0) {
46 * Preallocation of first nodes : 0, 1, 00, 01, 10, 11, 000, 001, etc.
47 * increases TLB hits even if for first lookup iterations.
48 * On 32-bit platforms the 7 preallocated bits takes continuous 4K,
49 * 8 - 8K, 9 - 16K, etc. On 64-bit platforms the 6 preallocated bits
50 * takes continuous 4K, 7 - 8K, 8 - 16K, etc. There is no sense to
51 * to preallocate more than one page, because further preallocation
52 * distributes the only bit per page. Instead, a random insertion
53 * may distribute several bits per page.
55 * Thus, by default we preallocate maximum
56 * 6 bits on amd64 (64-bit platform and 4K pages)
57 * 7 bits on i386 (32-bit platform and 4K pages)
58 * 7 bits on sparc64 in 64-bit mode (8K pages)
59 * 8 bits on sparc64 in 32-bit mode (8K pages)
62 if (preallocate
== -1) {
63 switch (ngx_pagesize
/ sizeof(ngx_radix_node_t
)) {
75 /* sparc64 in 32-bit mode */
84 while (preallocate
--) {
91 if (ngx_radix32tree_insert(tree
, key
, mask
, NGX_RADIX_NO_VALUE
)
109 ngx_radix32tree_insert(ngx_radix_tree_t
*tree
, uint32_t key
, uint32_t mask
,
113 ngx_radix_node_t
*node
, *next
;
137 if (node
->value
!= NGX_RADIX_NO_VALUE
) {
146 next
= ngx_radix_alloc(tree
);
154 next
->value
= NGX_RADIX_NO_VALUE
;
174 ngx_radix32tree_delete(ngx_radix_tree_t
*tree
, uint32_t key
, uint32_t mask
)
177 ngx_radix_node_t
*node
;
182 while (node
&& (bit
& mask
)) {
197 if (node
->right
|| node
->left
) {
198 if (node
->value
!= NGX_RADIX_NO_VALUE
) {
199 node
->value
= NGX_RADIX_NO_VALUE
;
207 if (node
->parent
->right
== node
) {
208 node
->parent
->right
= NULL
;
211 node
->parent
->left
= NULL
;
214 node
->right
= tree
->free
;
219 if (node
->right
|| node
->left
) {
223 if (node
->value
!= NGX_RADIX_NO_VALUE
) {
227 if (node
->parent
== NULL
) {
237 ngx_radix32tree_find(ngx_radix_tree_t
*tree
, uint32_t key
)
241 ngx_radix_node_t
*node
;
244 value
= NGX_RADIX_NO_VALUE
;
248 if (node
->value
!= NGX_RADIX_NO_VALUE
) {
269 ngx_radix128tree_insert(ngx_radix_tree_t
*tree
, u_char
*key
, u_char
*mask
,
274 ngx_radix_node_t
*node
, *next
;
282 while (bit
& mask
[i
]) {
307 if (node
->value
!= NGX_RADIX_NO_VALUE
) {
315 while (bit
& mask
[i
]) {
316 next
= ngx_radix_alloc(tree
);
324 next
->value
= NGX_RADIX_NO_VALUE
;
352 ngx_radix128tree_delete(ngx_radix_tree_t
*tree
, u_char
*key
, u_char
*mask
)
356 ngx_radix_node_t
*node
;
362 while (node
&& (bit
& mask
[i
])) {
385 if (node
->right
|| node
->left
) {
386 if (node
->value
!= NGX_RADIX_NO_VALUE
) {
387 node
->value
= NGX_RADIX_NO_VALUE
;
395 if (node
->parent
->right
== node
) {
396 node
->parent
->right
= NULL
;
399 node
->parent
->left
= NULL
;
402 node
->right
= tree
->free
;
407 if (node
->right
|| node
->left
) {
411 if (node
->value
!= NGX_RADIX_NO_VALUE
) {
415 if (node
->parent
== NULL
) {
425 ngx_radix128tree_find(ngx_radix_tree_t
*tree
, u_char
*key
)
430 ngx_radix_node_t
*node
;
434 value
= NGX_RADIX_NO_VALUE
;
438 if (node
->value
!= NGX_RADIX_NO_VALUE
) {
463 static ngx_radix_node_t
*
464 ngx_radix_alloc(ngx_radix_tree_t
*tree
)
470 tree
->free
= tree
->free
->right
;
474 if (tree
->size
< sizeof(ngx_radix_node_t
)) {
475 tree
->start
= ngx_pmemalign(tree
->pool
, ngx_pagesize
, ngx_pagesize
);
476 if (tree
->start
== NULL
) {
480 tree
->size
= ngx_pagesize
;
483 p
= (ngx_radix_node_t
*) tree
->start
;
484 tree
->start
+= sizeof(ngx_radix_node_t
);
485 tree
->size
-= sizeof(ngx_radix_node_t
);