blob: 8d416e4b79c6d680391468067f70fa0e3a231d4e [file] [log] [blame]
Martin Stjernholmc15e7e42020-12-02 22:50:53 +00001/*
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
28namespace 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.
76namespace detail {
77// Allocate a unique counter value each time it's called.
78struct VariantMapKeyCounterAllocator {
79 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>
88struct 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<).
106 virtual bool Compare(const VariantMapKeyRaw* other) const {
107 if (other == nullptr) {
108 return false;
109 }
110 return key_counter_ < other->key_counter_;
111 }
112
113 virtual ~VariantMapKeyRaw() {}
114
115 protected:
116 VariantMapKeyRaw()
117 : key_counter_(VariantMapKeyCounterAllocator::AllocateCounter()) {}
118 // explicit VariantMapKeyRaw(size_t counter)
119 // : key_counter_(counter) {}
120
121 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;
android-t13d2c5b22022-10-12 13:43:18 +0800128 VariantMapKeyRaw(VariantMapKeyRaw&&) noexcept = default;
Martin Stjernholmc15e7e42020-12-02 22:50:53 +0000129
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.
136template <typename TValue>
137struct 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.
140 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) {}
150 explicit VariantMapKey(const TValue& default_value)
151 : default_value_(std::make_shared<TValue>(default_value)) {}
152 explicit VariantMapKey(TValue&& default_value)
153 : default_value_(std::make_shared<TValue>(default_value)) {}
154 VariantMapKey() {}
155 virtual ~VariantMapKey() {}
156
157 private:
158 virtual VariantMapKeyRaw* Clone() const {
159 return new VariantMapKey<TValue>(*this);
160 }
161
162 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
171 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;
android-t13d2c5b22022-10-12 13:43:18 +0800182 VariantMapKey(VariantMapKey&&) noexcept = default;
Martin Stjernholmc15e7e42020-12-02 22:50:53 +0000183
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.
191namespace detail {
192struct VariantMapStringKeyRegistry {
193 // TODO
194};
195} // namespace detail
196
197// Alternative base type for all keys used by VariantMap, supports runtime strings as the name.
198template <typename TValue>
199struct VariantMapStringKey : VariantMapKey<TValue> {
200 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.
212template <typename Base, template <typename TV> class TKey>
213struct 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>
221 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>
228 TValue* Get(const TKey<TValue>& key) {
229 return GetValuePtr(key);
230 }
231
Paul Duffina82c23a2021-01-25 12:54:21 +0000232 // 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>
235 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
Martin Stjernholmc15e7e42020-12-02 22:50:53 +0000240 // 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>
243 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>
249 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 {
260 ScopedRemove(VariantMap& map, const TKey<TValue>& key) : map_(map), key_(key) {}
261 ~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>
273 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>
286 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>
293 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>
306 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>
317 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.
329 void Clear() {
330 DeleteStoredValues();
331 storage_map_.clear();
332 }
333
334 // How many key/value pairs are stored in this map.
335 size_t Size() const {
336 return storage_map_.size();
337 }
338
339 // Construct an empty map.
340 VariantMap() {}
341
342 template <typename ... TKeyValue>
343 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.
349 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.
android-t13d2c5b22022-10-12 13:43:18 +0800375 VariantMap(VariantMap&& other) noexcept {
Martin Stjernholmc15e7e42020-12-02 22:50:53 +0000376 operator=(std::forward<VariantMap>(other));
377 }
378
379 // Move the existing map's key/value pairs into this one. The other map becomes empty.
android-t13d2c5b22022-10-12 13:43:18 +0800380 VariantMap& operator=(VariantMap&& other) noexcept {
Martin Stjernholmc15e7e42020-12-02 22:50:53 +0000381 if (this != &other) {
382 Clear();
383 storage_map_.swap(other.storage_map_);
384 other.storage_map_.clear();
385 }
386 return *this;
387 }
388
389 ~VariantMap() {
390 DeleteStoredValues();
391 }
392
393 private:
394 void InitializeParameters() {}
395
396 template <typename TK, typename TValue, typename ... Rest>
397 void InitializeParameters(const TK& key, const TValue& value, const Rest& ... rest) {
android-t13d2c5b22022-10-12 13:43:18 +0800398 static_assert(std::is_same_v<TK, TKey<TValue>>, "The 0th/2nd/4th/etc parameters must be a key");
Martin Stjernholmc15e7e42020-12-02 22:50:53 +0000399
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 {
408 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>
422 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>
431 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>
440 TValue* GetValuePtr(const TKey<TValue>& key) {
441 return const_cast<TValue*>(GetValueConstPtr(key));
442 }
443
444 template <typename TValue>
445 const TValue* GetValuePtr(const TKey<TValue>& key) const {
446 return GetValueConstPtr(key);
447 }
448
449 template <typename TValue>
450 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>
460 static void StaticAssertKeyType() {
android-t13d2c5b22022-10-12 13:43:18 +0800461 static_assert(std::is_base_of_v<VariantMapKey<TValue>, TKey<TValue>>,
Martin Stjernholmc15e7e42020-12-02 22:50:53 +0000462 "The provided key type (TKey) must be a subclass of VariantMapKey");
463 }
464
465 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_