1 /* 2 * Copyright (C) 2013 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_COMPILER_UTILS_DEDUPE_SET_H_ 18 #define ART_COMPILER_UTILS_DEDUPE_SET_H_ 19 20 #include <set> 21 22 #include "base/mutex.h" 23 #include "base/stl_util.h" 24 25 namespace art { 26 27 // A simple data structure to handle hashed deduplication. Add is thread safe. 28 template <typename Key, typename HashType, typename HashFunc> 29 class DedupeSet { 30 typedef std::pair<HashType, Key*> HashedKey; 31 32 class Comparator { 33 public: operator()34 bool operator()(const HashedKey& a, const HashedKey& b) const { 35 if (a.first < b.first) return true; 36 if (a.first > b.first) return true; 37 return *a.second < *b.second; 38 } 39 }; 40 41 typedef std::set<HashedKey, Comparator> Keys; 42 43 public: 44 typedef typename Keys::iterator iterator; 45 typedef typename Keys::const_iterator const_iterator; 46 typedef typename Keys::size_type size_type; 47 typedef typename Keys::value_type value_type; 48 begin()49 iterator begin() { return keys_.begin(); } begin()50 const_iterator begin() const { return keys_.begin(); } end()51 iterator end() { return keys_.end(); } end()52 const_iterator end() const { return keys_.end(); } 53 Add(Thread * self,const Key & key)54 Key* Add(Thread* self, const Key& key) { 55 HashType hash = HashFunc()(key); 56 HashedKey hashed_key(hash, const_cast<Key*>(&key)); 57 MutexLock lock(self, lock_); 58 auto it = keys_.find(hashed_key); 59 if (it != keys_.end()) { 60 return it->second; 61 } 62 hashed_key.second = new Key(key); 63 keys_.insert(hashed_key); 64 return hashed_key.second; 65 } 66 DedupeSet()67 DedupeSet() : lock_("dedupe lock") { 68 } 69 ~DedupeSet()70 ~DedupeSet() { 71 STLDeleteValues(&keys_); 72 } 73 74 private: 75 Mutex lock_ DEFAULT_MUTEX_ACQUIRED_AFTER; 76 Keys keys_; 77 DISALLOW_COPY_AND_ASSIGN(DedupeSet); 78 }; 79 80 } // namespace art 81 82 #endif // ART_COMPILER_UTILS_DEDUPE_SET_H_ 83