| 92,7 → 92,7 |
|---|
| mavl_insert0(struct mavl *t, struct mavlnode **parent, const void **data) |
| { |
| struct mavlnode *n; |
| int rc, bal; |
| int rc, bal; |
| |
| n = *parent; |
| rc = t->cmp(*data, mavlnode_dataptr(n)); |
| 138,33 → 138,29 |
|---|
| } |
| |
| if (n->left->bal == 1) { |
| rot_lr(n, parent); |
| |
| if ((*parent)->bal == 1) { |
| switch (n->left->right->bal) { |
| case 1: |
| n->bal = 0; |
| n->left->bal = -1; |
| |
| } else if ((*parent)->bal == -1) { |
| break; |
| case -1: |
| break; |
| n->bal = 1; |
| n->left->bal = 0; |
| |
| } else { |
| break; |
| default: |
| n->bal = 0; |
| n->left->bal = 0; |
| } |
| |
| (*parent)->bal = 0; |
| |
| n->left->right->bal = 0; |
| rot_lr(n, parent); |
| return 0; |
| |
| } |
| |
| } |
| |
| return bal; |
| } |
| |
| } |
| /* rcs < 0 */ |
| /* rc is > 0 here */ |
| if (!n->right) { |
| |
| n->right = mavlnode_create(t, *data); |
| 197,22 → 193,22 |
|---|
| |
| } else if (n->right->bal == -1) { |
| |
| rot_rl(n, parent); |
| |
| if ((*parent)->bal == -1) { |
| switch (n->right->left->bal) { |
| case -1: |
| n->bal = 0; |
| n->right->bal = 1; |
| |
| } else if ((*parent)->bal == 1) { |
| break; |
| case 1: |
| n->bal = -1; |
| n->right->bal = 0; |
| |
| } else { |
| break; |
| default: |
| n->bal = 0; |
| n->right->bal = 0; |
| |
| } |
| |
| (*parent)->bal = 0; |
| n->right->left->bal = 0; |
| rot_rl(n, parent); |
| return 0; |
| } |
| } |
| 219,11 → 215,11 |
|---|
| return bal; |
| } |
| |
| void * |
| void * |
| mavl_insert(struct mavl *t, const void *data, int *exists) |
| { |
| const void *d; |
| int rc; |
| const void *d; |
| int rc; |
| |
| if (t->root == NULL) { |
| t->root = mavlnode_create(t, data); |
| 303,7 → 299,7 |
|---|
| struct mavlnode *n = *parent; |
| |
| if (n->left != 0) { |
| int bal = mavl_del_lo(t, &n->left, data); |
| int bal = mavl_del_lo(t, &n->left, data); |
| n->bal += bal; |
| if (n->bal == 1) { |
| return 0; |
| 315,7 → 311,6 |
|---|
| } |
| |
| /* found the lowest element */ |
| |
| *parent = n->right; |
| (void)memcpy(data, mavlnode_dataptr(n), t->data_size); |
| free(n); |
| 326,8 → 321,8 |
|---|
| mavl_del0(struct mavl *t, struct mavlnode **parent, void *data) |
| { |
| struct mavlnode *n = *parent; |
| int rc; |
| int bal; |
| int rc; |
| int bal; |
| rc = t->cmp(data, mavlnode_dataptr(n)); |
| |
| if (rc < 0) { |
| 392,11 → 387,11 |
|---|
| return 1; |
| } |
| |
| void * |
| void * |
| mavl_del(struct mavl *t, const void *data) |
| { |
| void *d; |
| int rc; |
| void *d; |
| int rc; |
| |
| if (!t->root) |
| return NULL; |
| 407,3 → 402,4 |
|---|
| return NULL; |
| return (void *)data; |
| } |
| |