Added ScopedPtrMap class, for maps that contain scoped_ptr values.

It is not currently possible to use scoped_ptr values in a std::map, due
to lack of C++11 library support; this class is a placeholder mapping
type that allows scoped_ptr values.

Internally, ScopedPtrMap does not use scoped_ptrs; it uses raw pointers
and automatically deletes its values when it is destroyed, or elements
are removed from the map. It is therefore safer to use than a map with
owned raw pointers as values, even when using an STLValueDeleter. It
also makes ownership much clearer, as you can insert elements into the
map via scoped_ptrs.

BUG=478594

Review URL: https://codereview.chromium.org/1076273004

Cr-Commit-Position: refs/heads/master@{#334083}

2 files changed, 361 insertions, 0 deletions

diff --git a/base/containers/scoped_ptr_map.h b/base/containers/scoped_ptr_map.h
new file mode 100644
index 0000000..19a1153
--- /dev/null
+++ b/base/containers/scoped_ptr_map.h
@@ -0,0 +1,137 @@
+// 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 BASE_CONTAINERS_SCOPED_PTR_MAP_H_
+#define BASE_CONTAINERS_SCOPED_PTR_MAP_H_
+
+#include <map>
+#include <utility>
+
+#include "base/basictypes.h"
+#include "base/memory/scoped_ptr.h"
+#include "base/move.h"
+#include "base/stl_util.h"
+
+// ScopedPtrMap provides a std::map that supports scoped_ptr values. It ensures
+// that the map's values are properly deleted when removed from the map, or when
+// the map is destroyed.
+//
+// |ScopedPtr| must be a type scoped_ptr<T>. This is for compatibility with
+// std::map in C++11.
+template <class Key, class ScopedPtr>
+class ScopedPtrMap {
+  MOVE_ONLY_TYPE_WITH_MOVE_CONSTRUCTOR_FOR_CPP_03(ScopedPtrMap)
+
+  using Container = std::map<Key, typename ScopedPtr::element_type*>;
+
+ public:
+  using allocator_type = typename Container::allocator_type;
+  using size_type = typename Container::size_type;
+  using difference_type = typename Container::difference_type;
+  using reference = typename Container::reference;
+  using const_reference = typename Container::const_reference;
+  using key_type = typename Container::key_type;
+  using const_iterator = typename Container::const_iterator;
+  using const_reverse_iterator = typename Container::const_reverse_iterator;
+
+  ScopedPtrMap() {}
+  ~ScopedPtrMap() { clear(); }
+  ScopedPtrMap(ScopedPtrMap<Key, ScopedPtr>&& other) { swap(other); }
+
+  ScopedPtrMap& operator=(ScopedPtrMap<Key, ScopedPtr>&& rhs) {
+    swap(rhs);
+    return *this;
+  }
+
+  const_iterator find(const Key& k) const { return data_.find(k); }
+  size_type count(const Key& k) const { return data_.count(k); }
+
+  bool empty() const { return data_.empty(); }
+  size_t size() const { return data_.size(); }
+
+  const_reverse_iterator rbegin() const { return data_.rbegin(); }
+  const_reverse_iterator rend() const { return data_.rend(); }
+
+  const_iterator begin() const { return data_.begin(); }
+  const_iterator end() const { return data_.end(); }
+
+  void swap(ScopedPtrMap<Key, ScopedPtr>& other) { data_.swap(other.data_); }
+
+  void clear() { STLDeleteValues(&data_); }
+
+  // Inserts |val| into the map, associated with |key|.
+  std::pair<const_iterator, bool> insert(const Key& key, ScopedPtr val) {
+    auto result = data_.insert(std::make_pair(key, val.get()));
+    if (result.second)
+      ignore_result(val.release());
+    return result;
+  }
+
+  // Inserts |val| into the map, associated with |key|. Overwrites any existing
+  // element at |key|.
+  void set(const Key& key, ScopedPtr val) {
+    typename ScopedPtr::element_type*& val_ref = data_[key];
+    delete val_ref;
+    val_ref = val.release();
+  }
+
+  void erase(const_iterator position) {
+    DCHECK(position != end());
+    delete position->second;
+    // Key-based lookup (cannot use const_iterator overload in C++03 library).
+    data_.erase(position->first);
+  }
+
+  size_type erase(const Key& k) {
+    typename Container::iterator it = data_.find(k);
+    if (it == end())
+      return 0;
+
+    delete it->second;
+    data_.erase(it);
+    return 1;
+  }
+
+  void erase(const_iterator first, const_iterator last) {
+    STLDeleteContainerPairSecondPointers(first, last);
+    // Need non-const iterators as required by the C++03 library.
+    data_.erase(ConstIteratorToIterator(first), ConstIteratorToIterator(last));
+  }
+
+  // Like |erase()|, but returns the element instead of deleting it.
+  ScopedPtr take_and_erase(const_iterator position) {
+    DCHECK(position != end());
+    if (position == end())
+      return ScopedPtr();
+
+    ScopedPtr ret(position->second);
+    // Key-based lookup (cannot use const_iterator overload in C++03 library).
+    data_.erase(position->first);
+    return ret.Pass();
+  }
+
+  // Like |erase()|, but returns the element instead of deleting it.
+  ScopedPtr take_and_erase(const Key& k) {
+    typename Container::iterator it = data_.find(k);
+    if (it == end())
+      return ScopedPtr();
+
+    ScopedPtr ret(it->second);
+    data_.erase(it);
+    return ret.Pass();
+  }
+
+ private:
+  Container data_;
+
+  typename Container::iterator ConstIteratorToIterator(const_iterator it) {
+    // This is the only way to convert a const iterator to a non-const iterator
+    // in C++03 (get the key and do the lookup again).
+    if (it == data_.end())
+      return data_.end();
+    return data_.find(it->first);
+  };
+};
+
+#endif  // BASE_CONTAINERS_SCOPED_PTR_MAP_H_
diff --git a/base/containers/scoped_ptr_map_unittest.cc b/base/containers/scoped_ptr_map_unittest.cc
new file mode 100644
index 0000000..ef70440
--- /dev/null
+++ b/base/containers/scoped_ptr_map_unittest.cc
@@ -0,0 +1,224 @@
+// 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 "base/containers/scoped_ptr_map.h"
+
+#include <map>
+#include <utility>
+
+#include "base/bind.h"
+#include "base/callback.h"
+#include "base/memory/scoped_ptr.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace {
+
+// A ScopedDestroyer sets a Boolean to true upon destruction.
+class ScopedDestroyer {
+ public:
+  ScopedDestroyer(bool* destroyed) : destroyed_(destroyed) {
+    *destroyed_ = false;
+  }
+
+  ~ScopedDestroyer() { *destroyed_ = true; }
+
+ private:
+  bool* destroyed_;
+};
+
+TEST(ScopedPtrMapTest, Insert) {
+  bool destroyed1 = false;
+  bool destroyed2 = false;
+  {
+    ScopedPtrMap<int, scoped_ptr<ScopedDestroyer>> scoped_map;
+
+    // Insert to new key.
+    ScopedDestroyer* elem1 = new ScopedDestroyer(&destroyed1);
+    EXPECT_FALSE(destroyed1);
+    EXPECT_TRUE(scoped_map.insert(0, make_scoped_ptr(elem1)).second);
+    EXPECT_EQ(elem1, scoped_map.find(0)->second);
+    EXPECT_FALSE(destroyed1);
+
+    // Insert to existing key.
+    ScopedDestroyer* elem2 = new ScopedDestroyer(&destroyed2);
+    EXPECT_FALSE(destroyed2);
+    EXPECT_FALSE(scoped_map.insert(0, make_scoped_ptr(elem2)).second);
+    EXPECT_EQ(elem1, scoped_map.find(0)->second);
+
+    EXPECT_FALSE(destroyed1);
+    EXPECT_TRUE(destroyed2);
+  }
+  EXPECT_TRUE(destroyed1);
+}
+
+TEST(ScopedPtrMapTest, Set) {
+  bool destroyed1 = false;
+  bool destroyed2 = false;
+  {
+    ScopedPtrMap<int, scoped_ptr<ScopedDestroyer>> scoped_map;
+
+    // Set a new key.
+    ScopedDestroyer* elem1 = new ScopedDestroyer(&destroyed1);
+    EXPECT_FALSE(destroyed1);
+    scoped_map.set(0, make_scoped_ptr(elem1));
+    EXPECT_EQ(elem1, scoped_map.find(0)->second);
+    EXPECT_FALSE(destroyed1);
+
+    // Set to replace an existing key.
+    ScopedDestroyer* elem2 = new ScopedDestroyer(&destroyed2);
+    EXPECT_FALSE(destroyed2);
+    scoped_map.set(0, make_scoped_ptr(elem2));
+    EXPECT_EQ(elem2, scoped_map.find(0)->second);
+
+    EXPECT_TRUE(destroyed1);
+    EXPECT_FALSE(destroyed2);
+  }
+  EXPECT_TRUE(destroyed1);
+  EXPECT_TRUE(destroyed2);
+}
+
+TEST(ScopedPtrMapTest, EraseIterator) {
+  bool destroyed = false;
+  ScopedPtrMap<int, scoped_ptr<ScopedDestroyer>> scoped_map;
+  scoped_map.insert(0, make_scoped_ptr(new ScopedDestroyer(&destroyed)));
+  EXPECT_FALSE(destroyed);
+  scoped_map.erase(scoped_map.find(0));
+  EXPECT_TRUE(destroyed);
+  EXPECT_TRUE(scoped_map.empty());
+}
+
+TEST(ScopedPtrMapTest, EraseKey) {
+  bool destroyed = false;
+  ScopedPtrMap<int, scoped_ptr<ScopedDestroyer>> scoped_map;
+  scoped_map.insert(0, make_scoped_ptr(new ScopedDestroyer(&destroyed)));
+  EXPECT_FALSE(destroyed);
+  EXPECT_EQ(1u, scoped_map.erase(0));
+  EXPECT_TRUE(destroyed);
+  EXPECT_TRUE(scoped_map.empty());
+
+  // Test erase of a non-existent key.
+  EXPECT_EQ(0u, scoped_map.erase(7));
+}
+
+TEST(ScopedPtrMapTest, EraseRange) {
+  bool destroyed1 = false;
+  bool destroyed2 = false;
+  ScopedPtrMap<int, scoped_ptr<ScopedDestroyer>> scoped_map;
+
+  scoped_map.insert(0, make_scoped_ptr(new ScopedDestroyer(&destroyed1)));
+  EXPECT_FALSE(destroyed1);
+
+  scoped_map.insert(1, make_scoped_ptr(new ScopedDestroyer(&destroyed2)));
+  EXPECT_FALSE(destroyed2);
+
+  scoped_map.erase(scoped_map.find(0), scoped_map.end());
+  EXPECT_TRUE(destroyed1);
+  EXPECT_TRUE(destroyed2);
+  EXPECT_TRUE(scoped_map.empty());
+}
+
+TEST(ScopedPtrMapTest, TakeAndErase) {
+  bool destroyed = false;
+  ScopedPtrMap<int, scoped_ptr<ScopedDestroyer>> scoped_map;
+  ScopedDestroyer* elem = new ScopedDestroyer(&destroyed);
+  scoped_map.insert(0, make_scoped_ptr(elem));
+  EXPECT_EQ(elem, scoped_map.find(0)->second);
+  EXPECT_FALSE(destroyed);
+  scoped_ptr<ScopedDestroyer> object = scoped_map.take_and_erase(0);
+  EXPECT_EQ(elem, object.get());
+  EXPECT_FALSE(destroyed);
+  EXPECT_TRUE(scoped_map.empty());
+  object.reset();
+  EXPECT_TRUE(destroyed);
+}
+
+TEST(ScopedPtrMapTest, Clear) {
+  bool destroyed = false;
+  ScopedPtrMap<int, scoped_ptr<ScopedDestroyer>> scoped_map;
+  scoped_map.insert(0, make_scoped_ptr(new ScopedDestroyer(&destroyed)));
+  EXPECT_FALSE(destroyed);
+  scoped_map.clear();
+  EXPECT_TRUE(destroyed);
+  EXPECT_TRUE(scoped_map.empty());
+}
+
+TEST(ScopedPtrMapTest, Scope) {
+  bool destroyed = false;
+  {
+    ScopedPtrMap<int, scoped_ptr<ScopedDestroyer>> scoped_map;
+    scoped_map.insert(0, make_scoped_ptr(new ScopedDestroyer(&destroyed)));
+    EXPECT_FALSE(destroyed);
+  }
+  EXPECT_TRUE(destroyed);
+}
+
+TEST(ScopedPtrMapTest, MoveConstruct) {
+  bool destroyed = false;
+  {
+    ScopedPtrMap<int, scoped_ptr<ScopedDestroyer>> scoped_map;
+    ScopedDestroyer* elem = new ScopedDestroyer(&destroyed);
+    scoped_map.insert(0, make_scoped_ptr(elem));
+    EXPECT_EQ(elem, scoped_map.find(0)->second);
+    EXPECT_FALSE(destroyed);
+    EXPECT_FALSE(scoped_map.empty());
+
+    ScopedPtrMap<int, scoped_ptr<ScopedDestroyer>> scoped_map_copy(
+        scoped_map.Pass());
+    EXPECT_TRUE(scoped_map.empty());
+    EXPECT_FALSE(scoped_map_copy.empty());
+    EXPECT_EQ(elem, scoped_map_copy.find(0)->second);
+    EXPECT_FALSE(destroyed);
+  }
+  EXPECT_TRUE(destroyed);
+}
+
+TEST(ScopedPtrMapTest, MoveAssign) {
+  bool destroyed = false;
+  {
+    ScopedPtrMap<int, scoped_ptr<ScopedDestroyer>> scoped_map;
+    ScopedDestroyer* elem = new ScopedDestroyer(&destroyed);
+    scoped_map.insert(0, make_scoped_ptr(elem));
+    EXPECT_EQ(elem, scoped_map.find(0)->second);
+    EXPECT_FALSE(destroyed);
+    EXPECT_FALSE(scoped_map.empty());
+
+    ScopedPtrMap<int, scoped_ptr<ScopedDestroyer>> scoped_map_assign;
+    scoped_map_assign = scoped_map.Pass();
+    EXPECT_TRUE(scoped_map.empty());
+    EXPECT_FALSE(scoped_map_assign.empty());
+    EXPECT_EQ(elem, scoped_map_assign.find(0)->second);
+    EXPECT_FALSE(destroyed);
+  }
+  EXPECT_TRUE(destroyed);
+}
+
+template <typename Key, typename ScopedPtr>
+ScopedPtrMap<Key, ScopedPtr> PassThru(ScopedPtrMap<Key, ScopedPtr> scoper) {
+  return scoper;
+}
+
+TEST(ScopedPtrMapTest, Passed) {
+  bool destroyed = false;
+  ScopedPtrMap<int, scoped_ptr<ScopedDestroyer>> scoped_map;
+  ScopedDestroyer* elem = new ScopedDestroyer(&destroyed);
+  scoped_map.insert(0, make_scoped_ptr(elem));
+  EXPECT_EQ(elem, scoped_map.find(0)->second);
+  EXPECT_FALSE(destroyed);
+
+  base::Callback<ScopedPtrMap<int, scoped_ptr<ScopedDestroyer>>(void)>
+      callback = base::Bind(&PassThru<int, scoped_ptr<ScopedDestroyer>>,
+                            base::Passed(&scoped_map));
+  EXPECT_TRUE(scoped_map.empty());
+  EXPECT_FALSE(destroyed);
+
+  ScopedPtrMap<int, scoped_ptr<ScopedDestroyer>> result = callback.Run();
+  EXPECT_TRUE(scoped_map.empty());
+  EXPECT_EQ(elem, result.find(0)->second);
+  EXPECT_FALSE(destroyed);
+
+  result.clear();
+  EXPECT_TRUE(destroyed);
+};
+
+}  // namespace