1 /***********************************************************************
2 * *
3 * This software is part of the ast package *
4 * Copyright (c) 1985-2010 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
dttree(Dt_t * dt,Void_t * obj,int type)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