comparison: ucx/avl.c
ucx/avl.c
- changeset 314
- 8722a668fb2a
- parent 255
- bf19378aed58
- child 335
- c1bc13faadaa
equal
deleted
inserted
replaced
| 313:d721250984d0 | 314:8722a668fb2a |
|---|---|
| 24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | 24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
| 25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE | 25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
| 26 * POSSIBILITY OF SUCH DAMAGE. | 26 * POSSIBILITY OF SUCH DAMAGE. |
| 27 */ | 27 */ |
| 28 | 28 |
| 29 #include <limits.h> | |
| 30 | |
| 29 #include "avl.h" | 31 #include "avl.h" |
| 30 | 32 |
| 31 #define ptrcast(ptr) ((void*)(ptr)) | 33 #define ptrcast(ptr) ((void*)(ptr)) |
| 32 #define alloc_tree(al) (UcxAVLTree*) almalloc((al), sizeof(UcxAVLTree)) | 34 #define alloc_tree(al) (UcxAVLTree*) almalloc((al), sizeof(UcxAVLTree)) |
| 33 #define alloc_node(al) (UcxAVLNode*) almalloc((al), sizeof(UcxAVLNode)) | 35 #define alloc_node(al) (UcxAVLNode*) almalloc((al), sizeof(UcxAVLNode)) |
| 147 void *ucx_avl_get(UcxAVLTree *tree, intptr_t key) { | 149 void *ucx_avl_get(UcxAVLTree *tree, intptr_t key) { |
| 148 UcxAVLNode *n = ucx_avl_get_node(tree, key); | 150 UcxAVLNode *n = ucx_avl_get_node(tree, key); |
| 149 return n ? n->value : NULL; | 151 return n ? n->value : NULL; |
| 150 } | 152 } |
| 151 | 153 |
| 154 UcxAVLNode *ucx_avl_find_node(UcxAVLTree *tree, intptr_t key, | |
| 155 distance_func dfnc, int mode) { | |
| 156 UcxAVLNode *n = tree->root; | |
| 157 UcxAVLNode *closest = NULL; | |
| 158 | |
| 159 intmax_t cmpresult; | |
| 160 intmax_t closest_dist; | |
| 161 closest_dist = mode == UCX_AVL_FIND_LOWER_BOUNDED ? INTMAX_MIN : INTMAX_MAX; | |
| 162 | |
| 163 while (n && (cmpresult = dfnc( | |
| 164 ptrcast(key), ptrcast(n->key), tree->userdata))) { | |
| 165 if (mode == UCX_AVL_FIND_CLOSEST) { | |
| 166 intmax_t dist = cmpresult; | |
| 167 if (dist < 0) dist *= -1; | |
| 168 if (dist < closest_dist) { | |
| 169 closest_dist = dist; | |
| 170 closest = n; | |
| 171 } | |
| 172 } else if (mode == UCX_AVL_FIND_LOWER_BOUNDED && cmpresult <= 0) { | |
| 173 if (cmpresult > closest_dist) { | |
| 174 closest_dist = cmpresult; | |
| 175 closest = n; | |
| 176 } | |
| 177 } else if (mode == UCX_AVL_FIND_UPPER_BOUNDED && cmpresult >= 0) { | |
| 178 if (cmpresult < closest_dist) { | |
| 179 closest_dist = cmpresult; | |
| 180 closest = n; | |
| 181 } | |
| 182 } | |
| 183 n = cmpresult > 0 ? n->right : n->left; | |
| 184 } | |
| 185 return n ? n : closest; | |
| 186 } | |
| 187 | |
| 188 void *ucx_avl_find(UcxAVLTree *tree, intptr_t key, | |
| 189 distance_func dfnc, int mode) { | |
| 190 UcxAVLNode *n = ucx_avl_find_node(tree, key, dfnc, mode); | |
| 191 return n ? n->value : NULL; | |
| 192 } | |
| 193 | |
| 152 int ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value) { | 194 int ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value) { |
| 153 return ucx_avl_put_s(tree, key, value, NULL); | 195 return ucx_avl_put_s(tree, key, value, NULL); |
| 154 } | 196 } |
| 155 | 197 |
| 156 int ucx_avl_put_s(UcxAVLTree *tree, intptr_t key, void *value, | 198 int ucx_avl_put_s(UcxAVLTree *tree, intptr_t key, void *value, |
| 270 } | 312 } |
| 271 | 313 |
| 272 size_t ucx_avl_count(UcxAVLTree *tree) { | 314 size_t ucx_avl_count(UcxAVLTree *tree) { |
| 273 return ucx_avl_countn(tree->root); | 315 return ucx_avl_countn(tree->root); |
| 274 } | 316 } |
| 317 | |
| 318 UcxAVLNode* ucx_avl_pred(UcxAVLNode* node) { | |
| 319 if (node->left) { | |
| 320 UcxAVLNode* n = node->left; | |
| 321 while (n->right) { | |
| 322 n = n->right; | |
| 323 } | |
| 324 return n; | |
| 325 } else { | |
| 326 UcxAVLNode* n = node; | |
| 327 while (n->parent) { | |
| 328 if (n->parent->right == n) { | |
| 329 return n->parent; | |
| 330 } else { | |
| 331 n = n->parent; | |
| 332 } | |
| 333 } | |
| 334 return NULL; | |
| 335 } | |
| 336 } | |
| 337 | |
| 338 UcxAVLNode* ucx_avl_succ(UcxAVLNode* node) { | |
| 339 if (node->right) { | |
| 340 UcxAVLNode* n = node->right; | |
| 341 while (n->left) { | |
| 342 n = n->left; | |
| 343 } | |
| 344 return n; | |
| 345 } else { | |
| 346 UcxAVLNode* n = node; | |
| 347 while (n->parent) { | |
| 348 if (n->parent->left == n) { | |
| 349 return n->parent; | |
| 350 } else { | |
| 351 n = n->parent; | |
| 352 } | |
| 353 } | |
| 354 return NULL; | |
| 355 } | |
| 356 } |
