Add a SmallMap to base for small map lookups.

This map has a static array that it will check brute-force before overflowing
into a normal map. For cases where simple key-value lookup is needed where there
are not expected to be many elements, this will be faster.

This adds ManualConstructor which is required for this.

This code is from internal util/gtl/small_map.h. I made the following changes:

Renamed small_map to SmallMap.

Added everything to the base namespace.

Added the helper templates at the top to a sub namespace "internal"

I renamed small_map_default_init to SmallMapDefaultInit since it's a class and that's how we name clases. However, I didn't rename has_key_equal and select_key_equal since those work with something called key_equal on the base container. I went back and forth on this, I'm happy to change.

Renamed the non-STL-like functions to CamelCase. The only case was "using_full_map" -> UsingFullMap

Removed unit test for the size of a Small Map (I don't think we care).

Added note about preferring hash_map for key equality checking.

Redid manual_constructor to use aligned_memory instead of manually doing everything itself. This removed a bunch of preprocessor goop and manual alignment. I also removed the 9-12 argument constructor versions of Init, which seemed excessive.

Removed InsertIfNotPresent unit test (we don't have an InsertIfNotPresent map helper function).

Added std:: on various things like pairs and make_pair and max.

Made SmallMap::size() and count() and erase() return size_t insted of int to keep compat for unsigned-vs-signed for STL. Added "u" after numbers in EXPECT_EQs to avoid signed/unsigned warnings.

BUG=

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

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@167001 0039d316-1c4b-4281-b951-d872f2087c98

1 files changed, 125 insertions, 0 deletions

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_