Fix alignment issue of ContiguousContainer

cc/base/contiguous_container_unittest.cc

Index: cc/base/contiguous_container_unittest.cc
diff --git a/cc/base/contiguous_container_unittest.cc b/cc/base/contiguous_container_unittest.cc
index dde2e62e56c5ab66d10a2317e650a17eb0f399f3..d2f68478cf2cac71540628e679c58bc582897b5b 100644
--- a/cc/base/contiguous_container_unittest.cc
+++ b/cc/base/contiguous_container_unittest.cc
@@ -26,14 +26,13 @@ struct Point3D : public Point2D {
 // Maximum size of a subclass of Point2D.
 static const size_t kMaxPointSize = sizeof(Point3D);
 
-// Alignment for Point2D and its subclasses.
-static const size_t kPointAlignment = sizeof(int);
-
 // How many elements to use for tests with "plenty" of elements.
 static const size_t kNumElements = 150;
 
+}  // namespace
+
 TEST(ContiguousContainerTest, SimpleStructs) {
-  ContiguousContainer<Point2D, kPointAlignment> list(kMaxPointSize);
+  ContiguousContainer<Point2D> list(kMaxPointSize);
   list.AllocateAndConstruct<Point2D>(1, 2);
   list.AllocateAndConstruct<Point3D>(3, 4, 5);
   list.AllocateAndConstruct<Point2D>(6, 7);
@@ -49,7 +48,7 @@ TEST(ContiguousContainerTest, SimpleStructs) {
 }
 
 TEST(ContiguousContainerTest, AllocateLots) {
-  ContiguousContainer<Point2D, kPointAlignment> list(kMaxPointSize);
+  ContiguousContainer<Point2D> list(kMaxPointSize);
   for (int i = 0; i < (int)kNumElements; i++) {
     list.AllocateAndConstruct<Point2D>(i, i);
     list.AllocateAndConstruct<Point2D>(i, i);
@@ -167,7 +166,7 @@ TEST(ContiguousContainerTest, DestructorCalledWithMultipleRemoveLastCalls) {
 }
 
 TEST(ContiguousContainerTest, InsertionAndIndexedAccess) {
-  ContiguousContainer<Point2D, kPointAlignment> list(kMaxPointSize);
+  ContiguousContainer<Point2D> list(kMaxPointSize);
 
   auto& point1 = list.AllocateAndConstruct<Point2D>();
   auto& point2 = list.AllocateAndConstruct<Point2D>();
@@ -182,7 +181,7 @@ TEST(ContiguousContainerTest, InsertionAndIndexedAccess) {
 }
 
 TEST(ContiguousContainerTest, InsertionAndClear) {
-  ContiguousContainer<Point2D, kPointAlignment> list(kMaxPointSize);
+  ContiguousContainer<Point2D> list(kMaxPointSize);
   EXPECT_TRUE(list.empty());
   EXPECT_EQ(0u, list.size());
 
@@ -200,7 +199,7 @@ TEST(ContiguousContainerTest, InsertionAndClear) {
 }
 
 TEST(ContiguousContainerTest, ElementAddressesAreStable) {
-  ContiguousContainer<Point2D, kPointAlignment> list(kMaxPointSize);
+  ContiguousContainer<Point2D> list(kMaxPointSize);
   std::vector<Point2D*> pointers;
   for (int i = 0; i < (int)kNumElements; i++)
     pointers.push_back(&list.AllocateAndConstruct<Point2D>());
@@ -214,7 +213,7 @@ TEST(ContiguousContainerTest, ElementAddressesAreStable) {
 }
 
 TEST(ContiguousContainerTest, ForwardIteration) {
-  ContiguousContainer<Point2D, kPointAlignment> list(kMaxPointSize);
+  ContiguousContainer<Point2D> list(kMaxPointSize);
   for (int i = 0; i < (int)kNumElements; i++)
     list.AllocateAndConstruct<Point2D>(i, i);
   unsigned count = 0;
@@ -229,7 +228,7 @@ TEST(ContiguousContainerTest, ForwardIteration) {
 }
 
 TEST(ContiguousContainerTest, ConstForwardIteration) {
-  ContiguousContainer<Point2D, kPointAlignment> list(kMaxPointSize);
+  ContiguousContainer<Point2D> list(kMaxPointSize);
   for (int i = 0; i < (int)kNumElements; i++)
     list.AllocateAndConstruct<Point2D>(i, i);
 
@@ -247,7 +246,7 @@ TEST(ContiguousContainerTest, ConstForwardIteration) {
 }
 
 TEST(ContiguousContainerTest, ReverseIteration) {
-  ContiguousContainer<Point2D, kPointAlignment> list(kMaxPointSize);
+  ContiguousContainer<Point2D> list(kMaxPointSize);
   for (int i = 0; i < (int)kNumElements; i++)
     list.AllocateAndConstruct<Point2D>(i, i);
 
@@ -328,12 +327,12 @@ TEST(ContiguousContainerTest, IterationAfterRemoveLast) {
 }
 
 TEST(ContiguousContainerTest, AppendByMovingSameList) {
-  ContiguousContainer<Point2D, kPointAlignment> list(kMaxPointSize);
+  ContiguousContainer<Point2D> list(kMaxPointSize);
   list.AllocateAndConstruct<Point3D>(1, 2, 3);
 
   // Moves the Point3D to the end, and default-constructs a Point2D in its
   // place.
-  list.AppendByMoving(&list.first(), sizeof(Point3D));
+  list.AppendByMoving(&list.first(), sizeof(Point3D), Log2Alignment<Point3D>());
   EXPECT_EQ(1, list.last().x);
   EXPECT_EQ(2, list.last().y);
   EXPECT_EQ(3, static_cast<const Point3D&>(list.last()).z);
@@ -342,7 +341,7 @@ TEST(ContiguousContainerTest, AppendByMovingSameList) {
   // Moves that Point2D to the end, and default-constructs another in its
   // place.
   list.first().x = 4;
-  list.AppendByMoving(&list.first(), sizeof(Point2D));
+  list.AppendByMoving(&list.first(), sizeof(Point2D), Log2Alignment<Point2D>());
   EXPECT_EQ(4, list.last().x);
   EXPECT_EQ(3u, list.size());
 }
@@ -368,7 +367,8 @@ TEST(ContiguousContainerTest, AppendByMovingDoesNotDestruct) {
   {
     // Make sure destructor isn't called during AppendByMoving.
     ContiguousContainer<DestructionNotifier> list2(sizeof(DestructionNotifier));
-    list2.AppendByMoving(&list1.last(), sizeof(DestructionNotifier));
+    list2.AppendByMoving(&list1.last(), sizeof(DestructionNotifier),
+                         Log2Alignment<DestructionNotifier>());
     EXPECT_FALSE(destroyed);
   }
   // But it should be destroyed when list2 is.
@@ -376,27 +376,30 @@ TEST(ContiguousContainerTest, AppendByMovingDoesNotDestruct) {
 }
 
 TEST(ContiguousContainerTest, AppendByMovingReturnsMovedPointer) {
-  ContiguousContainer<Point2D, kPointAlignment> list1(kMaxPointSize);
-  ContiguousContainer<Point2D, kPointAlignment> list2(kMaxPointSize);
+  ContiguousContainer<Point2D> list1(kMaxPointSize);
+  ContiguousContainer<Point2D> list2(kMaxPointSize);
 
   Point2D& point = list1.AllocateAndConstruct<Point2D>();
-  Point2D& moved_point1 = list2.AppendByMoving(&point, sizeof(Point2D));
+  Point2D& moved_point1 =
+      list2.AppendByMoving(&point, sizeof(Point2D), Log2Alignment<Point2D>());
   EXPECT_EQ(&moved_point1, &list2.last());
 
-  Point2D& moved_point2 = list1.AppendByMoving(&moved_point1, sizeof(Point2D));
+  Point2D& moved_point2 = list1.AppendByMoving(&moved_point1, sizeof(Point2D),
+                                               Log2Alignment<Point2D>());
   EXPECT_EQ(&moved_point2, &list1.last());
   EXPECT_NE(&moved_point1, &moved_point2);
 }
 
 TEST(ContiguousContainerTest, AppendByMovingReplacesSourceWithNewElement) {
-  ContiguousContainer<Point2D, kPointAlignment> list1(kMaxPointSize);
-  ContiguousContainer<Point2D, kPointAlignment> list2(kMaxPointSize);
+  ContiguousContainer<Point2D> list1(kMaxPointSize);
+  ContiguousContainer<Point2D> list2(kMaxPointSize);
 
   list1.AllocateAndConstruct<Point2D>(1, 2);
   EXPECT_EQ(1, list1.first().x);
   EXPECT_EQ(2, list1.first().y);
 
-  list2.AppendByMoving(&list1.first(), sizeof(Point2D));
+  list2.AppendByMoving(&list1.first(), sizeof(Point2D),
+                       Log2Alignment<Point2D>());
   EXPECT_EQ(0, list1.first().x);
   EXPECT_EQ(0, list1.first().y);
   EXPECT_EQ(1, list2.first().x);
@@ -407,7 +410,7 @@ TEST(ContiguousContainerTest, AppendByMovingReplacesSourceWithNewElement) {
 }
 
 TEST(ContiguousContainerTest, AppendByMovingElementsOfDifferentSizes) {
-  ContiguousContainer<Point2D, kPointAlignment> list(kMaxPointSize);
+  ContiguousContainer<Point2D> list(kMaxPointSize);
   list.AllocateAndConstruct<Point3D>(1, 2, 3);
   list.AllocateAndConstruct<Point2D>(4, 5);
 
@@ -419,14 +422,14 @@ TEST(ContiguousContainerTest, AppendByMovingElementsOfDifferentSizes) {
 
   // Test that moving the first element actually moves the entire object, not
   // just the base element.
-  list.AppendByMoving(&list[0], sizeof(Point3D));
+  list.AppendByMoving(&list[0], sizeof(Point3D), Log2Alignment<Point3D>());
   EXPECT_EQ(1, list[2].x);
   EXPECT_EQ(2, list[2].y);
   EXPECT_EQ(3, static_cast<const Point3D&>(list[2]).z);
   EXPECT_EQ(4, list[1].x);
   EXPECT_EQ(5, list[1].y);
 
-  list.AppendByMoving(&list[1], sizeof(Point2D));
+  list.AppendByMoving(&list[1], sizeof(Point2D), Log2Alignment<Point2D>());
   EXPECT_EQ(1, list[2].x);
   EXPECT_EQ(2, list[2].y);
   EXPECT_EQ(3, static_cast<const Point3D&>(list[2]).z);
@@ -435,9 +438,9 @@ TEST(ContiguousContainerTest, AppendByMovingElementsOfDifferentSizes) {
 }
 
 TEST(ContiguousContainerTest, Swap) {
-  ContiguousContainer<Point2D, kPointAlignment> list1(kMaxPointSize);
+  ContiguousContainer<Point2D> list1(kMaxPointSize);
   list1.AllocateAndConstruct<Point2D>(1, 2);
-  ContiguousContainer<Point2D, kPointAlignment> list2(kMaxPointSize);
+  ContiguousContainer<Point2D> list2(kMaxPointSize);
   list2.AllocateAndConstruct<Point2D>(3, 4);
   list2.AllocateAndConstruct<Point2D>(5, 6);
 
@@ -476,8 +479,7 @@ TEST(ContiguousContainerTest, CapacityInBytes) {
   // need to be adjusted.
   const size_t max_waste_factor = 8;
 
-  ContiguousContainer<Point2D, kPointAlignment> list(kMaxPointSize,
-                                                     initial_capacity);
+  ContiguousContainer<Point2D> list(kMaxPointSize, initial_capacity);
 
   // The capacity should grow with the list.
   for (int i = 0; i < iterations; i++) {
@@ -503,7 +505,7 @@ TEST(ContiguousContainerTest, CapacityInBytes) {
 TEST(ContiguousContainerTest, CapacityInBytesAfterClear) {
   // Clearing should restore the capacity of the container to the same as a
   // newly allocated one (without reserved capacity requested).
-  ContiguousContainer<Point2D, kPointAlignment> list(kMaxPointSize);
+  ContiguousContainer<Point2D> list(kMaxPointSize);
   size_t empty_capacity = list.GetCapacityInBytes();
   list.AllocateAndConstruct<Point2D>();
   list.AllocateAndConstruct<Point2D>();
@@ -511,5 +513,58 @@ TEST(ContiguousContainerTest, CapacityInBytesAfterClear) {
   EXPECT_EQ(empty_capacity, list.GetCapacityInBytes());
 }
 
-}  // namespace
+TEST(ContiguousContainerTest, Alignment) {
+  ContiguousContainer<char> container(64, 64);
+  void* item1 = container.Allocate(21, 4);  // alignment 16
+  ASSERT_TRUE(item1);
+  EXPECT_EQ(0u, reinterpret_cast<size_t>(item1) & 0x0F);
+  EXPECT_GE(21u, container.UsedCapacityInBytes());
+  // The initial gap may not be consistent among runs.
+  // |--------21-------|-------------------43-----------------------|
+  // |      item1      |                 unused                     |
+
+  void* item2 = container.Allocate(9, 3);  // alignment 8
+  ASSERT_TRUE(item2);
+  EXPECT_EQ(0u, reinterpret_cast<size_t>(item2) & 7);
+  // |---------24--------|---9---|----------------31----------------|
+  // |      item1      | | item2 |             unused               |
+  EXPECT_EQ(24u + 9u, container.UsedCapacityInBytes());
+
+  void* item3 = container.Allocate(3, 2);  // alignment 4
+  ASSERT_TRUE(item3);
+  EXPECT_EQ(0u, reinterpret_cast<size_t>(item3) & 3);
+  // |---------24--------|----12----|--3--|----------25-------------|
+  // |      item1      | | item2 |  |item3|        unused           |
+  EXPECT_EQ(24u + 12u + 3u, container.UsedCapacityInBytes());
+
+  void* item4 = container.Allocate(11, 0);
+  ASSERT_TRUE(item4);
+  // |---------24--------|----12----|--3--|---11---|-------14-------|
+  // |      item1      | | item2 |  |item3| item4  |     unused     |
+  EXPECT_EQ(24u + 12u + 3u + 11u, container.UsedCapacityInBytes());
+
+  // All of the above allocations should be in the initial buffer.
+  EXPECT_EQ(64u, container.GetCapacityInBytes());
+
+  // The initial buffer can't hold another object aligned at 16 bytes.
+  void* item5 = container.Allocate(8, 4);
+  ASSERT_TRUE(item5);
+  EXPECT_EQ(0u, reinterpret_cast<size_t>(item5) & 0x0F);
+  EXPECT_GT(container.GetCapacityInBytes(), 64u);
+
+  container.RemoveLast();  // item5
+  // The container should retain the last empty buffer to avoid reallocation of
+  // buffer for new item allocations.
+  EXPECT_GT(container.GetCapacityInBytes(), 64u);
+
+  container.RemoveLast();  // item4
+  EXPECT_EQ(24u + 12u + 3u, container.UsedCapacityInBytes());
+  container.RemoveLast();  // item3
+  EXPECT_EQ(24u + 12u, container.UsedCapacityInBytes());
+  container.RemoveLast();  // item2
+  EXPECT_EQ(24u, container.UsedCapacityInBytes());
+  container.RemoveLast();  // item1
+  EXPECT_EQ(0u, container.UsedCapacityInBytes());
+}
+
 }  // namespace cc