ucx: ucx/avl.c@bec61f067ea0

     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 = malloc(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 void *ucx_avl_get(UcxAVLTree *tree, intptr_t key) {

   122     UcxAVLNode *n = tree->root;

   123     int cmpresult;

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

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

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

   127     }

   128     return n ? n->value : NULL;

   129 }

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

   132     if (tree->root) {

   133         UcxAVLNode *n = tree->root;

   134         int cmpresult;

   135         while (cmpresult = tree->cmpfunc(

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

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

   138             if (m) {

   139                 n = m;

   140             } else {

   141                 break;

   142             }

   143         }

   145         if (cmpresult) {

   146             UcxAVLNode *e = malloc(sizeof(UcxAVLNode));

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

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

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

   150             ucx_avl_balance(tree, n);

   151             return NULL;

   152         } else {

   153             void *prevval = n->value;

   154             n->value = value;

   155             return prevval;

   156         }

   157     } else {

   158         tree->root = malloc(sizeof(UcxAVLNode));

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

   160         tree->root->height = 1;

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

   162         return NULL;

   163     }

   164 }

   166 void* ucx_avl_remove(UcxAVLTree *tree, intptr_t key) {

   167     UcxAVLNode *n = tree->root;

   168     int cmpresult;

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

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

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

   172     }

   173     if (n) {

   174         void *prevval = n->value;

   175         UcxAVLNode *p = n->parent;

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

   177             UcxAVLNode *s = n->right;

   178             while (s->left) {

   179                 s = s->left;

   180             }

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

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

   183             p = s->parent;

   184         } else {

   185             if (p) {

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

   187             } else {

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

   189             }

   190         }

   191         // TODO: free the correct memory

   193         if (p) {

   194             ucx_avl_balance(tree, p);

   195         }

   196         return prevval;

   197     } else {

   198         return NULL;

   199     }

   200 }

Mercurial > hg > ucx / file revision