Mercurial > hg > nginx

comparison src/core/ngx_radix_tree.c @ 342:0ee0642af5f1

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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 {