comparison: ucx/avl.c
ucx/avl.c
- changeset 112
- f62d271675bf
- parent 111
- 39f4c5fcaa60
- child 113
- 412b06dc0162
equal
deleted
inserted
replaced
| 111:39f4c5fcaa60 | 112:f62d271675bf |
|---|---|
| 1 /* | |
| 2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. | |
| 3 * | |
| 4 * Copyright 2015 Olaf Wintermann. All rights reserved. | |
| 5 * | |
| 6 * Redistribution and use in source and binary forms, with or without | |
| 7 * modification, are permitted provided that the following conditions are met: | |
| 8 * | |
| 9 * 1. Redistributions of source code must retain the above copyright | |
| 10 * notice, this list of conditions and the following disclaimer. | |
| 11 * | |
| 12 * 2. Redistributions in binary form must reproduce the above copyright | |
| 13 * notice, this list of conditions and the following disclaimer in the | |
| 14 * documentation and/or other materials provided with the distribution. | |
| 15 * | |
| 16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" | |
| 17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
| 18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | |
| 19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE | |
| 20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR | |
| 21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF | |
| 22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS | |
| 23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN | |
| 24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | |
| 25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE | |
| 26 * POSSIBILITY OF SUCH DAMAGE. | |
| 27 */ | |
| 28 | |
| 29 #include "avl.h" | |
| 30 | |
| 31 #define ptrcast(ptr) ((void*)(ptr)) | |
| 32 | |
| 33 static void ucx_avl_connect(UcxAVLTree *tree, | |
| 34 UcxAVLNode *node, UcxAVLNode *child, intptr_t nullkey) { | |
| 35 if (child) { | |
| 36 child->parent = node; | |
| 37 } | |
| 38 // if child is NULL, nullkey decides if left or right pointer is cleared | |
| 39 if (tree->cmpfunc( | |
| 40 ptrcast(child ? child->key : nullkey), | |
| 41 ptrcast(node->key), tree->userdata) > 0) { | |
| 42 node->right = child; | |
| 43 } else { | |
| 44 node->left = child; | |
| 45 } | |
| 46 size_t lh = node->left ? node->left->height : 0; | |
| 47 size_t rh = node->right ? node->right->height : 0; | |
| 48 node->height = 1 + (lh > rh ? lh : rh); | |
| 49 } | |
| 50 | |
| 51 #define avlheight(node) ((node) ? (node)->height : 0) | |
| 52 | |
| 53 static UcxAVLNode* avl_rotright(UcxAVLTree *tree, UcxAVLNode *l0) { | |
| 54 UcxAVLNode *p = l0->parent; | |
| 55 UcxAVLNode *l1 = l0->left; | |
| 56 if (p) { | |
| 57 ucx_avl_connect(tree, p, l1, 0); | |
| 58 } else { | |
| 59 l1->parent = NULL; | |
| 60 } | |
| 61 ucx_avl_connect(tree, l0, l1->right, l1->key); | |
| 62 ucx_avl_connect(tree, l1, l0, 0); | |
| 63 return l1; | |
| 64 } | |
| 65 | |
| 66 static UcxAVLNode* avl_rotleft(UcxAVLTree *tree, UcxAVLNode *l0) { | |
| 67 UcxAVLNode *p = l0->parent; | |
| 68 UcxAVLNode *l1 = l0->right; | |
| 69 if (p) { | |
| 70 ucx_avl_connect(tree, p, l1, 0); | |
| 71 } else { | |
| 72 l1->parent = NULL; | |
| 73 } | |
| 74 ucx_avl_connect(tree, l0, l1->left, l1->key); | |
| 75 ucx_avl_connect(tree, l1, l0, 0); | |
| 76 return l1; | |
| 77 } | |
| 78 | |
| 79 static void ucx_avl_balance(UcxAVLTree *tree, UcxAVLNode *n) { | |
| 80 int lh = avlheight(n->left); | |
| 81 int rh = avlheight(n->right); | |
| 82 n->height = 1 + (lh > rh ? lh : rh); | |
| 83 | |
| 84 if (lh - rh == 2) { | |
| 85 UcxAVLNode *c = n->left; | |
| 86 if (avlheight(c->right) - avlheight(c->left) == 1) { | |
| 87 avl_rotleft(tree, c); | |
| 88 } | |
| 89 n = avl_rotright(tree, n); | |
| 90 } else if (rh - lh == 2) { | |
| 91 UcxAVLNode *c = n->right; | |
| 92 if (avlheight(c->left) - avlheight(c->right) == 1) { | |
| 93 avl_rotright(tree, c); | |
| 94 } | |
| 95 n = avl_rotleft(tree, n); | |
| 96 } | |
| 97 | |
| 98 if (n->parent) { | |
| 99 ucx_avl_balance(tree, n->parent); | |
| 100 } else { | |
| 101 tree->root = n; | |
| 102 } | |
| 103 } | |
| 104 | |
| 105 UcxAVLTree *ucx_avl_new(cmp_func cmpfunc) { | |
| 106 return ucx_avl_new_a(cmpfunc, ucx_default_allocator()); | |
| 107 } | |
| 108 | |
| 109 UcxAVLTree *ucx_avl_new_a(cmp_func cmpfunc, UcxAllocator *allocator) { | |
| 110 UcxAVLTree *tree = almalloc(allocator, sizeof(UcxAVLTree)); | |
| 111 if (tree) { | |
| 112 tree->allocator = allocator; | |
| 113 tree->cmpfunc = cmpfunc; | |
| 114 tree->root = NULL; | |
| 115 tree->userdata = NULL; | |
| 116 } | |
| 117 | |
| 118 return tree; | |
| 119 } | |
| 120 | |
| 121 static void ucx_avl_free_node(UcxAllocator *al, UcxAVLNode *node) { | |
| 122 if (node) { | |
| 123 ucx_avl_free_node(al, node->left); | |
| 124 ucx_avl_free_node(al, node->right); | |
| 125 alfree(al, node); | |
| 126 } | |
| 127 } | |
| 128 | |
| 129 void ucx_avl_free(UcxAVLTree *tree) { | |
| 130 UcxAllocator *al = tree->allocator; | |
| 131 ucx_avl_free_node(al, tree->root); | |
| 132 alfree(al, tree); | |
| 133 } | |
| 134 | |
| 135 void *ucx_avl_get(UcxAVLTree *tree, intptr_t key) { | |
| 136 UcxAVLNode *n = tree->root; | |
| 137 int cmpresult; | |
| 138 while (n && (cmpresult = tree->cmpfunc( | |
| 139 ptrcast(key), ptrcast(n->key), tree->userdata))) { | |
| 140 n = cmpresult > 0 ? n->right : n->left; | |
| 141 } | |
| 142 return n ? n->value : NULL; | |
| 143 } | |
| 144 | |
| 145 void* ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value) { | |
| 146 if (tree->root) { | |
| 147 UcxAVLNode *n = tree->root; | |
| 148 int cmpresult; | |
| 149 while ((cmpresult = tree->cmpfunc( | |
| 150 ptrcast(key), ptrcast(n->key), tree->userdata))) { | |
| 151 UcxAVLNode *m = cmpresult > 0 ? n->right : n->left; | |
| 152 if (m) { | |
| 153 n = m; | |
| 154 } else { | |
| 155 break; | |
| 156 } | |
| 157 } | |
| 158 | |
| 159 if (cmpresult) { | |
| 160 UcxAVLNode *e = almalloc(tree->allocator, sizeof(UcxAVLNode)); | |
| 161 e->key = key; e->value = value; e->height = 1; | |
| 162 e->parent = e->left = e->right = NULL; | |
| 163 ucx_avl_connect(tree, n, e, 0); | |
| 164 ucx_avl_balance(tree, n); | |
| 165 return NULL; | |
| 166 } else { | |
| 167 void *prevval = n->value; | |
| 168 n->value = value; | |
| 169 return prevval; | |
| 170 } | |
| 171 } else { | |
| 172 tree->root = almalloc(tree->allocator, sizeof(UcxAVLNode)); | |
| 173 tree->root->key = key; tree->root->value = value; | |
| 174 tree->root->height = 1; | |
| 175 tree->root->parent = tree->root->left = tree->root->right = NULL; | |
| 176 return NULL; | |
| 177 } | |
| 178 } | |
| 179 | |
| 180 void* ucx_avl_remove(UcxAVLTree *tree, intptr_t key) { | |
| 181 UcxAVLNode *n = tree->root; | |
| 182 int cmpresult; | |
| 183 while (n && (cmpresult = tree->cmpfunc( | |
| 184 ptrcast(key), ptrcast(n->key), tree->userdata))) { | |
| 185 n = cmpresult > 0 ? n->right : n->left; | |
| 186 } | |
| 187 if (n) { | |
| 188 void *prevval = n->value; | |
| 189 UcxAVLNode *p = n->parent; | |
| 190 if (n->left && n->right) { | |
| 191 UcxAVLNode *s = n->right; | |
| 192 while (s->left) { | |
| 193 s = s->left; | |
| 194 } | |
| 195 ucx_avl_connect(tree, s->parent, s->right, s->key); | |
| 196 n->key = s->key; n->value = s->value; | |
| 197 p = s->parent; | |
| 198 alfree(tree->allocator, s); | |
| 199 } else { | |
| 200 if (p) { | |
| 201 ucx_avl_connect(tree, p, n->right ? n->right:n->left, n->key); | |
| 202 } else { | |
| 203 tree->root = n->right ? n->right : n->left; | |
| 204 if (tree->root) { | |
| 205 tree->root->parent = NULL; | |
| 206 } | |
| 207 } | |
| 208 alfree(tree->allocator, n); | |
| 209 } | |
| 210 | |
| 211 if (p) { | |
| 212 ucx_avl_balance(tree, p); | |
| 213 } | |
| 214 return prevval; | |
| 215 } else { | |
| 216 return NULL; | |
| 217 } | |
| 218 } | |
| 219 | |
| 220 static size_t ucx_avl_countn(UcxAVLNode *node) { | |
| 221 if (node) { | |
| 222 return 1 + ucx_avl_countn(node->left) + ucx_avl_countn(node->right); | |
| 223 } else { | |
| 224 return 0; | |
| 225 } | |
| 226 } | |
| 227 | |
| 228 size_t ucx_avl_count(UcxAVLTree *tree) { | |
| 229 return ucx_avl_countn(tree->root); | |
| 230 } |
