1/* 2 * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2013 Apple Inc. All rights reserved. 3 * 4 * This library is free software; you can redistribute it and/or 5 * modify it under the terms of the GNU Library General Public 6 * License as published by the Free Software Foundation; either 7 * version 2 of the License, or (at your option) any later version. 8 * 9 * This library is distributed in the hope that it will be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 12 * Library General Public License for more details. 13 * 14 * You should have received a copy of the GNU Library General Public License 15 * along with this library; see the file COPYING.LIB. If not, write to 16 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 17 * Boston, MA 02110-1301, USA. 18 * 19 */ 20 21#ifndef RefPtrHashMap_h 22#define RefPtrHashMap_h 23 24namespace WTF { 25 26 // This specialization is a copy of HashMap for use with RefPtr keys, with overloaded functions 27 // to allow for lookup by pointer instead of RefPtr, avoiding ref-count churn. 28 29 // FIXME: Find a way to do this with traits that doesn't require a copy of the HashMap template. 30 31 template<typename T, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg> 32 class HashMap<RefPtr<T>, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg> { 33 WTF_MAKE_FAST_ALLOCATED; 34 private: 35 typedef KeyTraitsArg KeyTraits; 36 typedef MappedTraitsArg MappedTraits; 37 typedef KeyValuePairHashTraits<KeyTraits, MappedTraits> ValueTraits; 38 39 public: 40 typedef typename KeyTraits::TraitType KeyType; 41 typedef T* RawKeyType; 42 typedef typename MappedTraits::TraitType MappedType; 43 typedef typename ValueTraits::TraitType ValueType; 44 45 private: 46 typedef typename MappedTraits::PeekType MappedPeekType; 47 48 typedef HashArg HashFunctions; 49 50 typedef HashTable<KeyType, ValueType, KeyValuePairKeyExtractor<ValueType>, 51 HashFunctions, ValueTraits, KeyTraits> HashTableType; 52 53 typedef HashMapTranslator<ValueTraits, HashFunctions> 54 Translator; 55 56 public: 57 typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator; 58 typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator; 59 typedef typename HashTableType::AddResult AddResult; 60 61 void swap(HashMap&); 62 63 int size() const; 64 int capacity() const; 65 bool isEmpty() const; 66 67 // iterators iterate over pairs of keys and values 68 iterator begin(); 69 iterator end(); 70 const_iterator begin() const; 71 const_iterator end() const; 72 73 IteratorRange<typename iterator::Keys> keys() { return makeIteratorRange(begin().keys(), end().keys()); } 74 const IteratorRange<typename const_iterator::Keys> keys() const { return makeIteratorRange(begin().keys(), end().keys()); } 75 76 IteratorRange<typename iterator::Values> values() { return makeIteratorRange(begin().values(), end().values()); } 77 const IteratorRange<typename const_iterator::Values> values() const { return makeIteratorRange(begin().values(), end().values()); } 78 79 iterator find(const KeyType&); 80 iterator find(RawKeyType); 81 const_iterator find(const KeyType&) const; 82 const_iterator find(RawKeyType) const; 83 bool contains(const KeyType&) const; 84 bool contains(RawKeyType) const; 85 MappedPeekType get(const KeyType&) const; 86 MappedPeekType get(RawKeyType) const; 87 MappedPeekType inlineGet(RawKeyType) const; 88 89 // replaces value but not key if key is already present 90 // return value is a pair of the iterator to the key location, 91 // and a boolean that's true if a new value was actually added 92 template<typename V> AddResult set(const KeyType&, V&&); 93 template<typename V> AddResult set(RawKeyType, V&&); 94 95 // does nothing if key is already present 96 // return value is a pair of the iterator to the key location, 97 // and a boolean that's true if a new value was actually added 98 template<typename V> AddResult add(const KeyType&, V&&); 99 template<typename V> AddResult add(RawKeyType, V&&); 100 101 bool remove(const KeyType&); 102 bool remove(RawKeyType); 103 bool remove(iterator); 104 void clear(); 105 106 MappedType take(const KeyType&); // efficient combination of get with remove 107 MappedType take(RawKeyType); // efficient combination of get with remove 108 109 private: 110 template<typename V> 111 AddResult inlineAdd(const KeyType&, V&&); 112 113 template<typename V> 114 AddResult inlineAdd(RawKeyType, V&&); 115 116 HashTableType m_impl; 117 }; 118 119 template<typename T, typename U, typename V, typename W, typename X> 120 inline void HashMap<RefPtr<T>, U, V, W, X>::swap(HashMap& other) 121 { 122 m_impl.swap(other.m_impl); 123 } 124 125 template<typename T, typename U, typename V, typename W, typename X> 126 inline int HashMap<RefPtr<T>, U, V, W, X>::size() const 127 { 128 return m_impl.size(); 129 } 130 131 template<typename T, typename U, typename V, typename W, typename X> 132 inline int HashMap<RefPtr<T>, U, V, W, X>::capacity() const 133 { 134 return m_impl.capacity(); 135 } 136 137 template<typename T, typename U, typename V, typename W, typename X> 138 inline bool HashMap<RefPtr<T>, U, V, W, X>::isEmpty() const 139 { 140 return m_impl.isEmpty(); 141 } 142 143 template<typename T, typename U, typename V, typename W, typename X> 144 inline typename HashMap<RefPtr<T>, U, V, W, X>::iterator HashMap<RefPtr<T>, U, V, W, X>::begin() 145 { 146 return m_impl.begin(); 147 } 148 149 template<typename T, typename U, typename V, typename W, typename X> 150 inline typename HashMap<RefPtr<T>, U, V, W, X>::iterator HashMap<RefPtr<T>, U, V, W, X>::end() 151 { 152 return m_impl.end(); 153 } 154 155 template<typename T, typename U, typename V, typename W, typename X> 156 inline typename HashMap<RefPtr<T>, U, V, W, X>::const_iterator HashMap<RefPtr<T>, U, V, W, X>::begin() const 157 { 158 return m_impl.begin(); 159 } 160 161 template<typename T, typename U, typename V, typename W, typename X> 162 inline typename HashMap<RefPtr<T>, U, V, W, X>::const_iterator HashMap<RefPtr<T>, U, V, W, X>::end() const 163 { 164 return m_impl.end(); 165 } 166 167 template<typename T, typename U, typename V, typename W, typename X> 168 inline typename HashMap<RefPtr<T>, U, V, W, X>::iterator HashMap<RefPtr<T>, U, V, W, X>::find(const KeyType& key) 169 { 170 return m_impl.find(key); 171 } 172 173 template<typename T, typename U, typename V, typename W, typename X> 174 inline typename HashMap<RefPtr<T>, U, V, W, X>::iterator HashMap<RefPtr<T>, U, V, W, X>::find(RawKeyType key) 175 { 176 return m_impl.template find<Translator>(key); 177 } 178 179 template<typename T, typename U, typename V, typename W, typename X> 180 inline typename HashMap<RefPtr<T>, U, V, W, X>::const_iterator HashMap<RefPtr<T>, U, V, W, X>::find(const KeyType& key) const 181 { 182 return m_impl.find(key); 183 } 184 185 template<typename T, typename U, typename V, typename W, typename X> 186 inline typename HashMap<RefPtr<T>, U, V, W, X>::const_iterator HashMap<RefPtr<T>, U, V, W, X>::find(RawKeyType key) const 187 { 188 return m_impl.template find<Translator>(key); 189 } 190 191 template<typename T, typename U, typename V, typename W, typename X> 192 inline bool HashMap<RefPtr<T>, U, V, W, X>::contains(const KeyType& key) const 193 { 194 return m_impl.contains(key); 195 } 196 197 template<typename T, typename U, typename V, typename W, typename X> 198 inline bool HashMap<RefPtr<T>, U, V, W, X>::contains(RawKeyType key) const 199 { 200 return m_impl.template contains<Translator>(key); 201 } 202 203 template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg> 204 template<typename V> 205 auto HashMap<RefPtr<KeyArg>, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::inlineAdd(const KeyType& key, V&& mapped) -> AddResult 206 { 207 return m_impl.template add<Translator>(key, std::forward<V>(mapped)); 208 } 209 210 template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg> 211 template<typename V> 212 auto HashMap<RefPtr<KeyArg>, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::inlineAdd(RawKeyType key, V&& mapped) -> AddResult 213 { 214 return m_impl.template add<Translator>(key, std::forward<V>(mapped)); 215 } 216 217 template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg> 218 template<typename V> 219 auto HashMap<RefPtr<KeyArg>, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::set(const KeyType& key, V&& value) -> AddResult 220 { 221 AddResult result = inlineAdd(key, std::forward<V>(value)); 222 if (!result.isNewEntry) { 223 // The inlineAdd call above found an existing hash table entry; we need to set the mapped value. 224 result.iterator->value = std::forward<V>(value); 225 } 226 return result; 227 } 228 229 template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg> 230 template<typename V> 231 auto HashMap<RefPtr<KeyArg>, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::set(RawKeyType key, V&& value) -> AddResult 232 { 233 AddResult result = inlineAdd(key, std::forward<V>(value)); 234 if (!result.isNewEntry) { 235 // The inlineAdd call above found an existing hash table entry; we need to set the mapped value. 236 result.iterator->value = std::forward<V>(value); 237 } 238 return result; 239 } 240 241 template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg> 242 template<typename V> 243 auto HashMap<RefPtr<KeyArg>, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::add(const KeyType& key, V&& value) -> AddResult 244 { 245 return inlineAdd(key, std::forward<V>(value)); 246 } 247 248 template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg> 249 template<typename V> 250 auto HashMap<RefPtr<KeyArg>, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::add(RawKeyType key, V&& value) -> AddResult 251 { 252 return inlineAdd(key, std::forward<V>(value)); 253 } 254 255 template<typename T, typename U, typename V, typename W, typename MappedTraits> 256 typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedPeekType 257 HashMap<RefPtr<T>, U, V, W, MappedTraits>::get(const KeyType& key) const 258 { 259 ValueType* entry = const_cast<HashTableType&>(m_impl).lookup(key); 260 if (!entry) 261 return MappedTraits::peek(MappedTraits::emptyValue()); 262 return MappedTraits::peek(entry->value); 263 } 264 265 template<typename T, typename U, typename V, typename W, typename MappedTraits> 266 typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedPeekType 267 inline HashMap<RefPtr<T>, U, V, W, MappedTraits>::inlineGet(RawKeyType key) const 268 { 269 ValueType* entry = const_cast<HashTableType&>(m_impl).template lookup<Translator>(key); 270 if (!entry) 271 return MappedTraits::peek(MappedTraits::emptyValue()); 272 return MappedTraits::peek(entry->value); 273 } 274 275 template<typename T, typename U, typename V, typename W, typename MappedTraits> 276 typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedPeekType 277 HashMap<RefPtr<T>, U, V, W, MappedTraits>::get(RawKeyType key) const 278 { 279 return inlineGet(key); 280 } 281 282 template<typename T, typename U, typename V, typename W, typename X> 283 inline bool HashMap<RefPtr<T>, U, V, W, X>::remove(iterator it) 284 { 285 if (it.m_impl == m_impl.end()) 286 return false; 287 m_impl.internalCheckTableConsistency(); 288 m_impl.removeWithoutEntryConsistencyCheck(it.m_impl); 289 return true; 290 } 291 292 template<typename T, typename U, typename V, typename W, typename X> 293 inline bool HashMap<RefPtr<T>, U, V, W, X>::remove(const KeyType& key) 294 { 295 return remove(find(key)); 296 } 297 298 template<typename T, typename U, typename V, typename W, typename X> 299 inline bool HashMap<RefPtr<T>, U, V, W, X>::remove(RawKeyType key) 300 { 301 return remove(find(key)); 302 } 303 304 template<typename T, typename U, typename V, typename W, typename X> 305 inline void HashMap<RefPtr<T>, U, V, W, X>::clear() 306 { 307 m_impl.clear(); 308 } 309 310 template<typename T, typename U, typename V, typename W, typename MappedTraits> 311 auto HashMap<RefPtr<T>, U, V, W, MappedTraits>::take(const KeyType& key) -> MappedType 312 { 313 iterator it = find(key); 314 if (it == end()) 315 return MappedTraits::emptyValue(); 316 MappedType value = WTF::move(it->value); 317 remove(it); 318 return value; 319 } 320 321 template<typename T, typename U, typename V, typename W, typename MappedTraits> 322 auto HashMap<RefPtr<T>, U, V, W, MappedTraits>::take(RawKeyType key) -> MappedType 323 { 324 iterator it = find(key); 325 if (it == end()) 326 return MappedTraits::emptyValue(); 327 MappedType value = WTF::move(it->value); 328 remove(it); 329 return value; 330 } 331 332} // namespace WTF 333 334#endif // RefPtrHashMap_h 335