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