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