Mon, 18 May 2015 18:42:45 +0200
fuck -Wparentheses
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@195 | 32 | |
universe@195 | 33 | static void ucx_avl_connect(UcxAVLTree *tree, |
universe@195 | 34 | UcxAVLNode *node, UcxAVLNode *child, intptr_t nullkey) { |
universe@195 | 35 | if (child) { |
universe@195 | 36 | child->parent = node; |
universe@195 | 37 | } |
universe@195 | 38 | // if child is NULL, nullkey decides if left or right pointer is cleared |
universe@195 | 39 | if (tree->cmpfunc( |
universe@195 | 40 | ptrcast(child ? child->key : nullkey), |
universe@195 | 41 | ptrcast(node->key), tree->userdata) > 0) { |
universe@195 | 42 | node->right = child; |
universe@195 | 43 | } else { |
universe@195 | 44 | node->left = child; |
universe@195 | 45 | } |
universe@195 | 46 | size_t lh = node->left ? node->left->height : 0; |
universe@195 | 47 | size_t rh = node->right ? node->right->height : 0; |
universe@195 | 48 | node->height = 1 + (lh > rh ? lh : rh); |
universe@195 | 49 | } |
universe@195 | 50 | |
universe@195 | 51 | #define avlheight(node) ((node) ? (node)->height : 0) |
universe@195 | 52 | |
universe@195 | 53 | static UcxAVLNode* avl_rotright(UcxAVLTree *tree, UcxAVLNode *l0) { |
universe@195 | 54 | UcxAVLNode *p = l0->parent; |
universe@195 | 55 | UcxAVLNode *l1 = l0->left; |
universe@195 | 56 | if (p) { |
universe@195 | 57 | ucx_avl_connect(tree, p, l1, 0); |
universe@195 | 58 | } else { |
universe@195 | 59 | l1->parent = NULL; |
universe@195 | 60 | } |
universe@195 | 61 | ucx_avl_connect(tree, l0, l1->right, l1->key); |
universe@195 | 62 | ucx_avl_connect(tree, l1, l0, 0); |
universe@195 | 63 | return l1; |
universe@195 | 64 | } |
universe@195 | 65 | |
universe@195 | 66 | static UcxAVLNode* avl_rotleft(UcxAVLTree *tree, UcxAVLNode *l0) { |
universe@195 | 67 | UcxAVLNode *p = l0->parent; |
universe@195 | 68 | UcxAVLNode *l1 = l0->right; |
universe@195 | 69 | if (p) { |
universe@195 | 70 | ucx_avl_connect(tree, p, l1, 0); |
universe@195 | 71 | } else { |
universe@195 | 72 | l1->parent = NULL; |
universe@195 | 73 | } |
universe@195 | 74 | ucx_avl_connect(tree, l0, l1->left, l1->key); |
universe@195 | 75 | ucx_avl_connect(tree, l1, l0, 0); |
universe@195 | 76 | return l1; |
universe@195 | 77 | } |
universe@195 | 78 | |
universe@195 | 79 | static void ucx_avl_balance(UcxAVLTree *tree, UcxAVLNode *n) { |
universe@195 | 80 | int lh = avlheight(n->left); |
universe@195 | 81 | int rh = avlheight(n->right); |
universe@195 | 82 | n->height = 1 + (lh > rh ? lh : rh); |
universe@195 | 83 | |
universe@195 | 84 | if (lh - rh == 2) { |
universe@195 | 85 | UcxAVLNode *c = n->left; |
universe@195 | 86 | if (avlheight(c->right) - avlheight(c->left) == 1) { |
universe@195 | 87 | avl_rotleft(tree, c); |
universe@195 | 88 | } |
universe@195 | 89 | n = avl_rotright(tree, n); |
universe@195 | 90 | } else if (rh - lh == 2) { |
universe@195 | 91 | UcxAVLNode *c = n->right; |
universe@195 | 92 | if (avlheight(c->left) - avlheight(c->right) == 1) { |
universe@195 | 93 | avl_rotright(tree, c); |
universe@195 | 94 | } |
universe@195 | 95 | n = avl_rotleft(tree, n); |
universe@195 | 96 | } |
universe@195 | 97 | |
universe@195 | 98 | if (n->parent) { |
universe@195 | 99 | ucx_avl_balance(tree, n->parent); |
universe@195 | 100 | } else { |
universe@195 | 101 | tree->root = n; |
universe@195 | 102 | } |
universe@195 | 103 | } |
universe@195 | 104 | |
universe@194 | 105 | UcxAVLTree *ucx_avl_new(cmp_func cmpfunc) { |
universe@194 | 106 | return ucx_avl_new_a(cmpfunc, ucx_default_allocator()); |
universe@194 | 107 | } |
universe@194 | 108 | |
universe@194 | 109 | UcxAVLTree *ucx_avl_new_a(cmp_func cmpfunc, UcxAllocator *allocator) { |
universe@196 | 110 | UcxAVLTree *tree = almalloc(allocator, sizeof(UcxAVLTree)); |
universe@194 | 111 | if (tree) { |
universe@194 | 112 | tree->allocator = allocator; |
universe@194 | 113 | tree->cmpfunc = cmpfunc; |
universe@194 | 114 | tree->root = NULL; |
universe@194 | 115 | tree->userdata = NULL; |
universe@194 | 116 | } |
universe@194 | 117 | |
universe@194 | 118 | return tree; |
universe@194 | 119 | } |
universe@194 | 120 | |
universe@196 | 121 | static void ucx_avl_free_node(UcxAllocator *al, UcxAVLNode *node) { |
universe@196 | 122 | if (node) { |
universe@196 | 123 | ucx_avl_free_node(al, node->left); |
universe@196 | 124 | ucx_avl_free_node(al, node->right); |
universe@196 | 125 | alfree(al, node); |
universe@196 | 126 | } |
universe@196 | 127 | } |
universe@196 | 128 | |
universe@196 | 129 | void ucx_avl_free(UcxAVLTree *tree) { |
universe@196 | 130 | UcxAllocator *al = tree->allocator; |
universe@196 | 131 | ucx_avl_free_node(al, tree->root); |
universe@196 | 132 | alfree(al, tree); |
universe@196 | 133 | } |
universe@196 | 134 | |
universe@194 | 135 | void *ucx_avl_get(UcxAVLTree *tree, intptr_t key) { |
universe@195 | 136 | UcxAVLNode *n = tree->root; |
universe@195 | 137 | int cmpresult; |
universe@195 | 138 | while (n && (cmpresult = tree->cmpfunc( |
universe@195 | 139 | ptrcast(key), ptrcast(n->key), tree->userdata))) { |
universe@195 | 140 | n = cmpresult > 0 ? n->right : n->left; |
universe@195 | 141 | } |
universe@195 | 142 | return n ? n->value : NULL; |
universe@194 | 143 | } |
universe@194 | 144 | |
universe@194 | 145 | void* ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value) { |
universe@195 | 146 | if (tree->root) { |
universe@195 | 147 | UcxAVLNode *n = tree->root; |
universe@195 | 148 | int cmpresult; |
universe@197 | 149 | while ((cmpresult = tree->cmpfunc( |
universe@197 | 150 | ptrcast(key), ptrcast(n->key), tree->userdata))) { |
universe@195 | 151 | UcxAVLNode *m = cmpresult > 0 ? n->right : n->left; |
universe@195 | 152 | if (m) { |
universe@195 | 153 | n = m; |
universe@195 | 154 | } else { |
universe@195 | 155 | break; |
universe@195 | 156 | } |
universe@195 | 157 | } |
universe@195 | 158 | |
universe@195 | 159 | if (cmpresult) { |
universe@196 | 160 | UcxAVLNode *e = almalloc(tree->allocator, sizeof(UcxAVLNode)); |
universe@195 | 161 | e->key = key; e->value = value; e->height = 1; |
universe@195 | 162 | e->parent = e->left = e->right = NULL; |
universe@195 | 163 | ucx_avl_connect(tree, n, e, 0); |
universe@195 | 164 | ucx_avl_balance(tree, n); |
universe@195 | 165 | return NULL; |
universe@195 | 166 | } else { |
universe@195 | 167 | void *prevval = n->value; |
universe@195 | 168 | n->value = value; |
universe@195 | 169 | return prevval; |
universe@195 | 170 | } |
universe@195 | 171 | } else { |
universe@196 | 172 | tree->root = almalloc(tree->allocator, sizeof(UcxAVLNode)); |
universe@195 | 173 | tree->root->key = key; tree->root->value = value; |
universe@195 | 174 | tree->root->height = 1; |
universe@195 | 175 | tree->root->parent = tree->root->left = tree->root->right = NULL; |
universe@195 | 176 | return NULL; |
universe@195 | 177 | } |
universe@194 | 178 | } |
universe@194 | 179 | |
universe@194 | 180 | void* ucx_avl_remove(UcxAVLTree *tree, intptr_t key) { |
universe@195 | 181 | UcxAVLNode *n = tree->root; |
universe@195 | 182 | int cmpresult; |
universe@195 | 183 | while (n && (cmpresult = tree->cmpfunc( |
universe@195 | 184 | ptrcast(key), ptrcast(n->key), tree->userdata))) { |
universe@195 | 185 | n = cmpresult > 0 ? n->right : n->left; |
universe@195 | 186 | } |
universe@195 | 187 | if (n) { |
universe@195 | 188 | void *prevval = n->value; |
universe@195 | 189 | UcxAVLNode *p = n->parent; |
universe@195 | 190 | if (n->left && n->right) { |
universe@195 | 191 | UcxAVLNode *s = n->right; |
universe@195 | 192 | while (s->left) { |
universe@195 | 193 | s = s->left; |
universe@195 | 194 | } |
universe@195 | 195 | ucx_avl_connect(tree, s->parent, s->right, s->key); |
universe@195 | 196 | n->key = s->key; n->value = s->value; |
universe@195 | 197 | p = s->parent; |
universe@196 | 198 | alfree(tree->allocator, s); |
universe@195 | 199 | } else { |
universe@195 | 200 | if (p) { |
universe@195 | 201 | ucx_avl_connect(tree, p, n->right ? n->right:n->left, n->key); |
universe@195 | 202 | } else { |
universe@195 | 203 | tree->root = n->right ? n->right : n->left; |
universe@195 | 204 | } |
universe@196 | 205 | alfree(tree->allocator, n); |
universe@195 | 206 | } |
universe@195 | 207 | |
universe@195 | 208 | if (p) { |
universe@195 | 209 | ucx_avl_balance(tree, p); |
universe@195 | 210 | } |
universe@195 | 211 | return prevval; |
universe@195 | 212 | } else { |
universe@195 | 213 | return NULL; |
universe@195 | 214 | } |
universe@194 | 215 | } |
universe@194 | 216 |