PostgreSQL Source Code: src/backend/lib/rbtree.c File Reference (original) (raw)

#include "[postgres.h](postgres%5F8h%5Fsource.html)"
#include "[lib/rbtree.h](rbtree%5F8h%5Fsource.html)"

Go to the source code of this file.

◆ RBTBLACK

◆ RBTNIL

◆ RBTRED

◆ rbt_begin_iterate()

Definition at line 802 of file rbtree.c.

803{

804

805 iter->rbt = rbt;

808

809 switch (ctrl)

810 {

811 case LeftRightWalk:

813 break;

814 case RightLeftWalk:

816 break;

817 default:

818 elog(ERROR, "unrecognized rbtree iteration order: %d", ctrl);

819 }

820}

static RBTNode * rbt_right_left_iterator(RBTreeIterator *iter)

static RBTNode * rbt_left_right_iterator(RBTreeIterator *iter)

RBTNode *(* iterate)(RBTreeIterator *iter)

References elog, ERROR, RBTreeIterator::is_over, RBTreeIterator::iterate, RBTreeIterator::last_visited, LeftRightWalk, RBTreeIterator::rbt, rbt_left_right_iterator(), rbt_right_left_iterator(), RBTNIL, RightLeftWalk, and RBTree::root.

Referenced by ginBeginBAScan(), testleftright(), and testrightleft().

◆ rbt_copy_data()

◆ rbt_create()

◆ rbt_delete()

◆ rbt_delete_fixup()

Definition at line 521 of file rbtree.c.

522{

523

524

525

526

527

529 {

530

531

532

533

534

535

536

537 if (x == x->parent->left)

538 {

539 RBTNode *w = x->parent->right;

540

542 {

544 x->parent->color = RBTRED;

545

547 w = x->parent->right;

548 }

549

551 {

553

554 x = x->parent;

555 }

556 else

557 {

559 {

562

564 w = x->parent->right;

565 }

566 w->color = x->parent->color;

569

571 x = rbt->root;

572 }

573 }

574 else

575 {

576 RBTNode *w = x->parent->left;

577

579 {

581 x->parent->color = RBTRED;

582

584 w = x->parent->left;

585 }

586

588 {

590

591 x = x->parent;

592 }

593 else

594 {

596 {

599

601 w = x->parent->left;

602 }

603 w->color = x->parent->color;

606

608 x = rbt->root;

609 }

610 }

611 }

613}

static void rbt_rotate_right(RBTree *rbt, RBTNode *x)

static void rbt_rotate_left(RBTree *rbt, RBTNode *x)

References RBTNode::color, RBTNode::left, rbt_rotate_left(), rbt_rotate_right(), RBTBLACK, RBTRED, RBTNode::right, RBTree::root, and x.

Referenced by rbt_delete_node().

◆ rbt_delete_node()

Definition at line 619 of file rbtree.c.

620{

622 *y;

623

624

625 if (!z || z == RBTNIL)

626 return;

627

628

629

630

631

632

634 {

635

636 y = z;

637 }

638 else

639 {

640

642 while (y->left != RBTNIL)

643 y = y->left;

644 }

645

646

648 x = y->left;

649 else

650 x = y->right;

651

652

653 x->parent = y->parent;

654 if (y->parent)

655 {

656 if (y == y->parent->left)

657 y->parent->left = x;

658 else

659 y->parent->right = x;

660 }

661 else

662 {

664 }

665

666

667

668

669

670 if (y != z)

672

673

674

675

676

679

680

683}

static void rbt_delete_fixup(RBTree *rbt, RBTNode *x)

static void rbt_copy_data(RBTree *rbt, RBTNode *dest, const RBTNode *src)

References RBTree::arg, RBTree::freefunc, RBTNode::left, rbt_copy_data(), rbt_delete_fixup(), RBTBLACK, RBTNIL, RBTNode::right, RBTree::root, x, and y.

Referenced by rbt_delete().

◆ rbt_find()

Definition at line 145 of file rbtree.c.

146{

148

149 while (node != RBTNIL)

150 {

152

153 if (cmp == 0)

154 return node;

155 else if (cmp < 0)

156 node = node->left;

157 else

158 node = node->right;

159 }

160

161 return NULL;

162}

static int cmp(const chr *x, const chr *y, size_t len)

rbt_comparator comparator

References RBTree::arg, cmp(), RBTree::comparator, data, RBTNode::left, RBTNIL, RBTNode::right, and RBTree::root.

Referenced by testdelete(), and testfind().

◆ rbt_find_great()

◆ rbt_find_less()

◆ rbt_insert()

Definition at line 453 of file rbtree.c.

454{

456 *parent,

457 *x;

459

460

461 current = rbt->root;

462 parent = NULL;

463 cmp = 0;

464

465 while (current != RBTNIL)

466 {

468 if (cmp == 0)

469 {

470

471

472

474 *isNew = false;

475 return current;

476 }

477 parent = current;

478 current = (cmp < 0) ? current->left : current->right;

479 }

480

481

482

483

484 *isNew = true;

485

487

489

492 x->parent = parent;

494

495

496 if (parent)

497 {

498 if (cmp < 0)

499 parent->left = x;

500 else

502 }

503 else

504 {

506 }

507

509

510 return x;

511}

static void rbt_insert_fixup(RBTree *rbt, RBTNode *x)

References RBTree::allocfunc, RBTree::arg, cmp(), RBTree::combiner, RBTree::comparator, data, RBTNode::left, rbt_copy_data(), rbt_insert_fixup(), RBTNIL, RBTRED, RBTNode::right, RBTree::root, and x.

Referenced by ginInsertBAEntry(), and rbt_populate().

◆ rbt_insert_fixup()

Definition at line 344 of file rbtree.c.

345{

346

347

348

349

350 while (x != rbt->root && x->parent->color == RBTRED)

351 {

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368 if (x->parent == x->parent->parent->left)

369 {

370 RBTNode *y = x->parent->parent->right;

371

373 {

374

377 x->parent->parent->color = RBTRED;

378

379 x = x->parent->parent;

380 }

381 else

382 {

383

384 if (x == x->parent->right)

385 {

386

387 x = x->parent;

389 }

390

391

393 x->parent->parent->color = RBTRED;

394

396 }

397 }

398 else

399 {

400

401 RBTNode *y = x->parent->parent->left;

402

404 {

405

408 x->parent->parent->color = RBTRED;

409

410 x = x->parent->parent;

411 }

412 else

413 {

414

415 if (x == x->parent->left)

416 {

417 x = x->parent;

419 }

421 x->parent->parent->color = RBTRED;

422

424 }

425 }

426 }

427

428

429

430

431

433}

References RBTNode::color, rbt_rotate_left(), rbt_rotate_right(), RBTBLACK, RBTRED, RBTree::root, x, and y.

Referenced by rbt_insert().

◆ rbt_iterate()

◆ rbt_left_right_iterator()

◆ rbt_leftmost()

◆ rbt_right_left_iterator()

◆ rbt_rotate_left()

Definition at line 263 of file rbtree.c.

264{

266

267

268 x->right = y->left;

270 y->left->parent = x;

271

272

274 y->parent = x->parent;

275 if (x->parent)

276 {

277 if (x == x->parent->left)

278 x->parent->left = y;

279 else

280 x->parent->right = y;

281 }

282 else

283 {

285 }

286

287

288 y->left = x;

290 x->parent = y;

291}

References RBTNIL, RBTree::root, x, and y.

Referenced by rbt_delete_fixup(), and rbt_insert_fixup().

◆ rbt_rotate_right()

Definition at line 300 of file rbtree.c.

301{

303

304

305 x->left = y->right;

307 y->right->parent = x;

308

309

311 y->parent = x->parent;

312 if (x->parent)

313 {

314 if (x == x->parent->right)

315 x->parent->right = y;

316 else

317 x->parent->left = y;

318 }

319 else

320 {

322 }

323

324

325 y->right = x;

327 x->parent = y;

328}

References RBTNIL, RBTree::root, x, and y.

Referenced by rbt_delete_fixup(), and rbt_insert_fixup().

◆ sentinel

Initial value:

Definition at line 63 of file rbtree.c.