Mercurial > hg > nginx-vendor-0-8

comparison src/core/ngx_radix_tree.c @ 38:2879cd3a40cb NGINX_0_1_19

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
nginx 0.1.19 *) Bugfix: now, if request contains the zero, then the 404 error is returned for the local requests. *) Bugfix: nginx could not be built on NetBSD 2.0. *) Bugfix: the timeout may occur while reading of the the client request body via SSL connections.
author Igor Sysoev <http://sysoev.ru>
date Wed, 16 Feb 2005 00:00:00 +0300
parents a39d1b793287
children 41ccba1aba45
comparison
equal deleted inserted replaced
37:3376a7dea5d6 38:2879cd3a40cb
10 10
11 static void *ngx_radix_alloc(ngx_radix_tree_t *tree); 11 static void *ngx_radix_alloc(ngx_radix_tree_t *tree);
12 12
13 13
14 ngx_radix_tree_t * 14 ngx_radix_tree_t *
15 ngx_radix_tree_create(ngx_pool_t *pool, ngx_uint_t preallocate) 15 ngx_radix_tree_create(ngx_pool_t *pool, ngx_int_t preallocate)
16 { 16 {
17 uint32_t key, mask, inc; 17 uint32_t key, mask, inc;
18 ngx_radix_tree_t *tree; 18 ngx_radix_tree_t *tree;
19 19
20 if (!(tree = ngx_palloc(pool, sizeof(ngx_radix_tree_t)))) { 20 if (!(tree = ngx_palloc(pool, sizeof(ngx_radix_tree_t)))) {
33 tree->root->right = NULL; 33 tree->root->right = NULL;
34 tree->root->left = NULL; 34 tree->root->left = NULL;
35 tree->root->parent = NULL; 35 tree->root->parent = NULL;
36 tree->root->value = NGX_RADIX_NO_VALUE; 36 tree->root->value = NGX_RADIX_NO_VALUE;
37 37
38 if (preallocate == 0) {
39 return tree;
40 }
41
38 /* 42 /*
39 * We preallocate the first nodes: 0, 1, 00, 01, 10, 11, 000, 001, etc., 43 * We preallocate the first nodes: 0, 1, 00, 01, 10, 11, 000, 001, etc.,
40 * to increase the TLB hits even if for the first lookup iterations. 44 * to increase the TLB hits even if for the first lookup iterations.
41 * On the 32-bit platforms the 7 preallocated bits takes continuous 4K, 45 * On the 32-bit platforms the 7 preallocated bits takes continuous 4K,
42 * 8 - 8K, 9 - 16K, etc. 46 * 8 - 8K, 9 - 16K, etc. On the 64-bit platforms the 6 preallocated bits
47 * takes continuous 4K, 7 - 8K, 8 - 16K, etc. There is no sense to
48 * to preallocate more than one page, because further preallocation
49 * distribute the only bit per page. Instead, the random insertion
50 * may distribute several bits per page.
51 *
52 * Thus, by default we preallocate maximum
53 * 6 bits on amd64 (64-bit platform and 4K pages)
54 * 7 bits on i386 (32-bit platform and 4K pages)
55 * 7 bits on sparc64 in 64-bit mode (8K pages)
56 * 8 bits on sparc64 in 32-bit mode (8K pages)
43 */ 57 */
58
59 if (preallocate == -1) {
60 switch (ngx_pagesize / sizeof(ngx_radix_tree_t)) {
61
62 /* amd64 */
63 case 128:
64 preallocate = 6;
65 break;
66
67 /* i386, sparc64 */
68 case 256:
69 preallocate = 7;
70 break;
71
72 /* sparc64 in 32-bit mode */
73 default:
74 preallocate = 8;
75 }
76 }
44 77
45 mask = 0; 78 mask = 0;
46 inc = 0x80000000; 79 inc = 0x80000000;
47 80
48 while (preallocate--) { 81 while (preallocate--) {