diff options
-rw-r--r-- | cc/BUILD.gn | 1 | ||||
-rw-r--r-- | cc/base/BUILD.gn | 1 | ||||
-rw-r--r-- | cc/base/list_container_helper.h | 3 | ||||
-rw-r--r-- | cc/base/random_access_list_container.h | 94 | ||||
-rw-r--r-- | cc/base/random_access_list_container_unittest.cc | 107 | ||||
-rw-r--r-- | cc/cc.gyp | 1 | ||||
-rw-r--r-- | cc/cc_tests.gyp | 1 |
7 files changed, 208 insertions, 0 deletions
diff --git a/cc/BUILD.gn b/cc/BUILD.gn index 095c6de..922ac34 100644 --- a/cc/BUILD.gn +++ b/cc/BUILD.gn @@ -725,6 +725,7 @@ test("cc_unittests") { "base/histograms_unittest.cc", "base/list_container_unittest.cc", "base/math_util_unittest.cc", + "base/random_access_list_container_unittest.cc", "base/region_unittest.cc", "base/rolling_time_delta_history_unittest.cc", "base/scoped_ptr_vector_unittest.cc", diff --git a/cc/base/BUILD.gn b/cc/base/BUILD.gn index 974f8a3..53194c9 100644 --- a/cc/base/BUILD.gn +++ b/cc/base/BUILD.gn @@ -18,6 +18,7 @@ source_set("base") { "list_container_helper.h", "math_util.cc", "math_util.h", + "random_access_list_container.h", "region.cc", "region.h", "resource_id.h", diff --git a/cc/base/list_container_helper.h b/cc/base/list_container_helper.h index fb953a6..31b2310 100644 --- a/cc/base/list_container_helper.h +++ b/cc/base/list_container_helper.h @@ -18,6 +18,9 @@ class CC_EXPORT ListContainerHelper final { template <typename T> friend class ListContainer; + template <typename T> + friend class RandomAccessListContainer; + explicit ListContainerHelper(size_t max_size_for_derived_class); ListContainerHelper(size_t max_size_for_derived_class, size_t num_of_elements_to_reserve_for); diff --git a/cc/base/random_access_list_container.h b/cc/base/random_access_list_container.h new file mode 100644 index 0000000..b2baf30 --- /dev/null +++ b/cc/base/random_access_list_container.h @@ -0,0 +1,94 @@ +// 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_RANDOM_ACCESS_LIST_CONTAINER_H_ +#define CC_BASE_RANDOM_ACCESS_LIST_CONTAINER_H_ + +#include <vector> + +#include "base/logging.h" +#include "cc/base/list_container_helper.h" + +namespace cc { + +// RandomAccessListContainer is a container similar to ListContainer (see +// list_container.h), but it allows random access into its elements via +// operator[]. In order to have efficient support for random access, some +// functionality is not available for RandomAccessListContainers, such as +// insert/deletes in the middle of the list. +template <class BaseElementType> +class RandomAccessListContainer { + public: + // BaseElementType is the type of raw pointers this class hands out; however, + // its derived classes might require different memory sizes. + // max_size_for_derived_class the largest memory size required for all the + // derived classes to use for allocation. + explicit RandomAccessListContainer(size_t max_size_for_derived_class) + : helper_(max_size_for_derived_class) {} + + // This constructor reserves the requested memory up front so only a single + // allocation is needed. When num_of_elements_to_reserve_for is zero, use the + // default size. + RandomAccessListContainer(size_t max_size_for_derived_class, + size_t num_of_elements_to_reserve_for) + : helper_(max_size_for_derived_class, num_of_elements_to_reserve_for) { + items_.reserve(num_of_elements_to_reserve_for); + } + + ~RandomAccessListContainer() { + for (BaseElementType* item : items_) + item->~BaseElementType(); + } + + void clear() { + for (BaseElementType* item : items_) + item->~BaseElementType(); + helper_.clear(); + items_.clear(); + } + + bool empty() const { return helper_.empty(); } + size_t size() const { return helper_.size(); } + size_t GetCapacityInBytes() const { return helper_.GetCapacityInBytes(); } + + template <typename DerivedElementType> + DerivedElementType* AllocateAndConstruct() { + auto* value = + new (helper_.Allocate(sizeof(DerivedElementType))) DerivedElementType; + items_.push_back(value); + return value; + } + + void RemoveLast() { + items_.back()->~BaseElementType(); + items_.pop_back(); + helper_.RemoveLast(); + } + + const BaseElementType* operator[](size_t index) const { + DCHECK_GE(index, 0u); + DCHECK_LT(index, items_.size()); + return items_[index]; + } + + BaseElementType* operator[](size_t index) { + DCHECK_GE(index, 0u); + DCHECK_LT(index, items_.size()); + return items_[index]; + } + + // Note that although BaseElementType objects can change, the pointer itself + // (in the vector) cannot. So this class only supports a const iterator. + using ConstIterator = typename std::vector<BaseElementType*>::const_iterator; + ConstIterator begin() const { return items_.begin(); } + ConstIterator end() const { return items_.end(); } + + private: + ListContainerHelper helper_; + std::vector<BaseElementType*> items_; +}; + +} // namespace cc + +#endif // CC_BASE_RANDOM_ACCESS_LIST_CONTAINER_H_ diff --git a/cc/base/random_access_list_container_unittest.cc b/cc/base/random_access_list_container_unittest.cc new file mode 100644 index 0000000..78004b4 --- /dev/null +++ b/cc/base/random_access_list_container_unittest.cc @@ -0,0 +1,107 @@ +// 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. + +#include "cc/base/random_access_list_container.h" + +#include <algorithm> +#include <vector> + +#include "testing/gmock/include/gmock/gmock.h" +#include "testing/gtest/include/gtest/gtest.h" + +namespace cc { +namespace { + +class Base { + public: + virtual ~Base() {} + int get_value() const { return value_; } + + protected: + explicit Base(int value) : value_(value) {} + + int value_; +}; + +const int kMagicNumberOne = 1; +const int kMagicNumberTwo = 2; +const int kMagicNumberThree = 3; + +class Derived1 : public Base { + public: + Derived1() : Base(kMagicNumberOne) {} +}; + +class Derived2 : public Base { + public: + Derived2() : Base(kMagicNumberTwo) {} +}; + +class Derived3 : public Base { + public: + Derived3() : Base(kMagicNumberThree) {} +}; + +size_t LargestDerivedElementSize() { + static_assert(sizeof(Derived1) >= sizeof(Derived2), + "Derived2 is larger than Derived1"); + static_assert(sizeof(Derived1) >= sizeof(Derived3), + "Derived3 is larger than Derived1"); + return sizeof(Derived1); +} + +TEST(RandomAccessListContainerTest, RandomAccess) { + RandomAccessListContainer<Base> list(LargestDerivedElementSize(), 1); + + list.AllocateAndConstruct<Derived1>(); + list.AllocateAndConstruct<Derived2>(); + list.AllocateAndConstruct<Derived3>(); + list.AllocateAndConstruct<Derived1>(); + list.AllocateAndConstruct<Derived2>(); + list.AllocateAndConstruct<Derived3>(); + + EXPECT_EQ(kMagicNumberOne, list[0]->get_value()); + EXPECT_EQ(kMagicNumberTwo, list[1]->get_value()); + EXPECT_EQ(kMagicNumberThree, list[2]->get_value()); + EXPECT_EQ(kMagicNumberOne, list[3]->get_value()); + EXPECT_EQ(kMagicNumberTwo, list[4]->get_value()); + EXPECT_EQ(kMagicNumberThree, list[5]->get_value()); + + list.RemoveLast(); + list.RemoveLast(); + list.RemoveLast(); + + EXPECT_EQ(kMagicNumberOne, list[0]->get_value()); + EXPECT_EQ(kMagicNumberTwo, list[1]->get_value()); + EXPECT_EQ(kMagicNumberThree, list[2]->get_value()); + + list.AllocateAndConstruct<Derived3>(); + list.AllocateAndConstruct<Derived2>(); + list.AllocateAndConstruct<Derived1>(); + + EXPECT_EQ(kMagicNumberOne, list[0]->get_value()); + EXPECT_EQ(kMagicNumberTwo, list[1]->get_value()); + EXPECT_EQ(kMagicNumberThree, list[2]->get_value()); + EXPECT_EQ(kMagicNumberThree, list[3]->get_value()); + EXPECT_EQ(kMagicNumberTwo, list[4]->get_value()); + EXPECT_EQ(kMagicNumberOne, list[5]->get_value()); +} + +TEST(RandomAccessListContainerTest, Clear) { + RandomAccessListContainer<Base> list(LargestDerivedElementSize(), 1); + + list.AllocateAndConstruct<Derived1>(); + list.AllocateAndConstruct<Derived2>(); + + EXPECT_EQ(kMagicNumberOne, list[0]->get_value()); + EXPECT_EQ(kMagicNumberTwo, list[1]->get_value()); + + list.clear(); + list.AllocateAndConstruct<Derived3>(); + + EXPECT_EQ(kMagicNumberThree, list[0]->get_value()); +} + +} // namespace +} // namespace cc @@ -85,6 +85,7 @@ 'base/list_container_helper.h', 'base/math_util.cc', 'base/math_util.h', + 'base/random_access_list_container.h', 'base/region.cc', 'base/region.h', 'base/resource_id.h', diff --git a/cc/cc_tests.gyp b/cc/cc_tests.gyp index 0ce77be..c5a0124 100644 --- a/cc/cc_tests.gyp +++ b/cc/cc_tests.gyp @@ -22,6 +22,7 @@ 'base/histograms_unittest.cc', 'base/list_container_unittest.cc', 'base/math_util_unittest.cc', + 'base/random_access_list_container_unittest.cc', 'base/region_unittest.cc', 'base/rolling_time_delta_history_unittest.cc', 'base/scoped_ptr_vector_unittest.cc', |