xref: /illumos-gate/usr/src/contrib/ast/src/lib/libast/cdt/dtview.c (revision b30d193948be5a7794d7ae3ba0ed9c2f72c88e0f)
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