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
156
157
|
/***********************************************************************
* *
* This software is part of the ast package *
* Copyright (c) 1985-2011 AT&T Intellectual Property *
* and is licensed under the *
* Eclipse Public License, Version 1.0 *
* by AT&T Intellectual Property *
* *
* A copy of the License is available at *
* http://www.eclipse.org/org/documents/epl-v10.html *
* (with md5 checksum b35adb5213ca9657e911e9befb180842) *
* *
* 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)
*/
/* these operations must be done without viewpathing */
#define DT_NOVIEWPATH (DT_INSERT|DT_APPEND|DT_DELETE|\
DT_ATTACH|DT_DETACH|DT_RELINK|DT_CLEAR| \
DT_FLATTEN|DT_EXTRACT|DT_RESTORE|DT_STAT)
#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
{
int cmp;
Dt_t *d, *p;
Void_t *o, *n, *oky, *nky;
if(type&DT_NOVIEWPATH)
return (*(dt->meth->searchf))(dt,obj,type);
o = NIL(Void_t*);
/* these ops look for the first appearance of an object of the right type */
if((type & (DT_MATCH|DT_SEARCH)) ||
((type & (DT_FIRST|DT_LAST|DT_ATLEAST|DT_ATMOST)) && !(dt->meth->type&DT_ORDERED) ) )
{ 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_ORDERED) /* ordered sets/bags */
{ if(!(type & (DT_FIRST|DT_LAST|DT_NEXT|DT_PREV|DT_ATLEAST|DT_ATMOST)) )
return NIL(Void_t*);
/* find the min/max element that satisfies the op requirement */
n = nky = NIL(Void_t*); p = NIL(Dt_t*);
for(d = dt; d; d = d->view)
{ if(!(o = (*d->meth->searchf)(d, obj, type)) )
continue;
oky = _DTKEY(d->disc,o);
if(n) /* get the right one among all dictionaries */
{ cmp = _DTCMP(d,oky,nky,d->disc);
if(((type & (DT_NEXT|DT_FIRST|DT_ATLEAST)) && cmp < 0) ||
((type & (DT_PREV|DT_LAST|DT_ATMOST)) && cmp > 0) )
goto b_est;
}
else
{ b_est: /* current best element to fit op requirement */
p = d;
n = o;
nky = oky;
}
}
dt->walk = p;
return n;
}
/* unordered collections */
if(!(type&(DT_NEXT|DT_PREV)) )
return NIL(Void_t*);
if(!dt->walk )
{ 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;
if(view && 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;
}
|
