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 #include <string> 22 23 #include "base/mutex.h" 24 #include "base/stl_util.h" 25 #include "base/stringprintf.h" 26 27 namespace art { 28 29 // A set of Keys that support a HashFunc returning HashType. Used to find duplicates of Key in the 30 // Add method. The data-structure is thread-safe through the use of internal locks, it also 31 // supports the lock being sharded. 32 template <typename Key, typename HashType, typename HashFunc, HashType kShard = 1> 33 class DedupeSet { 34 typedef std::pair<HashType, Key*> HashedKey; 35 36 class Comparator { 37 public: operator()38 bool operator()(const HashedKey& a, const HashedKey& b) const { 39 if (a.first != b.first) { 40 return a.first < b.first; 41 } else { 42 return *a.second < *b.second; 43 } 44 } 45 }; 46 47 public: Add(Thread * self,const Key & key)48 Key* Add(Thread* self, const Key& key) { 49 HashType raw_hash = HashFunc()(key); 50 HashType shard_hash = raw_hash / kShard; 51 HashType shard_bin = raw_hash % kShard; 52 HashedKey hashed_key(shard_hash, const_cast<Key*>(&key)); 53 MutexLock lock(self, *lock_[shard_bin]); 54 auto it = keys_[shard_bin].find(hashed_key); 55 if (it != keys_[shard_bin].end()) { 56 return it->second; 57 } 58 hashed_key.second = new Key(key); 59 keys_[shard_bin].insert(hashed_key); 60 return hashed_key.second; 61 } 62 DedupeSet(const char * set_name)63 explicit DedupeSet(const char* set_name) { 64 for (HashType i = 0; i < kShard; ++i) { 65 std::ostringstream oss; 66 oss << set_name << " lock " << i; 67 lock_name_[i] = oss.str(); 68 lock_[i].reset(new Mutex(lock_name_[i].c_str())); 69 } 70 } 71 ~DedupeSet()72 ~DedupeSet() { 73 for (HashType i = 0; i < kShard; ++i) { 74 STLDeleteValues(&keys_[i]); 75 } 76 } 77 78 private: 79 std::string lock_name_[kShard]; 80 std::unique_ptr<Mutex> lock_[kShard]; 81 std::set<HashedKey, Comparator> keys_[kShard]; 82 83 DISALLOW_COPY_AND_ASSIGN(DedupeSet); 84 }; 85 86 } // namespace art 87 88 #endif // ART_COMPILER_UTILS_DEDUPE_SET_H_ 89