da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/***********************************************************************
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* This software is part of the ast package *
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner* Copyright (c) 1985-2010 AT&T Intellectual Property *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* and is licensed under the *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Common Public License, Version 1.0 *
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin* by AT&T Intellectual Property *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* A copy of the License is available at *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* http://www.opensource.org/licenses/cpl1.0.txt *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9) *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Information and Software Systems Research *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* AT&T Research *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Florham Park NJ *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Glenn Fowler <gsf@research.att.com> *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* David Korn <dgk@research.att.com> *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Phong Vo <kpv@research.att.com> *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin***********************************************************************/
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#include "dthdr.h"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/* Set a view path from dict to view.
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin**
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin** Written by Kiem-Phong Vo (5/25/96)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin*/
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#if __STD_C
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinstatic Void_t* dtvsearch(Dt_t* dt, reg Void_t* obj, reg int type)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#else
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinstatic Void_t* dtvsearch(dt,obj,type)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinDt_t* dt;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinreg Void_t* obj;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinreg int type;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#endif
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin{
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Dt_t *d, *p;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Void_t *o, *n, *ok, *nk;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin int cmp, lk, sz, ky;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Dtcompar_f cmpf;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin /* these operations only happen at the top level */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if(type&(DT_INSERT|DT_DELETE|DT_CLEAR|DT_RENEW))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin return (*(dt->meth->searchf))(dt,obj,type);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if((type&(DT_MATCH|DT_SEARCH)) || /* order sets first/last done below */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin ((type&(DT_FIRST|DT_LAST)) && !(dt->meth->type&(DT_OBAG|DT_OSET)) ) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin { for(d = dt; d; d = d->view)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if((o = (*(d->meth->searchf))(d,obj,type)) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin break;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin dt->walk = d;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin return o;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if(dt->meth->type & (DT_OBAG|DT_OSET) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin { if(!(type & (DT_FIRST|DT_LAST|DT_NEXT|DT_PREV)) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin return NIL(Void_t*);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin n = nk = NIL(Void_t*); p = NIL(Dt_t*);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin for(d = dt; d; d = d->view)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin { if(!(o = (*d->meth->searchf)(d, obj, type)) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin continue;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin _DTDSC(d->disc,ky,sz,lk,cmpf);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin ok = _DTKEY(o,ky,sz);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if(n) /* get the right one among all dictionaries */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin { cmp = _DTCMP(d,ok,nk,d->disc,cmpf,sz);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if(((type & (DT_NEXT|DT_FIRST)) && cmp < 0) ||
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin ((type & (DT_PREV|DT_LAST)) && cmp > 0) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin goto a_dj;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin else /* looks good for now */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin { a_dj: p = d;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin n = o;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin nk = ok;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin dt->walk = p;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin return n;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin /* non-ordered methods */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if(!(type & (DT_NEXT|DT_PREV)) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin return NIL(Void_t*);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if(!dt->walk || obj != _DTOBJ(dt->walk->data->here, dt->walk->disc->link) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin { for(d = dt; d; d = d->view)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if((o = (*(d->meth->searchf))(d, obj, DT_SEARCH)) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin break;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin dt->walk = d;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if(!(obj = o) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin return NIL(Void_t*);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin for(d = dt->walk, obj = (*d->meth->searchf)(d, obj, type);; )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin { while(obj) /* keep moving until finding an uncovered object */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin { for(p = dt; ; p = p->view)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin { if(p == d) /* adjacent object is uncovered */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin return obj;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if((*(p->meth->searchf))(p, obj, DT_SEARCH) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin break;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin obj = (*d->meth->searchf)(d, obj, type);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if(!(d = dt->walk = d->view) ) /* move on to next dictionary */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin return NIL(Void_t*);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin else if(type&DT_NEXT)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin obj = (*(d->meth->searchf))(d,NIL(Void_t*),DT_FIRST);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin else obj = (*(d->meth->searchf))(d,NIL(Void_t*),DT_LAST);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin}
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#if __STD_C
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinDt_t* dtview(reg Dt_t* dt, reg Dt_t* view)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#else
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinDt_t* dtview(dt,view)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinreg Dt_t* dt;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinreg Dt_t* view;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#endif
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin{
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin reg Dt_t* d;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin UNFLATTEN(dt);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if(view)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin { UNFLATTEN(view);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if(view->meth != dt->meth) /* must use the same method */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin return NIL(Dt_t*);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin /* make sure there won't be a cycle */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin for(d = view; d; d = d->view)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if(d == dt)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin return NIL(Dt_t*);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin /* no more viewing lower dictionary */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if((d = dt->view) )
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin d->nview -= 1;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin dt->view = dt->walk = NIL(Dt_t*);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if(!view)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin { dt->searchf = dt->meth->searchf;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin return d;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin /* ok */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin dt->view = view;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin dt->searchf = dtvsearch;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin view->nview += 1;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin return view;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin}