ucx: ucx/avl.c@4477987d40cd

     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))

    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 }

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

    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 }

    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 }

    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);

    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     }

    98     if (n->parent) {

    99       ucx_avl_balance(tree, n->parent);

   100     } else {

   101       tree->root = n;

   102     }

   103 }

   105 UcxAVLTree *ucx_avl_new(cmp_func cmpfunc) {

   106     return ucx_avl_new_a(cmpfunc, ucx_default_allocator());

   107 }

   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     }

   118     return tree;

   119 }

   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 }

   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 }

   135 UcxAVLNode *ucx_avl_getn(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;

   143 }

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

   146     UcxAVLNode *n = ucx_avl_getn(tree, key);

   147     return n ? n->value : NULL;

   148 }

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

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

   152 }

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

   155         void **oldvalue) {

   156     if (tree->root) {

   157         UcxAVLNode *n = tree->root;

   158         int cmpresult;

   159         while ((cmpresult = tree->cmpfunc(

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

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

   162             if (m) {

   163                 n = m;

   164             } else {

   165                 break;

   166             }

   167         }

   169         if (cmpresult) {

   170             UcxAVLNode *e = almalloc(tree->allocator, sizeof(UcxAVLNode));

   171             if (e) {

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

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

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

   175                 ucx_avl_balance(tree, n);

   176                 return 0;

   177             } else {

   178                 return 1;

   179             }

   180         } else {

   181             if (oldvalue) {

   182                 *oldvalue = n->value;

   183             }

   184             n->value = value;

   185             return 0;

   186         }

   187     } else {

   188         tree->root = almalloc(tree->allocator, sizeof(UcxAVLNode));

   189         if (tree->root) {

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

   191             tree->root->height = 1;

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

   194             if (oldvalue) {

   195                 *oldvalue = NULL;

   196             }

   198             return 0;

   199         } else {

   200             return 1;

   201         }

   202     }

   203 }

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

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

   207 }

   209 int ucx_avl_remove_n(UcxAVLTree *tree, UcxAVLNode *node) {

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

   211 }

   213 int ucx_avl_remove_s(UcxAVLTree *tree, intptr_t key,

   214         intptr_t *oldkey, void **oldvalue) {

   216     UcxAVLNode *n = tree->root;

   217     int cmpresult;

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

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

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

   221     }

   222     if (n) {

   223         if (oldkey) {

   224             *oldkey = n->key;

   225         }

   226         if (oldvalue) {

   227             *oldvalue = n->value;

   228         }

   230         UcxAVLNode *p = n->parent;

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

   232             UcxAVLNode *s = n->right;

   233             while (s->left) {

   234                 s = s->left;

   235             }

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

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

   238             p = s->parent;

   239             alfree(tree->allocator, s);

   240         } else {

   241             if (p) {

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

   243             } else {

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

   245                 if (tree->root) {

   246                     tree->root->parent = NULL;

   247                 }

   248             }

   249             alfree(tree->allocator, n);

   250         }

   252         if (p) {

   253             ucx_avl_balance(tree, p);

   254         }

   256         return 0;

   257     } else {

   258         return 1;

   259     }

   260 }

   262 static size_t ucx_avl_countn(UcxAVLNode *node) {

   263     if (node) {

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

   265     } else {

   266         return 0;

   267     }

   268 }

   270 size_t ucx_avl_count(UcxAVLTree *tree) {

   271     return ucx_avl_countn(tree->root);

   272 }

Mercurial > hg > ucx / file revision

ucx/avl.c@4477987d40cd

ucx/avl.c