diff --git a/runtime/base/variant_map.h b/runtime/base/variant_map.h
new file mode 100644
index 0000000..cf7977e
--- /dev/null
+++ b/runtime/base/variant_map.h
@@ -0,0 +1,453 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ART_RUNTIME_BASE_VARIANT_MAP_H_
+#define ART_RUNTIME_BASE_VARIANT_MAP_H_
+
+#include <memory.h>
+#include <map>
+#include <utility>
+
+namespace art {
+
+//
+// A variant map is a heterogenous, type safe key->value map. It allows
+// for multiple different value types to be stored dynamically in the same map.
+//
+// It provides the following interface in a nutshell:
+//
+// struct VariantMap {
+//   template <typename TValue>
+//   TValue* Get(Key<T> key);  // nullptr if the value was never set, otherwise the value.
+//
+//   template <typename TValue>
+//   void Set(Key<T> key, TValue value);
+// };
+//
+// Since the key is strongly typed at compile-time, it is impossible to accidentally
+// read/write a value with a different type than the key at either compile-time or run-time.
+//
+// Do not use VariantMap/VariantMapKey directly. Instead subclass each of them and use
+// the subclass, for example:
+//
+// template <typename TValue>
+// struct FruitMapKey : VariantMapKey<TValue> {
+//   FruitMapKey() {}
+// };
+//
+// struct FruitMap : VariantMap<FruitMap, FruitMapKey> {
+//   // This 'using' line is necessary to inherit the variadic constructor.
+//   using VariantMap<FruitMap, FruitMapKey>::VariantMap;
+//
+//   // Make the next '4' usages of Key slightly shorter to type.
+//   template <typename TValue>
+//   using Key = FruitMapKey<TValue>;
+//
+//   static const Key<int> Apple;
+//   static const Key<double> Orange;
+//   static const Key<std::string> Banana;
+// };
+//
+// const FruitMap::Key<int> FruitMap::Apple;
+// const FruitMap::Key<double> FruitMap::Orange;
+// const FruitMap::Key<std::string> Banana;
+//
+// See variant_map_test.cc for more examples.
+//
+
+// Implementation details for VariantMap.
+namespace detail {
+  // Allocate a unique counter value each time it's called.
+  struct VariantMapKeyCounterAllocator {
+    static size_t AllocateCounter() {
+      static size_t counter = 0;
+      counter++;
+
+      return counter;
+    }
+  };
+
+  // Type-erased version of VariantMapKey<T>
+  struct VariantMapKeyRaw {
+    // TODO: this may need to call a virtual function to support string comparisons
+    bool operator<(const VariantMapKeyRaw& other) const {
+      return key_counter_ < other.key_counter_;
+    }
+
+    // The following functions need to be virtual since we don't know the compile-time type anymore:
+
+    // Clone the key, creating a copy of the contents.
+    virtual VariantMapKeyRaw* Clone() const = 0;
+
+    // Delete a value whose runtime type is that of the non-erased key's TValue.
+    virtual void ValueDelete(void* value) const = 0;
+
+    // Clone a value whose runtime type is that of the non-erased key's TValue.
+    virtual void* ValueClone(void* value) const = 0;
+
+    // Compare one key to another (same as operator<).
+    virtual bool Compare(const VariantMapKeyRaw* other) const {
+      if (other == nullptr) {
+        return false;
+      }
+      return key_counter_ < other->key_counter_;
+    }
+
+    virtual ~VariantMapKeyRaw() {}
+
+   protected:
+    VariantMapKeyRaw()
+        : key_counter_(VariantMapKeyCounterAllocator::AllocateCounter()) {}
+    // explicit VariantMapKeyRaw(size_t counter)
+    //     : key_counter_(counter) {}
+
+    size_t GetCounter() const {
+      return key_counter_;
+    }
+
+   protected:
+    // Avoid the object slicing problem; use Clone() instead.
+    VariantMapKeyRaw(const VariantMapKeyRaw& other) = default;
+    VariantMapKeyRaw(VariantMapKeyRaw&& other) = default;
+
+   private:
+    size_t key_counter_;  // Runtime type ID. Unique each time a new type is reified.
+  };
+}  // namespace detail
+
+// The base type for keys used by the VariantMap. Users must subclass this type.
+template <typename TValue>
+struct VariantMapKey : detail::VariantMapKeyRaw {
+  // Instantiate a default value for this key. If an explicit default value was provided
+  // then that is used. Otherwise, the default value for the type TValue{} is returned.
+  TValue CreateDefaultValue() const {
+    if (default_value_ == nullptr) {
+      return TValue{};  // NOLINT [readability/braces] [4]
+    } else {
+      return TValue(*default_value_);
+    }
+  }
+
+ protected:
+  // explicit VariantMapKey(size_t counter) : detail::VariantMapKeyRaw(counter) {}
+  explicit VariantMapKey(const TValue& default_value)
+    : default_value_(std::make_shared<TValue>(default_value)) {}
+  explicit VariantMapKey(TValue&& default_value)
+    : default_value_(std::make_shared<TValue>(default_value)) {}
+  VariantMapKey() {}
+  virtual ~VariantMapKey() {}
+
+ private:
+  virtual VariantMapKeyRaw* Clone() const {
+    return new VariantMapKey<TValue>(*this);
+  }
+
+  virtual void* ValueClone(void* value) const {
+    if (value == nullptr) {
+      return nullptr;
+    }
+
+    TValue* strong_value = reinterpret_cast<TValue*>(value);
+    return new TValue(*strong_value);
+  }
+
+  virtual void ValueDelete(void* value) const {
+    if (value == nullptr) {
+      return;
+    }
+
+    // Smartly invoke the proper delete/delete[]/etc
+    const std::default_delete<TValue> deleter = std::default_delete<TValue>();
+    deleter(reinterpret_cast<TValue*>(value));
+  }
+
+  VariantMapKey(const VariantMapKey& other) = default;
+  VariantMapKey(VariantMapKey&& other) = default;
+
+  template <typename Base, template <typename TV> class TKey> friend struct VariantMap;
+
+  // Store a prototype of the key's default value, for usage with VariantMap::GetOrDefault
+  std::shared_ptr<TValue> default_value_;
+};
+
+// Implementation details for a stringified VariantMapStringKey.
+namespace detail {
+  struct VariantMapStringKeyRegistry {
+    // TODO
+  };
+}  // namespace detail
+
+// Alternative base type for all keys used by VariantMap, supports runtime strings as the name.
+template <typename TValue>
+struct VariantMapStringKey : VariantMapKey<TValue> {
+  explicit VariantMapStringKey(const char* name)
+      :   // VariantMapKey(/*std::hash<std::string>()(name)*/),
+        name_(name) {
+  }
+
+ private:
+  const char* name_;
+};
+
+// A variant map allows type-safe heteregeneous key->value mappings.
+// All possible key types must be specified at compile-time. Values may be added/removed
+// at runtime.
+template <typename Base, template <typename TV> class TKey>
+struct VariantMap {
+  // Allow users of this static interface to use the key type.
+  template <typename TValue>
+  using Key = TKey<TValue>;
+
+  // Look up the value from the key. The pointer becomes invalid if this key is overwritten/removed.
+  // A null value is returned only when the key does not exist in this map.
+  template <typename TValue>
+  const TValue* Get(const TKey<TValue>& key) const {
+    return GetValuePtr(key);
+  }
+
+  // Look up the value from the key. The pointer becomes invalid if this key is overwritten/removed.
+  // A null value is returned only when the key does not exist in this map.
+  template <typename TValue>
+  TValue* Get(const TKey<TValue>& key) {
+    return GetValuePtr(key);
+  }
+
+  // Lookup the value from the key. If it was not set in the map, return the default value.
+  // The default value is either the key's default, or TValue{} if the key doesn't have a default.
+  template <typename TValue>
+  TValue GetOrDefault(const TKey<TValue>& key) const {
+    auto* ptr = Get(key);
+    return (ptr == nullptr) ? key.CreateDefaultValue() : *ptr;
+  }
+
+ private:
+  // TODO: move to detail, or make it more generic like a ScopeGuard(function)
+  template <typename TValue>
+  struct ScopedRemove {
+    ScopedRemove(VariantMap& map, const TKey<TValue>& key) : map_(map), key_(key) {}
+    ~ScopedRemove() {
+      map_.Remove(key_);
+    }
+
+    VariantMap& map_;
+    const TKey<TValue>& key_;
+  };
+
+ public:
+  // Release the value from the key. If it was not set in the map, returns the default value.
+  // If the key was set, it is removed as a side effect.
+  template <typename TValue>
+  TValue ReleaseOrDefault(const TKey<TValue>& key) {
+    ScopedRemove<TValue> remove_on_return(*this, key);
+
+    TValue* ptr = Get(key);
+    if (ptr != nullptr) {
+      return std::move(*ptr);
+    } else {
+      TValue default_value = key.CreateDefaultValue();
+      return std::move(default_value);
+    }
+  }
+
+  // See if a value is stored for this key.
+  template <typename TValue>
+  bool Exists(const TKey<TValue>& key) const {
+    return GetKeyValueIterator(key) != storage_map_.end();
+  }
+
+  // Set a value for a given key, overwriting the previous value if any.
+  template <typename TValue>
+  void Set(const TKey<TValue>& key, const TValue& value) {
+    Remove(key);
+    storage_map_.insert({{key.Clone(), new TValue(value)}});
+  }
+
+  // Set a value for a given key, only if there was no previous value before.
+  // Returns true if the value was set, false if a previous value existed.
+  template <typename TValue>
+  bool SetIfMissing(const TKey<TValue>& key, const TValue& value) {
+    TValue* ptr = Get(key);
+    if (ptr == nullptr) {
+      Set(key, value);
+      return true;
+    }
+    return false;
+  }
+
+  // Remove the value for a given key, or a no-op if there was no previously set value.
+  template <typename TValue>
+  void Remove(const TKey<TValue>& key) {
+    StaticAssertKeyType<TValue>();
+
+    auto&& it = GetKeyValueIterator(key);
+    if (it != storage_map_.end()) {
+      key.ValueDelete(it->second);
+      delete it->first;
+      storage_map_.erase(it);
+    }
+  }
+
+  // Remove all key/value pairs.
+  void Clear() {
+    DeleteStoredValues();
+    storage_map_.clear();
+  }
+
+  // How many key/value pairs are stored in this map.
+  size_t Size() const {
+    return storage_map_.size();
+  }
+
+  // Construct an empty map.
+  explicit VariantMap() {}
+
+  template <typename ... TKeyValue>
+  explicit VariantMap(const TKeyValue& ... key_value_list) {
+    static_assert(sizeof...(TKeyValue) % 2 == 0, "Must be an even number of key/value elements");
+    InitializeParameters(key_value_list...);
+  }
+
+  // Create a new map from an existing map, copying all the key/value pairs.
+  VariantMap(const VariantMap& other) {
+    operator=(other);
+  }
+
+  // Copy the key/value pairs from the other map into this one. Existing key/values are cleared.
+  VariantMap& operator=(const VariantMap& other) {
+    if (this == &other) {
+      return *this;
+    }
+
+    Clear();
+
+    for (auto&& kv_pair : other.storage_map_) {
+      const detail::VariantMapKeyRaw* raw_key_other = kv_pair.first;
+      void* value = kv_pair.second;
+
+      detail::VariantMapKeyRaw* cloned_raw_key = raw_key_other->Clone();
+      void* cloned_value = raw_key_other->ValueClone(value);
+
+      storage_map_.insert({{ cloned_raw_key, cloned_value }});
+    }
+
+    return *this;
+  }
+
+  // Create a new map by moving an existing map into this one. The other map becomes empty.
+  VariantMap(VariantMap&& other) {
+    operator=(std::forward<VariantMap>(other));
+  }
+
+  // Move the existing map's key/value pairs into this one. The other map becomes empty.
+  VariantMap& operator=(VariantMap&& other) {
+    if (this != &other) {
+      Clear();
+      storage_map_.swap(other.storage_map_);
+      other.storage_map_.clear();
+    }
+    return *this;
+  }
+
+  ~VariantMap() {
+    DeleteStoredValues();
+  }
+
+ private:
+  void InitializeParameters() {}
+
+  template <typename TK, typename TValue, typename ... Rest>
+  void InitializeParameters(const TK& key, const TValue& value, const Rest& ... rest) {
+    static_assert(
+        std::is_same<TK, TKey<TValue>>::value, "The 0th/2nd/4th/etc parameters must be a key");
+
+    const TKey<TValue>& key_refined = key;
+
+    Set(key_refined, value);
+    InitializeParameters(rest...);
+  }
+
+  // Custom key comparator for std::map, needed since we are storing raw pointers as the keys.
+  struct KeyComparator {
+    bool operator()(const detail::VariantMapKeyRaw* lhs,
+                    const detail::VariantMapKeyRaw* rhs) const {
+      if (lhs == nullptr) {
+        return lhs != rhs;
+      }
+
+      return lhs->Compare(rhs);
+    }
+  };
+
+  // Map of key pointers to value pointers. Pointers are never null.
+  using StorageMap = std::map<const detail::VariantMapKeyRaw*, void*, KeyComparator>;
+
+  template <typename TValue>
+  typename StorageMap::iterator GetKeyValueIterator(const TKey<TValue>& key) {
+    StaticAssertKeyType<TValue>();
+
+    const TKey<TValue>* key_ptr = &key;
+    const detail::VariantMapKeyRaw* raw_ptr = key_ptr;
+    return storage_map_.find(raw_ptr);
+  }
+
+  template <typename TValue>
+  typename StorageMap::const_iterator GetKeyValueIterator(const TKey<TValue>& key) const {
+    StaticAssertKeyType<TValue>();
+
+    const TKey<TValue>* key_ptr = &key;
+    const detail::VariantMapKeyRaw* raw_ptr = key_ptr;
+    return storage_map_.find(raw_ptr);
+  }
+
+  template <typename TValue>
+  TValue* GetValuePtr(const TKey<TValue>& key) {
+    return const_cast<TValue*>(GetValueConstPtr(key));
+  }
+
+  template <typename TValue>
+  const TValue* GetValuePtr(const TKey<TValue>& key) const {
+    return GetValueConstPtr(key);
+  }
+
+  template <typename TValue>
+  const TValue* GetValueConstPtr(const TKey<TValue>& key) const {
+    auto&& it = GetKeyValueIterator(key);
+    if (it == storage_map_.end()) {
+      return nullptr;
+    }
+
+    return reinterpret_cast<const TValue*>(it->second);
+  }
+
+  template <typename TValue>
+  static void StaticAssertKeyType() {
+    static_assert(std::is_base_of<VariantMapKey<TValue>, TKey<TValue>>::value,
+                  "The provided key type (TKey) must be a subclass of VariantMapKey");
+  }
+
+  void DeleteStoredValues() {
+    for (auto&& kv_pair : storage_map_) {
+      kv_pair.first->ValueDelete(kv_pair.second);
+      delete kv_pair.first;
+    }
+  }
+
+  StorageMap storage_map_;
+};
+
+}  // namespace art
+
+#endif  // ART_RUNTIME_BASE_VARIANT_MAP_H_