Fix alignment issue of ContiguousContainer

cc/base/contiguous_container.h

 // Copyright 2015 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #ifndef CC_BASE_CONTIGUOUS_CONTAINER_H_
 #define CC_BASE_CONTIGUOUS_CONTAINER_H_
 
 #include <stddef.h>
 
 #include <memory>
 #include <utility>
 
 #include "base/compiler_specific.h"
+#include "base/gtest_prod_util.h"
 #include "base/logging.h"
 #include "base/macros.h"
 #include "base/stl_util.h"
 #include "cc/base/cc_export.h"
 
 namespace cc {
 
+namespace internal {
+template <size_t input>
+struct Log2 {};
+template <>
+struct Log2<1> {
+  static const unsigned value = 0;
+};
+template <>
+struct Log2<2> {
+  static const unsigned value = 1;
+};
+template <>
+struct Log2<4> {
+  static const unsigned value = 2;
+};
+template <>
+struct Log2<8> {
+  static const unsigned value = 3;
+};
+template <>
+struct Log2<16> {
+  static const unsigned value = 4;
+};
+}  // namespace internal
+
+template <typename T>
+unsigned Log2Alignment() {
+  return internal::Log2<ALIGNOF(T)>::value;
+}
+
 // ContiguousContainer is a container which stores a list of heterogeneous
 // objects (in particular, of varying sizes), packed next to one another in
 // memory. Objects are never relocated, so it is safe to store pointers to them
 // for the lifetime of the container (unless the object is removed).
 //
 // Memory is allocated in a series of buffers (with exponential growth). When an
 // object is allocated, it is given only the space it requires (possibly with
 // enough padding to preserve alignment), rather than the maximum possible size.
 // This allows small and large objects to coexist without wasting much space.
 //
@@ skipping 11 matching lines @@
   ContiguousContainerBase(size_t max_object_size, size_t initial_size_bytes);
   ~ContiguousContainerBase();
 
   size_t size() const { return elements_.size(); }
   bool empty() const { return !size(); }
   size_t GetCapacityInBytes() const;
   size_t UsedCapacityInBytes() const;
   size_t MemoryUsageInBytes() const;
 
   // These do not invoke constructors or destructors.
-  void* Allocate(size_t object_size);
+  void* Allocate(size_t object_size, unsigned log2_alignment);
   void Clear();
   void RemoveLast();
   void Swap(ContiguousContainerBase& other);
 
   std::vector<void*> elements_;
 
  private:
   class Buffer;
 
   Buffer* AllocateNewBufferForNextAllocation(size_t buffer_size);
 
   std::vector<std::unique_ptr<Buffer>> buffers_;
   size_t end_index_;
   size_t max_object_size_;
 
   DISALLOW_COPY_AND_ASSIGN(ContiguousContainerBase);
 };
 
-// For most cases, no alignment stricter than pointer alignment is required. If
-// one of the derived classes has stronger alignment requirements (and the
-// static_assert fires), set alignment to the least common multiple of the
-// derived class alignments. For small structs without pointers, it may be
-// possible to reduce alignment for tighter packing.
-
-template <class BaseElementType, unsigned alignment = sizeof(void*)>
+template <class BaseElementType>
 class ContiguousContainer : public ContiguousContainerBase {
  private:
+  FRIEND_TEST_ALL_PREFIXES(ContiguousContainerTest, Alignment);
+
   // Declares itself as a forward iterator, but also supports a few more
   // things. The whole random access iterator interface is a bit much.
   template <typename BaseIterator, typename ValueType>
   class IteratorWrapper
       : public std::iterator<std::forward_iterator_tag, ValueType> {
    public:
     IteratorWrapper() {}
     bool operator==(const IteratorWrapper& other) const {
       return it_ == other.it_;
     }
@@ skipping 29 matching lines @@
       IteratorWrapper<std::vector<void*>::iterator, BaseElementType>;
   using const_iterator = IteratorWrapper<std::vector<void*>::const_iterator,
                                          const BaseElementType>;
   using reverse_iterator =
       IteratorWrapper<std::vector<void*>::reverse_iterator, BaseElementType>;
   using const_reverse_iterator =
       IteratorWrapper<std::vector<void*>::const_reverse_iterator,
                       const BaseElementType>;
 
   explicit ContiguousContainer(size_t max_object_size)
-      : ContiguousContainerBase(Align(max_object_size)) {}
+      : ContiguousContainerBase(max_object_size) {}
   ContiguousContainer(size_t max_object_size, size_t initial_size_bytes)
-      : ContiguousContainerBase(Align(max_object_size), initial_size_bytes) {}
+      : ContiguousContainerBase(max_object_size, initial_size_bytes) {}
 
   ~ContiguousContainer() {
     for (auto& element : *this) {
       // MSVC incorrectly reports this variable as unused.
       (void)element;
       element.~BaseElementType();
     }
   }
 
   using ContiguousContainerBase::size;
@@ skipping 19 matching lines @@
   const BaseElementType& first() const { return *begin(); }
   BaseElementType& last() { return *rbegin(); }
   const BaseElementType& last() const { return *rbegin(); }
   BaseElementType& operator[](size_t index) { return *(begin() + index); }
   const BaseElementType& operator[](size_t index) const {
     return *(begin() + index);
   }
 
   template <class DerivedElementType, typename... Args>
   DerivedElementType& AllocateAndConstruct(Args&&... args) {
-    static_assert(alignment % ALIGNOF(DerivedElementType) == 0,
-                  "Derived type requires stronger alignment.");
-    size_t alloc_size = Align(sizeof(DerivedElementType));
-    return *new (Allocate(alloc_size))
+    size_t alloc_size = sizeof(DerivedElementType);
+    return *new (Allocate(alloc_size, Log2Alignment<DerivedElementType>()))
         DerivedElementType(std::forward<Args>(args)...);
   }
 
   void RemoveLast() {
     DCHECK(!empty());
     last().~BaseElementType();
     ContiguousContainerBase::RemoveLast();
   }
 
   void Clear() {
     for (auto& element : *this) {
       // MSVC incorrectly reports this variable as unused.
       (void)element;
       element.~BaseElementType();
     }
     ContiguousContainerBase::Clear();
   }
 
   void Swap(ContiguousContainer& other) {
     ContiguousContainerBase::Swap(other);
   }
 
   // Appends a new element using memcpy, then default-constructs a base
   // element in its place. Use with care.
-  BaseElementType& AppendByMoving(BaseElementType* item, size_t size) {
+  BaseElementType& AppendByMoving(BaseElementType* item,
+                                  size_t size,
+                                  unsigned log2_alignment) {
     DCHECK_GE(size, sizeof(BaseElementType));
-    void* new_item = Allocate(size);
+    void* new_item = Allocate(size, log2_alignment);
     memcpy(new_item, static_cast<void*>(item), size);
     new (item) BaseElementType;
     return *static_cast<BaseElementType*>(new_item);
   }
-
- private:
-  static size_t Align(size_t size) {
-    size_t aligned_size = alignment * ((size + alignment - 1) / alignment);
-    DCHECK_EQ(aligned_size % alignment, 0u);
-    DCHECK_GE(aligned_size, size);
-    DCHECK_LT(aligned_size, size + alignment);
-    return aligned_size;
-  }
 };
 
 }  // namespace cc
 
 #endif  // CC_BASE_CONTIGUOUS_CONTAINER_H_