Mercurial > hg > nginx-quic
comparison src/core/ngx_radix_tree.c @ 340:0bf903191ceb
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 } |