Mercurial > hg > ucx / changeset

     1.1 --- a/ucx/avl.c	Sun May 17 18:32:41 2015 +0200
     1.2 +++ b/ucx/avl.c	Mon May 18 12:54:18 2015 +0200
     1.3 @@ -28,6 +28,80 @@
     1.4  
     1.5  #include "avl.h"
     1.6  
     1.7 +#define ptrcast(ptr) ((void*)(ptr))
     1.8 +
     1.9 +static void ucx_avl_connect(UcxAVLTree *tree,
    1.10 +        UcxAVLNode *node, UcxAVLNode *child, intptr_t nullkey) {
    1.11 +    if (child) {
    1.12 +        child->parent = node;
    1.13 +    }
    1.14 +    // if child is NULL, nullkey decides if left or right pointer is cleared
    1.15 +    if (tree->cmpfunc(
    1.16 +        ptrcast(child ? child->key : nullkey),
    1.17 +        ptrcast(node->key), tree->userdata) > 0) {
    1.18 +      node->right = child;
    1.19 +    } else {
    1.20 +      node->left = child;
    1.21 +    }
    1.22 +    size_t lh = node->left ? node->left->height : 0;
    1.23 +    size_t rh = node->right ? node->right->height : 0;
    1.24 +    node->height = 1 + (lh > rh ? lh : rh);
    1.25 +}
    1.26 +
    1.27 +#define avlheight(node) ((node) ? (node)->height : 0)
    1.28 +
    1.29 +static UcxAVLNode* avl_rotright(UcxAVLTree *tree, UcxAVLNode *l0) {
    1.30 +    UcxAVLNode *p = l0->parent;
    1.31 +    UcxAVLNode *l1 = l0->left;
    1.32 +    if (p) {
    1.33 +        ucx_avl_connect(tree, p, l1, 0);
    1.34 +    } else {
    1.35 +        l1->parent = NULL;
    1.36 +    }
    1.37 +    ucx_avl_connect(tree, l0, l1->right, l1->key);
    1.38 +    ucx_avl_connect(tree, l1, l0, 0);
    1.39 +    return l1;
    1.40 +}
    1.41 +
    1.42 +static UcxAVLNode* avl_rotleft(UcxAVLTree *tree, UcxAVLNode *l0) {
    1.43 +    UcxAVLNode *p = l0->parent;
    1.44 +    UcxAVLNode *l1 = l0->right;
    1.45 +    if (p) {
    1.46 +        ucx_avl_connect(tree, p, l1, 0);
    1.47 +    } else {
    1.48 +        l1->parent = NULL;
    1.49 +    }
    1.50 +    ucx_avl_connect(tree, l0, l1->left, l1->key);
    1.51 +    ucx_avl_connect(tree, l1, l0, 0);
    1.52 +    return l1;
    1.53 +}
    1.54 +
    1.55 +static void ucx_avl_balance(UcxAVLTree *tree, UcxAVLNode *n) {
    1.56 +    int lh = avlheight(n->left);
    1.57 +    int rh = avlheight(n->right);
    1.58 +    n->height = 1 + (lh > rh ? lh : rh);
    1.59 +    
    1.60 +    if (lh - rh == 2) {
    1.61 +      UcxAVLNode *c = n->left;
    1.62 +      if (avlheight(c->right) - avlheight(c->left) == 1) {
    1.63 +        avl_rotleft(tree, c);
    1.64 +      }
    1.65 +      n = avl_rotright(tree, n);
    1.66 +    } else if (rh - lh == 2) {  
    1.67 +      UcxAVLNode *c = n->right;
    1.68 +      if (avlheight(c->left) - avlheight(c->right) == 1) {
    1.69 +        avl_rotright(tree, c);
    1.70 +      }
    1.71 +      n = avl_rotleft(tree, n);
    1.72 +    }
    1.73 +
    1.74 +    if (n->parent) {
    1.75 +      ucx_avl_balance(tree, n->parent);
    1.76 +    } else {
    1.77 +      tree->root = n;
    1.78 +    }
    1.79 +}
    1.80 +
    1.81  UcxAVLTree *ucx_avl_new(cmp_func cmpfunc) {
    1.82      return ucx_avl_new_a(cmpfunc, ucx_default_allocator());
    1.83  }
    1.84 @@ -45,14 +119,83 @@
    1.85  }
    1.86  
    1.87  void *ucx_avl_get(UcxAVLTree *tree, intptr_t key) {
    1.88 -    return NULL;
    1.89 +    UcxAVLNode *n = tree->root;
    1.90 +    int cmpresult;
    1.91 +    while (n && (cmpresult = tree->cmpfunc(
    1.92 +            ptrcast(key), ptrcast(n->key), tree->userdata))) {
    1.93 +        n = cmpresult > 0 ? n->right : n->left;
    1.94 +    }
    1.95 +    return n ? n->value : NULL;
    1.96  }
    1.97  
    1.98  void* ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value) {
    1.99 -    return NULL;
   1.100 +    if (tree->root) {
   1.101 +        UcxAVLNode *n = tree->root;
   1.102 +        int cmpresult;
   1.103 +        while (cmpresult = tree->cmpfunc(
   1.104 +                ptrcast(key), ptrcast(n->key), tree->userdata)) {
   1.105 +            UcxAVLNode *m = cmpresult > 0 ? n->right : n->left;
   1.106 +            if (m) {
   1.107 +                n = m;
   1.108 +            } else {
   1.109 +                break;
   1.110 +            }
   1.111 +        }
   1.112 +
   1.113 +        if (cmpresult) {
   1.114 +            UcxAVLNode *e = malloc(sizeof(UcxAVLNode));
   1.115 +            e->key = key; e->value = value; e->height = 1;
   1.116 +            e->parent = e->left = e->right = NULL;
   1.117 +            ucx_avl_connect(tree, n, e, 0);
   1.118 +            ucx_avl_balance(tree, n);
   1.119 +            return NULL;
   1.120 +        } else {
   1.121 +            void *prevval = n->value;
   1.122 +            n->value = value;
   1.123 +            return prevval;
   1.124 +        }
   1.125 +    } else {
   1.126 +        tree->root = malloc(sizeof(UcxAVLNode));
   1.127 +        tree->root->key = key; tree->root->value = value;
   1.128 +        tree->root->height = 1;
   1.129 +        tree->root->parent = tree->root->left = tree->root->right = NULL;
   1.130 +        return NULL;
   1.131 +    }
   1.132  }
   1.133  
   1.134  void* ucx_avl_remove(UcxAVLTree *tree, intptr_t key) {
   1.135 -    return NULL;
   1.136 +    UcxAVLNode *n = tree->root;
   1.137 +    int cmpresult;
   1.138 +    while (n && (cmpresult = tree->cmpfunc(
   1.139 +            ptrcast(key), ptrcast(n->key), tree->userdata))) {
   1.140 +        n = cmpresult > 0 ? n->right : n->left;
   1.141 +    }
   1.142 +    if (n) {
   1.143 +        void *prevval = n->value;
   1.144 +        UcxAVLNode *p = n->parent;
   1.145 +        if (n->left && n->right) {
   1.146 +            UcxAVLNode *s = n->right;
   1.147 +            while (s->left) {
   1.148 +                s = s->left;
   1.149 +            }
   1.150 +            ucx_avl_connect(tree, s->parent, s->right, s->key);
   1.151 +            n->key = s->key; n->value = s->value;
   1.152 +            p = s->parent;
   1.153 +        } else {
   1.154 +            if (p) {
   1.155 +                ucx_avl_connect(tree, p, n->right ? n->right:n->left, n->key);
   1.156 +            } else {
   1.157 +                tree->root = n->right ? n->right : n->left;
   1.158 +            }
   1.159 +        }
   1.160 +        // TODO: free the correct memory
   1.161 +
   1.162 +        if (p) {
   1.163 +            ucx_avl_balance(tree, p);
   1.164 +        }
   1.165 +        return prevval;
   1.166 +    } else {
   1.167 +        return NULL;
   1.168 +    }
   1.169  }
   1.170