1 /* 2 * Copyright (C) 2005, 2006, 2007, 2008 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 24 namespace WTF { 25 26 // This specialization is a direct copy of HashMap, with overloaded functions 27 // to allow for lookup by pointer instead of RefPtr, avoiding ref-count churn. 28 29 // FIXME: Find a better way that doesn't require an entire copy of the HashMap template. 30 31 template<typename RawKeyType, typename ValueType, typename ValueTraits, typename HashFunctions> 32 struct RefPtrHashMapRawKeyTranslator { 33 typedef typename ValueType::first_type KeyType; 34 typedef typename ValueType::second_type MappedType; 35 typedef typename ValueTraits::FirstTraits KeyTraits; 36 typedef typename ValueTraits::SecondTraits MappedTraits; 37 38 static unsigned hash(RawKeyType key) { return HashFunctions::hash(key); } 39 static bool equal(const KeyType& a, RawKeyType b) { return HashFunctions::equal(a, b); } 40 static void translate(ValueType& location, RawKeyType key, const MappedType& mapped) 41 { 42 location.first = key; 43 location.second = mapped; 44 } 45 }; 46 47 template<typename T, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg> 48 class HashMap<RefPtr<T>, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg> { 49 WTF_MAKE_FAST_ALLOCATED; 50 private: 51 typedef KeyTraitsArg KeyTraits; 52 typedef MappedTraitsArg MappedTraits; 53 typedef PairHashTraits<KeyTraits, MappedTraits> ValueTraits; 54 55 public: 56 typedef typename KeyTraits::TraitType KeyType; 57 typedef T* RawKeyType; 58 typedef typename MappedTraits::TraitType MappedType; 59 typedef typename ValueTraits::TraitType ValueType; 60 61 private: 62 typedef HashArg HashFunctions; 63 64 typedef HashTable<KeyType, ValueType, PairFirstExtractor<ValueType>, 65 HashFunctions, ValueTraits, KeyTraits> HashTableType; 66 67 typedef RefPtrHashMapRawKeyTranslator<RawKeyType, ValueType, ValueTraits, HashFunctions> 68 RawKeyTranslator; 69 70 public: 71 typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator; 72 typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator; 73 74 void swap(HashMap&); 75 76 int size() const; 77 int capacity() const; 78 bool isEmpty() const; 79 80 // iterators iterate over pairs of keys and values 81 iterator begin(); 82 iterator end(); 83 const_iterator begin() const; 84 const_iterator end() const; 85 86 iterator find(const KeyType&); 87 iterator find(RawKeyType); 88 const_iterator find(const KeyType&) const; 89 const_iterator find(RawKeyType) const; 90 bool contains(const KeyType&) const; 91 bool contains(RawKeyType) const; 92 MappedType get(const KeyType&) const; 93 MappedType get(RawKeyType) const; 94 MappedType inlineGet(RawKeyType) const; 95 96 // replaces value but not key if key is already present 97 // return value is a pair of the iterator to the key location, 98 // and a boolean that's true if a new value was actually added 99 pair<iterator, bool> set(const KeyType&, const MappedType&); 100 pair<iterator, bool> set(RawKeyType, const MappedType&); 101 102 // does nothing if key is already present 103 // return value is a pair of the iterator to the key location, 104 // and a boolean that's true if a new value was actually added 105 pair<iterator, bool> add(const KeyType&, const MappedType&); 106 pair<iterator, bool> add(RawKeyType, const MappedType&); 107 108 void remove(const KeyType&); 109 void remove(RawKeyType); 110 void remove(iterator); 111 void clear(); 112 113 MappedType take(const KeyType&); // efficient combination of get with remove 114 MappedType take(RawKeyType); // efficient combination of get with remove 115 116 private: 117 pair<iterator, bool> inlineAdd(const KeyType&, const MappedType&); 118 pair<iterator, bool> inlineAdd(RawKeyType, const MappedType&); 119 120 HashTableType m_impl; 121 }; 122 123 template<typename T, typename U, typename V, typename W, typename X> 124 inline void HashMap<RefPtr<T>, U, V, W, X>::swap(HashMap& other) 125 { 126 m_impl.swap(other.m_impl); 127 } 128 129 template<typename T, typename U, typename V, typename W, typename X> 130 inline int HashMap<RefPtr<T>, U, V, W, X>::size() const 131 { 132 return m_impl.size(); 133 } 134 135 template<typename T, typename U, typename V, typename W, typename X> 136 inline int HashMap<RefPtr<T>, U, V, W, X>::capacity() const 137 { 138 return m_impl.capacity(); 139 } 140 141 template<typename T, typename U, typename V, typename W, typename X> 142 inline bool HashMap<RefPtr<T>, U, V, W, X>::isEmpty() const 143 { 144 return m_impl.isEmpty(); 145 } 146 147 template<typename T, typename U, typename V, typename W, typename X> 148 inline typename HashMap<RefPtr<T>, U, V, W, X>::iterator HashMap<RefPtr<T>, U, V, W, X>::begin() 149 { 150 return m_impl.begin(); 151 } 152 153 template<typename T, typename U, typename V, typename W, typename X> 154 inline typename HashMap<RefPtr<T>, U, V, W, X>::iterator HashMap<RefPtr<T>, U, V, W, X>::end() 155 { 156 return m_impl.end(); 157 } 158 159 template<typename T, typename U, typename V, typename W, typename X> 160 inline typename HashMap<RefPtr<T>, U, V, W, X>::const_iterator HashMap<RefPtr<T>, U, V, W, X>::begin() const 161 { 162 return m_impl.begin(); 163 } 164 165 template<typename T, typename U, typename V, typename W, typename X> 166 inline typename HashMap<RefPtr<T>, U, V, W, X>::const_iterator HashMap<RefPtr<T>, U, V, W, X>::end() const 167 { 168 return m_impl.end(); 169 } 170 171 template<typename T, typename U, typename V, typename W, typename X> 172 inline typename HashMap<RefPtr<T>, U, V, W, X>::iterator HashMap<RefPtr<T>, U, V, W, X>::find(const KeyType& key) 173 { 174 return m_impl.find(key); 175 } 176 177 template<typename T, typename U, typename V, typename W, typename X> 178 inline typename HashMap<RefPtr<T>, U, V, W, X>::iterator HashMap<RefPtr<T>, U, V, W, X>::find(RawKeyType key) 179 { 180 return m_impl.template find<RawKeyType, RawKeyTranslator>(key); 181 } 182 183 template<typename T, typename U, typename V, typename W, typename X> 184 inline typename HashMap<RefPtr<T>, U, V, W, X>::const_iterator HashMap<RefPtr<T>, U, V, W, X>::find(const KeyType& key) const 185 { 186 return m_impl.find(key); 187 } 188 189 template<typename T, typename U, typename V, typename W, typename X> 190 inline typename HashMap<RefPtr<T>, U, V, W, X>::const_iterator HashMap<RefPtr<T>, U, V, W, X>::find(RawKeyType key) const 191 { 192 return m_impl.template find<RawKeyType, RawKeyTranslator>(key); 193 } 194 195 template<typename T, typename U, typename V, typename W, typename X> 196 inline bool HashMap<RefPtr<T>, U, V, W, X>::contains(const KeyType& key) const 197 { 198 return m_impl.contains(key); 199 } 200 201 template<typename T, typename U, typename V, typename W, typename X> 202 inline bool HashMap<RefPtr<T>, U, V, W, X>::contains(RawKeyType key) const 203 { 204 return m_impl.template contains<RawKeyType, RawKeyTranslator>(key); 205 } 206 207 template<typename T, typename U, typename V, typename W, typename X> 208 inline pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool> 209 HashMap<RefPtr<T>, U, V, W, X>::inlineAdd(const KeyType& key, const MappedType& mapped) 210 { 211 typedef HashMapTranslator<ValueType, ValueTraits, HashFunctions> TranslatorType; 212 return m_impl.template add<KeyType, MappedType, TranslatorType>(key, mapped); 213 } 214 215 template<typename T, typename U, typename V, typename W, typename X> 216 inline pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool> 217 HashMap<RefPtr<T>, U, V, W, X>::inlineAdd(RawKeyType key, const MappedType& mapped) 218 { 219 return m_impl.template add<RawKeyType, MappedType, RawKeyTranslator>(key, mapped); 220 } 221 222 template<typename T, typename U, typename V, typename W, typename X> 223 pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool> 224 HashMap<RefPtr<T>, U, V, W, X>::set(const KeyType& key, const MappedType& mapped) 225 { 226 pair<iterator, bool> result = inlineAdd(key, mapped); 227 if (!result.second) { 228 // add call above didn't change anything, so set the mapped value 229 result.first->second = mapped; 230 } 231 return result; 232 } 233 234 template<typename T, typename U, typename V, typename W, typename X> 235 pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool> 236 HashMap<RefPtr<T>, U, V, W, X>::set(RawKeyType key, const MappedType& mapped) 237 { 238 pair<iterator, bool> result = inlineAdd(key, mapped); 239 if (!result.second) { 240 // add call above didn't change anything, so set the mapped value 241 result.first->second = mapped; 242 } 243 return result; 244 } 245 246 template<typename T, typename U, typename V, typename W, typename X> 247 pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool> 248 HashMap<RefPtr<T>, U, V, W, X>::add(const KeyType& key, const MappedType& mapped) 249 { 250 return inlineAdd(key, mapped); 251 } 252 253 template<typename T, typename U, typename V, typename W, typename X> 254 pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool> 255 HashMap<RefPtr<T>, U, V, W, X>::add(RawKeyType key, const MappedType& mapped) 256 { 257 return inlineAdd(key, mapped); 258 } 259 260 template<typename T, typename U, typename V, typename W, typename MappedTraits> 261 typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType 262 HashMap<RefPtr<T>, U, V, W, MappedTraits>::get(const KeyType& key) const 263 { 264 ValueType* entry = const_cast<HashTableType&>(m_impl).lookup(key); 265 if (!entry) 266 return MappedTraits::emptyValue(); 267 return entry->second; 268 } 269 270 template<typename T, typename U, typename V, typename W, typename MappedTraits> 271 typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType 272 inline HashMap<RefPtr<T>, U, V, W, MappedTraits>::inlineGet(RawKeyType key) const 273 { 274 ValueType* entry = const_cast<HashTableType&>(m_impl).template lookup<RawKeyType, RawKeyTranslator>(key); 275 if (!entry) 276 return MappedTraits::emptyValue(); 277 return entry->second; 278 } 279 280 template<typename T, typename U, typename V, typename W, typename MappedTraits> 281 typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType 282 HashMap<RefPtr<T>, U, V, W, MappedTraits>::get(RawKeyType key) const 283 { 284 return inlineGet(key); 285 } 286 287 template<typename T, typename U, typename V, typename W, typename X> 288 inline void HashMap<RefPtr<T>, U, V, W, X>::remove(iterator it) 289 { 290 if (it.m_impl == m_impl.end()) 291 return; 292 m_impl.internalCheckTableConsistency(); 293 m_impl.removeWithoutEntryConsistencyCheck(it.m_impl); 294 } 295 296 template<typename T, typename U, typename V, typename W, typename X> 297 inline void HashMap<RefPtr<T>, U, V, W, X>::remove(const KeyType& key) 298 { 299 remove(find(key)); 300 } 301 302 template<typename T, typename U, typename V, typename W, typename X> 303 inline void HashMap<RefPtr<T>, U, V, W, X>::remove(RawKeyType key) 304 { 305 remove(find(key)); 306 } 307 308 template<typename T, typename U, typename V, typename W, typename X> 309 inline void HashMap<RefPtr<T>, U, V, W, X>::clear() 310 { 311 m_impl.clear(); 312 } 313 314 template<typename T, typename U, typename V, typename W, typename MappedTraits> 315 typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType 316 HashMap<RefPtr<T>, U, V, W, MappedTraits>::take(const KeyType& key) 317 { 318 // This can probably be made more efficient to avoid ref/deref churn. 319 iterator it = find(key); 320 if (it == end()) 321 return MappedTraits::emptyValue(); 322 typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType result = it->second; 323 remove(it); 324 return result; 325 } 326 327 template<typename T, typename U, typename V, typename W, typename MappedTraits> 328 typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType 329 HashMap<RefPtr<T>, U, V, W, MappedTraits>::take(RawKeyType key) 330 { 331 // This can probably be made more efficient to avoid ref/deref churn. 332 iterator it = find(key); 333 if (it == end()) 334 return MappedTraits::emptyValue(); 335 typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType result = it->second; 336 remove(it); 337 return result; 338 } 339 340 } // namespace WTF 341 342 #endif // RefPtrHashMap_h 343
