Subversion Repositories PlanixRsrch.SVN

/*
 * 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;
}