comparison: ucx/avl.c
ucx/avl.c
- changeset 216
- dee5a88c4db7
- parent 205
- 54a7ceb9151f
- child 225
- a1a068c2c4ef
equal
deleted
inserted
replaced
| 215:e0853e077770 | 216:dee5a88c4db7 |
|---|---|
| 27 */ | 27 */ |
| 28 | 28 |
| 29 #include "avl.h" | 29 #include "avl.h" |
| 30 | 30 |
| 31 #define ptrcast(ptr) ((void*)(ptr)) | 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)) | |
| 32 | 34 |
| 33 static void ucx_avl_connect(UcxAVLTree *tree, | 35 static void ucx_avl_connect(UcxAVLTree *tree, |
| 34 UcxAVLNode *node, UcxAVLNode *child, intptr_t nullkey) { | 36 UcxAVLNode *node, UcxAVLNode *child, intptr_t nullkey) { |
| 35 if (child) { | 37 if (child) { |
| 36 child->parent = node; | 38 child->parent = node; |
| 105 UcxAVLTree *ucx_avl_new(cmp_func cmpfunc) { | 107 UcxAVLTree *ucx_avl_new(cmp_func cmpfunc) { |
| 106 return ucx_avl_new_a(cmpfunc, ucx_default_allocator()); | 108 return ucx_avl_new_a(cmpfunc, ucx_default_allocator()); |
| 107 } | 109 } |
| 108 | 110 |
| 109 UcxAVLTree *ucx_avl_new_a(cmp_func cmpfunc, UcxAllocator *allocator) { | 111 UcxAVLTree *ucx_avl_new_a(cmp_func cmpfunc, UcxAllocator *allocator) { |
| 110 UcxAVLTree *tree = almalloc(allocator, sizeof(UcxAVLTree)); | 112 UcxAVLTree* tree = alloc_tree(allocator); |
| 111 if (tree) { | 113 if (tree) { |
| 112 tree->allocator = allocator; | 114 tree->allocator = allocator; |
| 113 tree->cmpfunc = cmpfunc; | 115 tree->cmpfunc = cmpfunc; |
| 114 tree->root = NULL; | 116 tree->root = NULL; |
| 115 tree->userdata = NULL; | 117 tree->userdata = NULL; |
| 165 break; | 167 break; |
| 166 } | 168 } |
| 167 } | 169 } |
| 168 | 170 |
| 169 if (cmpresult) { | 171 if (cmpresult) { |
| 170 UcxAVLNode *e = almalloc(tree->allocator, sizeof(UcxAVLNode)); | 172 UcxAVLNode* e = alloc_node(tree->allocator); |
| 171 if (e) { | 173 if (e) { |
| 172 e->key = key; e->value = value; e->height = 1; | 174 e->key = key; e->value = value; e->height = 1; |
| 173 e->parent = e->left = e->right = NULL; | 175 e->parent = e->left = e->right = NULL; |
| 174 ucx_avl_connect(tree, n, e, 0); | 176 ucx_avl_connect(tree, n, e, 0); |
| 175 ucx_avl_balance(tree, n); | 177 ucx_avl_balance(tree, n); |
| 183 } | 185 } |
| 184 n->value = value; | 186 n->value = value; |
| 185 return 0; | 187 return 0; |
| 186 } | 188 } |
| 187 } else { | 189 } else { |
| 188 tree->root = almalloc(tree->allocator, sizeof(UcxAVLNode)); | 190 tree->root = alloc_node(tree->allocator); |
| 189 if (tree->root) { | 191 if (tree->root) { |
| 190 tree->root->key = key; tree->root->value = value; | 192 tree->root->key = key; tree->root->value = value; |
| 191 tree->root->height = 1; | 193 tree->root->height = 1; |
| 192 tree->root->parent = tree->root->left = tree->root->right = NULL; | 194 tree->root->parent = tree->root->left = tree->root->right = NULL; |
| 193 | 195 |
