Mercurial > hg > nginx

comparison src/core/ngx_radix_tree.c @ 340:0bf903191ceb

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
nginx-0.0.3-2004-05-25-19:28:46 import
author Igor Sysoev <igor@sysoev.ru>
date Tue, 25 May 2004 15:28:46 +0000
parents
children 41e552841296
comparison
equal deleted inserted replaced
339:8c5b69141dfd 340:0bf903191ceb
1
2 #include <ngx_config.h>
3 #include <ngx_core.h>
4
5
6 /* STUB: page size */
7 #define NGX_RADIX_TREE_POOL_SIZE 4096
8
9
10 static void *ngx_radix_alloc(ngx_radix_tree_t *tree, size_t size);
11
12
13 ngx_radix_tree_t *ngx_radix_tree_create(ngx_pool_t *pool)
14 {
15 ngx_radix_tree_t *tree;
16
17 if (!(tree = ngx_palloc(pool, sizeof(ngx_radix_tree_t)))) {
18 return NULL;
19 }
20
21 tree->root = NULL;
22 tree->pool = pool;
23 tree->free = NULL;
24 tree->size = 0;
25
26 return tree;
27 }
28
29
30 ngx_int_t ngx_radix32tree_insert(ngx_radix_tree_t *tree,
31 uint32_t key, uint32_t mask, uintptr_t value)
32 {
33 uint32_t bit;
34 ngx_radix_node_t *node, *new;
35
36 bit = 0x80000000;
37 node = tree->root;
38
39 while (node && (bit & mask)) {
40 if (key & bit) {
41 node = node->right;
42
43 } else {
44 node = node->left;
45 }
46
47 bit >>= 1;
48 }
49
50 if (node) {
51 if (node->value) {
52 return NGX_BUSY;
53 }
54
55 node->value = value;
56 return NGX_OK;
57 }
58
59 while (bit & mask) {
60 if (!(new = ngx_radix_alloc(tree, sizeof(ngx_radix_node_t)))) {
61 return NGX_ERROR;
62 }
63
64 new->value = value;
65
66 if (key & bit) {
67 node->right = new;
68
69 } else {
70 node->left = new;
71 }
72
73 bit >>= 1;
74 new = node;
75 }
76
77 return NGX_OK;
78 }
79
80
81 void ngx_radix32tree_delete(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask)
82 {
83 uint32_t bit;
84 ngx_radix_node_t *node;
85
86 bit = 0x80000000;
87 node = tree->root;
88
89 while (node && (bit & mask)) {
90 if (key & bit) {
91 node = node->right;
92
93 } else {
94 node = node->left;
95 }
96
97 bit >>= 1;
98 }
99
100 if (node) {
101 node->value = (uintptr_t) 0;
102 }
103 }
104
105
106 uintptr_t ngx_radix32tree_find(ngx_radix_tree_t *tree, uint32_t key)
107 {
108 uint32_t bit;
109 uintptr_t value;
110 ngx_radix_node_t *node;
111
112 bit = 0x80000000;
113 value = NULL;
114 node = tree->root;
115
116 while (node) {
117 if (node->value) {
118 value = node->value;
119 }
120
121 if (key & bit) {
122 node = node->right;
123
124 } else {
125 node = node->left;
126 }
127
128 bit >>= 1;
129 }
130
131 return value;
132 }
133
134
135 static void *ngx_radix_alloc(ngx_radix_tree_t *tree, size_t size)
136 {
137 char *p;
138
139 if (tree->size < size) {
140 if (!(tree->free = ngx_palloc(tree->pool, NGX_RADIX_TREE_POOL_SIZE))) {
141 return NULL;
142 }
143
144 tree->size = NGX_RADIX_TREE_POOL_SIZE;
145 }
146
147 p = tree->free;
148 tree->free += size;
149 tree->size -= size;
150
151 return p;
152 }