• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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_LIBARTBASE_BASE_VARIANT_MAP_H_
18 #define ART_LIBARTBASE_BASE_VARIANT_MAP_H_
19 
20 #include <memory.h>
21 #include <map>
22 #include <type_traits>
23 #include <utility>
24 
25 #include "android-base/logging.h"
26 #include "stl_util_identity.h"
27 
28 namespace art {
29 
30 //
31 // A variant map is a heterogenous, type safe key->value map. It allows
32 // for multiple different value types to be stored dynamically in the same map.
33 //
34 // It provides the following interface in a nutshell:
35 //
36 // struct VariantMap {
37 //   template <typename TValue>
38 //   TValue* Get(Key<T> key);  // null if the value was never set, otherwise the value.
39 //
40 //   template <typename TValue>
41 //   void Set(Key<T> key, TValue value);
42 // };
43 //
44 // Since the key is strongly typed at compile-time, it is impossible to accidentally
45 // read/write a value with a different type than the key at either compile-time or run-time.
46 //
47 // Do not use VariantMap/VariantMapKey directly. Instead subclass each of them and use
48 // the subclass, for example:
49 //
50 // template <typename TValue>
51 // struct FruitMapKey : VariantMapKey<TValue> {
52 //   FruitMapKey() {}
53 // };
54 //
55 // struct FruitMap : VariantMap<FruitMap, FruitMapKey> {
56 //   // This 'using' line is necessary to inherit the variadic constructor.
57 //   using VariantMap<FruitMap, FruitMapKey>::VariantMap;
58 //
59 //   // Make the next '4' usages of Key slightly shorter to type.
60 //   template <typename TValue>
61 //   using Key = FruitMapKey<TValue>;
62 //
63 //   static const Key<int> Apple;
64 //   static const Key<double> Orange;
65 //   static const Key<std::string> Banana;
66 // };
67 //
68 // const FruitMap::Key<int> FruitMap::Apple;
69 // const FruitMap::Key<double> FruitMap::Orange;
70 // const FruitMap::Key<std::string> Banana;
71 //
72 // See variant_map_test.cc for more examples.
73 //
74 
75 // Implementation details for VariantMap.
76 namespace detail {
77 // Allocate a unique counter value each time it's called.
78 struct VariantMapKeyCounterAllocator {
AllocateCounterVariantMapKeyCounterAllocator79   static size_t AllocateCounter() {
80     static size_t counter = 0;
81     counter++;
82 
83     return counter;
84   }
85 };
86 
87 // Type-erased version of VariantMapKey<T>
88 struct VariantMapKeyRaw {
89   // TODO: this may need to call a virtual function to support string comparisons
90   bool operator<(const VariantMapKeyRaw& other) const {
91     return key_counter_ < other.key_counter_;
92   }
93 
94   // The following functions need to be virtual since we don't know the compile-time type anymore:
95 
96   // Clone the key, creating a copy of the contents.
97   virtual VariantMapKeyRaw* Clone() const = 0;
98 
99   // Delete a value whose runtime type is that of the non-erased key's TValue.
100   virtual void ValueDelete(void* value) const = 0;
101 
102   // Clone a value whose runtime type is that of the non-erased key's TValue.
103   virtual void* ValueClone(void* value) const = 0;
104 
105   // Compare one key to another (same as operator<).
CompareVariantMapKeyRaw106   virtual bool Compare(const VariantMapKeyRaw* other) const {
107     if (other == nullptr) {
108       return false;
109     }
110     return key_counter_ < other->key_counter_;
111   }
112 
~VariantMapKeyRawVariantMapKeyRaw113   virtual ~VariantMapKeyRaw() {}
114 
115  protected:
VariantMapKeyRawVariantMapKeyRaw116   VariantMapKeyRaw()
117       : key_counter_(VariantMapKeyCounterAllocator::AllocateCounter()) {}
118   // explicit VariantMapKeyRaw(size_t counter)
119   //     : key_counter_(counter) {}
120 
GetCounterVariantMapKeyRaw121   size_t GetCounter() const {
122     return key_counter_;
123   }
124 
125  protected:
126   // Avoid the object slicing problem; use Clone() instead.
127   VariantMapKeyRaw(const VariantMapKeyRaw&) = default;
128   VariantMapKeyRaw(VariantMapKeyRaw&&) noexcept = default;
129 
130  private:
131   size_t key_counter_;  // Runtime type ID. Unique each time a new type is reified.
132 };
133 }  // namespace detail
134 
135 // The base type for keys used by the VariantMap. Users must subclass this type.
136 template <typename TValue>
137 struct VariantMapKey : detail::VariantMapKeyRaw {
138   // Instantiate a default value for this key. If an explicit default value was provided
139   // then that is used. Otherwise, the default value for the type TValue{} is returned.
CreateDefaultValueVariantMapKey140   TValue CreateDefaultValue() const {
141     if (default_value_ == nullptr) {
142       return TValue{};
143     } else {
144       return TValue(*default_value_);
145     }
146   }
147 
148  protected:
149   // explicit VariantMapKey(size_t counter) : detail::VariantMapKeyRaw(counter) {}
VariantMapKeyVariantMapKey150   explicit VariantMapKey(const TValue& default_value)
151     : default_value_(std::make_shared<TValue>(default_value)) {}
VariantMapKeyVariantMapKey152   explicit VariantMapKey(TValue&& default_value)
153     : default_value_(std::make_shared<TValue>(default_value)) {}
VariantMapKeyVariantMapKey154   VariantMapKey() {}
~VariantMapKeyVariantMapKey155   virtual ~VariantMapKey() {}
156 
157  private:
CloneVariantMapKey158   virtual VariantMapKeyRaw* Clone() const {
159     return new VariantMapKey<TValue>(*this);
160   }
161 
ValueCloneVariantMapKey162   virtual void* ValueClone(void* value) const {
163     if (value == nullptr) {
164       return nullptr;
165     }
166 
167     TValue* strong_value = reinterpret_cast<TValue*>(value);
168     return new TValue(*strong_value);
169   }
170 
ValueDeleteVariantMapKey171   virtual void ValueDelete(void* value) const {
172     if (value == nullptr) {
173       return;
174     }
175 
176     // Smartly invoke the proper delete/delete[]/etc
177     const std::default_delete<TValue> deleter = std::default_delete<TValue>();
178     deleter(reinterpret_cast<TValue*>(value));
179   }
180 
181   VariantMapKey(const VariantMapKey&) = default;
182   VariantMapKey(VariantMapKey&&) noexcept = default;
183 
184   template <typename Base, template <typename TV> class TKey> friend struct VariantMap;
185 
186   // Store a prototype of the key's default value, for usage with VariantMap::GetOrDefault
187   std::shared_ptr<TValue> default_value_;
188 };
189 
190 // Implementation details for a stringified VariantMapStringKey.
191 namespace detail {
192 struct VariantMapStringKeyRegistry {
193   // TODO
194 };
195 }  // namespace detail
196 
197 // Alternative base type for all keys used by VariantMap, supports runtime strings as the name.
198 template <typename TValue>
199 struct VariantMapStringKey : VariantMapKey<TValue> {
VariantMapStringKeyVariantMapStringKey200   explicit VariantMapStringKey(const char* name)
201       :   // VariantMapKey(/*std::hash<std::string>()(name)*/),
202         name_(name) {
203   }
204 
205  private:
206   const char* name_;
207 };
208 
209 // A variant map allows type-safe heteregeneous key->value mappings.
210 // All possible key types must be specified at compile-time. Values may be added/removed
211 // at runtime.
212 template <typename Base, template <typename TV> class TKey>
213 struct VariantMap {
214   // Allow users of this static interface to use the key type.
215   template <typename TValue>
216   using Key = TKey<TValue>;
217 
218   // Look up the value from the key. The pointer becomes invalid if this key is overwritten/removed.
219   // A null value is returned only when the key does not exist in this map.
220   template <typename TValue>
GetVariantMap221   const TValue* Get(const TKey<TValue>& key) const {
222     return GetValuePtr(key);
223   }
224 
225   // Look up the value from the key. The pointer becomes invalid if this key is overwritten/removed.
226   // A null value is returned only when the key does not exist in this map.
227   template <typename TValue>
GetVariantMap228   TValue* Get(const TKey<TValue>& key) {
229     return GetValuePtr(key);
230   }
231 
232   // Look up the value from the key and return the value wrapped in a std::optional. If it was not
233   // set in the map, return an empty std::optional.
234   template <typename TValue>
GetOptionalVariantMap235   std::optional<TValue> GetOptional(const TKey<TValue>& key) const {
236     auto* ptr = Get(key);
237     return (ptr == nullptr) ? std::optional<TValue>{} : std::make_optional(*ptr);
238   }
239 
240   // Lookup the value from the key. If it was not set in the map, return the default value.
241   // The default value is either the key's default, or TValue{} if the key doesn't have a default.
242   template <typename TValue>
GetOrDefaultVariantMap243   TValue GetOrDefault(const TKey<TValue>& key) const {
244     auto* ptr = Get(key);
245     return (ptr == nullptr) ? key.CreateDefaultValue() : *ptr;
246   }
247 
248   template <typename T, typename U>
AssignIfExistsVariantMap249   void AssignIfExists(const TKey<T>& key, U* out) {
250     DCHECK(out != nullptr);
251     if (Exists(key)) {
252       *out = std::move(*Get(key));
253     }
254   }
255 
256  private:
257   // TODO: move to detail, or make it more generic like a ScopeGuard(function)
258   template <typename TValue>
259   struct ScopedRemove {
ScopedRemoveVariantMap::ScopedRemove260     ScopedRemove(VariantMap& map, const TKey<TValue>& key) : map_(map), key_(key) {}
~ScopedRemoveVariantMap::ScopedRemove261     ~ScopedRemove() {
262       map_.Remove(key_);
263     }
264 
265     VariantMap& map_;
266     const TKey<TValue>& key_;
267   };
268 
269  public:
270   // Release the value from the key. If it was not set in the map, returns the default value.
271   // If the key was set, it is removed as a side effect.
272   template <typename TValue>
ReleaseOrDefaultVariantMap273   TValue ReleaseOrDefault(const TKey<TValue>& key) {
274     ScopedRemove<TValue> remove_on_return(*this, key);
275 
276     TValue* ptr = Get(key);
277     if (ptr != nullptr) {
278       return std::move(*ptr);
279     } else {
280       return key.CreateDefaultValue();
281     }
282   }
283 
284   // See if a value is stored for this key.
285   template <typename TValue>
ExistsVariantMap286   bool Exists(const TKey<TValue>& key) const {
287     return GetKeyValueIterator(key) != storage_map_.end();
288   }
289 
290   // Set a value for a given key, overwriting the previous value if any.
291   // Note: Omit the `value` from TValue type deduction, deduce only from the `key` argument.
292   template <typename TValue>
SetVariantMap293   void Set(const TKey<TValue>& key, const typename Identity<TValue>::type& value) {
294     // Clone the value first, to protect against &value == GetValuePtr(key).
295     auto* new_value = new TValue(value);
296 
297     Remove(key);
298     bool inserted = storage_map_.insert({key.Clone(), new_value}).second;
299     DCHECK(inserted);  // ensure key.Clone() does not leak memory.
300   }
301 
302   // Set a value for a given key, only if there was no previous value before.
303   // Returns true if the value was set, false if a previous value existed.
304   // Note: Omit the `value` from TValue type deduction, deduce only from the `key` argument.
305   template <typename TValue>
SetIfMissingVariantMap306   bool SetIfMissing(const TKey<TValue>& key, const typename Identity<TValue>::type& value) {
307     TValue* ptr = Get(key);
308     if (ptr == nullptr) {
309       Set(key, value);
310       return true;
311     }
312     return false;
313   }
314 
315   // Remove the value for a given key, or a no-op if there was no previously set value.
316   template <typename TValue>
RemoveVariantMap317   void Remove(const TKey<TValue>& key) {
318     StaticAssertKeyType<TValue>();
319 
320     auto&& it = GetKeyValueIterator(key);
321     if (it != storage_map_.end()) {
322       key.ValueDelete(it->second);
323       delete it->first;
324       storage_map_.erase(it);
325     }
326   }
327 
328   // Remove all key/value pairs.
ClearVariantMap329   void Clear() {
330     DeleteStoredValues();
331     storage_map_.clear();
332   }
333 
334   // How many key/value pairs are stored in this map.
SizeVariantMap335   size_t Size() const {
336     return storage_map_.size();
337   }
338 
339   // Construct an empty map.
VariantMapVariantMap340   VariantMap() {}
341 
342   template <typename ... TKeyValue>
VariantMapVariantMap343   explicit VariantMap(const TKeyValue& ... key_value_list) {
344     static_assert(sizeof...(TKeyValue) % 2 == 0, "Must be an even number of key/value elements");
345     InitializeParameters(key_value_list...);
346   }
347 
348   // Create a new map from an existing map, copying all the key/value pairs.
VariantMapVariantMap349   VariantMap(const VariantMap& other) {
350     operator=(other);
351   }
352 
353   // Copy the key/value pairs from the other map into this one. Existing key/values are cleared.
354   VariantMap& operator=(const VariantMap& other) {
355     if (this == &other) {
356       return *this;
357     }
358 
359     Clear();
360 
361     for (auto&& kv_pair : other.storage_map_) {
362       const detail::VariantMapKeyRaw* raw_key_other = kv_pair.first;
363       void* value = kv_pair.second;
364 
365       detail::VariantMapKeyRaw* cloned_raw_key = raw_key_other->Clone();
366       void* cloned_value = raw_key_other->ValueClone(value);
367 
368       storage_map_.insert({{ cloned_raw_key, cloned_value }});
369     }
370 
371     return *this;
372   }
373 
374   // Create a new map by moving an existing map into this one. The other map becomes empty.
VariantMapVariantMap375   VariantMap(VariantMap&& other) noexcept {
376     operator=(std::forward<VariantMap>(other));
377   }
378 
379   // Move the existing map's key/value pairs into this one. The other map becomes empty.
380   VariantMap& operator=(VariantMap&& other) noexcept {
381     if (this != &other) {
382       Clear();
383       storage_map_.swap(other.storage_map_);
384       other.storage_map_.clear();
385     }
386     return *this;
387   }
388 
~VariantMapVariantMap389   ~VariantMap() {
390     DeleteStoredValues();
391   }
392 
393  private:
InitializeParametersVariantMap394   void InitializeParameters() {}
395 
396   template <typename TK, typename TValue, typename ... Rest>
InitializeParametersVariantMap397   void InitializeParameters(const TK& key, const TValue& value, const Rest& ... rest) {
398     static_assert(std::is_same_v<TK, TKey<TValue>>, "The 0th/2nd/4th/etc parameters must be a key");
399 
400     const TKey<TValue>& key_refined = key;
401 
402     Set(key_refined, value);
403     InitializeParameters(rest...);
404   }
405 
406   // Custom key comparator for std::map, needed since we are storing raw pointers as the keys.
407   struct KeyComparator {
operatorVariantMap::KeyComparator408     bool operator()(const detail::VariantMapKeyRaw* lhs,
409                     const detail::VariantMapKeyRaw* rhs) const {
410       if (lhs == nullptr) {
411         return lhs != rhs;
412       }
413 
414       return lhs->Compare(rhs);
415     }
416   };
417 
418   // Map of key pointers to value pointers. Pointers are never null.
419   using StorageMap = std::map<const detail::VariantMapKeyRaw*, void*, KeyComparator>;
420 
421   template <typename TValue>
GetKeyValueIteratorVariantMap422   typename StorageMap::iterator GetKeyValueIterator(const TKey<TValue>& key) {
423     StaticAssertKeyType<TValue>();
424 
425     const TKey<TValue>* key_ptr = &key;
426     const detail::VariantMapKeyRaw* raw_ptr = key_ptr;
427     return storage_map_.find(raw_ptr);
428   }
429 
430   template <typename TValue>
GetKeyValueIteratorVariantMap431   typename StorageMap::const_iterator GetKeyValueIterator(const TKey<TValue>& key) const {
432     StaticAssertKeyType<TValue>();
433 
434     const TKey<TValue>* key_ptr = &key;
435     const detail::VariantMapKeyRaw* raw_ptr = key_ptr;
436     return storage_map_.find(raw_ptr);
437   }
438 
439   template <typename TValue>
GetValuePtrVariantMap440   TValue* GetValuePtr(const TKey<TValue>& key) {
441     return const_cast<TValue*>(GetValueConstPtr(key));
442   }
443 
444   template <typename TValue>
GetValuePtrVariantMap445   const TValue* GetValuePtr(const TKey<TValue>& key) const {
446     return GetValueConstPtr(key);
447   }
448 
449   template <typename TValue>
GetValueConstPtrVariantMap450   const TValue* GetValueConstPtr(const TKey<TValue>& key) const {
451     auto&& it = GetKeyValueIterator(key);
452     if (it == storage_map_.end()) {
453       return nullptr;
454     }
455 
456     return reinterpret_cast<const TValue*>(it->second);
457   }
458 
459   template <typename TValue>
StaticAssertKeyTypeVariantMap460   static void StaticAssertKeyType() {
461     static_assert(std::is_base_of_v<VariantMapKey<TValue>, TKey<TValue>>,
462                   "The provided key type (TKey) must be a subclass of VariantMapKey");
463   }
464 
DeleteStoredValuesVariantMap465   void DeleteStoredValues() {
466     for (auto&& kv_pair : storage_map_) {
467       kv_pair.first->ValueDelete(kv_pair.second);
468       delete kv_pair.first;
469     }
470   }
471 
472   StorageMap storage_map_;
473 };
474 
475 }  // namespace art
476 
477 #endif  // ART_LIBARTBASE_BASE_VARIANT_MAP_H_
478