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..ce134e4b0a718148e60b03b20464bf7ab98921b6 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), ALIGNOF(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), ALIGNOF(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),
+                         ALIGNOF(DestructionNotifier));
     EXPECT_FALSE(destroyed);
   }
   // But it should be destroyed when list2 is.
@@ -376,27 +376,29 @@ 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), ALIGNOF(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), ALIGNOF(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), ALIGNOF(Point2D));
   EXPECT_EQ(0, list1.first().x);
   EXPECT_EQ(0, list1.first().y);
   EXPECT_EQ(1, list2.first().x);
@@ -407,7 +409,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 +421,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), ALIGNOF(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), ALIGNOF(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 +437,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 +478,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 +504,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 +512,64 @@ TEST(ContiguousContainerTest, CapacityInBytesAfterClear) {
   EXPECT_EQ(empty_capacity, list.GetCapacityInBytes());
 }
 
-}  // namespace
+TEST(ContiguousContainerTest, Alignment) {
+  ContiguousContainer<char> container(256, 256);
+  void* item1 = container.Allocate(5, 128);
+  ASSERT_TRUE(item1);
+  EXPECT_EQ(0u, reinterpret_cast<size_t>(item1) & 0x7F);
+  EXPECT_GE(container.UsedCapacityInBytes(), 5u);
+  // The initial gap may not be consistent among runs.
+  // |initial_gap|--5--|---------------------unused--------------------------|
+  //             |item1|
+  size_t initial_gap = container.UsedCapacityInBytes() - 5;
+
+  void* item2 = container.Allocate(11, 64);
+  ASSERT_TRUE(item2);
+  EXPECT_EQ(0u, reinterpret_cast<size_t>(item2) & 0x3F);
+  // |initial_gap|-------64--------|-11--|--------------unused---------------|
+  //             |item1|           |item2|
+  EXPECT_EQ(initial_gap + 64u + 11u, container.UsedCapacityInBytes());
+
+  void* item3 = container.Allocate(13, 32);
+  ASSERT_TRUE(item3);
+  EXPECT_EQ(0u, reinterpret_cast<size_t>(item3) & 0x1F);
+  // |initial_gap|-------64--------|----32-----|-13--|-------unused----------|
+  //             |item1|           |item2|     |item3|
+  EXPECT_EQ(initial_gap + 64u + 32u + 13u, container.UsedCapacityInBytes());
+
+  void* item4 = container.Allocate(7, 16);
+  ASSERT_TRUE(item4);
+  EXPECT_EQ(0u, reinterpret_cast<size_t>(item4) & 0x0F);
+  // |initial_gap|-------64--------|----32-----|---16----|--7--|---unused----|
+  //             |item1|           |item2|     |item3|   |item4|
+  EXPECT_EQ(initial_gap + 64u + 32u + 16u + 7u,
+            container.UsedCapacityInBytes());
+
+  // All of the above allocations should be in the initial buffer.
+  EXPECT_EQ(container.GetCapacityInBytes(), 256u);
+
+  // item5 may or may not be allocated in the initial buffer, depending on
+  // initial_gap.
+  void* item5 = container.Allocate(9, 16);
+  ASSERT_TRUE(item5);
+  EXPECT_EQ(0u, reinterpret_cast<size_t>(item5) & 0x0F);
+
+  // Definitely the initial buffer can't hold another small object aligned at
+  // 128 bytes, because the buffer has no more available 128-byte aligned
+  // address.
+  void* item6 = container.Allocate(17, 128);
+  ASSERT_TRUE(item6);
+  EXPECT_EQ(0u, reinterpret_cast<size_t>(item6) & 0x3F);
+  EXPECT_GT(container.GetCapacityInBytes(), 256u);
+
+  container.RemoveLast();  // item6
+  container.RemoveLast();  // item5
+  // The container should retain the last empty buffer to avoid reallocation of
+  // buffer for new item allocations.
+  EXPECT_GT(container.GetCapacityInBytes(), 256u);
+
+  container.RemoveLast();  // item4
+  EXPECT_EQ(initial_gap + 64u + 32u + 16u, container.UsedCapacityInBytes());
+}
+
 }  // namespace cc