Back to home page

Nginx displayed by LXR

Source navigation ]
Diff markup ]
Identifier search ]
general search ]
 
 
Version: nginx-1.15.11 ]​[ nginx-1.14.2 ]​

0001 
0002 /*
0003  * Copyright (C) Igor Sysoev
0004  * Copyright (C) Nginx, Inc.
0005  */
0006 
0007 
0008 #include <ngx_config.h>
0009 #include <ngx_core.h>
0010 
0011 
0012 static ngx_radix_node_t *ngx_radix_alloc(ngx_radix_tree_t *tree);
0013 
0014 
0015 ngx_radix_tree_t *
0016 ngx_radix_tree_create(ngx_pool_t *pool, ngx_int_t preallocate)
0017 {
0018     uint32_t           key, mask, inc;
0019     ngx_radix_tree_t  *tree;
0020 
0021     tree = ngx_palloc(pool, sizeof(ngx_radix_tree_t));
0022     if (tree == NULL) {
0023         return NULL;
0024     }
0025 
0026     tree->pool = pool;
0027     tree->free = NULL;
0028     tree->start = NULL;
0029     tree->size = 0;
0030 
0031     tree->root = ngx_radix_alloc(tree);
0032     if (tree->root == NULL) {
0033         return NULL;
0034     }
0035 
0036     tree->root->right = NULL;
0037     tree->root->left = NULL;
0038     tree->root->parent = NULL;
0039     tree->root->value = NGX_RADIX_NO_VALUE;
0040 
0041     if (preallocate == 0) {
0042         return tree;
0043     }
0044 
0045     /*
0046      * Preallocation of first nodes : 0, 1, 00, 01, 10, 11, 000, 001, etc.
0047      * increases TLB hits even if for first lookup iterations.
0048      * On 32-bit platforms the 7 preallocated bits takes continuous 4K,
0049      * 8 - 8K, 9 - 16K, etc.  On 64-bit platforms the 6 preallocated bits
0050      * takes continuous 4K, 7 - 8K, 8 - 16K, etc.  There is no sense to
0051      * to preallocate more than one page, because further preallocation
0052      * distributes the only bit per page.  Instead, a random insertion
0053      * may distribute several bits per page.
0054      *
0055      * Thus, by default we preallocate maximum
0056      *     6 bits on amd64 (64-bit platform and 4K pages)
0057      *     7 bits on i386 (32-bit platform and 4K pages)
0058      *     7 bits on sparc64 in 64-bit mode (8K pages)
0059      *     8 bits on sparc64 in 32-bit mode (8K pages)
0060      */
0061 
0062     if (preallocate == -1) {
0063         switch (ngx_pagesize / sizeof(ngx_radix_node_t)) {
0064 
0065         /* amd64 */
0066         case 128:
0067             preallocate = 6;
0068             break;
0069 
0070         /* i386, sparc64 */
0071         case 256:
0072             preallocate = 7;
0073             break;
0074 
0075         /* sparc64 in 32-bit mode */
0076         default:
0077             preallocate = 8;
0078         }
0079     }
0080 
0081     mask = 0;
0082     inc = 0x80000000;
0083 
0084     while (preallocate--) {
0085 
0086         key = 0;
0087         mask >>= 1;
0088         mask |= 0x80000000;
0089 
0090         do {
0091             if (ngx_radix32tree_insert(tree, key, mask, NGX_RADIX_NO_VALUE)
0092                 != NGX_OK)
0093             {
0094                 return NULL;
0095             }
0096 
0097             key += inc;
0098 
0099         } while (key);
0100 
0101         inc >>= 1;
0102     }
0103 
0104     return tree;
0105 }
0106 
0107 
0108 ngx_int_t
0109 ngx_radix32tree_insert(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask,
0110     uintptr_t value)
0111 {
0112     uint32_t           bit;
0113     ngx_radix_node_t  *node, *next;
0114 
0115     bit = 0x80000000;
0116 
0117     node = tree->root;
0118     next = tree->root;
0119 
0120     while (bit & mask) {
0121         if (key & bit) {
0122             next = node->right;
0123 
0124         } else {
0125             next = node->left;
0126         }
0127 
0128         if (next == NULL) {
0129             break;
0130         }
0131 
0132         bit >>= 1;
0133         node = next;
0134     }
0135 
0136     if (next) {
0137         if (node->value != NGX_RADIX_NO_VALUE) {
0138             return NGX_BUSY;
0139         }
0140 
0141         node->value = value;
0142         return NGX_OK;
0143     }
0144 
0145     while (bit & mask) {
0146         next = ngx_radix_alloc(tree);
0147         if (next == NULL) {
0148             return NGX_ERROR;
0149         }
0150 
0151         next->right = NULL;
0152         next->left = NULL;
0153         next->parent = node;
0154         next->value = NGX_RADIX_NO_VALUE;
0155 
0156         if (key & bit) {
0157             node->right = next;
0158 
0159         } else {
0160             node->left = next;
0161         }
0162 
0163         bit >>= 1;
0164         node = next;
0165     }
0166 
0167     node->value = value;
0168 
0169     return NGX_OK;
0170 }
0171 
0172 
0173 ngx_int_t
0174 ngx_radix32tree_delete(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask)
0175 {
0176     uint32_t           bit;
0177     ngx_radix_node_t  *node;
0178 
0179     bit = 0x80000000;
0180     node = tree->root;
0181 
0182     while (node && (bit & mask)) {
0183         if (key & bit) {
0184             node = node->right;
0185 
0186         } else {
0187             node = node->left;
0188         }
0189 
0190         bit >>= 1;
0191     }
0192 
0193     if (node == NULL) {
0194         return NGX_ERROR;
0195     }
0196 
0197     if (node->right || node->left) {
0198         if (node->value != NGX_RADIX_NO_VALUE) {
0199             node->value = NGX_RADIX_NO_VALUE;
0200             return NGX_OK;
0201         }
0202 
0203         return NGX_ERROR;
0204     }
0205 
0206     for ( ;; ) {
0207         if (node->parent->right == node) {
0208             node->parent->right = NULL;
0209 
0210         } else {
0211             node->parent->left = NULL;
0212         }
0213 
0214         node->right = tree->free;
0215         tree->free = node;
0216 
0217         node = node->parent;
0218 
0219         if (node->right || node->left) {
0220             break;
0221         }
0222 
0223         if (node->value != NGX_RADIX_NO_VALUE) {
0224             break;
0225         }
0226 
0227         if (node->parent == NULL) {
0228             break;
0229         }
0230     }
0231 
0232     return NGX_OK;
0233 }
0234 
0235 
0236 uintptr_t
0237 ngx_radix32tree_find(ngx_radix_tree_t *tree, uint32_t key)
0238 {
0239     uint32_t           bit;
0240     uintptr_t          value;
0241     ngx_radix_node_t  *node;
0242 
0243     bit = 0x80000000;
0244     value = NGX_RADIX_NO_VALUE;
0245     node = tree->root;
0246 
0247     while (node) {
0248         if (node->value != NGX_RADIX_NO_VALUE) {
0249             value = node->value;
0250         }
0251 
0252         if (key & bit) {
0253             node = node->right;
0254 
0255         } else {
0256             node = node->left;
0257         }
0258 
0259         bit >>= 1;
0260     }
0261 
0262     return value;
0263 }
0264 
0265 
0266 #if (NGX_HAVE_INET6)
0267 
0268 ngx_int_t
0269 ngx_radix128tree_insert(ngx_radix_tree_t *tree, u_char *key, u_char *mask,
0270     uintptr_t value)
0271 {
0272     u_char             bit;
0273     ngx_uint_t         i;
0274     ngx_radix_node_t  *node, *next;
0275 
0276     i = 0;
0277     bit = 0x80;
0278 
0279     node = tree->root;
0280     next = tree->root;
0281 
0282     while (bit & mask[i]) {
0283         if (key[i] & bit) {
0284             next = node->right;
0285 
0286         } else {
0287             next = node->left;
0288         }
0289 
0290         if (next == NULL) {
0291             break;
0292         }
0293 
0294         bit >>= 1;
0295         node = next;
0296 
0297         if (bit == 0) {
0298             if (++i == 16) {
0299                 break;
0300             }
0301 
0302             bit = 0x80;
0303         }
0304     }
0305 
0306     if (next) {
0307         if (node->value != NGX_RADIX_NO_VALUE) {
0308             return NGX_BUSY;
0309         }
0310 
0311         node->value = value;
0312         return NGX_OK;
0313     }
0314 
0315     while (bit & mask[i]) {
0316         next = ngx_radix_alloc(tree);
0317         if (next == NULL) {
0318             return NGX_ERROR;
0319         }
0320 
0321         next->right = NULL;
0322         next->left = NULL;
0323         next->parent = node;
0324         next->value = NGX_RADIX_NO_VALUE;
0325 
0326         if (key[i] & bit) {
0327             node->right = next;
0328 
0329         } else {
0330             node->left = next;
0331         }
0332 
0333         bit >>= 1;
0334         node = next;
0335 
0336         if (bit == 0) {
0337             if (++i == 16) {
0338                 break;
0339             }
0340 
0341             bit = 0x80;
0342         }
0343     }
0344 
0345     node->value = value;
0346 
0347     return NGX_OK;
0348 }
0349 
0350 
0351 ngx_int_t
0352 ngx_radix128tree_delete(ngx_radix_tree_t *tree, u_char *key, u_char *mask)
0353 {
0354     u_char             bit;
0355     ngx_uint_t         i;
0356     ngx_radix_node_t  *node;
0357 
0358     i = 0;
0359     bit = 0x80;
0360     node = tree->root;
0361 
0362     while (node && (bit & mask[i])) {
0363         if (key[i] & bit) {
0364             node = node->right;
0365 
0366         } else {
0367             node = node->left;
0368         }
0369 
0370         bit >>= 1;
0371 
0372         if (bit == 0) {
0373             if (++i == 16) {
0374                 break;
0375             }
0376 
0377             bit = 0x80;
0378         }
0379     }
0380 
0381     if (node == NULL) {
0382         return NGX_ERROR;
0383     }
0384 
0385     if (node->right || node->left) {
0386         if (node->value != NGX_RADIX_NO_VALUE) {
0387             node->value = NGX_RADIX_NO_VALUE;
0388             return NGX_OK;
0389         }
0390 
0391         return NGX_ERROR;
0392     }
0393 
0394     for ( ;; ) {
0395         if (node->parent->right == node) {
0396             node->parent->right = NULL;
0397 
0398         } else {
0399             node->parent->left = NULL;
0400         }
0401 
0402         node->right = tree->free;
0403         tree->free = node;
0404 
0405         node = node->parent;
0406 
0407         if (node->right || node->left) {
0408             break;
0409         }
0410 
0411         if (node->value != NGX_RADIX_NO_VALUE) {
0412             break;
0413         }
0414 
0415         if (node->parent == NULL) {
0416             break;
0417         }
0418     }
0419 
0420     return NGX_OK;
0421 }
0422 
0423 
0424 uintptr_t
0425 ngx_radix128tree_find(ngx_radix_tree_t *tree, u_char *key)
0426 {
0427     u_char             bit;
0428     uintptr_t          value;
0429     ngx_uint_t         i;
0430     ngx_radix_node_t  *node;
0431 
0432     i = 0;
0433     bit = 0x80;
0434     value = NGX_RADIX_NO_VALUE;
0435     node = tree->root;
0436 
0437     while (node) {
0438         if (node->value != NGX_RADIX_NO_VALUE) {
0439             value = node->value;
0440         }
0441 
0442         if (key[i] & bit) {
0443             node = node->right;
0444 
0445         } else {
0446             node = node->left;
0447         }
0448 
0449         bit >>= 1;
0450 
0451         if (bit == 0) {
0452             i++;
0453             bit = 0x80;
0454         }
0455     }
0456 
0457     return value;
0458 }
0459 
0460 #endif
0461 
0462 
0463 static ngx_radix_node_t *
0464 ngx_radix_alloc(ngx_radix_tree_t *tree)
0465 {
0466     ngx_radix_node_t  *p;
0467 
0468     if (tree->free) {
0469         p = tree->free;
0470         tree->free = tree->free->right;
0471         return p;
0472     }
0473 
0474     if (tree->size < sizeof(ngx_radix_node_t)) {
0475         tree->start = ngx_pmemalign(tree->pool, ngx_pagesize, ngx_pagesize);
0476         if (tree->start == NULL) {
0477             return NULL;
0478         }
0479 
0480         tree->size = ngx_pagesize;
0481     }
0482 
0483     p = (ngx_radix_node_t *) tree->start;
0484     tree->start += sizeof(ngx_radix_node_t);
0485     tree->size -= sizeof(ngx_radix_node_t);
0486 
0487     return p;
0488 }