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 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 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 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 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 */ 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 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 */ 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 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 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 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 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 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