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 WTF_HashMap_h 22 #define WTF_HashMap_h 23 24 #include "HashTable.h" 25 26 namespace WTF { 27 28 template<typename PairType> struct PairFirstExtractor; 29 30 template<typename KeyArg, typename MappedArg, typename HashArg = typename DefaultHash<KeyArg>::Hash, 31 typename KeyTraitsArg = HashTraits<KeyArg>, typename MappedTraitsArg = HashTraits<MappedArg> > 32 class HashMap { 33 WTF_MAKE_FAST_ALLOCATED; 34 private: 35 typedef KeyTraitsArg KeyTraits; 36 typedef MappedTraitsArg MappedTraits; 37 typedef PairHashTraits<KeyTraits, MappedTraits> ValueTraits; 38 39 public: 40 typedef typename KeyTraits::TraitType KeyType; 41 typedef typename MappedTraits::TraitType MappedType; 42 typedef typename ValueTraits::TraitType ValueType; 43 44 private: 45 typedef HashArg HashFunctions; 46 47 typedef HashTable<KeyType, ValueType, PairFirstExtractor<ValueType>, 48 HashFunctions, ValueTraits, KeyTraits> HashTableType; 49 50 public: 51 typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator; 52 typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator; 53 54 void swap(HashMap&); 55 56 int size() const; 57 int capacity() const; 58 bool isEmpty() const; 59 60 // iterators iterate over pairs of keys and values 61 iterator begin(); 62 iterator end(); 63 const_iterator begin() const; 64 const_iterator end() const; 65 66 iterator find(const KeyType&); 67 const_iterator find(const KeyType&) const; 68 bool contains(const KeyType&) const; 69 MappedType get(const KeyType&) const; 70 71 // replaces value but not key if key is already present 72 // return value is a pair of the iterator to the key location, 73 // and a boolean that's true if a new value was actually added 74 pair<iterator, bool> set(const KeyType&, const MappedType&); 75 76 // does nothing if key is already present 77 // return value is a pair of the iterator to the key location, 78 // and a boolean that's true if a new value was actually added 79 pair<iterator, bool> add(const KeyType&, const MappedType&); 80 81 void remove(const KeyType&); 82 void remove(iterator); 83 void clear(); 84 85 MappedType take(const KeyType&); // efficient combination of get with remove 86 87 // An alternate version of find() that finds the object by hashing and comparing 88 // with some other type, to avoid the cost of type conversion. HashTranslator 89 // must have the following function members: 90 // static unsigned hash(const T&); 91 // static bool equal(const ValueType&, const T&); 92 template<typename T, typename HashTranslator> iterator find(const T&); 93 template<typename T, typename HashTranslator> const_iterator find(const T&) const; 94 template<typename T, typename HashTranslator> bool contains(const T&) const; 95 96 // An alternate version of add() that finds the object by hashing and comparing 97 // with some other type, to avoid the cost of type conversion if the object is already 98 // in the table. HashTranslator must have the following function members: 99 // static unsigned hash(const T&); 100 // static bool equal(const ValueType&, const T&); 101 // static translate(ValueType&, const T&, unsigned hashCode); 102 template<typename T, typename HashTranslator> pair<iterator, bool> add(const T&, const MappedType&); 103 104 void checkConsistency() const; 105 106 private: 107 pair<iterator, bool> inlineAdd(const KeyType&, const MappedType&); 108 109 HashTableType m_impl; 110 }; 111 112 template<typename PairType> struct PairFirstExtractor { 113 static const typename PairType::first_type& extract(const PairType& p) { return p.first; } 114 }; 115 116 template<typename ValueType, typename ValueTraits, typename HashFunctions> 117 struct HashMapTranslator { 118 typedef typename ValueType::first_type KeyType; 119 typedef typename ValueType::second_type MappedType; 120 121 static unsigned hash(const KeyType& key) { return HashFunctions::hash(key); } 122 static bool equal(const KeyType& a, const KeyType& b) { return HashFunctions::equal(a, b); } 123 static void translate(ValueType& location, const KeyType& key, const MappedType& mapped) 124 { 125 location.first = key; 126 location.second = mapped; 127 } 128 }; 129 130 template<typename ValueType, typename ValueTraits, typename T, typename Translator> 131 struct HashMapTranslatorAdapter { 132 typedef typename ValueType::first_type KeyType; 133 typedef typename ValueType::second_type MappedType; 134 135 static unsigned hash(const T& key) { return Translator::hash(key); } 136 static bool equal(const KeyType& a, const T& b) { return Translator::equal(a, b); } 137 static void translate(ValueType& location, const T& key, const MappedType& mapped, unsigned hashCode) 138 { 139 Translator::translate(location.first, key, hashCode); 140 location.second = mapped; 141 } 142 }; 143 144 template<typename T, typename U, typename V, typename W, typename X> 145 inline void HashMap<T, U, V, W, X>::swap(HashMap& other) 146 { 147 m_impl.swap(other.m_impl); 148 } 149 150 template<typename T, typename U, typename V, typename W, typename X> 151 inline int HashMap<T, U, V, W, X>::size() const 152 { 153 return m_impl.size(); 154 } 155 156 template<typename T, typename U, typename V, typename W, typename X> 157 inline int HashMap<T, U, V, W, X>::capacity() const 158 { 159 return m_impl.capacity(); 160 } 161 162 template<typename T, typename U, typename V, typename W, typename X> 163 inline bool HashMap<T, U, V, W, X>::isEmpty() const 164 { 165 return m_impl.isEmpty(); 166 } 167 168 template<typename T, typename U, typename V, typename W, typename X> 169 inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::begin() 170 { 171 return m_impl.begin(); 172 } 173 174 template<typename T, typename U, typename V, typename W, typename X> 175 inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::end() 176 { 177 return m_impl.end(); 178 } 179 180 template<typename T, typename U, typename V, typename W, typename X> 181 inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::begin() const 182 { 183 return m_impl.begin(); 184 } 185 186 template<typename T, typename U, typename V, typename W, typename X> 187 inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::end() const 188 { 189 return m_impl.end(); 190 } 191 192 template<typename T, typename U, typename V, typename W, typename X> 193 inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::find(const KeyType& key) 194 { 195 return m_impl.find(key); 196 } 197 198 template<typename T, typename U, typename V, typename W, typename X> 199 inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::find(const KeyType& key) const 200 { 201 return m_impl.find(key); 202 } 203 204 template<typename T, typename U, typename V, typename W, typename X> 205 inline bool HashMap<T, U, V, W, X>::contains(const KeyType& key) const 206 { 207 return m_impl.contains(key); 208 } 209 210 template<typename T, typename U, typename V, typename W, typename X> 211 template<typename TYPE, typename HashTranslator> 212 inline typename HashMap<T, U, V, W, X>::iterator 213 HashMap<T, U, V, W, X>::find(const TYPE& value) 214 { 215 typedef HashMapTranslatorAdapter<ValueType, ValueTraits, TYPE, HashTranslator> Adapter; 216 return m_impl.template find<TYPE, Adapter>(value); 217 } 218 219 template<typename T, typename U, typename V, typename W, typename X> 220 template<typename TYPE, typename HashTranslator> 221 inline typename HashMap<T, U, V, W, X>::const_iterator 222 HashMap<T, U, V, W, X>::find(const TYPE& value) const 223 { 224 typedef HashMapTranslatorAdapter<ValueType, ValueTraits, TYPE, HashTranslator> Adapter; 225 return m_impl.template find<TYPE, Adapter>(value); 226 } 227 228 template<typename T, typename U, typename V, typename W, typename X> 229 template<typename TYPE, typename HashTranslator> 230 inline bool 231 HashMap<T, U, V, W, X>::contains(const TYPE& value) const 232 { 233 typedef HashMapTranslatorAdapter<ValueType, ValueTraits, TYPE, HashTranslator> Adapter; 234 return m_impl.template contains<TYPE, Adapter>(value); 235 } 236 237 template<typename T, typename U, typename V, typename W, typename X> 238 inline pair<typename HashMap<T, U, V, W, X>::iterator, bool> 239 HashMap<T, U, V, W, X>::inlineAdd(const KeyType& key, const MappedType& mapped) 240 { 241 typedef HashMapTranslator<ValueType, ValueTraits, HashFunctions> TranslatorType; 242 return m_impl.template add<KeyType, MappedType, TranslatorType>(key, mapped); 243 } 244 245 template<typename T, typename U, typename V, typename W, typename X> 246 pair<typename HashMap<T, U, V, W, X>::iterator, bool> 247 HashMap<T, U, V, W, X>::set(const KeyType& key, const MappedType& mapped) 248 { 249 pair<iterator, bool> result = inlineAdd(key, mapped); 250 if (!result.second) { 251 // add call above didn't change anything, so set the mapped value 252 result.first->second = mapped; 253 } 254 return result; 255 } 256 257 template<typename T, typename U, typename V, typename W, typename X> 258 template<typename TYPE, typename HashTranslator> 259 pair<typename HashMap<T, U, V, W, X>::iterator, bool> 260 HashMap<T, U, V, W, X>::add(const TYPE& key, const MappedType& value) 261 { 262 typedef HashMapTranslatorAdapter<ValueType, ValueTraits, TYPE, HashTranslator> Adapter; 263 return m_impl.template addPassingHashCode<TYPE, MappedType, Adapter>(key, value); 264 } 265 266 template<typename T, typename U, typename V, typename W, typename X> 267 pair<typename HashMap<T, U, V, W, X>::iterator, bool> 268 HashMap<T, U, V, W, X>::add(const KeyType& key, const MappedType& mapped) 269 { 270 return inlineAdd(key, mapped); 271 } 272 273 template<typename T, typename U, typename V, typename W, typename MappedTraits> 274 typename HashMap<T, U, V, W, MappedTraits>::MappedType 275 HashMap<T, U, V, W, MappedTraits>::get(const KeyType& key) const 276 { 277 ValueType* entry = const_cast<HashTableType&>(m_impl).lookup(key); 278 if (!entry) 279 return MappedTraits::emptyValue(); 280 return entry->second; 281 } 282 283 template<typename T, typename U, typename V, typename W, typename X> 284 inline void HashMap<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<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<T, U, V, W, X>::clear() 300 { 301 m_impl.clear(); 302 } 303 304 template<typename T, typename U, typename V, typename W, typename MappedTraits> 305 typename HashMap<T, U, V, W, MappedTraits>::MappedType 306 HashMap<T, U, V, W, MappedTraits>::take(const KeyType& key) 307 { 308 // This can probably be made more efficient to avoid ref/deref churn. 309 iterator it = find(key); 310 if (it == end()) 311 return MappedTraits::emptyValue(); 312 typename HashMap<T, U, V, W, MappedTraits>::MappedType result = it->second; 313 remove(it); 314 return result; 315 } 316 317 template<typename T, typename U, typename V, typename W, typename X> 318 inline void HashMap<T, U, V, W, X>::checkConsistency() const 319 { 320 m_impl.checkTableConsistency(); 321 } 322 323 324 template<typename T, typename U, typename V, typename W, typename X> 325 bool operator==(const HashMap<T, U, V, W, X>& a, const HashMap<T, U, V, W, X>& b) 326 { 327 if (a.size() != b.size()) 328 return false; 329 330 typedef typename HashMap<T, U, V, W, X>::const_iterator const_iterator; 331 332 const_iterator end = a.end(); 333 const_iterator notFound = b.end(); 334 for (const_iterator it = a.begin(); it != end; ++it) { 335 const_iterator bPos = b.find(it->first); 336 if (bPos == notFound || it->second != bPos->second) 337 return false; 338 } 339 340 return true; 341 } 342 343 template<typename T, typename U, typename V, typename W, typename X> 344 inline bool operator!=(const HashMap<T, U, V, W, X>& a, const HashMap<T, U, V, W, X>& b) 345 { 346 return !(a == b); 347 } 348 349 template<typename MappedType, typename HashTableType> 350 void deleteAllPairSeconds(HashTableType& collection) 351 { 352 typedef typename HashTableType::const_iterator iterator; 353 iterator end = collection.end(); 354 for (iterator it = collection.begin(); it != end; ++it) 355 delete it->second; 356 } 357 358 template<typename T, typename U, typename V, typename W, typename X> 359 inline void deleteAllValues(const HashMap<T, U, V, W, X>& collection) 360 { 361 deleteAllPairSeconds<typename HashMap<T, U, V, W, X>::MappedType>(collection); 362 } 363 364 template<typename KeyType, typename HashTableType> 365 void deleteAllPairFirsts(HashTableType& collection) 366 { 367 typedef typename HashTableType::const_iterator iterator; 368 iterator end = collection.end(); 369 for (iterator it = collection.begin(); it != end; ++it) 370 delete it->first; 371 } 372 373 template<typename T, typename U, typename V, typename W, typename X> 374 inline void deleteAllKeys(const HashMap<T, U, V, W, X>& collection) 375 { 376 deleteAllPairFirsts<typename HashMap<T, U, V, W, X>::KeyType>(collection); 377 } 378 379 template<typename T, typename U, typename V, typename W, typename X, typename Y> 380 inline void copyKeysToVector(const HashMap<T, U, V, W, X>& collection, Y& vector) 381 { 382 typedef typename HashMap<T, U, V, W, X>::const_iterator::Keys iterator; 383 384 vector.resize(collection.size()); 385 386 iterator it = collection.begin().keys(); 387 iterator end = collection.end().keys(); 388 for (unsigned i = 0; it != end; ++it, ++i) 389 vector[i] = *it; 390 } 391 392 template<typename T, typename U, typename V, typename W, typename X, typename Y> 393 inline void copyValuesToVector(const HashMap<T, U, V, W, X>& collection, Y& vector) 394 { 395 typedef typename HashMap<T, U, V, W, X>::const_iterator::Values iterator; 396 397 vector.resize(collection.size()); 398 399 iterator it = collection.begin().values(); 400 iterator end = collection.end().values(); 401 for (unsigned i = 0; it != end; ++it, ++i) 402 vector[i] = *it; 403 } 404 405 } // namespace WTF 406 407 using WTF::HashMap; 408 409 #include "RefPtrHashMap.h" 410 411 #endif /* WTF_HashMap_h */ 412
