3 * Copyright (C) Igor Sysoev
7 #include <ngx_config.h>
11 static void *ngx_radix_alloc(ngx_radix_tree_t *tree);
15 ngx_radix_tree_create(ngx_pool_t *pool, ngx_int_t preallocate)
17 uint32_t key, mask, inc;
18 ngx_radix_tree_t *tree;
20 tree = ngx_palloc(pool, sizeof(ngx_radix_tree_t));
30 tree->root = ngx_radix_alloc(tree);
31 if (tree->root == NULL) {
35 tree->root->right = NULL;
36 tree->root->left = NULL;
37 tree->root->parent = NULL;
38 tree->root->value = NGX_RADIX_NO_VALUE;
40 if (preallocate == 0) {
45 * Preallocation of first nodes : 0, 1, 00, 01, 10, 11, 000, 001, etc.
46 * increases TLB hits even if for first lookup iterations.
47 * On 32-bit platforms the 7 preallocated bits takes continuous 4K,
48 * 8 - 8K, 9 - 16K, etc. On 64-bit platforms the 6 preallocated bits
49 * takes continuous 4K, 7 - 8K, 8 - 16K, etc. There is no sense to
50 * to preallocate more than one page, because further preallocation
51 * distributes the only bit per page. Instead, a random insertion
52 * may distribute several bits per page.
54 * Thus, by default we preallocate maximum
55 * 6 bits on amd64 (64-bit platform and 4K pages)
56 * 7 bits on i386 (32-bit platform and 4K pages)
57 * 7 bits on sparc64 in 64-bit mode (8K pages)
58 * 8 bits on sparc64 in 32-bit mode (8K pages)
61 if (preallocate == -1) {
62 switch (ngx_pagesize / sizeof(ngx_radix_tree_t)) {
74 /* sparc64 in 32-bit mode */
83 while (preallocate--) {
90 if (ngx_radix32tree_insert(tree, key, mask, NGX_RADIX_NO_VALUE)
108 ngx_radix32tree_insert(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask,
112 ngx_radix_node_t *node, *next;
136 if (node->value != NGX_RADIX_NO_VALUE) {
145 next = ngx_radix_alloc(tree);
153 next->value = NGX_RADIX_NO_VALUE;
173 ngx_radix32tree_delete(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask)
176 ngx_radix_node_t *node;
181 while (node && (bit & mask)) {
196 if (node->right || node->left) {
197 if (node->value != NGX_RADIX_NO_VALUE) {
198 node->value = NGX_RADIX_NO_VALUE;
206 if (node->parent->right == node) {
207 node->parent->right = NULL;
210 node->parent->left = NULL;
213 node->right = tree->free;
218 if (node->right || node->left) {
222 if (node->value != NGX_RADIX_NO_VALUE) {
226 if (node->parent == NULL) {
236 ngx_radix32tree_find(ngx_radix_tree_t *tree, uint32_t key)
240 ngx_radix_node_t *node;
243 value = NGX_RADIX_NO_VALUE;
247 if (node->value != NGX_RADIX_NO_VALUE) {
266 ngx_radix_alloc(ngx_radix_tree_t *tree)
271 p = (char *) tree->free;
272 tree->free = tree->free->right;
276 if (tree->size < sizeof(ngx_radix_node_t)) {
277 tree->start = ngx_pmemalign(tree->pool, ngx_pagesize, ngx_pagesize);
278 if (tree->start == NULL) {
282 tree->size = ngx_pagesize;
286 tree->start += sizeof(ngx_radix_node_t);
287 tree->size -= sizeof(ngx_radix_node_t);