Wed, 07 Aug 2019 21:14:58 +0200
ucx_array_sort() uses qsort_r(), if available
universe@192 | 1 | /* |
universe@192 | 2 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. |
universe@192 | 3 | * |
universe@259 | 4 | * Copyright 2017 Mike Becker, Olaf Wintermann All rights reserved. |
universe@192 | 5 | * |
universe@192 | 6 | * Redistribution and use in source and binary forms, with or without |
universe@192 | 7 | * modification, are permitted provided that the following conditions are met: |
universe@192 | 8 | * |
universe@192 | 9 | * 1. Redistributions of source code must retain the above copyright |
universe@192 | 10 | * notice, this list of conditions and the following disclaimer. |
universe@192 | 11 | * |
universe@192 | 12 | * 2. Redistributions in binary form must reproduce the above copyright |
universe@192 | 13 | * notice, this list of conditions and the following disclaimer in the |
universe@192 | 14 | * documentation and/or other materials provided with the distribution. |
universe@192 | 15 | * |
universe@192 | 16 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
universe@192 | 17 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
universe@192 | 18 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
universe@192 | 19 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE |
universe@192 | 20 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
universe@192 | 21 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
universe@192 | 22 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
universe@192 | 23 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
universe@192 | 24 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
universe@192 | 25 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
universe@192 | 26 | * POSSIBILITY OF SUCH DAMAGE. |
universe@192 | 27 | */ |
universe@192 | 28 | |
universe@251 | 29 | #include "ucx/avl.h" |
universe@251 | 30 | |
universe@243 | 31 | #include <limits.h> |
universe@243 | 32 | |
universe@195 | 33 | #define ptrcast(ptr) ((void*)(ptr)) |
universe@216 | 34 | #define alloc_tree(al) (UcxAVLTree*) almalloc((al), sizeof(UcxAVLTree)) |
universe@216 | 35 | #define alloc_node(al) (UcxAVLNode*) almalloc((al), sizeof(UcxAVLNode)) |
universe@195 | 36 | |
universe@195 | 37 | static void ucx_avl_connect(UcxAVLTree *tree, |
universe@195 | 38 | UcxAVLNode *node, UcxAVLNode *child, intptr_t nullkey) { |
universe@195 | 39 | if (child) { |
universe@195 | 40 | child->parent = node; |
universe@195 | 41 | } |
universe@195 | 42 | // if child is NULL, nullkey decides if left or right pointer is cleared |
universe@195 | 43 | if (tree->cmpfunc( |
universe@195 | 44 | ptrcast(child ? child->key : nullkey), |
universe@195 | 45 | ptrcast(node->key), tree->userdata) > 0) { |
universe@195 | 46 | node->right = child; |
universe@195 | 47 | } else { |
universe@195 | 48 | node->left = child; |
universe@195 | 49 | } |
universe@195 | 50 | size_t lh = node->left ? node->left->height : 0; |
universe@195 | 51 | size_t rh = node->right ? node->right->height : 0; |
universe@195 | 52 | node->height = 1 + (lh > rh ? lh : rh); |
universe@195 | 53 | } |
universe@195 | 54 | |
universe@195 | 55 | #define avlheight(node) ((node) ? (node)->height : 0) |
universe@195 | 56 | |
universe@195 | 57 | static UcxAVLNode* avl_rotright(UcxAVLTree *tree, UcxAVLNode *l0) { |
universe@195 | 58 | UcxAVLNode *p = l0->parent; |
universe@195 | 59 | UcxAVLNode *l1 = l0->left; |
universe@195 | 60 | if (p) { |
universe@195 | 61 | ucx_avl_connect(tree, p, l1, 0); |
universe@195 | 62 | } else { |
universe@195 | 63 | l1->parent = NULL; |
universe@195 | 64 | } |
universe@195 | 65 | ucx_avl_connect(tree, l0, l1->right, l1->key); |
universe@195 | 66 | ucx_avl_connect(tree, l1, l0, 0); |
universe@195 | 67 | return l1; |
universe@195 | 68 | } |
universe@195 | 69 | |
universe@195 | 70 | static UcxAVLNode* avl_rotleft(UcxAVLTree *tree, UcxAVLNode *l0) { |
universe@195 | 71 | UcxAVLNode *p = l0->parent; |
universe@195 | 72 | UcxAVLNode *l1 = l0->right; |
universe@195 | 73 | if (p) { |
universe@195 | 74 | ucx_avl_connect(tree, p, l1, 0); |
universe@195 | 75 | } else { |
universe@195 | 76 | l1->parent = NULL; |
universe@195 | 77 | } |
universe@195 | 78 | ucx_avl_connect(tree, l0, l1->left, l1->key); |
universe@195 | 79 | ucx_avl_connect(tree, l1, l0, 0); |
universe@195 | 80 | return l1; |
universe@195 | 81 | } |
universe@195 | 82 | |
universe@195 | 83 | static void ucx_avl_balance(UcxAVLTree *tree, UcxAVLNode *n) { |
universe@195 | 84 | int lh = avlheight(n->left); |
universe@195 | 85 | int rh = avlheight(n->right); |
universe@195 | 86 | n->height = 1 + (lh > rh ? lh : rh); |
universe@195 | 87 | |
universe@195 | 88 | if (lh - rh == 2) { |
universe@195 | 89 | UcxAVLNode *c = n->left; |
universe@195 | 90 | if (avlheight(c->right) - avlheight(c->left) == 1) { |
universe@195 | 91 | avl_rotleft(tree, c); |
universe@195 | 92 | } |
universe@195 | 93 | n = avl_rotright(tree, n); |
universe@195 | 94 | } else if (rh - lh == 2) { |
universe@195 | 95 | UcxAVLNode *c = n->right; |
universe@195 | 96 | if (avlheight(c->left) - avlheight(c->right) == 1) { |
universe@195 | 97 | avl_rotright(tree, c); |
universe@195 | 98 | } |
universe@195 | 99 | n = avl_rotleft(tree, n); |
universe@195 | 100 | } |
universe@195 | 101 | |
universe@195 | 102 | if (n->parent) { |
universe@195 | 103 | ucx_avl_balance(tree, n->parent); |
universe@195 | 104 | } else { |
universe@195 | 105 | tree->root = n; |
universe@195 | 106 | } |
universe@195 | 107 | } |
universe@195 | 108 | |
universe@194 | 109 | UcxAVLTree *ucx_avl_new(cmp_func cmpfunc) { |
universe@194 | 110 | return ucx_avl_new_a(cmpfunc, ucx_default_allocator()); |
universe@194 | 111 | } |
universe@194 | 112 | |
universe@194 | 113 | UcxAVLTree *ucx_avl_new_a(cmp_func cmpfunc, UcxAllocator *allocator) { |
universe@216 | 114 | UcxAVLTree* tree = alloc_tree(allocator); |
universe@194 | 115 | if (tree) { |
universe@194 | 116 | tree->allocator = allocator; |
universe@194 | 117 | tree->cmpfunc = cmpfunc; |
universe@194 | 118 | tree->root = NULL; |
universe@194 | 119 | tree->userdata = NULL; |
universe@194 | 120 | } |
universe@194 | 121 | |
universe@194 | 122 | return tree; |
universe@194 | 123 | } |
universe@194 | 124 | |
universe@196 | 125 | static void ucx_avl_free_node(UcxAllocator *al, UcxAVLNode *node) { |
universe@196 | 126 | if (node) { |
universe@196 | 127 | ucx_avl_free_node(al, node->left); |
universe@196 | 128 | ucx_avl_free_node(al, node->right); |
universe@196 | 129 | alfree(al, node); |
universe@196 | 130 | } |
universe@196 | 131 | } |
universe@196 | 132 | |
universe@196 | 133 | void ucx_avl_free(UcxAVLTree *tree) { |
universe@196 | 134 | UcxAllocator *al = tree->allocator; |
universe@196 | 135 | ucx_avl_free_node(al, tree->root); |
universe@196 | 136 | alfree(al, tree); |
universe@196 | 137 | } |
universe@196 | 138 | |
universe@287 | 139 | static void ucx_avl_free_content_node(UcxAllocator *al, UcxAVLNode *node, |
universe@287 | 140 | ucx_destructor destr) { |
universe@287 | 141 | if (node) { |
universe@287 | 142 | ucx_avl_free_content_node(al, node->left, destr); |
universe@287 | 143 | ucx_avl_free_content_node(al, node->right, destr); |
universe@287 | 144 | if (destr) { |
universe@287 | 145 | destr(node->value); |
universe@287 | 146 | } else { |
universe@287 | 147 | alfree(al, node->value); |
universe@287 | 148 | } |
universe@287 | 149 | } |
universe@287 | 150 | } |
universe@287 | 151 | |
universe@287 | 152 | void ucx_avl_free_content(UcxAVLTree *tree, ucx_destructor destr) { |
universe@287 | 153 | ucx_avl_free_content_node(tree->allocator, tree->root, destr); |
universe@287 | 154 | } |
universe@287 | 155 | |
universe@205 | 156 | UcxAVLNode *ucx_avl_get_node(UcxAVLTree *tree, intptr_t key) { |
universe@195 | 157 | UcxAVLNode *n = tree->root; |
universe@195 | 158 | int cmpresult; |
universe@195 | 159 | while (n && (cmpresult = tree->cmpfunc( |
universe@195 | 160 | ptrcast(key), ptrcast(n->key), tree->userdata))) { |
universe@195 | 161 | n = cmpresult > 0 ? n->right : n->left; |
universe@195 | 162 | } |
universe@204 | 163 | return n; |
universe@204 | 164 | } |
universe@204 | 165 | |
universe@204 | 166 | void *ucx_avl_get(UcxAVLTree *tree, intptr_t key) { |
universe@205 | 167 | UcxAVLNode *n = ucx_avl_get_node(tree, key); |
universe@195 | 168 | return n ? n->value : NULL; |
universe@194 | 169 | } |
universe@194 | 170 | |
universe@243 | 171 | UcxAVLNode *ucx_avl_find_node(UcxAVLTree *tree, intptr_t key, |
universe@243 | 172 | distance_func dfnc, int mode) { |
universe@243 | 173 | UcxAVLNode *n = tree->root; |
universe@243 | 174 | UcxAVLNode *closest = NULL; |
universe@243 | 175 | |
universe@243 | 176 | intmax_t cmpresult; |
universe@243 | 177 | intmax_t closest_dist; |
universe@243 | 178 | closest_dist = mode == UCX_AVL_FIND_LOWER_BOUNDED ? INTMAX_MIN : INTMAX_MAX; |
universe@243 | 179 | |
universe@243 | 180 | while (n && (cmpresult = dfnc( |
universe@243 | 181 | ptrcast(key), ptrcast(n->key), tree->userdata))) { |
universe@243 | 182 | if (mode == UCX_AVL_FIND_CLOSEST) { |
universe@243 | 183 | intmax_t dist = cmpresult; |
universe@243 | 184 | if (dist < 0) dist *= -1; |
universe@243 | 185 | if (dist < closest_dist) { |
universe@243 | 186 | closest_dist = dist; |
universe@243 | 187 | closest = n; |
universe@243 | 188 | } |
universe@243 | 189 | } else if (mode == UCX_AVL_FIND_LOWER_BOUNDED && cmpresult <= 0) { |
universe@243 | 190 | if (cmpresult > closest_dist) { |
universe@243 | 191 | closest_dist = cmpresult; |
universe@243 | 192 | closest = n; |
universe@243 | 193 | } |
universe@243 | 194 | } else if (mode == UCX_AVL_FIND_UPPER_BOUNDED && cmpresult >= 0) { |
universe@243 | 195 | if (cmpresult < closest_dist) { |
universe@243 | 196 | closest_dist = cmpresult; |
universe@243 | 197 | closest = n; |
universe@243 | 198 | } |
universe@243 | 199 | } |
universe@243 | 200 | n = cmpresult > 0 ? n->right : n->left; |
universe@243 | 201 | } |
universe@243 | 202 | return n ? n : closest; |
universe@243 | 203 | } |
universe@243 | 204 | |
universe@243 | 205 | void *ucx_avl_find(UcxAVLTree *tree, intptr_t key, |
universe@243 | 206 | distance_func dfnc, int mode) { |
universe@243 | 207 | UcxAVLNode *n = ucx_avl_find_node(tree, key, dfnc, mode); |
universe@243 | 208 | return n ? n->value : NULL; |
universe@243 | 209 | } |
universe@243 | 210 | |
universe@204 | 211 | int ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value) { |
universe@204 | 212 | return ucx_avl_put_s(tree, key, value, NULL); |
universe@204 | 213 | } |
universe@204 | 214 | |
universe@204 | 215 | int ucx_avl_put_s(UcxAVLTree *tree, intptr_t key, void *value, |
universe@204 | 216 | void **oldvalue) { |
universe@195 | 217 | if (tree->root) { |
universe@195 | 218 | UcxAVLNode *n = tree->root; |
universe@195 | 219 | int cmpresult; |
universe@197 | 220 | while ((cmpresult = tree->cmpfunc( |
universe@197 | 221 | ptrcast(key), ptrcast(n->key), tree->userdata))) { |
universe@195 | 222 | UcxAVLNode *m = cmpresult > 0 ? n->right : n->left; |
universe@195 | 223 | if (m) { |
universe@195 | 224 | n = m; |
universe@195 | 225 | } else { |
universe@195 | 226 | break; |
universe@195 | 227 | } |
universe@195 | 228 | } |
universe@195 | 229 | |
universe@195 | 230 | if (cmpresult) { |
universe@216 | 231 | UcxAVLNode* e = alloc_node(tree->allocator); |
universe@204 | 232 | if (e) { |
universe@204 | 233 | e->key = key; e->value = value; e->height = 1; |
universe@204 | 234 | e->parent = e->left = e->right = NULL; |
universe@204 | 235 | ucx_avl_connect(tree, n, e, 0); |
universe@204 | 236 | ucx_avl_balance(tree, n); |
universe@204 | 237 | return 0; |
universe@204 | 238 | } else { |
universe@204 | 239 | return 1; |
universe@204 | 240 | } |
universe@195 | 241 | } else { |
universe@204 | 242 | if (oldvalue) { |
universe@204 | 243 | *oldvalue = n->value; |
universe@204 | 244 | } |
universe@195 | 245 | n->value = value; |
universe@204 | 246 | return 0; |
universe@195 | 247 | } |
universe@195 | 248 | } else { |
universe@216 | 249 | tree->root = alloc_node(tree->allocator); |
universe@204 | 250 | if (tree->root) { |
universe@204 | 251 | tree->root->key = key; tree->root->value = value; |
universe@204 | 252 | tree->root->height = 1; |
universe@204 | 253 | tree->root->parent = tree->root->left = tree->root->right = NULL; |
universe@204 | 254 | |
universe@204 | 255 | if (oldvalue) { |
universe@204 | 256 | *oldvalue = NULL; |
universe@204 | 257 | } |
universe@204 | 258 | |
universe@204 | 259 | return 0; |
universe@204 | 260 | } else { |
universe@204 | 261 | return 1; |
universe@204 | 262 | } |
universe@195 | 263 | } |
universe@194 | 264 | } |
universe@194 | 265 | |
universe@204 | 266 | int ucx_avl_remove(UcxAVLTree *tree, intptr_t key) { |
universe@204 | 267 | return ucx_avl_remove_s(tree, key, NULL, NULL); |
universe@204 | 268 | } |
universe@204 | 269 | |
universe@205 | 270 | int ucx_avl_remove_node(UcxAVLTree *tree, UcxAVLNode *node) { |
universe@204 | 271 | return ucx_avl_remove_s(tree, node->key, NULL, NULL); |
universe@204 | 272 | } |
universe@204 | 273 | |
universe@204 | 274 | int ucx_avl_remove_s(UcxAVLTree *tree, intptr_t key, |
universe@204 | 275 | intptr_t *oldkey, void **oldvalue) { |
universe@204 | 276 | |
universe@195 | 277 | UcxAVLNode *n = tree->root; |
universe@195 | 278 | int cmpresult; |
universe@195 | 279 | while (n && (cmpresult = tree->cmpfunc( |
universe@195 | 280 | ptrcast(key), ptrcast(n->key), tree->userdata))) { |
universe@195 | 281 | n = cmpresult > 0 ? n->right : n->left; |
universe@195 | 282 | } |
universe@195 | 283 | if (n) { |
universe@204 | 284 | if (oldkey) { |
universe@204 | 285 | *oldkey = n->key; |
universe@204 | 286 | } |
universe@204 | 287 | if (oldvalue) { |
universe@204 | 288 | *oldvalue = n->value; |
universe@204 | 289 | } |
universe@204 | 290 | |
universe@195 | 291 | UcxAVLNode *p = n->parent; |
universe@195 | 292 | if (n->left && n->right) { |
universe@195 | 293 | UcxAVLNode *s = n->right; |
universe@195 | 294 | while (s->left) { |
universe@195 | 295 | s = s->left; |
universe@195 | 296 | } |
universe@195 | 297 | ucx_avl_connect(tree, s->parent, s->right, s->key); |
universe@195 | 298 | n->key = s->key; n->value = s->value; |
universe@195 | 299 | p = s->parent; |
universe@196 | 300 | alfree(tree->allocator, s); |
universe@195 | 301 | } else { |
universe@195 | 302 | if (p) { |
universe@195 | 303 | ucx_avl_connect(tree, p, n->right ? n->right:n->left, n->key); |
universe@195 | 304 | } else { |
universe@195 | 305 | tree->root = n->right ? n->right : n->left; |
olaf@203 | 306 | if (tree->root) { |
olaf@202 | 307 | tree->root->parent = NULL; |
olaf@202 | 308 | } |
universe@195 | 309 | } |
universe@196 | 310 | alfree(tree->allocator, n); |
universe@195 | 311 | } |
universe@195 | 312 | |
universe@195 | 313 | if (p) { |
universe@195 | 314 | ucx_avl_balance(tree, p); |
universe@195 | 315 | } |
universe@204 | 316 | |
universe@204 | 317 | return 0; |
universe@195 | 318 | } else { |
universe@204 | 319 | return 1; |
universe@195 | 320 | } |
universe@194 | 321 | } |
universe@194 | 322 | |
universe@199 | 323 | static size_t ucx_avl_countn(UcxAVLNode *node) { |
universe@199 | 324 | if (node) { |
universe@199 | 325 | return 1 + ucx_avl_countn(node->left) + ucx_avl_countn(node->right); |
universe@199 | 326 | } else { |
universe@199 | 327 | return 0; |
universe@199 | 328 | } |
universe@199 | 329 | } |
universe@199 | 330 | |
universe@199 | 331 | size_t ucx_avl_count(UcxAVLTree *tree) { |
universe@199 | 332 | return ucx_avl_countn(tree->root); |
universe@199 | 333 | } |
universe@245 | 334 | |
universe@245 | 335 | UcxAVLNode* ucx_avl_pred(UcxAVLNode* node) { |
universe@245 | 336 | if (node->left) { |
universe@245 | 337 | UcxAVLNode* n = node->left; |
universe@245 | 338 | while (n->right) { |
universe@245 | 339 | n = n->right; |
universe@245 | 340 | } |
universe@245 | 341 | return n; |
universe@245 | 342 | } else { |
universe@245 | 343 | UcxAVLNode* n = node; |
universe@245 | 344 | while (n->parent) { |
universe@245 | 345 | if (n->parent->right == n) { |
universe@245 | 346 | return n->parent; |
universe@245 | 347 | } else { |
universe@245 | 348 | n = n->parent; |
universe@245 | 349 | } |
universe@245 | 350 | } |
universe@245 | 351 | return NULL; |
universe@245 | 352 | } |
universe@245 | 353 | } |
universe@245 | 354 | |
universe@245 | 355 | UcxAVLNode* ucx_avl_succ(UcxAVLNode* node) { |
universe@245 | 356 | if (node->right) { |
universe@245 | 357 | UcxAVLNode* n = node->right; |
universe@245 | 358 | while (n->left) { |
universe@245 | 359 | n = n->left; |
universe@245 | 360 | } |
universe@245 | 361 | return n; |
universe@245 | 362 | } else { |
universe@245 | 363 | UcxAVLNode* n = node; |
universe@245 | 364 | while (n->parent) { |
universe@245 | 365 | if (n->parent->left == n) { |
universe@245 | 366 | return n->parent; |
universe@245 | 367 | } else { |
universe@245 | 368 | n = n->parent; |
universe@245 | 369 | } |
universe@245 | 370 | } |
universe@245 | 371 | return NULL; |
universe@245 | 372 | } |
universe@245 | 373 | } |