comparison: ucx/avl.c
ucx/avl.c
- changeset 196
- 1b4cdafef2eb
- parent 195
- bec61f067ea0
- child 197
- a82f3456b76d
equal
deleted
inserted
replaced
| 195:bec61f067ea0 | 196:1b4cdafef2eb |
|---|---|
| 105 UcxAVLTree *ucx_avl_new(cmp_func cmpfunc) { | 105 UcxAVLTree *ucx_avl_new(cmp_func cmpfunc) { |
| 106 return ucx_avl_new_a(cmpfunc, ucx_default_allocator()); | 106 return ucx_avl_new_a(cmpfunc, ucx_default_allocator()); |
| 107 } | 107 } |
| 108 | 108 |
| 109 UcxAVLTree *ucx_avl_new_a(cmp_func cmpfunc, UcxAllocator *allocator) { | 109 UcxAVLTree *ucx_avl_new_a(cmp_func cmpfunc, UcxAllocator *allocator) { |
| 110 UcxAVLTree *tree = malloc(sizeof(UcxAVLTree)); | 110 UcxAVLTree *tree = almalloc(allocator, sizeof(UcxAVLTree)); |
| 111 if (tree) { | 111 if (tree) { |
| 112 tree->allocator = allocator; | 112 tree->allocator = allocator; |
| 113 tree->cmpfunc = cmpfunc; | 113 tree->cmpfunc = cmpfunc; |
| 114 tree->root = NULL; | 114 tree->root = NULL; |
| 115 tree->userdata = NULL; | 115 tree->userdata = NULL; |
| 116 } | 116 } |
| 117 | 117 |
| 118 return tree; | 118 return tree; |
| 119 } | |
| 120 | |
| 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 } | |
| 128 | |
| 129 void ucx_avl_free(UcxAVLTree *tree) { | |
| 130 UcxAllocator *al = tree->allocator; | |
| 131 ucx_avl_free_node(al, tree->root); | |
| 132 alfree(al, tree); | |
| 119 } | 133 } |
| 120 | 134 |
| 121 void *ucx_avl_get(UcxAVLTree *tree, intptr_t key) { | 135 void *ucx_avl_get(UcxAVLTree *tree, intptr_t key) { |
| 122 UcxAVLNode *n = tree->root; | 136 UcxAVLNode *n = tree->root; |
| 123 int cmpresult; | 137 int cmpresult; |
| 141 break; | 155 break; |
| 142 } | 156 } |
| 143 } | 157 } |
| 144 | 158 |
| 145 if (cmpresult) { | 159 if (cmpresult) { |
| 146 UcxAVLNode *e = malloc(sizeof(UcxAVLNode)); | 160 UcxAVLNode *e = almalloc(tree->allocator, sizeof(UcxAVLNode)); |
| 147 e->key = key; e->value = value; e->height = 1; | 161 e->key = key; e->value = value; e->height = 1; |
| 148 e->parent = e->left = e->right = NULL; | 162 e->parent = e->left = e->right = NULL; |
| 149 ucx_avl_connect(tree, n, e, 0); | 163 ucx_avl_connect(tree, n, e, 0); |
| 150 ucx_avl_balance(tree, n); | 164 ucx_avl_balance(tree, n); |
| 151 return NULL; | 165 return NULL; |
| 153 void *prevval = n->value; | 167 void *prevval = n->value; |
| 154 n->value = value; | 168 n->value = value; |
| 155 return prevval; | 169 return prevval; |
| 156 } | 170 } |
| 157 } else { | 171 } else { |
| 158 tree->root = malloc(sizeof(UcxAVLNode)); | 172 tree->root = almalloc(tree->allocator, sizeof(UcxAVLNode)); |
| 159 tree->root->key = key; tree->root->value = value; | 173 tree->root->key = key; tree->root->value = value; |
| 160 tree->root->height = 1; | 174 tree->root->height = 1; |
| 161 tree->root->parent = tree->root->left = tree->root->right = NULL; | 175 tree->root->parent = tree->root->left = tree->root->right = NULL; |
| 162 return NULL; | 176 return NULL; |
| 163 } | 177 } |
| 179 s = s->left; | 193 s = s->left; |
| 180 } | 194 } |
| 181 ucx_avl_connect(tree, s->parent, s->right, s->key); | 195 ucx_avl_connect(tree, s->parent, s->right, s->key); |
| 182 n->key = s->key; n->value = s->value; | 196 n->key = s->key; n->value = s->value; |
| 183 p = s->parent; | 197 p = s->parent; |
| 198 alfree(tree->allocator, s); | |
| 184 } else { | 199 } else { |
| 185 if (p) { | 200 if (p) { |
| 186 ucx_avl_connect(tree, p, n->right ? n->right:n->left, n->key); | 201 ucx_avl_connect(tree, p, n->right ? n->right:n->left, n->key); |
| 187 } else { | 202 } else { |
| 188 tree->root = n->right ? n->right : n->left; | 203 tree->root = n->right ? n->right : n->left; |
| 189 } | 204 } |
| 190 } | 205 alfree(tree->allocator, n); |
| 191 // TODO: free the correct memory | 206 } |
| 192 | 207 |
| 193 if (p) { | 208 if (p) { |
| 194 ucx_avl_balance(tree, p); | 209 ucx_avl_balance(tree, p); |
| 195 } | 210 } |
| 196 return prevval; | 211 return prevval; |
