Mercurial > hg > nginx
comparison src/core/ngx_radix_tree.c @ 342:0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
author | Igor Sysoev <igor@sysoev.ru> |
---|---|
date | Wed, 26 May 2004 19:33:53 +0000 |
parents | 41e552841296 |
children | af4c6b45a687 |
comparison
equal
deleted
inserted
replaced
341:41e552841296 | 342:0ee0642af5f1 |
---|---|
16 | 16 |
17 if (!(tree = ngx_palloc(pool, sizeof(ngx_radix_tree_t)))) { | 17 if (!(tree = ngx_palloc(pool, sizeof(ngx_radix_tree_t)))) { |
18 return NULL; | 18 return NULL; |
19 } | 19 } |
20 | 20 |
21 tree->root = NULL; | |
22 tree->pool = pool; | 21 tree->pool = pool; |
23 tree->free = NULL; | 22 tree->free = NULL; |
24 tree->start = NULL; | 23 tree->start = NULL; |
25 tree->size = 0; | 24 tree->size = 0; |
26 | 25 |
26 if (!(tree->root = ngx_radix_alloc(tree, sizeof(ngx_radix_node_t)))) { | |
27 return NULL; | |
28 } | |
29 | |
30 tree->root->value = (uintptr_t) 0; | |
31 tree->root->right = NULL; | |
32 tree->root->left = NULL; | |
33 tree->root->parent = NULL; | |
34 | |
27 return tree; | 35 return tree; |
28 } | 36 } |
29 | 37 |
30 | 38 |
31 ngx_int_t ngx_radix32tree_insert(ngx_radix_tree_t *tree, | 39 ngx_int_t ngx_radix32tree_insert(ngx_radix_tree_t *tree, |
32 uint32_t key, uint32_t mask, uintptr_t value) | 40 uint32_t key, uint32_t mask, uintptr_t value) |
33 { | 41 { |
34 uint32_t bit; | 42 uint32_t bit; |
35 ngx_radix_node_t *node, *new; | 43 ngx_radix_node_t *node, *next; |
36 | 44 |
37 bit = 0x80000000; | 45 bit = 0x80000000; |
38 node = tree->root; | 46 node = tree->root; |
39 | 47 next = NULL; |
40 while (node && (bit & mask)) { | 48 |
41 if (key & bit) { | 49 while (bit & mask) { |
42 node = node->right; | 50 if (key & bit) { |
43 | 51 next = node->right; |
44 } else { | 52 |
45 node = node->left; | 53 } else { |
46 } | 54 next = node->left; |
47 | 55 } |
48 bit >>= 1; | 56 |
49 } | 57 bit >>= 1; |
50 | 58 |
51 if (node) { | 59 if (next == NULL) { |
60 break; | |
61 } | |
62 | |
63 node = next; | |
64 } | |
65 | |
66 if (next) { | |
52 if (node->value) { | 67 if (node->value) { |
53 return NGX_BUSY; | 68 return NGX_BUSY; |
54 } | 69 } |
55 | 70 |
56 node->value = value; | 71 node->value = value; |
57 return NGX_OK; | 72 return NGX_OK; |
58 } | 73 } |
59 | 74 |
60 while (bit & mask) { | 75 while (bit & mask) { |
61 if (!(new = ngx_radix_alloc(tree, sizeof(ngx_radix_node_t)))) { | 76 if (!(next = ngx_radix_alloc(tree, sizeof(ngx_radix_node_t)))) { |
62 return NGX_ERROR; | 77 return NGX_ERROR; |
63 } | 78 } |
64 | 79 |
65 new->value = value; | 80 next->value = value; |
66 new->right = NULL; | 81 next->right = NULL; |
67 new->left = NULL; | 82 next->left = NULL; |
68 | 83 next->parent = node; |
69 if (key & bit) { | 84 |
70 node->right = new; | 85 if (key & bit) { |
71 | 86 node->right = next; |
72 } else { | 87 |
73 node->left = new; | 88 } else { |
74 } | 89 node->left = next; |
75 | 90 } |
76 bit >>= 1; | 91 |
77 new = node; | 92 bit >>= 1; |
93 node = next; | |
78 } | 94 } |
79 | 95 |
80 return NGX_OK; | 96 return NGX_OK; |
81 } | 97 } |
82 | 98 |
83 | 99 |
84 void ngx_radix32tree_delete(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask) | 100 ngx_int_t ngx_radix32tree_delete(ngx_radix_tree_t *tree, |
101 uint32_t key, uint32_t mask) | |
85 { | 102 { |
86 uint32_t bit; | 103 uint32_t bit; |
87 ngx_radix_node_t *node, **prev; | 104 ngx_radix_node_t *node; |
88 | 105 |
89 bit = 0x80000000; | 106 bit = 0x80000000; |
90 node = tree->root; | 107 node = tree->root; |
91 prev = NULL; | |
92 | 108 |
93 while (node && (bit & mask)) { | 109 while (node && (bit & mask)) { |
94 if (key & bit) { | 110 if (key & bit) { |
95 prev = &node->right;; | |
96 node = node->right; | 111 node = node->right; |
97 | 112 |
98 } else { | 113 } else { |
99 prev = &node->left;; | |
100 node = node->left; | 114 node = node->left; |
101 } | 115 } |
102 | 116 |
103 bit >>= 1; | 117 bit >>= 1; |
104 } | 118 } |
105 | 119 |
106 if (node) { | 120 if (node == NULL) { |
107 | 121 return NGX_ERROR; |
108 /* the leaf nodes are moved to the free list only */ | 122 } |
109 | 123 |
110 if (node->right == NULL && node->left == NULL) { | 124 if (node->right || node->left) { |
111 *prev = NULL; | 125 node->value = (uintptr_t) 0; |
112 node->right = tree->free; | 126 return NGX_OK; |
113 tree->free = node; | 127 } |
114 | 128 |
115 } else { | 129 for ( ;; ) { |
116 node->value = (uintptr_t) 0; | 130 if (node->parent->right == node) { |
117 } | 131 node->parent->right = NULL; |
118 } | 132 } else { |
133 node->parent->left = NULL; | |
134 } | |
135 | |
136 node->right = tree->free; | |
137 tree->free = node; | |
138 | |
139 node = node->parent; | |
140 | |
141 if (node->right || node->left || node->value || node->parent == NULL) { | |
142 break; | |
143 } | |
144 } | |
145 | |
146 return NGX_OK; | |
119 } | 147 } |
120 | 148 |
121 | 149 |
122 uintptr_t ngx_radix32tree_find(ngx_radix_tree_t *tree, uint32_t key) | 150 uintptr_t ngx_radix32tree_find(ngx_radix_tree_t *tree, uint32_t key) |
123 { | 151 { |