xref: /titanic_44/usr/src/lib/libast/common/cdt/dtview.c (revision 990b4856d0eaada6f8140335733a1b1771ed2746)
1 /***********************************************************************
2 *                                                                      *
3 *               This software is part of the ast package               *
4 *           Copyright (c) 1985-2007 AT&T Knowledge Ventures            *
5 *                      and is licensed under the                       *
6 *                  Common Public License, Version 1.0                  *
7 *                      by AT&T Knowledge Ventures                      *
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
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
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