Mercurial > hg > nginx

comparison src/core/ngx_radix_tree.c @ 341:41e552841296

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
nginx-0.0.3-2004-05-26-19:30:12 import
author Igor Sysoev <igor@sysoev.ru>
date Wed, 26 May 2004 15:30:12 +0000
parents 0bf903191ceb
children 0ee0642af5f1
comparison
equal deleted inserted replaced
340:0bf903191ceb 341:41e552841296
19 } 19 }
20 20
21 tree->root = NULL; 21 tree->root = NULL;
22 tree->pool = pool; 22 tree->pool = pool;
23 tree->free = NULL; 23 tree->free = NULL;
24 tree->start = NULL;
24 tree->size = 0; 25 tree->size = 0;
25 26
26 return tree; 27 return tree;
27 } 28 }
28 29
60 if (!(new = ngx_radix_alloc(tree, sizeof(ngx_radix_node_t)))) { 61 if (!(new = ngx_radix_alloc(tree, sizeof(ngx_radix_node_t)))) {
61 return NGX_ERROR; 62 return NGX_ERROR;
62 } 63 }
63 64
64 new->value = value; 65 new->value = value;
66 new->right = NULL;
67 new->left = NULL;
65 68
66 if (key & bit) { 69 if (key & bit) {
67 node->right = new; 70 node->right = new;
68 71
69 } else { 72 } else {
79 82
80 83
81 void ngx_radix32tree_delete(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask) 84 void ngx_radix32tree_delete(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask)
82 { 85 {
83 uint32_t bit; 86 uint32_t bit;
84 ngx_radix_node_t *node; 87 ngx_radix_node_t *node, **prev;
85 88
86 bit = 0x80000000; 89 bit = 0x80000000;
87 node = tree->root; 90 node = tree->root;
91 prev = NULL;
88 92
89 while (node && (bit & mask)) { 93 while (node && (bit & mask)) {
90 if (key & bit) { 94 if (key & bit) {
95 prev = &node->right;;
91 node = node->right; 96 node = node->right;
92 97
93 } else { 98 } else {
99 prev = &node->left;;
94 node = node->left; 100 node = node->left;
95 } 101 }
96 102
97 bit >>= 1; 103 bit >>= 1;
98 } 104 }
99 105
100 if (node) { 106 if (node) {
101 node->value = (uintptr_t) 0; 107
108 /* the leaf nodes are moved to the free list only */
109
110 if (node->right == NULL && node->left == NULL) {
111 *prev = NULL;
112 node->right = tree->free;
113 tree->free = node;
114
115 } else {
116 node->value = (uintptr_t) 0;
117 }
102 } 118 }
103 } 119 }
104 120
105 121
106 uintptr_t ngx_radix32tree_find(ngx_radix_tree_t *tree, uint32_t key) 122 uintptr_t ngx_radix32tree_find(ngx_radix_tree_t *tree, uint32_t key)
108 uint32_t bit; 124 uint32_t bit;
109 uintptr_t value; 125 uintptr_t value;
110 ngx_radix_node_t *node; 126 ngx_radix_node_t *node;
111 127
112 bit = 0x80000000; 128 bit = 0x80000000;
113 value = NULL; 129 value = (uintptr_t) 0;
114 node = tree->root; 130 node = tree->root;
115 131
116 while (node) { 132 while (node) {
117 if (node->value) { 133 if (node->value) {
118 value = node->value; 134 value = node->value;
134 150
135 static void *ngx_radix_alloc(ngx_radix_tree_t *tree, size_t size) 151 static void *ngx_radix_alloc(ngx_radix_tree_t *tree, size_t size)
136 { 152 {
137 char *p; 153 char *p;
138 154
155 if (tree->free) {
156 p = (char *) tree->free;
157 tree->free = tree->free->right;
158 return p;
159 }
160
139 if (tree->size < size) { 161 if (tree->size < size) {
140 if (!(tree->free = ngx_palloc(tree->pool, NGX_RADIX_TREE_POOL_SIZE))) { 162 if (!(tree->start = ngx_palloc(tree->pool, NGX_RADIX_TREE_POOL_SIZE))) {
141 return NULL; 163 return NULL;
142 } 164 }
143 165
144 tree->size = NGX_RADIX_TREE_POOL_SIZE; 166 tree->size = NGX_RADIX_TREE_POOL_SIZE;
145 } 167 }
146 168
147 p = tree->free; 169 p = tree->start;
148 tree->free += size; 170 tree->start += size;
149 tree->size -= size; 171 tree->size -= size;
150 172
151 return p; 173 return p;
152 } 174 }