Mon, 18 May 2015 12:54:18 +0200
added AVL tree implementation - TODO: free memory + test cases
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@194 | 110 | UcxAVLTree *tree = malloc(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@194 | 121 | void *ucx_avl_get(UcxAVLTree *tree, intptr_t key) { |
universe@195 | 122 | UcxAVLNode *n = tree->root; |
universe@195 | 123 | int cmpresult; |
universe@195 | 124 | while (n && (cmpresult = tree->cmpfunc( |
universe@195 | 125 | ptrcast(key), ptrcast(n->key), tree->userdata))) { |
universe@195 | 126 | n = cmpresult > 0 ? n->right : n->left; |
universe@195 | 127 | } |
universe@195 | 128 | return n ? n->value : NULL; |
universe@194 | 129 | } |
universe@194 | 130 | |
universe@194 | 131 | void* ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value) { |
universe@195 | 132 | if (tree->root) { |
universe@195 | 133 | UcxAVLNode *n = tree->root; |
universe@195 | 134 | int cmpresult; |
universe@195 | 135 | while (cmpresult = tree->cmpfunc( |
universe@195 | 136 | ptrcast(key), ptrcast(n->key), tree->userdata)) { |
universe@195 | 137 | UcxAVLNode *m = cmpresult > 0 ? n->right : n->left; |
universe@195 | 138 | if (m) { |
universe@195 | 139 | n = m; |
universe@195 | 140 | } else { |
universe@195 | 141 | break; |
universe@195 | 142 | } |
universe@195 | 143 | } |
universe@195 | 144 | |
universe@195 | 145 | if (cmpresult) { |
universe@195 | 146 | UcxAVLNode *e = malloc(sizeof(UcxAVLNode)); |
universe@195 | 147 | e->key = key; e->value = value; e->height = 1; |
universe@195 | 148 | e->parent = e->left = e->right = NULL; |
universe@195 | 149 | ucx_avl_connect(tree, n, e, 0); |
universe@195 | 150 | ucx_avl_balance(tree, n); |
universe@195 | 151 | return NULL; |
universe@195 | 152 | } else { |
universe@195 | 153 | void *prevval = n->value; |
universe@195 | 154 | n->value = value; |
universe@195 | 155 | return prevval; |
universe@195 | 156 | } |
universe@195 | 157 | } else { |
universe@195 | 158 | tree->root = malloc(sizeof(UcxAVLNode)); |
universe@195 | 159 | tree->root->key = key; tree->root->value = value; |
universe@195 | 160 | tree->root->height = 1; |
universe@195 | 161 | tree->root->parent = tree->root->left = tree->root->right = NULL; |
universe@195 | 162 | return NULL; |
universe@195 | 163 | } |
universe@194 | 164 | } |
universe@194 | 165 | |
universe@194 | 166 | void* ucx_avl_remove(UcxAVLTree *tree, intptr_t key) { |
universe@195 | 167 | UcxAVLNode *n = tree->root; |
universe@195 | 168 | int cmpresult; |
universe@195 | 169 | while (n && (cmpresult = tree->cmpfunc( |
universe@195 | 170 | ptrcast(key), ptrcast(n->key), tree->userdata))) { |
universe@195 | 171 | n = cmpresult > 0 ? n->right : n->left; |
universe@195 | 172 | } |
universe@195 | 173 | if (n) { |
universe@195 | 174 | void *prevval = n->value; |
universe@195 | 175 | UcxAVLNode *p = n->parent; |
universe@195 | 176 | if (n->left && n->right) { |
universe@195 | 177 | UcxAVLNode *s = n->right; |
universe@195 | 178 | while (s->left) { |
universe@195 | 179 | s = s->left; |
universe@195 | 180 | } |
universe@195 | 181 | ucx_avl_connect(tree, s->parent, s->right, s->key); |
universe@195 | 182 | n->key = s->key; n->value = s->value; |
universe@195 | 183 | p = s->parent; |
universe@195 | 184 | } else { |
universe@195 | 185 | if (p) { |
universe@195 | 186 | ucx_avl_connect(tree, p, n->right ? n->right:n->left, n->key); |
universe@195 | 187 | } else { |
universe@195 | 188 | tree->root = n->right ? n->right : n->left; |
universe@195 | 189 | } |
universe@195 | 190 | } |
universe@195 | 191 | // TODO: free the correct memory |
universe@195 | 192 | |
universe@195 | 193 | if (p) { |
universe@195 | 194 | ucx_avl_balance(tree, p); |
universe@195 | 195 | } |
universe@195 | 196 | return prevval; |
universe@195 | 197 | } else { |
universe@195 | 198 | return NULL; |
universe@195 | 199 | } |
universe@194 | 200 | } |
universe@194 | 201 |