Fri, 26 Feb 2016 16:00:18 +0100
added casts for mallocs in AVL implementation (to satisfy c++ compiler)
universe@192 | 1 | /* |
universe@192 | 2 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. |
universe@192 | 3 | * |
universe@192 | 4 | * Copyright 2015 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@192 | 29 | #include "avl.h" |
universe@192 | 30 | |
universe@195 | 31 | #define ptrcast(ptr) ((void*)(ptr)) |
universe@216 | 32 | #define alloc_tree(al) (UcxAVLTree*) almalloc((al), sizeof(UcxAVLTree)) |
universe@216 | 33 | #define alloc_node(al) (UcxAVLNode*) almalloc((al), sizeof(UcxAVLNode)) |
universe@195 | 34 | |
universe@195 | 35 | static void ucx_avl_connect(UcxAVLTree *tree, |
universe@195 | 36 | UcxAVLNode *node, UcxAVLNode *child, intptr_t nullkey) { |
universe@195 | 37 | if (child) { |
universe@195 | 38 | child->parent = node; |
universe@195 | 39 | } |
universe@195 | 40 | // if child is NULL, nullkey decides if left or right pointer is cleared |
universe@195 | 41 | if (tree->cmpfunc( |
universe@195 | 42 | ptrcast(child ? child->key : nullkey), |
universe@195 | 43 | ptrcast(node->key), tree->userdata) > 0) { |
universe@195 | 44 | node->right = child; |
universe@195 | 45 | } else { |
universe@195 | 46 | node->left = child; |
universe@195 | 47 | } |
universe@195 | 48 | size_t lh = node->left ? node->left->height : 0; |
universe@195 | 49 | size_t rh = node->right ? node->right->height : 0; |
universe@195 | 50 | node->height = 1 + (lh > rh ? lh : rh); |
universe@195 | 51 | } |
universe@195 | 52 | |
universe@195 | 53 | #define avlheight(node) ((node) ? (node)->height : 0) |
universe@195 | 54 | |
universe@195 | 55 | static UcxAVLNode* avl_rotright(UcxAVLTree *tree, UcxAVLNode *l0) { |
universe@195 | 56 | UcxAVLNode *p = l0->parent; |
universe@195 | 57 | UcxAVLNode *l1 = l0->left; |
universe@195 | 58 | if (p) { |
universe@195 | 59 | ucx_avl_connect(tree, p, l1, 0); |
universe@195 | 60 | } else { |
universe@195 | 61 | l1->parent = NULL; |
universe@195 | 62 | } |
universe@195 | 63 | ucx_avl_connect(tree, l0, l1->right, l1->key); |
universe@195 | 64 | ucx_avl_connect(tree, l1, l0, 0); |
universe@195 | 65 | return l1; |
universe@195 | 66 | } |
universe@195 | 67 | |
universe@195 | 68 | static UcxAVLNode* avl_rotleft(UcxAVLTree *tree, UcxAVLNode *l0) { |
universe@195 | 69 | UcxAVLNode *p = l0->parent; |
universe@195 | 70 | UcxAVLNode *l1 = l0->right; |
universe@195 | 71 | if (p) { |
universe@195 | 72 | ucx_avl_connect(tree, p, l1, 0); |
universe@195 | 73 | } else { |
universe@195 | 74 | l1->parent = NULL; |
universe@195 | 75 | } |
universe@195 | 76 | ucx_avl_connect(tree, l0, l1->left, l1->key); |
universe@195 | 77 | ucx_avl_connect(tree, l1, l0, 0); |
universe@195 | 78 | return l1; |
universe@195 | 79 | } |
universe@195 | 80 | |
universe@195 | 81 | static void ucx_avl_balance(UcxAVLTree *tree, UcxAVLNode *n) { |
universe@195 | 82 | int lh = avlheight(n->left); |
universe@195 | 83 | int rh = avlheight(n->right); |
universe@195 | 84 | n->height = 1 + (lh > rh ? lh : rh); |
universe@195 | 85 | |
universe@195 | 86 | if (lh - rh == 2) { |
universe@195 | 87 | UcxAVLNode *c = n->left; |
universe@195 | 88 | if (avlheight(c->right) - avlheight(c->left) == 1) { |
universe@195 | 89 | avl_rotleft(tree, c); |
universe@195 | 90 | } |
universe@195 | 91 | n = avl_rotright(tree, n); |
universe@195 | 92 | } else if (rh - lh == 2) { |
universe@195 | 93 | UcxAVLNode *c = n->right; |
universe@195 | 94 | if (avlheight(c->left) - avlheight(c->right) == 1) { |
universe@195 | 95 | avl_rotright(tree, c); |
universe@195 | 96 | } |
universe@195 | 97 | n = avl_rotleft(tree, n); |
universe@195 | 98 | } |
universe@195 | 99 | |
universe@195 | 100 | if (n->parent) { |
universe@195 | 101 | ucx_avl_balance(tree, n->parent); |
universe@195 | 102 | } else { |
universe@195 | 103 | tree->root = n; |
universe@195 | 104 | } |
universe@195 | 105 | } |
universe@195 | 106 | |
universe@194 | 107 | UcxAVLTree *ucx_avl_new(cmp_func cmpfunc) { |
universe@194 | 108 | return ucx_avl_new_a(cmpfunc, ucx_default_allocator()); |
universe@194 | 109 | } |
universe@194 | 110 | |
universe@194 | 111 | UcxAVLTree *ucx_avl_new_a(cmp_func cmpfunc, UcxAllocator *allocator) { |
universe@216 | 112 | UcxAVLTree* tree = alloc_tree(allocator); |
universe@194 | 113 | if (tree) { |
universe@194 | 114 | tree->allocator = allocator; |
universe@194 | 115 | tree->cmpfunc = cmpfunc; |
universe@194 | 116 | tree->root = NULL; |
universe@194 | 117 | tree->userdata = NULL; |
universe@194 | 118 | } |
universe@194 | 119 | |
universe@194 | 120 | return tree; |
universe@194 | 121 | } |
universe@194 | 122 | |
universe@196 | 123 | static void ucx_avl_free_node(UcxAllocator *al, UcxAVLNode *node) { |
universe@196 | 124 | if (node) { |
universe@196 | 125 | ucx_avl_free_node(al, node->left); |
universe@196 | 126 | ucx_avl_free_node(al, node->right); |
universe@196 | 127 | alfree(al, node); |
universe@196 | 128 | } |
universe@196 | 129 | } |
universe@196 | 130 | |
universe@196 | 131 | void ucx_avl_free(UcxAVLTree *tree) { |
universe@196 | 132 | UcxAllocator *al = tree->allocator; |
universe@196 | 133 | ucx_avl_free_node(al, tree->root); |
universe@196 | 134 | alfree(al, tree); |
universe@196 | 135 | } |
universe@196 | 136 | |
universe@205 | 137 | UcxAVLNode *ucx_avl_get_node(UcxAVLTree *tree, intptr_t key) { |
universe@195 | 138 | UcxAVLNode *n = tree->root; |
universe@195 | 139 | int cmpresult; |
universe@195 | 140 | while (n && (cmpresult = tree->cmpfunc( |
universe@195 | 141 | ptrcast(key), ptrcast(n->key), tree->userdata))) { |
universe@195 | 142 | n = cmpresult > 0 ? n->right : n->left; |
universe@195 | 143 | } |
universe@204 | 144 | return n; |
universe@204 | 145 | } |
universe@204 | 146 | |
universe@204 | 147 | void *ucx_avl_get(UcxAVLTree *tree, intptr_t key) { |
universe@205 | 148 | UcxAVLNode *n = ucx_avl_get_node(tree, key); |
universe@195 | 149 | return n ? n->value : NULL; |
universe@194 | 150 | } |
universe@194 | 151 | |
universe@204 | 152 | int ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value) { |
universe@204 | 153 | return ucx_avl_put_s(tree, key, value, NULL); |
universe@204 | 154 | } |
universe@204 | 155 | |
universe@204 | 156 | int ucx_avl_put_s(UcxAVLTree *tree, intptr_t key, void *value, |
universe@204 | 157 | void **oldvalue) { |
universe@195 | 158 | if (tree->root) { |
universe@195 | 159 | UcxAVLNode *n = tree->root; |
universe@195 | 160 | int cmpresult; |
universe@197 | 161 | while ((cmpresult = tree->cmpfunc( |
universe@197 | 162 | ptrcast(key), ptrcast(n->key), tree->userdata))) { |
universe@195 | 163 | UcxAVLNode *m = cmpresult > 0 ? n->right : n->left; |
universe@195 | 164 | if (m) { |
universe@195 | 165 | n = m; |
universe@195 | 166 | } else { |
universe@195 | 167 | break; |
universe@195 | 168 | } |
universe@195 | 169 | } |
universe@195 | 170 | |
universe@195 | 171 | if (cmpresult) { |
universe@216 | 172 | UcxAVLNode* e = alloc_node(tree->allocator); |
universe@204 | 173 | if (e) { |
universe@204 | 174 | e->key = key; e->value = value; e->height = 1; |
universe@204 | 175 | e->parent = e->left = e->right = NULL; |
universe@204 | 176 | ucx_avl_connect(tree, n, e, 0); |
universe@204 | 177 | ucx_avl_balance(tree, n); |
universe@204 | 178 | return 0; |
universe@204 | 179 | } else { |
universe@204 | 180 | return 1; |
universe@204 | 181 | } |
universe@195 | 182 | } else { |
universe@204 | 183 | if (oldvalue) { |
universe@204 | 184 | *oldvalue = n->value; |
universe@204 | 185 | } |
universe@195 | 186 | n->value = value; |
universe@204 | 187 | return 0; |
universe@195 | 188 | } |
universe@195 | 189 | } else { |
universe@216 | 190 | tree->root = alloc_node(tree->allocator); |
universe@204 | 191 | if (tree->root) { |
universe@204 | 192 | tree->root->key = key; tree->root->value = value; |
universe@204 | 193 | tree->root->height = 1; |
universe@204 | 194 | tree->root->parent = tree->root->left = tree->root->right = NULL; |
universe@204 | 195 | |
universe@204 | 196 | if (oldvalue) { |
universe@204 | 197 | *oldvalue = NULL; |
universe@204 | 198 | } |
universe@204 | 199 | |
universe@204 | 200 | return 0; |
universe@204 | 201 | } else { |
universe@204 | 202 | return 1; |
universe@204 | 203 | } |
universe@195 | 204 | } |
universe@194 | 205 | } |
universe@194 | 206 | |
universe@204 | 207 | int ucx_avl_remove(UcxAVLTree *tree, intptr_t key) { |
universe@204 | 208 | return ucx_avl_remove_s(tree, key, NULL, NULL); |
universe@204 | 209 | } |
universe@204 | 210 | |
universe@205 | 211 | int ucx_avl_remove_node(UcxAVLTree *tree, UcxAVLNode *node) { |
universe@204 | 212 | return ucx_avl_remove_s(tree, node->key, NULL, NULL); |
universe@204 | 213 | } |
universe@204 | 214 | |
universe@204 | 215 | int ucx_avl_remove_s(UcxAVLTree *tree, intptr_t key, |
universe@204 | 216 | intptr_t *oldkey, void **oldvalue) { |
universe@204 | 217 | |
universe@195 | 218 | UcxAVLNode *n = tree->root; |
universe@195 | 219 | int cmpresult; |
universe@195 | 220 | while (n && (cmpresult = tree->cmpfunc( |
universe@195 | 221 | ptrcast(key), ptrcast(n->key), tree->userdata))) { |
universe@195 | 222 | n = cmpresult > 0 ? n->right : n->left; |
universe@195 | 223 | } |
universe@195 | 224 | if (n) { |
universe@204 | 225 | if (oldkey) { |
universe@204 | 226 | *oldkey = n->key; |
universe@204 | 227 | } |
universe@204 | 228 | if (oldvalue) { |
universe@204 | 229 | *oldvalue = n->value; |
universe@204 | 230 | } |
universe@204 | 231 | |
universe@195 | 232 | UcxAVLNode *p = n->parent; |
universe@195 | 233 | if (n->left && n->right) { |
universe@195 | 234 | UcxAVLNode *s = n->right; |
universe@195 | 235 | while (s->left) { |
universe@195 | 236 | s = s->left; |
universe@195 | 237 | } |
universe@195 | 238 | ucx_avl_connect(tree, s->parent, s->right, s->key); |
universe@195 | 239 | n->key = s->key; n->value = s->value; |
universe@195 | 240 | p = s->parent; |
universe@196 | 241 | alfree(tree->allocator, s); |
universe@195 | 242 | } else { |
universe@195 | 243 | if (p) { |
universe@195 | 244 | ucx_avl_connect(tree, p, n->right ? n->right:n->left, n->key); |
universe@195 | 245 | } else { |
universe@195 | 246 | tree->root = n->right ? n->right : n->left; |
olaf@203 | 247 | if (tree->root) { |
olaf@202 | 248 | tree->root->parent = NULL; |
olaf@202 | 249 | } |
universe@195 | 250 | } |
universe@196 | 251 | alfree(tree->allocator, n); |
universe@195 | 252 | } |
universe@195 | 253 | |
universe@195 | 254 | if (p) { |
universe@195 | 255 | ucx_avl_balance(tree, p); |
universe@195 | 256 | } |
universe@204 | 257 | |
universe@204 | 258 | return 0; |
universe@195 | 259 | } else { |
universe@204 | 260 | return 1; |
universe@195 | 261 | } |
universe@194 | 262 | } |
universe@194 | 263 | |
universe@199 | 264 | static size_t ucx_avl_countn(UcxAVLNode *node) { |
universe@199 | 265 | if (node) { |
universe@199 | 266 | return 1 + ucx_avl_countn(node->left) + ucx_avl_countn(node->right); |
universe@199 | 267 | } else { |
universe@199 | 268 | return 0; |
universe@199 | 269 | } |
universe@199 | 270 | } |
universe@199 | 271 | |
universe@199 | 272 | size_t ucx_avl_count(UcxAVLTree *tree) { |
universe@199 | 273 | return ucx_avl_countn(tree->root); |
universe@199 | 274 | } |