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