Elliott Hughes | 7484741 | 2012-06-20 18:10:21 -0700 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2012 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 | |
Brian Carlstrom | fc0e321 | 2013-07-17 14:40:12 -0700 | [diff] [blame] | 17 | #ifndef ART_RUNTIME_SAFE_MAP_H_ |
| 18 | #define ART_RUNTIME_SAFE_MAP_H_ |
Elliott Hughes | a0e1806 | 2012-04-13 15:59:59 -0700 | [diff] [blame] | 19 | |
| 20 | #include <map> |
Mathieu Chartier | 0a9dc05 | 2013-07-25 11:01:28 -0700 | [diff] [blame] | 21 | #include <memory> |
Elliott Hughes | a0e1806 | 2012-04-13 15:59:59 -0700 | [diff] [blame] | 22 | |
Elliott Hughes | 07ed66b | 2012-12-12 18:34:25 -0800 | [diff] [blame] | 23 | #include "base/logging.h" |
Elliott Hughes | a0e1806 | 2012-04-13 15:59:59 -0700 | [diff] [blame] | 24 | |
| 25 | namespace art { |
| 26 | |
| 27 | // Equivalent to std::map, but without operator[] and its bug-prone semantics (in particular, |
| 28 | // the implicit insertion of a default-constructed value on failed lookups). |
Mathieu Chartier | 0a9dc05 | 2013-07-25 11:01:28 -0700 | [diff] [blame] | 29 | template <typename K, typename V, typename Comparator = std::less<K>, |
Ian Rogers | 700a402 | 2014-05-19 16:49:03 -0700 | [diff] [blame] | 30 | typename Allocator = std::allocator<std::pair<const K, V>>> |
Elliott Hughes | a0e1806 | 2012-04-13 15:59:59 -0700 | [diff] [blame] | 31 | class SafeMap { |
| 32 | private: |
Mathieu Chartier | 0a9dc05 | 2013-07-25 11:01:28 -0700 | [diff] [blame] | 33 | typedef SafeMap<K, V, Comparator, Allocator> Self; |
Elliott Hughes | a0e1806 | 2012-04-13 15:59:59 -0700 | [diff] [blame] | 34 | |
| 35 | public: |
Vladimir Marko | 83cc7ae | 2014-02-12 18:02:05 +0000 | [diff] [blame] | 36 | typedef typename ::std::map<K, V, Comparator, Allocator>::key_compare key_compare; |
Vladimir Marko | bd72fc1 | 2014-07-09 16:06:40 +0100 | [diff] [blame^] | 37 | typedef typename ::std::map<K, V, Comparator, Allocator>::value_compare value_compare; |
Vladimir Marko | 83cc7ae | 2014-02-12 18:02:05 +0000 | [diff] [blame] | 38 | typedef typename ::std::map<K, V, Comparator, Allocator>::allocator_type allocator_type; |
| 39 | typedef typename ::std::map<K, V, Comparator, Allocator>::iterator iterator; |
| 40 | typedef typename ::std::map<K, V, Comparator, Allocator>::const_iterator const_iterator; |
| 41 | typedef typename ::std::map<K, V, Comparator, Allocator>::size_type size_type; |
Vladimir Marko | bd72fc1 | 2014-07-09 16:06:40 +0100 | [diff] [blame^] | 42 | typedef typename ::std::map<K, V, Comparator, Allocator>::key_type key_type; |
Vladimir Marko | 83cc7ae | 2014-02-12 18:02:05 +0000 | [diff] [blame] | 43 | typedef typename ::std::map<K, V, Comparator, Allocator>::value_type value_type; |
| 44 | |
| 45 | SafeMap() = default; |
| 46 | explicit SafeMap(const key_compare& cmp, const allocator_type& allocator = allocator_type()) |
| 47 | : map_(cmp, allocator) { |
| 48 | } |
Elliott Hughes | a0e1806 | 2012-04-13 15:59:59 -0700 | [diff] [blame] | 49 | |
Elliott Hughes | 7484741 | 2012-06-20 18:10:21 -0700 | [diff] [blame] | 50 | Self& operator=(const Self& rhs) { |
| 51 | map_ = rhs.map_; |
| 52 | return *this; |
| 53 | } |
Elliott Hughes | a0e1806 | 2012-04-13 15:59:59 -0700 | [diff] [blame] | 54 | |
Vladimir Marko | bd72fc1 | 2014-07-09 16:06:40 +0100 | [diff] [blame^] | 55 | key_compare key_comp() const { return map_.key_comp(); } |
| 56 | value_compare value_comp() const { return map_.value_comp(); } |
| 57 | |
Elliott Hughes | a0e1806 | 2012-04-13 15:59:59 -0700 | [diff] [blame] | 58 | iterator begin() { return map_.begin(); } |
| 59 | const_iterator begin() const { return map_.begin(); } |
| 60 | iterator end() { return map_.end(); } |
| 61 | const_iterator end() const { return map_.end(); } |
| 62 | |
| 63 | bool empty() const { return map_.empty(); } |
| 64 | size_type size() const { return map_.size(); } |
| 65 | |
Vladimir Marko | bd72fc1 | 2014-07-09 16:06:40 +0100 | [diff] [blame^] | 66 | void swap(Self& other) { map_.swap(other.map_); } |
Ian Rogers | 08f753d | 2012-08-24 14:35:25 -0700 | [diff] [blame] | 67 | void clear() { map_.clear(); } |
Vladimir Marko | bd72fc1 | 2014-07-09 16:06:40 +0100 | [diff] [blame^] | 68 | iterator erase(iterator it) { return map_.erase(it); } |
Elliott Hughes | a0e1806 | 2012-04-13 15:59:59 -0700 | [diff] [blame] | 69 | size_type erase(const K& k) { return map_.erase(k); } |
| 70 | |
| 71 | iterator find(const K& k) { return map_.find(k); } |
| 72 | const_iterator find(const K& k) const { return map_.find(k); } |
| 73 | |
Vladimir Marko | 2ac01fc | 2014-05-22 12:09:08 +0100 | [diff] [blame] | 74 | iterator lower_bound(const K& k) { return map_.lower_bound(k); } |
| 75 | const_iterator lower_bound(const K& k) const { return map_.lower_bound(k); } |
| 76 | |
Elliott Hughes | a0e1806 | 2012-04-13 15:59:59 -0700 | [diff] [blame] | 77 | size_type count(const K& k) const { return map_.count(k); } |
| 78 | |
| 79 | // Note that unlike std::map's operator[], this doesn't return a reference to the value. |
TDYa127 | b2eb5c1 | 2012-05-24 15:52:10 -0700 | [diff] [blame] | 80 | V Get(const K& k) const { |
| 81 | const_iterator it = map_.find(k); |
Elliott Hughes | a0e1806 | 2012-04-13 15:59:59 -0700 | [diff] [blame] | 82 | DCHECK(it != map_.end()); |
| 83 | return it->second; |
| 84 | } |
| 85 | |
| 86 | // Used to insert a new mapping. |
Vladimir Marko | bd72fc1 | 2014-07-09 16:06:40 +0100 | [diff] [blame^] | 87 | iterator Put(const K& k, const V& v) { |
| 88 | std::pair<iterator, bool> result = map_.emplace(k, v); |
Brian Carlstrom | 7934ac2 | 2013-07-26 10:54:15 -0700 | [diff] [blame] | 89 | DCHECK(result.second); // Check we didn't accidentally overwrite an existing value. |
Vladimir Marko | bd72fc1 | 2014-07-09 16:06:40 +0100 | [diff] [blame^] | 90 | return result.first; |
| 91 | } |
| 92 | |
| 93 | // Used to insert a new mapping at a known position for better performance. |
| 94 | iterator PutBefore(iterator pos, const K& k, const V& v) { |
| 95 | // Check that we're using the correct position and the key is not in the map. |
| 96 | DCHECK(pos == map_.end() || map_.key_comp()(k, pos->first)); |
| 97 | DCHECK(pos == map_.begin() || map_.key_comp()((--iterator(pos))->first, k)); |
| 98 | return map_.emplace_hint(pos, k, v); |
Elliott Hughes | a0e1806 | 2012-04-13 15:59:59 -0700 | [diff] [blame] | 99 | } |
| 100 | |
| 101 | // Used to insert a new mapping or overwrite an existing mapping. Note that if the value type |
| 102 | // of this container is a pointer, any overwritten pointer will be lost and if this container |
| 103 | // was the owner, you have a leak. |
| 104 | void Overwrite(const K& k, const V& v) { |
buzbee | d1643e4 | 2012-09-05 14:06:51 -0700 | [diff] [blame] | 105 | std::pair<iterator, bool> result = map_.insert(std::make_pair(k, v)); |
| 106 | if (!result.second) { |
| 107 | // Already there - update the value for the existing key |
| 108 | result.first->second = v; |
| 109 | } |
Elliott Hughes | a0e1806 | 2012-04-13 15:59:59 -0700 | [diff] [blame] | 110 | } |
| 111 | |
| 112 | bool Equals(const Self& rhs) const { |
| 113 | return map_ == rhs.map_; |
| 114 | } |
| 115 | |
| 116 | private: |
Mathieu Chartier | 0a9dc05 | 2013-07-25 11:01:28 -0700 | [diff] [blame] | 117 | ::std::map<K, V, Comparator, Allocator> map_; |
Elliott Hughes | a0e1806 | 2012-04-13 15:59:59 -0700 | [diff] [blame] | 118 | }; |
| 119 | |
Vladimir Marko | bd72fc1 | 2014-07-09 16:06:40 +0100 | [diff] [blame^] | 120 | template <typename K, typename V, typename Comparator, typename Allocator> |
| 121 | bool operator==(const SafeMap<K, V, Comparator, Allocator>& lhs, |
| 122 | const SafeMap<K, V, Comparator, Allocator>& rhs) { |
Elliott Hughes | a0e1806 | 2012-04-13 15:59:59 -0700 | [diff] [blame] | 123 | return lhs.Equals(rhs); |
| 124 | } |
| 125 | |
Vladimir Marko | bd72fc1 | 2014-07-09 16:06:40 +0100 | [diff] [blame^] | 126 | template <typename K, typename V, typename Comparator, typename Allocator> |
| 127 | bool operator!=(const SafeMap<K, V, Comparator, Allocator>& lhs, |
| 128 | const SafeMap<K, V, Comparator, Allocator>& rhs) { |
Elliott Hughes | a0e1806 | 2012-04-13 15:59:59 -0700 | [diff] [blame] | 129 | return !(lhs == rhs); |
| 130 | } |
| 131 | |
| 132 | } // namespace art |
| 133 | |
Brian Carlstrom | fc0e321 | 2013-07-17 14:40:12 -0700 | [diff] [blame] | 134 | #endif // ART_RUNTIME_SAFE_MAP_H_ |