0,0 → 1,409 |
/* |
* Copyright 2019, The PLANIX Project |
* |
* Redistribution and use in source and binary forms, with or without |
* modification, are permitted provided that the following conditions are |
* met: |
* |
* 1. Redistributions of source code must retain the above copyright notice, |
* this list of conditions and the following disclaimer. |
* |
* 2. Redistributions in binary form must reproduce the above copyright |
* notice, this list of conditions and the following disclaimer in the |
* documentation and/or other materials provided with the distribution. |
* |
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS |
* IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, |
* THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR |
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR |
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, |
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, |
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF |
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING |
* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS |
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
*/ |
|
#include <string.h> |
|
#include "mavl.h" |
|
static void |
rot_rl(struct mavlnode *n, struct mavlnode **parent) |
{ |
struct mavlnode *tmp; |
*parent = n->right->left; |
n->right->left = (*parent)->right; |
(*parent)->right = n->right; |
tmp = (*parent)->left; |
(*parent)->left = n; |
n->right = tmp; |
} |
|
static void |
rot_lr(struct mavlnode *n, struct mavlnode **parent) |
{ |
struct mavlnode *tmp; |
*parent = n->left->right; |
n->left->right = (*parent)->left; |
(*parent)->left = n->left; |
tmp = (*parent)->right; |
(*parent)->right = n; |
n->left = tmp; |
} |
|
static void |
rot_l(struct mavlnode *n, struct mavlnode **parent) |
{ |
struct mavlnode *tmp; |
*parent = n->right; |
tmp = n->right->left; |
n->right->left = n; |
n->right = tmp; |
} |
|
static void |
rot_r(struct mavlnode *n, struct mavlnode **parent) |
{ |
struct mavlnode *tmp; |
*parent = n->left; |
tmp = n->left->right; |
n->left->right = n; |
n->left = tmp; |
} |
|
static struct mavlnode * |
mavlnode_create(struct mavl *t, const void *data) |
{ |
struct mavlnode *n = t->malloc(sizeof(struct mavlnode) + t->data_size); |
if (!n) |
return NULL; |
|
n->left = n->right = NULL; |
n->bal = 0; |
|
(void)memcpy(mavlnode_dataptr(n), data, t->data_size); |
|
return n; |
} |
|
static int |
mavl_insert0(struct mavl *t, struct mavlnode **parent, const void **data) |
{ |
struct mavlnode *n; |
int rc, bal; |
|
n = *parent; |
rc = t->cmp(*data, mavlnode_dataptr(n)); |
|
if (rc == 0) { |
*data = mavlnode_dataptr(n); |
return 2; |
} |
|
if (rc < 0) { |
if (!n->left) { |
n->left = mavlnode_create(t, *data); |
*data = mavlnode_dataptr(n->left); |
if (!n->left) |
return MAVL_E_NOMEM; |
|
t->count++; |
if (n->right == 0) { |
n->bal = -1; |
return 1; |
} |
n->bal = 0; |
return 0; |
} |
|
/* n->left is not NULL */ |
bal = mavl_insert0(t, &n->left, data); |
|
if (bal > 1) |
return bal; |
|
n->bal -= bal; |
|
if (n->bal == 0) |
return 0; |
|
if (n->bal == -2) { |
if (n->left->bal == -1) { |
n->bal = 0; |
n->left->bal = 0; |
rot_r(n, parent); |
return 0; |
} |
|
if (n->left->bal == 1) { |
rot_lr(n, parent); |
|
if ((*parent)->bal == 1) { |
n->bal = 0; |
n->left->bal = -1; |
|
} else if ((*parent)->bal == -1) { |
n->bal = 1; |
n->left->bal = 0; |
|
} else { |
n->bal = 0; |
n->left->bal = 0; |
} |
|
(*parent)->bal = 0; |
|
return 0; |
|
} |
|
} |
|
return bal; |
|
} |
/* rcs < 0 */ |
if (!n->right) { |
|
n->right = mavlnode_create(t, *data); |
*data = mavlnode_dataptr(n->right); |
|
if (!n->right) |
return MAVL_E_NOMEM; |
|
t->count++; |
n->bal = n->left ? 0 : 1; |
return n->bal; |
} |
|
bal = mavl_insert0(t, &n->right, data); |
|
if (bal > 1) |
return bal; |
|
n->bal += bal; |
|
if (n->bal == 0) |
return 0; |
|
if (n->bal == 2) { |
if (n->right->bal == 1) { |
n->bal = 0; |
n->right->bal = 0; |
rot_l(n, parent); |
return 0; |
|
} else if (n->right->bal == -1) { |
|
rot_rl(n, parent); |
|
if ((*parent)->bal == -1) { |
n->bal = 0; |
n->right->bal = 1; |
|
} else if ((*parent)->bal == 1) { |
n->bal = -1; |
n->right->bal = 0; |
|
} else { |
n->bal = 0; |
n->right->bal = 0; |
} |
|
(*parent)->bal = 0; |
return 0; |
} |
} |
return bal; |
} |
|
void * |
mavl_insert(struct mavl *t, const void *data, int *exists) |
{ |
const void *d; |
int rc; |
|
if (t->root == NULL) { |
t->root = mavlnode_create(t, data); |
|
if (t->root) |
t->count++; |
|
if (exists != NULL) |
*exists = 0; |
return mavlnode_dataptr(t->root); |
} |
|
d = data; |
rc = mavl_insert0(t, &t->root, &d); |
|
if (rc >= 3) |
return NULL; |
|
if (exists != NULL) { |
if (rc == 2) |
*exists = 1; |
else |
*exists = 0; |
} |
return (void *)d; |
} |
|
static int |
adj_bal_l(struct mavlnode *n, struct mavlnode **parent) |
{ |
if (n->right->bal == 1) { |
n->bal = 0; |
n->right->bal = 0; |
rot_l(n, parent); |
return 1; |
} else if (n->right->bal == 0) { |
n->bal = 1; |
n->right->bal = -1; |
rot_l(n, parent); |
return 0; |
} else if (n->right->bal == -1) { |
n->bal = 0; |
n->right->bal = 0; |
n->right->left->bal = 0; |
rot_rl(n, parent); |
return 1; |
} |
return -11; /* that should never happen */ |
} |
|
static int |
adj_bal_r(struct mavlnode *n, struct mavlnode **parent) |
{ |
if (n->left->bal == -1) { |
n->bal = 0; |
n->left->bal = 0; |
rot_r(n, parent); |
return 1; |
} else if (n->left->bal == 0) { |
n->bal = -1; |
n->left->bal = 1; |
rot_r(n, parent); |
return 0; |
} else if (n->left->bal == 1) { |
n->bal = 0; |
n->left->bal = 0; |
n->left->right->bal = 0; |
rot_lr(n, parent); |
return 1; |
} |
return -11; /* that should never happen */ |
} |
|
static int |
mavl_del_lo(struct mavl *t, struct mavlnode **parent, void *data) |
{ |
struct mavlnode *n = *parent; |
|
if (n->left != 0) { |
int bal = mavl_del_lo(t, &n->left, data); |
n->bal += bal; |
if (n->bal == 1) { |
return 0; |
} |
if (n->bal != 2) |
return bal; |
(void)adj_bal_l(n, parent); |
return 0; |
} |
|
/* found the lowest element */ |
|
*parent = n->right; |
(void)memcpy(data, mavlnode_dataptr(n), t->data_size); |
free(n); |
return 1; |
} |
|
int |
mavl_del0(struct mavl *t, struct mavlnode **parent, void *data) |
{ |
struct mavlnode *n = *parent; |
int rc; |
int bal; |
rc = t->cmp(data, mavlnode_dataptr(n)); |
|
if (rc < 0) { |
if (!n->left) |
return MAVL_E_NOTFOUND; /* not found */ |
|
bal = mavl_del0(t, &n->left, data); |
if (bal == 2) |
return 2; |
|
n->bal += bal; |
if (n->bal == 1) |
return 0; |
|
if (n->bal != 2) |
return bal; |
|
return adj_bal_l(n, parent); |
} |
if (rc > 0) { |
if (!n->right) |
return MAVL_E_NOTFOUND; /* not found */ |
|
bal = mavl_del0(t, &n->right, data); |
if (bal == 2) |
return 2; |
|
n->bal -= bal; |
if (n->bal == -1) |
return 0; |
|
if (n->bal != -2) |
return bal; |
|
return adj_bal_r(n, parent); |
} |
|
if (n->right && n->left) { |
/* node has two childs */ |
if (t->del) { |
t->del(mavlnode_dataptr(n)); |
} |
t->count--; |
|
bal = mavl_del_lo(t, &n->right, mavlnode_dataptr(n)); |
n->bal -= bal; |
if (n->bal == -1) |
return 0; |
|
if (n->bal != -2) |
return bal; |
|
return adj_bal_r(n, parent); |
} |
|
*parent = n->right ? n->right : n->left; |
if (t->del) { |
t->del(mavlnode_dataptr(n)); |
} |
free(n); |
t->count--; |
return 1; |
} |
|
void * |
mavl_del(struct mavl *t, const void *data) |
{ |
void *d; |
int rc; |
|
if (!t->root) |
return NULL; |
|
d = (void *)data; |
rc = mavl_del0(t, &t->root, d); |
if (rc == MAVL_E_NOTFOUND) |
return NULL; |
return (void *)data; |
} |