diff options
| -rw-r--r-- | base/base.gyp | 1 | ||||
| -rw-r--r-- | base/base.gypi | 2 | ||||
| -rw-r--r-- | base/containers/small_map.h | 652 | ||||
| -rw-r--r-- | base/containers/small_map_unittest.cc | 491 | ||||
| -rw-r--r-- | base/memory/manual_constructor.h | 125 |
5 files changed, 1271 insertions, 0 deletions
diff --git a/base/base.gyp b/base/base.gyp index 0497c14..cc26f48 100644 --- a/base/base.gyp +++ b/base/base.gyp @@ -420,6 +420,7 @@ 'callback_unittest.nc', 'cancelable_callback_unittest.cc', 'command_line_unittest.cc', + 'containers/small_map_unittest.cc', 'cpu_unittest.cc', 'debug/leak_tracker_unittest.cc', 'debug/stack_trace_unittest.cc', diff --git a/base/base.gypi b/base/base.gypi index 3517653..465ab81 100644 --- a/base/base.gypi +++ b/base/base.gypi @@ -91,6 +91,7 @@ 'command_line.cc', 'command_line.h', 'compiler_specific.h', + 'containers/small_map.h', 'cpu.cc', 'cpu.h', 'critical_closure.h', @@ -233,6 +234,7 @@ 'memory/aligned_memory.cc', 'memory/aligned_memory.h', 'memory/linked_ptr.h', + 'memory/manual_constructor.h', 'memory/mru_cache.h', 'memory/raw_scoped_refptr_mismatch_checker.h', 'memory/ref_counted.cc', diff --git a/base/containers/small_map.h b/base/containers/small_map.h new file mode 100644 index 0000000..2c9ca25 --- /dev/null +++ b/base/containers/small_map.h @@ -0,0 +1,652 @@ +// Copyright (c) 2012 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 BASE_CONTAINERS_SMALL_MAP_H_ +#define BASE_CONTAINERS_SMALL_MAP_H_ + +#include <map> +#include <string> +#include <utility> + +#include "base/basictypes.h" +#include "base/hash_tables.h" +#include "base/logging.h" +#include "base/memory/manual_constructor.h" + +namespace base { + +// An STL-like associative container which starts out backed by a simple +// array but switches to some other container type if it grows beyond a +// fixed size. +// +// WHAT TYPE OF MAP SHOULD YOU USE? +// -------------------------------- +// +// - std::map should be the default if you're not sure, since it's the most +// difficult to mess up. Generally this is backed by a red-black tree. It +// will generate a lot of code (if you use a common key type like int or +// string the linker will probably emiminate the duplicates). It will +// do heap allocations for each element. +// +// - If you only ever keep a couple of items and have very simple usage, +// consider whether a using a vector and brute-force searching it will be +// the most efficient. It's not a lot of generated code (less then a +// red-black tree if your key is "weird" and not eliminated as duplicate of +// something else) and will probably be faster and do fewer heap allocations +// than std::map if you have just a couple of items. +// +// - base::hash_map should be used if you need O(1) lookups. It may waste +// space in the hash table, and it can be easy to write correct-looking +// code with the default hash function being wrong or poorly-behaving. +// +// - SmallMap combines the performance benefits of the brute-force-searched +// vector for small cases (no extra heap allocations), but can efficiently +// fall back if you end up adding many items. It will generate more code +// than std::map (at least 160 bytes for operator[]) which is bad if you +// have a "weird" key where map functions can't be +// duplicate-code-eliminated. If you have a one-off key and aren't in +// performance-critical code, this bloat may negate some of the benefits and +// you should consider on of the other options. +// +// SmallMap will pick up the comparator from the underlying map type. In +// std::map (and in MSVC additionally hash_map) only a "less" operator is +// defined, which requires us to do two comparisons per element when doing the +// brute-force search in the simple array. +// +// We define default overrides for the common map types to avoid this +// double-compare, but you should be aware of this if you use your own +// operator< for your map and supply yor own version of == to the SmallMap. +// You can use regular operator== by just doing: +// +// base::SmallMap<std::map<MyKey, MyValue>, 4, std::equal_to<KyKey> > +// +// +// USAGE +// ----- +// +// NormalMap: The map type to fall back to. This also defines the key +// and value types for the SmallMap. +// kArraySize: The size of the initial array of results. This will be +// allocated with the SmallMap object rather than separately on +// the heap. Once the map grows beyond this size, the map type +// will be used instead. +// EqualKey: A functor which tests two keys for equality. If the wrapped +// map type has a "key_equal" member (hash_map does), then that will +// be used by default. If the wrapped map type has a strict weak +// ordering "key_compare" (std::map does), that will be used to +// implement equality by default. +// MapInit: A functor that takes a ManualConstructor<NormalMap>* and uses it to +// initialize the map. This functor will be called at most once per +// SmallMap, when the map exceeds the threshold of kArraySize and we +// are about to copy values from the array to the map. The functor +// *must* call one of the Init() methods provided by +// ManualConstructor, since after it runs we assume that the NormalMap +// has been initialized. +// +// example: +// base::SmallMap< std::map<string, int> > days; +// days["sunday" ] = 0; +// days["monday" ] = 1; +// days["tuesday" ] = 2; +// days["wednesday"] = 3; +// days["thursday" ] = 4; +// days["friday" ] = 5; +// days["saturday" ] = 6; +// +// You should assume that SmallMap might invalidate all the iterators +// on any call to erase(), insert() and operator[]. + +namespace internal { + +template <typename NormalMap> +class SmallMapDefaultInit { + public: + void operator()(ManualConstructor<NormalMap>* map) const { + map->Init(); + } +}; + +// has_key_equal<M>::value is true iff there exists a type M::key_equal. This is +// used to dispatch to one of the select_equal_key<> metafunctions below. +template <typename M> +struct has_key_equal { + typedef char sml; // "small" is sometimes #defined so we use an abbreviation. + typedef struct { char dummy[2]; } big; + // Two functions, one accepts types that have a key_equal member, and one that + // accepts anything. They each return a value of a different size, so we can + // determine at compile-time which function would have been called. + template <typename U> static big test(typename U::key_equal*); + template <typename> static sml test(...); + // Determines if M::key_equal exists by looking at the size of the return + // type of the compiler-chosen test() function. + static const bool value = (sizeof(test<M>(0)) == sizeof(big)); +}; +template <typename M> const bool has_key_equal<M>::value; + +// Base template used for map types that do NOT have an M::key_equal member, +// e.g., std::map<>. These maps have a strict weak ordering comparator rather +// than an equality functor, so equality will be implemented in terms of that +// comparator. +// +// There's a partial specialization of this template below for map types that do +// have an M::key_equal member. +template <typename M, bool has_key_equal_value> +struct select_equal_key { + struct equal_key { + bool operator()(const typename M::key_type& left, + const typename M::key_type& right) { + // Implements equality in terms of a strict weak ordering comparator. + typename M::key_compare comp; + return !comp(left, right) && !comp(right, left); + } + }; +}; + +// Provide overrides to use operator== for key compare for the "normal" map and +// hash map types. If you override the default comparator or allocator for a +// map or hash_map, or use another type of map, this won't get used. +// +// If we switch to using std::unordered_map for base::hash_map, then the +// hash_map specialization can be removed. +template <typename KeyType, typename ValueType> +struct select_equal_key< std::map<KeyType, ValueType>, false> { + struct equal_key { + bool operator()(const KeyType& left, const KeyType& right) { + return left == right; + } + }; +}; +template <typename KeyType, typename ValueType> +struct select_equal_key< base::hash_map<KeyType, ValueType>, false> { + struct equal_key { + bool operator()(const KeyType& left, const KeyType& right) { + return left == right; + } + }; +}; + +// Partial template specialization handles case where M::key_equal exists, e.g., +// hash_map<>. +template <typename M> +struct select_equal_key<M, true> { + typedef typename M::key_equal equal_key; +}; + +} // namespace internal + +template <typename NormalMap, + int kArraySize = 4, + typename EqualKey = + typename internal::select_equal_key< + NormalMap, + internal::has_key_equal<NormalMap>::value>::equal_key, + typename MapInit = internal::SmallMapDefaultInit<NormalMap> > +class SmallMap { + // We cannot rely on the compiler to reject array of size 0. In + // particular, gcc 2.95.3 does it but later versions allow 0-length + // arrays. Therefore, we explicitly reject non-positive kArraySize + // here. + COMPILE_ASSERT(kArraySize > 0, default_initial_size_should_be_positive); + + public: + typedef typename NormalMap::key_type key_type; + typedef typename NormalMap::mapped_type data_type; + typedef typename NormalMap::mapped_type mapped_type; + typedef typename NormalMap::value_type value_type; + typedef EqualKey key_equal; + + SmallMap() : size_(0), functor_(MapInit()) {} + + explicit SmallMap(const MapInit& functor) : size_(0), functor_(functor) {} + + // Allow copy-constructor and assignment, since STL allows them too. + SmallMap(const SmallMap& src) { + // size_ and functor_ are initted in InitFrom() + InitFrom(src); + } + void operator=(const SmallMap& src) { + if (&src == this) return; + + // This is not optimal. If src and dest are both using the small + // array, we could skip the teardown and reconstruct. One problem + // to be resolved is that the value_type itself is pair<const K, + // V>, and const K is not assignable. + Destroy(); + InitFrom(src); + } + ~SmallMap() { + Destroy(); + } + + class const_iterator; + + class iterator { + public: + typedef typename NormalMap::iterator::iterator_category iterator_category; + typedef typename NormalMap::iterator::value_type value_type; + typedef typename NormalMap::iterator::difference_type difference_type; + typedef typename NormalMap::iterator::pointer pointer; + typedef typename NormalMap::iterator::reference reference; + + inline iterator(): array_iter_(NULL) {} + + inline iterator& operator++() { + if (array_iter_ != NULL) { + ++array_iter_; + } else { + ++hash_iter_; + } + return *this; + } + inline iterator operator++(int /*unused*/) { + iterator result(*this); + ++(*this); + return result; + } + inline iterator& operator--() { + if (array_iter_ != NULL) { + --array_iter_; + } else { + --hash_iter_; + } + return *this; + } + inline iterator operator--(int /*unused*/) { + iterator result(*this); + --(*this); + return result; + } + inline value_type* operator->() const { + if (array_iter_ != NULL) { + return array_iter_->get(); + } else { + return hash_iter_.operator->(); + } + } + + inline value_type& operator*() const { + if (array_iter_ != NULL) { + return *array_iter_->get(); + } else { + return *hash_iter_; + } + } + + inline bool operator==(const iterator& other) const { + if (array_iter_ != NULL) { + return array_iter_ == other.array_iter_; + } else { + return other.array_iter_ == NULL && hash_iter_ == other.hash_iter_; + } + } + + inline bool operator!=(const iterator& other) const { + return !(*this == other); + } + + bool operator==(const const_iterator& other) const; + bool operator!=(const const_iterator& other) const; + + private: + friend class SmallMap; + friend class const_iterator; + inline explicit iterator(ManualConstructor<value_type>* init) + : array_iter_(init) {} + inline explicit iterator(const typename NormalMap::iterator& init) + : array_iter_(NULL), hash_iter_(init) {} + + ManualConstructor<value_type>* array_iter_; + typename NormalMap::iterator hash_iter_; + }; + + class const_iterator { + public: + typedef typename NormalMap::const_iterator::iterator_category + iterator_category; + typedef typename NormalMap::const_iterator::value_type value_type; + typedef typename NormalMap::const_iterator::difference_type difference_type; + typedef typename NormalMap::const_iterator::pointer pointer; + typedef typename NormalMap::const_iterator::reference reference; + + inline const_iterator(): array_iter_(NULL) {} + // Non-explicit ctor lets us convert regular iterators to const iterators + inline const_iterator(const iterator& other) + : array_iter_(other.array_iter_), hash_iter_(other.hash_iter_) {} + + inline const_iterator& operator++() { + if (array_iter_ != NULL) { + ++array_iter_; + } else { + ++hash_iter_; + } + return *this; + } + inline const_iterator operator++(int /*unused*/) { + const_iterator result(*this); + ++(*this); + return result; + } + + inline const_iterator& operator--() { + if (array_iter_ != NULL) { + --array_iter_; + } else { + --hash_iter_; + } + return *this; + } + inline const_iterator operator--(int /*unused*/) { + const_iterator result(*this); + --(*this); + return result; + } + + inline const value_type* operator->() const { + if (array_iter_ != NULL) { + return array_iter_->get(); + } else { + return hash_iter_.operator->(); + } + } + + inline const value_type& operator*() const { + if (array_iter_ != NULL) { + return *array_iter_->get(); + } else { + return *hash_iter_; + } + } + + inline bool operator==(const const_iterator& other) const { + if (array_iter_ != NULL) { + return array_iter_ == other.array_iter_; + } else { + return other.array_iter_ == NULL && hash_iter_ == other.hash_iter_; + } + } + + inline bool operator!=(const const_iterator& other) const { + return !(*this == other); + } + + private: + friend class SmallMap; + inline explicit const_iterator( + const ManualConstructor<value_type>* init) + : array_iter_(init) {} + inline explicit const_iterator( + const typename NormalMap::const_iterator& init) + : array_iter_(NULL), hash_iter_(init) {} + + const ManualConstructor<value_type>* array_iter_; + typename NormalMap::const_iterator hash_iter_; + }; + + iterator find(const key_type& key) { + key_equal compare; + if (size_ >= 0) { + for (int i = 0; i < size_; i++) { + if (compare(array_[i]->first, key)) { + return iterator(array_ + i); + } + } + return iterator(array_ + size_); + } else { + return iterator(map()->find(key)); + } + } + + const_iterator find(const key_type& key) const { + key_equal compare; + if (size_ >= 0) { + for (int i = 0; i < size_; i++) { + if (compare(array_[i]->first, key)) { + return const_iterator(array_ + i); + } + } + return const_iterator(array_ + size_); + } else { + return const_iterator(map()->find(key)); + } + } + + // Invalidates iterators. + data_type& operator[](const key_type& key) { + key_equal compare; + + if (size_ >= 0) { + // operator[] searches backwards, favoring recently-added + // elements. + for (int i = size_-1; i >= 0; --i) { + if (compare(array_[i]->first, key)) { + return array_[i]->second; + } + } + if (size_ == kArraySize) { + ConvertToRealMap(); + return (*map_)[key]; + } else { + array_[size_].Init(key, data_type()); + return array_[size_++]->second; + } + } else { + return (*map_)[key]; + } + } + + // Invalidates iterators. + std::pair<iterator, bool> insert(const value_type& x) { + key_equal compare; + + if (size_ >= 0) { + for (int i = 0; i < size_; i++) { + if (compare(array_[i]->first, x.first)) { + return std::make_pair(iterator(array_ + i), false); + } + } + if (size_ == kArraySize) { + ConvertToRealMap(); // Invalidates all iterators! + std::pair<typename NormalMap::iterator, bool> ret = map_->insert(x); + return std::make_pair(iterator(ret.first), ret.second); + } else { + array_[size_].Init(x); + return std::make_pair(iterator(array_ + size_++), true); + } + } else { + std::pair<typename NormalMap::iterator, bool> ret = map_->insert(x); + return std::make_pair(iterator(ret.first), ret.second); + } + } + + // Invalidates iterators. + template <class InputIterator> + void insert(InputIterator f, InputIterator l) { + while (f != l) { + insert(*f); + ++f; + } + } + + iterator begin() { + if (size_ >= 0) { + return iterator(array_); + } else { + return iterator(map_->begin()); + } + } + const_iterator begin() const { + if (size_ >= 0) { + return const_iterator(array_); + } else { + return const_iterator(map_->begin()); + } + } + + iterator end() { + if (size_ >= 0) { + return iterator(array_ + size_); + } else { + return iterator(map_->end()); + } + } + const_iterator end() const { + if (size_ >= 0) { + return const_iterator(array_ + size_); + } else { + return const_iterator(map_->end()); + } + } + + void clear() { + if (size_ >= 0) { + for (int i = 0; i < size_; i++) { + array_[i].Destroy(); + } + } else { + map_.Destroy(); + } + size_ = 0; + } + + // Invalidates iterators. + void erase(const iterator& position) { + if (size_ >= 0) { + int i = position.array_iter_ - array_; + array_[i].Destroy(); + --size_; + if (i != size_) { + array_[i].Init(*array_[size_]); + array_[size_].Destroy(); + } + } else { + map_->erase(position.hash_iter_); + } + } + + size_t erase(const key_type& key) { + iterator iter = find(key); + if (iter == end()) return 0u; + erase(iter); + return 1u; + } + + size_t count(const key_type& key) const { + return (find(key) == end()) ? 0 : 1; + } + + size_t size() const { + if (size_ >= 0) { + return static_cast<size_t>(size_); + } else { + return map_->size(); + } + } + + bool empty() const { + if (size_ >= 0) { + return (size_ == 0); + } else { + return map_->empty(); + } + } + + // Returns true if we have fallen back to using the underlying map + // representation. + bool UsingFullMap() const { + return size_ < 0; + } + + inline NormalMap* map() { + CHECK(UsingFullMap()); + return map_.get(); + } + inline const NormalMap* map() const { + CHECK(UsingFullMap()); + return map_.get(); + } + + private: + int size_; // negative = using hash_map + + MapInit functor_; + + // We want to call constructors and destructors manually, but we don't + // want to allocate and deallocate the memory used for them separately. + // So, we use this crazy ManualConstructor class. + // + // Since array_ and map_ are mutually exclusive, we'll put them in a + // union, too. We add in a dummy_ value which quiets MSVC from otherwise + // giving an erroneous "union member has copy constructor" error message + // (C2621). This dummy member has to come before array_ to quiet the + // compiler. + // + // TODO(brettw) remove this and use C++11 unions when we require C++11. + union { + ManualConstructor<value_type> dummy_; + ManualConstructor<value_type> array_[kArraySize]; + ManualConstructor<NormalMap> map_; + }; + + void ConvertToRealMap() { + // Move the current elements into a temporary array. + ManualConstructor<value_type> temp_array[kArraySize]; + + for (int i = 0; i < kArraySize; i++) { + temp_array[i].Init(*array_[i]); + array_[i].Destroy(); + } + + // Initialize the map. + size_ = -1; + functor_(&map_); + + // Insert elements into it. + for (int i = 0; i < kArraySize; i++) { + map_->insert(*temp_array[i]); + temp_array[i].Destroy(); + } + } + + // Helpers for constructors and destructors. + void InitFrom(const SmallMap& src) { + functor_ = src.functor_; + size_ = src.size_; + if (src.size_ >= 0) { + for (int i = 0; i < size_; i++) { + array_[i].Init(*src.array_[i]); + } + } else { + functor_(&map_); + (*map_.get()) = (*src.map_.get()); + } + } + void Destroy() { + if (size_ >= 0) { + for (int i = 0; i < size_; i++) { + array_[i].Destroy(); + } + } else { + map_.Destroy(); + } + } +}; + +template <typename NormalMap, int kArraySize, typename EqualKey, + typename Functor> +inline bool SmallMap<NormalMap, kArraySize, EqualKey, + Functor>::iterator::operator==( + const const_iterator& other) const { + return other == *this; +} +template <typename NormalMap, int kArraySize, typename EqualKey, + typename Functor> +inline bool SmallMap<NormalMap, kArraySize, EqualKey, + Functor>::iterator::operator!=( + const const_iterator& other) const { + return other != *this; +} + +} // namespace base + +#endif // BASE_CONTAINERS_SMALL_MAP_H_ diff --git a/base/containers/small_map_unittest.cc b/base/containers/small_map_unittest.cc new file mode 100644 index 0000000..d1c8680 --- /dev/null +++ b/base/containers/small_map_unittest.cc @@ -0,0 +1,491 @@ +// Copyright (c) 2012 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 "base/containers/small_map.h" + +#include <stddef.h> + +#include <algorithm> +#include <functional> +#include <map> + +#include "base/logging.h" +#include "base/hash_tables.h" +#include "testing/gtest/include/gtest/gtest.h" + +namespace base { + +TEST(SmallMap, General) { + SmallMap<hash_map<int, int> > m; + + EXPECT_TRUE(m.empty()); + + m[0] = 5; + + EXPECT_FALSE(m.empty()); + EXPECT_EQ(m.size(), 1u); + + m[9] = 2; + + EXPECT_FALSE(m.empty()); + EXPECT_EQ(m.size(), 2u); + + EXPECT_EQ(m[9], 2); + EXPECT_EQ(m[0], 5); + EXPECT_FALSE(m.UsingFullMap()); + + SmallMap<hash_map<int, int> >::iterator iter(m.begin()); + ASSERT_TRUE(iter != m.end()); + EXPECT_EQ(iter->first, 0); + EXPECT_EQ(iter->second, 5); + ++iter; + ASSERT_TRUE(iter != m.end()); + EXPECT_EQ((*iter).first, 9); + EXPECT_EQ((*iter).second, 2); + ++iter; + EXPECT_TRUE(iter == m.end()); + + m[8] = 23; + m[1234] = 90; + m[-5] = 6; + + EXPECT_EQ(m[ 9], 2); + EXPECT_EQ(m[ 0], 5); + EXPECT_EQ(m[1234], 90); + EXPECT_EQ(m[ 8], 23); + EXPECT_EQ(m[ -5], 6); + EXPECT_EQ(m.size(), 5u); + EXPECT_FALSE(m.empty()); + EXPECT_TRUE(m.UsingFullMap()); + + iter = m.begin(); + for (int i = 0; i < 5; i++) { + EXPECT_TRUE(iter != m.end()); + ++iter; + } + EXPECT_TRUE(iter == m.end()); + + const SmallMap<hash_map<int, int> >& ref = m; + EXPECT_TRUE(ref.find(1234) != m.end()); + EXPECT_TRUE(ref.find(5678) == m.end()); +} + +TEST(SmallMap, PostFixIteratorIncrement) { + SmallMap<hash_map<int, int> > m; + m[0] = 5; + m[2] = 3; + + { + SmallMap<hash_map<int, int> >::iterator iter(m.begin()); + SmallMap<hash_map<int, int> >::iterator last(iter++); + ++last; + EXPECT_TRUE(last == iter); + } + + { + SmallMap<hash_map<int, int> >::const_iterator iter(m.begin()); + SmallMap<hash_map<int, int> >::const_iterator last(iter++); + ++last; + EXPECT_TRUE(last == iter); + } +} + +// Based on the General testcase. +TEST(SmallMap, CopyConstructor) { + SmallMap<hash_map<int, int> > src; + + { + SmallMap<hash_map<int, int> > m(src); + EXPECT_TRUE(m.empty()); + } + + src[0] = 5; + + { + SmallMap<hash_map<int, int> > m(src); + EXPECT_FALSE(m.empty()); + EXPECT_EQ(m.size(), 1u); + } + + src[9] = 2; + + { + SmallMap<hash_map<int, int> > m(src); + EXPECT_FALSE(m.empty()); + EXPECT_EQ(m.size(), 2u); + + EXPECT_EQ(m[9], 2); + EXPECT_EQ(m[0], 5); + EXPECT_FALSE(m.UsingFullMap()); + } + + src[8] = 23; + src[1234] = 90; + src[-5] = 6; + + { + SmallMap<hash_map<int, int> > m(src); + EXPECT_EQ(m[ 9], 2); + EXPECT_EQ(m[ 0], 5); + EXPECT_EQ(m[1234], 90); + EXPECT_EQ(m[ 8], 23); + EXPECT_EQ(m[ -5], 6); + EXPECT_EQ(m.size(), 5u); + EXPECT_FALSE(m.empty()); + EXPECT_TRUE(m.UsingFullMap()); + } +} + +template<class inner> +static void SmallMapToMap(SmallMap<inner> const& src, inner* dest) { + typename SmallMap<inner>::const_iterator it; + for (it = src.begin(); it != src.end(); ++it) { + dest->insert(std::make_pair(it->first, it->second)); + } +} + +template<class inner> +static bool SmallMapEqual(SmallMap<inner> const& a, + SmallMap<inner> const& b) { + inner ia, ib; + SmallMapToMap(a, &ia); + SmallMapToMap(b, &ib); + + // On most systems we can use operator== here, but under some lesser STL + // implementations it doesn't seem to work. So we manually compare. + if (ia.size() != ib.size()) + return false; + for (typename inner::iterator ia_it = ia.begin(), ib_it = ib.begin(); + ia_it != ia.end(); ++ia_it, ++ib_it) { + if (*ia_it != *ib_it) + return false; + } + return true; +} + +TEST(SmallMap, AssignmentOperator) { + SmallMap<hash_map<int, int> > src_small; + SmallMap<hash_map<int, int> > src_large; + + src_small[1] = 20; + src_small[2] = 21; + src_small[3] = 22; + EXPECT_FALSE(src_small.UsingFullMap()); + + src_large[1] = 20; + src_large[2] = 21; + src_large[3] = 22; + src_large[5] = 23; + src_large[6] = 24; + src_large[7] = 25; + EXPECT_TRUE(src_large.UsingFullMap()); + + // Assignments to empty. + SmallMap<hash_map<int, int> > dest_small; + dest_small = src_small; + EXPECT_TRUE(SmallMapEqual(dest_small, src_small)); + EXPECT_EQ(dest_small.UsingFullMap(), + src_small.UsingFullMap()); + + SmallMap<hash_map<int, int> > dest_large; + dest_large = src_large; + EXPECT_TRUE(SmallMapEqual(dest_large, src_large)); + EXPECT_EQ(dest_large.UsingFullMap(), + src_large.UsingFullMap()); + + // Assignments which assign from full to small, and vice versa. + dest_small = src_large; + EXPECT_TRUE(SmallMapEqual(dest_small, src_large)); + EXPECT_EQ(dest_small.UsingFullMap(), + src_large.UsingFullMap()); + + dest_large = src_small; + EXPECT_TRUE(SmallMapEqual(dest_large, src_small)); + EXPECT_EQ(dest_large.UsingFullMap(), + src_small.UsingFullMap()); + + // Double check that SmallMapEqual works: + dest_large[42] = 666; + EXPECT_FALSE(SmallMapEqual(dest_large, src_small)); +} + +TEST(SmallMap, Insert) { + SmallMap<hash_map<int, int> > sm; + + // loop through the transition from small map to map. + for (int i = 1; i <= 10; ++i) { + VLOG(1) << "Iteration " << i; + // insert an element + std::pair<SmallMap<hash_map<int, int> >::iterator, + bool> ret; + ret = sm.insert(std::make_pair(i, 100*i)); + EXPECT_TRUE(ret.second); + EXPECT_TRUE(ret.first == sm.find(i)); + EXPECT_EQ(ret.first->first, i); + EXPECT_EQ(ret.first->second, 100*i); + + // try to insert it again with different value, fails, but we still get an + // iterator back with the original value. + ret = sm.insert(std::make_pair(i, -i)); + EXPECT_FALSE(ret.second); + EXPECT_TRUE(ret.first == sm.find(i)); + EXPECT_EQ(ret.first->first, i); + EXPECT_EQ(ret.first->second, 100*i); + + // check the state of the map. + for (int j = 1; j <= i; ++j) { + SmallMap<hash_map<int, int> >::iterator it = sm.find(j); + EXPECT_TRUE(it != sm.end()); + EXPECT_EQ(it->first, j); + EXPECT_EQ(it->second, j * 100); + } + EXPECT_EQ(sm.size(), static_cast<size_t>(i)); + EXPECT_FALSE(sm.empty()); + } +} + +TEST(SmallMap, InsertRange) { + // loop through the transition from small map to map. + for (int elements = 0; elements <= 10; ++elements) { + VLOG(1) << "Elements " << elements; + hash_map<int, int> normal_map; + for (int i = 1; i <= elements; ++i) { + normal_map.insert(std::make_pair(i, 100*i)); + } + + SmallMap<hash_map<int, int> > sm; + sm.insert(normal_map.begin(), normal_map.end()); + EXPECT_EQ(normal_map.size(), sm.size()); + for (int i = 1; i <= elements; ++i) { + VLOG(1) << "Iteration " << i; + EXPECT_TRUE(sm.find(i) != sm.end()); + EXPECT_EQ(sm.find(i)->first, i); + EXPECT_EQ(sm.find(i)->second, 100*i); + } + } +} + +TEST(SmallMap, Erase) { + SmallMap<hash_map<std::string, int> > m; + SmallMap<hash_map<std::string, int> >::iterator iter; + + m["monday"] = 1; + m["tuesday"] = 2; + m["wednesday"] = 3; + + EXPECT_EQ(m["monday" ], 1); + EXPECT_EQ(m["tuesday" ], 2); + EXPECT_EQ(m["wednesday"], 3); + EXPECT_EQ(m.count("tuesday"), 1u); + EXPECT_FALSE(m.UsingFullMap()); + + iter = m.begin(); + ASSERT_TRUE(iter != m.end()); + EXPECT_EQ(iter->first, "monday"); + EXPECT_EQ(iter->second, 1); + ++iter; + ASSERT_TRUE(iter != m.end()); + EXPECT_EQ(iter->first, "tuesday"); + EXPECT_EQ(iter->second, 2); + ++iter; + ASSERT_TRUE(iter != m.end()); + EXPECT_EQ(iter->first, "wednesday"); + EXPECT_EQ(iter->second, 3); + ++iter; + EXPECT_TRUE(iter == m.end()); + + EXPECT_EQ(m.erase("tuesday"), 1u); + + EXPECT_EQ(m["monday" ], 1); + EXPECT_EQ(m["wednesday"], 3); + EXPECT_EQ(m.count("tuesday"), 0u); + EXPECT_EQ(m.erase("tuesday"), 0u); + + iter = m.begin(); + ASSERT_TRUE(iter != m.end()); + EXPECT_EQ(iter->first, "monday"); + EXPECT_EQ(iter->second, 1); + ++iter; + ASSERT_TRUE(iter != m.end()); + EXPECT_EQ(iter->first, "wednesday"); + EXPECT_EQ(iter->second, 3); + ++iter; + EXPECT_TRUE(iter == m.end()); + + m["thursday"] = 4; + m["friday"] = 5; + EXPECT_EQ(m.size(), 4u); + EXPECT_FALSE(m.empty()); + EXPECT_FALSE(m.UsingFullMap()); + + m["saturday"] = 6; + EXPECT_TRUE(m.UsingFullMap()); + + EXPECT_EQ(m.count("friday"), 1u); + EXPECT_EQ(m.erase("friday"), 1u); + EXPECT_TRUE(m.UsingFullMap()); + EXPECT_EQ(m.count("friday"), 0u); + EXPECT_EQ(m.erase("friday"), 0u); + + EXPECT_EQ(m.size(), 4u); + EXPECT_FALSE(m.empty()); + EXPECT_EQ(m.erase("monday"), 1u); + EXPECT_EQ(m.size(), 3u); + EXPECT_FALSE(m.empty()); + + m.clear(); + EXPECT_FALSE(m.UsingFullMap()); + EXPECT_EQ(m.size(), 0u); + EXPECT_TRUE(m.empty()); +} + +TEST(SmallMap, NonHashMap) { + SmallMap<std::map<int, int>, 4, std::equal_to<int> > m; + EXPECT_TRUE(m.empty()); + + m[9] = 2; + m[0] = 5; + + EXPECT_EQ(m[9], 2); + EXPECT_EQ(m[0], 5); + EXPECT_EQ(m.size(), 2u); + EXPECT_FALSE(m.empty()); + EXPECT_FALSE(m.UsingFullMap()); + + SmallMap<std::map<int, int>, 4, std::equal_to<int> >::iterator iter( + m.begin()); + ASSERT_TRUE(iter != m.end()); + EXPECT_EQ(iter->first, 9); + EXPECT_EQ(iter->second, 2); + ++iter; + ASSERT_TRUE(iter != m.end()); + EXPECT_EQ(iter->first, 0); + EXPECT_EQ(iter->second, 5); + ++iter; + EXPECT_TRUE(iter == m.end()); + --iter; + ASSERT_TRUE(iter != m.end()); + EXPECT_EQ(iter->first, 0); + EXPECT_EQ(iter->second, 5); + + m[8] = 23; + m[1234] = 90; + m[-5] = 6; + + EXPECT_EQ(m[ 9], 2); + EXPECT_EQ(m[ 0], 5); + EXPECT_EQ(m[1234], 90); + EXPECT_EQ(m[ 8], 23); + EXPECT_EQ(m[ -5], 6); + EXPECT_EQ(m.size(), 5u); + EXPECT_FALSE(m.empty()); + EXPECT_TRUE(m.UsingFullMap()); + + iter = m.begin(); + ASSERT_TRUE(iter != m.end()); + EXPECT_EQ(iter->first, -5); + EXPECT_EQ(iter->second, 6); + ++iter; + ASSERT_TRUE(iter != m.end()); + EXPECT_EQ(iter->first, 0); + EXPECT_EQ(iter->second, 5); + ++iter; + ASSERT_TRUE(iter != m.end()); + EXPECT_EQ(iter->first, 8); + EXPECT_EQ(iter->second, 23); + ++iter; + ASSERT_TRUE(iter != m.end()); + EXPECT_EQ(iter->first, 9); + EXPECT_EQ(iter->second, 2); + ++iter; + ASSERT_TRUE(iter != m.end()); + EXPECT_EQ(iter->first, 1234); + EXPECT_EQ(iter->second, 90); + ++iter; + EXPECT_TRUE(iter == m.end()); + --iter; + ASSERT_TRUE(iter != m.end()); + EXPECT_EQ(iter->first, 1234); + EXPECT_EQ(iter->second, 90); +} + +TEST(SmallMap, DefaultEqualKeyWorks) { + // If these tests compile, they pass. The EXPECT calls are only there to avoid + // unused variable warnings. + SmallMap<hash_map<int, int> > hm; + EXPECT_EQ(0u, hm.size()); + SmallMap<std::map<int, int> > m; + EXPECT_EQ(0u, m.size()); +} + +namespace { + +class hash_map_add_item : public hash_map<int, int> { + public: + hash_map_add_item() : hash_map<int, int>() {} + hash_map_add_item(const std::pair<int, int>& item) : hash_map<int, int>() { + insert(item); + } +}; + +void InitMap(ManualConstructor<hash_map_add_item>* map_ctor) { + map_ctor->Init(std::make_pair(0, 0)); +} + +class hash_map_add_item_initializer { + public: + explicit hash_map_add_item_initializer(int item_to_add) + : item_(item_to_add) {} + hash_map_add_item_initializer() + : item_(0) {} + void operator()(ManualConstructor<hash_map_add_item>* map_ctor) const { + map_ctor->Init(std::make_pair(item_, item_)); + } + + int item_; +}; + +} // anonymous namespace + +TEST(SmallMap, SubclassInitializationWithFunctionPointer) { + SmallMap<hash_map_add_item, 4, std::equal_to<int>, + void (&)(ManualConstructor<hash_map_add_item>*)> m(InitMap); + + EXPECT_TRUE(m.empty()); + + m[1] = 1; + m[2] = 2; + m[3] = 3; + m[4] = 4; + + EXPECT_EQ(4u, m.size()); + EXPECT_EQ(0u, m.count(0)); + + m[5] = 5; + EXPECT_EQ(6u, m.size()); + // Our function adds an extra item when we convert to a map. + EXPECT_EQ(1u, m.count(0)); +} + +TEST(SmallMap, SubclassInitializationWithFunctionObject) { + SmallMap<hash_map_add_item, 4, std::equal_to<int>, + hash_map_add_item_initializer> m(hash_map_add_item_initializer(-1)); + + EXPECT_TRUE(m.empty()); + + m[1] = 1; + m[2] = 2; + m[3] = 3; + m[4] = 4; + + EXPECT_EQ(4u, m.size()); + EXPECT_EQ(0u, m.count(-1)); + + m[5] = 5; + EXPECT_EQ(6u, m.size()); + // Our functor adds an extra item when we convert to a map. + EXPECT_EQ(1u, m.count(-1)); +} + +} // namespace base diff --git a/base/memory/manual_constructor.h b/base/memory/manual_constructor.h new file mode 100644 index 0000000..9275f73 --- /dev/null +++ b/base/memory/manual_constructor.h @@ -0,0 +1,125 @@ +// Copyright (c) 2012 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. + +// ManualConstructor statically-allocates space in which to store some +// object, but does not initialize it. You can then call the constructor +// and destructor for the object yourself as you see fit. This is useful +// for memory management optimizations, where you want to initialize and +// destroy an object multiple times but only allocate it once. +// +// (When I say ManualConstructor statically allocates space, I mean that +// the ManualConstructor object itself is forced to be the right size.) +// +// For example usage, check out base/containers/small_map.h. + +#ifndef BASE_MEMORY_MANUAL_CONSTRUCTOR_H_ +#define BASE_MEMORY_MANUAL_CONSTRUCTOR_H_ + +#include <stddef.h> + +#include "base/memory/aligned_memory.h" + +namespace base { + +template <typename Type> +class ManualConstructor { + public: + // No constructor or destructor because one of the most useful uses of + // this class is as part of a union, and members of a union cannot have + // constructors or destructors. And, anyway, the whole point of this + // class is to bypass these. + + // Support users creating arrays of ManualConstructor<>s. This ensures that + // the array itself has the correct alignment. + static void* operator new[](size_t size) { +#if defined(COMPILER_MSVC) + return AlignedAlloc(size, __alignof(Type)); +#else + return AlignedAlloc(size, __alignof__(Type)); +#endif + } + static void operator delete[](void* mem) { + AlignedFree(mem); + } + + inline Type* get() { + return space_.template data_as<Type>(); + } + inline const Type* get() const { + return space_.template data_as<Type>(); + } + + inline Type* operator->() { return get(); } + inline const Type* operator->() const { return get(); } + + inline Type& operator*() { return *get(); } + inline const Type& operator*() const { return *get(); } + + // You can pass up to eight constructor arguments as arguments of Init(). + inline void Init() { + new(space_.void_data()) Type; + } + + template <typename T1> + inline void Init(const T1& p1) { + new(space_.void_data()) Type(p1); + } + + template <typename T1, typename T2> + inline void Init(const T1& p1, const T2& p2) { + new(space_.void_data()) Type(p1, p2); + } + + template <typename T1, typename T2, typename T3> + inline void Init(const T1& p1, const T2& p2, const T3& p3) { + new(space_.void_data()) Type(p1, p2, p3); + } + + template <typename T1, typename T2, typename T3, typename T4> + inline void Init(const T1& p1, const T2& p2, const T3& p3, const T4& p4) { + new(space_.void_data()) Type(p1, p2, p3, p4); + } + + template <typename T1, typename T2, typename T3, typename T4, typename T5> + inline void Init(const T1& p1, const T2& p2, const T3& p3, const T4& p4, + const T5& p5) { + new(space_.void_data()) Type(p1, p2, p3, p4, p5); + } + + template <typename T1, typename T2, typename T3, typename T4, typename T5, + typename T6> + inline void Init(const T1& p1, const T2& p2, const T3& p3, const T4& p4, + const T5& p5, const T6& p6) { + new(space_.void_data()) Type(p1, p2, p3, p4, p5, p6); + } + + template <typename T1, typename T2, typename T3, typename T4, typename T5, + typename T6, typename T7> + inline void Init(const T1& p1, const T2& p2, const T3& p3, const T4& p4, + const T5& p5, const T6& p6, const T7& p7) { + new(space_.void_data()) Type(p1, p2, p3, p4, p5, p6, p7); + } + + template <typename T1, typename T2, typename T3, typename T4, typename T5, + typename T6, typename T7, typename T8> + inline void Init(const T1& p1, const T2& p2, const T3& p3, const T4& p4, + const T5& p5, const T6& p6, const T7& p7, const T8& p8) { + new(space_.void_data()) Type(p1, p2, p3, p4, p5, p6, p7, p8); + } + + inline void Destroy() { + get()->~Type(); + } + + private: +#if defined(COMPILER_MSVC) + AlignedMemory<sizeof(Type), __alignof(Type)> space_; +#else + AlignedMemory<sizeof(Type), __alignof__(Type)> space_; +#endif +}; + +} // namespace base + +#endif // BASE_MEMORY_MANUAL_CONSTRUCTOR_H_ |