1 /***********************************************************************
2 * *
3 * This software is part of the ast package *
4 * Copyright (c) 1985-2010 AT&T Intellectual Property *
5 * and is licensed under the *
6 * Common Public License, Version 1.0 *
7 * by AT&T Intellectual Property *
8 * *
9 * A copy of the License is available at *
10 * http://www.opensource.org/licenses/cpl1.0.txt *
11 * (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9) *
12 * *
13 * Information and Software Systems Research *
14 * AT&T Research *
15 * Florham Park NJ *
16 * *
17 * Glenn Fowler <gsf@research.att.com> *
18 * David Korn <dgk@research.att.com> *
19 * Phong Vo <kpv@research.att.com> *
20 * *
21 ***********************************************************************/
22 #include "dthdr.h"
23
24 /* Set a view path from dict to view.
25 **
26 ** Written by Kiem-Phong Vo (5/25/96)
27 */
28
29
30 #if __STD_C
dtvsearch(Dt_t * dt,reg Void_t * obj,reg int type)31 static Void_t* dtvsearch(Dt_t* dt, reg Void_t* obj, reg int type)
32 #else
33 static Void_t* dtvsearch(dt,obj,type)
34 Dt_t* dt;
35 reg Void_t* obj;
36 reg int type;
37 #endif
38 {
39 Dt_t *d, *p;
40 Void_t *o, *n, *ok, *nk;
41 int cmp, lk, sz, ky;
42 Dtcompar_f cmpf;
43
44 /* these operations only happen at the top level */
45 if(type&(DT_INSERT|DT_DELETE|DT_CLEAR|DT_RENEW))
46 return (*(dt->meth->searchf))(dt,obj,type);
47
48 if((type&(DT_MATCH|DT_SEARCH)) || /* order sets first/last done below */
49 ((type&(DT_FIRST|DT_LAST)) && !(dt->meth->type&(DT_OBAG|DT_OSET)) ) )
50 { for(d = dt; d; d = d->view)
51 if((o = (*(d->meth->searchf))(d,obj,type)) )
52 break;
53 dt->walk = d;
54 return o;
55 }
56
57 if(dt->meth->type & (DT_OBAG|DT_OSET) )
58 { if(!(type & (DT_FIRST|DT_LAST|DT_NEXT|DT_PREV)) )
59 return NIL(Void_t*);
60
61 n = nk = NIL(Void_t*); p = NIL(Dt_t*);
62 for(d = dt; d; d = d->view)
63 { if(!(o = (*d->meth->searchf)(d, obj, type)) )
64 continue;
65 _DTDSC(d->disc,ky,sz,lk,cmpf);
66 ok = _DTKEY(o,ky,sz);
67
68 if(n) /* get the right one among all dictionaries */
69 { cmp = _DTCMP(d,ok,nk,d->disc,cmpf,sz);
70 if(((type & (DT_NEXT|DT_FIRST)) && cmp < 0) ||
71 ((type & (DT_PREV|DT_LAST)) && cmp > 0) )
72 goto a_dj;
73 }
74 else /* looks good for now */
75 { a_dj: p = d;
76 n = o;
77 nk = ok;
78 }
79 }
80
81 dt->walk = p;
82 return n;
83 }
84
85 /* non-ordered methods */
86 if(!(type & (DT_NEXT|DT_PREV)) )
87 return NIL(Void_t*);
88
89 if(!dt->walk || obj != _DTOBJ(dt->walk->data->here, dt->walk->disc->link) )
90 { for(d = dt; d; d = d->view)
91 if((o = (*(d->meth->searchf))(d, obj, DT_SEARCH)) )
92 break;
93 dt->walk = d;
94 if(!(obj = o) )
95 return NIL(Void_t*);
96 }
97
98 for(d = dt->walk, obj = (*d->meth->searchf)(d, obj, type);; )
99 { while(obj) /* keep moving until finding an uncovered object */
100 { for(p = dt; ; p = p->view)
101 { if(p == d) /* adjacent object is uncovered */
102 return obj;
103 if((*(p->meth->searchf))(p, obj, DT_SEARCH) )
104 break;
105 }
106 obj = (*d->meth->searchf)(d, obj, type);
107 }
108
109 if(!(d = dt->walk = d->view) ) /* move on to next dictionary */
110 return NIL(Void_t*);
111 else if(type&DT_NEXT)
112 obj = (*(d->meth->searchf))(d,NIL(Void_t*),DT_FIRST);
113 else obj = (*(d->meth->searchf))(d,NIL(Void_t*),DT_LAST);
114 }
115 }
116
117 #if __STD_C
dtview(reg Dt_t * dt,reg Dt_t * view)118 Dt_t* dtview(reg Dt_t* dt, reg Dt_t* view)
119 #else
120 Dt_t* dtview(dt,view)
121 reg Dt_t* dt;
122 reg Dt_t* view;
123 #endif
124 {
125 reg Dt_t* d;
126
127 UNFLATTEN(dt);
128 if(view)
129 { UNFLATTEN(view);
130 if(view->meth != dt->meth) /* must use the same method */
131 return NIL(Dt_t*);
132 }
133
134 /* make sure there won't be a cycle */
135 for(d = view; d; d = d->view)
136 if(d == dt)
137 return NIL(Dt_t*);
138
139 /* no more viewing lower dictionary */
140 if((d = dt->view) )
141 d->nview -= 1;
142 dt->view = dt->walk = NIL(Dt_t*);
143
144 if(!view)
145 { dt->searchf = dt->meth->searchf;
146 return d;
147 }
148
149 /* ok */
150 dt->view = view;
151 dt->searchf = dtvsearch;
152 view->nview += 1;
153
154 return view;
155 }
156