Subversion Repositories PlanixRsrch.SVN

Compare Revisions

Ignore whitespace Rev 1 → Rev 2

/trunk/libmavl/mavl.c
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;
}