sky/engine/platform/PODRedBlackTree.h - Issue 705373003: Remove PODIntervalTree and machinery.

Side by Side Diff: sky/engine/platform/PODRedBlackTree.h

Issue 705373003: Remove PODIntervalTree and machinery. (Closed) Base URL: git@github.com:domokit/mojo.git@master

Patch Set: Created 6 years, 1 month ago

Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.

Jump to:

OLD	NEW
	(Empty)
1 /*

2 * Copyright (C) 2010 Google Inc. All rights reserved.

3 *

4 * Redistribution and use in source and binary forms, with or without

5 * modification, are permitted provided that the following conditions

6 * are met:

7 *

8 * 1. Redistributions of source code must retain the above copyright

9 * notice, this list of conditions and the following disclaimer.

10 * 2. Redistributions in binary form must reproduce the above copyright

11 * notice, this list of conditions and the following disclaimer in the

12 * documentation and/or other materials provided with the distribution.

13 *

14 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY

15 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED

16 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE

17 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY

18 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES

19 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;

20 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND

21 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF

23 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

24 */

25

26 // A red-black tree, which is a form of a balanced binary tree. It

27 // supports efficient insertion, deletion and queries of comparable

28 // elements. The same element may be inserted multiple times. The

29 // algorithmic complexity of common operations is:

30 //

31 // Insertion: O(lg(n))

32 // Deletion: O(lg(n))

33 // Querying: O(lg(n))

34 //

35 // The data type T that is stored in this red-black tree must be only

36 // Plain Old Data (POD), or bottom out into POD. It must _not_ rely on

37 // having its destructor called. This implementation internally

38 // allocates storage in large chunks and does not call the destructor

39 // on each object.

40 //

41 // Type T must supply a default constructor, a copy constructor, and

42 // the "<" and "==" operators.

43 //

44 // In debug mode, printing of the data contained in the tree is

45 // enabled. This requires the template specialization to be available:

46 //

47 // template<> struct ValueToString<T> {

48 // static String string(const T& t);

49 // };

50 //

51 // Note that when complex types are stored in this red/black tree, it

52 // is possible that single invocations of the "<" and "==" operators

53 // will be insufficient to describe the ordering of elements in the

54 // tree during queries. As a concrete example, consider the case where

55 // intervals are stored in the tree sorted by low endpoint. The "<"

56 // operator on the Interval class only compares the low endpoint, but

57 // the "==" operator takes into account the high endpoint as well.

58 // This makes the necessary logic for querying and deletion somewhat

59 // more complex. In order to properly handle such situations, the

60 // property "needsFullOrderingComparisons" must be set to true on

61 // the tree.

62 //

63 // This red-black tree is designed to be _augmented_; subclasses can

64 // add additional and summary information to each node to efficiently

65 // store and index more complex data structures. A concrete example is

66 // the IntervalTree, which extends each node with a summary statistic

67 // to efficiently store one-dimensional intervals.

68 //

69 // The design of this red-black tree comes from Cormen, Leiserson,

70 // and Rivest, _Introduction to Algorithms_, MIT Press, 1990.

71

72 #ifndef PODRedBlackTree_h

73 #define PODRedBlackTree_h

74

75 #include "platform/PODFreeListArena.h"

76 #include "wtf/Assertions.h"

77 #include "wtf/Noncopyable.h"

78 #include "wtf/RefPtr.h"

79 #ifndef NDEBUG

80 #include "wtf/text/CString.h"

81 #include "wtf/text/StringBuilder.h"

82 #include "wtf/text/WTFString.h"

83 #endif

84

85 namespace blink {

86

87 #ifndef NDEBUG

88 template<class T>

89 struct ValueToString;

90 #endif

91

92 enum UninitializedTreeEnum {

93 UninitializedTree

94 };

95

96 template<class T>

97 class PODRedBlackTree {

98 public:

99 class Node;

100

101 // Visitor interface for walking all of the tree's elements.

102 class Visitor {

103 public:

104 virtual void visit(const T& data) = 0;

105 protected:

106 virtual ~Visitor() { }

107 };

108

109 // Constructs a new red-black tree without allocating an arena.

110 // isInitialized will return false in this case. initIfNeeded can be used

111 // to init the structure. This constructor is usefull for creating

112 // lazy initialized tree.

113 explicit PODRedBlackTree(UninitializedTreeEnum)

114 : m_root(0)

115 , m_needsFullOrderingComparisons(false)

116 #ifndef NDEBUG

117 , m_verboseDebugging(false)

118 #endif

119 {

120 }

121

122 // Constructs a new red-black tree, allocating temporary objects

123 // from a newly constructed PODFreeListArena.

124 PODRedBlackTree()

125 : m_arena(PODFreeListArena<Node>::create())

126 , m_root(0)

127 , m_needsFullOrderingComparisons(false)

128 #ifndef NDEBUG

129 , m_verboseDebugging(false)

130 #endif

131 {

132 }

133

134 // Constructs a new red-black tree, allocating temporary objects

135 // from the given PODArena.

136 explicit PODRedBlackTree(PassRefPtr<PODFreeListArena<Node> > arena)

137 : m_arena(arena)

138 , m_root(0)

139 , m_needsFullOrderingComparisons(false)

140 #ifndef NDEBUG

141 , m_verboseDebugging(false)

142 #endif

143 {

144 }

145

146 virtual ~PODRedBlackTree() { }

147

148 // Clearing will delete the contents of the tree. After this call

149 // isInitialized will return false.

150 void clear()

151 {

152 markFree(m_root);

153 m_arena = nullptr;

154 m_root = 0;

155 }

156

157 bool isInitialized() const

158 {

159 return m_arena;

160 }

161

162 void initIfNeeded()

163 {

164 if (!m_arena)

165 m_arena = PODFreeListArena<Node>::create();

166 }

167

168 void initIfNeeded(PODFreeListArena<Node>* arena)

169 {

170 if (!m_arena)

171 m_arena = arena;

172 }

173

174 void add(const T& data)

175 {

176 ASSERT(isInitialized());

177 Node* node = m_arena->template allocateObject<T>(data);

178 insertNode(node);

179 }

180

181 // Returns true if the datum was found in the tree.

182 bool remove(const T& data)

183 {

184 ASSERT(isInitialized());

185 Node* node = treeSearch(data);

186 if (node) {

187 deleteNode(node);

188 return true;

189 }

190 return false;

191 }

192

193 bool contains(const T& data) const

194 {

195 ASSERT(isInitialized());

196 return treeSearch(data);

197 }

198

199 void visitInorder(Visitor* visitor) const

200 {

201 ASSERT(isInitialized());

202 if (!m_root)

203 return;

204 visitInorderImpl(m_root, visitor);

205 }

206

207 int size() const

208 {

209 ASSERT(isInitialized());

210 Counter counter;

211 visitInorder(&counter);

212 return counter.count();

213 }

214

215 // See the class documentation for an explanation of this property.

216 void setNeedsFullOrderingComparisons(bool needsFullOrderingComparisons)

217 {

218 m_needsFullOrderingComparisons = needsFullOrderingComparisons;

219 }

220

221 virtual bool checkInvariants() const

222 {

223 ASSERT(isInitialized());

224 int blackCount;

225 return checkInvariantsFromNode(m_root, &blackCount);

226 }

227

228 #ifndef NDEBUG

229 // Dumps the tree's contents to the logging info stream for

230 // debugging purposes.

231 void dump() const

232 {

233 if (m_arena)

234 dumpFromNode(m_root, 0);

235 }

236

237 // Turns on or off verbose debugging of the tree, causing many

238 // messages to be logged during insertion and other operations in

239 // debug mode.

240 void setVerboseDebugging(bool verboseDebugging)

241 {

242 m_verboseDebugging = verboseDebugging;

243 }

244 #endif

245

246 enum Color {

247 Red = 1,

248 Black

249 };

250

251 // The base Node class which is stored in the tree. Nodes are only

252 // an internal concept; users of the tree deal only with the data

253 // they store in it.

254 class Node {

255 WTF_MAKE_NONCOPYABLE(Node);

256 public:

257 // Constructor. Newly-created nodes are colored red.

258 explicit Node(const T& data)

259 : m_left(0)

260 , m_right(0)

261 , m_parent(0)

262 , m_color(Red)

263 , m_data(data)

264 {

265 }

266

267 virtual ~Node() { }

268

269 Color color() const { return m_color; }

270 void setColor(Color color) { m_color = color; }

271

272 // Fetches the user data.

273 T& data() { return m_data; }

274

275 // Copies all user-level fields from the source node, but not

276 // internal fields. For example, the base implementation of this

277 // method copies the "m_data" field, but not the child or parent

278 // fields. Any augmentation information also does not need to be

279 // copied, as it will be recomputed. Subclasses must call the

280 // superclass implementation.

281 virtual void copyFrom(Node* src) { m_data = src->data(); }

282

283 Node* left() const { return m_left; }

284 void setLeft(Node* node) { m_left = node; }

285

286 Node* right() const { return m_right; }

287 void setRight(Node* node) { m_right = node; }

288

289 Node* parent() const { return m_parent; }

290 void setParent(Node* node) { m_parent = node; }

291

292 private:

293 Node* m_left;

294 Node* m_right;

295 Node* m_parent;

296 Color m_color;

297 T m_data;

298 };

299

300 protected:

301 // Returns the root of the tree, which is needed by some subclasses.

302 Node* root() const { return m_root; }

303

304 private:

305 // This virtual method is the hook that subclasses should use when

306 // augmenting the red-black tree with additional per-node summary

307 // information. For example, in the case of an interval tree, this

308 // is used to compute the maximum endpoint of the subtree below the

309 // given node based on the values in the left and right children. It

310 // is guaranteed that this will be called in the correct order to

311 // properly update such summary information based only on the values

312 // in the left and right children. This method should return true if

313 // the node's summary information changed.

314 virtual bool updateNode(Node*) { return false; }

315

316 //----------------------------------------------------------------------

317 // Generic binary search tree operations

318 //

319

320 // Searches the tree for the given datum.

321 Node* treeSearch(const T& data) const

322 {

323 if (m_needsFullOrderingComparisons)

324 return treeSearchFullComparisons(m_root, data);

325

326 return treeSearchNormal(m_root, data);

327 }

328

329 // Searches the tree using the normal comparison operations,

330 // suitable for simple data types such as numbers.

331 Node* treeSearchNormal(Node* current, const T& data) const

332 {

333 while (current) {

334 if (current->data() == data)

335 return current;

336 if (data < current->data())

337 current = current->left();

338 else

339 current = current->right();

340 }

341 return 0;

342 }

343

344 // Searches the tree using multiple comparison operations, required

345 // for data types with more complex behavior such as intervals.

346 Node* treeSearchFullComparisons(Node* current, const T& data) const

347 {

348 if (!current)

349 return 0;

350 if (data < current->data())

351 return treeSearchFullComparisons(current->left(), data);

352 if (current->data() < data)

353 return treeSearchFullComparisons(current->right(), data);

354 if (data == current->data())

355 return current;

356

357 // We may need to traverse both the left and right subtrees.

358 Node* result = treeSearchFullComparisons(current->left(), data);

359 if (!result)

360 result = treeSearchFullComparisons(current->right(), data);

361 return result;

362 }

363

364 void treeInsert(Node* z)

365 {

366 Node* y = 0;

367 Node* x = m_root;

368 while (x) {

369 y = x;

370 if (z->data() < x->data())

371 x = x->left();

372 else

373 x = x->right();

374 }

375 z->setParent(y);

376 if (!y) {

377 m_root = z;

378 } else {

379 if (z->data() < y->data())

380 y->setLeft(z);

381 else

382 y->setRight(z);

383 }

384 }

385

386 // Finds the node following the given one in sequential ordering of

387 // their data, or null if none exists.

388 Node* treeSuccessor(Node* x)

389 {

390 if (x->right())

391 return treeMinimum(x->right());

392 Node* y = x->parent();

393 while (y && x == y->right()) {

394 x = y;

395 y = y->parent();

396 }

397 return y;

398 }

399

400 // Finds the minimum element in the sub-tree rooted at the given

401 // node.

402 Node* treeMinimum(Node* x)

403 {

404 while (x->left())

405 x = x->left();

406 return x;

407 }

408

409 // Helper for maintaining the augmented red-black tree.

410 void propagateUpdates(Node* start)

411 {

412 bool shouldContinue = true;

413 while (start && shouldContinue) {

414 shouldContinue = updateNode(start);

415 start = start->parent();

416 }

417 }

418

419 //----------------------------------------------------------------------

420 // Red-Black tree operations

421 //

422

423 // Left-rotates the subtree rooted at x.

424 // Returns the new root of the subtree (x's right child).

425 Node* leftRotate(Node* x)

426 {

427 // Set y.

428 Node* y = x->right();

429

430 // Turn y's left subtree into x's right subtree.

431 x->setRight(y->left());

432 if (y->left())

433 y->left()->setParent(x);

434

435 // Link x's parent to y.

436 y->setParent(x->parent());

437 if (!x->parent()) {

438 m_root = y;

439 } else {

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

441 x->parent()->setLeft(y);

442 else

443 x->parent()->setRight(y);

444 }

445

446 // Put x on y's left.

447 y->setLeft(x);

448 x->setParent(y);

449

450 // Update nodes lowest to highest.

451 updateNode(x);

452 updateNode(y);

453 return y;

454 }

455

456 // Right-rotates the subtree rooted at y.

457 // Returns the new root of the subtree (y's left child).

458 Node* rightRotate(Node* y)

459 {

460 // Set x.

461 Node* x = y->left();

462

463 // Turn x's right subtree into y's left subtree.

464 y->setLeft(x->right());

465 if (x->right())

466 x->right()->setParent(y);

467

468 // Link y's parent to x.

469 x->setParent(y->parent());

470 if (!y->parent()) {

471 m_root = x;

472 } else {

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

474 y->parent()->setLeft(x);

475 else

476 y->parent()->setRight(x);

477 }

478

479 // Put y on x's right.

480 x->setRight(y);

481 y->setParent(x);

482

483 // Update nodes lowest to highest.

484 updateNode(y);

485 updateNode(x);

486 return x;

487 }

488

489 // Inserts the given node into the tree.

490 void insertNode(Node* x)

491 {

492 treeInsert(x);

493 x->setColor(Red);

494 updateNode(x);

495

496 logIfVerbose(" PODRedBlackTree::InsertNode");

497

498 // The node from which to start propagating updates upwards.

499 Node* updateStart = x->parent();

500

501 while (x != m_root && x->parent()->color() == Red) {

502 if (x->parent() == x->parent()->parent()->left()) {

503 Node* y = x->parent()->parent()->right();

504 if (y && y->color() == Red) {

505 // Case 1

506 logIfVerbose(" Case 1/1");

507 x->parent()->setColor(Black);

508 y->setColor(Black);

509 x->parent()->parent()->setColor(Red);

510 updateNode(x->parent());

511 x = x->parent()->parent();

512 updateNode(x);

513 updateStart = x->parent();

514 } else {

515 if (x == x->parent()->right()) {

516 logIfVerbose(" Case 1/2");

517 // Case 2

518 x = x->parent();

519 leftRotate(x);

520 }

521 // Case 3

522 logIfVerbose(" Case 1/3");

523 x->parent()->setColor(Black);

524 x->parent()->parent()->setColor(Red);

525 Node* newSubTreeRoot = rightRotate(x->parent()->parent());

526 updateStart = newSubTreeRoot->parent();

527 }

528 } else {

529 // Same as "then" clause with "right" and "left" exchanged.

530 Node* y = x->parent()->parent()->left();

531 if (y && y->color() == Red) {

532 // Case 1

533 logIfVerbose(" Case 2/1");

534 x->parent()->setColor(Black);

535 y->setColor(Black);

536 x->parent()->parent()->setColor(Red);

537 updateNode(x->parent());

538 x = x->parent()->parent();

539 updateNode(x);

540 updateStart = x->parent();

541 } else {

542 if (x == x->parent()->left()) {

543 // Case 2

544 logIfVerbose(" Case 2/2");

545 x = x->parent();

546 rightRotate(x);

547 }

548 // Case 3

549 logIfVerbose(" Case 2/3");

550 x->parent()->setColor(Black);

551 x->parent()->parent()->setColor(Red);

552 Node* newSubTreeRoot = leftRotate(x->parent()->parent());

553 updateStart = newSubTreeRoot->parent();

554 }

555 }

556 }

557

558 propagateUpdates(updateStart);

559

560 m_root->setColor(Black);

561 }

562

563 // Restores the red-black property to the tree after splicing out

564 // a node. Note that x may be null, which is why xParent must be

565 // supplied.

566 void deleteFixup(Node* x, Node* xParent)

567 {

568 while (x != m_root && (!x \|\| x->color() == Black)) {

569 if (x == xParent->left()) {

570 // Note: the text points out that w can not be null.

571 // The reason is not obvious from simply looking at

572 // the code; it comes about from the properties of the

573 // red-black tree.

574 Node* w = xParent->right();

575 ASSERT(w); // x's sibling should not be null.

576 if (w->color() == Red) {

577 // Case 1

578 w->setColor(Black);

579 xParent->setColor(Red);

580 leftRotate(xParent);

581 w = xParent->right();

582 }

583 if ((!w->left() \|\| w->left()->color() == Black)

584 && (!w->right() \|\| w->right()->color() == Black)) {

585 // Case 2

586 w->setColor(Red);

587 x = xParent;

588 xParent = x->parent();

589 } else {

590 if (!w->right() \|\| w->right()->color() == Black) {

591 // Case 3

592 w->left()->setColor(Black);

593 w->setColor(Red);

594 rightRotate(w);

595 w = xParent->right();

596 }

597 // Case 4

598 w->setColor(xParent->color());

599 xParent->setColor(Black);

600 if (w->right())

601 w->right()->setColor(Black);

602 leftRotate(xParent);

603 x = m_root;

604 xParent = x->parent();

605 }

606 } else {

607 // Same as "then" clause with "right" and "left"

608 // exchanged.

609

610 // Note: the text points out that w can not be null.

611 // The reason is not obvious from simply looking at

612 // the code; it comes about from the properties of the

613 // red-black tree.

614 Node* w = xParent->left();

615 ASSERT(w); // x's sibling should not be null.

616 if (w->color() == Red) {

617 // Case 1

618 w->setColor(Black);

619 xParent->setColor(Red);

620 rightRotate(xParent);

621 w = xParent->left();

622 }

623 if ((!w->right() \|\| w->right()->color() == Black)

624 && (!w->left() \|\| w->left()->color() == Black)) {

625 // Case 2

626 w->setColor(Red);

627 x = xParent;

628 xParent = x->parent();

629 } else {

630 if (!w->left() \|\| w->left()->color() == Black) {

631 // Case 3

632 w->right()->setColor(Black);

633 w->setColor(Red);

634 leftRotate(w);

635 w = xParent->left();

636 }

637 // Case 4

638 w->setColor(xParent->color());

639 xParent->setColor(Black);

640 if (w->left())

641 w->left()->setColor(Black);

642 rightRotate(xParent);

643 x = m_root;

644 xParent = x->parent();

645 }

646 }

647 }

648 if (x)

649 x->setColor(Black);

650 }

651

652 // Deletes the given node from the tree. Note that this

653 // particular node may not actually be removed from the tree;

654 // instead, another node might be removed and its contents

655 // copied into z.

656 void deleteNode(Node* z)

657 {

658 // Y is the node to be unlinked from the tree.

659 Node* y;

660 if (!z->left() \|\| !z->right())

661 y = z;

662 else

663 y = treeSuccessor(z);

664

665 // Y is guaranteed to be non-null at this point.

666 Node* x;

667 if (y->left())

668 x = y->left();

669 else

670 x = y->right();

671

672 // X is the child of y which might potentially replace y in

673 // the tree. X might be null at this point.

674 Node* xParent;

675 if (x) {

676 x->setParent(y->parent());

677 xParent = x->parent();

678 } else {

679 xParent = y->parent();

680 }

681 if (!y->parent()) {

682 m_root = x;

683 } else {

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

685 y->parent()->setLeft(x);

686 else

687 y->parent()->setRight(x);

688 }

689 if (y != z) {

690 z->copyFrom(y);

691 // This node has changed location in the tree and must be updated.

692 updateNode(z);

693 // The parent and its parents may now be out of date.

694 propagateUpdates(z->parent());

695 }

696

697 // If we haven't already updated starting from xParent, do so now.

698 if (xParent && xParent != y && xParent != z)

699 propagateUpdates(xParent);

700 if (y->color() == Black)

701 deleteFixup(x, xParent);

702

703 m_arena->freeObject(y);

704 }

705

706 // Visits the subtree rooted at the given node in order.

707 void visitInorderImpl(Node* node, Visitor* visitor) const

708 {

709 if (node->left())

710 visitInorderImpl(node->left(), visitor);

711 visitor->visit(node->data());

712 if (node->right())

713 visitInorderImpl(node->right(), visitor);

714 }

715

716 void markFree(Node *node)

717 {

718 if (!node)

719 return;

720

721 if (node->left())

722 markFree(node->left());

723 if (node->right())

724 markFree(node->right());

725 m_arena->freeObject(node);

726 }

727

728 //----------------------------------------------------------------------

729 // Helper class for size()

730

731 // A Visitor which simply counts the number of visited elements.

732 class Counter : public Visitor {

733 WTF_MAKE_NONCOPYABLE(Counter);

734 public:

735 Counter()

736 : m_count(0) { }

737

738 virtual void visit(const T&) { ++m_count; }

739 int count() const { return m_count; }

740

741 private:

742 int m_count;

743 };

744

745 //----------------------------------------------------------------------

746 // Verification and debugging routines

747 //

748

749 // Returns in the "blackCount" parameter the number of black

750 // children along all paths to all leaves of the given node.

751 bool checkInvariantsFromNode(Node* node, int* blackCount) const

752 {

753 // Base case is a leaf node.

754 if (!node) {

755 *blackCount = 1;

756 return true;

757 }

758

759 // Each node is either red or black.

760 if (!(node->color() == Red \|\| node->color() == Black))

761 return false;

762

763 // Every leaf (or null) is black.

764

765 if (node->color() == Red) {

766 // Both of its children are black.

767 if (!((!node->left() \|\| node->left()->color() == Black)))

768 return false;

769 if (!((!node->right() \|\| node->right()->color() == Black)))

770 return false;

771 }

772

773 // Every simple path to a leaf node contains the same number of

774 // black nodes.

775 int leftCount = 0, rightCount = 0;

776 bool leftValid = checkInvariantsFromNode(node->left(), &leftCount);

777 bool rightValid = checkInvariantsFromNode(node->right(), &rightCount);

778 if (!leftValid \|\| !rightValid)

779 return false;

780 *blackCount = leftCount + (node->color() == Black ? 1 : 0);

781 return leftCount == rightCount;

782 }

783

784 #ifdef NDEBUG

785 void logIfVerbose(const char*) const { }

786 #else

787 void logIfVerbose(const char* output) const

788 {

789 if (m_verboseDebugging)

790 WTF_LOG_ERROR("%s", output);

791 }

792 #endif

793

794 #ifndef NDEBUG

795 // Dumps the subtree rooted at the given node.

796 void dumpFromNode(Node* node, int indentation) const

797 {

798 StringBuilder builder;

799 for (int i = 0; i < indentation; i++)

800 builder.append(' ');

801 builder.append('-');

802 if (node) {

803 builder.append(' ');

804 builder.append(ValueToString<T>::string(node->data()));

805 builder.append((node->color() == Black) ? " (black)" : " (red)");

806 }

807 WTF_LOG_ERROR("%s", builder.toString().ascii().data());

808 if (node) {

809 dumpFromNode(node->left(), indentation + 2);

810 dumpFromNode(node->right(), indentation + 2);

811 }

812 }

813 #endif

814

815 //----------------------------------------------------------------------

816 // Data members

817

818 RefPtr<PODFreeListArena<Node> > m_arena;

819 Node* m_root;

820 bool m_needsFullOrderingComparisons;

821 #ifndef NDEBUG

822 bool m_verboseDebugging;

823 #endif

824 };

825

826 } // namespace blink

827

828 #endif // PODRedBlackTree_h

OLD	NEW

« no previous file with comments | « sky/engine/platform/PODIntervalTreeTest.cpp ('k') | sky/engine/platform/PODRedBlackTreeTest.cpp » ('j') | no next file with comments »