1 /***********************************************************************
2 * *
3 * This software is part of the ast package *
4 * Copyright (c) 1985-2012 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 /* 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 typedef struct _dttree_s
33 { Dtdata_t data;
34 Dtlink_t* root; /* tree root */
35 } Dttree_t;
36
37 #ifdef CDT_DEBUG
dttreeprint(Dt_t * dt,Dtlink_t * here,int lev,char * (* objprintf)(Void_t *))38 int dttreeprint(Dt_t* dt, Dtlink_t* here, int lev, char* (*objprintf)(Void_t*) )
39 {
40 int k, rv;
41 char *obj, *endb, buf[1024];
42 Dtdisc_t *disc = dt->disc;
43 Dttree_t *tree = (Dttree_t*)dt->data;
44
45 if(!here && !(here = tree->root) )
46 return -1;
47
48 endb = buf; /* indentation */
49 for(k = 0; k < lev; ++k)
50 { *endb++ = ' '; *endb++ = ' '; }
51
52 *endb++ = '(';
53 obj = (*objprintf)(_DTOBJ(disc, here));
54 k = strlen(obj); memcpy(endb, obj, k); endb += k;
55 *endb++ = ')';
56 *endb++ = ':';
57 *endb++ = ' ';
58
59 *endb++ = '<';
60 if(here->_left)
61 obj = (*objprintf)(_DTOBJ(disc,here->_left));
62 else obj = "NIL";
63 k = strlen(obj); memcpy(endb, obj, k); endb += k;
64 *endb++ = '>';
65 *endb++ = ' ';
66
67 *endb++ = '<';
68 if(here->_rght)
69 obj = (*objprintf)(_DTOBJ(disc,here->_rght));
70 else obj = "NIL";
71 k = strlen(obj); memcpy(endb, obj, k); endb += k;
72 *endb++ = '>';
73 *endb++ = '\n';
74 write(2, buf, endb-buf);
75
76 if(here->_left)
77 dttreeprint(dt, here->_left, lev+1, objprintf);
78 if(here->_rght)
79 dttreeprint(dt, here->_rght, lev+1, objprintf);
80
81 return 0;
82 }
83 #endif
84
85 /* terminal object: DT_FIRST|DT_LAST */
86 #if __STD_C
tfirstlast(Dt_t * dt,int type)87 Void_t* tfirstlast(Dt_t* dt, int type)
88 #else
89 Void_t* tfirstlast(dt, type)
90 Dt_t* dt;
91 int type;
92 #endif
93 {
94 Dtlink_t *t, *root;
95 Dtdisc_t *disc = dt->disc;
96 Dttree_t *tree = (Dttree_t*)dt->data;
97
98 if(!(root = tree->root) )
99 return NIL(Void_t*);
100
101 if(type&DT_LAST)
102 { while((t = root->_rght) )
103 LROTATE(root,t);
104 }
105 else /* type&DT_FIRST */
106 { while((t = root->_left) )
107 RROTATE(root,t);
108 }
109 tree->root = root;
110
111 return _DTOBJ(disc, root);
112 }
113
114 /* DT_CLEAR */
115 #if __STD_C
tclear(Dt_t * dt)116 static Void_t* tclear(Dt_t* dt)
117 #else
118 static Void_t* tclear(dt)
119 Dt_t* dt;
120 #endif
121 {
122 Dtlink_t *root, *t;
123 Dtdisc_t *disc = dt->disc;
124 Dttree_t *tree = (Dttree_t*)dt->data;
125
126 root = tree->root;
127 tree->root = NIL(Dtlink_t*);
128 tree->data.size = 0;
129
130 if(root && (disc->link < 0 || disc->freef) )
131 { do
132 { while((t = root->_left) )
133 RROTATE(root,t);
134 t = root->_rght;
135 _dtfree(dt, root, DT_DELETE);
136 } while((root = t) );
137 }
138
139 return NIL(Void_t*);
140 }
141
142 #if __STD_C
tlist(Dt_t * dt,Dtlink_t * list,int type)143 static Void_t* tlist(Dt_t* dt, Dtlink_t* list, int type)
144 #else
145 static Void_t* tlist(dt, list, type)
146 Dt_t* dt;
147 Dtlink_t* list;
148 int type;
149 #endif
150 {
151 Void_t *obj;
152 Dtlink_t *last, *r, *t;
153 Dttree_t *tree = (Dttree_t*)dt->data;
154 Dtdisc_t *disc = dt->disc;
155
156 if(type&(DT_FLATTEN|DT_EXTRACT) )
157 { if((list = tree->root) )
158 { while((t = list->_left) ) /* make smallest object root */
159 RROTATE(list, t);
160 for(r = (last = list)->_rght; r; r = (last = r)->_rght)
161 { while((t = r->_left) ) /* no left children */
162 RROTATE(r,t);
163 last->_rght = r;
164 }
165 }
166
167 if(type&DT_FLATTEN)
168 tree->root = list;
169 else
170 { tree->root = NIL(Dtlink_t*);
171 dt->data->size = 0;
172 }
173 }
174 else /* if(type&DT_RESTORE) */
175 { dt->data->size = 0;
176 for(r = list; r; r = t)
177 { t = r->_rght;
178 obj = _DTOBJ(disc,r);
179 if((*dt->meth->searchf)(dt, (Void_t*)r, DT_RELINK) == obj )
180 dt->data->size += 1;
181 }
182 }
183
184 return (Void_t*)list;
185 }
186
187 #if __STD_C /* compute tree depth and number of nodes */
tsize(Dtlink_t * root,ssize_t lev,Dtstat_t * st)188 static ssize_t tsize(Dtlink_t* root, ssize_t lev, Dtstat_t* st)
189 #else
190 static ssize_t tsize(root, lev, st)
191 Dtlink_t* root;
192 ssize_t lev;
193 Dtstat_t* st;
194 #endif
195 {
196 ssize_t size, z;
197
198 if(!root) /* nothing to do */
199 return 0;
200
201 if(lev >= DT_MAXRECURSE) /* avoid blowing the stack */
202 return -1;
203
204 if(st)
205 { st->mlev = lev > st->mlev ? lev : st->mlev;
206 if(lev < DT_MAXSIZE)
207 { st->msize = lev > st->msize ? lev : st->msize;
208 st->lsize[lev] += 1; /* count #objects per level */
209 }
210 }
211
212 size = 1;
213
214 if((z = tsize(root->_left, lev+1, st)) < 0)
215 return -1;
216 else size += z;
217
218 if((z = tsize(root->_rght, lev+1, st)) < 0)
219 return -1;
220 else size += z;
221
222 return size;
223 }
224
225 #if __STD_C
tstat(Dt_t * dt,Dtstat_t * st)226 static Void_t* tstat(Dt_t* dt, Dtstat_t* st)
227 #else
228 static Void_t* tstat(dt, st)
229 Dt_t* dt;
230 Dtstat_t* st;
231 #endif
232 {
233 ssize_t size;
234 Dttree_t *tree = (Dttree_t*)dt->data;
235
236 if(!st)
237 return (Void_t*)dt->data->size;
238 else
239 { memset(st, 0, sizeof(Dtstat_t));
240 size = tsize(tree->root, 0, st);
241 /**/DEBUG_ASSERT((dt->data->type&DT_SHARE) || size == dt->data->size);
242 st->meth = dt->meth->type;
243 st->size = size;
244 st->space = sizeof(Dttree_t) + (dt->disc->link >= 0 ? 0 : size*sizeof(Dthold_t));
245 return (Void_t*)size;
246 }
247 }
248
249 #if __STD_C /* make a list into a balanced tree */
tbalance(Dtlink_t * list,ssize_t size)250 static Dtlink_t* tbalance(Dtlink_t* list, ssize_t size)
251 #else
252 static Dtlink_t* tbalance(list, size)
253 Dtlink_t* list;
254 ssize_t size;
255 #endif
256 {
257 ssize_t n;
258 Dtlink_t *l, *mid;
259
260 if(size <= 2)
261 return list;
262
263 for(l = list, n = size/2 - 1; n > 0; n -= 1)
264 l = l->_rght;
265
266 mid = l->_rght; l->_rght = NIL(Dtlink_t*);
267 mid->_left = tbalance(list, (n = size/2) );
268 mid->_rght = tbalance(mid->_rght, size - (n + 1));
269 return mid;
270 }
271
toptimize(Dt_t * dt)272 static void toptimize(Dt_t* dt)
273 {
274 ssize_t size;
275 Dtlink_t *l, *list;
276 Dttree_t *tree = (Dttree_t*)dt->data;
277
278 if((list = (Dtlink_t*)tlist(dt, NIL(Void_t*), DT_FLATTEN)) )
279 { for(size = 0, l = list; l; l = l->_rght)
280 size += 1;
281 tree->root = tbalance(list, size);
282 }
283 }
284
troot(Dt_t * dt,Dtlink_t * list,Dtlink_t * link,Void_t * obj,int type)285 static Dtlink_t* troot(Dt_t* dt, Dtlink_t* list, Dtlink_t* link, Void_t* obj, int type)
286 {
287 Dtlink_t *root, *last, *t, *r, *l;
288 Void_t *key, *o, *k;
289 Dtdisc_t *disc = dt->disc;
290
291 key = _DTKEY(disc, obj); /* key of object */
292
293 if(type&(DT_ATMOST|DT_ATLEAST) ) /* find the left-most or right-most element */
294 { list->_left = link->_rght;
295 list->_rght = link->_left;
296 if(type&DT_ATMOST)
297 { while((l = list->_left) )
298 { while((r = l->_rght) ) /* get the max elt of left subtree */
299 LROTATE(l,r);
300 list->_left = l;
301
302 o = _DTOBJ(disc,l); k = _DTKEY(disc,o);
303 if(_DTCMP(dt, key, k, disc) != 0 )
304 break;
305 else RROTATE(list,l);
306 }
307 }
308 else
309 { while((r = list->_rght) )
310 { while((l = r->_left) ) /* get the min elt of right subtree */
311 RROTATE(r,l);
312 list->_rght = r;
313
314 o = _DTOBJ(disc,r); k = _DTKEY(disc,o);
315 if(_DTCMP(dt, key, k, disc) != 0 )
316 break;
317 else LROTATE(list,r);
318 }
319 }
320 link->_rght = list->_left;
321 link->_left = list->_rght;
322 return list;
323 }
324
325 last = list; list->_left = list->_rght = NIL(Dtlink_t*);
326 root = NIL(Dtlink_t*);
327
328 while(!root && (t = link->_rght) ) /* link->_rght is the left subtree <= obj */
329 { while((r = t->_rght) ) /* make t the maximum element */
330 LROTATE(t,r);
331
332 o = _DTOBJ(disc,t); k = _DTKEY(disc,o);
333 if(_DTCMP(dt, key, k, disc) != 0 )
334 { link->_rght = t; /* no more of this group in subtree */
335 break;
336 }
337 else if((type & (DT_REMOVE|DT_NEXT|DT_PREV)) && o == obj)
338 { link->_rght = t->_left; /* found the exact object */
339 root = t;
340 }
341 else /* add t to equal list in an order-preserving manner */
342 { link->_rght = t->_left;
343 t->_left = t->_rght = NIL(Dtlink_t*);
344 if(type&DT_NEXT )
345 { last->_left = t; last = t; }
346 else { t->_rght = list; list = t; }
347 }
348 }
349
350 while(!root && (t = link->_left) ) /* link->_left is the right subtree >= obj */
351 { while((l = t->_left) ) /* make t the minimum element */
352 RROTATE(t,l);
353
354 o = _DTOBJ(disc,t); k = _DTKEY(disc,o);
355 if(_DTCMP(dt, key, k, disc) != 0 )
356 { link->_left = t; /* no more of this group in subtree */
357 break;
358 }
359 else if((type & (DT_REMOVE|DT_NEXT|DT_PREV)) && o == obj)
360 { link->_left = t->_rght; /* found the exact object */
361 root = t;
362 }
363 else /* add t to equal list in an order-preserving manner */
364 { link->_left = t->_rght;
365 t->_left = t->_rght = NIL(Dtlink_t*);
366 if(type&DT_NEXT )
367 { t->_left = list; list = t; }
368 else { last->_rght = t; last = t; }
369 }
370 }
371
372 if(!root) /* always set a non-trivial root */
373 { root = list;
374 if(type&DT_NEXT)
375 list = list->_left;
376 else list = list->_rght;
377 }
378
379 if(list) /* add the rest of the equal-list to the proper subtree */
380 { if(type&DT_NEXT)
381 { last->_left = link->_rght;
382 link->_rght = list;
383 }
384 else
385 { last->_rght = link->_left;
386 link->_left = list;
387 }
388 }
389
390 return root;
391 }
392
393 #if __STD_C
dttree(Dt_t * dt,Void_t * obj,int type)394 static Void_t* dttree(Dt_t* dt, Void_t* obj, int type)
395 #else
396 static Void_t* dttree(dt,obj,type)
397 Dt_t* dt;
398 Void_t* obj;
399 int type;
400 #endif
401 {
402 int cmp;
403 Void_t *o, *k, *key;
404 Dtlink_t *root, *t, *l, *r, *me, link;
405 Dtdisc_t *disc = dt->disc;
406 Dttree_t *tree = (Dttree_t*)dt->data;
407
408 type = DTTYPE(dt, type); /* map type for upward compatibility */
409 if(!(type&DT_OPERATIONS) )
410 return NIL(Void_t*);
411
412 DTSETLOCK(dt);
413
414 if(type&(DT_FIRST|DT_LAST) )
415 DTRETURN(obj, tfirstlast(dt, type));
416 else if(type&(DT_EXTRACT|DT_RESTORE|DT_FLATTEN))
417 DTRETURN(obj, tlist(dt, (Dtlink_t*)obj, type));
418 else if(type&DT_CLEAR)
419 DTRETURN(obj, tclear(dt));
420 else if(type&DT_STAT)
421 { toptimize(dt); /* balance tree to avoid deep recursion */
422 DTRETURN(obj, tstat(dt, (Dtstat_t*)obj));
423 }
424
425 if(!obj) /* from here on, an object prototype is required */
426 DTRETURN(obj, NIL(Void_t*));
427
428 if(type&DT_RELINK) /* relinking objects after some processing */
429 { me = (Dtlink_t*)obj;
430 obj = _DTOBJ(disc,me);
431 key = _DTKEY(disc,obj);
432 }
433 else
434 { me = NIL(Dtlink_t*);
435 if(type&DT_MATCH) /* no prototype object given, just the key */
436 { key = obj;
437 obj = NIL(Void_t*);
438 }
439 else key = _DTKEY(disc,obj); /* get key from prototype object */
440 }
441
442 memset(&link, 0, sizeof(link));
443 l = r = &link; /* link._rght(_left) will be LEFT(RIGHT) tree after splaying */
444 if((root = tree->root) && _DTOBJ(disc,root) != obj) /* splay-search for a matching object */
445 { while(1)
446 { o = _DTOBJ(disc,root); k = _DTKEY(disc,o);
447 if((cmp = _DTCMP(dt,key,k,disc)) == 0)
448 break;
449 else if(cmp < 0)
450 { if((t = root->_left) )
451 { o = _DTOBJ(disc,t); k = _DTKEY(disc,o);
452 if((cmp = _DTCMP(dt,key,k,disc)) < 0)
453 { rrotate(root,t);
454 rlink(r,t);
455 if(!(root = t->_left) )
456 break;
457 }
458 else if(cmp == 0)
459 { rlink(r,root);
460 root = t;
461 break;
462 }
463 else /* if(cmp > 0) */
464 { llink(l,t);
465 rlink(r,root);
466 if(!(root = t->_rght) )
467 break;
468 }
469 }
470 else
471 { rlink(r,root);
472 root = NIL(Dtlink_t*);
473 break;
474 }
475 }
476 else /* if(cmp > 0) */
477 { if((t = root->_rght) )
478 { o = _DTOBJ(disc,t); k = _DTKEY(disc,o);
479 if((cmp = _DTCMP(dt,key,k,disc)) > 0)
480 { lrotate(root,t);
481 llink(l,t);
482 if(!(root = t->_rght) )
483 break;
484 }
485 else if(cmp == 0)
486 { llink(l,root);
487 root = t;
488 break;
489 }
490 else /* if(cmp < 0) */
491 { rlink(r,t);
492 llink(l,root);
493 if(!(root = t->_left) )
494 break;
495 }
496 }
497 else
498 { llink(l,root);
499 root = NIL(Dtlink_t*);
500 break;
501 }
502 }
503 }
504 }
505 l->_rght = root ? root->_left : NIL(Dtlink_t*);
506 r->_left = root ? root->_rght : NIL(Dtlink_t*);
507
508 if(root)
509 { if(dt->meth->type&DT_OBAG ) /* may need to reset root to the right object */
510 { if((type&(DT_ATLEAST|DT_ATMOST)) ||
511 ((type&(DT_NEXT|DT_PREV|DT_REMOVE)) && _DTOBJ(disc,root) != obj) )
512 root = troot(dt, root, &link, obj, type);
513 }
514
515 if(type&(DT_SEARCH|DT_MATCH|DT_ATMOST|DT_ATLEAST))
516 { has_root: /* reconstitute the tree */
517 root->_left = link._rght;
518 root->_rght = link._left;
519 tree->root = root;
520 DTRETURN(obj, _DTOBJ(disc,root));
521 }
522 else if(type&DT_NEXT)
523 { root->_left = link._rght;
524 root->_rght = NIL(Dtlink_t*);
525 link._rght = root;
526 dt_next:
527 if((root = link._left) )
528 { while((t = root->_left) )
529 RROTATE(root,t);
530 link._left = root->_rght;
531 goto has_root;
532 }
533 else goto no_root;
534 }
535 else if(type&DT_PREV)
536 { root->_rght = link._left;
537 root->_left = NIL(Dtlink_t*);
538 link._left = root;
539 dt_prev:
540 if((root = link._rght) )
541 { while((t = root->_rght) )
542 LROTATE(root,t);
543 link._rght = root->_left;
544 goto has_root;
545 }
546 else goto no_root;
547 }
548 else if(type&DT_REMOVE) /* remove a particular element in the tree */
549 { if(_DTOBJ(disc,root) == obj)
550 goto dt_delete;
551 else
552 { root->_left = link._rght;
553 root->_rght = link._left;
554 tree->root = root;
555 DTRETURN(obj, NIL(Void_t*));
556 }
557 }
558 else if(type&(DT_DELETE|DT_DETACH))
559 { dt_delete: /* remove an object from the dictionary */
560 obj = _DTOBJ(disc,root);
561 _dtfree(dt, root, type);
562 dt->data->size -= 1;
563 goto no_root;
564 }
565 else if(type&(DT_INSERT|DT_APPEND|DT_ATTACH))
566 { if(dt->meth->type&DT_OSET)
567 { type |= DT_SEARCH; /* for announcement */
568 goto has_root;
569 }
570 else
571 { root->_left = NIL(Dtlink_t*);
572 root->_rght = link._left;
573 link._left = root;
574 goto dt_insert;
575 }
576 }
577 else if(type&DT_RELINK) /* a duplicate */
578 { if(dt->meth->type&DT_OSET)
579 _dtfree(dt, me, DT_DELETE);
580 else
581 { me->_left = NIL(Dtlink_t*);
582 me->_rght = link._left;
583 link._left = me;
584 }
585 goto has_root;
586 }
587 }
588 else /* no matching object, tree has been split to LEFT&RIGHT subtrees */
589 { if(type&(DT_SEARCH|DT_MATCH))
590 { no_root:
591 if(!(l = link._rght) ) /* no LEFT subtree */
592 tree->root = link._left; /* tree is RIGHT tree */
593 else
594 { while((t = l->_rght) ) /* maximize root of LEFT tree */
595 { if(t->_rght)
596 LLSHIFT(l,t);
597 else LROTATE(l,t);
598 }
599 l->_rght = link._left; /* hook RIGHT tree to LEFT root */
600 tree->root = l; /* LEFT tree is now the entire tree */
601 }
602
603 if(type&(DT_DELETE|DT_DETACH|DT_REMOVE))
604 DTRETURN(obj, obj);
605 else DTRETURN(obj, NIL(Void_t*));
606 }
607 else if(type&(DT_NEXT|DT_ATLEAST) )
608 goto dt_next;
609 else if(type&(DT_PREV|DT_ATMOST) )
610 goto dt_prev;
611 else if(type&(DT_DELETE|DT_DETACH|DT_REMOVE))
612 { obj = NIL(Void_t*);
613 goto no_root;
614 }
615 else if(type&(DT_INSERT|DT_APPEND|DT_ATTACH))
616 { dt_insert:
617 if(!(root = _dtmake(dt, obj, type)) )
618 { obj = NIL(Void_t*);
619 goto no_root;
620 }
621 else
622 { dt->data->size += 1;
623 goto has_root;
624 }
625 }
626 else if(type&DT_RELINK)
627 { root = me;
628 goto has_root;
629 }
630 }
631 DTRETURN(obj, NIL(Void_t*));
632
633 dt_return:
634 DTANNOUNCE(dt,obj,type);
635 DTCLRLOCK(dt);
636 return obj;
637 }
638
treeevent(Dt_t * dt,int event,Void_t * arg)639 static int treeevent(Dt_t* dt, int event, Void_t* arg)
640 {
641 Dttree_t *tree = (Dttree_t*)dt->data;
642
643 if(event == DT_OPEN)
644 { if(tree) /* already initialized */
645 return 0;
646 if(!(tree = (Dttree_t*)(*dt->memoryf)(dt, 0, sizeof(Dttree_t), dt->disc)) )
647 { DTERROR(dt, "Error in allocating a tree data structure");
648 return -1;
649 }
650 memset(tree, 0, sizeof(Dttree_t));
651 dt->data = (Dtdata_t*)tree;
652 return 1;
653 }
654 else if(event == DT_CLOSE)
655 { if(!tree)
656 return 0;
657 if(tree->root)
658 (void)tclear(dt);
659 (void)(*dt->memoryf)(dt, (Void_t*)tree, 0, dt->disc);
660 dt->data = NIL(Dtdata_t*);
661 return 0;
662 }
663 else if(event == DT_OPTIMIZE) /* balance the search tree */
664 { toptimize(dt);
665 return 0;
666 }
667 else return 0;
668 }
669
670 #if _UWIN
671
dtfinger(Dt_t * dt)672 Void_t* dtfinger(Dt_t* dt)
673 {
674 return (dt && dt->meth && (dt->meth->type & DT_ORDERED)) ? (Void_t*)((Dttree_t*)dt->data)->root : NIL(Void_t*);
675 }
676
677 #endif
678
679 /* make this method available */
680 static Dtmethod_t _Dtoset = { dttree, DT_OSET, treeevent, "Dtoset" };
681 static Dtmethod_t _Dtobag = { dttree, DT_OBAG, treeevent, "Dtobag" };
682 __DEFINE__(Dtmethod_t*,Dtoset,&_Dtoset);
683 __DEFINE__(Dtmethod_t*,Dtobag,&_Dtobag);
684
685 /* backwards compatibility */
686 #undef Dttree
687 #if defined(__EXPORT__)
688 __EXPORT__
689 #endif
690 __DEFINE__(Dtmethod_t*,Dttree,&_Dtoset);
691
692 #ifdef NoF
693 NoF(dttree)
694 #endif
695