dttree.c

Go to the documentation of this file.

#include        <cdt/dthdr.h>
#include        <stdlib.h>
 
/*      Ordered set/multiset
**      dt:     dictionary being searched
**      obj:    the object to look for.
**      type:   search type.
**
**      Written by Kiem-Phong Vo (5/25/96)
*/
 
static void* dttree(Dt_t* dt, void* obj, int type)
{
        Dtlink_t        *root, *t;
        int             cmp, lk, sz, ky;
        void            *o, *k, *key;
        Dtlink_t        *l, *r, *me = NULL, link;
        Dtcompar_f      cmpf;
        Dtdisc_t*       disc;
 
        UNFLATTEN(dt);
        disc = dt->disc; _DTDSC(disc,ky,sz,lk,cmpf);
 
        root = dt->data->here;
        if(!obj)
        {       if(!root || !(type&(DT_CLEAR|DT_FIRST|DT_LAST)) )
                        return NULL;
 
                if(type&DT_CLEAR) /* delete all objects */
                {       if(disc->freef || disc->link < 0)
                        {       do
                                {       while((t = root->left) )
                                                RROTATE(root,t);
                                        t = root->right;
                                        if(disc->freef)
                                                disc->freef(_DTOBJ(root, lk));
                                        if(disc->link < 0)
                                                free(root);
                                } while((root = t) );
                        }
 
                        dt->data->size = 0;
                        dt->data->here = NULL;
                        return NULL;
                }
                else /* computing largest/smallest element */
                {       if(type&DT_LAST)
                        {       while((t = root->right) )
                                        LROTATE(root,t);
                        }
                        else /* type&DT_FIRST */
                        {       while((t = root->left) )
                                        RROTATE(root,t);
                        }
 
                        dt->data->here = root;
                        return _DTOBJ(root,lk);
                }
        }
 
        /* note that link.right is LEFT tree and link.left is RIGHT tree */
        l = r = &link;
 
        /* allow apps to delete an object "actually" in the dictionary */
        if(dt->meth->type == DT_OBAG && (type&(DT_DELETE|DT_DETACH)) )
        {       key = _DTKEY(obj,ky,sz);
                for(o = dtsearch(dt,obj); o; o = dtnext(dt,o) )
                {       k = _DTKEY(o,ky,sz);
                        if(_DTCMP(key, k, cmpf, sz) != 0)
                                break;
                        if(o == obj)
                        {       root = dt->data->here;
                                l->right = root->left;
                                r->left  = root->right;
                                goto dt_delete;
                        }
                }
        }
 
        if(type&(DT_MATCH|DT_SEARCH|DT_INSERT))
        {       key = (type&DT_MATCH) ? obj : _DTKEY(obj,ky,sz);
                if(root)
                        goto do_search;
        }
        else if(type&DT_RENEW)
        {       me = obj;
                obj = _DTOBJ(me,lk);
                key = _DTKEY(obj,ky,sz);
                if(root)
                        goto do_search;
        }
        else if(root && _DTOBJ(root,lk) != obj)
        {       key = _DTKEY(obj,ky,sz);
        do_search:
                while(1)
                {       k = _DTOBJ(root,lk); k = _DTKEY(k,ky,sz);
                        if((cmp = _DTCMP(key, k, cmpf, sz)) == 0)
                                break;
                        else if(cmp < 0)
                        {       if((t = root->left) )
                                {       k = _DTOBJ(t,lk); k = _DTKEY(k,ky,sz);
                                        if((cmp = _DTCMP(key, k, cmpf, sz)) < 0)
                                        {       rrotate(root,t);
                                                rlink(r,t);
                                                if(!(root = t->left) )
                                                        break;
                                        }
                                        else if(cmp == 0)
                                        {       rlink(r,root);
                                                root = t;
                                                break;
                                        }
                                        else /* if(cmp > 0) */
                                        {       llink(l,t);
                                                rlink(r,root);
                                                if(!(root = t->right) )
                                                        break;
                                        }
                                }
                                else
                                {       rlink(r,root);
                                        root = NULL;
                                        break;
                                }
                        }
                        else /* if(cmp > 0) */
                        {       if((t = root->right) )
                                {       k = _DTOBJ(t,lk); k = _DTKEY(k,ky,sz);
                                        if((cmp = _DTCMP(key, k, cmpf, sz)) > 0)
                                        {       lrotate(root,t);
                                                llink(l,t);
                                                if(!(root = t->right) )
                                                        break;
                                        }
                                        else if(cmp == 0)
                                        {       llink(l,root);
                                                root = t;
                                                break;
                                        }
                                        else /* if(cmp < 0) */
                                        {       rlink(r,t);
                                                llink(l,root);
                                                if(!(root = t->left) )
                                                        break;
                                        }
                                }
                                else
                                {       llink(l,root);
                                        root = NULL;
                                        break;
                                }
                        }
                }
        }
 
        if(root)
        {       /* found it, now isolate it */
                l->right = root->left;
                r->left = root->right;
 
                if(type&(DT_SEARCH|DT_MATCH))
                { has_root:
                        root->left = link.right;
                        root->right = link.left;
                        if((dt->meth->type&DT_OBAG) && (type&(DT_SEARCH|DT_MATCH)) )
                        {       key = _DTOBJ(root,lk); key = _DTKEY(key,ky,sz);
                                while((t = root->left) )
                                {       /* find max of left subtree */
                                        while((r = t->right) )
                                                LROTATE(t,r);
                                        root->left = t;
 
                                        /* now see if it's in the same group */
                                        k = _DTOBJ(t,lk); k = _DTKEY(k,ky,sz);
                                        if(_DTCMP(key, k, cmpf, sz) != 0)
                                                break;
                                        RROTATE(root,t);
                                }
                        }
                        dt->data->here = root;
                        return _DTOBJ(root,lk);
                }
                else if(type&DT_NEXT)
                {       root->left = link.right;
                        root->right = NULL;
                        link.right = root;
                dt_next:
                        if((root = link.left) ) 
                        {       while((t = root->left) )
                                        RROTATE(root,t);
                                link.left = root->right;
                                goto has_root;
                        }
                        else    goto no_root;
                }
                else if(type&DT_PREV)
                {       root->right = link.left;
                        root->left = NULL;
                        link.left = root;
                dt_prev:
                        if((root = link.right) )
                        {       while((t = root->right) )
                                        LROTATE(root,t);
                                link.right = root->left;
                                goto has_root;
                        }
                        else    goto no_root;
                }
                else if(type&(DT_DELETE|DT_DETACH))
                {       /* taking an object out of the dictionary */
                dt_delete:
                        obj = _DTOBJ(root,lk);
                        if(disc->freef && (type&DT_DELETE))
                                disc->freef(obj);
                        if(disc->link < 0)
                                free(root);
                        if((dt->data->size -= 1) < 0)
                                dt->data->size = -1;
                        goto no_root;
                }
                else if(type&DT_INSERT)
                {       if(dt->meth->type&DT_OSET)
                                goto has_root;
                        else
                        {       root->left = NULL;
                                root->right = link.left;
                                link.left = root;
                                goto dt_insert;
                        }
                }
                else if(type&DT_RENEW) /* a duplicate */
                {       if(dt->meth->type&DT_OSET)
                        {       if(disc->freef)
                                        disc->freef(obj);
                                if(disc->link < 0)
                                        free(me);
                        }
                        else
                        {       me->left = NULL;
                                me->right = link.left;
                                link.left = me;
                                dt->data->size += 1;
                        }
                        goto has_root;
                }
        }
        else
        {       /* not found, finish up LEFT and RIGHT trees */
                r->left = NULL;
                l->right = NULL;
 
                if(type&DT_NEXT)
                        goto dt_next;
                else if(type&DT_PREV)
                        goto dt_prev;
                else if(type&(DT_SEARCH|DT_MATCH))
                { no_root:
                        while((t = r->left) )
                                r = t;
                        r->left = link.right;
                        dt->data->here = link.left;
                        return (type&DT_DELETE) ? obj : NULL;
                }
                else if(type&DT_INSERT)
                { dt_insert:
                        if(disc->makef && (type&DT_INSERT))
                                obj = disc->makef(obj, disc);
                        if(obj)
                        {       if(lk >= 0)
                                        root = _DTLNK(obj,lk);
                                else
                                {       root = malloc(sizeof(Dthold_t));
                                        if(root)
                                                ((Dthold_t*)root)->obj = obj;
                                        else if(disc->makef && disc->freef &&
                                                (type&DT_INSERT))
                                                disc->freef(obj);
                                }
                        }
                        if(root)
                        {       if(dt->data->size >= 0)
                                        dt->data->size += 1;
                                goto has_root;
                        }
                        else    goto no_root;
                }
                else if(type&DT_RENEW)
                {       root = me;
                        dt->data->size += 1;
                        goto has_root;
                }
                else /*if(type&DT_DELETE)*/
                {       obj = NULL;
                        goto no_root;
                }
        }
 
        return NULL;
}
 
/* make this method available */
static Dtmethod_t       _Dtoset =  { dttree, DT_OSET };
static Dtmethod_t       _Dtobag =  { dttree, DT_OBAG };
Dtmethod_t* Dtoset = &_Dtoset;
Dtmethod_t* Dtobag = &_Dtobag;
 
Dtmethod_t              _Dttree = { dttree, DT_OSET };
Dtmethod_t* Dttree = &_Dttree;