comparison: ucx/avl.c
ucx/avl.c
- changeset 195
- bec61f067ea0
- parent 194
- 0c1b7676e74c
- child 196
- 1b4cdafef2eb
equal
deleted
inserted
replaced
| 194:0c1b7676e74c | 195:bec61f067ea0 |
|---|---|
| 26 * POSSIBILITY OF SUCH DAMAGE. | 26 * POSSIBILITY OF SUCH DAMAGE. |
| 27 */ | 27 */ |
| 28 | 28 |
| 29 #include "avl.h" | 29 #include "avl.h" |
| 30 | 30 |
| 31 #define ptrcast(ptr) ((void*)(ptr)) | |
| 32 | |
| 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 } | |
| 50 | |
| 51 #define avlheight(node) ((node) ? (node)->height : 0) | |
| 52 | |
| 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 } | |
| 65 | |
| 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 } | |
| 78 | |
| 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); | |
| 83 | |
| 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 } | |
| 97 | |
| 98 if (n->parent) { | |
| 99 ucx_avl_balance(tree, n->parent); | |
| 100 } else { | |
| 101 tree->root = n; | |
| 102 } | |
| 103 } | |
| 104 | |
| 31 UcxAVLTree *ucx_avl_new(cmp_func cmpfunc) { | 105 UcxAVLTree *ucx_avl_new(cmp_func cmpfunc) { |
| 32 return ucx_avl_new_a(cmpfunc, ucx_default_allocator()); | 106 return ucx_avl_new_a(cmpfunc, ucx_default_allocator()); |
| 33 } | 107 } |
| 34 | 108 |
| 35 UcxAVLTree *ucx_avl_new_a(cmp_func cmpfunc, UcxAllocator *allocator) { | 109 UcxAVLTree *ucx_avl_new_a(cmp_func cmpfunc, UcxAllocator *allocator) { |
| 43 | 117 |
| 44 return tree; | 118 return tree; |
| 45 } | 119 } |
| 46 | 120 |
| 47 void *ucx_avl_get(UcxAVLTree *tree, intptr_t key) { | 121 void *ucx_avl_get(UcxAVLTree *tree, intptr_t key) { |
| 48 return NULL; | 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; | |
| 49 } | 129 } |
| 50 | 130 |
| 51 void* ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value) { | 131 void* ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value) { |
| 52 return NULL; | 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 } | |
| 144 | |
| 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 } | |
| 53 } | 164 } |
| 54 | 165 |
| 55 void* ucx_avl_remove(UcxAVLTree *tree, intptr_t key) { | 166 void* ucx_avl_remove(UcxAVLTree *tree, intptr_t key) { |
| 56 return NULL; | 167 UcxAVLNode *n = tree->root; |
| 57 } | 168 int cmpresult; |
| 58 | 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 | |
| 192 | |
| 193 if (p) { | |
| 194 ucx_avl_balance(tree, p); | |
| 195 } | |
| 196 return prevval; | |
| 197 } else { | |
| 198 return NULL; | |
| 199 } | |
| 200 } | |
| 201 |
