1// This may look like C code, but it is really -*- C++ -*- 2/* 3Copyright (C) 1988 Free Software Foundation 4 written by Doug Lea (dl@rocky.oswego.edu) 5 6This file is part of GNU CC. 7 8GNU CC is distributed in the hope that it will be useful, 9but WITHOUT ANY WARRANTY. No author or distributor 10accepts responsibility to anyone for the consequences of using it 11or for whether it serves any particular purpose or works at all, 12unless he says so in writing. Refer to the GNU CC General Public 13License for full details. 14 15Everyone is granted permission to copy, modify and redistribute 16GNU CC, but only under the conditions described in the 17GNU CC General Public License. A copy of this license is 18supposed to have been given to you along with GNU CC so you 19can know your rights and responsibilities. It should be in a 20file named COPYING. Among other things, the copyright notice 21and this notice must be preserved on all copies. 22*/ 23 24#ifdef __GNUG__ 25#pragma implementation 26#endif 27#include <stream.h> 28#include <assert.h> 29#include "<T>.<C>.AVLMap.h" 30 31 32/* 33 constants & inlines for maintaining balance & thread status in tree nodes 34*/ 35 36#define AVLBALANCEMASK 3 37#define AVLBALANCED 0 38#define AVLLEFTHEAVY 1 39#define AVLRIGHTHEAVY 2 40 41#define LTHREADBIT 4 42#define RTHREADBIT 8 43 44 45static inline int bf(<T><C>AVLNode* t) 46{ 47 return t->stat & AVLBALANCEMASK; 48} 49 50static inline void set_bf(<T><C>AVLNode* t, int b) 51{ 52 t->stat = (t->stat & ~AVLBALANCEMASK) | (b & AVLBALANCEMASK); 53} 54 55 56static inline int rthread(<T><C>AVLNode* t) 57{ 58 return t->stat & RTHREADBIT; 59} 60 61static inline void set_rthread(<T><C>AVLNode* t, int b) 62{ 63 if (b) 64 t->stat |= RTHREADBIT; 65 else 66 t->stat &= ~RTHREADBIT; 67} 68 69static inline int lthread(<T><C>AVLNode* t) 70{ 71 return t->stat & LTHREADBIT; 72} 73 74static inline void set_lthread(<T><C>AVLNode* t, int b) 75{ 76 if (b) 77 t->stat |= LTHREADBIT; 78 else 79 t->stat &= ~LTHREADBIT; 80} 81 82/* 83 traversal primitives 84*/ 85 86 87<T><C>AVLNode* <T><C>AVLMap::leftmost() 88{ 89 <T><C>AVLNode* t = root; 90 if (t != 0) while (t->lt != 0) t = t->lt; 91 return t; 92} 93 94<T><C>AVLNode* <T><C>AVLMap::rightmost() 95{ 96 <T><C>AVLNode* t = root; 97 if (t != 0) while (t->rt != 0) t = t->rt; 98 return t; 99} 100 101<T><C>AVLNode* <T><C>AVLMap::succ(<T><C>AVLNode* t) 102{ 103 <T><C>AVLNode* r = t->rt; 104 if (!rthread(t)) while (!lthread(r)) r = r->lt; 105 return r; 106} 107 108<T><C>AVLNode* <T><C>AVLMap::pred(<T><C>AVLNode* t) 109{ 110 <T><C>AVLNode* l = t->lt; 111 if (!lthread(t)) while (!rthread(l)) l = l->rt; 112 return l; 113} 114 115 116Pix <T><C>AVLMap::seek(<T&> key) 117{ 118 <T><C>AVLNode* t = root; 119 if (t == 0) 120 return 0; 121 for (;;) 122 { 123 int cmp = <T>CMP(key, t->item); 124 if (cmp == 0) 125 return Pix(t); 126 else if (cmp < 0) 127 { 128 if (lthread(t)) 129 return 0; 130 else 131 t = t->lt; 132 } 133 else if (rthread(t)) 134 return 0; 135 else 136 t = t->rt; 137 } 138} 139 140 141/* 142 The combination of threads and AVL bits make adding & deleting 143 interesting, but very awkward. 144 145 We use the following statics to avoid passing them around recursively 146*/ 147 148static int _need_rebalancing; // to send back balance info from rec. calls 149static <T>* _target_item; // add/del_item target 150static <T><C>AVLNode* _found_node; // returned added/deleted node 151static int _already_found; // for deletion subcases 152 153 154void <T><C>AVLMap:: _add(<T><C>AVLNode*& t) 155{ 156 int cmp = <T>CMP(*_target_item, t->item); 157 if (cmp == 0) 158 { 159 _found_node = t; 160 return; 161 } 162 else if (cmp < 0) 163 { 164 if (lthread(t)) 165 { 166 ++count; 167 _found_node = new <T><C>AVLNode(*_target_item, def); 168 set_lthread(_found_node, 1); 169 set_rthread(_found_node, 1); 170 _found_node->lt = t->lt; 171 _found_node->rt = t; 172 t->lt = _found_node; 173 set_lthread(t, 0); 174 _need_rebalancing = 1; 175 } 176 else 177 _add(t->lt); 178 if (_need_rebalancing) 179 { 180 switch(bf(t)) 181 { 182 case AVLRIGHTHEAVY: 183 set_bf(t, AVLBALANCED); 184 _need_rebalancing = 0; 185 return; 186 case AVLBALANCED: 187 set_bf(t, AVLLEFTHEAVY); 188 return; 189 case AVLLEFTHEAVY: 190 <T><C>AVLNode* l = t->lt; 191 if (bf(l) == AVLLEFTHEAVY) 192 { 193 if (rthread(l)) 194 t->lt = l; 195 else 196 t->lt = l->rt; 197 set_lthread(t, rthread(l)); 198 l->rt = t; 199 set_rthread(l, 0); 200 set_bf(t, AVLBALANCED); 201 set_bf(l, AVLBALANCED); 202 t = l; 203 _need_rebalancing = 0; 204 } 205 else 206 { 207 <T><C>AVLNode* r = l->rt; 208 set_rthread(l, lthread(r)); 209 if (lthread(r)) 210 l->rt = r; 211 else 212 l->rt = r->lt; 213 r->lt = l; 214 set_lthread(r, 0); 215 set_lthread(t, rthread(r)); 216 if (rthread(r)) 217 t->lt = r; 218 else 219 t->lt = r->rt; 220 r->rt = t; 221 set_rthread(r, 0); 222 if (bf(r) == AVLLEFTHEAVY) 223 set_bf(t, AVLRIGHTHEAVY); 224 else 225 set_bf(t, AVLBALANCED); 226 if (bf(r) == AVLRIGHTHEAVY) 227 set_bf(l, AVLLEFTHEAVY); 228 else 229 set_bf(l, AVLBALANCED); 230 set_bf(r, AVLBALANCED); 231 t = r; 232 _need_rebalancing = 0; 233 return; 234 } 235 } 236 } 237 } 238 else 239 { 240 if (rthread(t)) 241 { 242 ++count; 243 _found_node = new <T><C>AVLNode(*_target_item, def); 244 set_rthread(t, 0); 245 set_lthread(_found_node, 1); 246 set_rthread(_found_node, 1); 247 _found_node->lt = t; 248 _found_node->rt = t->rt; 249 t->rt = _found_node; 250 _need_rebalancing = 1; 251 } 252 else 253 _add(t->rt); 254 if (_need_rebalancing) 255 { 256 switch(bf(t)) 257 { 258 case AVLLEFTHEAVY: 259 set_bf(t, AVLBALANCED); 260 _need_rebalancing = 0; 261 return; 262 case AVLBALANCED: 263 set_bf(t, AVLRIGHTHEAVY); 264 return; 265 case AVLRIGHTHEAVY: 266 <T><C>AVLNode* r = t->rt; 267 if (bf(r) == AVLRIGHTHEAVY) 268 { 269 if (lthread(r)) 270 t->rt = r; 271 else 272 t->rt = r->lt; 273 set_rthread(t, lthread(r)); 274 r->lt = t; 275 set_lthread(r, 0); 276 set_bf(t, AVLBALANCED); 277 set_bf(r, AVLBALANCED); 278 t = r; 279 _need_rebalancing = 0; 280 } 281 else 282 { 283 <T><C>AVLNode* l = r->lt; 284 set_lthread(r, rthread(l)); 285 if (rthread(l)) 286 r->lt = l; 287 else 288 r->lt = l->rt; 289 l->rt = r; 290 set_rthread(l, 0); 291 set_rthread(t, lthread(l)); 292 if (lthread(l)) 293 t->rt = l; 294 else 295 t->rt = l->lt; 296 l->lt = t; 297 set_lthread(l, 0); 298 if (bf(l) == AVLRIGHTHEAVY) 299 set_bf(t, AVLLEFTHEAVY); 300 else 301 set_bf(t, AVLBALANCED); 302 if (bf(l) == AVLLEFTHEAVY) 303 set_bf(r, AVLRIGHTHEAVY); 304 else 305 set_bf(r, AVLBALANCED); 306 set_bf(l, AVLBALANCED); 307 t = l; 308 _need_rebalancing = 0; 309 return; 310 } 311 } 312 } 313 } 314} 315 316 317<C>& <T><C>AVLMap::operator [] (<T&> item) 318{ 319 if (root == 0) 320 { 321 ++count; 322 root = new <T><C>AVLNode(item, def); 323 set_rthread(root, 1); 324 set_lthread(root, 1); 325 return root->cont; 326 } 327 else 328 { 329 _target_item = &item; 330 _need_rebalancing = 0; 331 _add(root); 332 return _found_node->cont; 333 } 334} 335 336 337void <T><C>AVLMap::_del(<T><C>AVLNode* par, <T><C>AVLNode*& t) 338{ 339 int comp; 340 if (_already_found) 341 { 342 if (rthread(t)) 343 comp = 0; 344 else 345 comp = 1; 346 } 347 else 348 comp = <T>CMP(*_target_item, t->item); 349 if (comp == 0) 350 { 351 if (lthread(t) && rthread(t)) 352 { 353 _found_node = t; 354 if (t == par->lt) 355 { 356 set_lthread(par, 1); 357 par->lt = t->lt; 358 } 359 else 360 { 361 set_rthread(par, 1); 362 par->rt = t->rt; 363 } 364 _need_rebalancing = 1; 365 return; 366 } 367 else if (lthread(t)) 368 { 369 _found_node = t; 370 <T><C>AVLNode* s = succ(t); 371 if (s != 0 && lthread(s)) 372 s->lt = t->lt; 373 t = t->rt; 374 _need_rebalancing = 1; 375 return; 376 } 377 else if (rthread(t)) 378 { 379 _found_node = t; 380 <T><C>AVLNode* p = pred(t); 381 if (p != 0 && rthread(p)) 382 p->rt = t->rt; 383 t = t->lt; 384 _need_rebalancing = 1; 385 return; 386 } 387 else // replace item & find someone deletable 388 { 389 <T><C>AVLNode* p = pred(t); 390 t->item = p->item; 391 t->cont = p->cont; 392 _already_found = 1; 393 comp = -1; // fall through below to left 394 } 395 } 396 397 if (comp < 0) 398 { 399 if (lthread(t)) 400 return; 401 _del(t, t->lt); 402 if (!_need_rebalancing) 403 return; 404 switch (bf(t)) 405 { 406 case AVLLEFTHEAVY: 407 set_bf(t, AVLBALANCED); 408 return; 409 case AVLBALANCED: 410 set_bf(t, AVLRIGHTHEAVY); 411 _need_rebalancing = 0; 412 return; 413 case AVLRIGHTHEAVY: 414 <T><C>AVLNode* r = t->rt; 415 switch (bf(r)) 416 { 417 case AVLBALANCED: 418 if (lthread(r)) 419 t->rt = r; 420 else 421 t->rt = r->lt; 422 set_rthread(t, lthread(r)); 423 r->lt = t; 424 set_lthread(r, 0); 425 set_bf(t, AVLRIGHTHEAVY); 426 set_bf(r, AVLLEFTHEAVY); 427 _need_rebalancing = 0; 428 t = r; 429 return; 430 case AVLRIGHTHEAVY: 431 if (lthread(r)) 432 t->rt = r; 433 else 434 t->rt = r->lt; 435 set_rthread(t, lthread(r)); 436 r->lt = t; 437 set_lthread(r, 0); 438 set_bf(t, AVLBALANCED); 439 set_bf(r, AVLBALANCED); 440 t = r; 441 return; 442 case AVLLEFTHEAVY: 443 <T><C>AVLNode* l = r->lt; 444 set_lthread(r, rthread(l)); 445 if (rthread(l)) 446 r->lt = l; 447 else 448 r->lt = l->rt; 449 l->rt = r; 450 set_rthread(l, 0); 451 set_rthread(t, lthread(l)); 452 if (lthread(l)) 453 t->rt = l; 454 else 455 t->rt = l->lt; 456 l->lt = t; 457 set_lthread(l, 0); 458 if (bf(l) == AVLRIGHTHEAVY) 459 set_bf(t, AVLLEFTHEAVY); 460 else 461 set_bf(t, AVLBALANCED); 462 if (bf(l) == AVLLEFTHEAVY) 463 set_bf(r, AVLRIGHTHEAVY); 464 else 465 set_bf(r, AVLBALANCED); 466 set_bf(l, AVLBALANCED); 467 t = l; 468 return; 469 } 470 } 471 } 472 else 473 { 474 if (rthread(t)) 475 return; 476 _del(t, t->rt); 477 if (!_need_rebalancing) 478 return; 479 switch (bf(t)) 480 { 481 case AVLRIGHTHEAVY: 482 set_bf(t, AVLBALANCED); 483 return; 484 case AVLBALANCED: 485 set_bf(t, AVLLEFTHEAVY); 486 _need_rebalancing = 0; 487 return; 488 case AVLLEFTHEAVY: 489 <T><C>AVLNode* l = t->lt; 490 switch (bf(l)) 491 { 492 case AVLBALANCED: 493 if (rthread(l)) 494 t->lt = l; 495 else 496 t->lt = l->rt; 497 set_lthread(t, rthread(l)); 498 l->rt = t; 499 set_rthread(l, 0); 500 set_bf(t, AVLLEFTHEAVY); 501 set_bf(l, AVLRIGHTHEAVY); 502 _need_rebalancing = 0; 503 t = l; 504 return; 505 case AVLLEFTHEAVY: 506 if (rthread(l)) 507 t->lt = l; 508 else 509 t->lt = l->rt; 510 set_lthread(t, rthread(l)); 511 l->rt = t; 512 set_rthread(l, 0); 513 set_bf(t, AVLBALANCED); 514 set_bf(l, AVLBALANCED); 515 t = l; 516 return; 517 case AVLRIGHTHEAVY: 518 <T><C>AVLNode* r = l->rt; 519 set_rthread(l, lthread(r)); 520 if (lthread(r)) 521 l->rt = r; 522 else 523 l->rt = r->lt; 524 r->lt = l; 525 set_lthread(r, 0); 526 set_lthread(t, rthread(r)); 527 if (rthread(r)) 528 t->lt = r; 529 else 530 t->lt = r->rt; 531 r->rt = t; 532 set_rthread(r, 0); 533 if (bf(r) == AVLLEFTHEAVY) 534 set_bf(t, AVLRIGHTHEAVY); 535 else 536 set_bf(t, AVLBALANCED); 537 if (bf(r) == AVLRIGHTHEAVY) 538 set_bf(l, AVLLEFTHEAVY); 539 else 540 set_bf(l, AVLBALANCED); 541 set_bf(r, AVLBALANCED); 542 t = r; 543 return; 544 } 545 } 546 } 547} 548 549 550 551void <T><C>AVLMap::del(<T&> item) 552{ 553 if (root == 0) return; 554 _need_rebalancing = 0; 555 _already_found = 0; 556 _found_node = 0; 557 _target_item = &item; 558 _del(root, root); 559 if (_found_node) 560 { 561 delete(_found_node); 562 if (--count == 0) 563 root = 0; 564 } 565} 566 567void <T><C>AVLMap::_kill(<T><C>AVLNode* t) 568{ 569 if (t != 0) 570 { 571 if (!lthread(t)) _kill(t->lt); 572 if (!rthread(t)) _kill(t->rt); 573 delete t; 574 } 575} 576 577 578<T><C>AVLMap::<T><C>AVLMap(<T><C>AVLMap& b) :<T><C>Map(b.def) 579{ 580 root = 0; 581 count = 0; 582 for (Pix i = b.first(); i != 0; b.next(i)) 583 (*this)[b.key(i)] = b.contents(i); 584} 585 586 587int <T><C>AVLMap::OK() 588{ 589 int v = 1; 590 if (root == 0) 591 v = count == 0; 592 else 593 { 594 int n = 1; 595 <T><C>AVLNode* trail = leftmost(); 596 <T><C>AVLNode* t = succ(trail); 597 while (t != 0) 598 { 599 ++n; 600 v &= <T>CMP(trail->item, t->item) < 0; 601 trail = t; 602 t = succ(t); 603 } 604 v &= n == count; 605 } 606 if (!v) error("invariant failure"); 607 return v; 608} 609