Rev 2496 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed
| Rev 2496 | Rev 2497 | ||
|---|---|---|---|
| Line 215... | Line 215... | ||
| 215 | if (top->lft != NULL) |
215 | if (top->lft != NULL) |
| 216 | top->lft->par = top; |
216 | top->lft->par = top; |
| 217 | par->par = top->par; |
217 | par->par = top->par; |
| 218 | top->par = par; |
218 | top->par = par; |
| 219 | par->rgt = top; |
219 | par->rgt = top; |
| - | 220 | par->balance = 0; |
|
| 220 | par->balance = top->balance = 0; |
221 | top->balance = 0; |
| 221 | *dpc = par; |
222 | *dpc = par; |
| 222 | } else { |
223 | } else { |
| 223 | /* |
224 | /* |
| 224 | * LR rotation. |
225 | * LR rotation. |
| 225 | */ |
226 | */ |
| Line 240... | Line 241... | ||
| 240 | 241 | ||
| 241 | if (gpa->balance == -1) { |
242 | if (gpa->balance == -1) { |
| 242 | par->balance = 0; |
243 | par->balance = 0; |
| 243 | top->balance = 1; |
244 | top->balance = 1; |
| 244 | } else if (gpa->balance == 0) { |
245 | } else if (gpa->balance == 0) { |
| - | 246 | par->balance = 0; |
|
| 245 | par->balance = top->balance = 0; |
247 | top->balance = 0; |
| 246 | } else { |
248 | } else { |
| 247 | par->balance = -1; |
249 | par->balance = -1; |
| 248 | top->balance = 0; |
250 | top->balance = 0; |
| 249 | } |
251 | } |
| 250 | gpa->balance = 0; |
252 | gpa->balance = 0; |
| Line 260... | Line 262... | ||
| 260 | if (top->rgt != NULL) |
262 | if (top->rgt != NULL) |
| 261 | top->rgt->par = top; |
263 | top->rgt->par = top; |
| 262 | par->par = top->par; |
264 | par->par = top->par; |
| 263 | top->par = par; |
265 | top->par = par; |
| 264 | par->lft = top; |
266 | par->lft = top; |
| - | 267 | par->balance = 0; |
|
| 265 | par->balance = top->balance = 0; |
268 | top->balance = 0; |
| 266 | *dpc = par; |
269 | *dpc = par; |
| 267 | } else { |
270 | } else { |
| 268 | /* |
271 | /* |
| 269 | * RL rotation. |
272 | * RL rotation. |
| 270 | */ |
273 | */ |
| Line 285... | Line 288... | ||
| 285 | 288 | ||
| 286 | if (gpa->balance == 1) { |
289 | if (gpa->balance == 1) { |
| 287 | par->balance = 0; |
290 | par->balance = 0; |
| 288 | top->balance = -1; |
291 | top->balance = -1; |
| 289 | } else if (gpa->balance == 0) { |
292 | } else if (gpa->balance == 0) { |
| - | 293 | par->balance = 0; |
|
| 290 | par->balance = top->balance = 0; |
294 | top->balance = 0; |
| 291 | } else { |
295 | } else { |
| 292 | par->balance = 1; |
296 | par->balance = 1; |
| 293 | top->balance = 0; |
297 | top->balance = 0; |
| 294 | } |
298 | } |
| 295 | gpa->balance = 0; |
299 | gpa->balance = 0; |
| Line 302... | Line 306... | ||
| 302 | return; |
306 | return; |
| 303 | } |
307 | } |
| 304 | 308 | ||
| 305 | } |
309 | } |
| 306 | 310 | ||
| - | 311 | /** Repair the tree after reparenting node u. |
|
| - | 312 | * |
|
| - | 313 | * If node u has no parent, mark it as the root of the whole tree. Otherwise |
|
| - | 314 | * node v represents stale address of one of the children of node u's parent. |
|
| - | 315 | * Replace v with w as node u parent's child (for most uses, u and w will be the |
|
| - | 316 | * same). |
|
| - | 317 | * |
|
| - | 318 | * @param t AVL tree. |
|
| - | 319 | * @param u Node whose new parent has a stale child pointer. |
|
| - | 320 | * @param v Stale child of node u's new parent. |
|
| - | 321 | * @param w New child of node u's new parent. |
|
| - | 322 | * @param dir If not NULL, address of the variable where to store information |
|
| - | 323 | * about whether w replaced v in the left or the right subtree of |
|
| - | 324 | * u's new parent. |
|
| - | 325 | * @param ro Read only operation; do not modify any tree pointers. This is |
|
| - | 326 | * useful for tracking direction via the dir pointer. |
|
| - | 327 | * |
|
| - | 328 | * @return Zero if w became the new root of the tree, otherwise return |
|
| - | 329 | * non-zero. |
|
| - | 330 | */ |
|
| - | 331 | static int |
|
| - | 332 | repair(avltree_t *t, avltree_node_t *u, avltree_node_t *v, avltree_node_t *w, |
|
| - | 333 | int *dir, int ro) |
|
| - | 334 | { |
|
| - | 335 | if (u->par == NULL) { |
|
| - | 336 | if (!ro) |
|
| - | 337 | t->root = w; |
|
| - | 338 | return 0; |
|
| - | 339 | } else { |
|
| - | 340 | if (u->par->lft == v) { |
|
| - | 341 | if (!ro) |
|
| - | 342 | u->par->lft = w; |
|
| - | 343 | if (dir) |
|
| - | 344 | *dir = LEFT; |
|
| - | 345 | } else { |
|
| - | 346 | ASSERT(u->par->rgt == v); |
|
| - | 347 | if (!ro) |
|
| - | 348 | u->par->rgt = w; |
|
| - | 349 | if (dir) |
|
| - | 350 | *dir = RIGHT; |
|
| - | 351 | } |
|
| - | 352 | } |
|
| - | 353 | return 1; |
|
| - | 354 | } |
|
| - | 355 | ||
| - | 356 | #define REBALANCE(DIR1, DIR2, SIGN) \ |
|
| - | 357 | if (cur->balance == -1 * SIGN) { \ |
|
| - | 358 | par->balance = 0; \ |
|
| - | 359 | gpa->balance = 1 * SIGN; \ |
|
| - | 360 | if (gpa->DIR1) \ |
|
| - | 361 | gpa->DIR1->par = gpa; \ |
|
| - | 362 | par->DIR2->par = par; \ |
|
| - | 363 | } else if (cur->balance == 0) { \ |
|
| - | 364 | par->balance = 0; \ |
|
| - | 365 | gpa->balance = 0; \ |
|
| - | 366 | if (gpa->DIR1) \ |
|
| - | 367 | gpa->DIR1->par = gpa; \ |
|
| - | 368 | if (par->DIR2) \ |
|
| - | 369 | par->DIR2->par = par; \ |
|
| - | 370 | } else { \ |
|
| - | 371 | par->balance = -1 * SIGN; \ |
|
| - | 372 | gpa->balance = 0; \ |
|
| - | 373 | if (par->DIR2) \ |
|
| - | 374 | par->DIR2->par = par; \ |
|
| - | 375 | gpa->DIR1->par = gpa; \ |
|
| - | 376 | } \ |
|
| - | 377 | cur->balance = 0; |
|
| - | 378 | ||
| - | 379 | #define REBALANCE_LR() REBALANCE(lft, rgt, 1) |
|
| - | 380 | #define REBALANCE_RL() REBALANCE(rgt, lft, -1) |
|
| - | 381 | ||
| 307 | /** Delete a node from the AVL tree. |
382 | /** Delete a node from the AVL tree. |
| 308 | * |
383 | * |
| 309 | * Because multiple identical keys are allowed, the parent pointers are |
384 | * Because multiple identical keys are allowed, the parent pointers are |
| 310 | * essential during deletion. |
385 | * essential during deletion. |
| 311 | * |
386 | * |
| Line 315... | Line 390... | ||
| 315 | void avltree_delete(avltree_t *t, avltree_node_t *node) |
390 | void avltree_delete(avltree_t *t, avltree_node_t *node) |
| 316 | { |
391 | { |
| 317 | avltree_node_t *cur; |
392 | avltree_node_t *cur; |
| 318 | avltree_node_t *par; |
393 | avltree_node_t *par; |
| 319 | avltree_node_t *gpa; |
394 | avltree_node_t *gpa; |
| 320 | uint8_t dir; |
395 | int dir; |
| 321 | 396 | ||
| 322 | ASSERT(t); |
397 | ASSERT(t); |
| 323 | ASSERT(node); |
398 | ASSERT(node); |
| 324 | 399 | ||
| 325 | if (node->lft == NULL) { |
400 | if (node->lft == NULL) { |
| 326 | if (node->rgt) { |
401 | if (node->rgt) { |
| 327 | /* |
402 | /* |
| 328 | * Replace the node with its only right son. |
403 | * Replace the node with its only right son. |
| 329 | * |
404 | * |
| 330 | * Balance of the right son will be repaired in the |
405 | * Balance of the right son will be repaired in the |
| Line 352... | Line 427... | ||
| 352 | cur = NULL; |
427 | cur = NULL; |
| 353 | dir = (gpa->lft == node) ? LEFT: RIGHT; |
428 | dir = (gpa->lft == node) ? LEFT: RIGHT; |
| 354 | } |
429 | } |
| 355 | } else { |
430 | } else { |
| 356 | /* |
431 | /* |
| 357 | * The node has left and right son. Find a node with the |
432 | * The node has the left son. Find a node with the smallest key |
| 358 | * smallest key in the left subtree and replace the deleted node |
433 | * in the left subtree and replace the deleted node with that |
| 359 | * with that node. |
434 | * node. |
| 360 | */ |
435 | */ |
| 361 | for (cur = node->lft; cur->rgt != NULL; cur = cur->rgt) |
436 | for (cur = node->lft; cur->rgt != NULL; cur = cur->rgt) |
| 362 | ; |
437 | ; |
| 363 | 438 | ||
| 364 | if (cur != node->lft) { |
439 | if (cur != node->lft) { |
| Line 400... | Line 475... | ||
| 400 | 475 | ||
| 401 | /* |
476 | /* |
| 402 | * Repair the parent node's pointer which pointed previously to the |
477 | * Repair the parent node's pointer which pointed previously to the |
| 403 | * deleted node. |
478 | * deleted node. |
| 404 | */ |
479 | */ |
| 405 | if (node->par == NULL) { |
480 | (void) repair(t, node, node, cur, NULL, false); |
| 406 | t->root = cur; |
- | |
| 407 | } else { |
- | |
| 408 | if (node->par->lft == node) { |
- | |
| 409 | node->par->lft = cur; |
- | |
| 410 | } else { |
- | |
| 411 | node->par->rgt = cur; |
- | |
| 412 | } |
- | |
| 413 | } |
- | |
| 414 | 481 | ||
| 415 | /* |
482 | /* |
| 416 | * Repair cycle which repairs balances of nodes on the way from from the |
483 | * Repair cycle which repairs balances of nodes on the way from from the |
| 417 | * cut-off node up to the root. |
484 | * cut-off node up to the root. |
| 418 | */ |
485 | */ |
| Line 448... | Line 515... | ||
| 448 | /* |
515 | /* |
| 449 | * Repair balances and paternity of |
516 | * Repair balances and paternity of |
| 450 | * children, depending on the balance |
517 | * children, depending on the balance |
| 451 | * factor of the grand child (cur). |
518 | * factor of the grand child (cur). |
| 452 | */ |
519 | */ |
| 453 | if (cur->balance == 1) { |
- | |
| 454 | par->balance = 0; |
- | |
| 455 | gpa->balance = -1; |
- | |
| 456 | if (gpa->rgt) |
520 | REBALANCE_RL(); |
| 457 | gpa->rgt->par = gpa; |
- | |
| 458 | par->lft->par = par; |
- | |
| 459 | } else if (cur->balance == 0) { |
- | |
| 460 | par->balance = gpa->balance = 0; |
- | |
| 461 | if (gpa->rgt) |
- | |
| 462 | gpa->rgt->par = gpa; |
- | |
| 463 | if (par->lft) |
- | |
| 464 | par->lft->par = par; |
- | |
| 465 | } else { |
- | |
| 466 | par->balance = 1; |
- | |
| 467 | gpa->balance = 0; |
- | |
| 468 | if (par->lft) |
- | |
| 469 | par->lft->par = par; |
- | |
| 470 | gpa->rgt->par = gpa; |
- | |
| 471 | } |
- | |
| 472 | cur->balance = 0; |
- | |
| 473 | 521 | ||
| 474 | /* |
522 | /* |
| 475 | * Repair paternity. |
523 | * Repair paternity. |
| 476 | */ |
524 | */ |
| 477 | cur->par = gpa->par; |
525 | cur->par = gpa->par; |
| 478 | gpa->par = cur; |
526 | gpa->par = cur; |
| 479 | par->par = cur; |
527 | par->par = cur; |
| 480 | 528 | ||
| 481 | /* |
- | |
| 482 | * Repair the pointer which pointed to |
529 | if (!repair(t, cur, gpa, cur, &dir, |
| 483 | * the balanced node. If it was root |
- | |
| 484 | * then the balancing is finished. |
- | |
| 485 | * Otherwise continue with the next |
- | |
| 486 | * iteration (parent node). |
- | |
| 487 | */ |
530 | false)) |
| 488 | if (cur->par == NULL) { |
- | |
| 489 | t->root = cur; |
- | |
| 490 | break; |
531 | break; |
| 491 | } else { |
- | |
| 492 | if (cur->par->lft == gpa) { |
- | |
| 493 | cur->par->lft = cur; |
- | |
| 494 | dir = LEFT; |
- | |
| 495 | } else { |
- | |
| 496 | cur->par->rgt = cur; |
- | |
| 497 | dir = RIGHT; |
- | |
| 498 | } |
- | |
| 499 | } |
- | |
| 500 | gpa = cur->par; |
532 | gpa = cur->par; |
| 501 | } else { |
533 | } else { |
| 502 | /* |
534 | /* |
| 503 | * RR rotation. |
535 | * RR rotation. |
| 504 | */ |
536 | */ |
| Line 523... | Line 555... | ||
| 523 | * balanced. |
555 | * balanced. |
| 524 | */ |
556 | */ |
| 525 | par->balance = -1; |
557 | par->balance = -1; |
| 526 | gpa->balance = 1; |
558 | gpa->balance = 1; |
| 527 | 559 | ||
| 528 | /* |
- | |
| 529 | * Repair the pointer which |
- | |
| 530 | * pointed to the balanced node |
- | |
| 531 | * and finish balancing. |
- | |
| 532 | */ |
- | |
| 533 | if (par->par == NULL) { |
- | |
| 534 | t->root = par; |
- | |
| 535 | } else { |
- | |
| 536 | if (par->par->lft == |
560 | (void) repair(t, par, gpa, par, |
| 537 | gpa) { |
- | |
| 538 | par->par->lft = |
- | |
| 539 | par; |
- | |
| 540 | } else { |
- | |
| 541 | par->par->rgt = |
- | |
| 542 | par; |
561 | NULL, false); |
| 543 | } |
- | |
| 544 | } |
- | |
| 545 | break; |
562 | break; |
| 546 | } else { |
563 | } else { |
| 547 | par->balance = gpa->balance = 0; |
564 | par->balance = 0; |
| 548 | /* |
- | |
| 549 | * Repair the pointer which |
- | |
| 550 | * pointed to the balanced node. |
565 | gpa->balance = 0; |
| 551 | * If it was root then balancing |
- | |
| 552 | * is finished. Otherwise |
- | |
| 553 | * continue with the next |
- | |
| 554 | * iteration (parent node). |
- | |
| 555 | */ |
- | |
| 556 | if (par->par == NULL) { |
566 | if (!repair(t, par, gpa, par, |
| 557 | t->root = par; |
567 | &dir, false)) |
| 558 | break; |
568 | break; |
| 559 | } else { |
- | |
| 560 | if (par->par->lft == |
- | |
| 561 | gpa) { |
- | |
| 562 | par->par->lft = |
- | |
| 563 | par; |
- | |
| 564 | dir = LEFT; |
- | |
| 565 | } else { |
- | |
| 566 | par->par->rgt = |
- | |
| 567 | par; |
- | |
| 568 | dir = RIGHT; |
- | |
| 569 | } |
- | |
| 570 | } |
- | |
| 571 | } |
569 | } |
| 572 | gpa = par->par; |
570 | gpa = par->par; |
| 573 | } |
571 | } |
| 574 | } else { |
572 | } else { |
| 575 | /* |
573 | /* |
| 576 | * Repair the pointer which pointed to the |
574 | * Repair the pointer which pointed to the |
| 577 | * balanced node. If it was root then balancing |
575 | * balanced node. If it was root then balancing |
| 578 | * is finished else continue with the next |
576 | * is finished else continue with the next |
| 579 | * iteration (parent node). |
577 | * iteration (parent node). |
| 580 | */ |
578 | */ |
| 581 | if (!gpa->par) |
579 | if (!repair(t, gpa, gpa, NULL, &dir, true)) |
| 582 | break; |
580 | break; |
| 583 | - | ||
| 584 | if (gpa->par->lft == gpa) { |
- | |
| 585 | dir = LEFT; |
- | |
| 586 | } else { |
- | |
| 587 | dir = RIGHT; |
- | |
| 588 | } |
- | |
| 589 | gpa = gpa->par; |
581 | gpa = gpa->par; |
| 590 | } |
582 | } |
| 591 | } else { |
583 | } else { |
| 592 | /* |
584 | /* |
| 593 | * Deletion was made in the right subtree. |
585 | * Deletion was made in the right subtree. |
| Line 619... | Line 611... | ||
| 619 | /* |
611 | /* |
| 620 | * Repair balances and paternity of |
612 | * Repair balances and paternity of |
| 621 | * children, depending on the balance |
613 | * children, depending on the balance |
| 622 | * factor of the grand child (cur). |
614 | * factor of the grand child (cur). |
| 623 | */ |
615 | */ |
| 624 | if (cur->balance == -1) { |
- | |
| 625 | par->balance = 0; |
- | |
| 626 | gpa->balance = 1; |
- | |
| 627 | if (gpa->lft) |
616 | REBALANCE_LR(); |
| 628 | gpa->lft->par = gpa; |
- | |
| 629 | par->rgt->par = par; |
- | |
| 630 | } else if (cur->balance == 0) { |
- | |
| 631 | par->balance = gpa->balance = 0; |
- | |
| 632 | if (gpa->lft) |
- | |
| 633 | gpa->lft->par = gpa; |
- | |
| 634 | if (par->rgt) |
- | |
| 635 | par->rgt->par = par; |
- | |
| 636 | } else { |
- | |
| 637 | par->balance = -1; |
- | |
| 638 | gpa->balance = 0; |
- | |
| 639 | if (par->rgt) |
- | |
| 640 | par->rgt->par = par; |
- | |
| 641 | gpa->lft->par = gpa; |
- | |
| 642 | } |
- | |
| 643 | cur->balance = 0; |
- | |
| 644 | 617 | ||
| 645 | /* |
618 | /* |
| 646 | * Repair paternity. |
619 | * Repair paternity. |
| 647 | */ |
620 | */ |
| 648 | cur->par = gpa->par; |
621 | cur->par = gpa->par; |
| 649 | gpa->par = cur; |
622 | gpa->par = cur; |
| 650 | par->par = cur; |
623 | par->par = cur; |
| 651 | 624 | ||
| 652 | /* |
- | |
| 653 | * Repair the pointer which pointed to |
625 | if (!repair(t, cur, gpa, cur, &dir, |
| 654 | * the balanced node. If it was root |
- | |
| 655 | * then balancing is finished. Otherwise |
- | |
| 656 | * continue with the next iteration |
- | |
| 657 | * (parent node). |
626 | false)) |
| 658 | */ |
- | |
| 659 | if (cur->par == NULL) { |
- | |
| 660 | t->root = cur; |
- | |
| 661 | break; |
627 | break; |
| 662 | } else { |
- | |
| 663 | if (cur->par->lft == gpa) { |
- | |
| 664 | cur->par->lft = cur; |
- | |
| 665 | dir = LEFT; |
- | |
| 666 | } else { |
- | |
| 667 | cur->par->rgt = cur; |
- | |
| 668 | dir = RIGHT; |
- | |
| 669 | } |
- | |
| 670 | } |
- | |
| 671 | gpa = cur->par; |
628 | gpa = cur->par; |
| 672 | } else { |
629 | } else { |
| 673 | /* |
630 | /* |
| 674 | * LL rotation. |
631 | * LL rotation. |
| 675 | */ |
632 | */ |
| 676 | 633 | ||
| 677 | gpa->lft = par->rgt; |
634 | gpa->lft = par->rgt; |
| 678 | if (par->rgt) |
635 | if (par->rgt) |
| 679 | par->rgt->par = gpa; |
636 | par->rgt->par = gpa; |
| 680 | par->rgt = gpa; |
637 | par->rgt = gpa; |
| 681 | /* |
638 | /* |
| Line 693... | Line 650... | ||
| 693 | * balanced. |
650 | * balanced. |
| 694 | */ |
651 | */ |
| 695 | par->balance = 1; |
652 | par->balance = 1; |
| 696 | gpa->balance = -1; |
653 | gpa->balance = -1; |
| 697 | 654 | ||
| 698 | /* |
- | |
| 699 | * Repair the pointer which |
- | |
| 700 | * pointed to the balanced node |
- | |
| 701 | * and finish balancing. |
- | |
| 702 | */ |
- | |
| 703 | if (par->par == NULL) { |
- | |
| 704 | t->root = par; |
- | |
| 705 | } else { |
- | |
| 706 | if (par->par->lft == |
655 | (void) repair(t, par, gpa, par, |
| 707 | gpa) { |
- | |
| 708 | par->par->lft = |
- | |
| 709 | par; |
- | |
| 710 | } else { |
- | |
| 711 | par->par->rgt = |
- | |
| 712 | par; |
656 | NULL, false); |
| 713 | } |
- | |
| 714 | } |
- | |
| 715 | break; |
657 | break; |
| 716 | } else { |
658 | } else { |
| - | 659 | par->balance = 0; |
|
| 717 | par->balance = gpa->balance = 0; |
660 | gpa->balance = 0; |
| 718 | 661 | ||
| 719 | /* |
- | |
| 720 | * Repair the pointer which |
- | |
| 721 | * pointed to the balanced node. |
- | |
| 722 | * If it was root then balancing |
- | |
| 723 | * is finished. Otherwise |
- | |
| 724 | * continue with the next |
- | |
| 725 | * iteration (parent node). |
- | |
| 726 | */ |
- | |
| 727 | if (par->par == NULL) { |
662 | if (!repair(t, par, gpa, par, |
| 728 | t->root = par; |
663 | &dir, false)) |
| 729 | break; |
664 | break; |
| 730 | } else { |
- | |
| 731 | if (par->par->lft == |
- | |
| 732 | gpa) { |
- | |
| 733 | par->par->lft = |
- | |
| 734 | par; |
- | |
| 735 | dir = LEFT; |
- | |
| 736 | } else { |
- | |
| 737 | par->par->rgt = |
- | |
| 738 | par; |
- | |
| 739 | dir = RIGHT; |
- | |
| 740 | } |
- | |
| 741 | } |
- | |
| 742 | } |
665 | } |
| 743 | gpa = par->par; |
666 | gpa = par->par; |
| 744 | } |
667 | } |
| 745 | } else { |
668 | } else { |
| 746 | /* |
669 | /* |
| 747 | * Repair the pointer which pointed to the |
670 | * Repair the pointer which pointed to the |
| 748 | * balanced node. If it was root then balancing |
671 | * balanced node. If it was root then balancing |
| 749 | * is finished. Otherwise continue with the next |
672 | * is finished. Otherwise continue with the next |
| 750 | * iteration (parent node). |
673 | * iteration (parent node). |
| 751 | */ |
674 | */ |
| 752 | if (!gpa->par) |
675 | if (!repair(t, gpa, gpa, NULL, &dir, true)) |
| 753 | break; |
676 | break; |
| 754 | - | ||
| 755 | if (gpa->par->lft == gpa) { |
- | |
| 756 | dir = LEFT; |
- | |
| 757 | } else { |
- | |
| 758 | dir = RIGHT; |
- | |
| 759 | } |
- | |
| 760 | gpa = gpa->par; |
677 | gpa = gpa->par; |
| 761 | } |
678 | } |
| 762 | } |
679 | } |
| 763 | } |
680 | } |
| 764 | } |
681 | } |
| Line 790... | Line 707... | ||
| 790 | return true; |
707 | return true; |
| 791 | } |
708 | } |
| 792 | 709 | ||
| 793 | /** @} |
710 | /** @} |
| 794 | */ |
711 | */ |
| - | 712 | ||