1748474146da0c6484fa3dca0a700f612d47550c3Elliott Hughes/* 2748474146da0c6484fa3dca0a700f612d47550c3Elliott Hughes * Copyright (C) 2012 The Android Open Source Project 3748474146da0c6484fa3dca0a700f612d47550c3Elliott Hughes * 4748474146da0c6484fa3dca0a700f612d47550c3Elliott Hughes * Licensed under the Apache License, Version 2.0 (the "License"); 5748474146da0c6484fa3dca0a700f612d47550c3Elliott Hughes * you may not use this file except in compliance with the License. 6748474146da0c6484fa3dca0a700f612d47550c3Elliott Hughes * You may obtain a copy of the License at 7748474146da0c6484fa3dca0a700f612d47550c3Elliott Hughes * 8748474146da0c6484fa3dca0a700f612d47550c3Elliott Hughes * http://www.apache.org/licenses/LICENSE-2.0 9748474146da0c6484fa3dca0a700f612d47550c3Elliott Hughes * 10748474146da0c6484fa3dca0a700f612d47550c3Elliott Hughes * Unless required by applicable law or agreed to in writing, software 11748474146da0c6484fa3dca0a700f612d47550c3Elliott Hughes * distributed under the License is distributed on an "AS IS" BASIS, 12748474146da0c6484fa3dca0a700f612d47550c3Elliott Hughes * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13748474146da0c6484fa3dca0a700f612d47550c3Elliott Hughes * See the License for the specific language governing permissions and 14748474146da0c6484fa3dca0a700f612d47550c3Elliott Hughes * limitations under the License. 15748474146da0c6484fa3dca0a700f612d47550c3Elliott Hughes */ 16748474146da0c6484fa3dca0a700f612d47550c3Elliott Hughes 17fc0e3219edc9a5bf81b166e82fd5db2796eb6a0dBrian Carlstrom#ifndef ART_RUNTIME_SAFE_MAP_H_ 18fc0e3219edc9a5bf81b166e82fd5db2796eb6a0dBrian Carlstrom#define ART_RUNTIME_SAFE_MAP_H_ 19a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes 20a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes#include <map> 210a9dc05e704bfd033bac2aa38a4fc6f6b8e6cf93Mathieu Chartier#include <memory> 22a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes 235369c40f75fdcb1be7a7c06db212ce965c83a164Mathieu Chartier#include "base/allocator.h" 2407ed66b5ae659c452cbe1ab20c3dbf1d6f546461Elliott Hughes#include "base/logging.h" 25a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes 26a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughesnamespace art { 27a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes 28a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes// Equivalent to std::map, but without operator[] and its bug-prone semantics (in particular, 29a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes// the implicit insertion of a default-constructed value on failed lookups). 300a9dc05e704bfd033bac2aa38a4fc6f6b8e6cf93Mathieu Chartiertemplate <typename K, typename V, typename Comparator = std::less<K>, 315369c40f75fdcb1be7a7c06db212ce965c83a164Mathieu Chartier typename Allocator = TrackingAllocator<std::pair<const K, V>, kAllocatorTagSafeMap>> 32a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughesclass SafeMap { 33a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes private: 340a9dc05e704bfd033bac2aa38a4fc6f6b8e6cf93Mathieu Chartier typedef SafeMap<K, V, Comparator, Allocator> Self; 35a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes 36a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes public: 3783cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko typedef typename ::std::map<K, V, Comparator, Allocator>::key_compare key_compare; 38bd72fc137a51257f61038ba21c15cf5f1abcdbefVladimir Marko typedef typename ::std::map<K, V, Comparator, Allocator>::value_compare value_compare; 3983cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko typedef typename ::std::map<K, V, Comparator, Allocator>::allocator_type allocator_type; 4083cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko typedef typename ::std::map<K, V, Comparator, Allocator>::iterator iterator; 4183cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko typedef typename ::std::map<K, V, Comparator, Allocator>::const_iterator const_iterator; 4283cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko typedef typename ::std::map<K, V, Comparator, Allocator>::size_type size_type; 43bd72fc137a51257f61038ba21c15cf5f1abcdbefVladimir Marko typedef typename ::std::map<K, V, Comparator, Allocator>::key_type key_type; 4483cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko typedef typename ::std::map<K, V, Comparator, Allocator>::value_type value_type; 4583cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko 4683cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko SafeMap() = default; 4783cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko explicit SafeMap(const key_compare& cmp, const allocator_type& allocator = allocator_type()) 4883cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko : map_(cmp, allocator) { 4983cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko } 50a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes 51748474146da0c6484fa3dca0a700f612d47550c3Elliott Hughes Self& operator=(const Self& rhs) { 52748474146da0c6484fa3dca0a700f612d47550c3Elliott Hughes map_ = rhs.map_; 53748474146da0c6484fa3dca0a700f612d47550c3Elliott Hughes return *this; 54748474146da0c6484fa3dca0a700f612d47550c3Elliott Hughes } 55a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes 56b19955d3c8fbd9588f7e17299e559d02938154b6Vladimir Marko allocator_type get_allocator() const { return map_.get_allocator(); } 57bd72fc137a51257f61038ba21c15cf5f1abcdbefVladimir Marko key_compare key_comp() const { return map_.key_comp(); } 58bd72fc137a51257f61038ba21c15cf5f1abcdbefVladimir Marko value_compare value_comp() const { return map_.value_comp(); } 59bd72fc137a51257f61038ba21c15cf5f1abcdbefVladimir Marko 60a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes iterator begin() { return map_.begin(); } 61a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes const_iterator begin() const { return map_.begin(); } 62a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes iterator end() { return map_.end(); } 63a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes const_iterator end() const { return map_.end(); } 64a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes 65a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes bool empty() const { return map_.empty(); } 66a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes size_type size() const { return map_.size(); } 67a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes 68bd72fc137a51257f61038ba21c15cf5f1abcdbefVladimir Marko void swap(Self& other) { map_.swap(other.map_); } 6908f753d5859936f8d3524e9e4faa6cee353873eaIan Rogers void clear() { map_.clear(); } 70bd72fc137a51257f61038ba21c15cf5f1abcdbefVladimir Marko iterator erase(iterator it) { return map_.erase(it); } 71a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes size_type erase(const K& k) { return map_.erase(k); } 72a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes 73a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes iterator find(const K& k) { return map_.find(k); } 74a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes const_iterator find(const K& k) const { return map_.find(k); } 75a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes 762ac01fc279e8397beacf90302b0f215040eb78faVladimir Marko iterator lower_bound(const K& k) { return map_.lower_bound(k); } 772ac01fc279e8397beacf90302b0f215040eb78faVladimir Marko const_iterator lower_bound(const K& k) const { return map_.lower_bound(k); } 782ac01fc279e8397beacf90302b0f215040eb78faVladimir Marko 79a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes size_type count(const K& k) const { return map_.count(k); } 80a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes 81a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes // Note that unlike std::map's operator[], this doesn't return a reference to the value. 82b2eb5c18d628dc84bdc424b5e5a491382d867e36TDYa V Get(const K& k) const { 83b2eb5c18d628dc84bdc424b5e5a491382d867e36TDYa const_iterator it = map_.find(k); 84a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes DCHECK(it != map_.end()); 85a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes return it->second; 86a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes } 87a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes 88a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes // Used to insert a new mapping. 89bd72fc137a51257f61038ba21c15cf5f1abcdbefVladimir Marko iterator Put(const K& k, const V& v) { 90bd72fc137a51257f61038ba21c15cf5f1abcdbefVladimir Marko std::pair<iterator, bool> result = map_.emplace(k, v); 917934ac288acfb2552bb0b06ec1f61e5820d924a4Brian Carlstrom DCHECK(result.second); // Check we didn't accidentally overwrite an existing value. 92bd72fc137a51257f61038ba21c15cf5f1abcdbefVladimir Marko return result.first; 93bd72fc137a51257f61038ba21c15cf5f1abcdbefVladimir Marko } 94bd72fc137a51257f61038ba21c15cf5f1abcdbefVladimir Marko 95bd72fc137a51257f61038ba21c15cf5f1abcdbefVladimir Marko // Used to insert a new mapping at a known position for better performance. 96bd72fc137a51257f61038ba21c15cf5f1abcdbefVladimir Marko iterator PutBefore(iterator pos, const K& k, const V& v) { 97bd72fc137a51257f61038ba21c15cf5f1abcdbefVladimir Marko // Check that we're using the correct position and the key is not in the map. 98bd72fc137a51257f61038ba21c15cf5f1abcdbefVladimir Marko DCHECK(pos == map_.end() || map_.key_comp()(k, pos->first)); 99bd72fc137a51257f61038ba21c15cf5f1abcdbefVladimir Marko DCHECK(pos == map_.begin() || map_.key_comp()((--iterator(pos))->first, k)); 100bd72fc137a51257f61038ba21c15cf5f1abcdbefVladimir Marko return map_.emplace_hint(pos, k, v); 101a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes } 102a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes 103a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes // Used to insert a new mapping or overwrite an existing mapping. Note that if the value type 104a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes // of this container is a pointer, any overwritten pointer will be lost and if this container 105a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes // was the owner, you have a leak. 106a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes void Overwrite(const K& k, const V& v) { 107d1643e41ef242ae656f667bf3c8b0324635cefd3buzbee std::pair<iterator, bool> result = map_.insert(std::make_pair(k, v)); 108d1643e41ef242ae656f667bf3c8b0324635cefd3buzbee if (!result.second) { 109d1643e41ef242ae656f667bf3c8b0324635cefd3buzbee // Already there - update the value for the existing key 110d1643e41ef242ae656f667bf3c8b0324635cefd3buzbee result.first->second = v; 111d1643e41ef242ae656f667bf3c8b0324635cefd3buzbee } 112a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes } 113a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes 114a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes bool Equals(const Self& rhs) const { 115a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes return map_ == rhs.map_; 116a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes } 117a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes 118a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes private: 1190a9dc05e704bfd033bac2aa38a4fc6f6b8e6cf93Mathieu Chartier ::std::map<K, V, Comparator, Allocator> map_; 120a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes}; 121a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes 122bd72fc137a51257f61038ba21c15cf5f1abcdbefVladimir Markotemplate <typename K, typename V, typename Comparator, typename Allocator> 123bd72fc137a51257f61038ba21c15cf5f1abcdbefVladimir Markobool operator==(const SafeMap<K, V, Comparator, Allocator>& lhs, 124bd72fc137a51257f61038ba21c15cf5f1abcdbefVladimir Marko const SafeMap<K, V, Comparator, Allocator>& rhs) { 125a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes return lhs.Equals(rhs); 126a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes} 127a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes 128bd72fc137a51257f61038ba21c15cf5f1abcdbefVladimir Markotemplate <typename K, typename V, typename Comparator, typename Allocator> 129bd72fc137a51257f61038ba21c15cf5f1abcdbefVladimir Markobool operator!=(const SafeMap<K, V, Comparator, Allocator>& lhs, 130bd72fc137a51257f61038ba21c15cf5f1abcdbefVladimir Marko const SafeMap<K, V, Comparator, Allocator>& rhs) { 131a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes return !(lhs == rhs); 132a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes} 133a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes 1345369c40f75fdcb1be7a7c06db212ce965c83a164Mathieu Chartiertemplate<class Key, class T, AllocatorTag kTag, class Compare = std::less<Key>> 1355369c40f75fdcb1be7a7c06db212ce965c83a164Mathieu Chartierclass AllocationTrackingSafeMap : public SafeMap< 1365369c40f75fdcb1be7a7c06db212ce965c83a164Mathieu Chartier Key, T, Compare, TrackingAllocator<std::pair<Key, T>, kTag>> { 1375369c40f75fdcb1be7a7c06db212ce965c83a164Mathieu Chartier}; 1385369c40f75fdcb1be7a7c06db212ce965c83a164Mathieu Chartier 139a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes} // namespace art 140a0e180632411f7fe0edf454e571c42209ee7b540Elliott Hughes 141fc0e3219edc9a5bf81b166e82fd5db2796eb6a0dBrian Carlstrom#endif // ART_RUNTIME_SAFE_MAP_H_ 142