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 "mavl.h"

void
mavl_rot(struct mavlnode *n, struct mavlnode **parent, int dir)
{
        struct mavlnode *tmp;
        *parent = n->s[dir];
        tmp = n->s[dir]->s[1-dir]; 
        n->s[dir]->s[1-dir]=n;
        n->s[dir]=tmp;
}

void
mavl_drot(struct mavlnode *n, struct mavlnode **parent, int dir)
{
        mavl_rot(n->s[dir],&n->s[dir],1-dir);
        mavl_rot(n,parent,dir);
}

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->s[0] = n->s[1] = 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,b;
        int dir,sdir;

        if (*parent==NULL){
                *parent = mavlnode_create(t, *data);
                *data = mavlnode_dataptr(*parent);
                if (*parent==NULL)
                        return MAVL_E_NOMEM;
                t->count++;
                return 1;
        }

        n = *parent;
        rc = t->cmp(*data, mavlnode_dataptr(n));

        if (rc == 0) {
                *data = mavlnode_dataptr(n);
                return 2;
        }

        dir = rc>0 ? 1:0;

        /* rc is > 0  here */
        bal = mavl_insert0(t, &n->s[dir], data);

        if (bal > 1)
                return bal;

        sdir = dir ? 1:-1;
        n->bal += bal*sdir;

        if (n->bal == 0)
                return 0;

        if (n->bal == 2*sdir) {
                if (n->s[dir]->bal == sdir) {
                        n->bal = 0;
                        n->s[dir]->bal = 0;
                        mavl_rot(n, parent,dir);
                        return 0;
                } 
                
                b = n->s[dir]->s[1-dir]->bal;
                if (b==-sdir){
                        n->bal = 0;
                        n->s[dir]->bal = sdir;
                }else if (b==sdir){
                        n->bal = -sdir;
                        n->s[dir]->bal = 0;
                }else{
                        n->bal = 0;
                        n->s[dir]->bal = 0;
                }

                n->s[dir]->s[1-dir]->bal = 0;
                mavl_drot(n, parent,dir);
                return 0;
        }
        return bal;
}

void *
mavl_insert(struct mavl *t, const void *data, int *exists)
{
        const void *d;
        int rc;

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