dttree.c revision 34f9b3eef6fdadbda0a846aa4d68691ac40eace5
/***********************************************************************
* *
* This software is part of the ast package *
* Copyright (c) 1985-2009 AT&T Intellectual Property *
* and is licensed under the *
* Common Public License, Version 1.0 *
* by AT&T Intellectual Property *
* *
* A copy of the License is available at *
* http://www.opensource.org/licenses/cpl1.0.txt *
* (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9) *
* *
* Information and Software Systems Research *
* AT&T Research *
* Florham Park NJ *
* *
* Glenn Fowler <gsf@research.att.com> *
* David Korn <dgk@research.att.com> *
* Phong Vo <kpv@research.att.com> *
* *
***********************************************************************/
#include "dthdr.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)
*/
#if __STD_C
static Void_t* dttree(Dt_t* dt, Void_t* obj, int type)
#else
static Void_t* dttree(dt,obj,type)
Dt_t* dt;
Void_t* obj;
int type;
#endif
{
Dtlink_t *root, *t;
int cmp, lk, sz, ky;
Void_t *o, *k, *key;
Dtlink_t *l, *r, *me, link;
int n, minp, turn[DT_MINP];
Dtcompar_f cmpf;
Dtdisc_t* disc;
UNFLATTEN(dt);
disc = dt->disc; _DTDSC(disc,ky,sz,lk,cmpf);
dt->type &= ~DT_FOUND;
root = dt->data->here;
if(!obj)
{ if(!root || !(type&(DT_CLEAR|DT_FIRST|DT_LAST)) )
return NIL(Void_t*);
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)(dt,_DTOBJ(root,lk),disc);
if(disc->link < 0)
(*dt->memoryf)(dt,(Void_t*)root,0,disc);
} while((root = t) );
}
dt->data->size = 0;
dt->data->here = NIL(Dtlink_t*);
return NIL(Void_t*);
}
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(dt,key,k,disc,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|DT_ATTACH))
{ key = (type&DT_MATCH) ? obj : _DTKEY(obj,ky,sz);
if(root)
goto do_search;
}
else if(type&DT_RENEW)
{ me = (Dtlink_t*)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:
if(dt->meth->type == DT_OSET &&
(minp = dt->data->minp) != 0 && (type&(DT_MATCH|DT_SEARCH)) )
{ /* simple search, note that minp should be even */
for(t = root, n = 0; n < minp; ++n)
{ k = _DTOBJ(t,lk); k = _DTKEY(k,ky,sz);
if((cmp = _DTCMP(dt,key,k,disc,cmpf,sz)) == 0)
return _DTOBJ(t,lk);
else
{ turn[n] = cmp;
if(!(t = cmp < 0 ? t->left : t->right) )
return NIL(Void_t*);
}
}
/* exceed search length, top-down splay now */
for(n = 0; n < minp; n += 2)
{ if(turn[n] < 0)
{ t = root->left;
if(turn[n+1] < 0)
{ rrotate(root,t);
rlink(r,t);
root = t->left;
}
else
{ llink(l,t);
rlink(r,root);
root = t->right;
}
}
else
{ t = root->right;
if(turn[n+1] > 0)
{ lrotate(root,t);
llink(l,t);
root = t->right;
}
else
{ rlink(r,t);
llink(l,root);
root = t->left;
}
}
}
}
while(1)
{ k = _DTOBJ(root,lk); k = _DTKEY(k,ky,sz);
if((cmp = _DTCMP(dt,key,k,disc,cmpf,sz)) == 0)
break;
else if(cmp < 0)
{ if((t = root->left) )
{ k = _DTOBJ(t,lk); k = _DTKEY(k,ky,sz);
if((cmp = _DTCMP(dt,key,k,disc,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 = NIL(Dtlink_t*);
break;
}
}
else /* if(cmp > 0) */
{ if((t = root->right) )
{ k = _DTOBJ(t,lk); k = _DTKEY(k,ky,sz);
if((cmp = _DTCMP(dt,key,k,disc,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 = NIL(Dtlink_t*);
break;
}
}
}
}
if(root)
{ /* found it, now isolate it */
dt->type |= DT_FOUND;
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(dt,key,k,disc,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 = NIL(Dtlink_t*);
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 = NIL(Dtlink_t*);
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)(dt,obj,disc);
if(disc->link < 0)
(*dt->memoryf)(dt,(Void_t*)root,0,disc);
if((dt->data->size -= 1) < 0)
dt->data->size = -1;
goto no_root;
}
else if(type&(DT_INSERT|DT_ATTACH))
{ if(dt->meth->type&DT_OSET)
goto has_root;
else
{ root->left = NIL(Dtlink_t*);
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)(dt,obj,disc);
if(disc->link < 0)
(*dt->memoryf)(dt,(Void_t*)me,0,disc);
}
else
{ me->left = NIL(Dtlink_t*);
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 = NIL(Dtlink_t*);
l->right = NIL(Dtlink_t*);
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 : NIL(Void_t*);
}
else if(type&(DT_INSERT|DT_ATTACH))
{ dt_insert:
if(disc->makef && (type&DT_INSERT))
obj = (*disc->makef)(dt,obj,disc);
if(obj)
{ if(lk >= 0)
root = _DTLNK(obj,lk);
else
{ root = (Dtlink_t*)(*dt->memoryf)
(dt,NIL(Void_t*),sizeof(Dthold_t),disc);
if(root)
((Dthold_t*)root)->obj = obj;
else if(disc->makef && disc->freef &&
(type&DT_INSERT))
(*disc->freef)(dt,obj,disc);
}
}
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 = NIL(Void_t*);
goto no_root;
}
}
return NIL(Void_t*);
}
/* make this method available */
static Dtmethod_t _Dtoset = { dttree, DT_OSET };
static Dtmethod_t _Dtobag = { dttree, DT_OBAG };
__DEFINE__(Dtmethod_t*,Dtoset,&_Dtoset);
__DEFINE__(Dtmethod_t*,Dtobag,&_Dtobag);
#ifndef KPVDEL /* backward compatibility - delete next time around */
Dtmethod_t _Dttree = { dttree, DT_OSET };
__DEFINE__(Dtmethod_t*,Dtorder,&_Dttree);
__DEFINE__(Dtmethod_t*,Dttree,&_Dttree);
#endif
#ifdef NoF
NoF(dttree)
#endif