rbtree.c Source File (original) (raw)

35#define RBTBLACK (0)

36#define RBTRED (1)

42{

43 RBTNode *root;

55};

61#define RBTNIL (&sentinel)

64{

66};

100

107 void *arg)

108{

110

112

114 tree->node_size = node_size;

115 tree->comparator = comparator;

116 tree->combiner = combiner;

117 tree->allocfunc = allocfunc;

118 tree->freefunc = freefunc;

119

121

123}

124

125

126static inline void

128{

130}

131

132

133

134

135

136

137

138

139

140

141

142

143

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}

163

164

165

166

167

168

169

170

173{

176

177 while (node != RBTNIL)

178 {

180

181 if (equal_match && cmp == 0)

182 return node;

183 else if (cmp < 0)

184 {

185 greater = node;

186 node = node->left;

187 }

188 else

189 node = node->right;

190 }

191

192 return greater;

193}

194

195

196

197

198

199

200

201

204{

207

208 while (node != RBTNIL)

209 {

211

212 if (equal_match && cmp == 0)

213 return node;

214 else if (cmp > 0)

215 {

216 lesser = node;

217 node = node->right;

218 }

219 else

220 node = node->left;

221 }

222

223 return lesser;

224}

225

226

227

228

229

230

231

232

233

236{

239

240 while (node != RBTNIL)

241 {

242 leftmost = node;

243 node = node->left;

244 }

245

246 if (leftmost != RBTNIL)

247 return leftmost;

248

249 return NULL;

250}

251

252

253

254

255

256

257

258

259

260

261

262static void

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}

292

293

294

295

296

297

298

299static void

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}

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343static void

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}

434

435

436

437

438

439

440

441

442

443

444

445

446

447

448

449

450

451

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}

512

513

514

515

516

517

518

519

520static void

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}

614

615

616

617

618static void

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}

684

685

686

687

688

689

690

691

692

693

694void

696{

698}

699

700

701

702

703

706{

708 {

712

714 }

715

717 {

721

723 }

724

725 for (;;)

726 {

728

731 {

733 break;

734 }

735

737 break;

738

739

740

741 }

742

744}

745

748{

750 {

754

756 }

757

759 {

763

765 }

766

767 for (;;)

768 {

770

773 {

775 break;

776 }

777

779 break;

780

781

782

783 }

784

786}

787

788

789

790

791

792

793

794

795

796

797

798

799

800

801void

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}

821

822

823

824

827{

829 return NULL;

830

831 return iter->iterate(iter);

832}

Assert(PointerIsAligned(start, uint64))

RBTNode * rbt_find_great(RBTree *rbt, const RBTNode *data, bool equal_match)

RBTNode * rbt_iterate(RBTreeIterator *iter)

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

static RBTNode * rbt_right_left_iterator(RBTreeIterator *iter)

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

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

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

static RBTNode * rbt_left_right_iterator(RBTreeIterator *iter)

RBTNode * rbt_insert(RBTree *rbt, const RBTNode *data, bool *isNew)

void rbt_begin_iterate(RBTree *rbt, RBTOrderControl ctrl, RBTreeIterator *iter)

static void rbt_delete_node(RBTree *rbt, RBTNode *z)

RBTNode * rbt_find_less(RBTree *rbt, const RBTNode *data, bool equal_match)

RBTree * rbt_create(Size node_size, rbt_comparator comparator, rbt_combiner combiner, rbt_allocfunc allocfunc, rbt_freefunc freefunc, void *arg)

RBTNode * rbt_find(RBTree *rbt, const RBTNode *data)

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

RBTNode * rbt_leftmost(RBTree *rbt)

void rbt_delete(RBTree *rbt, RBTNode *node)

void(* rbt_freefunc)(RBTNode *x, void *arg)

void(* rbt_combiner)(RBTNode *existing, const RBTNode *newdata, void *arg)

RBTNode *(* rbt_allocfunc)(void *arg)

int(* rbt_comparator)(const RBTNode *a, const RBTNode *b, void *arg)

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

RBTNode *(* iterate)(RBTreeIterator *iter)

rbt_comparator comparator