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