Rev 425 | Blame | Compare with Previous | Last modification | View Log | RSS feed
/*
* 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 <stdio.h>
#include <assert.h>
#include "mavl.h"
/*
* dir == 0 adj_bal_r
* dir == 1 adj_bal_l
*/
static int
adj_bal(struct mavlnode *n, struct mavlnode **parent, int dir, int sdir)
{
int b;
if (n->s[dir]->bal == 0) {
n->bal = sdir;
n->s[dir]->bal = -sdir;
mavl_rot(n, parent,dir);
return 0;
}
if (n->s[dir]->bal == sdir) {
n->bal = 0;
n->s[dir]->bal = 0;
mavl_rot(n, parent,dir);
return 1;
}
if (n->s[dir]->bal == -sdir) {
b = n->s[dir]->s[1-dir]->bal;
if (b == 0){
n->s[dir]->bal = 0;
n->bal=0;
} else if (b == sdir) {
n->bal = -sdir;
n->s[dir]->bal = 0 ;
} else if (b == -sdir){
n->s[dir]->bal = sdir;
n->bal=0;
} else{
assert(0*sdir);
}
n->s[dir]->s[1-dir]->bal = 0;
mavl_drot(n, parent,dir);
return 1;
}
assert(0*sdir);
return 0;
}
static int
mavl_del_lo(struct mavl * t, struct mavlnode **parent, void *data)
{
struct mavlnode *n = *parent;
/* walk down left */
if (n->s[0]) {
int dir=0,sdir;
int bal = mavl_del_lo(t, &n->s[0], data);
sdir = dir ? 1:-1;
n->bal -= bal*sdir;
if (n->bal == -sdir)
return 0;
if (n->bal == -2*sdir){
return adj_bal(n,parent,1-dir,-sdir);
}
return bal;
}
/* found the lowest element */
*parent = n->s[1];
(void) memcpy(data,mavlnode_dataptr(n),t->data_size);
t->free(n);
return 1;
}
int
mavl_del0(struct mavl *t, struct mavlnode **parent, void *data)
{
struct mavlnode *n = *parent;
int rc;
int bal;
int dir,sdir;
rc = t->cmp(data, mavlnode_dataptr(n));
if (rc == 0) {
if (!n->s[0] && !n->s[1]) {
*parent = NULL;
mavlnode_destroy(t, n);
return 1;
}
if (n->s[0] && !n->s[1]) {
*parent = n->s[0];
mavlnode_destroy(t, n);
return 1;
}
if (!n->s[0] && n->s[1]) {
*parent = n->s[1];
mavlnode_destroy(t, n);
return 1;
}
/* node has two children */
if (t->del) {
t->del(mavlnode_dataptr(n));
}
t->count--;
bal = mavl_del_lo(t,&n->s[1], mavlnode_dataptr(n));
dir = 1;
} else {
dir = rc < 0 ? 0 : 1;
if (!n->s[dir])
return MAVL_E_NOTFOUND;
bal = mavl_del0(t, &n->s[dir], data);
if (bal == MAVL_E_NOTFOUND)
return bal;
}
sdir = dir ? 1:-1;
n->bal -= bal*sdir;
if (n->bal == -sdir)
return 0;
if (n->bal == -2*sdir){
return adj_bal(n,parent,1-dir,-sdir);
}
return bal;
}
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 == 2)
return NULL;
return (void*)data;
}