--- a/ucx/avl.c Tue May 19 14:04:48 2015 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,230 +0,0 @@ -/* - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. - * - * Copyright 2015 Olaf Wintermann. All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions are met: - * - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" - * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE - * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR - * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF - * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS - * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN - * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) - * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE - * POSSIBILITY OF SUCH DAMAGE. - */ - -#include "avl.h" - -#define ptrcast(ptr) ((void*)(ptr)) - -static void ucx_avl_connect(UcxAVLTree *tree, - UcxAVLNode *node, UcxAVLNode *child, intptr_t nullkey) { - if (child) { - child->parent = node; - } - // if child is NULL, nullkey decides if left or right pointer is cleared - if (tree->cmpfunc( - ptrcast(child ? child->key : nullkey), - ptrcast(node->key), tree->userdata) > 0) { - node->right = child; - } else { - node->left = child; - } - size_t lh = node->left ? node->left->height : 0; - size_t rh = node->right ? node->right->height : 0; - node->height = 1 + (lh > rh ? lh : rh); -} - -#define avlheight(node) ((node) ? (node)->height : 0) - -static UcxAVLNode* avl_rotright(UcxAVLTree *tree, UcxAVLNode *l0) { - UcxAVLNode *p = l0->parent; - UcxAVLNode *l1 = l0->left; - if (p) { - ucx_avl_connect(tree, p, l1, 0); - } else { - l1->parent = NULL; - } - ucx_avl_connect(tree, l0, l1->right, l1->key); - ucx_avl_connect(tree, l1, l0, 0); - return l1; -} - -static UcxAVLNode* avl_rotleft(UcxAVLTree *tree, UcxAVLNode *l0) { - UcxAVLNode *p = l0->parent; - UcxAVLNode *l1 = l0->right; - if (p) { - ucx_avl_connect(tree, p, l1, 0); - } else { - l1->parent = NULL; - } - ucx_avl_connect(tree, l0, l1->left, l1->key); - ucx_avl_connect(tree, l1, l0, 0); - return l1; -} - -static void ucx_avl_balance(UcxAVLTree *tree, UcxAVLNode *n) { - int lh = avlheight(n->left); - int rh = avlheight(n->right); - n->height = 1 + (lh > rh ? lh : rh); - - if (lh - rh == 2) { - UcxAVLNode *c = n->left; - if (avlheight(c->right) - avlheight(c->left) == 1) { - avl_rotleft(tree, c); - } - n = avl_rotright(tree, n); - } else if (rh - lh == 2) { - UcxAVLNode *c = n->right; - if (avlheight(c->left) - avlheight(c->right) == 1) { - avl_rotright(tree, c); - } - n = avl_rotleft(tree, n); - } - - if (n->parent) { - ucx_avl_balance(tree, n->parent); - } else { - tree->root = n; - } -} - -UcxAVLTree *ucx_avl_new(cmp_func cmpfunc) { - return ucx_avl_new_a(cmpfunc, ucx_default_allocator()); -} - -UcxAVLTree *ucx_avl_new_a(cmp_func cmpfunc, UcxAllocator *allocator) { - UcxAVLTree *tree = almalloc(allocator, sizeof(UcxAVLTree)); - if (tree) { - tree->allocator = allocator; - tree->cmpfunc = cmpfunc; - tree->root = NULL; - tree->userdata = NULL; - } - - return tree; -} - -static void ucx_avl_free_node(UcxAllocator *al, UcxAVLNode *node) { - if (node) { - ucx_avl_free_node(al, node->left); - ucx_avl_free_node(al, node->right); - alfree(al, node); - } -} - -void ucx_avl_free(UcxAVLTree *tree) { - UcxAllocator *al = tree->allocator; - ucx_avl_free_node(al, tree->root); - alfree(al, tree); -} - -void *ucx_avl_get(UcxAVLTree *tree, intptr_t key) { - UcxAVLNode *n = tree->root; - int cmpresult; - while (n && (cmpresult = tree->cmpfunc( - ptrcast(key), ptrcast(n->key), tree->userdata))) { - n = cmpresult > 0 ? n->right : n->left; - } - return n ? n->value : NULL; -} - -void* ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value) { - if (tree->root) { - UcxAVLNode *n = tree->root; - int cmpresult; - while ((cmpresult = tree->cmpfunc( - ptrcast(key), ptrcast(n->key), tree->userdata))) { - UcxAVLNode *m = cmpresult > 0 ? n->right : n->left; - if (m) { - n = m; - } else { - break; - } - } - - if (cmpresult) { - UcxAVLNode *e = almalloc(tree->allocator, sizeof(UcxAVLNode)); - e->key = key; e->value = value; e->height = 1; - e->parent = e->left = e->right = NULL; - ucx_avl_connect(tree, n, e, 0); - ucx_avl_balance(tree, n); - return NULL; - } else { - void *prevval = n->value; - n->value = value; - return prevval; - } - } else { - tree->root = almalloc(tree->allocator, sizeof(UcxAVLNode)); - tree->root->key = key; tree->root->value = value; - tree->root->height = 1; - tree->root->parent = tree->root->left = tree->root->right = NULL; - return NULL; - } -} - -void* ucx_avl_remove(UcxAVLTree *tree, intptr_t key) { - UcxAVLNode *n = tree->root; - int cmpresult; - while (n && (cmpresult = tree->cmpfunc( - ptrcast(key), ptrcast(n->key), tree->userdata))) { - n = cmpresult > 0 ? n->right : n->left; - } - if (n) { - void *prevval = n->value; - UcxAVLNode *p = n->parent; - if (n->left && n->right) { - UcxAVLNode *s = n->right; - while (s->left) { - s = s->left; - } - ucx_avl_connect(tree, s->parent, s->right, s->key); - n->key = s->key; n->value = s->value; - p = s->parent; - alfree(tree->allocator, s); - } else { - if (p) { - ucx_avl_connect(tree, p, n->right ? n->right:n->left, n->key); - } else { - tree->root = n->right ? n->right : n->left; - if (tree->root) { - tree->root->parent = NULL; - } - } - alfree(tree->allocator, n); - } - - if (p) { - ucx_avl_balance(tree, p); - } - return prevval; - } else { - return NULL; - } -} - -static size_t ucx_avl_countn(UcxAVLNode *node) { - if (node) { - return 1 + ucx_avl_countn(node->left) + ucx_avl_countn(node->right); - } else { - return 0; - } -} - -size_t ucx_avl_count(UcxAVLTree *tree) { - return ucx_avl_countn(tree->root); -}