ucx: ucx/avl.c@dee5a88c4db7

     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  */

    29 #include "avl.h"

    31 #define ptrcast(ptr) ((void*)(ptr))

    32 #define alloc_tree(al) (UcxAVLTree*) almalloc((al), sizeof(UcxAVLTree))

    33 #define alloc_node(al) (UcxAVLNode*) almalloc((al), sizeof(UcxAVLNode))

    35 static void ucx_avl_connect(UcxAVLTree *tree,

    36         UcxAVLNode *node, UcxAVLNode *child, intptr_t nullkey) {

    37     if (child) {

    38         child->parent = node;

    39     }

    40     // if child is NULL, nullkey decides if left or right pointer is cleared

    41     if (tree->cmpfunc(

    42         ptrcast(child ? child->key : nullkey),

    43         ptrcast(node->key), tree->userdata) > 0) {

    44       node->right = child;

    45     } else {

    46       node->left = child;

    47     }

    48     size_t lh = node->left ? node->left->height : 0;

    49     size_t rh = node->right ? node->right->height : 0;

    50     node->height = 1 + (lh > rh ? lh : rh);

    51 }

    53 #define avlheight(node) ((node) ? (node)->height : 0)

    55 static UcxAVLNode* avl_rotright(UcxAVLTree *tree, UcxAVLNode *l0) {

    56     UcxAVLNode *p = l0->parent;

    57     UcxAVLNode *l1 = l0->left;

    58     if (p) {

    59         ucx_avl_connect(tree, p, l1, 0);

    60     } else {

    61         l1->parent = NULL;

    62     }

    63     ucx_avl_connect(tree, l0, l1->right, l1->key);

    64     ucx_avl_connect(tree, l1, l0, 0);

    65     return l1;

    66 }

    68 static UcxAVLNode* avl_rotleft(UcxAVLTree *tree, UcxAVLNode *l0) {

    69     UcxAVLNode *p = l0->parent;

    70     UcxAVLNode *l1 = l0->right;

    71     if (p) {

    72         ucx_avl_connect(tree, p, l1, 0);

    73     } else {

    74         l1->parent = NULL;

    75     }

    76     ucx_avl_connect(tree, l0, l1->left, l1->key);

    77     ucx_avl_connect(tree, l1, l0, 0);

    78     return l1;

    79 }

    81 static void ucx_avl_balance(UcxAVLTree *tree, UcxAVLNode *n) {

    82     int lh = avlheight(n->left);

    83     int rh = avlheight(n->right);

    84     n->height = 1 + (lh > rh ? lh : rh);

    86     if (lh - rh == 2) {

    87       UcxAVLNode *c = n->left;

    88       if (avlheight(c->right) - avlheight(c->left) == 1) {

    89         avl_rotleft(tree, c);

    90       }

    91       n = avl_rotright(tree, n);

    92     } else if (rh - lh == 2) {

    93       UcxAVLNode *c = n->right;

    94       if (avlheight(c->left) - avlheight(c->right) == 1) {

    95         avl_rotright(tree, c);

    96       }

    97       n = avl_rotleft(tree, n);

    98     }

   100     if (n->parent) {

   101       ucx_avl_balance(tree, n->parent);

   102     } else {

   103       tree->root = n;

   104     }

   105 }

   107 UcxAVLTree *ucx_avl_new(cmp_func cmpfunc) {

   108     return ucx_avl_new_a(cmpfunc, ucx_default_allocator());

   109 }

   111 UcxAVLTree *ucx_avl_new_a(cmp_func cmpfunc, UcxAllocator *allocator) {

   112     UcxAVLTree* tree = alloc_tree(allocator);

   113     if (tree) {

   114         tree->allocator = allocator;

   115         tree->cmpfunc = cmpfunc;

   116         tree->root = NULL;

   117         tree->userdata = NULL;

   118     }

   120     return tree;

   121 }

   123 static void ucx_avl_free_node(UcxAllocator *al, UcxAVLNode *node) {

   124     if (node) {

   125         ucx_avl_free_node(al, node->left);

   126         ucx_avl_free_node(al, node->right);

   127         alfree(al, node);

   128     }

   129 }

   131 void ucx_avl_free(UcxAVLTree *tree) {

   132     UcxAllocator *al = tree->allocator;

   133     ucx_avl_free_node(al, tree->root);

   134     alfree(al, tree);

   135 }

   137 UcxAVLNode *ucx_avl_get_node(UcxAVLTree *tree, intptr_t key) {

   138     UcxAVLNode *n = tree->root;

   139     int cmpresult;

   140     while (n && (cmpresult = tree->cmpfunc(

   141             ptrcast(key), ptrcast(n->key), tree->userdata))) {

   142         n = cmpresult > 0 ? n->right : n->left;

   143     }

   144     return n;

   145 }

   147 void *ucx_avl_get(UcxAVLTree *tree, intptr_t key) {

   148     UcxAVLNode *n = ucx_avl_get_node(tree, key);

   149     return n ? n->value : NULL;

   150 }

   152 int ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value) {

   153     return ucx_avl_put_s(tree, key, value, NULL);

   154 }

   156 int ucx_avl_put_s(UcxAVLTree *tree, intptr_t key, void *value,

   157         void **oldvalue) {

   158     if (tree->root) {

   159         UcxAVLNode *n = tree->root;

   160         int cmpresult;

   161         while ((cmpresult = tree->cmpfunc(

   162                 ptrcast(key), ptrcast(n->key), tree->userdata))) {

   163             UcxAVLNode *m = cmpresult > 0 ? n->right : n->left;

   164             if (m) {

   165                 n = m;

   166             } else {

   167                 break;

   168             }

   169         }

   171         if (cmpresult) {

   172             UcxAVLNode* e = alloc_node(tree->allocator);

   173             if (e) {

   174                 e->key = key; e->value = value; e->height = 1;

   175                 e->parent = e->left = e->right = NULL;

   176                 ucx_avl_connect(tree, n, e, 0);

   177                 ucx_avl_balance(tree, n);

   178                 return 0;

   179             } else {

   180                 return 1;

   181             }

   182         } else {

   183             if (oldvalue) {

   184                 *oldvalue = n->value;

   185             }

   186             n->value = value;

   187             return 0;

   188         }

   189     } else {

   190         tree->root = alloc_node(tree->allocator);

   191         if (tree->root) {

   192             tree->root->key = key; tree->root->value = value;

   193             tree->root->height = 1;

   194             tree->root->parent = tree->root->left = tree->root->right = NULL;

   196             if (oldvalue) {

   197                 *oldvalue = NULL;

   198             }

   200             return 0;

   201         } else {

   202             return 1;

   203         }

   204     }

   205 }

   207 int ucx_avl_remove(UcxAVLTree *tree, intptr_t key) {

   208     return ucx_avl_remove_s(tree, key, NULL, NULL);

   209 }

   211 int ucx_avl_remove_node(UcxAVLTree *tree, UcxAVLNode *node) {

   212     return ucx_avl_remove_s(tree, node->key, NULL, NULL);

   213 }

   215 int ucx_avl_remove_s(UcxAVLTree *tree, intptr_t key,

   216         intptr_t *oldkey, void **oldvalue) {

   218     UcxAVLNode *n = tree->root;

   219     int cmpresult;

   220     while (n && (cmpresult = tree->cmpfunc(

   221             ptrcast(key), ptrcast(n->key), tree->userdata))) {

   222         n = cmpresult > 0 ? n->right : n->left;

   223     }

   224     if (n) {

   225         if (oldkey) {

   226             *oldkey = n->key;

   227         }

   228         if (oldvalue) {

   229             *oldvalue = n->value;

   230         }

   232         UcxAVLNode *p = n->parent;

   233         if (n->left && n->right) {

   234             UcxAVLNode *s = n->right;

   235             while (s->left) {

   236                 s = s->left;

   237             }

   238             ucx_avl_connect(tree, s->parent, s->right, s->key);

   239             n->key = s->key; n->value = s->value;

   240             p = s->parent;

   241             alfree(tree->allocator, s);

   242         } else {

   243             if (p) {

   244                 ucx_avl_connect(tree, p, n->right ? n->right:n->left, n->key);

   245             } else {

   246                 tree->root = n->right ? n->right : n->left;

   247                 if (tree->root) {

   248                     tree->root->parent = NULL;

   249                 }

   250             }

   251             alfree(tree->allocator, n);

   252         }

   254         if (p) {

   255             ucx_avl_balance(tree, p);

   256         }

   258         return 0;

   259     } else {

   260         return 1;

   261     }

   262 }

   264 static size_t ucx_avl_countn(UcxAVLNode *node) {

   265     if (node) {

   266         return 1 + ucx_avl_countn(node->left) + ucx_avl_countn(node->right);

   267     } else {

   268         return 0;

   269     }

   270 }

   272 size_t ucx_avl_count(UcxAVLTree *tree) {

   273     return ucx_avl_countn(tree->root);

   274 }

Mercurial > hg > ucx / file revision

ucx/avl.c@dee5a88c4db7

ucx/avl.c