Requesting C++ readability review for these classes and unit tests.

The arena allocator is designed for optimized allocation and
deallocation of small temporary objects, and is used by the
augmentable red-black tree. In a subsequent checkin, the red-black
tree will be augmented into an interval tree, which is a key data
structure for efficient implementation of one of the algorithms in the
forthcoming code in this directory.

Review URL: http://codereview.chromium.org/596093

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@39414 0039d316-1c4b-4281-b951-d872f2087c98

6 files changed, 102 insertions, 107 deletions

diff --git a/o3d/core/cross/gpu2d/arena.h b/o3d/core/cross/gpu2d/arena.h
index 67059d5..486eedf 100644
--- a/o3d/core/cross/gpu2d/arena.h
+++ b/o3d/core/cross/gpu2d/arena.h
@@ -29,11 +29,17 @@
  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */
 
+// An arena allocates large chunks of memory internally and allocates
+// individual objects out of those chunks. Objects are not freed
+// individually; their storage is reclaimed all at once when the arena
+// is destroyed. The arena calls the constructors of the objects
+// allocated within, but NOT their destructors.
+
 #ifndef O3D_CORE_CROSS_GPU2D_ARENA_H_
 #define O3D_CORE_CROSS_GPU2D_ARENA_H_
 
-#include <assert.h>
 #include <stddef.h>
+
 #include <algorithm>
 #include <list>
 
@@ -42,11 +48,6 @@
 namespace o3d {
 namespace gpu2d {
 
-// An arena allocates large chunks of memory internally and allocates
-// individual objects out of those chunks. Objects are not freed
-// individually; their storage is reclaimed all at once when the arena
-// is destroyed. The arena calls the constructors of the objects
-// allocated within, but NOT their destructors.
 class Arena {
  public:
   // The arena is configured with an allocator, which is responsible
@@ -147,7 +148,7 @@ class Arena {
 
   // Rounds up the given allocation size to the specified alignment.
   size_t RoundUp(size_t size, size_t alignment) {
-    assert(alignment % 2 == 0);
+    DCHECK(alignment % 2 == 0);
     return (size + alignment - 1) & ~(alignment - 1);
   }
 
diff --git a/o3d/core/cross/gpu2d/arena_test.cc b/o3d/core/cross/gpu2d/arena_test.cc
index 1a217f9..0c34bbf 100644
--- a/o3d/core/cross/gpu2d/arena_test.cc
+++ b/o3d/core/cross/gpu2d/arena_test.cc
@@ -34,8 +34,9 @@
 #include <algorithm>
 #include <vector>
 
-#include "gtest/gtest.h"
+#include "base/scoped_ptr.h"
 #include "core/cross/gpu2d/arena.h"
+#include "gtest/gtest.h"
 
 namespace o3d {
 namespace gpu2d {
@@ -112,15 +113,16 @@ TEST_F(ArenaTest, CanAllocateFromMoreThanOneRegion) {
 
 // Make sure the arena frees all allocated regions during destruction.
 TEST_F(ArenaTest, FreesAllAllocatedRegions) {
-  TrackedMallocAllocator* base_allocator = new TrackedMallocAllocator();
-  Arena* arena = new Arena(base_allocator);
-  for (int i = 0; i < 3; i++) {
-    arena->Alloc<TestClass1>();
+  scoped_ptr<TrackedMallocAllocator> base_allocator(
+      new TrackedMallocAllocator());
+  {
+    scoped_ptr<Arena> arena(new Arena(base_allocator.get()));
+    for (int i = 0; i < 3; i++) {
+      arena->Alloc<TestClass1>();
+    }
+    EXPECT_GT(base_allocator->NumRegions(), 0);
   }
-  EXPECT_GT(base_allocator->NumRegions(), 0);
-  delete arena;
   EXPECT_TRUE(base_allocator->IsEmpty());
-  delete base_allocator;
 }
 
 // Make sure the arena runs constructors of the objects allocated within.
diff --git a/o3d/core/cross/gpu2d/red_black_tree.h b/o3d/core/cross/gpu2d/red_black_tree.h
index 7dd7446..e9ba092 100644
--- a/o3d/core/cross/gpu2d/red_black_tree.h
+++ b/o3d/core/cross/gpu2d/red_black_tree.h
@@ -29,21 +29,6 @@
  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */
 
-
-#ifndef O3D_CORE_CROSS_GPU2D_RED_BLACK_TREE_H_
-#define O3D_CORE_CROSS_GPU2D_RED_BLACK_TREE_H_
-
-#include <string>
-
-#include "base/logging.h"
-#include "core/cross/gpu2d/arena.h"
-
-namespace o3d {
-namespace gpu2d {
-
-// Uncomment this for verbose logging output.
-// #define O3D_CORE_CROSS_GPU2D_RED_BLACK_TREE_VERBOSE
-
 // A red-black tree, which is a form of a balanced binary tree. It
 // supports efficient insertion, deletion and queries of comparable
 // elements. The same element may be inserted multiple times. The
@@ -79,6 +64,18 @@ namespace gpu2d {
 //
 // The design of this red-black tree comes from Cormen, Leiserson,
 // and Rivest, _Introduction to Algorithms_, MIT Press, 1990.
+
+#ifndef O3D_CORE_CROSS_GPU2D_RED_BLACK_TREE_H_
+#define O3D_CORE_CROSS_GPU2D_RED_BLACK_TREE_H_
+
+#include <string>
+
+#include "base/logging.h"
+#include "core/cross/gpu2d/arena.h"
+
+namespace o3d {
+namespace gpu2d {
+
 template<class T>
 class RedBlackTree {
  public:
@@ -95,7 +92,8 @@ class RedBlackTree {
       : arena_(new Arena()),
         should_delete_arena_(true),
         root_(NULL),
-        needs_full_ordering_comparisons_(false) {
+        needs_full_ordering_comparisons_(false),
+        verbose_debugging_(false) {
   }
 
   // Constructs a new red-black tree, allocating temporary objects
@@ -105,7 +103,8 @@ class RedBlackTree {
       : arena_(arena),
         should_delete_arena_(false),
         root_(NULL),
-        needs_full_ordering_comparisons_(false) {
+        needs_full_ordering_comparisons_(false),
+        verbose_debugging_(false) {
   }
 
   // Destructor deletes the internal Arena if it was not explicitly
@@ -155,7 +154,7 @@ class RedBlackTree {
 
   // Returns true if the tree's invariants are preserved.
   bool Verify() {
-    int black_count = 0;
+    int black_count;
     return VerifyFromNode(root_, &black_count);
   }
 
@@ -172,6 +171,13 @@ class RedBlackTree {
     needs_full_ordering_comparisons_ = needs_full_ordering_comparisons;
   }
 
+  // Turns on or off verbose debugging of the tree, causing many
+  // messages to be logged during insertion and other operations in
+  // debug mode.
+  void set_verbose_debugging(bool on_or_off) {
+    verbose_debugging_ = on_or_off;
+  }
+
  protected:
   enum Color {
     kRed = 1,
@@ -443,9 +449,7 @@ class RedBlackTree {
     x->set_color(kRed);
     UpdateNode(x);
 
-#ifdef O3D_CORE_CROSS_GPU2D_RED_BLACK_TREE_VERBOSE
-    DLOG(INFO) << "  RedBlackTree::InsertNode";
-#endif
+    DLOG_IF(INFO, verbose_debugging_) << "  RedBlackTree::InsertNode";
 
     // The node from which to start propagating updates upwards.
     Node* update_start = x->parent();
@@ -455,9 +459,7 @@ class RedBlackTree {
         Node* y = x->parent()->parent()->right();
         if (y != NULL && y->color() == kRed) {
           // Case 1
-#ifdef O3D_CORE_CROSS_GPU2D_RED_BLACK_TREE_VERBOSE
-          DLOG(INFO) << "  Case 1/1";
-#endif
+          DLOG_IF(INFO, verbose_debugging_) << "  Case 1/1";
           x->parent()->set_color(kBlack);
           y->set_color(kBlack);
           x->parent()->parent()->set_color(kRed);
@@ -467,17 +469,13 @@ class RedBlackTree {
           update_start = x->parent();
         } else {
           if (x == x->parent()->right()) {
-#ifdef O3D_CORE_CROSS_GPU2D_RED_BLACK_TREE_VERBOSE
-            DLOG(INFO) << "  Case 1/2";
-#endif
+            DLOG_IF(INFO, verbose_debugging_) << "  Case 1/2";
             // Case 2
             x = x->parent();
             LeftRotate(x);
           }
           // Case 3
-#ifdef O3D_CORE_CROSS_GPU2D_RED_BLACK_TREE_VERBOSE
-          DLOG(INFO) << "  Case 1/3";
-#endif
+          DLOG_IF(INFO, verbose_debugging_) << "  Case 1/3";
           x->parent()->set_color(kBlack);
           x->parent()->parent()->set_color(kRed);
           RightRotate(x->parent()->parent());
@@ -488,9 +486,7 @@ class RedBlackTree {
         Node* y = x->parent()->parent()->left();
         if (y != NULL && y->color() == kRed) {
           // Case 1
-#ifdef O3D_CORE_CROSS_GPU2D_RED_BLACK_TREE_VERBOSE
-          DLOG(INFO) << "  Case 2/1";
-#endif
+          DLOG_IF(INFO, verbose_debugging_) << "  Case 2/1";
           x->parent()->set_color(kBlack);
           y->set_color(kBlack);
           x->parent()->parent()->set_color(kRed);
@@ -501,16 +497,12 @@ class RedBlackTree {
         } else {
           if (x == x->parent()->left()) {
             // Case 2
-#ifdef O3D_CORE_CROSS_GPU2D_RED_BLACK_TREE_VERBOSE
-            DLOG(INFO) << "  Case 2/2";
-#endif
+            DLOG_IF(INFO, verbose_debugging_) << "  Case 2/2";
             x = x->parent();
             RightRotate(x);
           }
           // Case 3
-#ifdef O3D_CORE_CROSS_GPU2D_RED_BLACK_TREE_VERBOSE
-          DLOG(INFO) << "  Case 2/3";
-#endif
+          DLOG_IF(INFO, verbose_debugging_) << "  Case 2/3";
           x->parent()->set_color(kBlack);
           x->parent()->parent()->set_color(kRed);
           LeftRotate(x->parent()->parent());
@@ -759,6 +751,7 @@ class RedBlackTree {
   bool should_delete_arena_;
   Node* root_;
   bool needs_full_ordering_comparisons_;
+  bool verbose_debugging_;
 
   DISALLOW_COPY_AND_ASSIGN(RedBlackTree);
 };
diff --git a/o3d/core/cross/gpu2d/red_black_tree_test.cc b/o3d/core/cross/gpu2d/red_black_tree_test.cc
index 16ceb27..cada4ef 100644
--- a/o3d/core/cross/gpu2d/red_black_tree_test.cc
+++ b/o3d/core/cross/gpu2d/red_black_tree_test.cc
@@ -33,126 +33,123 @@
 
 #include <vector>
 
-#include "gtest/gtest.h"
 #include "core/cross/gpu2d/red_black_tree.h"
 #include "core/cross/gpu2d/tree_test_helpers.h"
+#include "gtest/gtest.h"
 
 namespace o3d {
 namespace gpu2d {
 
-class RedBlackTreeTest : public testing::Test {
-};
-
-TEST_F(RedBlackTreeTest, TestSingleElementInsertion) {
+TEST(RedBlackTreeTest, TestSingleElementInsertion) {
   RedBlackTree<int> tree;
   tree.Insert(5);
-  EXPECT_TRUE(tree.Verify());
+  ASSERT_TRUE(tree.Verify());
   EXPECT_TRUE(tree.Contains(5));
 }
 
-TEST_F(RedBlackTreeTest, TestMultipleElementInsertion) {
+TEST(RedBlackTreeTest, TestMultipleElementInsertion) {
   RedBlackTree<int> tree;
   tree.Insert(4);
-  EXPECT_TRUE(tree.Verify());
+  ASSERT_TRUE(tree.Verify());
   EXPECT_TRUE(tree.Contains(4));
   tree.Insert(3);
-  EXPECT_TRUE(tree.Verify());
+  ASSERT_TRUE(tree.Verify());
   EXPECT_TRUE(tree.Contains(3));
   tree.Insert(5);
-  EXPECT_TRUE(tree.Verify());
+  ASSERT_TRUE(tree.Verify());
   EXPECT_TRUE(tree.Contains(5));
   EXPECT_TRUE(tree.Contains(4));
   EXPECT_TRUE(tree.Contains(3));
 }
 
-TEST_F(RedBlackTreeTest, TestDuplicateElementInsertion) {
+TEST(RedBlackTreeTest, TestDuplicateElementInsertion) {
   RedBlackTree<int> tree;
   tree.Insert(3);
-  EXPECT_TRUE(tree.Verify());
+  ASSERT_TRUE(tree.Verify());
   tree.Insert(3);
-  EXPECT_TRUE(tree.Verify());
+  ASSERT_TRUE(tree.Verify());
   tree.Insert(3);
-  EXPECT_TRUE(tree.Verify());
+  ASSERT_TRUE(tree.Verify());
   EXPECT_EQ(3, tree.NumElements());
   EXPECT_TRUE(tree.Contains(3));
 }
 
-TEST_F(RedBlackTreeTest, TestSingleElementInsertionAndDeletion) {
+TEST(RedBlackTreeTest, TestSingleElementInsertionAndDeletion) {
   RedBlackTree<int> tree;
   tree.Insert(5);
-  EXPECT_TRUE(tree.Verify());
+  ASSERT_TRUE(tree.Verify());
   EXPECT_TRUE(tree.Contains(5));
   tree.Delete(5);
-  EXPECT_TRUE(tree.Verify());
+  ASSERT_TRUE(tree.Verify());
   EXPECT_FALSE(tree.Contains(5));
 }
 
-TEST_F(RedBlackTreeTest, TestMultipleElementInsertionAndDeletion) {
+TEST(RedBlackTreeTest, TestMultipleElementInsertionAndDeletion) {
   RedBlackTree<int> tree;
   tree.Insert(4);
-  EXPECT_TRUE(tree.Verify());
+  ASSERT_TRUE(tree.Verify());
   EXPECT_TRUE(tree.Contains(4));
   tree.Insert(3);
-  EXPECT_TRUE(tree.Verify());
+  ASSERT_TRUE(tree.Verify());
   EXPECT_TRUE(tree.Contains(3));
   tree.Insert(5);
-  EXPECT_TRUE(tree.Verify());
+  ASSERT_TRUE(tree.Verify());
   EXPECT_TRUE(tree.Contains(5));
   EXPECT_TRUE(tree.Contains(4));
   EXPECT_TRUE(tree.Contains(3));
   tree.Delete(4);
-  EXPECT_TRUE(tree.Verify());
+  ASSERT_TRUE(tree.Verify());
   EXPECT_TRUE(tree.Contains(3));
   EXPECT_FALSE(tree.Contains(4));
   EXPECT_TRUE(tree.Contains(5));
   tree.Delete(5);
-  EXPECT_TRUE(tree.Verify());
+  ASSERT_TRUE(tree.Verify());
   EXPECT_TRUE(tree.Contains(3));
   EXPECT_FALSE(tree.Contains(4));
   EXPECT_FALSE(tree.Contains(5));
   EXPECT_EQ(1, tree.NumElements());
 }
 
-TEST_F(RedBlackTreeTest, TestDuplicateElementInsertionAndDeletion) {
+TEST(RedBlackTreeTest, TestDuplicateElementInsertionAndDeletion) {
   RedBlackTree<int> tree;
   tree.Insert(3);
-  EXPECT_TRUE(tree.Verify());
+  ASSERT_TRUE(tree.Verify());
   tree.Insert(3);
-  EXPECT_TRUE(tree.Verify());
+  ASSERT_TRUE(tree.Verify());
   tree.Insert(3);
-  EXPECT_TRUE(tree.Verify());
+  ASSERT_TRUE(tree.Verify());
   EXPECT_EQ(3, tree.NumElements());
   EXPECT_TRUE(tree.Contains(3));
   tree.Delete(3);
-  EXPECT_TRUE(tree.Verify());
+  ASSERT_TRUE(tree.Verify());
   tree.Delete(3);
-  EXPECT_TRUE(tree.Verify());
+  ASSERT_TRUE(tree.Verify());
   EXPECT_EQ(1, tree.NumElements());
   EXPECT_TRUE(tree.Contains(3));
   tree.Delete(3);
-  EXPECT_TRUE(tree.Verify());
+  ASSERT_TRUE(tree.Verify());
   EXPECT_EQ(0, tree.NumElements());
   EXPECT_FALSE(tree.Contains(3));
 }
 
-TEST_F(RedBlackTreeTest, FailingInsertionRegressionTest1) {
+TEST(RedBlackTreeTest, FailingInsertionRegressionTest1) {
   RedBlackTree<int> tree;
   tree.Insert(5113);
-  EXPECT_TRUE(tree.Verify());
+  ASSERT_TRUE(tree.Verify());
   tree.Insert(4517);
-  EXPECT_TRUE(tree.Verify());
+  ASSERT_TRUE(tree.Verify());
   tree.Insert(3373);
-  EXPECT_TRUE(tree.Verify());
+  ASSERT_TRUE(tree.Verify());
   tree.Insert(9307);
-  EXPECT_TRUE(tree.Verify());
+  ASSERT_TRUE(tree.Verify());
   tree.Insert(7077);
-  EXPECT_TRUE(tree.Verify());
+  ASSERT_TRUE(tree.Verify());
 }
 
 namespace {
-void InsertionAndDeletionTest(int32 seed, int tree_size) {
+void InsertionAndDeletionTest(const int32 seed, const int tree_size) {
   InitRandom(seed);
-  int max_val = tree_size;
+  const int max_val = tree_size;
   // Build the tree.
   RedBlackTree<int> tree;
   std::vector<int> values;
@@ -179,11 +176,11 @@ void InsertionAndDeletionTest(int32 seed, int tree_size) {
 }
 }  // anonymous namespace
 
-TEST_F(RedBlackTreeTest, RandomDeletionAndInsertionRegressionTest1) {
+TEST(RedBlackTreeTest, RandomDeletionAndInsertionRegressionTest1) {
   InsertionAndDeletionTest(12311, 100);
 }
 
-TEST_F(RedBlackTreeTest, TestRandomDeletionAndInsertion) {
+TEST(RedBlackTreeTest, TestRandomDeletionAndInsertion) {
   InsertionAndDeletionTest(GenerateSeed(), 100);
 }
 
diff --git a/o3d/core/cross/gpu2d/tree_test_helpers.cc b/o3d/core/cross/gpu2d/tree_test_helpers.cc
index d78fb74..337d7d1 100644
--- a/o3d/core/cross/gpu2d/tree_test_helpers.cc
+++ b/o3d/core/cross/gpu2d/tree_test_helpers.cc
@@ -29,9 +29,11 @@
  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */
 
+#include "core/cross/gpu2d/tree_test_helpers.h"
+
 #include <cstdlib>
+
 #include "base/rand_util.h"
-#include "core/cross/gpu2d/tree_test_helpers.h"
 
 namespace o3d {
 namespace gpu2d {
@@ -40,20 +42,20 @@ int32 GenerateSeed() {
   // A seed of 1 has the special behavior of resetting the random
   // number generator. Assume that if we call this routine that we
   // don't want this behavior.
-  int seed = 0;
+  int seed;
   do {
     seed = base::RandInt(0, 2 << 15);
   } while (seed <= 1);
   return seed;
 }
 
-void InitRandom(int32 seed) {
+void InitRandom(const int32 seed) {
   srand(seed);
 }
 
-int32 NextRandom(int32 max) {
+int32 NextRandom(const int32 max_val) {
   // rand_r is not available on Windows
-  return rand() % max;  // NOLINT
+  return rand() % max_val;  // NOLINT
 }
 
 }  // namespace gpu2d
diff --git a/o3d/core/cross/gpu2d/tree_test_helpers.h b/o3d/core/cross/gpu2d/tree_test_helpers.h
index 1817f9a..39c74b7 100644
--- a/o3d/core/cross/gpu2d/tree_test_helpers.h
+++ b/o3d/core/cross/gpu2d/tree_test_helpers.h
@@ -29,6 +29,11 @@
  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */
 
+// Simple pseudorandom number generator helper functions, used by the
+// red-black and interval tree tests.
+//
+// These are **not** thread safe!
+
 #ifndef O3D_CORE_CROSS_GPU2D_TREE_TEST_HELPERS_H_
 #define O3D_CORE_CROSS_GPU2D_TREE_TEST_HELPERS_H_
 
@@ -37,21 +42,16 @@
 namespace o3d {
 namespace gpu2d {
 
-// Simple pseudorandom number generator helper functions, used by the
-// red-black and interval tree tests.
-//
-// These are **not** thread safe!
-
 // Generates a seed value to be passed to InitRandom().
 int32 GenerateSeed();
 
 // Initializes the pseudo-random number generator with a specific seed.
-void InitRandom(int32 seed);
+void InitRandom(const int32 seed);
 
 // Produces the next pseudo-random number in the sequence, in the
-// range from [0..max). Negative numbers are not allowed and will
+// range from [0..max_val). Negative numbers are not allowed and will
 // produce undefined results.
-int32 NextRandom(int32 max);
+int32 NextRandom(const int32 max_val);
 
 }  // namespace gpu2d
 }  // namespace o3d