1 /* 2 * Copyright (C) 2015 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef ART_RUNTIME_BASE_VARIANT_MAP_H_ 18 #define ART_RUNTIME_BASE_VARIANT_MAP_H_ 19 20 #include <memory.h> 21 #include <map> 22 #include <type_traits> 23 #include <utility> 24 25 #include "base/stl_util.h" 26 27 namespace art { 28 29 // 30 // A variant map is a heterogenous, type safe key->value map. It allows 31 // for multiple different value types to be stored dynamically in the same map. 32 // 33 // It provides the following interface in a nutshell: 34 // 35 // struct VariantMap { 36 // template <typename TValue> 37 // TValue* Get(Key<T> key); // null if the value was never set, otherwise the value. 38 // 39 // template <typename TValue> 40 // void Set(Key<T> key, TValue value); 41 // }; 42 // 43 // Since the key is strongly typed at compile-time, it is impossible to accidentally 44 // read/write a value with a different type than the key at either compile-time or run-time. 45 // 46 // Do not use VariantMap/VariantMapKey directly. Instead subclass each of them and use 47 // the subclass, for example: 48 // 49 // template <typename TValue> 50 // struct FruitMapKey : VariantMapKey<TValue> { 51 // FruitMapKey() {} 52 // }; 53 // 54 // struct FruitMap : VariantMap<FruitMap, FruitMapKey> { 55 // // This 'using' line is necessary to inherit the variadic constructor. 56 // using VariantMap<FruitMap, FruitMapKey>::VariantMap; 57 // 58 // // Make the next '4' usages of Key slightly shorter to type. 59 // template <typename TValue> 60 // using Key = FruitMapKey<TValue>; 61 // 62 // static const Key<int> Apple; 63 // static const Key<double> Orange; 64 // static const Key<std::string> Banana; 65 // }; 66 // 67 // const FruitMap::Key<int> FruitMap::Apple; 68 // const FruitMap::Key<double> FruitMap::Orange; 69 // const FruitMap::Key<std::string> Banana; 70 // 71 // See variant_map_test.cc for more examples. 72 // 73 74 // Implementation details for VariantMap. 75 namespace detail { 76 // Allocate a unique counter value each time it's called. 77 struct VariantMapKeyCounterAllocator { AllocateCounterVariantMapKeyCounterAllocator78 static size_t AllocateCounter() { 79 static size_t counter = 0; 80 counter++; 81 82 return counter; 83 } 84 }; 85 86 // Type-erased version of VariantMapKey<T> 87 struct VariantMapKeyRaw { 88 // TODO: this may need to call a virtual function to support string comparisons 89 bool operator<(const VariantMapKeyRaw& other) const { 90 return key_counter_ < other.key_counter_; 91 } 92 93 // The following functions need to be virtual since we don't know the compile-time type anymore: 94 95 // Clone the key, creating a copy of the contents. 96 virtual VariantMapKeyRaw* Clone() const = 0; 97 98 // Delete a value whose runtime type is that of the non-erased key's TValue. 99 virtual void ValueDelete(void* value) const = 0; 100 101 // Clone a value whose runtime type is that of the non-erased key's TValue. 102 virtual void* ValueClone(void* value) const = 0; 103 104 // Compare one key to another (same as operator<). CompareVariantMapKeyRaw105 virtual bool Compare(const VariantMapKeyRaw* other) const { 106 if (other == nullptr) { 107 return false; 108 } 109 return key_counter_ < other->key_counter_; 110 } 111 ~VariantMapKeyRawVariantMapKeyRaw112 virtual ~VariantMapKeyRaw() {} 113 114 protected: VariantMapKeyRawVariantMapKeyRaw115 VariantMapKeyRaw() 116 : key_counter_(VariantMapKeyCounterAllocator::AllocateCounter()) {} 117 // explicit VariantMapKeyRaw(size_t counter) 118 // : key_counter_(counter) {} 119 GetCounterVariantMapKeyRaw120 size_t GetCounter() const { 121 return key_counter_; 122 } 123 124 protected: 125 // Avoid the object slicing problem; use Clone() instead. 126 VariantMapKeyRaw(const VariantMapKeyRaw&) = default; 127 VariantMapKeyRaw(VariantMapKeyRaw&&) = default; 128 129 private: 130 size_t key_counter_; // Runtime type ID. Unique each time a new type is reified. 131 }; 132 } // namespace detail 133 134 // The base type for keys used by the VariantMap. Users must subclass this type. 135 template <typename TValue> 136 struct VariantMapKey : detail::VariantMapKeyRaw { 137 // Instantiate a default value for this key. If an explicit default value was provided 138 // then that is used. Otherwise, the default value for the type TValue{} is returned. CreateDefaultValueVariantMapKey139 TValue CreateDefaultValue() const { 140 if (default_value_ == nullptr) { 141 return TValue{}; // NOLINT [readability/braces] [4] 142 } else { 143 return TValue(*default_value_); 144 } 145 } 146 147 protected: 148 // explicit VariantMapKey(size_t counter) : detail::VariantMapKeyRaw(counter) {} VariantMapKeyVariantMapKey149 explicit VariantMapKey(const TValue& default_value) 150 : default_value_(std::make_shared<TValue>(default_value)) {} VariantMapKeyVariantMapKey151 explicit VariantMapKey(TValue&& default_value) 152 : default_value_(std::make_shared<TValue>(default_value)) {} VariantMapKeyVariantMapKey153 VariantMapKey() {} ~VariantMapKeyVariantMapKey154 virtual ~VariantMapKey() {} 155 156 private: CloneVariantMapKey157 virtual VariantMapKeyRaw* Clone() const { 158 return new VariantMapKey<TValue>(*this); 159 } 160 ValueCloneVariantMapKey161 virtual void* ValueClone(void* value) const { 162 if (value == nullptr) { 163 return nullptr; 164 } 165 166 TValue* strong_value = reinterpret_cast<TValue*>(value); 167 return new TValue(*strong_value); 168 } 169 ValueDeleteVariantMapKey170 virtual void ValueDelete(void* value) const { 171 if (value == nullptr) { 172 return; 173 } 174 175 // Smartly invoke the proper delete/delete[]/etc 176 const std::default_delete<TValue> deleter = std::default_delete<TValue>(); 177 deleter(reinterpret_cast<TValue*>(value)); 178 } 179 180 VariantMapKey(const VariantMapKey&) = default; 181 VariantMapKey(VariantMapKey&&) = default; 182 183 template <typename Base, template <typename TV> class TKey> friend struct VariantMap; 184 185 // Store a prototype of the key's default value, for usage with VariantMap::GetOrDefault 186 std::shared_ptr<TValue> default_value_; 187 }; 188 189 // Implementation details for a stringified VariantMapStringKey. 190 namespace detail { 191 struct VariantMapStringKeyRegistry { 192 // TODO 193 }; 194 } // namespace detail 195 196 // Alternative base type for all keys used by VariantMap, supports runtime strings as the name. 197 template <typename TValue> 198 struct VariantMapStringKey : VariantMapKey<TValue> { VariantMapStringKeyVariantMapStringKey199 explicit VariantMapStringKey(const char* name) 200 : // VariantMapKey(/*std::hash<std::string>()(name)*/), 201 name_(name) { 202 } 203 204 private: 205 const char* name_; 206 }; 207 208 // A variant map allows type-safe heteregeneous key->value mappings. 209 // All possible key types must be specified at compile-time. Values may be added/removed 210 // at runtime. 211 template <typename Base, template <typename TV> class TKey> 212 struct VariantMap { 213 // Allow users of this static interface to use the key type. 214 template <typename TValue> 215 using Key = TKey<TValue>; 216 217 // Look up the value from the key. The pointer becomes invalid if this key is overwritten/removed. 218 // A null value is returned only when the key does not exist in this map. 219 template <typename TValue> GetVariantMap220 const TValue* Get(const TKey<TValue>& key) const { 221 return GetValuePtr(key); 222 } 223 224 // Look up the value from the key. The pointer becomes invalid if this key is overwritten/removed. 225 // A null value is returned only when the key does not exist in this map. 226 template <typename TValue> GetVariantMap227 TValue* Get(const TKey<TValue>& key) { 228 return GetValuePtr(key); 229 } 230 231 // Lookup the value from the key. If it was not set in the map, return the default value. 232 // The default value is either the key's default, or TValue{} if the key doesn't have a default. 233 template <typename TValue> GetOrDefaultVariantMap234 TValue GetOrDefault(const TKey<TValue>& key) const { 235 auto* ptr = Get(key); 236 return (ptr == nullptr) ? key.CreateDefaultValue() : *ptr; 237 } 238 239 private: 240 // TODO: move to detail, or make it more generic like a ScopeGuard(function) 241 template <typename TValue> 242 struct ScopedRemove { ScopedRemoveVariantMap::ScopedRemove243 ScopedRemove(VariantMap& map, const TKey<TValue>& key) : map_(map), key_(key) {} ~ScopedRemoveVariantMap::ScopedRemove244 ~ScopedRemove() { 245 map_.Remove(key_); 246 } 247 248 VariantMap& map_; 249 const TKey<TValue>& key_; 250 }; 251 252 public: 253 // Release the value from the key. If it was not set in the map, returns the default value. 254 // If the key was set, it is removed as a side effect. 255 template <typename TValue> ReleaseOrDefaultVariantMap256 TValue ReleaseOrDefault(const TKey<TValue>& key) { 257 ScopedRemove<TValue> remove_on_return(*this, key); 258 259 TValue* ptr = Get(key); 260 if (ptr != nullptr) { 261 return std::move(*ptr); 262 } else { 263 return key.CreateDefaultValue(); 264 } 265 } 266 267 // See if a value is stored for this key. 268 template <typename TValue> ExistsVariantMap269 bool Exists(const TKey<TValue>& key) const { 270 return GetKeyValueIterator(key) != storage_map_.end(); 271 } 272 273 // Set a value for a given key, overwriting the previous value if any. 274 // Note: Omit the `value` from TValue type deduction, deduce only from the `key` argument. 275 template <typename TValue> SetVariantMap276 void Set(const TKey<TValue>& key, const typename Identity<TValue>::type& value) { 277 // Clone the value first, to protect against &value == GetValuePtr(key). 278 auto* new_value = new TValue(value); 279 280 Remove(key); 281 storage_map_.insert({{key.Clone(), new_value}}); 282 } 283 284 // Set a value for a given key, only if there was no previous value before. 285 // Returns true if the value was set, false if a previous value existed. 286 // Note: Omit the `value` from TValue type deduction, deduce only from the `key` argument. 287 template <typename TValue> SetIfMissingVariantMap288 bool SetIfMissing(const TKey<TValue>& key, const typename Identity<TValue>::type& value) { 289 TValue* ptr = Get(key); 290 if (ptr == nullptr) { 291 Set(key, value); 292 return true; 293 } 294 return false; 295 } 296 297 // Remove the value for a given key, or a no-op if there was no previously set value. 298 template <typename TValue> RemoveVariantMap299 void Remove(const TKey<TValue>& key) { 300 StaticAssertKeyType<TValue>(); 301 302 auto&& it = GetKeyValueIterator(key); 303 if (it != storage_map_.end()) { 304 key.ValueDelete(it->second); 305 delete it->first; 306 storage_map_.erase(it); 307 } 308 } 309 310 // Remove all key/value pairs. ClearVariantMap311 void Clear() { 312 DeleteStoredValues(); 313 storage_map_.clear(); 314 } 315 316 // How many key/value pairs are stored in this map. SizeVariantMap317 size_t Size() const { 318 return storage_map_.size(); 319 } 320 321 // Construct an empty map. VariantMapVariantMap322 explicit VariantMap() {} 323 324 template <typename ... TKeyValue> VariantMapVariantMap325 explicit VariantMap(const TKeyValue& ... key_value_list) { 326 static_assert(sizeof...(TKeyValue) % 2 == 0, "Must be an even number of key/value elements"); 327 InitializeParameters(key_value_list...); 328 } 329 330 // Create a new map from an existing map, copying all the key/value pairs. VariantMapVariantMap331 VariantMap(const VariantMap& other) { 332 operator=(other); 333 } 334 335 // Copy the key/value pairs from the other map into this one. Existing key/values are cleared. 336 VariantMap& operator=(const VariantMap& other) { 337 if (this == &other) { 338 return *this; 339 } 340 341 Clear(); 342 343 for (auto&& kv_pair : other.storage_map_) { 344 const detail::VariantMapKeyRaw* raw_key_other = kv_pair.first; 345 void* value = kv_pair.second; 346 347 detail::VariantMapKeyRaw* cloned_raw_key = raw_key_other->Clone(); 348 void* cloned_value = raw_key_other->ValueClone(value); 349 350 storage_map_.insert({{ cloned_raw_key, cloned_value }}); 351 } 352 353 return *this; 354 } 355 356 // Create a new map by moving an existing map into this one. The other map becomes empty. VariantMapVariantMap357 VariantMap(VariantMap&& other) { 358 operator=(std::forward<VariantMap>(other)); 359 } 360 361 // Move the existing map's key/value pairs into this one. The other map becomes empty. 362 VariantMap& operator=(VariantMap&& other) { 363 if (this != &other) { 364 Clear(); 365 storage_map_.swap(other.storage_map_); 366 other.storage_map_.clear(); 367 } 368 return *this; 369 } 370 ~VariantMapVariantMap371 ~VariantMap() { 372 DeleteStoredValues(); 373 } 374 375 private: InitializeParametersVariantMap376 void InitializeParameters() {} 377 378 template <typename TK, typename TValue, typename ... Rest> InitializeParametersVariantMap379 void InitializeParameters(const TK& key, const TValue& value, const Rest& ... rest) { 380 static_assert( 381 std::is_same<TK, TKey<TValue>>::value, "The 0th/2nd/4th/etc parameters must be a key"); 382 383 const TKey<TValue>& key_refined = key; 384 385 Set(key_refined, value); 386 InitializeParameters(rest...); 387 } 388 389 // Custom key comparator for std::map, needed since we are storing raw pointers as the keys. 390 struct KeyComparator { operatorVariantMap::KeyComparator391 bool operator()(const detail::VariantMapKeyRaw* lhs, 392 const detail::VariantMapKeyRaw* rhs) const { 393 if (lhs == nullptr) { 394 return lhs != rhs; 395 } 396 397 return lhs->Compare(rhs); 398 } 399 }; 400 401 // Map of key pointers to value pointers. Pointers are never null. 402 using StorageMap = std::map<const detail::VariantMapKeyRaw*, void*, KeyComparator>; 403 404 template <typename TValue> GetKeyValueIteratorVariantMap405 typename StorageMap::iterator GetKeyValueIterator(const TKey<TValue>& key) { 406 StaticAssertKeyType<TValue>(); 407 408 const TKey<TValue>* key_ptr = &key; 409 const detail::VariantMapKeyRaw* raw_ptr = key_ptr; 410 return storage_map_.find(raw_ptr); 411 } 412 413 template <typename TValue> GetKeyValueIteratorVariantMap414 typename StorageMap::const_iterator GetKeyValueIterator(const TKey<TValue>& key) const { 415 StaticAssertKeyType<TValue>(); 416 417 const TKey<TValue>* key_ptr = &key; 418 const detail::VariantMapKeyRaw* raw_ptr = key_ptr; 419 return storage_map_.find(raw_ptr); 420 } 421 422 template <typename TValue> GetValuePtrVariantMap423 TValue* GetValuePtr(const TKey<TValue>& key) { 424 return const_cast<TValue*>(GetValueConstPtr(key)); 425 } 426 427 template <typename TValue> GetValuePtrVariantMap428 const TValue* GetValuePtr(const TKey<TValue>& key) const { 429 return GetValueConstPtr(key); 430 } 431 432 template <typename TValue> GetValueConstPtrVariantMap433 const TValue* GetValueConstPtr(const TKey<TValue>& key) const { 434 auto&& it = GetKeyValueIterator(key); 435 if (it == storage_map_.end()) { 436 return nullptr; 437 } 438 439 return reinterpret_cast<const TValue*>(it->second); 440 } 441 442 template <typename TValue> StaticAssertKeyTypeVariantMap443 static void StaticAssertKeyType() { 444 static_assert(std::is_base_of<VariantMapKey<TValue>, TKey<TValue>>::value, 445 "The provided key type (TKey) must be a subclass of VariantMapKey"); 446 } 447 DeleteStoredValuesVariantMap448 void DeleteStoredValues() { 449 for (auto&& kv_pair : storage_map_) { 450 kv_pair.first->ValueDelete(kv_pair.second); 451 delete kv_pair.first; 452 } 453 } 454 455 StorageMap storage_map_; 456 }; 457 458 } // namespace art 459 460 #endif // ART_RUNTIME_BASE_VARIANT_MAP_H_ 461