1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/avl.c Tue Oct 17 16:15:41 2017 +0200
1.3 @@ -0,0 +1,356 @@
1.4 +/*
1.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
1.6 + *
1.7 + * Copyright 2017 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 +UcxAVLNode *ucx_avl_get_node(UcxAVLTree *tree, intptr_t key) {
1.143 + UcxAVLNode *n = tree->root;
1.144 + int cmpresult;
1.145 + while (n && (cmpresult = tree->cmpfunc(
1.146 + ptrcast(key), ptrcast(n->key), tree->userdata))) {
1.147 + n = cmpresult > 0 ? n->right : n->left;
1.148 + }
1.149 + return n;
1.150 +}
1.151 +
1.152 +void *ucx_avl_get(UcxAVLTree *tree, intptr_t key) {
1.153 + UcxAVLNode *n = ucx_avl_get_node(tree, key);
1.154 + return n ? n->value : NULL;
1.155 +}
1.156 +
1.157 +UcxAVLNode *ucx_avl_find_node(UcxAVLTree *tree, intptr_t key,
1.158 + distance_func dfnc, int mode) {
1.159 + UcxAVLNode *n = tree->root;
1.160 + UcxAVLNode *closest = NULL;
1.161 +
1.162 + intmax_t cmpresult;
1.163 + intmax_t closest_dist;
1.164 + closest_dist = mode == UCX_AVL_FIND_LOWER_BOUNDED ? INTMAX_MIN : INTMAX_MAX;
1.165 +
1.166 + while (n && (cmpresult = dfnc(
1.167 + ptrcast(key), ptrcast(n->key), tree->userdata))) {
1.168 + if (mode == UCX_AVL_FIND_CLOSEST) {
1.169 + intmax_t dist = cmpresult;
1.170 + if (dist < 0) dist *= -1;
1.171 + if (dist < closest_dist) {
1.172 + closest_dist = dist;
1.173 + closest = n;
1.174 + }
1.175 + } else if (mode == UCX_AVL_FIND_LOWER_BOUNDED && cmpresult <= 0) {
1.176 + if (cmpresult > closest_dist) {
1.177 + closest_dist = cmpresult;
1.178 + closest = n;
1.179 + }
1.180 + } else if (mode == UCX_AVL_FIND_UPPER_BOUNDED && cmpresult >= 0) {
1.181 + if (cmpresult < closest_dist) {
1.182 + closest_dist = cmpresult;
1.183 + closest = n;
1.184 + }
1.185 + }
1.186 + n = cmpresult > 0 ? n->right : n->left;
1.187 + }
1.188 + return n ? n : closest;
1.189 +}
1.190 +
1.191 +void *ucx_avl_find(UcxAVLTree *tree, intptr_t key,
1.192 + distance_func dfnc, int mode) {
1.193 + UcxAVLNode *n = ucx_avl_find_node(tree, key, dfnc, mode);
1.194 + return n ? n->value : NULL;
1.195 +}
1.196 +
1.197 +int ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value) {
1.198 + return ucx_avl_put_s(tree, key, value, NULL);
1.199 +}
1.200 +
1.201 +int ucx_avl_put_s(UcxAVLTree *tree, intptr_t key, void *value,
1.202 + void **oldvalue) {
1.203 + if (tree->root) {
1.204 + UcxAVLNode *n = tree->root;
1.205 + int cmpresult;
1.206 + while ((cmpresult = tree->cmpfunc(
1.207 + ptrcast(key), ptrcast(n->key), tree->userdata))) {
1.208 + UcxAVLNode *m = cmpresult > 0 ? n->right : n->left;
1.209 + if (m) {
1.210 + n = m;
1.211 + } else {
1.212 + break;
1.213 + }
1.214 + }
1.215 +
1.216 + if (cmpresult) {
1.217 + UcxAVLNode* e = alloc_node(tree->allocator);
1.218 + if (e) {
1.219 + e->key = key; e->value = value; e->height = 1;
1.220 + e->parent = e->left = e->right = NULL;
1.221 + ucx_avl_connect(tree, n, e, 0);
1.222 + ucx_avl_balance(tree, n);
1.223 + return 0;
1.224 + } else {
1.225 + return 1;
1.226 + }
1.227 + } else {
1.228 + if (oldvalue) {
1.229 + *oldvalue = n->value;
1.230 + }
1.231 + n->value = value;
1.232 + return 0;
1.233 + }
1.234 + } else {
1.235 + tree->root = alloc_node(tree->allocator);
1.236 + if (tree->root) {
1.237 + tree->root->key = key; tree->root->value = value;
1.238 + tree->root->height = 1;
1.239 + tree->root->parent = tree->root->left = tree->root->right = NULL;
1.240 +
1.241 + if (oldvalue) {
1.242 + *oldvalue = NULL;
1.243 + }
1.244 +
1.245 + return 0;
1.246 + } else {
1.247 + return 1;
1.248 + }
1.249 + }
1.250 +}
1.251 +
1.252 +int ucx_avl_remove(UcxAVLTree *tree, intptr_t key) {
1.253 + return ucx_avl_remove_s(tree, key, NULL, NULL);
1.254 +}
1.255 +
1.256 +int ucx_avl_remove_node(UcxAVLTree *tree, UcxAVLNode *node) {
1.257 + return ucx_avl_remove_s(tree, node->key, NULL, NULL);
1.258 +}
1.259 +
1.260 +int ucx_avl_remove_s(UcxAVLTree *tree, intptr_t key,
1.261 + intptr_t *oldkey, void **oldvalue) {
1.262 +
1.263 + UcxAVLNode *n = tree->root;
1.264 + int cmpresult;
1.265 + while (n && (cmpresult = tree->cmpfunc(
1.266 + ptrcast(key), ptrcast(n->key), tree->userdata))) {
1.267 + n = cmpresult > 0 ? n->right : n->left;
1.268 + }
1.269 + if (n) {
1.270 + if (oldkey) {
1.271 + *oldkey = n->key;
1.272 + }
1.273 + if (oldvalue) {
1.274 + *oldvalue = n->value;
1.275 + }
1.276 +
1.277 + UcxAVLNode *p = n->parent;
1.278 + if (n->left && n->right) {
1.279 + UcxAVLNode *s = n->right;
1.280 + while (s->left) {
1.281 + s = s->left;
1.282 + }
1.283 + ucx_avl_connect(tree, s->parent, s->right, s->key);
1.284 + n->key = s->key; n->value = s->value;
1.285 + p = s->parent;
1.286 + alfree(tree->allocator, s);
1.287 + } else {
1.288 + if (p) {
1.289 + ucx_avl_connect(tree, p, n->right ? n->right:n->left, n->key);
1.290 + } else {
1.291 + tree->root = n->right ? n->right : n->left;
1.292 + if (tree->root) {
1.293 + tree->root->parent = NULL;
1.294 + }
1.295 + }
1.296 + alfree(tree->allocator, n);
1.297 + }
1.298 +
1.299 + if (p) {
1.300 + ucx_avl_balance(tree, p);
1.301 + }
1.302 +
1.303 + return 0;
1.304 + } else {
1.305 + return 1;
1.306 + }
1.307 +}
1.308 +
1.309 +static size_t ucx_avl_countn(UcxAVLNode *node) {
1.310 + if (node) {
1.311 + return 1 + ucx_avl_countn(node->left) + ucx_avl_countn(node->right);
1.312 + } else {
1.313 + return 0;
1.314 + }
1.315 +}
1.316 +
1.317 +size_t ucx_avl_count(UcxAVLTree *tree) {
1.318 + return ucx_avl_countn(tree->root);
1.319 +}
1.320 +
1.321 +UcxAVLNode* ucx_avl_pred(UcxAVLNode* node) {
1.322 + if (node->left) {
1.323 + UcxAVLNode* n = node->left;
1.324 + while (n->right) {
1.325 + n = n->right;
1.326 + }
1.327 + return n;
1.328 + } else {
1.329 + UcxAVLNode* n = node;
1.330 + while (n->parent) {
1.331 + if (n->parent->right == n) {
1.332 + return n->parent;
1.333 + } else {
1.334 + n = n->parent;
1.335 + }
1.336 + }
1.337 + return NULL;
1.338 + }
1.339 +}
1.340 +
1.341 +UcxAVLNode* ucx_avl_succ(UcxAVLNode* node) {
1.342 + if (node->right) {
1.343 + UcxAVLNode* n = node->right;
1.344 + while (n->left) {
1.345 + n = n->left;
1.346 + }
1.347 + return n;
1.348 + } else {
1.349 + UcxAVLNode* n = node;
1.350 + while (n->parent) {
1.351 + if (n->parent->left == n) {
1.352 + return n->parent;
1.353 + } else {
1.354 + n = n->parent;
1.355 + }
1.356 + }
1.357 + return NULL;
1.358 + }
1.359 +}
