1.1 --- a/src/avl.c Mon Dec 30 09:54:10 2019 +0100
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,373 +0,0 @@
1.4 -/*
1.5 - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
1.6 - *
1.7 - * Copyright 2017 Mike Becker, Olaf Wintermann All rights reserved.
1.8 - *
1.9 - * Redistribution and use in source and binary forms, with or without
1.10 - * modification, are permitted provided that the following conditions are met:
1.11 - *
1.12 - * 1. Redistributions of source code must retain the above copyright
1.13 - * notice, this list of conditions and the following disclaimer.
1.14 - *
1.15 - * 2. Redistributions in binary form must reproduce the above copyright
1.16 - * notice, this list of conditions and the following disclaimer in the
1.17 - * documentation and/or other materials provided with the distribution.
1.18 - *
1.19 - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
1.20 - * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
1.21 - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
1.22 - * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
1.23 - * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
1.24 - * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
1.25 - * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
1.26 - * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
1.27 - * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
1.28 - * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
1.29 - * POSSIBILITY OF SUCH DAMAGE.
1.30 - */
1.31 -
1.32 -#include "ucx/avl.h"
1.33 -
1.34 -#include <limits.h>
1.35 -
1.36 -#define ptrcast(ptr) ((void*)(ptr))
1.37 -#define alloc_tree(al) (UcxAVLTree*) almalloc((al), sizeof(UcxAVLTree))
1.38 -#define alloc_node(al) (UcxAVLNode*) almalloc((al), sizeof(UcxAVLNode))
1.39 -
1.40 -static void ucx_avl_connect(UcxAVLTree *tree,
1.41 - UcxAVLNode *node, UcxAVLNode *child, intptr_t nullkey) {
1.42 - if (child) {
1.43 - child->parent = node;
1.44 - }
1.45 - // if child is NULL, nullkey decides if left or right pointer is cleared
1.46 - if (tree->cmpfunc(
1.47 - ptrcast(child ? child->key : nullkey),
1.48 - ptrcast(node->key), tree->userdata) > 0) {
1.49 - node->right = child;
1.50 - } else {
1.51 - node->left = child;
1.52 - }
1.53 - size_t lh = node->left ? node->left->height : 0;
1.54 - size_t rh = node->right ? node->right->height : 0;
1.55 - node->height = 1 + (lh > rh ? lh : rh);
1.56 -}
1.57 -
1.58 -#define avlheight(node) ((node) ? (node)->height : 0)
1.59 -
1.60 -static UcxAVLNode* avl_rotright(UcxAVLTree *tree, UcxAVLNode *l0) {
1.61 - UcxAVLNode *p = l0->parent;
1.62 - UcxAVLNode *l1 = l0->left;
1.63 - if (p) {
1.64 - ucx_avl_connect(tree, p, l1, 0);
1.65 - } else {
1.66 - l1->parent = NULL;
1.67 - }
1.68 - ucx_avl_connect(tree, l0, l1->right, l1->key);
1.69 - ucx_avl_connect(tree, l1, l0, 0);
1.70 - return l1;
1.71 -}
1.72 -
1.73 -static UcxAVLNode* avl_rotleft(UcxAVLTree *tree, UcxAVLNode *l0) {
1.74 - UcxAVLNode *p = l0->parent;
1.75 - UcxAVLNode *l1 = l0->right;
1.76 - if (p) {
1.77 - ucx_avl_connect(tree, p, l1, 0);
1.78 - } else {
1.79 - l1->parent = NULL;
1.80 - }
1.81 - ucx_avl_connect(tree, l0, l1->left, l1->key);
1.82 - ucx_avl_connect(tree, l1, l0, 0);
1.83 - return l1;
1.84 -}
1.85 -
1.86 -static void ucx_avl_balance(UcxAVLTree *tree, UcxAVLNode *n) {
1.87 - int lh = avlheight(n->left);
1.88 - int rh = avlheight(n->right);
1.89 - n->height = 1 + (lh > rh ? lh : rh);
1.90 -
1.91 - if (lh - rh == 2) {
1.92 - UcxAVLNode *c = n->left;
1.93 - if (avlheight(c->right) - avlheight(c->left) == 1) {
1.94 - avl_rotleft(tree, c);
1.95 - }
1.96 - n = avl_rotright(tree, n);
1.97 - } else if (rh - lh == 2) {
1.98 - UcxAVLNode *c = n->right;
1.99 - if (avlheight(c->left) - avlheight(c->right) == 1) {
1.100 - avl_rotright(tree, c);
1.101 - }
1.102 - n = avl_rotleft(tree, n);
1.103 - }
1.104 -
1.105 - if (n->parent) {
1.106 - ucx_avl_balance(tree, n->parent);
1.107 - } else {
1.108 - tree->root = n;
1.109 - }
1.110 -}
1.111 -
1.112 -UcxAVLTree *ucx_avl_new(cmp_func cmpfunc) {
1.113 - return ucx_avl_new_a(cmpfunc, ucx_default_allocator());
1.114 -}
1.115 -
1.116 -UcxAVLTree *ucx_avl_new_a(cmp_func cmpfunc, UcxAllocator *allocator) {
1.117 - UcxAVLTree* tree = alloc_tree(allocator);
1.118 - if (tree) {
1.119 - tree->allocator = allocator;
1.120 - tree->cmpfunc = cmpfunc;
1.121 - tree->root = NULL;
1.122 - tree->userdata = NULL;
1.123 - }
1.124 -
1.125 - return tree;
1.126 -}
1.127 -
1.128 -static void ucx_avl_free_node(UcxAllocator *al, UcxAVLNode *node) {
1.129 - if (node) {
1.130 - ucx_avl_free_node(al, node->left);
1.131 - ucx_avl_free_node(al, node->right);
1.132 - alfree(al, node);
1.133 - }
1.134 -}
1.135 -
1.136 -void ucx_avl_free(UcxAVLTree *tree) {
1.137 - UcxAllocator *al = tree->allocator;
1.138 - ucx_avl_free_node(al, tree->root);
1.139 - alfree(al, tree);
1.140 -}
1.141 -
1.142 -static void ucx_avl_free_content_node(UcxAllocator *al, UcxAVLNode *node,
1.143 - ucx_destructor destr) {
1.144 - if (node) {
1.145 - ucx_avl_free_content_node(al, node->left, destr);
1.146 - ucx_avl_free_content_node(al, node->right, destr);
1.147 - if (destr) {
1.148 - destr(node->value);
1.149 - } else {
1.150 - alfree(al, node->value);
1.151 - }
1.152 - }
1.153 -}
1.154 -
1.155 -void ucx_avl_free_content(UcxAVLTree *tree, ucx_destructor destr) {
1.156 - ucx_avl_free_content_node(tree->allocator, tree->root, destr);
1.157 -}
1.158 -
1.159 -UcxAVLNode *ucx_avl_get_node(UcxAVLTree *tree, intptr_t key) {
1.160 - UcxAVLNode *n = tree->root;
1.161 - int cmpresult;
1.162 - while (n && (cmpresult = tree->cmpfunc(
1.163 - ptrcast(key), ptrcast(n->key), tree->userdata))) {
1.164 - n = cmpresult > 0 ? n->right : n->left;
1.165 - }
1.166 - return n;
1.167 -}
1.168 -
1.169 -void *ucx_avl_get(UcxAVLTree *tree, intptr_t key) {
1.170 - UcxAVLNode *n = ucx_avl_get_node(tree, key);
1.171 - return n ? n->value : NULL;
1.172 -}
1.173 -
1.174 -UcxAVLNode *ucx_avl_find_node(UcxAVLTree *tree, intptr_t key,
1.175 - distance_func dfnc, int mode) {
1.176 - UcxAVLNode *n = tree->root;
1.177 - UcxAVLNode *closest = NULL;
1.178 -
1.179 - intmax_t cmpresult;
1.180 - intmax_t closest_dist;
1.181 - closest_dist = mode == UCX_AVL_FIND_LOWER_BOUNDED ? INTMAX_MIN : INTMAX_MAX;
1.182 -
1.183 - while (n && (cmpresult = dfnc(
1.184 - ptrcast(key), ptrcast(n->key), tree->userdata))) {
1.185 - if (mode == UCX_AVL_FIND_CLOSEST) {
1.186 - intmax_t dist = cmpresult;
1.187 - if (dist < 0) dist *= -1;
1.188 - if (dist < closest_dist) {
1.189 - closest_dist = dist;
1.190 - closest = n;
1.191 - }
1.192 - } else if (mode == UCX_AVL_FIND_LOWER_BOUNDED && cmpresult <= 0) {
1.193 - if (cmpresult > closest_dist) {
1.194 - closest_dist = cmpresult;
1.195 - closest = n;
1.196 - }
1.197 - } else if (mode == UCX_AVL_FIND_UPPER_BOUNDED && cmpresult >= 0) {
1.198 - if (cmpresult < closest_dist) {
1.199 - closest_dist = cmpresult;
1.200 - closest = n;
1.201 - }
1.202 - }
1.203 - n = cmpresult > 0 ? n->right : n->left;
1.204 - }
1.205 - return n ? n : closest;
1.206 -}
1.207 -
1.208 -void *ucx_avl_find(UcxAVLTree *tree, intptr_t key,
1.209 - distance_func dfnc, int mode) {
1.210 - UcxAVLNode *n = ucx_avl_find_node(tree, key, dfnc, mode);
1.211 - return n ? n->value : NULL;
1.212 -}
1.213 -
1.214 -int ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value) {
1.215 - return ucx_avl_put_s(tree, key, value, NULL);
1.216 -}
1.217 -
1.218 -int ucx_avl_put_s(UcxAVLTree *tree, intptr_t key, void *value,
1.219 - void **oldvalue) {
1.220 - if (tree->root) {
1.221 - UcxAVLNode *n = tree->root;
1.222 - int cmpresult;
1.223 - while ((cmpresult = tree->cmpfunc(
1.224 - ptrcast(key), ptrcast(n->key), tree->userdata))) {
1.225 - UcxAVLNode *m = cmpresult > 0 ? n->right : n->left;
1.226 - if (m) {
1.227 - n = m;
1.228 - } else {
1.229 - break;
1.230 - }
1.231 - }
1.232 -
1.233 - if (cmpresult) {
1.234 - UcxAVLNode* e = alloc_node(tree->allocator);
1.235 - if (e) {
1.236 - e->key = key; e->value = value; e->height = 1;
1.237 - e->parent = e->left = e->right = NULL;
1.238 - ucx_avl_connect(tree, n, e, 0);
1.239 - ucx_avl_balance(tree, n);
1.240 - return 0;
1.241 - } else {
1.242 - return 1;
1.243 - }
1.244 - } else {
1.245 - if (oldvalue) {
1.246 - *oldvalue = n->value;
1.247 - }
1.248 - n->value = value;
1.249 - return 0;
1.250 - }
1.251 - } else {
1.252 - tree->root = alloc_node(tree->allocator);
1.253 - if (tree->root) {
1.254 - tree->root->key = key; tree->root->value = value;
1.255 - tree->root->height = 1;
1.256 - tree->root->parent = tree->root->left = tree->root->right = NULL;
1.257 -
1.258 - if (oldvalue) {
1.259 - *oldvalue = NULL;
1.260 - }
1.261 -
1.262 - return 0;
1.263 - } else {
1.264 - return 1;
1.265 - }
1.266 - }
1.267 -}
1.268 -
1.269 -int ucx_avl_remove(UcxAVLTree *tree, intptr_t key) {
1.270 - return ucx_avl_remove_s(tree, key, NULL, NULL);
1.271 -}
1.272 -
1.273 -int ucx_avl_remove_node(UcxAVLTree *tree, UcxAVLNode *node) {
1.274 - return ucx_avl_remove_s(tree, node->key, NULL, NULL);
1.275 -}
1.276 -
1.277 -int ucx_avl_remove_s(UcxAVLTree *tree, intptr_t key,
1.278 - intptr_t *oldkey, void **oldvalue) {
1.279 -
1.280 - UcxAVLNode *n = tree->root;
1.281 - int cmpresult;
1.282 - while (n && (cmpresult = tree->cmpfunc(
1.283 - ptrcast(key), ptrcast(n->key), tree->userdata))) {
1.284 - n = cmpresult > 0 ? n->right : n->left;
1.285 - }
1.286 - if (n) {
1.287 - if (oldkey) {
1.288 - *oldkey = n->key;
1.289 - }
1.290 - if (oldvalue) {
1.291 - *oldvalue = n->value;
1.292 - }
1.293 -
1.294 - UcxAVLNode *p = n->parent;
1.295 - if (n->left && n->right) {
1.296 - UcxAVLNode *s = n->right;
1.297 - while (s->left) {
1.298 - s = s->left;
1.299 - }
1.300 - ucx_avl_connect(tree, s->parent, s->right, s->key);
1.301 - n->key = s->key; n->value = s->value;
1.302 - p = s->parent;
1.303 - alfree(tree->allocator, s);
1.304 - } else {
1.305 - if (p) {
1.306 - ucx_avl_connect(tree, p, n->right ? n->right:n->left, n->key);
1.307 - } else {
1.308 - tree->root = n->right ? n->right : n->left;
1.309 - if (tree->root) {
1.310 - tree->root->parent = NULL;
1.311 - }
1.312 - }
1.313 - alfree(tree->allocator, n);
1.314 - }
1.315 -
1.316 - if (p) {
1.317 - ucx_avl_balance(tree, p);
1.318 - }
1.319 -
1.320 - return 0;
1.321 - } else {
1.322 - return 1;
1.323 - }
1.324 -}
1.325 -
1.326 -static size_t ucx_avl_countn(UcxAVLNode *node) {
1.327 - if (node) {
1.328 - return 1 + ucx_avl_countn(node->left) + ucx_avl_countn(node->right);
1.329 - } else {
1.330 - return 0;
1.331 - }
1.332 -}
1.333 -
1.334 -size_t ucx_avl_count(UcxAVLTree *tree) {
1.335 - return ucx_avl_countn(tree->root);
1.336 -}
1.337 -
1.338 -UcxAVLNode* ucx_avl_pred(UcxAVLNode* node) {
1.339 - if (node->left) {
1.340 - UcxAVLNode* n = node->left;
1.341 - while (n->right) {
1.342 - n = n->right;
1.343 - }
1.344 - return n;
1.345 - } else {
1.346 - UcxAVLNode* n = node;
1.347 - while (n->parent) {
1.348 - if (n->parent->right == n) {
1.349 - return n->parent;
1.350 - } else {
1.351 - n = n->parent;
1.352 - }
1.353 - }
1.354 - return NULL;
1.355 - }
1.356 -}
1.357 -
1.358 -UcxAVLNode* ucx_avl_succ(UcxAVLNode* node) {
1.359 - if (node->right) {
1.360 - UcxAVLNode* n = node->right;
1.361 - while (n->left) {
1.362 - n = n->left;
1.363 - }
1.364 - return n;
1.365 - } else {
1.366 - UcxAVLNode* n = node;
1.367 - while (n->parent) {
1.368 - if (n->parent->left == n) {
1.369 - return n->parent;
1.370 - } else {
1.371 - n = n->parent;
1.372 - }
1.373 - }
1.374 - return NULL;
1.375 - }
1.376 -}
