comparison: ucx/avl.c
ucx/avl.c
- changeset 204
- 4477987d40cd
- parent 203
- 3d999ea3f780
- child 205
- 54a7ceb9151f
equal
deleted
inserted
replaced
| 203:3d999ea3f780 | 204:4477987d40cd |
|---|---|
| 130 UcxAllocator *al = tree->allocator; | 130 UcxAllocator *al = tree->allocator; |
| 131 ucx_avl_free_node(al, tree->root); | 131 ucx_avl_free_node(al, tree->root); |
| 132 alfree(al, tree); | 132 alfree(al, tree); |
| 133 } | 133 } |
| 134 | 134 |
| 135 void *ucx_avl_get(UcxAVLTree *tree, intptr_t key) { | 135 UcxAVLNode *ucx_avl_getn(UcxAVLTree *tree, intptr_t key) { |
| 136 UcxAVLNode *n = tree->root; | 136 UcxAVLNode *n = tree->root; |
| 137 int cmpresult; | 137 int cmpresult; |
| 138 while (n && (cmpresult = tree->cmpfunc( | 138 while (n && (cmpresult = tree->cmpfunc( |
| 139 ptrcast(key), ptrcast(n->key), tree->userdata))) { | 139 ptrcast(key), ptrcast(n->key), tree->userdata))) { |
| 140 n = cmpresult > 0 ? n->right : n->left; | 140 n = cmpresult > 0 ? n->right : n->left; |
| 141 } | 141 } |
| 142 return n; | |
| 143 } | |
| 144 | |
| 145 void *ucx_avl_get(UcxAVLTree *tree, intptr_t key) { | |
| 146 UcxAVLNode *n = ucx_avl_getn(tree, key); | |
| 142 return n ? n->value : NULL; | 147 return n ? n->value : NULL; |
| 143 } | 148 } |
| 144 | 149 |
| 145 void* ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value) { | 150 int ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value) { |
| 151 return ucx_avl_put_s(tree, key, value, NULL); | |
| 152 } | |
| 153 | |
| 154 int ucx_avl_put_s(UcxAVLTree *tree, intptr_t key, void *value, | |
| 155 void **oldvalue) { | |
| 146 if (tree->root) { | 156 if (tree->root) { |
| 147 UcxAVLNode *n = tree->root; | 157 UcxAVLNode *n = tree->root; |
| 148 int cmpresult; | 158 int cmpresult; |
| 149 while ((cmpresult = tree->cmpfunc( | 159 while ((cmpresult = tree->cmpfunc( |
| 150 ptrcast(key), ptrcast(n->key), tree->userdata))) { | 160 ptrcast(key), ptrcast(n->key), tree->userdata))) { |
| 156 } | 166 } |
| 157 } | 167 } |
| 158 | 168 |
| 159 if (cmpresult) { | 169 if (cmpresult) { |
| 160 UcxAVLNode *e = almalloc(tree->allocator, sizeof(UcxAVLNode)); | 170 UcxAVLNode *e = almalloc(tree->allocator, sizeof(UcxAVLNode)); |
| 161 e->key = key; e->value = value; e->height = 1; | 171 if (e) { |
| 162 e->parent = e->left = e->right = NULL; | 172 e->key = key; e->value = value; e->height = 1; |
| 163 ucx_avl_connect(tree, n, e, 0); | 173 e->parent = e->left = e->right = NULL; |
| 164 ucx_avl_balance(tree, n); | 174 ucx_avl_connect(tree, n, e, 0); |
| 165 return NULL; | 175 ucx_avl_balance(tree, n); |
| 176 return 0; | |
| 177 } else { | |
| 178 return 1; | |
| 179 } | |
| 166 } else { | 180 } else { |
| 167 void *prevval = n->value; | 181 if (oldvalue) { |
| 182 *oldvalue = n->value; | |
| 183 } | |
| 168 n->value = value; | 184 n->value = value; |
| 169 return prevval; | 185 return 0; |
| 170 } | 186 } |
| 171 } else { | 187 } else { |
| 172 tree->root = almalloc(tree->allocator, sizeof(UcxAVLNode)); | 188 tree->root = almalloc(tree->allocator, sizeof(UcxAVLNode)); |
| 173 tree->root->key = key; tree->root->value = value; | 189 if (tree->root) { |
| 174 tree->root->height = 1; | 190 tree->root->key = key; tree->root->value = value; |
| 175 tree->root->parent = tree->root->left = tree->root->right = NULL; | 191 tree->root->height = 1; |
| 176 return NULL; | 192 tree->root->parent = tree->root->left = tree->root->right = NULL; |
| 177 } | 193 |
| 178 } | 194 if (oldvalue) { |
| 179 | 195 *oldvalue = NULL; |
| 180 void* ucx_avl_remove(UcxAVLTree *tree, intptr_t key) { | 196 } |
| 197 | |
| 198 return 0; | |
| 199 } else { | |
| 200 return 1; | |
| 201 } | |
| 202 } | |
| 203 } | |
| 204 | |
| 205 int ucx_avl_remove(UcxAVLTree *tree, intptr_t key) { | |
| 206 return ucx_avl_remove_s(tree, key, NULL, NULL); | |
| 207 } | |
| 208 | |
| 209 int ucx_avl_remove_n(UcxAVLTree *tree, UcxAVLNode *node) { | |
| 210 return ucx_avl_remove_s(tree, node->key, NULL, NULL); | |
| 211 } | |
| 212 | |
| 213 int ucx_avl_remove_s(UcxAVLTree *tree, intptr_t key, | |
| 214 intptr_t *oldkey, void **oldvalue) { | |
| 215 | |
| 181 UcxAVLNode *n = tree->root; | 216 UcxAVLNode *n = tree->root; |
| 182 int cmpresult; | 217 int cmpresult; |
| 183 while (n && (cmpresult = tree->cmpfunc( | 218 while (n && (cmpresult = tree->cmpfunc( |
| 184 ptrcast(key), ptrcast(n->key), tree->userdata))) { | 219 ptrcast(key), ptrcast(n->key), tree->userdata))) { |
| 185 n = cmpresult > 0 ? n->right : n->left; | 220 n = cmpresult > 0 ? n->right : n->left; |
| 186 } | 221 } |
| 187 if (n) { | 222 if (n) { |
| 188 void *prevval = n->value; | 223 if (oldkey) { |
| 224 *oldkey = n->key; | |
| 225 } | |
| 226 if (oldvalue) { | |
| 227 *oldvalue = n->value; | |
| 228 } | |
| 229 | |
| 189 UcxAVLNode *p = n->parent; | 230 UcxAVLNode *p = n->parent; |
| 190 if (n->left && n->right) { | 231 if (n->left && n->right) { |
| 191 UcxAVLNode *s = n->right; | 232 UcxAVLNode *s = n->right; |
| 192 while (s->left) { | 233 while (s->left) { |
| 193 s = s->left; | 234 s = s->left; |
| 209 } | 250 } |
| 210 | 251 |
| 211 if (p) { | 252 if (p) { |
| 212 ucx_avl_balance(tree, p); | 253 ucx_avl_balance(tree, p); |
| 213 } | 254 } |
| 214 return prevval; | 255 |
| 215 } else { | 256 return 0; |
| 216 return NULL; | 257 } else { |
| 258 return 1; | |
| 217 } | 259 } |
| 218 } | 260 } |
| 219 | 261 |
| 220 static size_t ucx_avl_countn(UcxAVLNode *node) { | 262 static size_t ucx_avl_countn(UcxAVLNode *node) { |
| 221 if (node) { | 263 if (node) { |
