00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #ifndef WTF_HashMap_h
00023 #define WTF_HashMap_h
00024
00025 #include "HashTable.h"
00026
00027 namespace WTF {
00028
00029 template<typename PairType> struct PairFirstExtractor;
00030
00031 template<typename KeyArg, typename MappedArg, typename HashArg = typename DefaultHash<KeyArg>::Hash,
00032 typename KeyTraitsArg = HashTraits<KeyArg>, typename MappedTraitsArg = HashTraits<MappedArg> >
00033 class HashMap {
00034 private:
00035 typedef KeyTraitsArg KeyTraits;
00036 typedef MappedTraitsArg MappedTraits;
00037 typedef PairHashTraits<KeyTraits, MappedTraits> ValueTraits;
00038
00039 public:
00040 typedef typename KeyTraits::TraitType KeyType;
00041 typedef typename MappedTraits::TraitType MappedType;
00042 typedef typename ValueTraits::TraitType ValueType;
00043
00044 private:
00045 typedef HashArg HashFunctions;
00046
00047 typedef HashTable<KeyType, ValueType, PairFirstExtractor<ValueType>,
00048 HashFunctions, ValueTraits, KeyTraits> HashTableType;
00049
00050 public:
00051 typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator;
00052 typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator;
00053
00054 void swap(HashMap&);
00055
00056 int size() const;
00057 int capacity() const;
00058 bool isEmpty() const;
00059
00060
00061 iterator begin();
00062 iterator end();
00063 const_iterator begin() const;
00064 const_iterator end() const;
00065
00066 iterator find(const KeyType&);
00067 const_iterator find(const KeyType&) const;
00068 bool contains(const KeyType&) const;
00069 MappedType get(const KeyType&) const;
00070
00071
00072
00073
00074 pair<iterator, bool> set(const KeyType&, const MappedType&);
00075
00076
00077
00078
00079 pair<iterator, bool> add(const KeyType&, const MappedType&);
00080
00081 void remove(const KeyType&);
00082 void remove(iterator);
00083 void clear();
00084
00085 MappedType take(const KeyType&);
00086
00087 private:
00088 pair<iterator, bool> inlineAdd(const KeyType&, const MappedType&);
00089
00090 HashTableType m_impl;
00091 };
00092
00093 template<typename PairType> struct PairFirstExtractor {
00094 static const typename PairType::first_type& extract(const PairType& p) { return p.first; }
00095 };
00096
00097 template<typename ValueType, typename ValueTraits, typename HashFunctions>
00098 struct HashMapTranslator {
00099 typedef typename ValueType::first_type KeyType;
00100 typedef typename ValueType::second_type MappedType;
00101
00102 static unsigned hash(const KeyType& key) { return HashFunctions::hash(key); }
00103 static bool equal(const KeyType& a, const KeyType& b) { return HashFunctions::equal(a, b); }
00104 static void translate(ValueType& location, const KeyType& key, const MappedType& mapped)
00105 {
00106 location.first = key;
00107 location.second = mapped;
00108 }
00109 };
00110
00111 template<typename T, typename U, typename V, typename W, typename X>
00112 inline void HashMap<T, U, V, W, X>::swap(HashMap& other)
00113 {
00114 m_impl.swap(other.m_impl);
00115 }
00116
00117 template<typename T, typename U, typename V, typename W, typename X>
00118 inline int HashMap<T, U, V, W, X>::size() const
00119 {
00120 return m_impl.size();
00121 }
00122
00123 template<typename T, typename U, typename V, typename W, typename X>
00124 inline int HashMap<T, U, V, W, X>::capacity() const
00125 {
00126 return m_impl.capacity();
00127 }
00128
00129 template<typename T, typename U, typename V, typename W, typename X>
00130 inline bool HashMap<T, U, V, W, X>::isEmpty() const
00131 {
00132 return m_impl.isEmpty();
00133 }
00134
00135 template<typename T, typename U, typename V, typename W, typename X>
00136 inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::begin()
00137 {
00138 return m_impl.begin();
00139 }
00140
00141 template<typename T, typename U, typename V, typename W, typename X>
00142 inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::end()
00143 {
00144 return m_impl.end();
00145 }
00146
00147 template<typename T, typename U, typename V, typename W, typename X>
00148 inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::begin() const
00149 {
00150 return m_impl.begin();
00151 }
00152
00153 template<typename T, typename U, typename V, typename W, typename X>
00154 inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::end() const
00155 {
00156 return m_impl.end();
00157 }
00158
00159 template<typename T, typename U, typename V, typename W, typename X>
00160 inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::find(const KeyType& key)
00161 {
00162 return m_impl.find(key);
00163 }
00164
00165 template<typename T, typename U, typename V, typename W, typename X>
00166 inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::find(const KeyType& key) const
00167 {
00168 return m_impl.find(key);
00169 }
00170
00171 template<typename T, typename U, typename V, typename W, typename X>
00172 inline bool HashMap<T, U, V, W, X>::contains(const KeyType& key) const
00173 {
00174 return m_impl.contains(key);
00175 }
00176
00177 template<typename T, typename U, typename V, typename W, typename X>
00178 inline pair<typename HashMap<T, U, V, W, X>::iterator, bool>
00179 HashMap<T, U, V, W, X>::inlineAdd(const KeyType& key, const MappedType& mapped)
00180 {
00181 typedef HashMapTranslator<ValueType, ValueTraits, HashFunctions> TranslatorType;
00182 return m_impl.template add<KeyType, MappedType, TranslatorType>(key, mapped);
00183 }
00184
00185 template<typename T, typename U, typename V, typename W, typename X>
00186 pair<typename HashMap<T, U, V, W, X>::iterator, bool>
00187 HashMap<T, U, V, W, X>::set(const KeyType& key, const MappedType& mapped)
00188 {
00189 pair<iterator, bool> result = inlineAdd(key, mapped);
00190 if (!result.second) {
00191
00192 result.first->second = mapped;
00193 }
00194 return result;
00195 }
00196
00197 template<typename T, typename U, typename V, typename W, typename X>
00198 pair<typename HashMap<T, U, V, W, X>::iterator, bool>
00199 HashMap<T, U, V, W, X>::add(const KeyType& key, const MappedType& mapped)
00200 {
00201 return inlineAdd(key, mapped);
00202 }
00203
00204 template<typename T, typename U, typename V, typename W, typename MappedTraits>
00205 typename HashMap<T, U, V, W, MappedTraits>::MappedType
00206 HashMap<T, U, V, W, MappedTraits>::get(const KeyType& key) const
00207 {
00208 ValueType* entry = const_cast<HashTableType&>(m_impl).lookup(key);
00209 if (!entry)
00210 return MappedTraits::emptyValue();
00211 return entry->second;
00212 }
00213
00214 template<typename T, typename U, typename V, typename W, typename X>
00215 inline void HashMap<T, U, V, W, X>::remove(iterator it)
00216 {
00217 if (it.m_impl == m_impl.end())
00218 return;
00219 m_impl.checkTableConsistency();
00220 m_impl.removeWithoutEntryConsistencyCheck(it.m_impl);
00221 }
00222
00223 template<typename T, typename U, typename V, typename W, typename X>
00224 inline void HashMap<T, U, V, W, X>::remove(const KeyType& key)
00225 {
00226 remove(find(key));
00227 }
00228
00229 template<typename T, typename U, typename V, typename W, typename X>
00230 inline void HashMap<T, U, V, W, X>::clear()
00231 {
00232 m_impl.clear();
00233 }
00234
00235 template<typename T, typename U, typename V, typename W, typename MappedTraits>
00236 typename HashMap<T, U, V, W, MappedTraits>::MappedType
00237 HashMap<T, U, V, W, MappedTraits>::take(const KeyType& key)
00238 {
00239
00240 iterator it = find(key);
00241 if (it == end())
00242 return MappedTraits::emptyValue();
00243 typename HashMap<T, U, V, W, MappedTraits>::MappedType result = it->second;
00244 remove(it);
00245 return result;
00246 }
00247
00248 template<typename T, typename U, typename V, typename W, typename X>
00249 bool operator==(const HashMap<T, U, V, W, X>& a, const HashMap<T, U, V, W, X>& b)
00250 {
00251 if (a.size() != b.size())
00252 return false;
00253
00254 typedef typename HashMap<T, U, V, W, X>::const_iterator const_iterator;
00255
00256 const_iterator end = a.end();
00257 const_iterator notFound = b.end();
00258 for (const_iterator it = a.begin(); it != end; ++it) {
00259 const_iterator bPos = b.find(it->first);
00260 if (bPos == notFound || it->second != bPos->second)
00261 return false;
00262 }
00263
00264 return true;
00265 }
00266
00267 template<typename T, typename U, typename V, typename W, typename X>
00268 inline bool operator!=(const HashMap<T, U, V, W, X>& a, const HashMap<T, U, V, W, X>& b)
00269 {
00270 return !(a == b);
00271 }
00272
00273 template<typename MappedType, typename HashTableType>
00274 void deleteAllPairSeconds(HashTableType& collection)
00275 {
00276 typedef typename HashTableType::const_iterator iterator;
00277 iterator end = collection.end();
00278 for (iterator it = collection.begin(); it != end; ++it)
00279 delete it->second;
00280 }
00281
00282 template<typename T, typename U, typename V, typename W, typename X>
00283 inline void deleteAllValues(const HashMap<T, U, V, W, X>& collection)
00284 {
00285 deleteAllPairSeconds<typename HashMap<T, U, V, W, X>::MappedType>(collection);
00286 }
00287
00288 template<typename KeyType, typename HashTableType>
00289 void deleteAllPairFirsts(HashTableType& collection)
00290 {
00291 typedef typename HashTableType::const_iterator iterator;
00292 iterator end = collection.end();
00293 for (iterator it = collection.begin(); it != end; ++it)
00294 delete it->first;
00295 }
00296
00297 template<typename T, typename U, typename V, typename W, typename X>
00298 inline void deleteAllKeys(const HashMap<T, U, V, W, X>& collection)
00299 {
00300 deleteAllPairFirsts<typename HashMap<T, U, V, W, X>::KeyType>(collection);
00301 }
00302
00303 template<typename T, typename U, typename V, typename W, typename X, typename Y>
00304 inline void copyKeysToVector(const HashMap<T, U, V, W, X>& collection, Y& vector)
00305 {
00306 typedef typename HashMap<T, U, V, W, X>::const_iterator::Keys iterator;
00307
00308 vector.resize(collection.size());
00309
00310 iterator it = collection.begin().keys();
00311 iterator end = collection.end().keys();
00312 for (unsigned i = 0; it != end; ++it, ++i)
00313 vector[i] = *it;
00314 }
00315
00316 template<typename T, typename U, typename V, typename W, typename X, typename Y>
00317 inline void copyValuesToVector(const HashMap<T, U, V, W, X>& collection, Y& vector)
00318 {
00319 typedef typename HashMap<T, U, V, W, X>::const_iterator::Values iterator;
00320
00321 vector.resize(collection.size());
00322
00323 iterator it = collection.begin().values();
00324 iterator end = collection.end().values();
00325 for (unsigned i = 0; it != end; ++it, ++i)
00326 vector[i] = *it;
00327 }
00328
00329 }
00330
00331 using WTF::HashMap;
00332
00333 #include "RefPtrHashMap.h"
00334
00335 #endif