blob: 402c7e9cb52419394299a5fece44ee5c263f560a [file] [log] [blame]
Elliott Hughes74847412012-06-20 18:10:21 -07001/*
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 Carlstromfc0e3212013-07-17 14:40:12 -070017#ifndef ART_RUNTIME_SAFE_MAP_H_
18#define ART_RUNTIME_SAFE_MAP_H_
Elliott Hughesa0e18062012-04-13 15:59:59 -070019
20#include <map>
Mathieu Chartier0a9dc052013-07-25 11:01:28 -070021#include <memory>
Elliott Hughesa0e18062012-04-13 15:59:59 -070022
Mathieu Chartierbad02672014-08-25 13:08:22 -070023#include "base/allocator.h"
Elliott Hughes07ed66b2012-12-12 18:34:25 -080024#include "base/logging.h"
Elliott Hughesa0e18062012-04-13 15:59:59 -070025
26namespace art {
27
28// Equivalent to std::map, but without operator[] and its bug-prone semantics (in particular,
29// the implicit insertion of a default-constructed value on failed lookups).
Mathieu Chartier0a9dc052013-07-25 11:01:28 -070030template <typename K, typename V, typename Comparator = std::less<K>,
Mathieu Chartierbad02672014-08-25 13:08:22 -070031 typename Allocator = TrackingAllocator<std::pair<const K, V>, kAllocatorTagSafeMap>>
Elliott Hughesa0e18062012-04-13 15:59:59 -070032class SafeMap {
33 private:
Mathieu Chartier0a9dc052013-07-25 11:01:28 -070034 typedef SafeMap<K, V, Comparator, Allocator> Self;
Elliott Hughesa0e18062012-04-13 15:59:59 -070035
36 public:
Vladimir Marko83cc7ae2014-02-12 18:02:05 +000037 typedef typename ::std::map<K, V, Comparator, Allocator>::key_compare key_compare;
Vladimir Markobd72fc12014-07-09 16:06:40 +010038 typedef typename ::std::map<K, V, Comparator, Allocator>::value_compare value_compare;
Vladimir Marko83cc7ae2014-02-12 18:02:05 +000039 typedef typename ::std::map<K, V, Comparator, Allocator>::allocator_type allocator_type;
40 typedef typename ::std::map<K, V, Comparator, Allocator>::iterator iterator;
41 typedef typename ::std::map<K, V, Comparator, Allocator>::const_iterator const_iterator;
42 typedef typename ::std::map<K, V, Comparator, Allocator>::size_type size_type;
Vladimir Markobd72fc12014-07-09 16:06:40 +010043 typedef typename ::std::map<K, V, Comparator, Allocator>::key_type key_type;
Vladimir Marko83cc7ae2014-02-12 18:02:05 +000044 typedef typename ::std::map<K, V, Comparator, Allocator>::value_type value_type;
45
46 SafeMap() = default;
Andreas Gampe758a8012015-04-03 21:28:42 -070047 SafeMap(const SafeMap&) = default;
Vladimir Marko83cc7ae2014-02-12 18:02:05 +000048 explicit SafeMap(const key_compare& cmp, const allocator_type& allocator = allocator_type())
49 : map_(cmp, allocator) {
50 }
Elliott Hughesa0e18062012-04-13 15:59:59 -070051
Elliott Hughes74847412012-06-20 18:10:21 -070052 Self& operator=(const Self& rhs) {
53 map_ = rhs.map_;
54 return *this;
55 }
Elliott Hughesa0e18062012-04-13 15:59:59 -070056
Vladimir Markob19955d2014-07-29 12:04:10 +010057 allocator_type get_allocator() const { return map_.get_allocator(); }
Vladimir Markobd72fc12014-07-09 16:06:40 +010058 key_compare key_comp() const { return map_.key_comp(); }
59 value_compare value_comp() const { return map_.value_comp(); }
60
Elliott Hughesa0e18062012-04-13 15:59:59 -070061 iterator begin() { return map_.begin(); }
62 const_iterator begin() const { return map_.begin(); }
63 iterator end() { return map_.end(); }
64 const_iterator end() const { return map_.end(); }
65
66 bool empty() const { return map_.empty(); }
67 size_type size() const { return map_.size(); }
68
Vladimir Markobd72fc12014-07-09 16:06:40 +010069 void swap(Self& other) { map_.swap(other.map_); }
Ian Rogers08f753d2012-08-24 14:35:25 -070070 void clear() { map_.clear(); }
Vladimir Markobd72fc12014-07-09 16:06:40 +010071 iterator erase(iterator it) { return map_.erase(it); }
Elliott Hughesa0e18062012-04-13 15:59:59 -070072 size_type erase(const K& k) { return map_.erase(k); }
73
74 iterator find(const K& k) { return map_.find(k); }
75 const_iterator find(const K& k) const { return map_.find(k); }
76
Vladimir Marko2ac01fc2014-05-22 12:09:08 +010077 iterator lower_bound(const K& k) { return map_.lower_bound(k); }
78 const_iterator lower_bound(const K& k) const { return map_.lower_bound(k); }
79
Elliott Hughesa0e18062012-04-13 15:59:59 -070080 size_type count(const K& k) const { return map_.count(k); }
81
82 // Note that unlike std::map's operator[], this doesn't return a reference to the value.
TDYa127b2eb5c12012-05-24 15:52:10 -070083 V Get(const K& k) const {
84 const_iterator it = map_.find(k);
Elliott Hughesa0e18062012-04-13 15:59:59 -070085 DCHECK(it != map_.end());
86 return it->second;
87 }
88
89 // Used to insert a new mapping.
Vladimir Markobd72fc12014-07-09 16:06:40 +010090 iterator Put(const K& k, const V& v) {
91 std::pair<iterator, bool> result = map_.emplace(k, v);
Brian Carlstrom7934ac22013-07-26 10:54:15 -070092 DCHECK(result.second); // Check we didn't accidentally overwrite an existing value.
Vladimir Markobd72fc12014-07-09 16:06:40 +010093 return result.first;
94 }
95
96 // Used to insert a new mapping at a known position for better performance.
97 iterator PutBefore(iterator pos, const K& k, const V& v) {
98 // Check that we're using the correct position and the key is not in the map.
99 DCHECK(pos == map_.end() || map_.key_comp()(k, pos->first));
100 DCHECK(pos == map_.begin() || map_.key_comp()((--iterator(pos))->first, k));
101 return map_.emplace_hint(pos, k, v);
Elliott Hughesa0e18062012-04-13 15:59:59 -0700102 }
103
104 // Used to insert a new mapping or overwrite an existing mapping. Note that if the value type
105 // of this container is a pointer, any overwritten pointer will be lost and if this container
106 // was the owner, you have a leak.
107 void Overwrite(const K& k, const V& v) {
buzbeed1643e42012-09-05 14:06:51 -0700108 std::pair<iterator, bool> result = map_.insert(std::make_pair(k, v));
109 if (!result.second) {
110 // Already there - update the value for the existing key
111 result.first->second = v;
112 }
Elliott Hughesa0e18062012-04-13 15:59:59 -0700113 }
114
115 bool Equals(const Self& rhs) const {
116 return map_ == rhs.map_;
117 }
118
119 private:
Mathieu Chartier0a9dc052013-07-25 11:01:28 -0700120 ::std::map<K, V, Comparator, Allocator> map_;
Elliott Hughesa0e18062012-04-13 15:59:59 -0700121};
122
Vladimir Markobd72fc12014-07-09 16:06:40 +0100123template <typename K, typename V, typename Comparator, typename Allocator>
124bool operator==(const SafeMap<K, V, Comparator, Allocator>& lhs,
125 const SafeMap<K, V, Comparator, Allocator>& rhs) {
Elliott Hughesa0e18062012-04-13 15:59:59 -0700126 return lhs.Equals(rhs);
127}
128
Vladimir Markobd72fc12014-07-09 16:06:40 +0100129template <typename K, typename V, typename Comparator, typename Allocator>
130bool operator!=(const SafeMap<K, V, Comparator, Allocator>& lhs,
131 const SafeMap<K, V, Comparator, Allocator>& rhs) {
Elliott Hughesa0e18062012-04-13 15:59:59 -0700132 return !(lhs == rhs);
133}
134
Mathieu Chartierbad02672014-08-25 13:08:22 -0700135template<class Key, class T, AllocatorTag kTag, class Compare = std::less<Key>>
136class AllocationTrackingSafeMap : public SafeMap<
137 Key, T, Compare, TrackingAllocator<std::pair<Key, T>, kTag>> {
138};
139
Elliott Hughesa0e18062012-04-13 15:59:59 -0700140} // namespace art
141
Brian Carlstromfc0e3212013-07-17 14:40:12 -0700142#endif // ART_RUNTIME_SAFE_MAP_H_