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 namespace WTF { 22 23 // This specialization is a direct copy of HashMap, with overloaded functions 24 // to allow for lookup by pointer instead of RefPtr, avoiding ref-count churn. 25 26 // FIXME: Find a better way that doesn't require an entire copy of the HashMap template. 27 28 template<typename RawKeyType, typename ValueType, typename ValueTraits, typename HashFunctions> 29 struct RefPtrHashMapRawKeyTranslator { 30 typedef typename ValueType::first_type KeyType; 31 typedef typename ValueType::second_type MappedType; 32 typedef typename ValueTraits::FirstTraits KeyTraits; 33 typedef typename ValueTraits::SecondTraits MappedTraits; 34 35 static unsigned hash(RawKeyType key) { return HashFunctions::hash(key); } 36 static bool equal(const KeyType& a, RawKeyType b) { return HashFunctions::equal(a, b); } 37 static void translate(ValueType& location, RawKeyType key, const MappedType& mapped) 38 { 39 location.first = key; 40 location.second = mapped; 41 } 42 }; 43 44 template<typename T, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg> 45 class HashMap<RefPtr<T>, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg> : public FastAllocBase { 46 private: 47 typedef KeyTraitsArg KeyTraits; 48 typedef MappedTraitsArg MappedTraits; 49 typedef PairHashTraits<KeyTraits, MappedTraits> ValueTraits; 50 51 public: 52 typedef typename KeyTraits::TraitType KeyType; 53 typedef T* RawKeyType; 54 typedef typename MappedTraits::TraitType MappedType; 55 typedef typename ValueTraits::TraitType ValueType; 56 57 private: 58 typedef HashArg HashFunctions; 59 60 typedef HashTable<KeyType, ValueType, PairFirstExtractor<ValueType>, 61 HashFunctions, ValueTraits, KeyTraits> HashTableType; 62 63 typedef RefPtrHashMapRawKeyTranslator<RawKeyType, ValueType, ValueTraits, HashFunctions> 64 RawKeyTranslator; 65 66 public: 67 typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator; 68 typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator; 69 70 void swap(HashMap&); 71 72 int size() const; 73 int capacity() const; 74 bool isEmpty() const; 75 76 // iterators iterate over pairs of keys and values 77 iterator begin(); 78 iterator end(); 79 const_iterator begin() const; 80 const_iterator end() const; 81 82 iterator find(const KeyType&); 83 iterator find(RawKeyType); 84 const_iterator find(const KeyType&) const; 85 const_iterator find(RawKeyType) const; 86 bool contains(const KeyType&) const; 87 bool contains(RawKeyType) const; 88 MappedType get(const KeyType&) const; 89 MappedType get(RawKeyType) const; 90 MappedType inlineGet(RawKeyType) const; 91 92 // replaces value but not key if key is already present 93 // return value is a pair of the iterator to the key location, 94 // and a boolean that's true if a new value was actually added 95 pair<iterator, bool> set(const KeyType&, const MappedType&); 96 pair<iterator, bool> set(RawKeyType, const MappedType&); 97 98 // does nothing if key is already present 99 // return value is a pair of the iterator to the key location, 100 // and a boolean that's true if a new value was actually added 101 pair<iterator, bool> add(const KeyType&, const MappedType&); 102 pair<iterator, bool> add(RawKeyType, const MappedType&); 103 104 void remove(const KeyType&); 105 void remove(RawKeyType); 106 void remove(iterator); 107 void clear(); 108 109 MappedType take(const KeyType&); // efficient combination of get with remove 110 MappedType take(RawKeyType); // efficient combination of get with remove 111 112 private: 113 pair<iterator, bool> inlineAdd(const KeyType&, const MappedType&); 114 pair<iterator, bool> inlineAdd(RawKeyType, const MappedType&); 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<RawKeyType, RawKeyTranslator>(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<RawKeyType, RawKeyTranslator>(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<RawKeyType, RawKeyTranslator>(key); 201 } 202 203 template<typename T, typename U, typename V, typename W, typename X> 204 inline pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool> 205 HashMap<RefPtr<T>, U, V, W, X>::inlineAdd(const KeyType& key, const MappedType& mapped) 206 { 207 typedef HashMapTranslator<ValueType, ValueTraits, HashFunctions> TranslatorType; 208 return m_impl.template add<KeyType, MappedType, TranslatorType>(key, mapped); 209 } 210 211 template<typename T, typename U, typename V, typename W, typename X> 212 inline pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool> 213 HashMap<RefPtr<T>, U, V, W, X>::inlineAdd(RawKeyType key, const MappedType& mapped) 214 { 215 return m_impl.template add<RawKeyType, MappedType, RawKeyTranslator>(key, mapped); 216 } 217 218 template<typename T, typename U, typename V, typename W, typename X> 219 pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool> 220 HashMap<RefPtr<T>, U, V, W, X>::set(const KeyType& key, const MappedType& mapped) 221 { 222 pair<iterator, bool> result = inlineAdd(key, mapped); 223 if (!result.second) { 224 // add call above didn't change anything, so set the mapped value 225 result.first->second = mapped; 226 } 227 return result; 228 } 229 230 template<typename T, typename U, typename V, typename W, typename X> 231 pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool> 232 HashMap<RefPtr<T>, U, V, W, X>::set(RawKeyType key, const MappedType& mapped) 233 { 234 pair<iterator, bool> result = inlineAdd(key, mapped); 235 if (!result.second) { 236 // add call above didn't change anything, so set the mapped value 237 result.first->second = mapped; 238 } 239 return result; 240 } 241 242 template<typename T, typename U, typename V, typename W, typename X> 243 pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool> 244 HashMap<RefPtr<T>, U, V, W, X>::add(const KeyType& key, const MappedType& mapped) 245 { 246 return inlineAdd(key, mapped); 247 } 248 249 template<typename T, typename U, typename V, typename W, typename X> 250 pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool> 251 HashMap<RefPtr<T>, U, V, W, X>::add(RawKeyType key, const MappedType& mapped) 252 { 253 return inlineAdd(key, mapped); 254 } 255 256 template<typename T, typename U, typename V, typename W, typename MappedTraits> 257 typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType 258 HashMap<RefPtr<T>, U, V, W, MappedTraits>::get(const KeyType& key) const 259 { 260 ValueType* entry = const_cast<HashTableType&>(m_impl).lookup(key); 261 if (!entry) 262 return MappedTraits::emptyValue(); 263 return entry->second; 264 } 265 266 template<typename T, typename U, typename V, typename W, typename MappedTraits> 267 typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType 268 inline HashMap<RefPtr<T>, U, V, W, MappedTraits>::inlineGet(RawKeyType key) const 269 { 270 ValueType* entry = const_cast<HashTableType&>(m_impl).template lookup<RawKeyType, RawKeyTranslator>(key); 271 if (!entry) 272 return MappedTraits::emptyValue(); 273 return entry->second; 274 } 275 276 template<typename T, typename U, typename V, typename W, typename MappedTraits> 277 typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType 278 HashMap<RefPtr<T>, U, V, W, MappedTraits>::get(RawKeyType key) const 279 { 280 return inlineGet(key); 281 } 282 283 template<typename T, typename U, typename V, typename W, typename X> 284 inline void HashMap<RefPtr<T>, U, V, W, X>::remove(iterator it) 285 { 286 if (it.m_impl == m_impl.end()) 287 return; 288 m_impl.internalCheckTableConsistency(); 289 m_impl.removeWithoutEntryConsistencyCheck(it.m_impl); 290 } 291 292 template<typename T, typename U, typename V, typename W, typename X> 293 inline void HashMap<RefPtr<T>, U, V, W, X>::remove(const KeyType& key) 294 { 295 remove(find(key)); 296 } 297 298 template<typename T, typename U, typename V, typename W, typename X> 299 inline void HashMap<RefPtr<T>, U, V, W, X>::remove(RawKeyType key) 300 { 301 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 typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType 312 HashMap<RefPtr<T>, U, V, W, MappedTraits>::take(const KeyType& key) 313 { 314 // This can probably be made more efficient to avoid ref/deref churn. 315 iterator it = find(key); 316 if (it == end()) 317 return MappedTraits::emptyValue(); 318 typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType result = it->second; 319 remove(it); 320 return result; 321 } 322 323 template<typename T, typename U, typename V, typename W, typename MappedTraits> 324 typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType 325 HashMap<RefPtr<T>, U, V, W, MappedTraits>::take(RawKeyType key) 326 { 327 // This can probably be made more efficient to avoid ref/deref churn. 328 iterator it = find(key); 329 if (it == end()) 330 return MappedTraits::emptyValue(); 331 typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType result = it->second; 332 remove(it); 333 return result; 334 } 335 336 } // namespace WTF 337
