1da2e3ebdSchin /***********************************************************************
2da2e3ebdSchin * *
3da2e3ebdSchin * This software is part of the ast package *
4*b30d1939SAndy Fiddaman * Copyright (c) 1985-2011 AT&T Intellectual Property *
5da2e3ebdSchin * and is licensed under the *
6*b30d1939SAndy Fiddaman * Eclipse Public License, Version 1.0 *
77c2fbfb3SApril Chin * by AT&T Intellectual Property *
8da2e3ebdSchin * *
9da2e3ebdSchin * A copy of the License is available at *
10*b30d1939SAndy Fiddaman * http://www.eclipse.org/org/documents/epl-v10.html *
11*b30d1939SAndy Fiddaman * (with md5 checksum b35adb5213ca9657e911e9befb180842) *
12da2e3ebdSchin * *
13da2e3ebdSchin * Information and Software Systems Research *
14da2e3ebdSchin * AT&T Research *
15da2e3ebdSchin * Florham Park NJ *
16da2e3ebdSchin * *
17da2e3ebdSchin * Glenn Fowler <gsf@research.att.com> *
18da2e3ebdSchin * David Korn <dgk@research.att.com> *
19da2e3ebdSchin * Phong Vo <kpv@research.att.com> *
20da2e3ebdSchin * *
21da2e3ebdSchin ***********************************************************************/
22da2e3ebdSchin #include "dthdr.h"
23da2e3ebdSchin
24da2e3ebdSchin /* Set a view path from dict to view.
25da2e3ebdSchin **
26da2e3ebdSchin ** Written by Kiem-Phong Vo (5/25/96)
27da2e3ebdSchin */
28da2e3ebdSchin
29*b30d1939SAndy Fiddaman /* these operations must be done without viewpathing */
30*b30d1939SAndy Fiddaman #define DT_NOVIEWPATH (DT_INSERT|DT_APPEND|DT_DELETE|\
31*b30d1939SAndy Fiddaman DT_ATTACH|DT_DETACH|DT_RELINK|DT_CLEAR| \
32*b30d1939SAndy Fiddaman DT_FLATTEN|DT_EXTRACT|DT_RESTORE|DT_STAT)
33da2e3ebdSchin
34da2e3ebdSchin #if __STD_C
dtvsearch(Dt_t * dt,reg Void_t * obj,reg int type)35da2e3ebdSchin static Void_t* dtvsearch(Dt_t* dt, reg Void_t* obj, reg int type)
36da2e3ebdSchin #else
37da2e3ebdSchin static Void_t* dtvsearch(dt,obj,type)
38da2e3ebdSchin Dt_t* dt;
39da2e3ebdSchin reg Void_t* obj;
40da2e3ebdSchin reg int type;
41da2e3ebdSchin #endif
42da2e3ebdSchin {
43*b30d1939SAndy Fiddaman int cmp;
44da2e3ebdSchin Dt_t *d, *p;
45*b30d1939SAndy Fiddaman Void_t *o, *n, *oky, *nky;
46da2e3ebdSchin
47*b30d1939SAndy Fiddaman if(type&DT_NOVIEWPATH)
48da2e3ebdSchin return (*(dt->meth->searchf))(dt,obj,type);
49da2e3ebdSchin
50*b30d1939SAndy Fiddaman o = NIL(Void_t*);
51*b30d1939SAndy Fiddaman
52*b30d1939SAndy Fiddaman /* these ops look for the first appearance of an object of the right type */
53*b30d1939SAndy Fiddaman if((type & (DT_MATCH|DT_SEARCH)) ||
54*b30d1939SAndy Fiddaman ((type & (DT_FIRST|DT_LAST|DT_ATLEAST|DT_ATMOST)) && !(dt->meth->type&DT_ORDERED) ) )
55da2e3ebdSchin { for(d = dt; d; d = d->view)
56da2e3ebdSchin if((o = (*(d->meth->searchf))(d,obj,type)) )
57da2e3ebdSchin break;
58da2e3ebdSchin dt->walk = d;
59da2e3ebdSchin return o;
60da2e3ebdSchin }
61da2e3ebdSchin
62*b30d1939SAndy Fiddaman if(dt->meth->type & DT_ORDERED) /* ordered sets/bags */
63*b30d1939SAndy Fiddaman { if(!(type & (DT_FIRST|DT_LAST|DT_NEXT|DT_PREV|DT_ATLEAST|DT_ATMOST)) )
64da2e3ebdSchin return NIL(Void_t*);
65da2e3ebdSchin
66*b30d1939SAndy Fiddaman /* find the min/max element that satisfies the op requirement */
67*b30d1939SAndy Fiddaman n = nky = NIL(Void_t*); p = NIL(Dt_t*);
68da2e3ebdSchin for(d = dt; d; d = d->view)
69da2e3ebdSchin { if(!(o = (*d->meth->searchf)(d, obj, type)) )
70da2e3ebdSchin continue;
71*b30d1939SAndy Fiddaman oky = _DTKEY(d->disc,o);
72da2e3ebdSchin
73da2e3ebdSchin if(n) /* get the right one among all dictionaries */
74*b30d1939SAndy Fiddaman { cmp = _DTCMP(d,oky,nky,d->disc);
75*b30d1939SAndy Fiddaman if(((type & (DT_NEXT|DT_FIRST|DT_ATLEAST)) && cmp < 0) ||
76*b30d1939SAndy Fiddaman ((type & (DT_PREV|DT_LAST|DT_ATMOST)) && cmp > 0) )
77*b30d1939SAndy Fiddaman goto b_est;
78da2e3ebdSchin }
79*b30d1939SAndy Fiddaman else
80*b30d1939SAndy Fiddaman { b_est: /* current best element to fit op requirement */
81*b30d1939SAndy Fiddaman p = d;
82da2e3ebdSchin n = o;
83*b30d1939SAndy Fiddaman nky = oky;
84da2e3ebdSchin }
85da2e3ebdSchin }
86da2e3ebdSchin
87da2e3ebdSchin dt->walk = p;
88da2e3ebdSchin return n;
89da2e3ebdSchin }
90da2e3ebdSchin
91*b30d1939SAndy Fiddaman /* unordered collections */
92*b30d1939SAndy Fiddaman if(!(type&(DT_NEXT|DT_PREV)) )
93da2e3ebdSchin return NIL(Void_t*);
94da2e3ebdSchin
95*b30d1939SAndy Fiddaman if(!dt->walk )
96da2e3ebdSchin { for(d = dt; d; d = d->view)
97da2e3ebdSchin if((o = (*(d->meth->searchf))(d, obj, DT_SEARCH)) )
98da2e3ebdSchin break;
99da2e3ebdSchin dt->walk = d;
100da2e3ebdSchin if(!(obj = o) )
101da2e3ebdSchin return NIL(Void_t*);
102da2e3ebdSchin }
103da2e3ebdSchin
104da2e3ebdSchin for(d = dt->walk, obj = (*d->meth->searchf)(d, obj, type);; )
105da2e3ebdSchin { while(obj) /* keep moving until finding an uncovered object */
106da2e3ebdSchin { for(p = dt; ; p = p->view)
107da2e3ebdSchin { if(p == d) /* adjacent object is uncovered */
108da2e3ebdSchin return obj;
109da2e3ebdSchin if((*(p->meth->searchf))(p, obj, DT_SEARCH) )
110da2e3ebdSchin break;
111da2e3ebdSchin }
112da2e3ebdSchin obj = (*d->meth->searchf)(d, obj, type);
113da2e3ebdSchin }
114da2e3ebdSchin
115da2e3ebdSchin if(!(d = dt->walk = d->view) ) /* move on to next dictionary */
116da2e3ebdSchin return NIL(Void_t*);
117da2e3ebdSchin else if(type&DT_NEXT)
118da2e3ebdSchin obj = (*(d->meth->searchf))(d,NIL(Void_t*),DT_FIRST);
119da2e3ebdSchin else obj = (*(d->meth->searchf))(d,NIL(Void_t*),DT_LAST);
120da2e3ebdSchin }
121da2e3ebdSchin }
122da2e3ebdSchin
123da2e3ebdSchin #if __STD_C
dtview(reg Dt_t * dt,reg Dt_t * view)124da2e3ebdSchin Dt_t* dtview(reg Dt_t* dt, reg Dt_t* view)
125da2e3ebdSchin #else
126da2e3ebdSchin Dt_t* dtview(dt,view)
127da2e3ebdSchin reg Dt_t* dt;
128da2e3ebdSchin reg Dt_t* view;
129da2e3ebdSchin #endif
130da2e3ebdSchin {
131da2e3ebdSchin reg Dt_t* d;
132da2e3ebdSchin
133*b30d1939SAndy Fiddaman if(view && view->meth != dt->meth) /* must use the same method */
134*b30d1939SAndy Fiddaman return NIL(Dt_t*);
135da2e3ebdSchin
136da2e3ebdSchin /* make sure there won't be a cycle */
137da2e3ebdSchin for(d = view; d; d = d->view)
138da2e3ebdSchin if(d == dt)
139da2e3ebdSchin return NIL(Dt_t*);
140da2e3ebdSchin
141da2e3ebdSchin /* no more viewing lower dictionary */
142da2e3ebdSchin if((d = dt->view) )
143da2e3ebdSchin d->nview -= 1;
144da2e3ebdSchin dt->view = dt->walk = NIL(Dt_t*);
145da2e3ebdSchin
146da2e3ebdSchin if(!view)
147da2e3ebdSchin { dt->searchf = dt->meth->searchf;
148da2e3ebdSchin return d;
149da2e3ebdSchin }
150da2e3ebdSchin
151da2e3ebdSchin /* ok */
152da2e3ebdSchin dt->view = view;
153da2e3ebdSchin dt->searchf = dtvsearch;
154da2e3ebdSchin view->nview += 1;
155da2e3ebdSchin
156da2e3ebdSchin return view;
157da2e3ebdSchin }
158