xref: /titanic_44/usr/src/lib/libast/common/cdt/dttree.c (revision 379c004d1f26b343f034bba8a350290691d00d38)
1 /***********************************************************************
2 *                                                                      *
3 *               This software is part of the ast package               *
4 *          Copyright (c) 1985-2008 AT&T Intellectual Property          *
5 *                      and is licensed under the                       *
6 *                  Common Public License, Version 1.0                  *
7 *                    by AT&T Intellectual Property                     *
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 /*	Ordered set/multiset
25 **	dt:	dictionary being searched
26 **	obj:	the object to look for.
27 **	type:	search type.
28 **
29 **      Written by Kiem-Phong Vo (5/25/96)
30 */
31 
32 #if __STD_C
33 static Void_t* dttree(Dt_t* dt, Void_t* obj, int type)
34 #else
35 static Void_t* dttree(dt,obj,type)
36 Dt_t*		dt;
37 Void_t* 	obj;
38 int		type;
39 #endif
40 {
41 	Dtlink_t	*root, *t;
42 	int		cmp, lk, sz, ky;
43 	Void_t		*o, *k, *key;
44 	Dtlink_t	*l, *r, *me, link;
45 	int		n, minp, turn[DT_MINP];
46 	Dtcompar_f	cmpf;
47 	Dtdisc_t*	disc;
48 
49 	UNFLATTEN(dt);
50 	disc = dt->disc; _DTDSC(disc,ky,sz,lk,cmpf);
51 	dt->type &= ~DT_FOUND;
52 
53 	root = dt->data->here;
54 	if(!obj)
55 	{	if(!root || !(type&(DT_CLEAR|DT_FIRST|DT_LAST)) )
56 			return NIL(Void_t*);
57 
58 		if(type&DT_CLEAR) /* delete all objects */
59 		{	if(disc->freef || disc->link < 0)
60 			{	do
61 				{	while((t = root->left) )
62 						RROTATE(root,t);
63 					t = root->right;
64 					if(disc->freef)
65 						(*disc->freef)(dt,_DTOBJ(root,lk),disc);
66 					if(disc->link < 0)
67 						(*dt->memoryf)(dt,(Void_t*)root,0,disc);
68 				} while((root = t) );
69 			}
70 
71 			dt->data->size = 0;
72 			dt->data->here = NIL(Dtlink_t*);
73 			return NIL(Void_t*);
74 		}
75 		else /* computing largest/smallest element */
76 		{	if(type&DT_LAST)
77 			{	while((t = root->right) )
78 					LROTATE(root,t);
79 			}
80 			else /* type&DT_FIRST */
81 			{	while((t = root->left) )
82 					RROTATE(root,t);
83 			}
84 
85 			dt->data->here = root;
86 			return _DTOBJ(root,lk);
87 		}
88 	}
89 
90 	/* note that link.right is LEFT tree and link.left is RIGHT tree */
91 	l = r = &link;
92 
93 	/* allow apps to delete an object "actually" in the dictionary */
94 	if(dt->meth->type == DT_OBAG && (type&(DT_DELETE|DT_DETACH)) )
95 	{	key = _DTKEY(obj,ky,sz);
96 		for(o = dtsearch(dt,obj); o; o = dtnext(dt,o) )
97 		{	k = _DTKEY(o,ky,sz);
98 			if(_DTCMP(dt,key,k,disc,cmpf,sz) != 0)
99 				break;
100 			if(o == obj)
101 			{	root = dt->data->here;
102 				l->right = root->left;
103 				r->left  = root->right;
104 				goto dt_delete;
105 			}
106 		}
107 	}
108 
109 	if(type&(DT_MATCH|DT_SEARCH|DT_INSERT|DT_ATTACH))
110 	{	key = (type&DT_MATCH) ? obj : _DTKEY(obj,ky,sz);
111 		if(root)
112 			goto do_search;
113 	}
114 	else if(type&DT_RENEW)
115 	{	me = (Dtlink_t*)obj;
116 		obj = _DTOBJ(me,lk);
117 		key = _DTKEY(obj,ky,sz);
118 		if(root)
119 			goto do_search;
120 	}
121 	else if(root && _DTOBJ(root,lk) != obj)
122 	{	key = _DTKEY(obj,ky,sz);
123 	do_search:
124 		if(dt->meth->type == DT_OSET &&
125 		   (minp = dt->data->minp) != 0 && (type&(DT_MATCH|DT_SEARCH)) )
126 		{	/* simple search, note that minp should be even */
127 			for(t = root, n = 0; n < minp; ++n)
128 			{	k = _DTOBJ(t,lk); k = _DTKEY(k,ky,sz);
129 				if((cmp = _DTCMP(dt,key,k,disc,cmpf,sz)) == 0)
130 					return _DTOBJ(t,lk);
131 				else
132 				{	turn[n] = cmp;
133 					if(!(t = cmp < 0 ? t->left : t->right) )
134 						return NIL(Void_t*);
135 				}
136 			}
137 
138 			/* exceed search length, top-down splay now */
139 			for(n = 0; n < minp; n += 2)
140 			{	if(turn[n] < 0)
141 				{	t = root->left;
142 					if(turn[n+1] < 0)
143 					{	rrotate(root,t);
144 						rlink(r,t);
145 						root = t->left;
146 					}
147 					else
148 					{	llink(l,t);
149 						rlink(r,root);
150 						root = t->right;
151 					}
152 				}
153 				else
154 				{	t = root->right;
155 					if(turn[n+1] > 0)
156 					{	lrotate(root,t);
157 						llink(l,t);
158 						root = t->right;
159 					}
160 					else
161 					{	rlink(r,t);
162 						llink(l,root);
163 						root = t->left;
164 					}
165 				}
166 			}
167 		}
168 
169 		while(1)
170 		{	k = _DTOBJ(root,lk); k = _DTKEY(k,ky,sz);
171 			if((cmp = _DTCMP(dt,key,k,disc,cmpf,sz)) == 0)
172 				break;
173 			else if(cmp < 0)
174 			{	if((t = root->left) )
175 				{	k = _DTOBJ(t,lk); k = _DTKEY(k,ky,sz);
176 					if((cmp = _DTCMP(dt,key,k,disc,cmpf,sz)) < 0)
177 					{	rrotate(root,t);
178 						rlink(r,t);
179 						if(!(root = t->left) )
180 							break;
181 					}
182 					else if(cmp == 0)
183 					{	rlink(r,root);
184 						root = t;
185 						break;
186 					}
187 					else /* if(cmp > 0) */
188 					{	llink(l,t);
189 						rlink(r,root);
190 						if(!(root = t->right) )
191 							break;
192 					}
193 				}
194 				else
195 				{	rlink(r,root);
196 					root = NIL(Dtlink_t*);
197 					break;
198 				}
199 			}
200 			else /* if(cmp > 0) */
201 			{	if((t = root->right) )
202 				{	k = _DTOBJ(t,lk); k = _DTKEY(k,ky,sz);
203 					if((cmp = _DTCMP(dt,key,k,disc,cmpf,sz)) > 0)
204 					{	lrotate(root,t);
205 						llink(l,t);
206 						if(!(root = t->right) )
207 							break;
208 					}
209 					else if(cmp == 0)
210 					{	llink(l,root);
211 						root = t;
212 						break;
213 					}
214 					else /* if(cmp < 0) */
215 					{	rlink(r,t);
216 						llink(l,root);
217 						if(!(root = t->left) )
218 							break;
219 					}
220 				}
221 				else
222 				{	llink(l,root);
223 					root = NIL(Dtlink_t*);
224 					break;
225 				}
226 			}
227 		}
228 	}
229 
230 	if(root)
231 	{	/* found it, now isolate it */
232 		dt->type |= DT_FOUND;
233 		l->right = root->left;
234 		r->left = root->right;
235 
236 		if(type&(DT_SEARCH|DT_MATCH))
237 		{ has_root:
238 			root->left = link.right;
239 			root->right = link.left;
240 			if((dt->meth->type&DT_OBAG) && (type&(DT_SEARCH|DT_MATCH)) )
241 			{	key = _DTOBJ(root,lk); key = _DTKEY(key,ky,sz);
242 				while((t = root->left) )
243 				{	/* find max of left subtree */
244 					while((r = t->right) )
245 						LROTATE(t,r);
246 					root->left = t;
247 
248 					/* now see if it's in the same group */
249 					k = _DTOBJ(t,lk); k = _DTKEY(k,ky,sz);
250 					if(_DTCMP(dt,key,k,disc,cmpf,sz) != 0)
251 						break;
252 					RROTATE(root,t);
253 				}
254 			}
255 			dt->data->here = root;
256 			return _DTOBJ(root,lk);
257 		}
258 		else if(type&DT_NEXT)
259 		{	root->left = link.right;
260 			root->right = NIL(Dtlink_t*);
261 			link.right = root;
262 		dt_next:
263 			if((root = link.left) )
264 			{	while((t = root->left) )
265 					RROTATE(root,t);
266 				link.left = root->right;
267 				goto has_root;
268 			}
269 			else	goto no_root;
270 		}
271 		else if(type&DT_PREV)
272 		{	root->right = link.left;
273 			root->left = NIL(Dtlink_t*);
274 			link.left = root;
275 		dt_prev:
276 			if((root = link.right) )
277 			{	while((t = root->right) )
278 					LROTATE(root,t);
279 				link.right = root->left;
280 				goto has_root;
281 			}
282 			else	goto no_root;
283 		}
284 		else if(type&(DT_DELETE|DT_DETACH))
285 		{	/* taking an object out of the dictionary */
286 		dt_delete:
287 			obj = _DTOBJ(root,lk);
288 			if(disc->freef && (type&DT_DELETE))
289 				(*disc->freef)(dt,obj,disc);
290 			if(disc->link < 0)
291 				(*dt->memoryf)(dt,(Void_t*)root,0,disc);
292 			if((dt->data->size -= 1) < 0)
293 				dt->data->size = -1;
294 			goto no_root;
295 		}
296 		else if(type&(DT_INSERT|DT_ATTACH))
297 		{	if(dt->meth->type&DT_OSET)
298 				goto has_root;
299 			else
300 			{	root->left = NIL(Dtlink_t*);
301 				root->right = link.left;
302 				link.left = root;
303 				goto dt_insert;
304 			}
305 		}
306 		else if(type&DT_RENEW) /* a duplicate */
307 		{	if(dt->meth->type&DT_OSET)
308 			{	if(disc->freef)
309 					(*disc->freef)(dt,obj,disc);
310 				if(disc->link < 0)
311 					(*dt->memoryf)(dt,(Void_t*)me,0,disc);
312 			}
313 			else
314 			{	me->left = NIL(Dtlink_t*);
315 				me->right = link.left;
316 				link.left = me;
317 				dt->data->size += 1;
318 			}
319 			goto has_root;
320 		}
321 	}
322 	else
323 	{	/* not found, finish up LEFT and RIGHT trees */
324 		r->left = NIL(Dtlink_t*);
325 		l->right = NIL(Dtlink_t*);
326 
327 		if(type&DT_NEXT)
328 			goto dt_next;
329 		else if(type&DT_PREV)
330 			goto dt_prev;
331 		else if(type&(DT_SEARCH|DT_MATCH))
332 		{ no_root:
333 			while((t = r->left) )
334 				r = t;
335 			r->left = link.right;
336 			dt->data->here = link.left;
337 			return (type&DT_DELETE) ? obj : NIL(Void_t*);
338 		}
339 		else if(type&(DT_INSERT|DT_ATTACH))
340 		{ dt_insert:
341 			if(disc->makef && (type&DT_INSERT))
342 				obj = (*disc->makef)(dt,obj,disc);
343 			if(obj)
344 			{	if(lk >= 0)
345 					root = _DTLNK(obj,lk);
346 				else
347 				{	root = (Dtlink_t*)(*dt->memoryf)
348 						(dt,NIL(Void_t*),sizeof(Dthold_t),disc);
349 					if(root)
350 						((Dthold_t*)root)->obj = obj;
351 					else if(disc->makef && disc->freef &&
352 						(type&DT_INSERT))
353 						(*disc->freef)(dt,obj,disc);
354 				}
355 			}
356 			if(root)
357 			{	if(dt->data->size >= 0)
358 					dt->data->size += 1;
359 				goto has_root;
360 			}
361 			else	goto no_root;
362 		}
363 		else if(type&DT_RENEW)
364 		{	root = me;
365 			dt->data->size += 1;
366 			goto has_root;
367 		}
368 		else /*if(type&DT_DELETE)*/
369 		{	obj = NIL(Void_t*);
370 			goto no_root;
371 		}
372 	}
373 
374 	return NIL(Void_t*);
375 }
376 
377 /* make this method available */
378 static Dtmethod_t	_Dtoset =  { dttree, DT_OSET };
379 static Dtmethod_t	_Dtobag =  { dttree, DT_OBAG };
380 __DEFINE__(Dtmethod_t*,Dtoset,&_Dtoset);
381 __DEFINE__(Dtmethod_t*,Dtobag,&_Dtobag);
382 
383 #ifndef KPVDEL /* backward compatibility - delete next time around */
384 Dtmethod_t		_Dttree = { dttree, DT_OSET };
385 __DEFINE__(Dtmethod_t*,Dtorder,&_Dttree);
386 __DEFINE__(Dtmethod_t*,Dttree,&_Dttree);
387 #endif
388 
389 #ifdef NoF
390 NoF(dttree)
391 #endif
392